公开(公告)号：US09747322B2

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

申请号：US14506530

申请日：2014-10-03

Applicant: GOOGLE INC.

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

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

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.

公开(公告)号：US09659031B2

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

申请号：US14037298

申请日：2013-09-25

Applicant: Google Inc.

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

IPC: G06F17/30 ,  G06F11/34 ,  H04L29/08 ,  G06F11/20

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.

公开(公告)号：US10009250B2

公开(公告)日：2018-06-26

申请号：US15167944

申请日：2016-05-27

Applicant: GOOGLE INC.

Inventor： Alexandre Drobychev ,  Alexander Kesselman ,  George Datuashvili

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

CPC classification number: H04L43/0876 ,  G06F16/27 ,  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.

公开(公告)号：US09600558B2

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

申请号：US13927010

申请日：2013-06-25

Applicant: Google Inc.

Inventor： Alexander Kesselman ,  Alexandre Drobychev ,  George Datuashvili

IPC: G06F7/00 ,  G06F17/30 ,  G06F3/06 ,  H04L29/08

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.

公开(公告)号：US09298736B2

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

申请号：US14293966

申请日：2014-06-02

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 method allocates object replicas in a distributed storage system. The method identifies a plurality of objects in the distributed storage system. Each object has an associated storage policy that specifies a target number of object replicas stored at distinct instances of the distributed storage system. The method identifies an object of the plurality of objects whose number of object replicas exceeds the target number of object replicas specified by the storage policy associated with the object. The method selects a first replica of the object for removal based on last access times for replicas of the object, and transmits a request to a first instance of the distributed storage system that stores the first replica. The request instructs the first instance to remove the first replica of the object.

Abstract translation: 一种方法在分布式存储系统中分配对象副本。 该方法识别分布式存储系统中的多个对象。 每个对象具有关联的存储策略，其指定存储在分布式存储系统的不同实例处的对象副本的目标数量。 该方法识别多个对象的对象，其对象副本的数量超过与对象相关联的存储策略指定的对象副本的目标数量。 该方法基于对象的副本的最后访问时间选择要删除的对象的第一副本，并将请求发送到存储第一副本的分布式存储系统的第一实例。 请求指示第一个实例删除对象的第一个副本。

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

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