System and method for controlling access to web services resources

• US 10,116,581 B2
• Filed: 02/22/2016
• Issued: 10/30/2018
• Est. Priority Date: 02/10/2006
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Geller, Alan S., Singh, Rahul
• Primary Examiner(s): Christensen, Scott B
• Application Number:
  US15/050,401
• Publication Number:
  US 20160173406A1
• Time in Patent Office: 981 Days
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 63/101 Access control lists [ACL]
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD

Abstract

A system and method for controlling access to web services resources. A system may include a storage medium configured to store instructions and one or more processors configured to access the storage medium. The instructions may be executable by at least one of the processors to implement a web services access control system (ACS) configured to receive requests. Each request specifies an access operation to be performed with respect to a corresponding resource. Each of the requests is associated with a corresponding principal. For each received request, the ACS may be further configured to determine whether an access control entry exists that is associated with both the resource and principal associated with the request and that specifies an access type sufficient to perform the access operation. If no such entry exists, the ACS may deny the request.

Claims

1. A system comprising:

a plurality of compute nodes that implement a distributed data store;

a programmatic interface for the distributed data store implemented via one or more hardware processors of at least some of the plurality of compute nodes;

the distributed data store, configured to;

receive a request to store a record in a table from a client, wherein the table is maintained in the distributed data store, wherein the request is received via the programmatic interface for the distributed data store;

identify a partition of the table to store the record according to a partition key value of the record and an identifier of the table, wherein the table is maintained in the distributed data store across a plurality of different partitions including the partition;

select a plurality of storage hosts implemented at different ones of the plurality of compute nodes to store the record according to a replication factor specified for the table by the client or another client via the programmatic interface, wherein the replication factor is specified to store the record to a first number of hosts, wherein the plurality of storage hosts are mapped to the partition of the table;

send the record to the plurality of storage hosts to be stored; and

upon a determination that a predetermined minimum number of the plurality of storage hosts have successfully stored the record, wherein the predetermined minimum number is less than the first number of hosts, send, via the programmatic interface, a completion indication for the request to the client.

2. The system of claim 1, wherein to identify the partition of the table, the distributed data store is configured to:

apply a hash function to the partition key value of the record to generate a hash value; and

determine a partition identifier that corresponds to the partition based on the hash value.

3. The system of claim 2, wherein to select the plurality of storage hosts, the distributed data store is configured to:

generate respective other hash values for individual ones of a larger collection of storage hosts including the plurality of storage hosts based on respective identifiers for the individual ones of the larger collection of storage hosts and the hash value generated for the record; and

apply a selection criterion to the respective other hash values for the individual ones of the larger collection of storage hosts to identify the respective other hash values for the plurality of storage hosts as the selected plurality of storage hosts.

4. The system of claim 1, wherein the distributed data store is further configured to:

prior to the selection of the plurality of storage hosts, select a plurality of data centers, wherein a different one of the plurality of storage hosts is implemented in each of the plurality of data centers.

5. The system of claim 1, wherein the distributed data store is further configured to:

receive a request to read the record from the client via the programmatic interface, wherein said request includes the partition key value of the record and the identifier of the table;

in response to the receipt of the request to read the record;

determine the partition of the record based on the partition key value of the record and the identifier of the table included in the request;

identify the plurality of storage hosts mapped to the partition;

retrieve the record from one or more of the plurality of storage hosts; and

return the record to the client.

6. The system of claim 1, wherein the distributed data store is a storage service accessible to the client via a network, wherein the table is one of a plurality of different tables stored for a plurality of different clients of the storage service including the client.

7. A method, comprising:

performing, by one or more computing devices;

receiving a request to store a record in a table from a client, wherein the table is maintained in a distributed data store, wherein the request is received via a programmatic interface for the distributed data store;

identifying a partition of the table to store the record according to a partition key value of the record and an identifier of the table, wherein the table is maintained in the distributed data store across a plurality of different partitions including the partition;

selecting a plurality of storage hosts implemented at different ones of the plurality of compute nodes to store the record according to a replication factor specified for the table by the client or another client via the programmatic interface, wherein the replication factor is specified to store the record to a first number of hosts, wherein the plurality of storage hosts are mapped to the partition of the table;

sending the record to the plurality of storage hosts to be stored; and

upon determining that a predetermined minimum number of the plurality of storage nodes have successfully stored the record, wherein the predetermined minimum number is less than the first number of hosts, sending a completion indication for the request to the client via the programmatic interface.

8. The method of claim 7, wherein identifying the partition of the table comprises:

applying a hash function to the partition key value of the record to generate a hash value; and

determining a partition identifier that corresponds to the partition based on the hash value.

9. The method of claim 8, wherein selecting the plurality of storage hosts comprises:

generating respective other hash values for individual ones of a larger collection of storage hosts including the plurality of storage hosts based on respective identifiers for the individual ones of the larger collection of storage hosts and the hash value generated for the record; and

applying a selection criterion to the respective other hash values for the individual ones of the larger collection of storage hosts to identify the respective other hash values for the plurality of storage hosts as the selected plurality of storage hosts.

10. The method of claim 7, further comprising:

prior selecting the plurality of storage hosts, selecting a plurality of data centers, wherein a different one of the plurality of storage hosts is implemented in each of the plurality of data centers.

11. The method of claim 7, further comprising:

receiving a request to read the record from the client via the programmatic interface, wherein said request includes the partition key value of the record and the identifier of the table;

in response to receiving the request to read the record;

determining the partition of the record based on the partition key value of the record and the identifier of the table-included in the request;

identifying the plurality of storage hosts mapped to the partition;

retrieving the record from one or more of the plurality of storage hosts; and

returning the record to the client.

12. The method of claim 7, wherein the distributed data store is a storage service accessible to the client via a network, wherein the table is one of a plurality of different tables stored for a plurality of different clients of the storage service including the client.

13. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

receiving a request to store a record in a table from a client, wherein the table is maintained in a distributed data store, wherein the request is received via a programmatic interface for the distributed data store;

identifying a partition of the table to store the record according to a partition key value of the record and an identifier of the table, wherein the table is maintained in the distributed data store across a plurality of different partitions including the partition;

selecting a plurality of storage hosts implemented at different ones of the plurality of compute nodes to store the record according to a replication factor specified for the table by the client or another client via the programmatic interface, wherein the replication factor is specified to store the record to a first number of hosts, wherein the plurality of storage hosts are mapped to the partition of the table;

sending the record to the plurality of storage hosts to be stored; and

upon determining that a predetermined minimum number of the plurality of storage nodes have successfully stored the record, wherein the predetermined minimum number is less than the first number of hosts, sending a completion indication for the request to the client via the programmatic interface.

14. The non-transitory, computer-readable storage medium of claim 13, wherein, in identifying the partition of the table, the program instructions cause the one or more computing devices to implement:

applying a hash function to the partition key value of the record to generate a hash value; and

determining a partition identifier that corresponds to the partition based on the hash value.

15. The non-transitory, computer-readable storage medium of claim 14, wherein, in selecting the plurality of storage hosts, the program instructions cause the one or more computing devices to implement:

generating respective other hash values for individual ones of a larger collection of storage hosts including the plurality of storage hosts based on respective identifiers for the individual ones of the larger collection of storage hosts and the hash value generated for the record; and

applying a selection criterion to the respective other hash values for the individual ones of the larger collection of storage hosts to identify the respective other hash values for the plurality of storage hosts as the selected plurality of storage hosts.

16. The non-transitory, computer-readable storage medium of claim 13, wherein the program instructions cause the one or more computing devices to further implement:

prior selecting the plurality of storage hosts, selecting a plurality of data centers, wherein a different one of the plurality of storage hosts is implemented in each of the plurality of data centers.

17. The non-transitory, computer-readable storage medium of claim 13, wherein the program instructions cause the one or more computing devices to further implement:

receiving a request to read the record from the client via the programmatic interface, wherein said request includes the partition key value of the record and the identifier of the table;

in response to receiving the request to read the record;

determining the partition of the record based on the partition key value of the record and the identifier of the table included in the request;

identifying the plurality of storage hosts mapped to the partition;

retrieving the record from one or more of the plurality of storage hosts; and

returning the record to the client.

18. The non-transitory, computer-readable storage medium of claim 13, wherein the distributed data store is a storage service accessible to the client via a network, wherein the table is one of a plurality of different tables stored for a plurality of different clients of the storage service including the client.