# US 2013/0159261 A1 · De-duplication reference tag reconciliation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2013/0159261 A1 - Document ID: US20130159261A1 - Status: Published application - Kind: A1 - Application number: 13/332,038 - Filed: 2011-12-20 - Published: 2013-06-20 - Earliest claimed: 2011-12-20 - Assignees: Quantum Corporation - Inventors: Matthew Dewey; Roderick B. Wideman - Web page: https://patentgrep.com/patent/US20130159261A1 ## CPC - G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)} - G06F 3/0641: {De-duplication techniques} - G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Example apparatus and methods concern de-duplication reference tag reconciliation associated with garbage collection and/or reference health checking. One example method may include accessing data associated with members of a set of references to blocks of data stored by a data de-duplication system. The method may process the first data to manipulate a Bloom filter into a state from which membership in the set of references can be assessed. The method may also include accessing a block identifier identified with a member of the set of blocks of data stored by the data de-duplication system and assessing membership in the set of references for the block identifier by querying the Bloom filter with the block identifier. If the block is not referenced, as determined by querying the Bloom filter, then the method may include performing a block reclamation action on the unreferenced block. ## Claims ### Claim 1 A method, comprising: controlling a processor to access first data associated with members of a set of references to members of a set of blocks of data stored by a data de-duplication system in a block pool; controlling the processor to process the first data to manipulate a Bloom filter into a state from which membership in the set of references can be assessed; controlling the processor to access a block identifier identified with a member of the set of blocks of data stored by the data de-duplication system; controlling the processor to assess membership in the set of references for the block identifier by querying the Bloom filter with the block identifier; and controlling the processor to selectively perform a block reclamation action upon determining that the Bloom filter indicates that there is no member of the set of references associated with the block identifier, where the reclamation action comprises deleting the block from the block pool and reclaiming storage in the block pool associated with the block. ### Claim 2 (depends on 1) The method of claim 1, where the first data is one of, a list of references to blocks stored in the block pool, a list of references to BLOBs stored in the block pool. ### Claim 3 (depends on 2) The method of claim 2, the list of references being associated with a file system for which the de-duplication system stores de-duplicated data. ### Claim 4 (depends on 1) The method of claim 1, comprising: controlling the processor to modulate the first data and the block identifier in a manner sufficient to change the false positive response of the Bloom filter with respect to at least one query. ### Claim 5 (depends on 4) The method of claim 4, where modulating the first data and the block identifier includes manipulating the first data into a second, different data and manipulating the block identifier into a second, different identifier. ### Claim 6 (depends on 4) The method of claim 4, comprising determining to modulate the first data and the block identifier as a function of one or more of, a length of time the Bloom filter has been in use, a number of queries presented to the Bloom filter, and a number of false positives produced by the Bloom filter. ### Claim 7 (canceled) ### Claim 8 (depends on 1) The method of claim 1, where processing the first data to manipulate the Bloom filter comprises using a first set of hashes, and where querying the Bloom filter with the block identifier includes processing the block identifier using the first set of hashes. ### Claim 9 (depends on 8) The method of claim 8, comprising selectively controlling the processor to change from processing the first data to manipulate the Bloom filter using a first set of hashes to processing the first data to manipulate the Bloom filter using a second, different set of hashes, and controlling the processor to change from querying the Bloom filter with the block identifier after processing the block identifier using the first set of hashes to querying the Bloom filter with the block identifier after processing the block identifier using the second, different set of hashes. ### Claim 10 A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer control the computer to perform a method, the method comprising: controlling a processor to access first data associated with members of a set of blocks of data stored by a data de-duplication system; controlling the processor to process the first data to manipulate a Bloom filter into a state from which membership in the set of blocks of data can be assessed; controlling the processor to access a reference to a block stored by the data de-duplication system, the reference being associated with a referencing entity for which the data de-duplication system stores blocks of data; controlling the processor to assess membership in the set of stored blocks of data for the reference to the block by querying the Bloom filter with the reference to the block; and controlling the processor to perform a remedial reference action upon determining that the Bloom filter indicates that there is no member of the set of stored blocks of data associated with the reference to the block. ### Claim 11 (depends on 10) The non-transitory computer-readable medium of claim 10, where the first data is one of, a list of blocks of data in the set of stored blocks of data stored in a block pool associated with the data de-duplication system, and a list of BLOBs stored in the block pool. ### Claim 12 (depends on 10) The non-transitory computer-readable medium of claim 10, where the reference to the block of data is associated with a file system for which the data de-duplication system stores de-duplicated data. ### Claim 13 (depends on 10) The non-transitory computer-readable medium of claim 10, the method comprising performing one of: manipulating the first Bloom filter to a state where the first Bloom filter will produce less than a 1% false positive rate for set membership; and manipulating the first Bloom filter to a state where the first Bloom filter will produce less than a 0.1% false positive rate for set membership. ### Claim 14 (depends on 10) The non-transitory computer-readable medium of claim 10, the method comprising selectively modulating the first data and the reference. ### Claim 15 (depends on 14) The non-transitory computer-readable medium of claim 14, where modulating the first data comprises performing a data altering operation on the first data and where modulating the reference comprises performing a data altering operation on the reference. ### Claim 16 (depends on 10) The non-transitory computer-readable medium of claim 10, where modulating the first data and the reference comprises changing a set of hashes used to process data that populates the Bloom filter and to process data that queries the Bloom filter. ### Claim 17 An apparatus, comprising: a processor; a memory; a set of logics; and an interface to connect the processor, the memory, and the set of logics, the set of logics comprising: a first logic configured to populate a Bloom filter with first information concerning a first set; a second logic configured to query the Bloom filter with an entry from a second set; and a third logic configured to control a processor to take an action as a function of the second logic determining that the Bloom filter indicates that the entry from the second set does not have a corresponding member in the first set, where the action is associated with de-duplication reference tag reconciliation. ### Claim 18 (depends on 17) The apparatus of claim 17, the first set being a set of blocks stored in a block pool associated with a de-duplication system, the second set being a set of references to blocks referenced by a referencing entity, where the block pool stores blocks associated with the referencing entity. ### Claim 19 (depends on 18) The apparatus of claim 18, the referencing entity being a file system and the action being a reference remediation action. ### Claim 20 (depends on 17) The apparatus of claim 17, the first set being a set of references to blocks referenced by a referencing entity, the second set being a set of blocks stored in a block pool associated with a de-duplication system, and the action being a space reclamation action.