公开(公告)号：US20150189013A1

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

申请号：US14582055

申请日：2014-12-23

Applicant: Google Inc.

Inventor： Alexandre Drobychev ,  Michael O'Reilly

IPC: H04L29/08

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

公开(公告)号：US20160277275A1

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

申请号：US15167944

申请日：2016-05-27

Applicant: GOOGLE INC.

Inventor： Alexandre Drobychev ,  Alexander Kesselman ,  George Datuashvili

IPC: H04L12/26 ,  H04L29/06 ,  H04L29/08

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

Abstract: The various embodiments described herein include methods, systems, and devices for managing load in a distributed storage system. In one aspect, a method is performed at a first instance server in the distributed storage system, the first instance server having memory and at least one processor coupled to the memory. The method includes: (i) issuing a first plurality of requests to a second instance server; (ii) obtaining one or more messages from the second instance server in response to the first plurality of requests, the messages indicating a utilization rate of the second instance server; (iii) determining a transaction rate limit for the second instance server based on the utilization rate of the second instance server; and (iv) issuing a second plurality of requests to the second instance server, where the second plurality of requests are issued at a rate no greater than the transaction rate limit.

Abstract translation: 本文描述的各种实施例包括用于管理分布式存储系统中的负载的方法，系统和设备。 一方面，在分布式存储系统中的第一实例服务器处执行一种方法，所述第一实例服务器具有存储器，并且至少一个处理器耦合到所述存储器。 该方法包括：（i）向第二实例服务器发出第一多个请求; （ii）响应于所述第一多个请求从所述第二实例服务器获得一个或多个消息，所述消息指示所述第二实例服务器的利用率; （iii）基于第二实例服务器的利用率确定第二实例服务器的事务速率限制; 以及（iv）向所述第二实例服务器发出第二多个请求，其中以不大于所述事务速率限制的速率发出所述第二多个请求。

公开(公告)号：US20160275125A1

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

申请号：US15144700

申请日：2016-05-02

Applicant: GOOGLE INC.

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

IPC: G06F17/30

CPC classification number: G06F16/23 ,  G06F3/065 ,  G06F16/122 ,  G06F16/248 ,  G06F16/27

Abstract: A distributed storage system stores data for files. A first blob (binary large object) of data is received. The first blob is split into one or more first chunks of data. Content fingerprints for the first chunks of data are computed. The first chunks of data are stored in a chunk store while and their content fingerprints are stored in a store distinct from the chunk store. A second blob of data is received. The second blob is split into one or more second chunks of data. Content fingerprints for the second chunks of data are computed. Then for a second chunk of data whose content fingerprint matches a content fingerprint of a first chunk of data, a second reference to the corresponding first chunk of data that has a matching content fingerprint is stored, but the second chunk of data is not stored.

Abstract translation: 分布式存储系统存储文件数据。 接收到第一个blob（二进制大对象）数据。 第一个blob被分成一个或多个第一批数据。 计算第一批数据的内容指纹。 第一批数据被存储在块存储器中，并且它们的内容指纹被存储在与块存储器不同的存储器中。 接收第二个数据块。 第二个Blob被分成一个或多个第二个数据块。 计算第二批数据的内容指纹。 然后，对于其内容指纹与第一组数据的内容指纹匹配的第二数据块，存储具有匹配内容指纹的对应的第一数据块的第二参考，但不存储第二组数据。

公开(公告)号：US09400828B2

公开(公告)日：2016-07-26

申请号：US14882205

申请日：2015-10-13

Applicant: Google Inc.

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

IPC: G06F17/30 ,  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. An object is received, which comprises one or more chunks. Each chunk comprises one or more storage blocks. The blocks for a single chunk are stored in a single journal. 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. The global metadata is updated to reflect the replication, whereas the local metadata is unchanged by the replication.

Abstract translation: 在分布式存储系统中放置对象副本包括首先打开用于存储对象块的日志。 接收到一个包含一个或多个块的对象。 每个块包括一个或多个存储块。 单个块的块存储在单个日志中。 存储对象的全局元数据，其中包含对象的块列表。 存储块的本地元数据，其包括标识多个块的每个块的块列表。 本地元数据与日记相关联。 该杂志以后关闭。 该日记随后被复制到第二个实例。 全局元数据被更新以反映复制，而复制的本地元数据不变。

公开(公告)号：US09317524B2

公开(公告)日：2016-04-19

申请号：US14538716

申请日：2014-11-11

Applicant: GOOGLE INC.

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

IPC: G06F17/00 ,  G06F7/00 ,  G06F17/30 ,  G06F13/10 ,  G06G7/62 ,  H04L29/08

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

Abstract: A system and method for generating replication requests for objects in a distributed storage system is provided. For a respective object in a distributed storage system the following is performed. Replication policies for the object that have not been satisfied are determined. Replication requests are ranked for the object whose replication policies have not been satisfied based on a number of replicas of the object that need to be created in order to satisfy the replication policies for the object. Replication requests are generated for the object based at least in part on the replication policies for the object that have not been satisfied and on a current state of the distributed storage system. At least a subset of the replication requests for the objects in the distributed storage system are distributed to respective instances of the distributed storage system corresponding to the replication requests for execution.

Abstract translation: 提供了一种用于在分布式存储系统中生成对象的复制请求的系统和方法。 对于分布式存储系统中的相应对象，执行以下操作。 确定尚未满足的对象的复制策略。 基于需要创建的对象的副本的数量，为了满足对象的复制策略，复制请求被排序为其复制策略尚未满足的对象。 至少部分地基于对于尚未满足的对象和分布式存储系统的当前状态的复制策略为该对象生成复制请求。 对分布式存储系统中的对象的复制请求的至少一个子集分配到与复制请求执行相对应的分布式存储系统的相应实例。

公开(公告)号：US20160034549A1

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

申请号：US14882205

申请日：2015-10-13

Applicant: Google Inc.

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

IPC: G06F17/30

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. An object is received, which comprises one or more chunks. Each chunk comprises one or more storage blocks. The blocks for a single chunk are stored in a single journal. 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. The global metadata is updated to reflect the replication, whereas the local metadata is unchanged by the replication.

Abstract translation: 在分布式存储系统中放置对象副本包括首先打开用于存储对象块的日志。 接收到一个包含一个或多个块的对象。 每个块包括一个或多个存储块。 单个块的块存储在单个日志中。 存储对象的全局元数据，其中包含对象的块列表。 存储块的本地元数据，其包括标识多个块的每个块的块列表。 本地元数据与日记相关联。 该杂志以后关闭。 该日记随后被复制到第二个实例。 全局元数据被更新以反映复制，而复制的本地元数据不变。

公开(公告)号：US09081841B2

公开(公告)日：2015-07-14

申请号：US13732041

申请日：2012-12-31

Applicant: GOOGLE INC.

Inventor： Alexander Kesselman ,  Alexandre Drobychev

IPC: G06F17/30 ,  G06F3/06 ,  G06F12/02

CPC classification number: G06F17/30578 ,  G06F3/0605 ,  G06F3/0619 ,  G06F3/0652 ,  G06F3/067 ,  G06F12/0269 ,  G06F17/30215

Abstract: A method may be performed by a device of a group of devices in a distributed data replication system. The method may include storing objects in a data store, at least one or more of the objects being replicated with the distributed data replication system, and conducting a scan of the objects in the data store. The method may further include identifying one of the objects as not having a reference pointing to the object, storing a delete negotiation message as metadata associated with the one of the objects, and replicating the metadata with the delete negotiation message to one or more other devices of the group of devices.

Abstract translation: 一种方法可以由分布式数据复制系统中的一组设备的设备执行。 该方法可以包括将对象存储在数据存储器中，所述对象中的至少一个或多个被复制分布式数据复制系统，并对数据存储中的对象进行扫描。 该方法还可以包括将对象中的一个标识为不具有指向对象的引用，将删除协商消息存储为与该对象之一相关联的元数据，并将具有删除协商消息的元数据复制到一个或多个其他设备 的设备组。

公开(公告)号：US20150186043A1

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

申请号：US14142706

申请日：2013-12-27

Applicant: Google Inc.

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

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

公开(公告)号：US20150142743A1

公开(公告)日：2015-05-21

申请号：US14538716

申请日：2014-11-11

Applicant: GOOGLE INC.

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

IPC: G06F17/30

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

Abstract: A system and method for generating replication requests for objects in a distributed storage system is provided. For a respective object in a distributed storage system the following is performed. Replication policies for the object that have not been satisfied are determined. Replication requests are ranked for the object whose replication policies have not been satisfied based on a number of replicas of the object that need to be created in order to satisfy the replication policies for the object. Replication requests are generated for the object based at least in part on the replication policies for the object that have not been satisfied and on a current state of the distributed storage system. At least a subset of the replication requests for the objects in the distributed storage system are distributed to respective instances of the distributed storage system corresponding to the replication requests for execution.

Abstract translation: 提供了一种用于在分布式存储系统中生成对象的复制请求的系统和方法。 对于分布式存储系统中的相应对象，执行以下操作。 确定尚未满足的对象的复制策略。 基于需要创建的对象的副本的数量，为了满足对象的复制策略，复制请求被排序为其复制策略尚未满足的对象。 至少部分地基于对于尚未满足的对象和分布式存储系统的当前状态的复制策略为该对象生成复制请求。 对分布式存储系统中的对象的复制请求的至少一个子集分配到与复制请求执行相对应的分布式存储系统的相应实例。

公开(公告)号：US20150026128A1

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

申请号：US14506530

申请日：2014-10-03

Applicant: GOOGLE INC.

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

IPC: G06F17/30

CPC classification number: G06F17/30345 ,  G06F3/065 ,  G06F17/30082 ,  G06F17/30554 ,  G06F17/30575

Abstract: A distributed storage system has multiple instances. There is a plurality of local instances, and at least some of the local instances are at physically distinct geographic locations. Each local instance is configured to store data for a non-empty set of blobs in a plurality of data stores having a plurality of distinct data store types. In addition, each local instance stores metadata for the respective set of blobs in a metadata store distinct from the data stores. There is also a plurality of global instances. Each global instance is configured to store data for zero or more blobs in zero or more data stores and store metadata for all blobs stored at any local or global instance. The system selects one global instance to run a replication module that replicates blobs between instances according to blob policies. Some systems also include dynamic replication based on user needs.

Abstract translation: 分布式存储系统有多个实例。 存在多个本地实例，并且至少一些本地实例位于物理上不同的地理位置。 每个本地实例被配置为在具有多个不同数据存储类型的多个数据存储器中存储用于非空的一组Blob的数据。 此外，每个本地实例存储与数据存储不同的元数据存储中的相应组的组的元数据。 还有多个全局实例。 每个全局实例被配置为在零个或多个数据存储中存储零个或多个blob的数据，并存储在任何本地或全局实例中存储的所有blob的元数据。 系统选择一个全局实例来运行复制模块，该复制模块根据blob策略在实例之间复制Blob。 一些系统还包括基于用户需求的动态复制。