公开(公告)号：US09519510B2

公开(公告)日：2016-12-13

申请号：US14231077

申请日：2014-03-31

Applicant: Amazon Technologies, Inc.

Inventor： Jacob A. Strauss ,  Matteo Frigo ,  Alex Haugland ,  Matti Juhani Oikarinen ,  Pradeep Vincent ,  Joshua Samuel Hendrickson

IPC: G06F7/00 ,  G06F17/00 ,  G06F9/46

CPC classification number: G06F9/467 ,  G06F9/466

Abstract: A node of a storage service is selected as a coordinator of a distributed transaction involving multiple page-level modifications. The coordinator identifies other nodes as members of a node chain collectively storing physical data pages at which proposed modifications are to be performed, including a decider node responsible for a decision to commit the transaction. The coordinator generates a transaction preparation message comprising a representation of an order of respective commit decisions associated with the proposed modifications, and transmits the message to a selected node of the chain for a sequential propagation along the chain. Each chain node performs a local commit analysis for its changes and stores a record of its intent to commit. If a decision to commit is reached at the decider, the proposed modifications are completed.

Abstract translation: 选择存储服务的节点作为涉及多个页面级修改的分布式事务的协调器。 协调器将其他节点标识为节点链的成员，共同存储将要执行所提出的修改的物理数据页，包括负责决定提交事务的决定节点。 协调器生成交易准备消息，其包括与所提出的修改相关联的各自提交决定的顺序的表示，并且将消息发送到链的所选节点，以沿着链的顺序传播。 每个链节点对其更改执行本地提交分析，并存储其提交意图的记录。 如果决定者达成了作出决定，则建议的修改完成。

公开(公告)号：US09495478B2

公开(公告)日：2016-11-15

申请号：US14231095

申请日：2014-03-31

Applicant: Amazon Technologies, Inc.

Inventor： Joshua Samuel Hendrickson ,  Matti Juhani Oikarinen ,  Alex Haugland ,  Pradeep Vincent ,  Matteo Frigo ,  Xiaobin Wu

IPC: G06F17/30

CPC classification number: G06F17/30958 ,  G06F17/30097

Abstract: A directed acyclic graph (DAG) is generated to represent a namespace of a directory. In response to a request to create a new object with a specified name, a hash value bit sequence is computed for the name. A plurality of levels of the DAG are navigated using successive subsequences of the bit sequence to identify a candidate node for storing a new entry corresponding to the specified name. If the candidate node meets a split criterion, the new entry and at least a selected subset of entries of the candidate node's list of entries are distributed among a plurality of DAG nodes, including at least one new DAG node, using respective bit sequences obtained by applying the hash function for each distributed entry.

Abstract translation: 生成有向无环图（DAG）来表示目录的命名空间。 响应于创建具有指定名称的新对象的请求，为该名称计算哈希值比特序列。 使用比特序列的连续子序列导航多个DAG级别，以识别用于存储与指定名称相对应的新条目的候选节点。 如果候选节点满足分割标准，则候选节点的条目列表的新条目和至少一个选定的条目子集在包括至少一个新的DAG节点的多个DAG节点之间分配，使用由 对每个分布式条目应用散列函数。