Volume-based key-value store

• US 9,971,526 B1
• Filed: 06/29/2015
• Issued: 05/15/2018
• Est. Priority Date: 06/29/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Wei, Danny, Priescu, Valentin, Olson, Marc Stephen, Hawks, Benjamin Arthur
• Primary Examiner(s): Mackes, Kris E
• Assistant Examiner(s): Bui, Thuy T
• Application Number:
  US14/754,326
• Time in Patent Office: 1,051 Days
• Field of Search: 707744
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

The current document describes a storage system that provides a storage volume with a block-data interface to one or more clients. The storage system provides a key-value store that is associated with the storage volume. The clients access the key-value store via a key-value interface that provides a number of key-value operations to read, write, list, and delete key-value records from the key-value store. In some implementations, the key-value interface provides additional key-value operations that support the use of the key-value store by more than one client at a time. An environment in which the key-value store is used by the clients to retain I/O throttling parameters is described.

Claims

1. A computer-implemented method, comprising:

providing a storage volume on a storage server, the storage volume including a block-data store and a key-value store, the block-data store accessible via a block-data interface that supports block-data operations, the key-value store accessible via a key-value interface that supports key-value operations, the key-value store holding input/output throttling information associated with the storage volume, and the key-value store holding throttling parameters associated with the storage volume that include a burst-bucket key-value record that includes a burst-bucket value and a timestamp value that is updated with a current time when the burst-bucket value is updated;

receiving, from a client via the key-value interface, a request to perform a key value operation on the key-value store;

performing the key-value operation on the key-value store;

receiving, from a client via the block-data interface, a request to perform a block-data operation on the block-data store; and

performing the block-data operation on the block-data store.

2. The computer-implemented method of claim 1, wherein the key-value store contains a number of key-value records that are stored in a B-tree that is ordered based at least in part on the key of each key-value record of the number of key-value records.

3. The computer-implemented method of claim 1, wherein the supported key-value operations include a read operation, a write operation, a list operation, and a delete operation.

4. A storage system, comprising:

a storage volume containing a key-value store and a block-data store, the key-value store holding input/output throttling information associated with the storage volume, and the key-value store holding throttling parameters associated with the storage volume that include a burst-bucket key-value record that includes a burst-bucket value and a timestamp value that is updated with a current time when the burst-bucket value is updated;

a volume interface configured to process requests specifying key-value operations and requests specifying block-data operations; and

one or more processors coupled to a non-transitory computer readable storage medium containing instructions that, when executed by the one or more processors, cause the system to implement one or more interfaces and, as part of implementing the one or more interfaces;

receive the request from a client via the volume interface, the received request specifying a key-value operation or a block-data operation; and

process the request.

5. The system of claim 4, wherein the key-value store and the block-data store on the storage volume are replicated to a slave storage volume containing a slave key-value store and a slave block-data store.

6. The system of claim 4, wherein the volume interface is configured to receive and process a request to perform a compare-and-swap operation.

7. The system of claim 4, wherein the volume interface is configured to receive and process a request to perform a list operation.

8. The system of claim 4, wherein:

the volume includes a plurality of partitions; and

the partitions include a copy of the key-value store.

9. The system of claim 4, wherein the volume interface is configured to receive and process a request to perform key-value read, key-value write, key-value list, and key value delete operations.

10. The system of claim 4, wherein the key-value store retains key-value records associated with client-based throttling.

11. The system of claim 4, wherein the volume interface is configured to receive and process a request to perform block-data read and block-data write operations.

12. A non-transitory computer-readable storage medium having stored thereon executable instructions that, if executed by one or more processors of a computer system, cause the computer system to at least:

receive, from a client via a key-value interface on a storage server, a request to perform a key-value operation on a key-value store, the storage server including a volume being accessible to the client via a block-data interface configured to receive requests to process requests, from the client, to perform block-data operations, the key-value store holding input/output throttling information associated with the volume, and the key-value store holding throttling parameters associated with the storage volume that include a burst-bucket key-value record that includes a burst-bucket value and a timestamp value that is updated with a current time when the burst-bucket value is updated; and

perform the key-value operation on the key-value store as part of processing the request.

13. The non-transitory computer-readable storage medium of claim 12, wherein the key-value store is implemented using a hash table.

14. The non-transitory computer-readable storage medium of claim 12, wherein:

the key-value operation is a list operation with a prefix parameter; and

the instructions that cause the computer system to perform the key-value operation on the key-value store, when executed by the one or more processors, causes the computer system to provide, to the client, keys that are contained in the key-value store.

15. The non-transitory computer-readable storage medium of claim 12, wherein:

the volume includes a plurality of partitions distributed among a plurality of physical storage devices; and

the partitions include a key-value store accessible via the key-value interface.

16. The non-transitory computer-readable storage medium of claim 12, wherein the request to perform the key-value operation on the key-value store is received at the key-value interface.

17. The non-transitory computer-readable storage medium of claim 12, wherein the key-value operation is a compare-and-swap operation.