公开(公告)号：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.

公开(公告)号：US20160134696A1

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

申请号：US14995171

申请日：2016-01-13

Applicant: GOOGLE INC.

Inventor： Gia Datuashvili ,  Alexander Kesselman ,  Alexandre Drobychev

IPC: H04L29/08 ,  G06F17/30

CPC classification number: H04L67/1095 ,  G06F17/30156 ,  G06F17/30174 ,  G06F17/30212 ,  G06F17/30371 ,  G06F17/30489 ,  G06F17/30575

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

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

公开(公告)号：US08775326B1

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

申请号：US13850783

申请日：2013-03-26

Applicant: Google Inc.

Inventor： Thomas Nielsen ,  Ellen Spertus ,  Alexandre Drobychev

IPC: G06Q99/00

CPC classification number: G06F21/6245 ,  G06Q10/10 ,  G06Q50/01 ,  H04L63/104 ,  H04L67/306

Abstract: Systems and methods for controlling access to relationship information in a social network are described. One described method comprises receiving a request from an observer for relationship information indicating at least a first relationship between a target in a social network and a second entity in the social network, identifying at least a first privacy rule for the first relationship, and outputting at least part of the relationship information to the observer if the first privacy rule is satisfied.

Abstract translation: 描述了用于控制对社交网络中的关系信息的访问的系统和方法。 一种描述的方法包括从观察者接收关于指示社交网络中的目标与社交网络中的第二实体之间的至少第一关系的关系信息的请求，至少识别第一关系的第一隐私规则，并且在 如果满足第一个隐私规则，则至少一部分关系信息给观察者。

公开(公告)号：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.

公开(公告)号：US20170208120A1

公开(公告)日：2017-07-20

申请号：US14996463

申请日：2016-01-15

Applicant: Google Inc.

Inventor： Alexandre Drobychev ,  Alexander Kesselman ,  Arun Subbiah

IPC: H04L29/08 ,  H04L12/24

CPC classification number: H04L67/1008 ,  G06F9/5011 ,  G06F9/5044 ,  H04L41/0896 ,  H04L67/101 ,  H04L67/1029 ,  H04L67/1097

Abstract: Methods, systems, and apparatus, including computer programs encoded on computer storage media, for throttling data probabilistically. One of the methods includes receiving, from a client device for a particular entity, a request to process data, determining a size of data to be processed, providing, to a throttler system, a bandwidth assignment request indicating the particular entity and the size of data to be processed, receiving, from the throttler system, a bandwidth assignment for the particular entity to use when serving the request, and probabilistically determining whether to currently serve the request based on the bandwidth assignment, the size of the data to be processed, and an accrued quantity of tokens for the particular entity.

公开(公告)号：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.

公开(公告)号：US09396202B1

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

申请号：US14142662

申请日：2013-12-27

Applicant: Google Inc.

Inventor： Alexandre Drobychev ,  Alexander Kesselman

IPC: G06F17/30

CPC classification number: G06F17/30153 ,  G06F17/30174

Abstract: Managing consistency of object replicas is performed at a first instance of a distributed storage system. The first instance performs garbage collection on a shard that includes a first plurality of object chunks, thereby removing a second plurality of object chunks from the shard. This leaves a third plurality of object chunks in the shard, where the first plurality of object chunks is the union of the second and third pluralities of object chunks. The first instance sends a first list of identifiers to a second instance of the distributed storage system. The second instance has a replica of the shard. The first list of identifiers specifies the object chunks in the third plurality of object chunks. The second instance removes all object chunks from the replica of the shard that are not included in the first list.

Abstract translation: 在分布式存储系统的第一个实例中执行对象副本的管理一致性。 第一实例在包括第一多个对象块的分片上执行垃圾收集，从而从分片中移除第二多个对象块。 这样在碎片中留下第三组对象块，其中第一组多个对象块是第二和第三组对象块的并集。 第一个实例将第一个标识符列表发送到分布式存储系统的第二个实例。 第二个实例有一个分片的副本。 第一个标识符列表指定第三组对象块中的对象块。 第二个实例从未包含在第一个列表中的分片的副本中删除所有对象块。

公开(公告)号：US09110823B2

公开(公告)日：2015-08-18

申请号：US14582055

申请日：2014-12-23

Applicant: Google Inc.

Inventor： Alexandre Drobychev ,  Michael O'Reilly

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