Granted Patent B2

US 9,626,422 · App. 14/047,958 · Granted Apr 18, 2017

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.

G06F17/30595G06F17/30306G06F17/30584

Abstract

Claims (75)

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, without waiting for each action to succeed before moving on to the next action, wherein each transaction of the set of asynchronous database transactions is initiated after beginning said copying and before completing said copying; and

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

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

2. The method of claim 1 , further comprising 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.

3. The method of claim 2 , further comprising 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.

4. The method of claim 2 , further comprising:

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 each transaction of the set of synchronous database transactions is initiated after the write queues are emptied due to said replaying.

5. The method of claim 1 , 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 1 , wherein transactions use multi-version concurrency control (MVCC).

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

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

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

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

12. A distributed database system comprising one or more processors configured to split a first slice of a representation in the database into a plurality of new slices, the one or more processors 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, without waiting for each action to succeed before moving on to the next action, wherein each transaction of the set of asynchronous database transactions is initiated after the system begins said copy and before completing said copying; and

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

13. The distributed database system of claim 12 , wherein the reslicing system is further configured to 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.

14. The distributed database system of claim 13 , wherein the reslicing system is further configured to 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.

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

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,

wherein each transaction of the set of synchronous database transactions is initiated after the write queues are emptied due to said replaying.

16. The distributed database system of claim 12 , 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.

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

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, without waiting for each action to succeed before moving on to the next action, wherein each transaction of the set of asynchronous database transactions is initiated after the one or more computing devices begin said copy and before completing said copying; and

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

19. The distributed database system of claim 18 , wherein the reslicing system is further configured to 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.

20. The distributed database system of claim 19 , wherein the reslicing system is further configured to 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.

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

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,

wherein each transaction of the set of synchronous database transactions is initiated after the write queues are emptied due to said replaying.

22. The distributed database system of claim 18 , 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.

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

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; and

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

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

25. The method of claim 24 , further comprising:

activating the new slices after said replaying; and

deactivating the first slice.

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

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

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

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

Assignments (9)

Continuity (2)