Method and apparatus for creating a short hash handle highly correlated with a globally-unique hash signature
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.
1. A method comprising:
receiving a hash handle;
determining whether a value of a hash handle bit of the hash handle is a first value or a second value;
responsive to determining that the value of the hash handle bit is the first value:
identifying a corresponding hash signature in a data structure based at least in part on at least a first portion of the hash handle, the corresponding hash signature comprising the at least the first portion of the hash handle; and
removing the corresponding hash signature from the data structure;
responsive to determining that the value of the hash handle bit is the second value:
identifying a given index in an array of indices that corresponds to the hash handle, each index having a corresponding entry, the given index comprising at least a second portion of the hash handle, the entry corresponding to the given index storing a given hash signature;
marking the entry corresponding to the given index as free; and
removing the given hash signature from the entry corresponding to the given index,
wherein the method is implemented by at least one processing device comprising a processor coupled to a memory.
2. The method of claim 1 wherein the hash handle is an n-bit hash handle and wherein the first portion of the hash handle comprises n−1 bits of the hash handle.
3. The method of claim 2 wherein the lowest n−1 bits of the corresponding hash signature comprises the first portion of the hash handle.
4. The method of claim 1 wherein the hash handle is an n-bit hash handle and wherein the second portion of the hash handle comprises n−1 bits of the hash handle.
5. The method of claim 4 wherein the given index comprises n−1 bits and wherein the n−1 bits of the given index comprises the second portion of the hash handle.
6. The method of claim 1 wherein the hash handle is an n-bit hash handle and wherein the hash handle bit is a most significant bit of the hash handle.
7. The method of claim 1 wherein the hash handle is an n-bit hash handle and wherein the hash handle bit is a least significant bit of the hash handle.
8. A system comprising:
at least one processor coupled to memory, the at least one processor configured:
to receive a hash handle;
to determine whether a value of a hash handle bit of the hash handle is a first value or a second value;
responsive to determining that the value of the hash handle bit is the first value:
to identify a corresponding hash signature in a data structure based at least in part on at least a first portion of the hash handle, the corresponding hash signature comprising the at least the first portion of the hash handle; and
to remove the corresponding hash signature from the data structure;
responsive to determining that the value of the hash handle bit is the second value:
to identify a given index in an array of indices that corresponds to the hash handle, each index having a corresponding entry, the given index comprising at least a second portion of the hash handle, the entry corresponding to the given index storing a given hash signature;
to mark the entry corresponding to the given index as free; and
to remove the given hash signature from the entry corresponding to the given index.
9. The system of claim 8 wherein the hash handle is an n-bit hash handle and wherein the first portion of the hash handle comprises n−1 bits of the hash handle.
10. The system of claim 9 wherein the lowest n−1 bits of the corresponding hash signature comprises the first portion of the hash handle.
11. The system of claim 8 wherein the hash handle is an n-bit hash handle and wherein the second portion of the hash handle comprises n−1 bits of the hash handle.
12. The system of claim 11 wherein the given index comprises n−1 bits and wherein the n−1 bits of the given index comprises the second portion of the hash handle.
13. The system of claim 8 wherein the hash handle is an n-bit hash handle and wherein the hash handle bit is a most significant bit of the hash handle.
14. The system of claim 8 wherein the hash handle is an n-bit hash handle and wherein the hash handle bit is a least significant bit of the hash handle.
15. A computer program product comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code when executed by at least one processing device causes the at least one processing device:
to receive a hash handle;
to determine whether a value of a hash handle bit of the hash handle is a first value or a second value;
responsive to determining that the value of the hash handle bit is the first value:
to identify a corresponding hash signature in a data structure based at least in part on at least a first portion of the hash handle, the corresponding hash signature comprising the at least the first portion of the hash handle; and
to remove the corresponding hash signature from the data structure;
responsive to determining that the value of the hash handle bit is the second value:
to identify a given index in an array of indices that corresponds to the hash handle, each index having a corresponding entry, the given index comprising at least a second portion of the hash handle, the entry corresponding to the given index storing a given hash signature;
to mark the entry corresponding to the given index as free; and
to remove the given hash signature from the entry corresponding to the given index.
16. The computer program product of claim 15 wherein the hash handle is an n-bit hash handle and wherein the first portion of the hash handle comprises n−1 bits of the hash handle.
17. The computer program product of claim 16 wherein the lowest n−1 bits of the corresponding hash signature comprises the first portion of the hash handle.
18. The computer program product of claim 15 wherein the hash handle is an n-bit hash handle and wherein the second portion of the hash handle comprises n−1 bits of the hash handle.
19. The computer program product of claim 18 wherein the given index comprises n−1 bits and wherein the n−1 bits of the given index comprises the second portion of the hash handle.
20. The computer program product of claim 15 wherein the hash handle is an n-bit hash handle and wherein the hash handle bit is one of a most significant bit of the hash handle and a least significant bit of the hash handle.