Simulating hierarchical structures in key value stores

• US 10,303,669 B1
• Filed: 03/30/2016
• Issued: 05/28/2019
• Est. Priority Date: 03/30/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Stephens, Christopher Andrew, Acheson, Alazel, Laurence, Douglas Stewart, Markle, Seth William
• Primary Examiner(s): Mamillapalli, Pavan
• Application Number:
  US15/085,824
• Time in Patent Office: 1,154 Days
• Field of Search: 707756
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2219 Large Object storage; Management thereof

Abstract

A key-value store is adapted to represent hierarchical structures, such as directory structures, to be associated with objects otherwise mapped to a flat keyspace. For example, one or more key-value pairs stored in the key-value store are designated to have a key indicating the name of a hierarchical structure, and an associated value that maps the structure to a namespace (e.g., of a group of objects to be associated with a directory). Inbound requests for operations related to the objects in a given namespace and defining the structure are checked against such “redirecting” key-value pairs to determine whether the structure is related to the namespace objects, and if so, the request is internally processed to perform the requested operations against the actual key-value pair(s) associated with the objects without necessitating identification of the objects with a fully qualified name as represented in the flat keyspace.

Claims

1. A computer-implemented method, comprising:

under the control of one or more computer systems configured with executable instructions,

storing a plurality of key-value pairs in a key-value store, a first subset of the plurality of key-value pairs including a first key and a first value, the first key indicating an object name and the first value indicating a location where an object associated with the object name of the first key is stored, a second subset of the plurality of key-value pairs including a second key and a second value, the second key indicating a delimiter and a directory name associated with a namespace, the second value indicating the namespace; and

in response to a first data retrieval request including the directory name and the delimiter;

querying the key-value store to determine that the directory name matches at least a key-value pair of the second subset of the plurality of key-value pairs;

as a result of the directory name matching at least the second key of the second subset of the plurality of key-value pairs, using the second key to determine the namespace associated with the second value;

mapping the directory name to the determined namespace of one or more objects associated with the first data retrieval request; and

retrieving, using the first subset of the plurality of key-value pairs, the one or more objects having the determined namespace and associated with the first data retrieval request from the location indicated by the first value.

2. The computer-implemented method of claim 1, further comprising, in response to a rename request for the directory name associated with the namespace, updating the first key to reflect a new directory name.

3. The computer-implemented method of claim 1, wherein the location where the object is stored is associated with a data storage system separate from the one or more computer systems.

4. The computer-implemented method of claim 1, wherein the plurality of key-value pairs are associated with objects stored in a plurality of disparate data storage systems.

5. A system, comprising:

at least one computing device configured to implement one or more services that;

adapt a keyspace represented in a key-value store, the keyspace including a plurality of key-value pairs arranged in a flat hierarchy, to include a structure simulating a multi-level hierarchy within the keyspace, by at least;

storing a key-value pair in the key-value store, the key-value pair having a key that indicates a redirect name for the structure and a value that indicates a namespace associated with the structure; and

assigning a delimiter that, when invoked, activates a redirect for requests associated with the structure; and

in response to a request, associated with the namespace, that invokes the delimiter;

verify that a requested structure name defined in the request matches the redirect name for the structure;

as a result of the requested structure name matches the redirect name for the structure, append, to the request, the redirect name for the structure to the namespace, thereby generating an appended request; and

perform one or more actions associated with the request in accordance with the appended request.

6. The system of claim 5, wherein the request is a request to retrieve one or more objects stored in connection with one or more key-value pairs of the plurality of key-value pairs.

7. The system of claim 5, wherein the request is a request to store, delete, or list one or more objects in connection with one or more key-value pairs of the plurality of key-value pairs.

8. The system of claim 5, wherein the structure is a directory structure.

9. The system of claim 8, wherein the directory structure is defined by a requestor associated with the request.

10. The system of claim 5, wherein the one or more services are further configured to, in response to a rename request for a structure associated with the namespace, update the key with a new redirect name.

11. The system of claim 5, wherein at least some values stored in the key-value store point to locations of objects stored outside of the key-value store.

12. The system of claim 5, wherein the request is received through an application programming interface provided by the system.

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

simulate a multi-level hierarchy in a keyspace having a flat hierarchy and being represented in a key-value store, the keyspace including a plurality of key-value pairs, by at least;

generating a redirecting key-value pair for storage in the key-value store, the redirecting key-value pair having a key that indicates a redirect name and a value that indicates a namespace; and

assigning a delimiter that, when invoked, activates a redirect for requests associated with the redirecting key-value pair; and

in response to a request invoking the delimiter;

verify that a requested redirect name in the request matches the key of the redirecting key-value pair; and

as a result of verifying that the requested redirect name in the request matches the key of the redirecting key-value pair, perform one or more in accordance with the request.

14. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to assign the delimiter in response to receiving an external request defining the delimiter.

15. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to assign the delimiter by predetermining the delimiter.

16. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to append the requested redirect name to the request.

17. The non-transitory computer-readable storage medium of claim 13, wherein the multi-level hierarchy is a directory tree viewable by a requester associated with the request.

18. The non-transitory computer-readable storage medium of claim 13, wherein the request is a write request associated with an object to be stored via the computer system.

19. The non-transitory computer-readable storage medium of claim 13, wherein the request is a read request associated with an object to be stored via the computer system.

20. The non-transitory computer-readable storage medium of claim 13, wherein the namespace is associated with a data storage system on which a plurality of objects associated with the request is stored.