Using double hashing schema to reduce short hash handle collisions and improve memory allocation in content-addressable storage systems

• US 10,728,035 B1
• Filed: 09/16/2016
• Issued: 07/28/2020
• Est. Priority Date: 12/31/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Shoikhet, Kirill, Braunschvig, Gilad, Zinger, Eldad, Luz, Kobi, Schneider, Zvi
• Primary Examiner(s): Rossiter, Sean D
• Assistant Examiner(s): Wu, Stephanie
• Application Number:
  US15/267,860
• Time in Patent Office: 1,411 Days
• Field of Search: None
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Example embodiments of the present invention relate and a method and an apparatus for double hashing. The method including receiving a hash signature, including a short hash handle, for a data block. The method then includes determining a bucket with which the hash signature should be associated and associating the hash signature with the bucket.

Claims

1. A method for content addressable storage of data blocks in a distributed data storage system comprising:

receiving a hash signature, including a short hash handle, for a data block, wherein the hash signature corresponds to a physical address of the data block within the content addressable storage, wherein the hash signature comprises a first identification of a first bucket and a second identification of a second bucket;

selecting one of the first bucket and the second bucket based at least in part on the first identification and the second identification as a bucket with which the hash signature should be associated; and

associating the hash signature with the selected one of the first bucket and the second bucket, wherein associating the hash signature includes modifying a bit of the short hash handle to provide an indication of which one of the first identification of the first bucket and the second identification of the second bucket in the hash signature corresponds to the selected one of the first bucket and the second bucket.

2. The method of claim 1 wherein selecting one of the first bucket and the second bucket based at least in part on the first identification and the second identification comprises determining whether or not both the first bucket and the second bucket each comprise at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprise a hash entry having the short hash handle.

3. The method of claim 2 further comprising, if both the first bucket and the second bucket each comprise at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprise a hash entry having the short hash handle:

determining a selected bucket among the first bucket and the second bucket which has the fewest number of entries; and

associating the hash signature with the selected bucket having the fewest number of entries.

4. The method of claim 2 further comprising, if only one of the first bucket and the second bucket comprises at least one hash entry having the short hash handle:

determining the one bucket among the first bucket and the second bucket which comprises the at least one hash entry having the short hash handle; and

associating the hash signature with the other of the first bucket and the second bucket that does not comprise at least one hash entry having the short hash handle.

5. The method of claim 1 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the first bucket based at least in part on both the first bucket and the second bucket each comprising at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprising a hash entry having the short hash handle and a first number of entries associated with the first bucket is less than a second number of entries associated with the second bucket.

6. The method of claim 1 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the second bucket based at least in part on both the first bucket and the second bucket each comprising at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprising a hash entry having the short hash handle and a first number of entries associated with the first bucket is greater than a second number of entries associated with the second bucket.

7. The method of claim 1 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the first bucket based at least in part on the second bucket comprising a hash entry having the short hash handle.

8. The method of claim 1 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the second bucket based at least in part on the first bucket comprising a hash entry having the short hash handle.

9. The method of claim 1, wherein the first indication comprises a first plurality of bits of the hash signature and the second indication comprises a second plurality of bits of the hash signature that are different than the first plurality of bits of the hash signature.

10. A system for content addressable storage of data blocks in a distributed data storage system comprising:

one or more processors; and

memory storing computer program code that when executed on the one or more processors causes the system to perform the operations of;

receiving a hash signature, including a short hash handle, for a data block, wherein the hash signature corresponds to a physical address of the data block within the content addressable storage, wherein the hash signature comprises a first identification of a first bucket and a second identification of a second bucket;

selecting one of the first bucket and the second bucket based at least in part on the first identification and the second identification as a bucket with which the hash signature should be associated; and

associating the hash signature with the selected one of the first bucket and the second bucket, wherein associating the hash signature includes modifying a bit of the short hash handle to provide an indication of which one of the first identification of the first bucket and the second identification of the second bucket in the hash signature corresponds to the selected one of the first bucket and the second bucket.

11. The system of claim 10 wherein selecting one of the first bucket and the second bucket based at least in part on the first identification and the second identification comprises determining whether or not both the first bucket and the second bucket each comprise at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprise a hash entry having the short hash handle.

12. The system of claim 11 further comprising, if both the first bucket and the second bucket each comprise at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprise a hash entry having the short hash handle:

determining a selected bucket among the first bucket and the second bucket which has the fewest number of entries; and

associating the hash signature with the selected bucket having the fewest number of entries.

13. The system of claim 11 further comprising, if only one of the first bucket and the second bucket comprises at least one hash entry having the short hash handle:

determining the one bucket among the first bucket and the second bucket which comprises the at least one hash entry having the short hash handle; and

associating the hash signature with the other of the first bucket and the second bucket that does not comprise at least one hash entry having the short hash handle.

14. The system of claim 10 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the first bucket based at least in part on both the first bucket and the second bucket each comprising at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprising a hash entry having the short hash handle and a first number of entries associated with the first bucket is less than a second number of entries associated with the second bucket.

15. The system of claim 10 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the second bucket based at least in part on both the first bucket and the second bucket each comprising at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprising a hash entry having the short hash handle and a first number of entries associated with the first bucket is greater than a second number of entries associated with the second bucket.

16. The system of claim 10 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the first bucket based at least in part on the second bucket comprising a hash entry having the short hash handle.

17. The system of claim 10 wherein associating the hash signature with the selected one of the first bucket and the second bucket comprises associating the hash signature with the second bucket based at least in part on the first bucket comprising a hash entry having the short hash handle.

18. The system of claim 10, wherein the first indication comprises a first plurality of bits of the hash signature and the second indication comprises a second plurality of bits of the hash signature that are different than the first plurality of bits of the hash signature.

19. A computer program product for content addressable storage of data blocks in a distributed data storage system including a non-transitory compute readable storage medium having computer program code thereon that when executed on a processor of a computer causes the computer to perform double hashing, the computer program code comprising:

computer program code for receiving a hash signature, including a short hash handle, for a data block, wherein the hash signature corresponds to a physical address of the data block within the content addressable storage, wherein the hash signature comprises a first identification of a first bucket and a second identification of a second bucket;

computer program code for selecting one of the first bucket and the second bucket based at least in part on the first identification and the second identification as a bucket with which the hash signature should be associated; and

computer program code for associating the hash signature with the selected one of the first bucket and the second bucket, wherein associating the hash signature includes modifying a bit of the short hash handle to provide an indication of which one of the first identification of the first bucket and the second identification of the second bucket in the hash signature corresponds to the selected one of the first bucket and the second bucket.

20. The computer program product of claim 19 wherein selecting one of the first bucket and the second bucket based at least in part on the first identification and the second identification comprises determining whether or not both the first bucket and the second bucket each comprise at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprise a hash entry having the short hash handle;

wherein the computer program code further comprises;

computer program code for, if both the first bucket and the second bucket each comprise at least one hash entry having the short hash handle or neither of the first bucket and the second bucket comprise a hash entry having the short hash handle;

determining a selected bucket among the first bucket and the second bucket which has the fewest number of entries; and

associating the hash signature with the selected bucket having the fewest number of entries;

computer program code for, if only one of the first bucket and the second bucket comprises at least one hash entry having the short hash handle;

determining the one bucket among the first bucket and the second bucket which comprises the at least one hash entry having the short hash handle; and

associating the hash signature with the other of the first bucket and the second bucket that does not comprise at least one hash entry having the short hash handle.

21. The computer program product of claim 19, wherein the first indication comprises a first plurality of bits of the hash signature and the second indication comprises a second plurality of bits of the hash signature that are different than the first plurality of bits of the hash signature.