# US 12,762,099 B2 · Data storage system with automated correction of reference counts in addressing structure to avoid capacity leakage > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,762,099 B2 - Document ID: US12762099B2 - Status: Granted - Kind: B2 - Application number: 18/403,997 - Filed: 2024-01-04 - Published: 2025-07-10 - Granted: 2026-10-13 - Earliest claimed: 2024-01-04 - Assignees: Dell Products L.P. - Applicants: Dell Products L.P. - Inventors: Uri Shabi; Vladimir Shveidel; Jonathan Volij - Web page: https://patentgrep.com/patent/US12762099B2 ## CPC - G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method in a data storage system includes foreground processes that produce incorrect-high reference counts greater than corresponding numbers of actual references to associated data instances (e.g., virtual large blocks), representing loss of storage capacity. A background process corrects a reference count for a data instance by (1) copying the data instance to a new data instance with an initial reference count of zero and making the new data instance unavailable for reclaiming, (2) scanning a set of referencing structures for all references to the data instance, and for each reference (i) replacing the reference with a new reference to the new data instance, and (ii) incrementing the reference count of the new data instance, and (3) upon completing the scanning, making the new data instance available for eventual reclaiming based on its reference count reaching zero. The process restores reference count accuracy and reduces loss/leakage of storage capacity. ## Claims ### Claim 1 A method of operating a data storage system having data deduplication functionality including storage of unique data instances with associated reference counts each indicating a respective number of distinct references to the associated data instance, the storage system also having reclamation functionality that reclaims storage for reuse based on reference counts of associated data instances reaching zero, comprising: performing one or more foreground processes in a manner that produces incorrect-high reference counts greater than corresponding numbers of actual references to associated data instances, the incorrect-high reference counts resulting in loss of storage capacity by non-reclamation of data instances when their number of actual references has reached zero and their reference counts are non-zero; and performing a background process of correcting the reference counts by, for each of the unique data instances, (1) copying the unique data instance to a new data instance with an initial reference count of zero and making the new data instance unavailable for reclaiming, (2) scanning a set of referencing structures for all references to the unique data instance, and for each reference (i) replacing the reference with a new reference to the new data instance, and (ii) incrementing the reference count of the new data instance, and (3) upon completing the scanning, making the new data instance available for eventual reclaiming based on its reference count reaching zero; wherein replacing the reference with the new reference includes replacing a pointer to data of the unique data instance with a new pointer to the same data in the new data instance as part of a garbage collecting background process; wherein each of the unique data instances includes a respective associated existing reference count resulting from the foreground processes, the existing reference count having a non-zero value, and wherein the copying of each the unique data instances to a respective new data instance refrains from copying the existing reference count and instead creates a new reference count with the initial reference count of zero, for use in the subsequent steps 2 (i) and 2 (ii) for the new data instance; and wherein making the new data instance unavailable for reclaiming includes setting an indication that indicates to a reclamation service that the new data instance is unavailable for reclaiming, including while the new data instance has the initial reference count of zero. ### Claim 2 (depends on 1) The method of claim 1, wherein making the new data instance unavailable for reclaiming includes marking the new data instance as in-progress, and wherein making the new data instance available for eventual reclaiming includes clearing the in-progress marking. ### Claim 3 (depends on 1) The method of claim 1, wherein the referencing structures are included in a mapper structure organized and operative to map logical block addresses to physical block addresses. ### Claim 4 (depends on 3) The method of claim 3, wherein the mapper structure has a multi-layer organization including a tree-organized first layer including the referencing structures and a second layer having metadata of the data instances, the metadata including the reference counts. ### Claim 5 (depends on 4) The method of claim 4, wherein the referencing structures are leaf structures forming a lowest sub-layer of the tree-organized first layer, the leaf structures having a generally M:1 relationship to the data instances to effect the data deduplication functionality. ### Claim 6 (depends on 5) The method of claim 5, wherein the background process is a leaf fixer process being configured and operative to: (i) be executed in regular cycles and concurrently with regular user load that is dynamically modifying the references contained in the set of referencing structures; (ii) employ a working set of data instances whose references are to be fixed, and fix all references in the working set; (iii) traverse an entire relevant metadata space; and (iv) guarantee that all references have been updated and thereby enable safe removal of old data instances. ### Claim 7 (depends on 4) The method of claim 4, wherein the second layer includes virtual large blocks (VLBs) storing the reference counts and having pointers to respective physical large blocks (PLBs) providing underlying physical storage of the data instances. ### Claim 8 (depends on 1) The method of claim 1, wherein performing one or more foreground processes in a manner that produces incorrect-high reference counts includes one or more of (1) a performance optimization that intentionally trades performance for reduced capacity by refraining from updating a reference count, (2) decoupled, non-transactional updating of the references and the reference counts, and (3) errors including incorrect programming. ### Claim 9 (depends on 8) The method of claim 8, wherein the performance optimization includes a blind update of a reference count. ### Claim 10 (depends on 8) The method of claim 8, wherein the non-transactional updating includes updating a reference count without acquiring an exclusive lock for the data instance. ### Claim 11 A data storage system having storage processing circuitry and physical storage media, the storage processing circuitry executing computer program instructions to cause the data storage system to provide secondary data storage services to host computers including data deduplication functionality and reclamation functionality, the deduplication functionality including storage of unique data instances with associated reference counts each indicating a respective number of distinct references to the associated data instance, the reclamation functionality reclaiming storage for reuse based on reference counts of associated data instances reaching zero, the data storage services further including: performing one or more foreground processes in a manner that produces incorrect-high reference counts greater than corresponding numbers of actual references to associated data instances, the incorrect-high reference counts resulting in loss of storage capacity by non-reclamation of data instances when their number of actual references has reached zero and their reference counts are non-zero; and performing a background process of correcting the reference counts by, for each of the unique data instances, (1) copying the unique data instance to a new data instance with an initial reference count of zero and making the new data instance unavailable for reclaiming, (2) scanning a set of referencing structures for all references to the unique data instance, and for each reference (i) replacing the reference with a new reference to the new data instance, and (ii) incrementing the reference count of the new data instance, and (3) upon completing the scanning, making the new data instance available for eventual reclaiming based on its reference count reaching zero; wherein replacing the reference with the new reference includes replacing a pointer to data of the unique data instance with a new pointer to the same data in the new data instance as part of a garbage collecting background process; wherein each of the unique data instances includes a respective associated existing reference count resulting from the foreground processes, the existing reference count having a non-zero value, and wherein the copying of each the unique data instances to a respective new data instance refrains from copying the existing reference count and instead creates a new reference count with the initial reference count of zero, for use in the subsequent steps 2 (i) and 2 (ii) for the new data instance; and wherein making the new data instance unavailable for reclaiming includes setting an indication that indicates to a reclamation service that the new data instance is unavailable for reclaiming, including while the new data instance has the initial reference count of zero. ### Claim 12 (depends on 11) The data storage system of claim 11, wherein making the new data instance unavailable for reclaiming includes marking the new data instance as in-progress, and wherein making the new data instance available for eventual reclaiming includes clearing the in-progress marking. ### Claim 13 (depends on 11) The data storage system of claim 11, wherein the referencing structures are included in a mapper structure organized and operative to map logical block addresses to physical block addresses. ### Claim 14 (depends on 13) The data storage system of claim 13, wherein the mapper structure has a multi-layer organization including a tree-organized first layer including the referencing structures and a second layer having metadata of the data instances, the metadata including the reference counts. ### Claim 15 (depends on 14) The data storage system of claim 14, wherein the referencing structures are leaf structures forming a lowest sub-layer of the tree-organized first layer, the leaf structures having a generally M:1 relationship to the data instances to effect the data deduplication functionality. ### Claim 16 (depends on 15) The data storage system of claim 15, wherein the background process is a leaf fixer process being configured and operative to: (i) be executed in regular cycles and concurrently with regular user load that is dynamically modifying the references contained in the set of referencing structures; (ii) employ a working set of data instances whose references are to be fixed, and fix all references in the working set; (iii) traverse an entire relevant metadata space; and (iv) guarantee that all references have been updated and thereby enable safe removal of old data instances. ### Claim 17 (depends on 14) The data storage system of claim 14, wherein the second layer includes virtual large blocks (VLBs) storing the reference counts and having pointers to respective physical large blocks (PLBs) providing underlying physical storage of the data instances. ### Claim 18 (depends on 11) The data storage system of claim 11, wherein performing one or more foreground processes in a manner that produces incorrect-high reference counts includes one or more of (1) a performance optimization that intentionally trades performance for reduced capacity by refraining from updating a reference count, (2) decoupled, non-transactional updating of the references and the reference counts, and (3) errors including incorrect programming. ### Claim 19 (depends on 18) The data storage system of claim 18, wherein the performance optimization includes a blind update of a reference count, and wherein the non-transactional updating includes updating a reference count without acquiring an exclusive lock for the data instance. ### Claim 20 (depends on 1) The method of claim 1, wherein the new data instance has the initial reference count of zero after the unique data instance is copied to the new data instance.