公开(公告)号：US11599520B1

公开(公告)日：2023-03-07

申请号：US14753505

申请日：2015-06-29

Applicant: Amazon Technologies, Inc.

Inventor： Allan Henry Vermeulen ,  Timothy Daniel Cole ,  John Michael Morkel ,  Christopher Richard Jacques De Kadt ,  Artem Danilov ,  Andrew Wayne Ross

IPC: G06F16/245 ,  G06F16/23 ,  G06F9/46 ,  G06F16/22

Abstract: A query restriction descriptor indicating one or more attributes of a data object of a multi-data-store storage system is determined at a client-side component of the system. The query restrictions descriptor is used to prepare at least a read set descriptor of a proposed transaction. The read set of the proposed transaction includes a query with a predicate directed to the one or more attributes. A transformation function is applied to the predicate, and the result of the transformation is included in the read set descriptor. The proposed transaction is sent to a journal manager of the system, which performs read-write conflict detection using the read set descriptor and write set descriptors of one or more previously-committed transactions.

公开(公告)号：US10666569B1

公开(公告)日：2020-05-26

申请号：US15275296

申请日：2016-09-23

Applicant: Amazon Technologies, Inc.

Inventor： Christopher Richard Jacques de Kadt ,  Benjamin Warren Mercier ,  Carlos Vara Callau ,  Timothy Daniel Cole ,  Aaron Gifford Freshwater ,  Sayantan Chakravorty ,  Allan Henry Vermeulen

IPC: G06F11/14 ,  G06F16/18 ,  G06F16/23 ,  H04L12/911 ,  H04L29/08

Abstract: A journal service manages a journal that holds a number of journal entries. Journal entries are provided to the journal service by one or more producer services, and the journal service provides journal entries to one or more consumer services. Lead consumers retrieve journal entries from the journal service by specifying a named cursor which identifies a location within the journal from which the journal entries are retrieved. The journal service may select a lead producer and a lead consumer from a collection of candidate producers and consumers using a fitness score determined for each candidate producer and consumer. The fitness score may be based at least in part on the processing capability, predicted reliability, and cost of each candidate producer and consumer. The journal service may replace a lead consumer or producer with an alternate consumer or producer in response to a variety of events.

公开(公告)号：US10346434B1

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

申请号：US14833005

申请日：2015-08-21

Applicant: Amazon Technologies, Inc.

Inventor： John Michael Morkel ,  Timothy Daniel Cole ,  Artem Danilov ,  Andrew Wayne Ross ,  Christopher Richard Jacques De Kadt ,  Tate Andrew Certain ,  Allan Henry Vermeulen

IPC: G06F16/21 ,  G06F16/28

Abstract: A partitioning policy for materializing writes indicated in journal entries of a multi-data-store database is determined. The policy indicates a partitioning attribute of a data object. A write applier associated with a materialization node of the database processes journal entries according to the partitioning policy. If the value of the partitioning attribute associated with a write of a particular journal entry indicates that the write belongs to a partition materialized at the materialization node, the write applier propagates the write to the materialization node for storage at the node's storage devices.

公开(公告)号：US10324905B1

公开(公告)日：2019-06-18

申请号：US14833009

申请日：2015-08-21

Applicant: Amazon Technologies, Inc.

Inventor： Andrew Wayne Ross ,  Artem Danilov ,  Timothy Daniel Cole ,  Tate Andrew Certain ,  Christopher Richard Jacques De Kadt ,  John Michael Morkel ,  Allan Henry Vermeulen

IPC: G06F16/18 ,  G06F16/23 ,  G06F16/28

Abstract: A particular node of a journal-based multi-node distributed storage system requests the addition of an acceptability verification request entry to the journal, indicating a proposed state change of the system. The particular node examines contents of entries added to the journal after the acceptability verification request entry. After determining that a targeted set of acceptability verification response entries have been added to the journal, indicating that the potential state change meets acceptance criteria at respective other nodes of the system, the particular node requests an addition of a committed transaction entry to the journal, indicating an approval of the proposed state change.

公开(公告)号：US10303795B2

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

申请号：US14482668

申请日：2014-09-10

Applicant: Amazon Technologies, Inc.

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

IPC: G06F17/30 ,  H04L29/08

Abstract: In response to a read request directed to a first data store of a storage group, a state transition indicator is identified, corresponding to a modification that has been applied at the data store before a response to the read is prepared. A read descriptor that includes the state transition indicator and read repeatability verification metadata is prepared. The metadata can be used to check whether the read request is a repeatable read. The read descriptor is transmitted to a client-side component of the storage group.

公开(公告)号：US10198346B1

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

申请号：US14868275

申请日：2015-09-28

Applicant: Amazon Technologies, Inc.

Inventor： Timothy Daniel Cole ,  John Michael Morkel ,  Andrew Wayne Ross ,  Tate Andrew Certain ,  Artem Danilov ,  Christopher Richard Jacques De Kadt ,  Allan Henry Vermeulen

IPC: G06F17/30 ,  G06F11/36

Abstract: A test coordinator for an application whose data is to be stored at a journal-based multi-data-store database using an optimistic concurrency control protocol identifies a test descriptor. The test descriptor indicates a particular order of a plurality of events associated with the application's data, such as reads from various data stores and propagations of committed writes from the database journal to the data stores. The test coordinator uses a set of control mechanisms to cause the events to occur in a selected execution environment in the particular order, and stores an indication of a state reached by the application in response to the events.

公开(公告)号：US10108658B1

公开(公告)日：2018-10-23

申请号：US14833000

申请日：2015-08-21

Applicant: Amazon Technologies, Inc.

Inventor： Timothy Daniel Cole ,  Michael Benjamin Deardeuff ,  Artem Danilov ,  John Michael Morkel ,  Tate Andrew Certain ,  Christopher Richard Jacques De Kadt ,  Aaron Gifford Freshwater ,  Allan Henry Vermeulen ,  Andrew Wayne Ross

IPC: G06F7/00 ,  G06F17/00 ,  G06F17/30

Abstract: A data store manager of a multi-data-store journal-based database performs a sequential analysis of committed transaction entries of a journal. A particular entry includes a directive to determine a value of an attribute of a data object based on a result obtained from a value generator, and does not specify the value of the attribute. The data store manager determines the value using a local version of the value generator, and stores the value in a materialized version of the data object. In response to a programmatic read request, the data store manager provides the materialized version of the data object.

公开(公告)号：US09916372B1

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

申请号：US14268951

申请日：2014-05-02

Applicant: Amazon Technologies, Inc.

Inventor： William Nathan John Hurst ,  Timothy Daniel Cole

IPC: G06F17/30

CPC classification number: G06F17/30575 ,  G06F17/3033 ,  G06F17/30578

Abstract: Computing devices may synchronize respective copies of a repository in part by sharing status information for records stored in the repository. Status information may be conveyed by encoding record identifiers in a hashtable. A hash function may be selected to have an output range equal to or larger than a number of records in the repository. A plurality of hash function outputs may be mapped to a storage location containing a sum of identifiers and a count of identifiers included in the sum. The storage location may be transmitted to a remote computing device, which may unfold the data in the storage location to identify changed records.

公开(公告)号：US09251235B1

公开(公告)日：2016-02-02

申请号：US14024452

申请日：2013-09-11

Applicant: Amazon Technologies, Inc.

Inventor： William Nathan John Hurst ,  Timothy Daniel Cole ,  Christopher Gerald Emery ,  Ivan Avramov ,  Jonathan Peter Wright

IPC: G06K9/54 ,  G06F17/30

CPC classification number: G06F17/30581

Abstract: A device may participate in a shared data state in which editing operations performed locally are distributed and synchronized with other devices participating in the shared data state. Data may be maintained in log-structured storage files on each device. Changes made locally may be conditionally appended to log-structured storage and committed or rolled back during synchronization. Sets of related change descriptors may be identified based on inferred user intent. Conflict resolution rules may be applied to sets of related change descriptors. Conflicts may be resolved through application of conflict resolution rules or through a user-involved process.

Abstract translation: 设备可以参与共享数据状态，其中在本地执行的编辑操作与参与共享数据状态的其他设备分布和同步。 数据可以在每个设备上的日志结构存储文件中维护。 本地进行的更改可能有条件地附加到日志结构存储，并在同步期间提交或回退。 可以基于推断的用户意图来识别相关变化描述符的集合。 冲突解决规则可以应用于相关变更描述符的集合。 可以通过应用冲突解决规则或通过用户涉及的过程来解决冲突。