Policy mediated hierarchical structures in key value stores

• US 10,460,120 B1
• Filed: 03/30/2016
• Issued: 10/29/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): Henning, Matthew T
• Application Number:
  US15/085,775
• Time in Patent Office: 1,308 Days
• Field of Search: 726 1
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database

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, as well as one or more policies associated with the structure, the namespace, the key-value pairs, or some combination thereof, to determine whether the structure is related to the namespace objects and whether one or more requested actions are authorized against that structure.

Claims

1. A computer-implemented method, comprising:

simulating 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 associated with a plurality of objects stored in connection with a computer system, 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 for a subset of the plurality of key-value pairs directed to an indicator of a directory to be represented comprising a set of more than one object including a subset of the plurality of objects other than the redirecting key-value pair, and

a value that indicates a namespace associated with the subset of the plurality of key-value pairs directed to the subset of the plurality of objects;

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

associating, to the multi-level hierarchy, a policy that applies to the multi-level hierarchy so as to control a requestor'"'"'s access to the multi-level hierarchy; and

in response to a request invoking the delimiter,

processing the policy, based at least in part on verifying that a requested redirect name in the request matches the key of the redirecting key-value pair, to perform one or more actions in accordance with the request.

2. The computer-implemented method of claim 1, wherein the policy is under control of a policy management service.

3. The computer-implemented method of claim 1, wherein the policy includes information related to a subset of the one or more actions for which the requestor is authorized.

4. The computer-implemented method of claim 1, wherein the policy is associated with the multi-level hierarchy by being identified in the value of the redirecting key-value pair.

5. A system, comprising:

one or more processors; and

memory storing instructions that, as a result of being executed by the one or more processors, cause the system to;

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 an indicator of a directory structure to be represented comprising a plural set of objects including a subset of a plurality of objects of the structure and a value that indicates a namespace associated with the subset of the plurality of objects of the structure; and

assigning a policy to the structure, the policy indicating at least one or more authorized requestors associated with the structure; and

in response to a request, associated with the namespace, at least;

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

if 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;

access the policy to determine whether one or more actions associated with the request are authorized; and

if the policy authorizes the one or more actions, perform the one or more actions associated with the request in accordance with the appended request and the policy.

6. The system of claim 5, wherein the request is a request to retrieve an object 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 an object 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 policy assigned to the structure is under control of a policy management service associated with the system.

11. The system of claim 10, wherein the policy is accessed via an application programming interface call by an entity associated with the key-value store to the policy management service.

12. The system of claim 5, wherein the one or more actions are implicitly based on an identity of a requestor associated with the request.

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:

create, in a key-value store having a flat keyspace, a multi-level hierarchy, the keyspace including a plurality of key-value pairs associated with a plurality of objects stored in connection with the computer system, 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 for an indicator of a directory structure to be represented comprising a set of more than one object, the set of more than one object including a subset of the plurality of objects and a value that indicates a namespace associated with the subset of the plurality of objects; and

mapping a policy to the redirecting key-value pair, the policy including access-related information for the subset of the plurality of objects; and

in response to a request associated with the subset of the plurality of objects, at least;

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

access the policy to determine, from the access-related information, an allowable action from at least one action associated with the request and related to the subset of the plurality of objects; and

perform the allowable action 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 access the policy by obtaining the policy from a policy management service associated with the computer system.

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 map the policy to the redirecting key-value pair by including information identifying the policy in the value of the redirecting key-value pair.

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 determine the allowable action based at least in part on an identity of a requestor associated with 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 the subset of the plurality of objects.

19. The non-transitory computer-readable storage medium of claim 13, wherein the request is a read request associated with the subset of the plurality of objects.

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