Granted Patent B2

US 8,554,726 · App. 13/151,203 · Granted Oct 8, 2013

Inventors: Jason Frantz (San Francisco, CA); Sergei Tsarev (San Francisco, CA); Jim Gale (San Francisco, CA); Scott Smith (San Francisco, CA); Dan Adkins (Oakland, CA)

Assignee: Clustrix, Inc.

Abstract

Claims (95)

1. A method of splitting a first slice of a representation in a distributed database into a plurality of new slices, the method comprising:

creating a plurality of write queues, each write queue corresponding to a different one of the new slices;

copying units of data in the first slice to the new slices according to a distribution function that determines, for each unit of data in the first slice, one of the new slices into which to copy the unit of data;

asynchronously writing one or more actions of a set of one or more asynchronous database transactions to the first slice, wherein each transaction of the set of asynchronous database transactions is initiated after said creating of the write queues;

asynchronously enqueuing the one or more actions of the set of asynchronous database transactions in the write queues according to the distribution function;

replaying the actions in the write queues to the new slices after completing the copying of data in the first slice to the new slices; and

controlling a speed of said asynchronously enqueuing the one or more actions of the set of asynchronous database transactions during said replaying the actions in the write queues, such that the actions in the write queues are dequeued faster than new actions are enqueued in the write queues, until the write queues are emptied,

wherein the method is performed by one or more computing devices.

2. The method of claim 1 , wherein transactions use multi-version concurrency control (MVCC).

3. The method of claim 1 , further comprising reading one or more actions of the set of asynchronous database transactions from the first slice.

4. A method of splitting a first slice of a representation in a distributed database into a plurality of new slices, the method comprising:

creating a plurality of write queues, each write queue corresponding to a different one of the new slices;

copying units of data in the first slice to the new slices according to a distribution function that determines, for each unit of data in the first slice, one of the new slices into which to copy the unit of data;

asynchronously writing one or more actions of a set of one or more asynchronous database transactions to the first slice, wherein each transaction of the set of asynchronous database transactions is initiated after said creating of the write queues;

asynchronously genqueuin the one or more actions of the set of asynchronous database transactions in the write queues according to the distribution function;

replaying the actions in the write queues to the new slices after completing the copying of data in the first slice to the new slices;

synchronously writing one or more actions of a set of one or more synchronous database transactions to the first slice, wherein each transaction of the set of synchronous database transactions is initiated after the write queues are emptied due to said replaying; and

synchronously enqueuing the one or more actions of the set of synchronous database transactions in the write queues according to the distribution function,

wherein the method is performed by one or more computing devices.

5. The method of claim 4 , further comprising:

deactivating the first slice and activating the new slices after the set of asynchronous database transactions terminates;

writing one or more actions of a set of one or more new-slice database transactions to the new slices according to the distribution function, wherein each transaction of the set of new-slice database transactions is initiated after activating the new slices; and

writing one or more actions of the set of new-slice database transactions to the first slice until the set of synchronous database transactions terminates.

6. The method of claim 5 , further comprising deleting the first slice and the write queues after the set of synchronous database transactions terminates.

7. The method of claim 5 , further comprising reading one or more actions of the set of new-slice database transactions from the new slices according to the distribution function.

8. The method of claim 4 , further comprising reading one or more actions of the set of synchronous database transactions from the first slice.

9. The method of claim 4 , wherein replaying the actions in the write queues to the new slices comprises:

reading a particular action from one of the write queues, the particular action being associated with a particular synchronous database transaction of the set of synchronous database transactions;

detecting a failure of the particular action;

updating the particular synchronous database transaction to a failed state; and

reversing all of the actions of the particular synchronous database transaction that have been written to the first slice and replayed to the queues.

10. The method of claim 4 , wherein transactions use multi-version concurrency control (MVCC).

11. The method of claim 4 , further comprising reading one or more actions of the set of asynchronous database transactions from the first slice.

12. A distributed database system comprising a reslicing system for splitting a first slice of a representation in the database into a plurality of new slices, and one or more computing devices operative to implement the reslicing system, the reslicing system being configured to:

create a plurality of new slices;

create a plurality of write queues, each write queue corresponding to a different one of the new slices;

copy units of data in the first slice to the new slices according to a distribution function that determines, for each unit of data in the first slice, one of the new slices into which to copy the unit of data;

asynchronously write one or more actions of a set of one or more asynchronous database transactions to the first slice, wherein each transaction of the set of asynchronous database transactions is initiated after the creation of the write queues;

asynchronously enqueue the one or more actions of the set of asynchronous database transactions in the write queues according to the distribution function;

replay the actions in the write queues to the new slices after completing the copying of data in the first slice to the new slices; and

control a speed of the asynchronous enqueuing of the one or more actions of the set of asynchronous database transactions during the replaying of the actions in the write queues, such that the actions in the write queues are dequeued faster than new actions are being enqueued in the write queues, until the write queues are emptied.

13. The distributed database system of claim 12 , wherein the reslicing system is further configured to read one or more actions of the set of asynchronous database transactions from the first slice.

14. A distributed database system comprising a reslicing system for splitting a first slice of a representation in the database into a plurality of new slices, and one or more computing devices operative to implement the reslicing system, the reslicing system being configured to:

create a plurality of new slices;

create a plurality of write queues, each write queue corresponding to a different one of the new slices;

copy units of data in the first slice to the new slices according to a distribution function that determines, for each unit of data in the first slice, one of the new slices into which to copy the unit of data;

asynchronously write one or more actions of a set of one or more asynchronous database transactions to the first slice, wherein each transaction of the set of asynchronous database transactions is initiated after the creation of the write queues;

asynchronously enqueue the one or more actions of the set of asynchronous database transactions in the write queues according to the distribution function;

replay the actions in the write queues to the new slices after completing the copying of data in the first slice to the new slices;

synchronously write one or more actions of a set of one or more synchronous database transactions to the first slice, wherein each transaction of the set of synchronous database transactions is initiated after the write queues are emptied due to the replaying; and

synchronously enqueue the one or more actions of the set of one or more synchronous database transactions in the write queues according to the distribution function.

15. The distributed database system of claim 14 , wherein the reslicing system is further configured to:

deactivate the first slice and activate the new slices after the set of asynchronous database transactions terminates;

write one or more actions of a set of one or more new-slice database transactions to the new slices according to the distribution function, wherein each transaction of the set of new-slice database transactions is initiated after activating the new slices; and

write one or more actions of the set of new-slice database transactions to the first slice until the set of synchronous database transactions terminates.

16. The distributed database system of claim 15 , wherein the reslicing system is further configured to delete the first slice and the write queues after the set of synchronous database transactions terminates.

17. The distributed database system of claim 14 , wherein the reslicing system is further configured to read one or more actions of the set of asynchronous database transactions from the first slice.

18. A computer-readable non-transitory storage medium comprising code for splitting a first slice of a representation in a database into a plurality of new slices, the code capable of causing one or more computing devices to:

create a plurality of new slices;

create a plurality of write queues, each write queue corresponding to a different one of the new slices;

copy units of data in the first slice to the new slices according to a distribution function that determines, for each unit of data in the first slice, one of the new slices into which to copy the unit of data;

asynchronously write one or more actions of a set of one or more asynchronous database transactions to the first slice, wherein each transaction of the set of asynchronous database transactions is initiated after the creation of the write queues;

asynchronously enqueue the one or more actions of the set of asynchronous database transactions in the write queues according to the distribution function;

replay the actions in the write queues to the new slices after completing the copying of data in the first slice to the new slices; and

control a speed of the asynchronous enqueuing of the one or more actions of the set of asynchronous database transactions during the replaying of the actions in the write queues, such that the actions in the write queues are dequeued faster than new actions are being enqueued in the write queues, until the write queues are emptied.

19. The medium of claim 18 , the code further capable of causing one or more computing devices to read one or more actions of the set of asynchronous database transactions from the first slice.

20. A computer-readable non-transitory storage medium comprising code for splitting a first slice of a representation in a database into a plurality of new slices, the code capable of causing one or more computing devices to:

create a plurality of new slices;

create a plurality of write queues, each write queue corresponding to a different one of the new slices;

copy units of data in the first slice to the new slices according to a distribution function that determines, for each unit of data in the first slice, one of the new slices into which to copy the unit of data;

asynchronously write one or more actions of a set of one or more asynchronous database transactions to the first slice, wherein each transaction of the set of asynchronous database transactions is initiated after the creation of the write queues;

asynchronously enqueue the one or more actions of the set of asynchronous database transactions in the write queues according to the distribution function;

replay the actions in the write queues to the new slices after completing the copying of data in the first slice to the new slices;

synchronously write one or more actions of a set of one or more synchronous database transactions to the first slice, wherein each transaction of the set of synchronous database transactions is initiated after the write queues are emptied due to the replaying; and

synchronously enqueue the one or more actions of the first set of one or more synchronous database transactions in the write queues according to the distribution function.

21. The medium of claim 20 , the code further capable of causing one or more computing devices to:

deactivate the first slice and activate the new slices after the set of asynchronous database transactions terminates;

write one or more actions of a set of one or more new-slice database transactions to the new slices according to the distribution function, wherein each transaction of the set of new-slice database transactions is initiated after activating the new slices; and

write one or more actions of the set of new-slice database transactions to the first slice until the set of synchronous database transactions terminates.

22. The medium of claim 21 , the code further capable of causing one or more computing devices to delete the first slice and the write queues after the set of synchronous database transactions terminates.

23. The medium of claim 20 , the code further capable of causing one or more computing devices to read one or more actions of the set of asynchronous database transactions from the first slice.

24. A method of splitting a first slice of a representation in a distributed database into a plurality of new slices, the method comprising:

creating the new slices;

creating a plurality of write queues, each write queue corresponding to a different one of the new slices;

copying units of data in the first slice to the new slices according to a distribution function that determines, for each unit of data in the first slice, one of the new slices into which to copy the unit of data;

writing one or more actions of one or more database transactions to the first slice after beginning said copying;

enqueuing the one or more actions of the one or more database transactions in the write queues according to the distribution function;

replaying the actions in the write queues to the new slices;

activating the new slices; and

deactivating the first slice,

wherein the method is performed by one or more computing devices.

25. The method of claim 24 , wherein no write locks are applied to the first slice during said copying, writing, enqueuing, and replaying.

26. The method of claim 24 , further comprising conducting database transactions associated with the first slice during said copying, writing, enqueuing, and replaying.

27. The method of claim 26 , further comprising conducting substantially all received database transactions associated with the first slice during said copying, writing, enqueuing, and replaying.

28. The method of claim 24 , further comprising writing the one or more actions of the one or more database transactions to the first slice during said copying.

Assignments (10)

Continuity (1)