公开(公告)号：US11327949B2

公开(公告)日：2022-05-10

申请号：US15495815

申请日：2017-04-24

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: G06F7/00 ,  G06F17/30 ,  G06F16/23 ,  G06F11/14 ,  G06F16/27 ,  G06F16/2455 ,  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 back up a table, the service may export individual partitions of the table from the database and package them to be independently uploaded (e.g., in parallel) to a remote storage system (e.g., a key-value durable storage system). Prior to uploading the exported and packaged partitions to the remote storage system, the service may verify that the exported and packaged partitions can be subsequently restored, which may include unpackaging and/or re-inflating the exported and packaged partitions to create additional unpackaged copies of the partitions, re-importing the additional unpackaged copies of the partitions into the database (e.g., as additional replicas), and/or comparing checksums generated for the exported partitions with checksums generated for the additional unpackaged copies of the partitions.

公开(公告)号：US11120052B1

公开(公告)日：2021-09-14

申请号：US16021707

申请日：2018-06-28

Applicant: Amazon Technologies, Inc.

Inventor： Mustafa Ozan Ozen ,  Sandeep Bhatia ,  Atilim Cetin ,  Lonnie J. Princehouse ,  Timothy Andrew Rath ,  Gaurav Saxena

IPC: G06F16/28 ,  G06F16/22 ,  G06F16/2455

Abstract: Techniques are described for clustering data at the point of ingestion for storage using scalable storage resources. To cluster data at the point of ingestion, a data ingestion and query service uses a multilevel hash tree (MLHT)-based index to map a hierarchy of attribute values associated with each data element onto a point of a MLHT (which itself conceptually maps onto a continuous range of values). The total range of the MLHT is divided into one or more data partitions, each of which is mapped to one or more physical storage resources. A mapping algorithm uses the hierarchy of attribute fields to calculate the position of each data element ingested and, consequently, a physical storage resource at which to store the data element.

公开(公告)号：US20210200446A1

公开(公告)日：2021-07-01

申请号：US17133009

申请日：2020-12-23

Applicant: Amazon Technologies, Inc.

Inventor： Swaminathan Sivasubramanian ,  Stefano Stefani ,  Wei Xiao ,  Timothy Andrew Rath ,  Rande A. Blackman ,  Grant Alexander MacDonald McAlister ,  Raymond S. Bradford

IPC: G06F3/06

Abstract: A system that implements a scaleable data storage service may maintain tables in a data store on behalf of storage service clients. The service may maintain data in partitions stored on respective computing nodes in the system. The service may support multiple throughput models, including a committed throughput model and a best effort throughput model. A service request to create a table may specify that requests directed to the table should be serviced under a committed throughput model and may specify the committed throughput level in terms of logical service request units. The service may reserve low-latency storage and other resources sufficient to meet the specified committed throughput level. A client/user may request a modification to the committed throughput level in anticipation of workload changes, such as an increase or decrease in traffic or data volume. In response, the system may increase or decrease the resources reserved for the table.

公开(公告)号：US10769175B1

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

申请号：US14503102

申请日：2014-09-30

Applicant: Amazon Technologies, Inc.

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

IPC: G06Q10/10 ,  G06Q30/02 ,  G06F16/28 ,  G06F16/24

Abstract: A hosted analytics system may be integrated with transactional data systems and additional data sources such real-time systems and log files. A data processing pipeline may transform data on arrival for incorporation into an n-dimensional cube. Correlation between patterns of events in transactional data may be identified. Upon arrival, new data may be transformed and incorporated into the n-dimensional cube. Similarity between the new data and a previously identified correlation may be determined and flagged.

公开(公告)号：US10296606B2

公开(公告)日：2019-05-21

申请号：US15376410

申请日：2016-12-12

Applicant: Amazon Technologies, Inc.

Inventor： Allan Henry Vermeulen ,  Timothy Andrew Rath ,  Timothy Daniel Cole ,  Kiran-Kumar Muniswamy-Reddy

IPC: G06F17/30

Abstract: At a client-side component of a storage group, a read descriptor generated in response to a read request directed to a first data store is received. The read descriptor includes a state transition indicator corresponding to a write that has been applied at the first data store. A write descriptor indicative of a write that depends on a result of the read request is generated at the client-side component. The read descriptor and the write descriptor are included in a commit request for a candidate transaction at the client-side component, and transmitted to a transaction manager.

公开(公告)号：US10257288B2

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

申请号：US14570900

申请日：2014-12-15

Applicant: Amazon Technologies, Inc.

Inventor： Wei Xiao ,  David Alan Lutz ,  Timothy Andrew Rath ,  Maximiliano Maccanti ,  Miguel Mascarenhas Filipe ,  David Craig Yanacek

IPC: H04L29/08 ,  H04L29/06 ,  G06F11/34 ,  G06F9/50

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.

公开(公告)号：US10025673B1

公开(公告)日：2018-07-17

申请号：US14032870

申请日：2013-09-20

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: G06F17/30 ,  G06F11/14

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.

公开(公告)号：US09996573B1

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

申请号：US14222377

申请日：2014-03-21

Applicant: Amazon Technologies, Inc.

Inventor： Akshat Vig ,  Wei Xiao ,  Somasundaram Perianayagam ,  Timothy Andrew Rath ,  Barry Bailey Hunter, Jr. ,  Kiran-Kumar Muniswamy-Reddy ,  Yijun Lu ,  Qiang Liu ,  Ying Lin ,  Stuart Henry Seelye Marshall

IPC: G06F17/30

CPC classification number: G06F17/30584

Abstract: A hosted service may limit access to a table initially comprising one or more partitions. Access to the table may be limited to a provisioned capacity. A client of the service may request an increased capacity. A minimum number of partitions for providing the increased capacity may be determined. Proportions of the increased capacity may be allocated among members of successive generations of partitions to be provided by a member of a generation or its descendants. The proportions may be allocated to minimize the costs associated with splitting partitions based on the minimum number of partitions.

公开(公告)号：US09886348B2

公开(公告)日：2018-02-06

申请号：US14754564

申请日：2015-06-29

Applicant: Amazon Technologies, Inc.

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

IPC: G06F11/14 ,  G06F17/30

CPC classification number: G06F11/1451 ,  G06F11/1425 ,  G06F11/2094 ,  G06F11/2097 ,  G06F17/30557 ,  G06F17/30575 ,  G06F17/30578

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.

公开(公告)号：US20170228417A1

公开(公告)日：2017-08-10

申请号：US15495815

申请日：2017-04-24

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: G06F17/30 ,  G06F11/14

CPC classification number: G06F16/2365 ,  G06F11/1451 ,  G06F11/1464 ,  G06F11/1469 ,  G06F11/2094 ,  G06F16/24561 ,  G06F16/278 ,  G06F2201/80 ,  G06F2201/84

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 back up a table, the service may export individual partitions of the table from the database and package them to be independently uploaded (e.g., in parallel) to a remote storage system (e.g., a key-value durable storage system). Prior to uploading the exported and packaged partitions to the remote storage system, the service may verify that the exported and packaged partitions can be subsequently restored, which may include unpackaging and/or re-inflating the exported and packaged partitions to create additional unpackaged copies of the partitions, re-importing the additional unpackaged copies of the partitions into the database (e.g., as additional replicas), and/or comparing checksums generated for the exported partitions with checksums generated for the additional unpackaged copies of the partitions.