Method of adapting a uniform access indexing process to a non-uniform access memory, and computer system
First Claim
1. A method of performing indexing operations on index records stored in a non-uniform access memory using a uniform access indexing process, each index record having an associated index key and the index keys being uniformly distributed and unique, the method comprising:
- inputting an index key into a lookup function to generate a logical bucket identifier by displacement hashing of the index key;
inputting the generated logical bucket identifier into a translation function to identify a physical bucket location in the non-uniform access memory for the associated index record, the translation function accessing a bucket translation table mapping logical bucket identifier and physical bucket location for each of the stored index records;
reading index records from one or more physical bucket locations in the memory;
collecting, in cache, index records associated with the read physical bucket locations;
sequentially writing the index records from cache into a new location in the memory; and
updating the bucket translation table with the physical bucket locations for the sequentially written index records.
3 Assignments
0 Petitions
Accused Products
Abstract
Method and apparatus for constructing an index that scales to a large number of records and provides a high transaction rate. New data structures and methods are provided to ensure that an indexing algorithm performs in a way that is natural (efficient) to the algorithm, while a non-uniform access memory device sees IO (input/output) traffic that is efficient for the memory device. One data structure, a translation table, is created that maps logical buckets as viewed by the indexing algorithm to physical buckets on the memory device. This mapping is such that write performance to non-uniform access SSD and flash devices is enhanced. Another data structure, an associative cache is used to collect buckets and write them out sequentially to the memory device as large sequential writes. Methods are used to populate the cache with buckets (of records) that are required by the indexing algorithm. Additional buckets may be read from the memory device to cache during a demand read, or by a scavenging process, to facilitate the generation of free erase blocks.
-
Citations
21 Claims
-
1. A method of performing indexing operations on index records stored in a non-uniform access memory using a uniform access indexing process, each index record having an associated index key and the index keys being uniformly distributed and unique, the method comprising:
-
inputting an index key into a lookup function to generate a logical bucket identifier by displacement hashing of the index key; inputting the generated logical bucket identifier into a translation function to identify a physical bucket location in the non-uniform access memory for the associated index record, the translation function accessing a bucket translation table mapping logical bucket identifier and physical bucket location for each of the stored index records; reading index records from one or more physical bucket locations in the memory; collecting, in cache, index records associated with the read physical bucket locations; sequentially writing the index records from cache into a new location in the memory; and updating the bucket translation table with the physical bucket locations for the sequentially written index records. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A computer system for performing indexing operations on index records stored in a non-uniform access memory using a uniform access indexing process, the computer system comprising:
-
the non-uniform access memory containing an index of index records stored in physical bucket locations of the memory, each index record having an associated index key and the index keys being uniformly distributed and unique; lookup function means for receiving an index key and generating a logical bucket identifier by displacement hashing of the index key; a bucket translation table mapping logical bucket identifiers and physical bucket locations for each of the stored index records; translation function means for receiving the generated logical bucket identifier and identifying a physical bucket location in the non-uniform access memory for the associated index record by accessing the bucket translation table mapping; reading means for reading index records from one or more physical bucket locations in the memory; a cache for collecting index records associated with the read physical bucket locations; writing means for sequentially writing the index records from cache into a new location in the memory; and updating means for updating the bucket translation table with the physical bucket locations for the sequentially written index records. - View Dependent Claims (19, 20, 21)
-
Specification