High-Performance Indexing For Data-Intensive Systems
First Claim
1. A method for indexing data in a storage system comprising:
- (a) receiving a data element for storage in a storage system at a storage address;
(b) determining a slot address in an index in a first memory as a function of a key value of the data element for storage;
(c) storing the data element for storage linked to the storage address as an index pair at the slot address; and
(d) transferring at an interval the index pair from the first memory to an index in a second memory being a flash memory larger in capacity than the first memory to be preferentially combined with previously transferred index pairs having the same slot address.
2 Assignments
0 Petitions
Accused Products
Abstract
Aspects of the present invention provide high-performance indexing for data-intensive systems in which “slicing” is used to organize indexing data on an SSD such that related entries are located together. Slicing enables combining multiple reads into a single “slice read” of related items, offering high read performance. Small in-memory indexes, such as hash tables, bloom filters or LSH tables, may be used as buffers for insert operations to resolve slow random writes on the SSD. When full, these buffers are written to the SSD. The internal architecture of the SSD may also be leveraged to achieve higher performance via parallelism. Such parallelism may occur at the channel-level, the package-level, the die-level and/or the plane-level. Consequently, memory and compute resources are freed for use by higher layer applications, and better performance may be achieved.
47 Citations
20 Claims
-
1. A method for indexing data in a storage system comprising:
-
(a) receiving a data element for storage in a storage system at a storage address; (b) determining a slot address in an index in a first memory as a function of a key value of the data element for storage; (c) storing the data element for storage linked to the storage address as an index pair at the slot address; and (d) transferring at an interval the index pair from the first memory to an index in a second memory being a flash memory larger in capacity than the first memory to be preferentially combined with previously transferred index pairs having the same slot address. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method for indexing data in a storage system using flash memory comprising:
-
(a) determining the mapping between a first logical page and a first plurality of memories coupled to a first channel within a flash memory; (b) determining the mapping between a second logical page and a second plurality of memories coupled to a second channel within the flash memory; and (c) reordering a plurality of read requests to the flash memory to allow a plurality of read cycles to occur at the same time within the flash memory. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification