Back to results
US 11,381,400 B2Granted
Using double hashing schema to reduce short hash handle collisions and improve memory allocation in content-addressable storage systems
AssigneeEMC IP Holding Company LLC
InventorsKirill Shoikhet, Gilad Braunschvig, Eldad Zinger, Kobi Luz, Zvi Schneider
Life of this patent
Estimating the term…
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.
Claims20
A method comprising:
- obtaining a hash handle comprising a portion that identifies a given indicator of a plurality of indicators of a hash signature, each indicator of the hash signature corresponding to one of a plurality of data structures, each data structure comprising mappings of hash signatures to physical addresses on at least one storage device of a storage system;
- selecting the given indicator based at least in part on the portion of the hash handle;
- identifying a mapping between the hash signature and one or more of the physical addresses based at least in part on the data structure that corresponds to the given indicator;
- and
- obtaining data from the one or more of the physical addresses based at least in part on the identified mapping;
- wherein the data structures comprise respective buckets;
- wherein each indicator identifies a particular one of the buckets and comprises at least a portion of one or more bytes of the hash signature;
- wherein the plurality of indicators comprise at least a first indicator and a second indicator identifying respective first and second ones of the buckets, the given indicator being one of the first indicator and the second indicator;
- wherein the first indicator comprises at least a portion of a first byte of the hash signature and the second indicator comprises at least a portion of a second byte of the hash signature;
- wherein the second byte is different than the first byte;
- and
- wherein the method is implemented by a processing device comprising a processor coupled to a memory.
9 more elements
An apparatus comprising:
- a processing device comprising a processor coupled to memory, the processing device being configured:
- to obtain a hash handle comprising a portion that identifies a given indicator of a plurality of indicators of a hash signature, each indicator of the hash signature corresponding to one of a plurality of data structures, each data structure comprising mappings of hash signatures
- to physical addresses on at least one storage device of a storage system;
- to select the given indicator based at least in part on the portion of the hash handle;
- to identify a mapping between the hash signature and one or more of the physical addresses based at least in part on the data structure that corresponds to the given indicator;
- and
- to obtain data from the one or more of the physical addresses based at least in part on the identified mappings wherein the data structures comprise respective buckets;
- wherein each indicator identifies a particular one of the buckets and comprises at least a portion of one or more bytes of the hash signature;
- wherein the plurality of indicators comprise at least a first indicator and a second indicator identifying respective first and second ones of the buckets, the given indicator being one of the first indicator and the second indicator;
- wherein the first indicator comprises at least a portion of a first byte of the hash signature and the second indicator comprises at least a portion of a second byte of the hash signature;
- and
- wherein the second byte is different than the first byte.
9 more elements
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 a processing device comprising a processor coupled to memory, causes the processing device:
- to obtain a hash handle comprising a portion that identifies a given indicator of a plurality of indicators of a hash signature, each indicator of the hash signature corresponding to one of a plurality of data structures, each data structure comprising mappings of hash signatures to physical addresses on at least one storage device of a storage system;
- to select the given indicator based at least in part on the portion of the hash handle;
- to identify a mapping between the hash signature and one or more of the physical addresses based at least in part on the data structure that corresponds to the given indicator;
- and
- to obtain data from the one or more of the physical addresses based at least in part on the identified mapping,
- wherein the data structures comprise respective buckets;
- wherein each indicator identifies a particular one of the buckets and comprises at least a portion of one or more bytes of the hash signature;
- and
- wherein the plurality of indicators comprise at least a first indicator and a second indicator identifying respective first and second ones of the buckets, the given indicator being one of the first indicator and the second indicator;
- wherein the first indicator comprises at least a portion of a first byte of the hash signature and the second indicator comprises at least a portion of a second byte of the hash signature;
- and
- wherein the second byte is different than the first byte.
9 more elements
Dependencies are inferred from the claim text.