Operating On Objects Stored In A Distributed Database

• US 20110196882A1
• Filed: 02/09/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,838,595 B2
• Time in Patent Office: Days
• US Class Current: 707/753
• 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 operating on objects stored in a distributed database is provided. Rows of a distributed database that correspond to an index are identified. The identified rows are sorted lexicographically based on row names of the identified rows. The sorted rows are ordered by priorities of objects corresponding to the sorted rows. The objects corresponding to the sorted rows are operated on in priority order. In some embodiments, the objects are replication requests for replicating data in a distributed storage system, and operating on the objects corresponding to the sorted rows in priority order includes executing the replication requests in priority order to replicate data in the distributed storage system.

Claims

1. A computer-implemented method for operating on objects stored in a distributed database in priority order, 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 to perform the method, comprising;

identifying rows of a distributed database that correspond to an index;

sorting the identified rows lexicographically based on row names of the identified rows, wherein the sorted rows are ordered by priorities of objects corresponding to the sorted rows; and

operating on the objects corresponding to the sorted rows in priority order.

2. The method of claim 1,

wherein the objects are replication requests for replicating data in a distributed storage system;

and

wherein operating on the objects corresponding to the sorted rows in priority order includes executing the replication requests in priority order to replicate data in the distributed storage system.

3. The method of claim 1, wherein the computer system is a tablet server.

4. The method of claim 3, wherein the distributed storage system includes a plurality of tablet servers.

5. The method of claim 4, wherein a respective tablet server in the plurality of tablet servers operates on respective objects corresponding to a respective index.

6. The method of claim 1, wherein a respective row name is based on a respective index, a respective priority, and a respective unique identifier of a respective object.

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

8. A system for operating on objects stored in a distributed database in priority order, comprising:

one or more processors;

memory; and

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

identify rows of a distributed database that correspond to an index;

sort the identified rows lexicographically based on row names of the identified rows, wherein the sorted rows are ordered by priorities of objects corresponding to the sorted rows; and

operate on the objects corresponding to the sorted rows in priority order.

9. The system of claim 8,

wherein the objects are replication requests for replicating data in a distributed storage system;

and

wherein the instructions to operate on the objects corresponding to the sorted rows in priority order include instructions to execute the replication requests in priority order to replicate data in the distributed storage system.

10. The system of claim 8, wherein the computer system is a tablet server.

11. The system of claim 10, wherein the distributed storage system includes a plurality of tablet servers.

12. The system of claim 11, wherein a respective tablet server in the plurality of tablet servers operates on respective objects corresponding to a respective index.

13. The system of claim 8, wherein a respective row name is based on a respective index, a respective priority, and a respective unique identifier of a respective object.

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

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

identify rows of a distributed database that correspond to an index;

sort the identified rows lexicographically based on row names of the identified rows, wherein the sorted rows are ordered by priorities of objects corresponding to the sorted rows; and

operate on the objects corresponding to the sorted rows in priority order.

16. The computer readable storage medium of claim 15,

wherein the objects are replication requests for replicating data in a distributed storage system;

and

wherein the instructions to operate on the objects corresponding to the sorted rows in priority order include instructions to execute the replication requests in priority order to replicate data in the distributed storage system.

17. The computer readable storage medium of claim 15, wherein the computer system is a tablet server.

18. The computer readable storage medium of claim 17, wherein the distributed storage system includes a plurality of tablet servers.

19. The computer readable storage medium of claim 18, wherein a respective tablet server in the plurality of tablet servers operates on respective objects corresponding to a respective index.

20. The computer readable storage medium of claim 15, wherein a respective row name is based on a respective index, a respective priority, and a respective unique identifier of a respective object.

21. The computer readable storage medium of claim 15, wherein the index is a shard index.