公开(公告)号：US20160292249A1

公开(公告)日：2016-10-06

申请号：US15090547

申请日：2016-04-04

Applicant: Amazon Technologies, Inc.

Inventor： JAI VASANTH ,  BARRY BAILEY HUNTER, JR. ,  KIRAN-KUMAR MUNISWAMY-REDDY ,  DAVID ALAN LUTZ ,  JIAN WANG ,  MAXIMILIANO MACCANTI

IPC: G06F17/30 ,  G06F11/07 ,  G06F11/00 ,  G06F9/48 ,  H04L29/08

CPC classification number: G06F17/30575 ,  G06F3/0617 ,  G06F9/4881 ,  G06F11/006 ,  G06F11/07 ,  G06F11/0709 ,  G06F11/0793 ,  G06F2201/86 ,  H04L67/1095

Abstract: Detecting replica faults within a replica group and dynamically scheduling replica healing operations are described. Status metadata for one or more replica groups may be accessed. Based, at least in part, the status data a number of available replicas for at least one replica group may be determined to incompliant with a healthy state definition for the replica group. One or more healing operations to restore the number of available replicas for the at least one replica group to the respective healthy state definition may be dynamically scheduled. In some embodiments, one or more resource constraints for performing healing operations and one or more resource requirements for each of the one or more healing operations may be used to order the one or more healing operations.

Abstract translation: 对副本组中的副本故障进行检测并动态调度复制恢复操作。 可以访问一个或多个副本组的状态元数据。 至少部分地基于状态数据，至少一个副本组的可用副本的数量可以被确定为与副本组的健康状态定义不一致。 可以动态地调度用于将至少一个副本组的可用副本的数量恢复到相应的健康状态定义的一个或多个愈合操作。 在一些实施例中，用于执行愈合操作的一个或多个资源约束和针对所述一个或多个愈合操作中的每一个的一个或多个资源需求可用于对一个或多个愈合操作进行排序。

公开(公告)号：US20170161160A1

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

申请号：US15413764

申请日：2017-01-24

Applicant: Amazon Technologies, Inc.

Inventor： MICHAEL T. HELMICK ,  JAKUB KULESZA ,  TIMOTHY ANDREW RATH ,  STEFANO STEFANI ,  DAVID ALAN LUTZ

IPC: G06F11/20

CPC classification number: G06F11/2025 ,  G06F11/00 ,  G06F11/2028 ,  G06F11/2041 ,  G06F11/2046 ,  G06F11/2097

Abstract: Disclosed are various embodiments for distributing data items within a plurality of nodes. A data item that is subject to a data item update request is updated from a master node to a plurality of slave notes. The update of the data item is determined to be locality-based durable based at least in part on acknowledgements received from the slave nodes. Upon detection that the master node has failed, a new master candidate is determined via an election among the plurality of slave nodes.

公开(公告)号：US20150363124A1

公开(公告)日：2015-12-17

申请号：US14834392

申请日：2015-08-24

Applicant: Amazon Technologies, Inc.

Inventor： TIMOTHY ANDREW RATH ,  JAKUB KULESZA ,  DAVID ALAN LUTZ

IPC: G06F3/06 ,  H04L29/08

CPC classification number: H04L41/0668 ,  G06F3/0617 ,  G06F3/0653 ,  G06F3/0659 ,  G06F3/0683 ,  G06F11/1425 ,  G06F11/1662 ,  G06F11/2028 ,  G06F11/2041 ,  G06F11/2048 ,  G06F11/2094 ,  G06F11/2097 ,  G06F2201/825 ,  H04L67/1097 ,  H04L67/16

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.

Abstract translation: 实现数据存储服务的系统可以代表存储服务客户端存储数据。 系统可以将数据保存在存储在系统中各个计算节点上的各种分区的多个副本中。 系统可以使用单个主故障切换协议，当副本尝试成为其所属的副本组的主副本时可用。 尝试成为主副本可能包括获取与副本组相关联的锁，以及从组中的其他副本收集状态信息。 状态信息可以指示另一个副本是否支持尝试（在这种情况下它被包括在故障切换仲裁中），或存储比尝试成为主机的副本更多的最新数据或元数据（在这种情况下可能需要同步）。 如果故障转移仲裁包含足够的副本，副本可能会成为主服务器。

公开(公告)号：US20150301901A1

公开(公告)日：2015-10-22

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

Abstract translation: 实现数据存储服务的系统可以代表存储服务客户端存储数据。 系统可以在存储在系统中的相应计算节点上的分区的多个副本中维护数据。 副本组的主副本可以增加组的成员版本指示符，并且可以向组的其他成员传播指示组的成员变化的元数据（包括成员版本指示符）。 传播元数据可以包括将包含元数据的日志记录发送到要附加到其各自日志的其他副本。 一旦成员变更变得持久，可能会被提交。 尝试成为副本组的主人的副本可能会确定组中的另一个副本已经观察到更新的成员身份版本，在这种情况下，日志可以被同步或剪切，或尝试可能被放弃。

公开(公告)号：US20160285678A1

公开(公告)日：2016-09-29

申请号：US15179812

申请日：2016-06-10

Applicant: Amazon Technologies, Inc.

Inventor： TIMOTHY ANDREW RATH ,  JAKUB KULESZA ,  DAVID ALAN LUTZ

IPC: H04L12/24 ,  H04L29/08

CPC classification number: H04L41/0668 ,  G06F3/0617 ,  G06F3/0653 ,  G06F3/0659 ,  G06F3/0683 ,  G06F11/1425 ,  G06F11/1662 ,  G06F11/2028 ,  G06F11/2041 ,  G06F11/2048 ,  G06F11/2094 ,  G06F11/2097 ,  G06F2201/825 ,  H04L67/1097 ,  H04L67/16

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.

公开(公告)号：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中定义的分割命令，以将原始和附加副本划分为多个副本组，并配置每个副本组以维护存储在分区中的表数据的相应部分 分裂之前。

公开(公告)号：US20150046395A1

公开(公告)日：2015-02-12

申请号：US14491789

申请日：2014-09-19

Applicant: Amazon Technologies, Inc.

Inventor： TIMOTHY ANDREW RATH ,  DAVID ALAN LUTZ

IPC: G06F17/30

CPC classification number: G06F16/27 ,  G06F16/182 ,  G06F16/273 ,  G06F16/278 ,  H04W84/20

Abstract: A system that implements a data storage service may store data on behalf of clients in multiple replicas on respective computing nodes. The system may employ an external service to select a master replica for a replica group. The master replica may service consistent read operations and/or write operations that are directed to the replica group (or to a data partition stored by the replica group). The master replica may employ a quorum based mechanism for performing replicated write operations, and a local lease mechanism for determining the replica authorized to perform consistent reads, even when the external service is unavailable. The master replica may propagate local leases to replica group members as replicated writes. If another replica assumes mastership for the replica group, it may not begin servicing consistent read operations that are directed to the replica group until the lease period for a current local lease expires.

Abstract translation: 实现数据存储服务的系统可以将代表客户端的数据存储在各个计算节点上的多个副本中。 系统可以使用外部服务来为副本组选择主副本。 主副本可以服务于针对副本组（或由副本组存储的数据分区）的一致的读取操作和/或写入操作。 主副本可以采用基于仲裁的机制来执行复制的写操作，以及用于确定被授权执行一致读取的副本的本地租赁机制，即使当外部服务不可用时。 主副本可以将本地租约作为复制的写入传播给副本组成员。 如果另一个副本对于副本组承担主管权，那么在当前本地租赁的租赁期到期之前，它可能无法开始服务定向到副本组的一致的读取操作。

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

公开(公告)号：US20150120658A1

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

申请号：US14589884

申请日：2015-01-05

Applicant: Amazon Technologies, Inc.

Inventor： TIMOTHY ANDREW RATH ,  JAKUB KULESZA ,  DAVID ALAN LUTZ

IPC: G06F17/30

CPC classification number: G06F17/30584 ,  G06F17/30215 ,  G06F17/30575

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. The system may split a data partition into two new partitions, and may split the replica group that stored the original partitions into two new replica groups, each storing one of the new partitions. To split the replica group, the master replica may propagate membership changes to the other members of the replica group for adding members to the original replica group and for splitting the expanded replica group into two new replica groups. Subsequent to the split, replicas may attempt to become the master for the original replica group or for a new replica group. If an attempt to become master replica for the original replica group succeeds, the split may fail.

Abstract translation: 实现数据存储服务的系统可以代表存储服务客户端存储数据。 系统可以在存储在系统中的相应计算节点上的分区的多个副本中维护数据。 系统可以将数据分区拆分成两个新的分区，并且可以将存储原始分区的副本组拆分成两个新的副本组，每个副本组存储一个新的分区。 要拆分副本组，主副本可能将成员身份更改传播到副本组的其他成员，以将成员添加到原始副本组，并将扩展副本组分成两个新的副本组。 分割后，副本可能会尝试成为原始副本组或新副本组的主节点。 如果尝试成为原始副本组的主副本成功，则拆分可能会失败。