Scalable indexing

• US 10,176,113 B2
• Filed: 10/21/2014
• Issued: 01/08/2019
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Bowden, Paul, Beaverson, Arthur J.
• Primary Examiner(s): Torgrimson, Tyler
• Application Number:
  US14/519,722
• Publication Number:
  US 20150039907A1
• Time in Patent Office: 1,540 Days
• 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 adapting a uniform access indexing process with a non-uniform access memory, the method comprising:

storing a dictionary of index records in the non-uniform access memory, each index record comprising fields for an index key, a reference count and a physical block address, the index keys being uniformly distributed and unique;

maintaining a bucket translation table for mapping logical bucket identifiers to physical bucket locations of the memory including generating a logical bucket identifier by displacement hashing an index key, and the table comprising a mapping of the logical bucket identifier to a physical bucket location of the memory where the associated index record is stored;

collecting in cache a plurality of bucket entries, wherein each bucket entry comprises a set of index records having the same logical bucket identifier;

writing the collection of entries from the cache to contiguous physical bucket locations of the memory as a sequential write; and

updating the bucket translation table with the physical bucket locations for the bucket entries of the collection written from the cache to the memory.

2. The method of claim 1 wherein the index key comprises a cryptographic hash digest of data;

and

the physical block address field contains a pointer to a physical block address of the data stored on a storage device.

3. The method of claim 1 wherein the method includes designating as read only in cache the index records written sequentially to the memory.

4. The method of claim 1 wherein the generating a logical bucket identifier by displacement hashing includes utilizing a plurality of hash functions.

5. The method of claim 1 wherein the memory comprises a flash memory device which includes a plurality of erase blocks, each erase block comprising a plurality of pages, and each page comprising a plurality of buckets.

6. The method of claim 5, including:

performing a scavenging process to generate free erase blocks by reading erase blocks to the cache.

7. The method of claim 1, including:

reading one or more sequential index records from the memory to the cache; and

designating as free physical bucket locations in memory from which the one or more index records were read.

8. 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 physical bucket locations of the memory from which the valid index records were read.

9. The method of claim 1, including:

generating a plurality of logical bucket identifiers for the index key, wherein the displacement hashing function selects from among the plurality of generated logical bucket identifiers.

10. The method of claim 1, wherein:

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

11. 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.

12. The method of claim 1, wherein:

the bucket size is a function of the minimum write size of the memory based on a page or partial page.

13. The method of claim 1, wherein:

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

14. The method of claim 13, 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 bucket locations is met.

15. The method of claim 13, including:

generating free erase blocks by reading additional buckets to the cache in response to random read operations.

16. The method of claim 1 including:

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

17. The method of claim 1, wherein:

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

18. The method of claim 1, wherein:

the index records of the bucket are not ordered.

19. The method of claim 1, wherein:

the bucket translation table is stored in persistent memory.

20. The method of claim 1, wherein:

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

21. 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.

22. A non-transitory computer readable medium storing instructions executable by a processor, the non-transitory machine readable medium comprising instructions to:

store a dictionary of index records in the non-uniform access memory, each index record comprising fields for an index key, a reference count and a physical block address, the index keys being uniformly distributed and unique;

maintain a bucket translation table for mapping logical bucket identifiers to physical bucket locations of the memory, wherein a logical bucket identifier being generated by displacement hashing an index key, and the table comprising a mapping of the logical bucket identifier to a physical bucket location of the memory where the associated index record is stored;

collect in cache a plurality of bucket entries, wherein each bucket entry comprises a set of index records having the same logical bucket identifier;

write the collection of entries from the cache to contiguous physical bucket locations of the memory as a sequential write; and

update the bucket translation table with the physical bucket locations for the bucket entries of the collection written from the cache to the memory.

23. The non-transitory computer readable medium of claim 22 further comprising instructions to:

read one or more sequential index records from the memory to the cache; and

designating as free physical bucket locations in memory from which the one or more index records were read.

24. The non-transitory computer readable medium of claim 22 further comprising instructions to:

render 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 physical bucket locations of the memory from which the valid index records were read.

25. The non-transitory computer readable medium of claim 22 further comprising instructions to:

generate free erase blocks by reading additional buckets to the cache in response to random read operations, wherein each erase block comprises a plurality of pages.

26. The non-transitory computer readable medium of claim 22,

wherein the memory comprises a flash memory device which includes a plurality of erase blocks, each erase block comprising a plurality of pages, and each page comprising a plurality of buckets, and

the non-transitory computer readable medium further comprising instructions to perform a scavenging process to generate free erase blocks by reading erase blocks to the cache.

27. A computer system comprising:

a non-uniform access memory containing a dictionary of index records stored in physical bucket locations of the memory, each index record comprising fields for an index key, a reference count and a physical block address, the index keys being uniformly distributed and unique;

a processor; and

non-transitory machine readable medium storing instructions that, when executed, cause the processor to;

maintain a bucket translation table to map a logical bucket identifier, generated by displacement hashing an index key of the dictionary, to a physical bucket location of the memory where an index record associated with the index key is stored;

collect bucket entries in a cache, each bucket entry comprising a set of index records having the same logical bucket identifier to be written to the memory;

write sequentially a collection of the bucket entries from the cache to contiguous physical bucket locations of the memory; and

update the bucket translation table with the physical bucket locations for the bucket entries of the collection.

28. The system of claim 27 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.

29. The system of claim 27 wherein:

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

30. The system of claim 27 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.