System and method for replicating objects in a distributed storage system

• US 8,862,617 B2
• Filed: 02/07/2011
• Issued: 10/14/2014
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kesselman, Alexander
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): Mobin, Hasanul
• Application Number:
  US13/022,564
• Publication Number:
  US 20110196873A1
• Time in Patent Office: 1,345 Days
• Field of Search: None
• US Class Current: 707/770
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A system and method for inserting an object into a distributed database is provided. An object to be inserted into a priority queue is received, wherein the object includes a unique identifier and a priority. Next, an index for the object is generated. A row name for the object is then generated based on the index, the priority of the object, and the unique identifier of the object, wherein a lexicographical order of the row name for a higher priority object is smaller than the lexicographical order of the row name for a lower priority object. The object is then inserted into a row of a distributed database using the row name.

Claims

1. A computer-implemented method for inserting an object into a distributed database, comprising:

at a computer system including one or more processors and memory storing one or more programs for execution by the one or more processors;

receiving an object to be inserted into a priority queue, wherein the object includes a unique identifier and a specified priority;

generating an index for the object by applying a hashing function to the unique identifier, wherein the index is a shard index;

converting the specified priority of the object to a string;

generating a row name for the object by combining the index, the string corresponding to the specified priority of the object, and the unique identifier of the object; and

inserting the object into a row of the distributed database according to a lexicographic order using the row name;

wherein the lexicographical order causes rows for higher priority objects to be inserted before rows for lower priority objects.

2. The method of claim 1, wherein the hashing function is selected from the group consisting of:

SHA-1; and

MD5.

3. The method of claim 1, wherein combining the index, the string, and the unique identifier comprises concatenating the index, the string, and the unique identifier.

4. The method of claim 1, wherein the object is a replication request to replicate data in a distributed storage system.

5. The method of claim 1, further comprising:

receiving a respective index;

scanning the distributed database to identify objects in the distributed database that have row names including the respective index;

sorting the identified objects based on the row names so that the identified objects are sorted in priority order; and

inserting the sorted objects into a priority queue.

6. The method of claim 5, wherein the priority queue is a replication queue, and for each respective object in the priority queue, the respective priority is based on an extent to which the respective object satisfies a respective storage policy.

7. A system for inserting an object into a distributed database, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions to;

receive an object to be inserted into a priority queue, wherein the object includes a unique identifier and a specified priority;

generate an index for the object by applying a hashing function to the unique identifier, wherein the index is a shard index;

convert the specified priority of the object to a string;

generate a row name for the object by combining the index, the string corresponding to the specified priority of the object, and the unique identifier of the object; and

insert the object into a row of the distributed database according to a lexicographic order using the row name;

wherein the lexicographical order causes rows for higher priority objects to be inserted before rows for lower priority objects.

8. The system of claim 7, wherein the hashing function is selected from the group consisting of:

SHA-1; and

MD5.

9. The system of claim 7, wherein the instructions to combine the index, the string, and the unique identifier comprise instructions to concatenate the index, the string, and the unique identifier.

10. The system of claim 7, wherein the object is a replication request to replicate data in a distributed storage system.

11. The system of claim 7, further comprising instructions to:

receive a respective index;

scan the distributed database to identify objects in the distributed database that have row names including the respective index;

sort the identified objects based on the row names so that the identified objects are sorted in priority order; and

insert the sorted objects into a priority queue.

12. The system of claim 11, wherein the priority queue is a replication queue, and for each respective object in the priority queue, the respective priority is based on an extent to which the respective object satisfies a respective storage policy.

13. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions to:

receive an object to be inserted into a priority queue, wherein the object includes a unique identifier and a specified priority;

generate an index for the object by applying a hashing function to the unique identifier, wherein the index is a shard index;

convert the specified priority of the object to a string;

generate a row name for the object by combining the index, the string corresponding to the specified priority of the object, and the unique identifier of the object; and

insert the object into a row of the distributed database according to a lexicographic order using the row name;

wherein the lexicographical order causes rows for higher priority objects to be inserted before rows for lower priority objects.

14. The computer readable storage medium of claim 13, wherein the hashing function is selected from the group consisting of:

SHA-1; and

MD5.

15. The computer readable storage medium of claim 13, wherein the instructions to combine the index, the string, and the unique identifier comprise instructions to concatenate the index, the string, and the unique identifier.

16. The computer readable storage medium of claim 13, wherein the object is a replication request to replicate data in a distributed storage system.

17. The computer readable storage medium of claim 13, further comprising instructions to:

receive a respective index;

scan the distributed database to identify objects in the distributed database that have row names including the respective index;

sort the identified objects based on the row names so that the identified objects are sorted in priority order; and

insert the sorted objects into a priority queue.

18. The computer readable storage medium of claim 17, wherein the priority queue is a replication queue, and for each respective object in the priority queue, the respective priority is based on an extent to which the respective object satisfies a respective storage policy.