Indirect block containing references to blocks of a persistent fingerprint index

Patent metadata

Field	Value
Publication number	US-11468030-B2
Application number	US-201916669993-A
Country	US
Kind code	B2
Filing date	Oct 31, 2019
Priority date	Oct 31, 2019
Publication date	Oct 11, 2022
Grant date	Oct 11, 2022

Abstract

In some examples, a system performs data deduplication using a deduplication fingerprint index in a hash data structure comprising a plurality of blocks, wherein the hash data structure is stored in persistent storage, and a block of the plurality of blocks comprises fingerprints computed based on content of respective data units. The system uses an indirect block in a memory to access a given block of the plurality of blocks in the hash data structure, the indirect block containing references to blocks of the hash data structure containing the deduplication fingerprint index, and the references indicating storage locations of the plurality of blocks in the persistent storage.

First claim

What is claimed is:

1. A non-transitory machine-readable storage medium comprising instructions that upon execution cause a system to:
perform data deduplication using a deduplication fingerprint index in a hash data structure comprising a plurality of blocks, wherein the hash data structure is stored in persistent storage, and a block of the plurality of blocks comprises fingerprints computed based on content of respective data units, wherein a first block of the plurality of blocks in the hash data structure comprises a plurality of buckets, and wherein each bucket of the plurality of buckets associates a respective fingerprint to a storage location indicator of a corresponding data unit, the respective fingerprint computed based on the corresponding data unit; and
use an indirect block in a memory to access a given block of the plurality of blocks in the hash data structure, the indirect block containing references to blocks of the hash data structure containing the deduplication fingerprint index, and the references identifying storage locations of the plurality of blocks in the persistent storage.

2. The non-transitory machine-readable storage medium of claim 1 , wherein the indirect block does not include any of the fingerprints computed based on the content of the respective data units.

3. The non-transitory machine-readable storage medium of claim 1 , wherein the indirect block does not include size information regarding sizes of the blocks of the hash data structure.

4. The non-transitory machine-readable storage medium of claim 1 , wherein the hash data structure is a log structured hash table, and wherein the instructions upon execution cause the system to:
for updating the log structured hash table, append new blocks containing fingerprints to the log structured hash table.

5. The non-transitory machine-readable storage medium of claim 4 , wherein the log structured hash table comprises segments, each segment of the segments comprising multiple blocks, and
wherein the appending comprises appending a new segment comprising the new blocks to a boundary of the log structured hash table.

6. The non-transitory machine-readable storage medium of claim 1 , wherein a bucket of the plurality of buckets associates a plurality of fingerprints to respective storage location indicators of corresponding data units.

7. The non-transitory machine-readable storage medium of claim 1 , wherein the hash data structure comprises header information indicating a number of fingerprints included in each bucket of the plurality of buckets.

8. The non-transitory machine-readable storage medium of claim 1 , wherein the given block of the plurality of blocks in the hash data structure is accessible using the indirect block without performing a binary search of the deduplication fingerprint index.

9. The non-transitory machine-readable storage medium of claim 1 , wherein the instructions upon execution cause the system to:
for a data unit, compute a corresponding fingerprint based on the data unit;
compute a respective block index based on the corresponding fingerprint, the respective block index referring to a corresponding block of the deduplication fingerprint index in the hash data structure;
use the respective block index to look up a given reference, from among the references, in the indirect block; and
determine, from the given reference, the storage location of the given corresponding block.

10. The non-transitory machine-readable storage medium of claim 1 , wherein the plurality of blocks in the hash data structure are variable sized blocks.

11. The non-transitory machine-readable storage medium of claim 1 , wherein the references include addresses of the plurality of blocks in the persistent storage.

12. The non-transitory machine-readable storage medium of claim 1 , wherein the hash data structure in the persistent storage contains a persistent version of the indirect block.

13. A system comprising:
persistent storage to store a hash data structure comprising a deduplication fingerprint index, the hash data structure comprising a plurality of blocks, and a block of the plurality of blocks comprises fingerprints computed based on content of respective data units, the fingerprints included in the deduplication fingerprint index, wherein a first block of the plurality of blocks in the hash data structure comprises a plurality of buckets, and wherein each bucket of the plurality of buckets associates a respective fingerprint to a storage location indicator of a corresponding data unit, the respective fingerprint computed based on the corresponding data unit;
a memory to store an indirect block containing block references indicating storage locations of blocks of the hash data structure containing the deduplication fingerprint index; and
a processor to execute instructions stored on a machine-readable storage medium to:
compute block indexes based on respective fingerprints for the deduplication fingerprint index, wherein different block indexes map to different block references in the indirect block, and
use the computed block indexes to look up respective block references in the indirect block.

14. The system of claim 13 , wherein the processor is to execute instructions stored on the machine-readable storage medium to access a given block of the plurality of blocks in the hash data structure using a block reference retrieved from the indirect block, and wherein the block references of the indirect block identify storage locations of the plurality of blocks in the persistent storage.

15. The system of claim 13 , wherein the processor is to execute instructions stored on the machine-readable storage medium to:
receive an incoming data unit;
compute a fingerprint based on the incoming data unit;
based on the computed fingerprint, access an entry of the indirect block and retrieve a respective block reference from the accessed entry; and
as part of a deduplication process for the incoming data unit, determine if the computed fingerprint is included in a block, of the deduplication fingerprint index, referenced by the respective block reference.

16. The system of claim 15 , wherein the block referenced by the respective block reference includes fingerprints in sorted order.

17. The system of claim 13 , wherein the hash data structure is a log structured hash table, and wherein the processor is to execute instructions stored on the machine-readable storage medium to:
for updating the log structured hash table, append new blocks containing fingerprints to a boundary of the log structured hash table.

18. A method performed by a system comprising a hardware processor, comprising:
performing data deduplication using a deduplication fingerprint index in a hash data structure comprising a plurality of blocks, wherein the hash data structure is stored in persistent storage, and a block of the plurality of blocks comprises fingerprints computed based on content of respective data units, the fingerprints arranged in sorted order in the block, wherein a first block of the plurality of blocks in the hash data structure comprises a plurality of buckets, and wherein each bucket of the plurality of buckets associates a respective fingerprint to a storage location indicator of a corresponding data unit, the respective fingerprint computed based on the corresponding data unit;
storing an indirect block in a memory, the indirect block containing an array of references to blocks of the hash data structure containing the deduplication fingerprint index, the references ident

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Goswami Sudhanshu
• Manivel Vinay
• Mandal Sonam
• Maheshwari Umesh
• Vu Hy

Classifications

• G06F16/1748 Primary

  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) · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/24562

  Pointer or reference processing operations · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/2272 Primary

  Management thereof · CPC title