Method and apparatus utilizing non-uniform hash functions for placing records in non-uniform access memory

A computer system comprising a processor and program code which, when executed by the processor, places index records in an index stored in a flash memory, the index being used by a storage system to access each data element written to the storage system, wherein each record comprises an associated record key and an identifier of an associated data element written to the storage system, the system including:

• a flash memory containing the index records stored in physical bucket locations of the flash memory;
• a hash value generator;
• and
• a translation component;
• wherein inserting a new index record in the index includes steps of:
• if the new record is of a first type, the hash value generator applying a first ordered list of hash functions to the associated record key by applying the first hash function in the first list to the associated record key to produce a candidate logical bucket identifier, which is of a logical bucket in a logical bucket space and which the translation component maps to a physical bucket location of a first region of the flash memory, and if there is no available slot in the physical bucket location of the first region the hash value generator applying the second hash function in the first list to the associated record key to produce a different candidate logical bucket identifier;
• and
• if the new record is of a second type, the hash value generator applying a second ordered list of hash functions to the associated record key by applying the first hash function in the second ordered list to the associated record key to produce a candidate logical bucket identifier, which is of a logical bucket in said logical bucket space and which the translation component maps to a physical bucket location of a second region of the flash memory, and if there is no available slot in the physical bucket location of the second region the hash value generator applying the second hash function in the second ordered list to the associated record key to produce a different candidate logical bucket identifier;
• wherein the first hash function in the first list addresses a subset of logical buckets in said logical bucket space so that the first region is localized, and the first hash function in the first list is different from the first hash function in the second list, wherein the second region is different from and not limited to the first region,
• wherein the first type of record is more frequently modified than the second type of record, and the first hash function of the first list preferably addresses the first record type to the localized first region that is narrower than the second region, thereby reducing the records to be rewritten during an erase block scavenge of the flash memory.