Storage system with reduced hash key memory
AssigneeSTEC, Inc.
InventorsMohammad Reza SADRI, Saied KAZEMI, Siddharth CHOUDHURI
Life of this patent
Estimating the term…
Abstract
A system and method are disclosed for storing data in a hash table. The method includes receiving data, determining a location identifier for the data wherein the location identifier identifies a location in the hash table for storing the data and the location identifier is derived from the data, compressing the data by extracting the location identifier; and storing the compressed data in the identified location of the hash table.
Claims20
A method for retrieving data from a hash table, the method comprising:
- receiving an index of a hash table;
- retrieving compressed data stored at the index of the hash table;
- determining a set number based on the index and an associativity, the associativity indicating a capacity of the hash table;
- determining whether wrapping is required;
- when the wrapping is required,
- expanding the compressed data based on the set number and a total number of sets in the hash table;
- and
- when the wrapping is not required,
- expanding the compressed data based on the set number.
A storage device for retrieving data from a hash table, the storage device comprising:
- a host interface for communicating with a host device;
- a memory for storing data;
- a memory controller, comprising logic stored in a computer readable medium, configured to:
- receive an index of a hash table;
- retrieve compressed data stored at the index of the hash table;
- determine a set number based on the index and an associativity, the associativity indicating a capacity of the hash table;
- determine whether wrapping is required;
- when the wrapping is required,
- expand the compressed data based on the set number and a total number of sets in the hash table;
- and
- when the wrapping is not required,
- expand the compressed data based on the set number.
A non-transitory computer program product, tangibly embodied in a computer-readable medium, the computer program product including instructions operable to cause a data processing apparatus to:
- receive an index of a hash table;
- retrieve compressed data stored at the index of the hash table;
- determine a set number based on the index and an associativity, the associativity indicating a capacity of the hash table;
- determine whether wrapping is required;
- if wrapping is required,
- expand the compressed data based on the set number and a total number of sets in the hash table;
- and
- otherwise,
- expand the compressed data based on the set number.
Dependencies are inferred from the claim text.