公开(公告)号：US08683112B2

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

申请号：US13907531

申请日：2013-05-31

Applicant: Google Inc.

Inventor： Alexandre Drobychev ,  Alexander Kesselman

IPC: G06F13/00

CPC classification number: G06F17/30578 ,  G06F17/30091 ,  G06F17/30212

Abstract: A method performed by two or more devices of a group of devices in a distributed data replication system may include receiving a group of chunks having a same unique temporary identifier, the group of chunks comprising an object to be uploaded; creating an entry for the object in a replicated index, the entry being keyed by the unique temporary identifier, and the replicated index being replicated at each of the two or more devices; and determining, by an initiating device of the two or more devices, that a union of the group of chunks contains all data of the object. The method may also include calculating a content-based identifier to the object; creating another entry for the object in the replicated index, the other entry being keyed by the content-based identifier; and updating the replicated index to point from the unique temporary identifier to the content-based identifier.

Abstract translation: 分布式数据复制系统中的一组设备的两个或多个设备执行的方法可以包括接收具有相同唯一临时标识符的一组块，该组块包括要上传的对象; 在复制索引中创建对象的条目，该条目由唯一临时标识符键入，并且复制索引被复制在两个或更多个设备中的每一个上; 以及由所述两个或多个设备的发起设备确定所述一组组合的联合包含所述对象的所有数据。 该方法还可以包括：向对象计算基于内容的标识符; 为复制索引中的对象创建另一个条目，另一个条目由基于内容的标识符键入; 并将所复制的索引更新为从唯一临时标识符指向基于内容的标识符。

公开(公告)号：US20140032200A1

公开(公告)日：2014-01-30

申请号：US14037298

申请日：2013-09-25

Applicant: Google Inc.

Inventor： Yonatan Zunger ,  Alexandre Drobychev ,  Alexander Kesselman ,  Rebekah C. Vickrey ,  Frank Clare Dachille ,  George Datuashvili

IPC: G06G7/62

CPC classification number: G06F17/30215 ,  G06F11/2094 ,  G06F11/3457 ,  H04L67/1095 ,  H04L67/1097

Abstract: A distributed storage system has a plurality of instances. A computer system simulates the state of the distributed storage system. The system obtains a current state of the distributed storage system and replication policies for objects in the distributed storage system. Each replication policy specifies criteria for placing copies of the relevant objects among the plurality of instances. The system receives proposed modifications to the state of the distributed storage system and simulates the state of the distributed storage system over time based on the current state of the distributed storage system, current statistical trends in the state of the distributed storage system, the replication policies for the objects in the distributed storage system, and the proposed modifications to the state of the distributed storage system. One or more reports are generated relating to time evolution of the state of the distributed storage system based on the simulation.

Abstract translation: 分布式存储系统具有多个实例。 计算机系统模拟分布式存储系统的状态。 系统获取分布式存储系统的当前状态和分布式存储系统中对象的复制策略。 每个复制策略指定在多个实例中放置相关对象的副本的标准。 系统接收对分布式存储系统状态的建议修改，并根据分布式存储系统的当前状态，分布式存储系统状态下的当前统计趋势，复制策略，模拟分布式存储系统随时间的状态 对于分布式存储系统中的对象，以及对分布式存储系统状态的建议修改。 基于模拟，生成与分布式存储系统的状态的时间演化相关的一个或多个报告。

公开(公告)号：US09819728B2

公开(公告)日：2017-11-14

申请号：US13874381

申请日：2013-04-30

Applicant: Google Inc.

Inventor： Alex Kesselman ,  Alexandre Drobychev

IPC: G06F15/16 ,  H04L29/08

CPC classification number: H04L67/1097 ,  G06F3/06 ,  H04L67/1002

Abstract: A system, computer-readable storage medium storing at least one program, and a computer-implemented method for facilitating deduplication of operations to be performed is presented. An operation to be performed is received. A mapping function is applied to at least one parameter of the operation to produce a mapping value in a target mapping space, the target mapping space being partitioned between target servers in a set of target servers proportional to resource capacities of the target servers in the set of target servers. A target server in the set of target servers whose portion of the target mapping space includes the mapping value is identified. The operation is issued to the target server.

公开(公告)号：US20170272503A1

公开(公告)日：2017-09-21

申请号：US13874381

申请日：2013-04-30

Applicant: Google Inc.

Inventor： Alex Kesselman ,  Alexandre Drobychev

IPC: H04L29/08

CPC classification number: H04L67/1097 ,  G06F3/06 ,  H04L67/1002

Abstract: A system, computer-readable storage medium storing at least one program, and a computer-implemented method for facilitating deduplication of operations to be performed is presented. An operation to be performed is received. A mapping function is applied to at least one parameter of the operation to produce a mapping value in a target mapping space, the target mapping space being partitioned between target servers in a set of target servers proportional to resource capacities of the target servers in the set of target servers. A target server in the set of target servers whose portion of the target mapping space includes the mapping value is identified. The operation is issued to the target server.

公开(公告)号：US09659080B1

公开(公告)日：2017-05-23

申请号：US13873132

申请日：2013-04-29

Applicant: Google Inc.

Inventor： Alexandre Drobychev ,  Michael O'Reilly ,  Mark Waldron

IPC: G06F17/30

CPC classification number: G06F17/30215 ,  G06F17/30575 ,  H04L67/1095

Abstract: A location assignment daemon (LAD) manages placement of object replicas in a distributed storage system. The distributed storage system may include a plurality of instances, which may be at distinct geographic locations. The LAD determines placement categories for objects stored in the distributed storage system. A placement category for an object corresponds to the object's placement policy and current replica locations. There are substantially fewer placement categories than objects. The LAD determines an action plan for each placement category whose associated objects require either creation or removal of object replicas. Each action plan includes either creating or removing an object replica. The LAD prioritizes the action plans and implements at least a subset of the action plans in priority order in accordance with available resources in the distributed storage system. Each action plan is applied to objects in the placement category corresponding to the action plan.

公开(公告)号：US09356793B1

公开(公告)日：2016-05-31

申请号：US13761100

申请日：2013-02-06

Applicant: GOOGLE INC.

Inventor： Alexandre Drobychev ,  Alexander Kesselman ,  George Datuashvili

IPC: G06F15/16 ,  H04L12/26

CPC classification number: H04L43/0876 ,  G06F17/30 ,  H04L67/10 ,  H04L67/1002 ,  H04L67/1095 ,  H04L67/1097 ,  H04L67/32 ,  H04L67/42

Abstract: A system, computer-readable storage medium storing at least one program, and a computer-implemented method for managing load on a downstream server in a distributed storage system is presented. Messages received from the downstream server in response to transactions issued by the upstream server to the downstream server are monitored, where the transactions are issued to the downstream server at a rate no greater than a transaction rate limit, the transaction rate limit being based at least in part on a maximum transaction processing rate of the downstream server. The transaction rate limit is adjusted based at least in part on a number of messages that include a pushback signal received over at least one predetermined time interval, where the pushback signal indicates that a utilization rate of the downstream server has exceeded a predetermined utilization rate.

Abstract translation: 提出了存储至少一个程序的系统，计算机可读存储介质以及用于在分布式存储系统中的下游服务器上管理负载的计算机实现的方法。 监视从下游服务器接收到的响应于上游服务器向下游服务器发送的事务的消息，其中以不大于事务速率限制的速率向下游服务器发送事务，事务速率限制至少基于 部分是下游服务器的最大事务处理速率。 至少部分地基于包括在至少一个预定时间间隔上接收的推回信号的消息的数量来调整事务速率限制，其中推回信号指示下游服务器的利用率已经超过预定的利用率。

公开(公告)号：US20140379715A1

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

申请号：US13927010

申请日：2013-06-25

Applicant: Google Inc.

Inventor： Alexander Kesselman ,  Alexandre Drobychev ,  George Datuashvili

IPC: G06F17/30

CPC classification number: G06F17/30598 ,  G06F3/0605 ,  G06F3/0656 ,  G06F3/067 ,  G06F17/30575 ,  H04L67/1095

Abstract: Managing placement of object replicas is performed at a first instance of a distributed storage system. One or more journals are opened for storage of object chunks. Each journal is associated with a single placement policy. A first object is received comprising at least a first object chunk. The first object is associated with a first placement policy. The first object chunk is stored in a first journal whose associated placement policy matches the first placement policy. The first journal stores only object chunks for objects whose placement policies match the first placement policy. For the first journal, the receiving and storing operations are repeated for multiple objects whose associated placement policies match the first placement policy, until a first termination condition occurs. Then, the first journal is closed. Subsequently, the first journal is replicated to a second instance of the distributed storage system according to the first placement policy.

Abstract translation: 管理对象副本的放置在分布式存储系统的第一个实例执行。 打开一个或多个日志以存储对象块。 每个日记帐都与单一的刊登位置政策相关联。 接收包括至少第一对象块的第一对象。 第一个对象与第一个放置策略相关联。 第一个对象块存储在第一个日志中，其关联的布局策略与第一个布局策略匹配。 第一个日记帐仅存储其展示位置政策与第一个展示位置政策匹配的对象的对象块。 对于第一个日志，对于其相关联的布局策略与第一布局策略匹配的多个对象重复接收和存储操作，直到发生第一终止条件。 那么，第一本杂志是关闭的。 随后，根据第一放置策略，第一个日志被复制到分布式存储系统的第二个实例。

公开(公告)号：US20140236888A1

公开(公告)日：2014-08-21

申请号：US14265298

申请日：2014-04-29

Applicant: Google Inc.

Inventor： Gia Datuashvili ,  Alexander Kesselman ,  Alexandre Drobychev

IPC: G06F17/30

CPC classification number: H04L67/1095 ,  G06F16/1748 ,  G06F16/178 ,  G06F16/184 ,  G06F16/2365 ,  G06F16/24556 ,  G06F16/27

Abstract: A method is performed by a device of a group of devices in a distributed data replication system. The method includes storing an index of objects in the distributed data replication system, the index being replicated while the objects are stored locally by the plurality of devices in the distributed data replication system. The method also includes conducting a scan of at least a portion of the index and identifying a redundant replica(s) of the at least one of the objects based on the scan of the index. The method further includes de-duplicating the redundant replica(s), and updating the index to reflect the status of the redundant replica.

Abstract translation: 一种方法由分布式数据复制系统中的一组设备的设备执行。 所述方法包括在所述分布式数据复制系统中存储对象的索引，所述索引在所述对象由所述分布式数据复制系统中的所述多个设备在本地存储的同时进行复制。 该方法还包括对索引的至少一部分进行扫描，并且基于索引的扫描来识别所述至少一个对象的冗余副本。 该方法还包括解除复制冗余副本，并更新索引以反映冗余副本的状态。

公开(公告)号：US09158472B2

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

申请号：US14142706

申请日：2013-12-27

Applicant: Google Inc.

Inventor： Alexander Kesselman ,  Michael O'Reilly ,  George Datuashvili ,  Alexandre Drobychev

IPC: G06F12/00 ,  G06F3/06

CPC classification number: G06F17/30575 ,  G06F3/0614 ,  G06F3/065 ,  G06F3/067 ,  G06F17/30321 ,  G06F17/30342

Abstract: Placement of object replicas in a distributed storage system includes, at a first instance, opening a journal for storage of object chunks. Each journal is associated with a single placement policy. An object is received, which comprises a chunk. The object has a placement policy, and the chunk comprises a plurality of storage blocks. The blocks are stored in a journal that matches the placement policy. Global metadata for the object is stored, which includes a list of chunks for the object. Local metadata for the chunk is stored, which includes a block list identifying each block of the plurality of blocks. The local metadata is associated with the journal. The journal is later closed. The journal is subsequently replicated to a second instance according to the placement policy. The global metadata is updated to reflect the replication, whereas the local metadata is unchanged by the replication.

Abstract translation: 在分布式存储系统中放置对象副本包括首先打开用于存储对象块的日志。 每个日记帐都与单一的刊登位置政策相关联。 接收到一个包含块的对象。 对象具有放置策略，并且该块包括多个存储块。 这些区块存储在与展示位置策略匹配的日记帐中。 存储对象的全局元数据，其中包含对象的块列表。 存储块的本地元数据，其包括标识多个块的每个块的块列表。 本地元数据与日记相关联。 该杂志以后关闭。 该日记随后根据放置政策复制到第二个实例。 全局元数据被更新以反映复制，而复制的本地元数据不变。

公开(公告)号：US08918555B1

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

申请号：US13669596

申请日：2012-11-06

Applicant: Google Inc.

Inventor： Alexandre Drobychev ,  Michael O'Reilly

IPC: G06F3/00 ,  G06F13/00 ,  G06F13/38

CPC classification number: G06F13/10 ,  G06F3/0608 ,  G06F3/0614 ,  G06F3/065 ,  G06F3/067 ,  G06F13/385 ,  G06F17/30212

Abstract: In one implementation, groups of objects may be maintained, each group including one or more objects that are to be replicated at one or more of the storage clusters. The objects may be assigned to the groups based on replication choices where at least some of the objects are assigned to multiple ones of the groups. A priority value may be determined and associated with each of the groups, the priority value of a particular group being determined based on priority values associated with objects within the particular group. The objects may be selected, for replication, in a replication order based on the priority value of the groups and replication of the selected objects may be initiated.

Abstract translation: 在一个实现中，可以维护对象组，每个组包括要在一个或多个存储集群中复制的一个或多个对象。 可以基于复制选择将对象分配给组，其中至少一些对象被分配给多个组。 可以确定优先级值并与每个组相关联，基于与特定组内的对象相关联的优先级值来确定特定组的优先级值。 可以基于组的优先级值以复制顺序来选择对象进行复制，并且可以启动所选对象的复制。