System and Method for Replicating Objects In A Distributed Storage System

• US 20110196873A1
• Filed: 02/07/2011
• Published: 08/11/2011
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kesselman, Alexander
• Granted Patent: US 8,862,617 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• 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 priority;

generating an index for the object;

generating a row name for the object 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; and

inserting the object into a row of the distributed database using the row name.

2. The method of claim 1, wherein generating the index includes generating the index by applying a hashing function to the unique identifier.

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

SHA-1 ; and

MD5.

4. The method of claim 2, wherein generating the row name for the object based on the index and the priority of the object includes:

converting the priority of the object to a string, wherein a lexicographical order of the string for a higher priority object is smaller than the lexicographical order of the string for a lower priority object; and

generating the row name for the object by concatenating the index, the string corresponding to the priority of the object, and the unique identifier of the object.

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

6. The method of claim 1, wherein the index is a shard index.

7. 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.

8. The method of claim 7, wherein the priority queue is a replication queue.

9. 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 priority;

generate an index for the object;

generate a row name for the object 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; and

insert the object into a row of the distributed database using the row name.

10. The system of claim 9, wherein the instructions to generate the index include instructions to generate the index by applying a hashing function to the unique identifier.

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

SHA-1; and

MD5.

12. The system of claim 9, wherein the instructions to generate the row name for the object based on the index and the priority of the object include instructions to:

convert the priority of the object to a string, wherein a lexicographical order of the string for a higher priority object is smaller than the lexicographical order of the string for a lower priority object; and

generate the row name for the object by concatenating the index, the string corresponding to the priority of the object, and the unique identifier of the object.

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

14. The system of claim 9, wherein the index is a shard index.

15. The system of claim 9, 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.

16. The system of claim 15, wherein the priority queue is a replication queue.

17. 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 priority;

generate an index for the object;

generate a row name for the object 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; and

insert the object into a row of the distributed database using the row name.

18. The computer readable storage medium of claim 17, wherein the instructions to generate the index include instructions to generate the index by applying a hashing function to the unique identifier.

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

SHA-1; and

MD5.

20. The computer readable storage medium of claim 17, wherein the instructions to generate the row name for the object based on the index and the priority of the object include instructions to:

convert the priority of the object to a string, wherein a lexicographical order of the string for a higher priority object is smaller than the lexicographical order of the string for a lower priority object; and

generate the row name for the object by concatenating the index, the string corresponding to the priority of the object, and the unique identifier of the object.

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

22. The computer readable storage medium of claim 17, wherein the index is a shard index.

23. The computer readable storage medium of claim 17, 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.

24. The computer readable storage medium of claim 23, wherein the priority queue is a replication queue.