Back to results
US 12,717,500 B2Granted
Key sorting between key-value solid state drives and hosts
AssigneeSamsung Electronics Co., Ltd.
InventorsYangwook Kang, Pratik Mishra, Yang Seok Ki
Life of this patent
Estimating the term…
Abstract
A Key-Value storage device is disclosed. The Key-Value storage device may include a first storage for data that is persistent. The Key-Value storage device 125) may also include a second storage for a main index structure to map a key to a location in the first storage. A controller may process a read request, a write request, or a delete request from a host using the first storage. A third storage may store a secondary index structure that stores the key, the secondary index structure being sorted.
Claims20
A Key-Value (KV) storage device, comprising:
- a first non-transitory storage for data, the first non-transitory storage including a persistent storage;
- a second non-transitory storage storing a main index structure mapping a key to a location in the first non-transitory storage storing a value, the key and the value forming a Key-Value pair;
- a controller to execute at least one of a read request, a write request, or a delete request using the first non-transitory storage;
- and
- a third non-transitory storage storing a secondary index structure storing the key, wherein the secondary index structure is sorted,
- wherein the secondary index structure is modified based at least in part on the at least one of the read request, the write request, or the delete request;
- and
- wherein the KV storage device is configured to receive a range query from a host, to identify a second key and a third key in the secondary index structure that satisfy the range query, and to send the second key and the third key to the host in response to the range query.
5 more elements
A method, comprising:
- receiving a request at a Key-Value (KV) storage device, the request including at least an operation and a key, the operation including at least one of a write operation or a delete operation;
- executing the request using a first storage of the KV storage device based at least in part on the operation and the key, thereby determining a location in the first storage associated with the key;
- modifying a main index structure of the KV storage device based at least in part on the operation, the key, and the location;
- logging the operation and the key in a log block of the KV storage device;
- returning a result of the request from the KV storage device;
- modifying a secondary index structure based at least in part on the log block;
- receiving a range query at the KV storage device;
- identifying a second key and a third key in the secondary index structure that satisfy the range query;
- and
- responding to the range query from the KV storage device with the second key and the third key.
7 more elements
A method, comprising:
- requesting a key by a host from a log block on a Key-Value (KV) storage device;
- receiving the key at the host from the KV storage device;
- generating, by the host, a secondary index structure based at least in part on the key, the secondary index structure sorted according to at least the key and a second key;
- sending the secondary index structure from the host to the KV storage device for storage on the KV storage device;
- sending a range query from the host to the KV storage device;
- and
- receiving at the host from the KV storage device a second key and a third key in response to the range query;
- wherein the secondary index structure is distinct from a main index structure used by the KV storage device to execute a read request including the key, a write request including the key, or a delete request including the key.
5 more elements
Dependencies are inferred from the claim text.