Method and apparatus for creating a short hash handle highly correlated with a globally-unique hash signature

• US 10,396,994 B1
• Filed: 03/11/2016
• Issued: 08/27/2019
• 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: Hallak, Renen, Kalish, Ronen, Luz, Kobi, Rokach, Ehud
• Primary Examiner(s): Rossiter, Sean D
• Assistant Examiner(s): Wu, Stephanie
• Application Number:
  US15/067,574
• Time in Patent Office: 1,264 Days
• Field of Search: None
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• 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
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Example embodiments of the present invention relate and a method and an apparatus for managing a short hash handle. The method including receiving an I/O including a first identifier for a data block and examining the first identifier in comparison with a second identifier. The data block identified in the I/O then may be managed according to the first identifier and the second identifier.

Claims

1. A computer-implemented method for creating a short hash handle comprising:

receiving data to be stored from a production system to a replication system;

receiving a hash signature of at least n-bits generated based at least in part on the data;

determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle;

designating a short hash handle based on the determination of whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle, wherein the designated short hash handle is at least an n-bit short hash handle comprising n−

1 bits associated with the received hash signature and a hash handle bit, the hash handle bit indicating whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle; and

storing an indication of the relationship of the designated short hash handle to the hash signature.

4. The method of claim 1 wherein the hash signature is a system-wide unique hash signature.

5. The method of claim 1,

wherein determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle comprises determining that the lowest n−

1 bits of the received hash signature do not correspond to an existing short hash handle;

wherein the n−

1 bits associated with the received hash signature of the designated short hash handle comprise the lowest n−

1 bits of the received hash signature; and

wherein the hash handle bit of the designated short hash handle is set of a first value indicating that the lowest n−

1 bits of the received hash signature do not correspond to an existing short hash handle.

6. The method of claim 5, further comprising:

receiving the designated short hash handle in association with an input-output operation;

determining that the hash handle bit of the designated short hash handle is set to the first value; and

responsive to determining that the hash handle bit of the designated short hash handle is set to the first value;

obtaining the lowest n−

1 bits of the corresponding hash signature from the n−

1 bits of designated short hash handle; and

obtaining the hash signature based at least in part on the obtained lowest n−

1 bits.

7. The method of claim 1,

wherein determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle comprises determining that the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle, the method further comprising obtaining an available index in a hash data structure associated with the existing short hash handle;

wherein the n−

1 bits associated with the received hash signature of the designated short hash handle comprise the available index; and

wherein the hash handle bit of the designated short hash handle is set of a second value indicating that the lowest n−

1 bits of the received hash signature correspond to the existing short hash handle.

8. The method of claim 7, wherein the hash data structure comprises a plurality of entries, each entry comprising an index and corresponding value, the method further comprising storing the received hash signature in the hash data structure as the value corresponding to the available index.

9. The method of claim 8, further comprising:

receiving the designated short hash handle in association with an input-output operation;

determining that the hash handle bit of the designated short hash handle is set to the second value; and

responsive to determining that the hash handle bit of the designated short hash handle is set to the second value, accessing the index in the hash data structure that corresponds to the n−

1 bits of the designated short hash handle to obtain the corresponding hash signature.

2. A system comprising:

one or more processors; and

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

receiving data to be stored from a production system to a replication system;

receiving a hash signature of at least n-bits generated based at least in part on to the data;

determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle;

designating a short hash handle based on the determination of whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle, wherein the designated short hash handle is at least an n-bit short hash handle comprising n−

1 bits associated with the received hash signature and a hash handle bit, the hash handle bit indicating whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle; and

storing an indication of the relationship of the designated short hash handle to the hash signature.

10. The system of claim 2 wherein the hash signature is a system-wide unique hash signature.

11. The system of claim 2,

wherein determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle comprises determining that the lowest n−

1 bits of the received hash signature do not correspond to an existing short hash handle;

wherein the n−

1 bits associated with the received hash signature of the designated short hash handle comprise the lowest n−

1 bits of the received hash signature; and

wherein the hash handle bit of the designated short hash handle is set of a first value indicating that the lowest n−

1 bits of the received hash signature do not correspond to an existing short hash handle.

12. The system of claim 11, wherein the computer program code further causes the at least one of the one or more processors to perform the operations of:

receiving the designated short hash handle in association with an input-output operation;

determining that the hash handle bit of the designated short hash handle is set to the first value; and

responsive to determining that the hash handle bit of the designated short hash handle is set to the first value;

obtaining the lowest n−

1 bits of the corresponding hash signature from the n−

1 bits of designated short hash handle; and

obtaining the hash signature based at least in part on the obtained lowest n−

1 bits.

13. The system of claim 2,

wherein determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle comprises determining that the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle, the method further comprising obtaining an available index in a hash data structure associated with the existing short hash handle;

wherein the n−

1 bits associated with the received hash signature of the designated short hash handle comprise the available index; and

wherein the hash handle bit of the designated short hash handle is set of a second value indicating that the lowest n−

1 bits of the received hash signature correspond to the existing short hash handle.

14. The system of claim 13, wherein the hash data structure comprises a plurality of entries, each entry comprising an index and corresponding value, the method further comprising storing the received hash signature in the hash data structure as the value corresponding to the available index.

15. The system of claim 14, wherein the computer program code further causes the at least one of the one or more processors to perform the operations of:

receiving the designated short hash handle in association with an input-output operation;

determining that the hash handle bit of the designated short hash handle is set to the second value; and

responsive to determining that the hash handle bit of the designated short hash handle is set to the second value, accessing the index in the hash data structure that corresponds to the n−

1 bits of the designated short hash handle to obtain the corresponding hash signature.

3. A computer program product comprising a non-transitory computer readable storage medium having computer program code stored thereon that, when executed on a processor of a computer, causes the computer to perform the operations of:

receiving data to be stored from a production system to a replication system;

receiving a hash signature of at least n-bits generated based at least in part on the data;

determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle;

designating a short hash handle based on the determination of whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle, wherein the designated short hash handle is at least an n-bit short hash handle comprising n−

1 bits associated with the received hash signature and a hash handle bit, the hash handle bit indicating whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle; and

storing an indication of the relationship of the designated short hash handle to the hash signature.

16. The computer program product of claim 3 wherein the hash signature is a system-wide unique hash signature.

17. The computer program product of claim 3,

wherein determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle comprises determining that the lowest n−

1 bits of the received hash signature do not correspond to an existing short hash handle;

wherein the n−

1 bits associated with the received hash signature of the designated short hash handle comprise the lowest n−

1 bits of the received hash signature; and

wherein the hash handle bit of the designated short hash handle is set of a first value indicating that the lowest n−

1 bits of the received hash signature do not correspond to an existing short hash handle.

18. The computer program product of claim 17, wherein the computer program code further causes the computer to perform the operations of:

receiving the designated short hash handle in association with an input-output operation;

determining that the hash handle bit of the designated short hash handle is set to the first value; and

responsive to determining that the hash handle bit of the designated short hash handle is set to the first value;

obtaining the lowest n−

1 bits of the corresponding hash signature from the n−

1 bits of designated short hash handle; and

obtaining the hash signature based at least in part on the obtained lowest n−

1 bits.

19. The computer program product of claim 3,

wherein determining whether or not the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle comprises determining that the lowest n−

1 bits of the received hash signature correspond to an existing short hash handle, the method further comprising obtaining an available index in a hash data structure associated with the existing short hash handle;

wherein the n−

1 bits associated with the received hash signature of the designated short hash handle comprise the available index; and

wherein the hash handle bit of the designated short hash handle is set of a second value indicating that the lowest n−

1 bits of the received hash signature correspond to the existing short hash handle.

20. The computer program product of claim 19, wherein the hash data structure comprises a plurality of entries, each entry comprising an index and corresponding value, the method further comprising storing the received hash signature in the hash data structure as the value corresponding to the available index.

21. The computer program product of claim 20, wherein the computer program code further causes the computer to perform the operations of:

receiving the designated short hash handle in association with an input-output operation;

determining that the hash handle bit of the designated short hash handle is set to the second value; and

responsive to determining that the hash handle bit of the designated short hash handle is set to the second value, accessing the index in the hash data structure that corresponds to the n−

1 bits of the designated short hash handle to obtain the corresponding hash signature.