Patent ID: 9684462
Date: 2017-06-20
CPC Classifications: G06F

Claim:
1. A method of reducing the scavenging overhead of flash memory storing an index; the index comprising a plurality of index records, each record comprising an associated record key and an identifier of an associated data element written to a storage system; wherein the method comprises inserting a new index record in the index stored in the flash memory including steps of: if the new record is of a first type, 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 a 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 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, 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 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.