Timothy A Rath

US Patent:

8473775, Jun 25, 2013

Filed:

Dec 14, 2010

Appl. No.:

12/967187

Inventors:

Michael T. Helmick - Seattle WA, US
Jakub Kulesza - Bellevue WA, US
Timothy A. Rath - Seattle WA, US
Stefano Stefani - Issaquah WA, US
David A. Lutz - Renton WA, US

Assignee:

Amazon Technologies, Inc. - Reno NV

International Classification:

G06F 11/00

US Classification:

714 411, 707623

Abstract:

Disclosed are various embodiments for distributing data items within a plurality of nodes. A data item update request is replicated from a master node in a plurality of nodes to a plurality of slave nodes within the plurality of nodes. The replicated data item update request is determined to be locality-based durable. Responsive to the determination that the replicated data item update request is locality-based durable, the data item update request is confirmed to a client, wherein the client had originated the data item update request. Upon failover of the master node to another node within the plurality of nodes, a fault-tolerant failover quorum ensures that all previously confirmed updates are found and recognized by the new master node.

US Patent:

8572091, Oct 29, 2013

Filed:

Jun 27, 2011

Appl. No.:

13/169990

Inventors:

Swaminathan Sivasubramanian - Seattle WA, US
Stefano Stefani - Issaquah WA, US
Chiranjeeb Buragohain - Seattle WA, US
Rande A. Blackman - Seattle WA, US
Timothy Andrew Rath - Seattle WA, US
Grant A. M. McAlister - Seattle WA, US
Jakub Kulesza - Bellevue WA, US
Wei Xiao - Kirkland WA, US
Raymond S. Bradford - Seattle WA, US

Assignee:

Amazon Technologies, Inc. - Reno NV

International Classification:

G06F 17/00
G06F 17/30

US Classification:

707747, 707968, 707972

Abstract:

A system that implements a scaleable data storage service may maintain tables in a non-relational data store on behalf of service clients. Each table may include multiple items. Each item may include one or more attributes, each containing a name-value pair. The system may provide an API through which clients can query tables maintained by the service. Items may be partitioned and indexed in a table according to a simple or composite primary key contained in all items in the table. A composite primary key may include a hash key attribute, and a range key attribute. The range key attribute may be usable to order items having the same hash key attribute value, and to partition them dependent on a range of range key attribute values. A query request may specify a logical or mathematical expression dependent on range key attribute values and may be directed to multiple partitions.

US Patent:

8595267, Nov 26, 2013

Filed:

Jun 27, 2011

Appl. No.:

13/170031

Inventors:

Swaminathan Sivasubramanian - Seattle WA, US
Stefano Stefani - Issaquah WA, US
Chiranjeeb Buragohain - Seattle WA, US
Rande A. Blackman - Seattle WA, US
Timothy Andrew Rath - Seattle WA, US
Grant A. M. McAlister - Seattle WA, US
Jakub Kulesza - Bellevue WA, US
James Hamilton - Seattle WA, US
Raymond S. Bradford - Seattle WA, US
Luis Felipe Cabrera - Bellevue WA, US

Assignee:

Amazon Technologies, Inc. - Reno NV

International Classification:

G06F 7/00
G06F 17/30
G06F 9/50
G06F 12/08

US Classification:

707803, 707809, 707968, 707972

Abstract:

A system that implements a scalable data storage service may maintain tables in a non-relational data store on behalf of clients. The system may provide a Web services interface through which service requests are received, and an API usable to request that a table be created, deleted, or described; that an item be stored, retrieved, deleted, or its attributes modified; or that a table be queried (or scanned) with filtered items and/or their attributes returned. An asynchronous workflow may be invoked to create or delete a table. Items stored in tables may be partitioned and indexed using a simple or composite primary key. The system may not impose pre-defined limits on table size, and may employ a flexible schema. The service may provide a best-effort or committed throughput model. The system may automatically scale and/or re-partition tables in response to detecting workload changes, node failures, or other conditions or anomalies.

US Patent:

20140082028, Mar 20, 2014

Filed:

Nov 25, 2013

Appl. No.:

14/088786

Inventors:

STEFANO STEFANI - ISSAQUAH WA, US
RANDE A. BLACKMAN - SEATTLE WA, US
TIMOTHY ANDREW RATH - SEATTLE WA, US
RAYMOND S. BRADFORD - SEATTLE WA, US
GRANT ALEXANDER MACDONALD MCALISTER - SEATTLE WA, US
JAKUB KULESZA - BELLEVUE WA, US
JAMES R. HAMILTON - SEATTLE WA, US
LUIS FELIPE CABRERA - BELLEVUE WA, US

Assignee:

Amazon Technologies, Inc. - Reno NV

International Classification:

G06F 17/30

US Classification:

707803

Abstract:

A system that implements a scalable data storage service may maintain tables in a non-relational data store on behalf of clients. The system may provide a Web services interface through which service requests are received, and an API usable to request that a table be created, deleted, or described; that an item be stored, retrieved, deleted, or its attributes modified; or that a table be queried (or scanned) with filtered items and/or their attributes returned. An asynchronous workflow may be invoked to create or delete a table. Items stored in tables may be partitioned and indexed using a simple or composite primary key. The system may not impose pre-defined limits on table size, and may employ a flexible schema. The service may provide a best-effort or committed throughput model. The system may automatically scale and/or re-partition tables in response to detecting workload changes, node failures, or other conditions or anomalies.

US Patent:

8458517, Jun 4, 2013

Filed:

Apr 30, 2010

Appl. No.:

12/771840

Inventors:

Allan H. Vermeulen - Seattle WA, US
Timothy Andrew Rath - Seattle WA, US

Assignee:

Amazon Technologies, Inc. - Reno NV

International Classification:

G06F 11/18
G06F 11/00

US Classification:

714 15, 714 381, 714 471, 709201

Abstract:

A system and method is disclosed for recording checkpoints in a distributed system. A distributed system comprises one or more computers implementing a plurality of nodes coordinating with one another to maintain a shared state of the distributed system. The system chooses a given one of the plurality of nodes to record a checkpoint of the shared state. In response, the given node records the checkpoint by isolating itself from communication with the other nodes, storing the checkpoint, restarting, and attempting to reinitialize its state from the stored checkpoint. Restarting may include deliberately causing a runtime error in the node. If the reinitialization is successful, the node restores communication with the other nodes and indicates to them that the newly stored checkpoint is valid.

US Patent:

20210329077, Oct 21, 2021

Filed:

Apr 30, 2021

Appl. No.:

17/245811

Inventors:

- Seattle WA, US
David Alan Lutz - Renton WA, US
Timothy Andrew Rath - Des Moines WA, US
Maximiliano Maccanti - Bellevue WA, US
Miguel Mascarenhas Filipe - Seattle WA, US
David Craig Yanacek - Seattle WA, US

Assignee:

Amazon Technologies, Inc. - Seattle WA

International Classification:

H04L 29/08
G06F 9/50
G06F 11/34
H04L 12/917
H04L 12/24
H04L 12/911
H04L 29/06

Abstract:

A system that provides services to clients may receive and service requests, various ones of which may require different amounts of work. The system may determine whether it is operating in an overloaded or underloaded state based on a current work throughput rate, a target work throughput rate, a maximum request rate, or an actual request rate, and may dynamically adjust the maximum request rate in response. For example, if the maximum request rate is being exceeded, the maximum request rate may be raised or lowered, dependent on the current work throughput rate. If the target or committed work throughput rate is being exceeded, but the maximum request rate is not being exceeded, a lower maximum request rate may be proposed. Adjustments to the maximum request rate may be made using multiple incremental adjustments. Service request tokens may be added to a leaky token bucket at the maximum request rate.

US Patent:

20210103604, Apr 8, 2021

Filed:

Sep 11, 2020

Appl. No.:

17/019047

Inventors:

- Seattle WA, US
Stefano Stefani - Issaquah WA, US
Chiranjeeb Buragohain - Issaquah WA, US
Rande A. Blackman - Seattle WA, US
Timothy Andrew Rath - Des Moines WA, US
Raymond S. Bradford - Seattle WA, US
Grant Alexander MacDonald McAlister - Seattle WA, US
Jakub Kulesza - Bellevue WA, US
James R. Hamilton - Seattle WA, US
Luis Felipe Cabrera - Bellevue WA, US

Assignee:

Amazon Technologies, Inc. - Seattle WA

International Classification:

G06F 16/27
G06F 16/20
G06F 16/21
G06F 16/215
G06F 16/25
G06F 16/22
G06F 9/50
H04L 29/08

Abstract:

A system that implements a scalable data storage service may maintain tables in a non-relational data store on behalf of clients. The system may provide a Web services interface through which service requests are received, and an API usable to request that a table be created, deleted, or described; that an item be stored, retrieved, deleted, or its attributes modified; or that a table be queried (or scanned) with filtered items and/or their attributes returned. An asynchronous workflow may be invoked to create or delete a table. Items stored in tables may be partitioned and indexed using a simple or composite primary key. The system may not impose pre-defined limits on table size, and may employ a flexible schema. The service may provide a best-effort or committed throughput model. The system may automatically scale and/or re-partition tables in response to detecting workload changes, node failures, or other conditions or anomalies.

US Patent:

20210064476, Mar 4, 2021

Filed:

Sep 11, 2020

Appl. No.:

17/019072

Inventors:

- Seattle WA, US
Timothy Andrew Rath - Seattle WA, US
Rama Krishna Sandeep Pokkunuri - Seattle WA, US
Akshat Vig - Seattle WA, US
Clarence Wing Yin NG - Daly City CA, US
Srivaths Badrinath Copparam - Issaquah WA, US
Rajaprabhu Thiruchi Loganathan - Issaquah WA, US
Wei Xiao - Kirkland WA, US
William Alexander Stevenson - Seattle WA, US

Assignee:

Amazon Technologies, Inc. - Seattle WA

International Classification:

G06F 11/14

Abstract:

A system that implements a data storage service may store data for a database table in multiple replicated partitions on respective storage nodes. In response to a request to back up a table, the service may back up individual partitions of the table to a remote storage system independently and (in some cases) in parallel, and may update (or create) and store metadata about the table and its partitions on storage nodes of the data storage service and/or in the remote storage system. Backing up each partition may include exporting it from the database in which the table is stored, packaging and compressing the exported partition for upload, and uploading the exported, packaged, and compressed partition to the remote storage system. The remote storage system may be a key-value durable storage system in which each backed-up partition is accessible using its partition identifier as the key.