Managing deduplication in a data storage system using a Bloomier filter data dictionary

• US 10,146,786 B2
• Filed: 05/08/2017
• Issued: 12/04/2018
• Est. Priority Date: 12/09/2014
• Status: Active Grant

• Current Assignee: Dell International LLC (Dell Technologies Inc.)
• Original Assignee: Dell International LLC (Dell Technologies Inc.)
• Inventors: Brosch, Ryan W.
• Primary Examiner(s): Spieler, William
• Application Number:
  US15/589,200
• Publication Number:
  US 20170242869A1
• Time in Patent Office: 575 Days
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: 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
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

A method including maintaining a library having a plurality of storage tablets, each storage tablet storing a plurality of hash-to-storage mappings, each mapping a hash value to a storage location at which a block of data is stored, the block of data translating to the hash value pursuant to a hashing algorithm. The method also including upon receipt and/or determination of a new hash for incoming data pursuant to the hashing algorithm: a) querying a tablet cache for a hash-to-storage mapping having the new hash, the tablet cache comprising a subset of storage tablets copied from the library; and/or b) querying a secondary index for a hash-to-storage tablet mapping having the new hash, the secondary index including a plurality of filters, each filter mapping each of a plurality of key hashes to a storage tablet of the library storing that particular key hash in a hash-to-storage mapping.

Claims

1. A method for facilitating data deduplication in a data storage system, the method comprising:

maintaining an index comprising a plurality of filters, each filter electronically mapping each of a plurality of hashes to an electronic data library storing a plurality of hash-to-storage mappings;

wherein the plurality of filters are categorized into layers, with a plurality of filters in each layer.

2. The method of claim 1, wherein each of the plurality of hash-to-storage mappings maps a hash value to a storage address location in a data storage subsystem at which a block of data is stored, the block of data translating to the hash value pursuant to a hashing algorithm.

3. The method of claim 1, further comprising maintaining the plurality of filters of the index in random access memory (RAM).

4. The method of claim 3, wherein the electronic data library is maintained in non-volatile memory.

5. The method of claim 3, wherein at least a portion of the electronic data library is maintained as read-only.

6. The method of claim 1, wherein each of the plurality of filters is a Bloomier filter.

7. An information handling system comprising:

a processor; and

a memory accessible to the processor and storing instructions that, when executed by the processor, cause the processor to maintain an index comprising a plurality of filters, each filter electronically mapping each of a plurality of hashes to an electronic data library storing a plurality of hash-to-storage mappings, wherein the plurality of filters are categorized into layers, with a plurality of filters in each layer.

8. The information handling system of claim 7, wherein each of the plurality of hash-to-storage mappings each maps a hash value to a storage address location in the information handling system at which a block of data is stored, the block of data translating to the hash value pursuant to a hashing algorithm.

9. The information handling system of claim 7, wherein the plurality of filters are stored in random access memory (RAM).

10. The information handling system of claim 9, wherein the electronic data library is maintained in non-volatile memory.

11. The information handling system of claim 7, wherein each of the plurality of filters is a Bloomier filter.

12. The information handling system of claim 11, wherein the plurality of hashes mapped by the filters of the index are a pre-defined subset of hashes stored in the electronic data library.

13. The information handling system of claim 7, wherein the layers form a cascade of filter layers with, for each layer above a bottom layer, a filter from that layer is formed from a combination of the filters from a lower layer.

14. The information handling system of claim 7, wherein the electronic data library comprises a plurality of storage tablets, each storage tablet electronically storing a plurality of hash-to-storage mappings.

15. The information handling system of claim 14, further comprising a tablet cache stored in RAM, the tablet cache comprising a subset of storage tablets copied from the electronic data library.

16. The information handling system of claim 15, wherein the tablet cache comprises a storage tablet copied from the data library that has been most recently accessed for a hash-to-storage mapping.

17. A method for data deduplication in a data storage system, the method comprising:

maintaining an index comprising a plurality of filters, each filter electronically mapping each of a plurality of hashes to an electronic data library storing a plurality of hash-to-storage mappings, wherein the plurality of filters are categorized into layers, with a plurality of filters in each layer; and

upon at least one of receipt and determination of a new hash for incoming data, querying the index for a hash-to-storage tablet mapping comprising the new hash.

18. The method of claim 17, wherein the electronic data library comprises a plurality of storage tablets, each storage tablet electronically storing a plurality of hash-to-storage mappings, and the method further comprising:

maintaining a tablet cache comprising a subset of storage tablets copied from the electronic data library; and

upon at least one of receipt and determination of a new hash for incoming data, querying the tablet cache for a hash-to-storage mapping comprising the new hash.