Method of adapting a uniform access indexing process to a non-uniform access memory, and computer system
US8880544B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 25, 2010 |
| Grant date | Nov 4, 2014 |
| Priority date | — |
| Expiry date | Oct 6, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2212/7211
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.