Managing deduplication in a data storage system using a Bloomier filter data dictionary
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.
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.