Operating on objects stored in a distributed database

• US 8,838,595 B2
• Filed: 02/09/2011
• Issued: 09/16/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/024,091
• Publication Number:
  US 20110196882A1
• Time in Patent Office: 1,315 Days
• Field of Search: None
• US Class Current: 707/736
• 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 method for managing a distributed priority queue, comprising:

at a computer system with a plurality of processors, volatile memory storing a list of queued objects in order based on a respective priority assigned to each respective object of the queued objects, and a database stored in non-volatile storage, wherein the database comprises a plurality of ranges of rows, and each range of rows corresponds to a respective unique index value;

receiving a plurality of objects and storing each respective received object in a respective row of the database according to a respective assigned index value and a respective priority of the object;

scanning a range of rows in the database corresponding to a first index value, wherein the range of rows corresponding to the first index value is sorted according to the respective priorities of the respective objects stored in the range of rows;

identifying a high priority object within the range of rows;

inserting the high priority object into the list of queued objects in priority order; and

selecting an object of highest priority from the list of queued objects and initiating execution of a task corresponding to the selected object.

2. The method of claim 1, wherein a first object of the plurality of objects is assigned a first index value, a second object of the plurality of objects is assigned a second index value, and the first index value is distinct from the second index value.

3. The method of claim 1, wherein the respective assigned index value for each respective object is based on a respective unique identifier of the respective object.

4. The method of claim 3, wherein the respective assigned index value for each respective object is computed by applying a hash function to the respective unique identifier.

5. A system for managing a distributed priority queue, comprising:

a plurality of processors;

volatile memory;

non-volatile storage;

a list of queued objects stored in the volatile memory in order based on a respective priority assigned to each respective object of the queued objects;

a database stored in the non-volatile storage, wherein the database comprises a plurality of ranges of rows, and each range of rows corresponds to a respective unique index value;

an object receiving module, which is configured to receive objects and store each respective received object in a respective row of the database according to a respective assigned index value and a respective priority of the object;

a scanning module, which is configured to;

scan a range of rows in the database corresponding to a first index value, wherein the range of rows corresponding to the first index value is sorted according to the respective priorities of the respective objects stored in the range of rows;

identify a high priority object within the range of rows; and

insert the high priority object into the list of queued objects in priority order; and

an object execution module, which is configured to select an object of highest priority from the list of queued objects and initiate execution of a task corresponding to the selected object.

6. The system of claim 5, wherein the object receiving module is further configured to assign a first index value to a first received object, and configured to assign a second index value to a second received object, wherein the first index value is distinct from the second index value.

7. The system of claim 5, wherein the respective assigned index value for each respective object is based on a respective unique identifier of the respective object.

8. The system of claim 7, wherein the respective assigned index value for each respective object is computed by applying a hash function to the respective unique identifier.

9. A non-transitory computer readable storage medium storing one or more programs configured for execution by a plurality of processors of a computer system to manage a distributed priority queue, wherein the computer system includes volatile memory storing a list of queued objects in order based on a respective priority assigned to each respective object of the queued objects, and a database stored in non-volatile storage, wherein the database comprises a plurality of ranges of rows, and each range of rows corresponds to a respective unique index value, the one or more programs comprising instructions for:

receiving a plurality of objects and storing each respective received object in a respective row of the database according to a respective assigned index value and a respective priority of the object;

scanning a range of rows in the database corresponding to a first index value, wherein the range of rows corresponding to the first index value is sorted according to the respective priorities of the respective objects stored in the range of rows;

identifying a high priority object within the range of rows;

inserting the high priority object into the list of queued objects in priority order; and

selecting an object of highest priority from the list of queued objects and initiating execution of a task corresponding to the selected object.

10. The computer readable storage medium of claim 9, wherein a first object of the plurality of objects is assigned a first index value, a second object of the plurality of objects is assigned a second index value, and the first index value is distinct from the second index value.

11. The computer readable storage medium of claim 9, wherein the respective assigned index value for each respective object is based on a respective unique identifier of the respective object.

12. The computer readable storage medium of claim 11, wherein the respective assigned index value for each respective object is computed by applying a hash function to the respective unique identifier.