公开(公告)号：US11048685B1

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

申请号：US15950488

申请日：2018-04-11

Applicant: Amazon Technologies, Inc.

Inventor： Usman Ahmed Shami ,  Wei Xiao

IPC: G06F16/00 ,  G06F16/23 ,  G06F16/2455

Abstract: A repository of key-value data may store a first object value having an internal structure of a hierarchy of sub-objects. The repository may receive a request to modify the first object, expressed as a function, without side effects, of one or more parameters. Values may be assigned to the one or more parameters by mapping from the parameters to locations in the hierarchy of sub-objects. A second object may be formed based on the return value of the function. The first object may be replaced in the repository by the second object.

公开(公告)号：US10999381B2

公开(公告)日：2021-05-04

申请号：US16377078

申请日：2019-04-05

Applicant: Amazon Technologies, Inc.

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

IPC: H04L12/24 ,  H04L29/08 ,  H04L12/917 ,  H04L12/911 ,  G06F9/50 ,  G06F11/34 ,  H04L29/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.

公开(公告)号：US20200341657A1

公开(公告)日：2020-10-29

申请号：US16926519

申请日：2020-07-10

Applicant: Amazon Technologies, Inc.

Inventor： Stefano Stefani ,  Timothy Andrew Rath ,  Chiranjeeb Buragahain ,  Yan Valerie Leshinsky ,  David Alan Lutz ,  Jakub Kulesza ,  Wei Xiao ,  Jai Vasanth

IPC: G06F3/06 ,  G06F16/27

Abstract: A system that implements a scalable data storage service may maintain tables in a data store on behalf of storage service clients. The service may maintain table data in multiple replicas of partitions that are stored on respective computing nodes in the system. In response to detecting an anomaly in the system, detecting a change in data volume on a partition or service request traffic directed to a partition, or receiving a service request from a client to split a partition, the data storage service may create additional copies of a partition replica using a physical copy mechanism. The data storage service may issue a split command defined in an API for the data store to divide the original and additional replicas into multiple replica groups, and to configure each replica group to maintain a respective portion of the table data that was stored in the partition before the split.

公开(公告)号：US10776212B2

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

申请号：US15495827

申请日：2017-04-24

Applicant: Amazon Technologies, Inc.

Inventor： Maximliano 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/00 ,  G06F11/14 ,  G06F11/20

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.

公开(公告)号：US10747739B1

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

申请号：US14859055

申请日：2015-09-18

Applicant: Amazon Technologies, Inc.

Inventor： Kiran Kumar Muniswamy Reddy ,  Xianglong Huang ,  Pejus Manoj Das ,  Wei Xiao

IPC: G06F16/22 ,  G06F16/28 ,  G06F16/23

Abstract: A data storage system may implement implicit checkpoint for generating a secondary of a table. Indexing updates may be replicated and maintained across a replica group storing a table for a data store. Upon detection of a restart event for generating a secondary index, a replica in the replica group may evaluate the indexing updates to determine an index creation restart point according to an order for indexing the table. The generation of the secondary index may be resumed at the index creation restart point. In this way, secondary index generation may continue whether or not a previously indexing replica in the replica group, such as a master replica, is available to continue generating the secondary index.

公开(公告)号：US10459898B2

公开(公告)日：2019-10-29

申请号：US14845220

申请日：2015-09-03

Applicant: Amazon Technologies, Inc.

Inventor： David Craig Yanacek ,  Mohammad Zeeshan Qureshi ,  Jai Vasanth ,  Pejus Manoj Das ,  Stefano Stefani ,  Stuart Henry Seelye Marshall ,  Wei Xiao

IPC: G06F16/21 ,  G06F16/22 ,  G06F16/955

Abstract: Methods and apparatus for configurable-capacity time-series tables are disclosed. A schedule of database table management operations, including at least an operation to change a throughput constraint associated with a table in response to a triggering event, is generated. The table is instantiated with an initial throughput constraint in accordance with the schedule. Work requests directed to the table are accepted based on the initial throughput constraint. The throughput constraint is modified in response to the triggering event. Subsequent work requests are accepted based on the modified throughput constraint.

公开(公告)号：US10387578B1

公开(公告)日：2019-08-20

申请号：US14868181

申请日：2015-09-28

Applicant: Amazon Technologies, Inc.

Inventor： Wei Xiao ,  David Craig Yanacek

IPC: G06F17/30

Abstract: Capacity utilization may be controlled by a token-based allocation of input/output capacity. Operations on nested objects may utilize capacity based on factors other than input/output capacity. A capacity utilization model may be used to scale input/output utilization associated with an operation on a nested object so that the scaled input/output utilization correlates to the computing capacity used performing the operation on the nested object. The correlation may be determined to be valid for a range of attributes associated with the operation.

公开(公告)号：US10380090B1

公开(公告)日：2019-08-13

申请号：US14852295

申请日：2015-09-11

Applicant: Amazon Technologies, Inc.

Inventor： Wei Xiao ,  Usman Ahmed Shami ,  Fahad Ahmed ,  Andrew Desmond Budiman

IPC: G06F17/30 ,  G06F16/22 ,  G06F16/28

Abstract: A database may store an object comprising a hierarchy of sub-objects. Numeric identifiers may be assigned to names of the sub-objects and used in place of the names when writing the object to storage. Scalar values may be prefixed with length indicators. Collections may be prefixed with counts indicative of the number of elements in the corresponding collection. A portion of the object may be retrieved from storage by traversing a path from the root of the hierarchy to the desired portion. Length and count information may be used to skip over portions of the object during the traversal.

公开(公告)号：US20180322017A1

公开(公告)日：2018-11-08

申请号：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

CPC classification number: G06F11/1458

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.

公开(公告)号：US09917782B2

公开(公告)日：2018-03-13

申请号：US15413325

申请日：2017-01-23

Applicant: Amazon Technologies, Inc.

Inventor： Wei Xiao ,  Bjorn Patrick Swift ,  Kiran-Kumar Muniswamy-Reddy ,  Miguel Mascarenhas Filipe ,  Yijun Lu ,  Stuart Henry Seelye Marshall ,  Stefano Stefani ,  James R. Hamilton

IPC: G06F15/173 ,  H04L12/819 ,  H04L12/927 ,  H04L12/26

CPC classification number: H04L47/215 ,  H04L43/16 ,  H04L47/70 ,  H04L47/80

Abstract: Methods and apparatus for equitable distribution of excess shared-resource throughput capacity are disclosed. A first and a second work target are configured to access a shared resource to implement accepted work requests. Admission control is managed at the work targets using respective token buckets. A first metric indicative of the work request arrival rates at the work targets during a time interval, and a second metric associated with the provisioned capacities of the work targets are determined. A number of tokens determined based on a throughput limit of the shared resource is distributed among the work targets to be used for admission control during a subsequent time interval. The number of tokens distributed to each work target is based on the first metric and/or the second metric.