公开(公告)号：US20140379922A1

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

申请号：US13926684

申请日：2013-06-25

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: H04L12/56

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.

Abstract translation: 披露了公平分配超额共享资源吞吐能力的方法和手段。 第一个和第二个工作目标被配置为访问共享资源以实现接受的工作请求。 使用相应令牌桶在工作目标上管理入学控制。 确定在时间间隔内指示工作目标的工作请求到达率的第一指标，以及与工作目标的提供能力相关联的第二度量。 基于共享资源的吞吐量限制确定的多个令牌被分配在在随后的时间间隔期间用于准入控制的工作目标中。 分配给每个工作目标的令牌数量基于第一度量和/或第二度量。

公开(公告)号：US20150268890A1

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

申请号：US14733851

申请日：2015-06-08

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

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.

Abstract translation: 实现可扩展数据存储服务的系统可以代表存储服务客户端来维护数据存储中的表。 该服务可以在存储在系统中的相应计算节点上的分区的多个副本中维护表数据。 响应于检测到系统中的异常，检测指向分区的分区或服务请求流量上的数据量的变化，或者从客户端接收分割分区的服务请求，数据存储服务可以创建附加副本 使用物理复制机制的分区副本。 数据存储服务可以发布在数据存储的API中定义的分割命令，以将原始和附加副本划分为多个副本组，并配置每个副本组以维护存储在分区中的表数据的相应部分 分裂之前。

公开(公告)号：US20140379506A1

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

申请号：US13926694

申请日：2013-06-25

Applicant: Amazon Technologies, Inc.

Inventor： STUART HENRY SEELYE MARSHALL ,  WEI XIAO ,  BJORN PATRICK SWIFT ,  KIRAN-KUMAR MUNISWAMY-REDDY ,  MIGUEL MASCARENHAS FILIPE ,  YIJUN LU ,  STEFANO STEFANI ,  JAMES R. HAMILTON

IPC: G06Q30/06

CPC classification number: H04L47/12 ,  G06F9/5005 ,  G06Q30/0283 ,  H04L47/215

Abstract: Methods and apparatus for token-based pricing policies for burst-mode operations are disclosed. A pricing policy to be applied to token population changes at a token bucket used for admission control during burst-mode operations at a work target is determined. Over a time period, changes to the token population of that bucket are recorded. A billing amount to be charged to a client is determined, based on the recorded changes in token population and an associated pricing amount indicated in the pricing policy.

Abstract translation: 公开了用于突发模式操作的基于令牌的定价策略的方法和装置。 确定在工作目标的突发模式操作期间用于接纳控制的令牌桶处的令牌容量变化的定价策略。 在一段时间内，记录对该桶的令牌群的更改。 基于记录的令牌种群的变化和定价策略中指示的相关定价金额来确定要向客户收取的计费金额。

公开(公告)号：US20140379921A1

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

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

CPC classification number: H04L47/70 ,  G06F9/5027 ,  G06F9/5061 ,  G06F11/2094 ,  H04L41/0893 ,  H04L67/10

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.

Abstract translation: 披露了网络可访问业务资源孤岛的方法和装置。 基于分组标准，选择用于数据库服务的资源的子集，包括来自多个数据中心中的每一个的至少一个资源。 筒仓路由层节点将资源仓确定为客户端工作请求所针对的目标仓库。 客户端工作请求由客户端发送到目标仓库的前端资源，或者由客户端的筒仓路由层节点发送到目标仓库的前端资源。 目标仓的前端资源将工作请求的表示发送到目标仓的后端资源，其中执行与请求相对应的工作操作。

公开(公告)号：US20140376368A1

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

申请号：US13926697

申请日：2013-06-25

Applicant: Amazon Technologies, Inc.

Inventor： WEI XIAO ,  BJORN PATRICK SWIFT ,  KIRAN-KUMAR MUNISWAMY-REDDY ,  MIGUEL MASCARENHAS FILIPE ,  YIJUN LU ,  STEFANO STEFANI ,  JAMES R. HAMILTON

IPC: H04L12/70

CPC classification number: H04L47/12

Abstract: Methods and apparatus for compound token buckets usable for burst-mode admission control are disclosed. A peak burst rate and a sustained burst rate of work requests that are to be supported at a work target are determined. The maximum token populations of a peak-burst token bucket and a sustained-burst token bucket are configured, based on the peak burst rate and the sustained burst rate respectively. In response to receiving a work request directed at the work target, a determination to accept the work request for execution is made based at least in part on the token population of the peak-burst token bucket and/or the sustained-burst token bucket.

Abstract translation: 公开了可用于突发模式准入控制的复合令牌桶的方法和装置。 确定要在工作目标中支持的峰值突发速率和工作请求的持续突发速率。 基于峰值突发速率和持续突发速率，配置峰值突发令牌桶和持续突​​发令牌桶的最大标记量。 响应于接收到针对工作目标的工作请求，至少部分地基于峰 - 突发令牌桶和/或持续突发令牌桶的令牌总数进行接受执行工作请求的确定。

公开(公告)号：US20140279905A1

公开(公告)日：2014-09-18

申请号：US13800796

申请日：2013-03-13

Applicant: AMAZON TECHNOLOGIES, INC.

Inventor： KIRAN-KUMAR MUNISWAMY-REDDY ,  BJORN PATRICK SWIFT ,  MIGUEL MASCARENHAS FILIPE ,  TIMOTHY ANDREW RATH ,  STEFANO STEFANI ,  YIJUN LU ,  WEI XIAO ,  STUART HENRY SEELYE MARSHALL ,  JAMES R. HAMILTON

IPC: G06F17/30

CPC classification number: G06F16/27 ,  G06F11/0757 ,  G06F11/2023 ,  G06F2201/84 ,  G06F2209/522

Abstract: Methods and apparatus for token-based admission control for replicated writes are disclosed. Data objects are divided into partitions, and corresponding to each partition, at least a master replica and a slave replica are stored. A determination as to whether to accept a write request directed to the partition is made based at least in part on one or more of (a) available throughput capacity at the master replica, and (b) an indication, obtained using a token-based protocol, of available throughput capacity at the slave replica. If the write request is accepted, one or more data modification operations are initiated.

Abstract translation: 公开了用于复制写入的基于令牌的准入控制的方法和装置。 数据对象分为分区，对应于每个分区，至少存储主副本和从副副本。 至少部分地基于主副本上的（a）可用吞吐量容量中的一个或多个来确定是否接受针对分区的写请求，以及（b）使用基于令牌的 协议，从属副本的可用吞吐量容量。 如果接受了写入请求，则启动一个或多个数据修改操作。

公开(公告)号：US20140258232A1

公开(公告)日：2014-09-11

申请号：US14281508

申请日：2014-05-19

Applicant: Amazon Technologies, Inc.

Inventor： STEFANO STEFANI ,  TIMOTHY ANDREW RATH ,  JAKUB KULESZA ,  WEI XIAO

IPC: G06F17/30

CPC classification number: G06F17/30584 ,  G06F11/1471 ,  G06F11/2023 ,  G06F11/2094

Abstract: A system that implements a data storage service may maintain tables in a data store on behalf of clients. The service may maintain table data in multiple replicas of partitions of the data that are stored on respective computing nodes in the system. In response to detecting a failure or fault condition, or receiving a service request from a client to move or copy a partition replica, the data store may copy a partition replica to another computing node using a physical copy mechanism. The physical copy mechanism may copy table data from physical storage locations in which it is stored to physical storage locations allocated to a destination replica on the other computing node. During copying, service requests to modify table data may be logged and applied to the replica being copied. A catch-up operation may be performed to apply modification requests received during copying to the destination replica.

Abstract translation: 实现数据存储服务的系统可以代表客户端在数据存储中维护表。 该服务可以在存储在系统中的相应计算节点上的数据的分区的多个副本中维护表数据。 响应于检测到故障或故障状况，或者从客户端接收到移动或复制分区副本的服务请求，数据存储可以使用物理复制机制将分区副本复制到另一个计算节点。 物理复制机制可以将表数据从其存储的物理存储位置复制到分配给另一个计算节点上的目标副本的物理存储位置。 在复制期间，可能会记录修改表数据的服务请求并将其应用于复制副本。 可以执行追赶操作以将复制期间接收的修改请求应用于目的地复本。

公开(公告)号：US20170075949A1

公开(公告)日：2017-03-16

申请号：US15362484

申请日：2016-11-28

Applicant: Amazon Technologies, Inc.

Inventor： STEFANO STEFANI ,  CHIRANJEEB BURAGOHAIN ,  JAI VASANTH ,  WEI XIAO

IPC: G06F17/30

CPC classification number: G06F16/235 ,  G06F16/23 ,  G06F16/2365 ,  G06F16/278

Abstract: A system that implements a scaleable data storage service may maintain tables in a non-relational data store on behalf of clients. Each table may include multiple items. Each item may include one or more attributes, each containing a name-value pair. Attribute values may be scalars or sets of numbers or strings. The system may provide an API usable to request that values of one or more of an item's attributes be updated. An update request may be conditional on expected values of one or more item attributes (e.g., the same or different item attributes). In response to a request to update the values of one or more item attributes, the previous values and/or updated values may be optionally returned for the updated item attributes or for all attributes of an item targeted by an update request. Items stored in tables may be indexed using a simple or composite primary key.

Abstract translation: 实现可扩展数据存储服务的系统可以代表客户端在非关系数据存储中维护表。 每个表可以包括多个项目。 每个项目可以包括一个或多个属性，每个属性包含名称 - 值对。 属性值可以是标量或数字或字符串集合。 系统可以提供可用于请求更新项目属性中的一个或多个的值的API。 更新请求可以以一个或多个项目属性（例如，相同或不同的项目属性）的预期值为条件。 响应于更新一个或多个项目属性的值的请求，可以可选地为更新的项目属性或由更新请求定向的项目的所有属性返回先前值和/或更新的值。 存储在表中的项目可以使用简单或复合主键进行索引。

公开(公告)号：US20150269239A1

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

申请号：US14733887

申请日：2015-06-08

Applicant: Amazon Technologies, Inc.

Inventor： BJORN PATRICK SWIFT ,  WEI XIAO ,  STUART HENRY SEELYE MARSHALL ,  STEFANO STEFANI ,  TIMOTHY ANDREW RATH ,  DAVID ALAN LUTZ

IPC: G06F17/30

CPC classification number: G06F17/30584 ,  G06F17/30575

Abstract: A system that implements a data storage service may store data in multiple replicated partitions on respective storage nodes. The selection of the storage nodes (or storage devices thereof) on which to store the partition replicas may be performed by administrative components that are responsible for partition management and resource allocation for respective groups of storage nodes (e.g., based on a global view of resource capacity or usage), or the selection of particular storage devices of a storage node may be determined by the storage node itself (e.g., based on a local view of resource capacity or usage). Placement policies applied at the administrative layer or storage layer may be based on the percentage or amount of provisioned, reserved, or available storage or IOPS capacity on each storage device, and particular placements (or subsequent operations to move partition replicas) may result in an overall resource utilization that is well balanced.

Abstract translation: 实现数据存储服务的系统可以将数据存储在相应存储节点上的多个复制分区中。 存储分区副本的存储节点（或其存储设备）的选择可以由负责相应组的存储节点的分区管理和资源分配的管理组件执行（例如，基于资源的全局视图 容量或使用），或存储节点的特定存储设备的选择可以由存储节点本身（例如，基于资源容量或用途的本地视图）来确定。 在管理层或存储层应用的布局策略可以基于每个存储设备上的配置，保留或可用存储或IOPS容量的百分比或数量，以及特定的展示位置（或后续的移动分区副本的操作）可能导致 整体资源利用情况良好。

公开(公告)号：US20150156123A1

公开(公告)日：2015-06-04

申请号：US14617671

申请日：2015-02-09

Applicant: Amazon Technologies, Inc.

Inventor： WEI XIAO ,  DAVID ALAN LUTZ ,  TIMOTHY ANDREW RATH ,  MAXIMILIANO MACCANTI ,  MIGUEL MASCARENHAS FILIPE ,  DAVID CRAIG YANACEK

IPC: H04L12/819 ,  H04L12/801

CPC classification number: H04L47/215 ,  H04L47/12 ,  H04L67/327

Abstract: A system that provides services to clients may receive and service requests, various ones of which may require different amounts of work. An admission control mechanism may manage requests based on tokens, each of which represents a fixed amount of work. The tokens may be added to a token bucket at rate that is dependent on a target work throughput rate while the number of tokens in the bucket does not exceed its maximum capacity. If at least a pre-determined minimum number of tokens is present in the bucket when a service request is received, it may be serviced. Servicing a request may include deducting an initial number of tokens from the bucket, determining that the amount of work performed in servicing the request is different than that represented by the initially deducted tokens, and deducting additional tokens from or replacing tokens in the bucket to reflect the difference.

Abstract translation: 向客户端提供服务的系统可以接收和服务请求，其中各种可能需要不同的工作量。 准入控制机制可以管理基于令牌的请求，每个代表固定的工作量。 令牌可以以取决于目标工作吞吐率的速率添加到令牌桶中，而桶中的令牌数量不超过其最大容量。 如果当接收到服务请求时，至少在桶中存在至少一个预先确定的令牌，则可以对其进行维修。 服务请求可以包括从桶中扣除初始数量的令牌，确定在服务请求中执行的工作量与最初扣除的令牌所表示的工作量不同，并从桶中扣除额外的令牌或替换令牌以反映 区别。