Method of adapting a uniform access indexing process to a non-uniform access memory, and computer system

• US 8,880,544 B2
• Filed: 06/25/2010
• Issued: 11/04/2014
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: SimpliVity Corporation (Hewlett-Packard Enterprise Company)
• Inventors: Bowden, Paul, Beaverson, Arthur J.
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): TORGRIMSON, TYLER J
• Application Number:
  US12/823,452
• Publication Number:
  US 20100332846A1
• Time in Patent Office: 1,593 Days
• Field of Search: None
• US Class Current: 707/760
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/1054 the data cache being concurrently physically addressed
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 2212/2542 Non-uniform memory access [NUMA] architecture
• CPC Class Codes: G06F 2212/402 Encrypted data
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/502 using adaptive policy
• CPC Class Codes: G06F 2212/6032 Way prediction in set-associative cache
• CPC Class Codes: G06F 2212/7211 Wear leveling

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.

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.

2. The method of claim 1, including:

designating as free the physical locations in memory from which the index records were read.

3. The method of claim 1, including:

rendering a plurality of sequential physical bucket locations of the memory as a free block by reading any valid index records in the block to the cache and designating as free the physical locations of the memory from which such index records were read.

4. The method of claim 1, wherein

the displacement hashing generates a plurality of logical bucket identifiers for the index key and selects from among the plurality of generated logical bucket identifiers.

5. The method of claim 1, wherein:

the memory comprises one or more of flash, phase-change, and solid state disk memory devices.

6. The method of claim 1, wherein:

the memory is limited by one or more of random write access time, random read-modify-write access time, sequential write, alignment restrictions, erase time, erase block boundaries and wear.

7. The method of claim 1, wherein:

the physical bucket size is a function of a minimum write size of the memory.

8. The method of claim 1, wherein:

the size of the physical bucket is a page or partial page.

9. The method of claim 8, wherein:

the memory has an erase block comprising a plurality of pages.

10. The method of claim 1, including:

maintaining a bucket valid table for tracking which physical bucket locations of the memory are valid.

11. The method of claim 1, wherein:

a physical bucket location of the memory comprises a set of index records and a self-index into the bucket translation table.

12. The method of claim 11, wherein:

the index records of the bucket are not ordered.

13. The method of claim 1, wherein:

the bucket translation table is stored in persistent memory.

14. The method of claim 1, including:

tracking the number of free physical bucket locations in an erase block and implementing a process to generate a free erase block when a threshold of free physical bucket locations is met.

15. The method of claim 1, wherein:

the indexing process performs indexing operations based on requests that index records be inserted, deleted, looked up or modified.

16. The method of claim 1, wherein:

the indexing process presents logical bucket operations for reading and writing to physical bucket locations which store the index records.

17. The method of claim 1 wherein:

the size of the physical bucket is one kilobyte (1 KB).

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.

19. The system of claim 18, wherein:

the memory that stores the index comprises a physical device layer characterized by non-uniform read and write access and immutability with respect to size, alignment and timing.

20. The system of claim 18, wherein:

the memory that stores the index comprises one or more of flash, phase-change and solid state disk memory devices.

21. The system of claim 18, wherein:

the memory that stores the index comprises a flash memory device which includes a plurality of erase blocks, each erase block comprises a plurality of pages, and each page comprises a plurality of buckets.