Techniques and systems for scalable request handling in data processing systems

• US 10,394,789 B1
• Filed: 12/07/2015
• Issued: 08/27/2019
• Est. Priority Date: 12/07/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Animesh, Rishabh, Doddameti, Sandesh
• Primary Examiner(s): Le, Thu Nguyet T
• Application Number:
  US14/961,749
• Time in Patent Office: 1,359 Days
• Field of Search: 707769
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• 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 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A computer system, such as a data storage system, implements techniques for managing unpredictable and/or bursty system demand. For example, a database service implements a schema and/or a database table rotation that allows for events to be allocated substantially evenly across the available keyspace. In some embodiments, asynchronous and synchronous components of a data processing system are accordingly isolated so as to improve the operational efficiency and utilization of both.

Claims

1. A computer-implemented method, comprising:

in response to receiving a plurality of data storage requests for data to be stored in a plurality of volumes of durable storage of a data storage system, processing the data storage requests by at least;

obtaining events associated with each of the plurality of data storage requests;

assigning the events to one or more specified database tables, wherein the one or more database tables are rotated for assignment of the events, the database tables being configured so as to include an entry for each of the assigned events in both;

a primary index table that utilizes a pseudorandomly generated primary key for each of the assigned events; and

a secondary index table that uses information in the primary index table as its primary key, the information being different from the pseudorandomly generated primary key;

storing, asynchronous from receiving the plurality of the data storage requests, the data into the plurality of volumes in accordance with the events assigned to the one or more database tables, the data stored by at least;

applying a redundancy code to the data associated with the data storage requests to generate a set of shards representative of the data;

storing the shards on the plurality of volumes; and

updating entries corresponding to the events assigned to the one or more database tables; and

responding, synchronous from receiving the plurality of the data storage requests, to status requests regarding pendency of the events associated with each of the plurality of data storage requests by at least using the primary key of the secondary index table.

2. The computer-implemented method of claim 1, wherein each primary key includes information that identifies the respective assigned event.

3. The computer-implemented method of claim 1, further comprising updating the secondary index table in connection with populating the primary index table with each of the entries for the assigned events.

4. A system, comprising:

at least one computing device configured to implement one or more services, wherein the one or more services are configured to;

in response to receiving a plurality of data processing requests, process the plurality of requests by at least;

assigning events associated with each request of the plurality of requests to a subset of a series of database tables, wherein the subset of the series of database tables is cycled for assignment of the events, each of the assigned events being associated with a respective identifier, the identifier generated stochastically, and the assigning of events causing each event of the assigned event to be allocated to a processing partition based on a value of the respective identifier; and

in response to an update related to an allocated event, using a respective processing partition to execute the update.

5. The system of claim 4, wherein the one or more services are further configured to asynchronously service the allocated events.

6. The system of claim 5, wherein the asynchronous servicing of the allocated events cause the related update.

7. The system of claim 4, wherein the plurality of data processing requests are data storage requests.

8. The system of claim 7, wherein the one or more services are further configured to, in response to the data storage requests, asynchronously service the data storage requests by at least:

encoding data associated with the data storage requests using a redundancy code, so as to generate a set of shards, a quorum quantity of the set usable to reconstruct original data associated with the set of shards;

storing the shards on one or more data storage devices; and

generating updates for a respective allocated event in accordance with storing the shards.

9. The system of claim 4, wherein the database tables include both a primary index table and a secondary minimal index table that is keyed to an attribute, other than an identifier to which the primary index table is keyed.

10. The system of claim 9, wherein the one or more services are further configured to synchronously respond to status requests related to the allocated events using at least information in the secondary minimal index table.

11. The system of claim 10, wherein the processing partition is administered by a database service capable of manipulating the processing partition.

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

in response to receiving a data processing request, populate a database table with information relating to a plurality of events associated with the data processing request, the information including an identifier for each event of the plurality of events, the database table being configured to use the identifier as its primary key, the identifier being generated so as to decorrelate the events from other events when the events are assigned;

assign each event of the plurality of events to one of a plurality of processing partitions based at least in part on a value of the identifier, each processing partition of the plurality of processing partitions having a portion of overall processing capacity of a database service configured to service the plurality of events; and

cause the database service to service the event using the processing partition.

13. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to populate a a different database table the information relating to the plurality of events after an interval of time, thereby causing unprocessed events of the plurality of events to be assigned to another of a plurality of processing partitions.

14. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to asynchronously process the events on the database table so as to service the data processing request.

15. The non-transitory computer-readable storage medium of claim 12, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to generate, in response to population of the database table, a secondary minimal index table that uses information in the database table other than the identifier as a primary key.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to process status inquiries related to an event of the plurality of events by performing a lookup using at least the secondary minimal index table.

17. The non-transitory computer-readable storage medium of claim 12, wherein the data processing requests are associated with data to be stored in accordance with the requests, on one or more data storage devices associated with the system.

18. The non-transitory computer-readable storage medium of claim 17, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to asynchronously cause the storage of the data on the one or more data storage devices.

19. The non-transitory computer-readable storage medium of claim 18, wherein the asynchronous storage of the data generates at least some of the plurality of events.