Alexander Kesselman

US Patent:

8271455, Sep 18, 2012

Filed:

Feb 9, 2011

Appl. No.:

13/024186

Inventors:

Alexander Kesselman - Sunnyvale CA, US

Assignee:

Google, Inc. - Mountain View CA

International Classification:

G06F 7/00

US Classification:

707679, 707770, 707812, 707969, 707974

Abstract:

A system and method for storing replication requests for objects in a distributed storage system is provided. A plurality of replication requests for objects stored on storage devices in a distributed storage system is received. Respective row keys are generated for respective replication requests in the plurality of replication requests based on parameters of the respective replication requests. The respective row keys include respective globally-determined priorities for the respective replication requests that facilitate sorting of the respective replication requests by priority. The respective replication requests are stored in respective records of a distributed database using the respective row keys, wherein the respective records of the distributed database are distributed across a plurality of nodes of the distributed database.

US Patent:

8285686, Oct 9, 2012

Filed:

Feb 9, 2011

Appl. No.:

13/024243

Inventors:

Alexander Kesselman - Sunnyvale CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 7/00

US Classification:

707679, 707770, 707812, 707969, 707974

Abstract:

A system and method for executing replication requests for objects in a distributed storage system is provided. A replication queue is identified from a plurality of replication queues corresponding to a replication key. The replication key includes information related to at least a source storage device in a distributed storage system at which objects are located and a destination storage device in the distributed storage system to which the objects are to be replicated. A distributed database is scanned using an identifier of the replication queue to produce a list of replication requests corresponding to the replication queue. The records of the distributed database are distributed across a plurality of nodes of the distributed database. The replication requests in the list of replication requests are executed in priority order. Replication requests are deleted from the distributed database only when the replication requests are complete.

US Patent:

8335769, Dec 18, 2012

Filed:

Feb 9, 2011

Appl. No.:

13/024259

Inventors:

Alexander Kesselman - Sunnyvale CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 7/00

US Classification:

707679, 707770, 707812, 707969, 707974

Abstract:

A system and method for executing replication requests for objects in a distributed database is provided. A plurality of replication requests for objects in a distributed storage system is received. The replication requests are partitioned into one or more replication queues. A respective replication queue includes replication requests that have a respective replication key. The respective replication key includes information related to at least a respective source storage device at which a respective object is located and a respective destination storage device to which the respective object is to be replicated. For each respective replication queue, the replication requests in the replication queue are sorted based on priorities of the replication requests. Commands to execute a highest priority request are issued in each respective replication queue. When a respective replication request is completed, the respective replication request is deleted from the replication queue.

US Patent:

8341118, Dec 25, 2012

Filed:

Feb 7, 2011

Appl. No.:

13/022579

Inventors:

Alexandre Drobychev - San Jose CA, US
Alexander Kesselman - Sunnyvale CA, US
Rebekah C. Vickrey - Mountain View CA, US
Frank C. Dachille - Mountain View CA, US
George Datuashvili - Cupertino CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 17/30

US Classification:

707636, 707635, 707626

Abstract:

A server computer at a first storage sub-system of a distributed storage system receives from a client a first client request for an object. If the object is not present in the first storage sub-system, the server computer identifies a second storage sub-system of the distributed storage system as having a replica of the requested object, the requested object including content and metadata. The server computer submits an object replication request for the requested object to the second storage sub-system and independently receives the content and metadata of the requested object from the second storage sub-system. The server computer generates a new replica of the object at the first storage sub-system using the received metadata and content and returns the metadata of the new replica of the object to the client.

US Patent:

8346820, Jan 1, 2013

Filed:

Dec 22, 2009

Appl. No.:

12/644689

Inventors:

Alexander Kesselman - Sunnyvale CA, US
Alexandre Drobychev - San Jose CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 12/00

US Classification:

707813

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.

US Patent:

8352424, Jan 8, 2013

Filed:

Feb 7, 2011

Appl. No.:

13/022290

Inventors:

Yonatan Zunger - Mountain View CA, US
Alexandre Drobychev - San Jose CA, US
Alexander Kesselman - Sunnyvale CA, US
Rebekah C. Vickrey - Mountain View CA, US
Frank C. Dachille - Mountain View CA, US
George Datuashvili - Cupertino CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 7/00
G06F 17/00

US Classification:

707610, 707611, 707612, 707624, 707625, 709248

Abstract:

A system and method for generating replication requests for objects in a distributed storage system is provided. Replication requests for objects in a distributed storage system are generated based at least in part on replication policies for the objects and a current state of the distributed storage system, wherein a respective replication request for a respective object instructs a respective instance of the distributed storage system to replicate the respective object so as to at least partially satisfy a replication policy for the respective object, wherein a respective replication policy includes criteria specifying at least storage device types on which replicas of object are to be stored. At least a subset of the replication requests is then distributed to the respective instances of the distributed storage system for execution.

US Patent:

8423517, Apr 16, 2013

Filed:

Feb 7, 2011

Appl. No.:

13/022551

Inventors:

Alexander Kesselman - Sunnyvale CA, US
Alexandre Drobychev - San Jose CA, US
Daniel J. Ford - East Palo Alto CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 17/30

US Classification:

707689

Abstract:

A system and method for determining an age of an object is provided. A first index for a timestamp entry in a sequence of timestamps corresponding to a time at which an object was created is identified. At least one subsequence of timestamps from the sequence of timestamps having indexes for entries in the sequence of timestamps that are between the first index in the sequence of timestamps and a last index for a last timestamp entry in the sequence of timestamps is identified, wherein the at least one subsequence of timestamps conforms to a function of a time interval between storage of consecutive current timestamps reported by clock of the computer system. Timestamps from the sequence of timestamps that are not included in the at least one subsequence of timestamps are removed. An age of the object is determined based on the at least one subsequence of timestamps.

US Patent:

8468291, Jun 18, 2013

Filed:

Apr 11, 2012

Appl. No.:

13/444247

Inventors:

Alexandre Drobychev - San Jose CA, US
Alexander Kesselman - Sunnyvale CA, US

Assignee:

Google Inc. - Mountain View CA

International Classification:

G06F 13/00

US Classification:

711100, 711163, 711164

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.