公开(公告)号：US11036591B2

公开(公告)日：2021-06-15

申请号：US16035465

申请日：2018-07-13

Applicant: Amazon Technologies, Inc.

Inventor： Maximiliano Maccanti ,  Timothy Andrew Rath ,  Rama Krishna Sandeep Pokkunuri ,  Akshat Vig ,  Clarence Wing Yin Ng ,  Srivaths Badrinath Copparam ,  Rajaprabhu Thiruchi Loganathan ,  Wei Xiao ,  William Alexander Stevenson

IPC: G06F11/14 ,  G06F11/20

Abstract: A system that implements a data storage service may store data for database tables in multiple replicated partitions on respective storage nodes. In response to a request to restore a given table that was backed up in a remote storage system (e.g., key-value durable storage system), the service may create a new table, and may import a copy of each of the partitions of the given table from the remote storage system into the new table. The request to restore the table may specify a modified value for a configuration parameter for the table or for one of its partitions. The service may apply the new configuration parameter value to the table or its partitions during the restore operation. The new configuration parameter value may indicate an increase or decrease in storage capacity or throughput capacity, and its application may automatically trigger a partition split or move operation.

公开(公告)号：US10929240B2

公开(公告)日：2021-02-23

申请号：US15887853

申请日：2018-02-02

Applicant: Amazon Technologies, Inc.

Inventor： Timothy Andrew Rath ,  Jakub Kulesza ,  David Alan Lutz

IPC: G06F11/14 ,  G06F16/25 ,  G06F16/27 ,  G06F11/20

Abstract: A system that implements a data storage service may store data on behalf of storage service clients. The system may maintain data in multiple replicas of partitions that are stored on respective computing nodes in the system. A master replica for a replica group may increment a membership version indicator for the group, and may propagate metadata (including the membership version indicator) indicating a membership change for the group to other members of the group. Propagating the metadata may include sending a log record containing the metadata to the other replicas to be appended to their respective logs. Once the membership change becomes durable, it may be committed. A replica attempting to become the master of a replica group may determine that another replica in the group has observed a more recent membership version, in which case logs may be synchronized or snipped, or the attempt may be abandoned.

公开(公告)号：US10776397B2

公开(公告)日：2020-09-15

申请号：US14494524

申请日：2014-09-23

Applicant: Amazon Technologies, Inc.

Inventor： Santosh Kalki ,  Srinivasan Sundar Raghavan ,  Timothy Andrew Rath ,  Mukul Vijay Karnik ,  Amol Devgan ,  Swaminathan Sivasubramanian

IPC: G06F16/28 ,  H04L29/06 ,  G06F16/24 ,  G06F16/26 ,  G06F16/185 ,  G06F16/27 ,  G06F16/901 ,  G06F21/62

Abstract: An online analytical processing system may comprise an n-dimensional cube partitioned into slices, in which each slice may represent data points at the intersections of fixed and variable dimensions. Computation of data points within a slice may be deferred. A dependency graph may be initially constructed, in which the dependency graph is utilized in a subsequent computation. Calculation of data points may be prioritized based on information indicative of a chance that the data points will be accessed.

公开(公告)号：US10776395B2

公开(公告)日：2020-09-15

申请号：US15694828

申请日：2017-09-03

Applicant: Amazon Technologies, Inc.

Inventor： Swaminathan Sivasubramanian ,  Stefano Stefani ,  Chiranjeeb Buragohain ,  Rande A. Blackman ,  Timothy Andrew Rath ,  Raymond S. Bradford ,  Grant Alexander MacDonald McAlister ,  Jakub Kulesza ,  James R. Hamilton ,  Luis Felipe Cabrera

IPC: G06F16/27 ,  G06F16/20 ,  G06F16/21 ,  G06F16/215 ,  G06F16/25 ,  G06F16/22 ,  G06F9/50 ,  H04L29/08 ,  G06F12/0846

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.

公开(公告)号：US20200228393A1

公开(公告)日：2020-07-16

申请号：US16833334

申请日：2020-03-27

Applicant: Amazon Technologies, Inc.

Inventor： Timothy Andrew Rath ,  Jakub Kulesza ,  David Alan Lutz

IPC: H04L12/24 ,  G06F11/20 ,  G06F11/14 ,  G06F11/16 ,  G06F3/06 ,  H04L29/08

Abstract: A system that implements a data storage service may store data on behalf of storage service clients. The system may maintain data in multiple replicas of various partitions that are stored on respective computing nodes in the system. The system may employ a single master failover protocol, usable when a replica attempts to become the master replica for a replica group of which it is a member. Attempting to become the master replica may include acquiring a lock associated with the replica group, and gathering state information from the other replicas in the group. The state information may indicate whether another replica supports the attempt (in which case it is included in a failover quorum) or stores more recent data or metadata than the replica attempting to become the master (in which case synchronization may be required). If the failover quorum includes enough replicas, the replica may become the master.

公开(公告)号：US10542068B2

公开(公告)日：2020-01-21

申请号：US15437376

申请日：2017-02-20

Applicant: Amazon Technologies, Inc.

Inventor： Allan Henry Vermeulen ,  Timothy Andrew Rath

IPC: H04L29/08 ,  H04L12/911 ,  H04L29/06

Abstract: To checkpoint a shared state in a distributed system, a node may first isolate itself from communication with other nodes of a distributed system. The node may then store a checkpoint of the shared state. The node then restarts and attempts to initialize its operating state from the stored checkpoint. In response to successfully initializing its operating state, the node restores communication with one or more other nodes of the distributed system. The node then indicates to the one or more other nodes that the stored checkpoint of the shared state is valid.

公开(公告)号：US10482102B2

公开(公告)日：2019-11-19

申请号：US15431706

申请日：2017-02-13

Applicant: Amazon Technologies, Inc.

Inventor： Akshat Vig ,  Timothy Andrew Rath ,  Stuart Henry Seelye Marshall ,  Rande A. Blackman ,  David Alan Lutz ,  Jian Wang ,  Jiandan Zheng ,  Janani Narayanan

IPC: G06F17/30 ,  G06F16/27 ,  G06F16/28 ,  G06F16/90 ,  G06F16/2458 ,  G06F16/2455

Abstract: Methods and apparatus for conditional master election in a distributed database are described. A plurality of replicas of a database object are stored by a distributed database service. Some types of operations corresponding to client requests directed at the database object are to be coordinated by a master replica. Client access to the database object is enabled prior to election of a master replica. In response to a triggering condition, a particular replica is elected master. The master coordinates implementation of operations with one or more other replicas in response to client requests.

公开(公告)号：US10425470B1

公开(公告)日：2019-09-24

申请号：US15427926

申请日：2017-02-08

Applicant: Amazon Technologies, Inc.

Inventor： Yijun Lu ,  Stuart Henry Seelye Marshall ,  Timothy Andrew Rath ,  Rande Anthony Blackman ,  Wei Xiao

IPC: G06F15/16 ,  H04L29/08 ,  H04L12/911

Abstract: Partitions of a hosted computing service may be maintained on a computing node. Processing of requests to access the partition may be limited to constrain capacity utilization to a provisioned amount of capacity reserved for the partition. A second, additional amount of capacity may be associated with the partition and may reflect potential future changes to the provisioned amount of capacity. A sum of provisioned and additional capacities associated with partitions on a computing node may be calculated. The computing node may be ranked, relative to other computing nodes, for maintaining new or relocated partitions based on the sum.

公开(公告)号：US10162876B1

公开(公告)日：2018-12-25

申请号：US14973629

申请日：2015-12-17

Applicant: Amazon Technologies, Inc.

Inventor： Srinivasan Sundar Raghavan ,  Swaminathan Sivasubramanian ,  Timothy Andrew Rath ,  Mukul Vijay Karnik ,  Amol Devgan ,  Santosh Kalki

IPC: H04L29/06 ,  G06F17/30

Abstract: An analytics module may be embedded into an application developed, published, or used by an entity in addition to the owner of the data under analysis. An access token may be submitted by the analytics module to a provider of hosted services. The access token may correspond to an n-dimensional cube containing data at a level of granularity permitted to the application. The access token may incorporate additional policies controlling access to the corresponding n-dimensional cube.

公开(公告)号：US10158579B2

公开(公告)日：2018-12-18

申请号：US13924157

申请日：2013-06-21

Applicant: Amazon Technologies, Inc.

Inventor： Adam Douglas Morley ,  Vincent Anthony Brancato ,  Stefano Stefani ,  Jai Vasanth ,  Wei Xiao ,  Maximiliano Maccanti ,  Swaminathan Sivasubramanian ,  Rande A. Blackman ,  Timothy Andrew Rath

IPC: H04L12/911 ,  H04L12/24 ,  H04L29/08 ,  G06F11/20 ,  G06F9/50

Abstract: Methods and apparatus for resource silos at network-accessible services are disclosed. A subset of resources used for a database service, including at least one resource from each of a plurality of data centers, is selected for membership in a resource silo based on grouping criteria. A silo routing layer node identifies the resource silo as the target silo to which a client work request is to be directed. The client work request is sent to a front-end resource of the target silo either by the client, or by the silo routing layer node on behalf of the client. The front-end resource of the target silo transmits a representation of the work request to a back-end resource of the target silo, where a work operation corresponding to request is performed.