Granted Patent B2

US 9,348,883 · App. 13/151,040 · Granted May 24, 2016

Inventors: Jim Gale (San Francisco, CA); Scott Smith (San Francisco, CA)

Assignee: CLUSTRIX, INC.

G06F17/30578

Abstract

Claims (58)

1. A method of replaying transactions in a slave database, the method comprising:

receiving a sequence of events executed on a master database, the sequence of events associated with one or more tables and at least one transaction of the master database;

identifying a first row of the one or more tables associated with a first event in the sequence;

identifying a second row of the one or more tables associated with a second event in the sequence, the second event after the first event; and

replaying the first and second events on the slave database in parallel if the first and second rows are different rows with unique sets of values, and otherwise replaying the first and second events serially;

wherein the first and second rows are each associated with a first table of the one or more tables,

wherein identifying the first row associated with the first event includes identifying a value of a primary key of the first table associated with the first event, and wherein identifying the second row associated with the second event includes identifying a value of the primary key associated with the second event,

wherein replaying comprises determining that the first and second rows are different rows based on the value of the primary key associated with the first event and the value of the primary key associated with the second event, and

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

2. The method of claim 1 , further comprising:

identifying a third row associated with a third event in the sequence, the third event after the first and second events; and

replaying the first, second and third events on the slave database at least partially in parallel in a first batch if the first, second and third rows each are different rows with unique sets of values.

3. The method of claim 2 , further comprising:

identifying a fourth row associated with a fourth event in the sequence, the fourth event after the first, second and third events; and

replaying the fourth event on the slave database in a second batch after replaying the first batch if the fourth row is the same row as any of the first, second, and third rows, and otherwise replaying the first, second, third and fourth events at least partially in parallel in the first batch if the first, second, third and fourth rows each are different rows with unique sets of values.

4. The method of claim 1 , wherein replaying the first and second events on the slave database comprises replaying the first and second events in parallel when the value of the primary key associated with the first event is different than the value of the primary key associated with the second event.

5. The method of claim 1 , wherein said replaying the first and second events on the slave database in parallel when the first and second rows are different rows with unique sets of values comprises:

storing the value of the primary key associated with the first event in a lock table; and

determining that the first and second rows are different rows by determining that the value of the primary key associated with the second event is not included in the lock table.

6. The method of claim 5 , further comprising responding to the determination that the value of the primary key associated with the second event is not included in the lock table by adding the value of the primary key associated with the second event to the lock table.

7. The method of claim 5 , wherein the first event is a row update, and wherein identifying the first row associated with the first event includes identifying a first value of the primary key associated with a value of the first row before the update and indentifying a second value of the primary key associated with a value of the first row after the update, and wherein storing the value of the primary key associated with the first event in the lock table comprises storing the first value and the second value of the primary key in the lock table.

8. The method of claim 5 , wherein said otherwise replaying the first and second events serially comprises determining that the value of the primary key associated with the second event is included in the lock table.

9. The method of claim 8 , further comprising removing all of the values from the lock table.

10. The method of claim 1 , wherein the first and second rows are each associated with a first table of the one or more tables, and wherein identifying the first row associated with the first event further includes identifying a value of at least one unique key of the first table associated with the first event, and wherein identifying the second row associated with the second event further includes identifying a value of the least one unique key associated with the second event.

11. The method of claim 1 , wherein receiving the sequence of events comprises receiving a portion of a transaction log from a master database.

12. The method of claim 11 , further comprising:

identifying a special event in the portion of the transaction log; and

executing the special event in isolation from the other events in the sequence of events.

13. The method of claim 12 , wherein the special event includes at least one of a table creation, a table deletion, a column creation or a column deletion.

14. A non-transitory computer-readable storage medium comprising instructions that when executed perform a method of replaying transactions in a slave database, the method comprising:

receiving a sequence of events executed on a master database, the sequence of events associated with one or more tables and at least one transaction of the master database;

identifying a first row of the one or more tables associated with a first event in the sequence;

identifying a second row of the one or more tables associated with a second event in the sequence, the second event after the first event; and

replaying the first and second events on the slave database in parallel if the first and second rows are different rows with unique sets of values, and otherwise replaying the first and second events serially,

wherein the first and second rows are each associated with a first table of the one or more tables,

wherein identifying the first row associated with the first event includes identifying a value of a primary key of the first table associated with the first event, and wherein identifying the second row associated with the second event includes identifying a value of the primary key associated with the second event, and

wherein replaying comprises determining that the first and second rows are different rows based on the value of the primary key associated with the first event and the value of the primary key associated with the second event.

15. The computer-readable storage medium of claim 14 , the method further comprising:

identifying a third row associated with a third event in the sequence, the third event after the first and second events; and

replaying the first, second and third events on the slave database at least partially in parallel in a first batch if the first, second and third rows each are different rows with unique sets of values.

16. The computer-readable storage medium of claim 14 , wherein replaying the first and second events on the slave database comprises replaying the first and second events in parallel when the value of the primary key associated with the first event is different than the value of the primary key associated with the second event.

17. The computer-readable storage medium of claim 14 , wherein said replaying the first and second events on the slave database in parallel when the first and second rows are different rows with unique sets of values comprises:

storing the value of the primary key associated with the first event in a lock table; and

determining that the first and second rows are different rows by determining that the value of the primary key associated with the second event is not included in the lock table.

18. The computer-readable storage medium of claim 17 , the method further comprising responding to the determination that the value of the primary key associated with the second event is not included in the lock table by adding the value of the primary key associated with the second event to the lock table.

19. The computer-readable storage medium of claim 17 , wherein said otherwise replaying the first and second events serially comprises determining that the value of the primary key associated with the second event is included in the lock table.

20. A system for replaying transactions on a slave database, the system comprising:

a slave replay module configured to receive a transaction log including a sequence of events executed on a master database, the sequence of events associated with one or more tables and at least one transaction of the master database; and

one or more computing devices operative to implement the slave replay module;

wherein the slave replay module is configured to identify a first row of the one or more tables associated with a first event in the sequence, and to identify a second row of the one or more tables associated with a second event in the sequence, the second event after the first event,

wherein the slave replay module is configured to replay the first and second events on the slave database in parallel if the first and second rows are different rows with unique sets of values and to otherwise replay the first and second events serially,

wherein the first and second rows are each associated with a first table of the one or more tables,

wherein identifying the first row associated with the first event includes identifying a value of a primary key of the first table associated with the first event, and wherein identifying the second row associated with the second event includes identifying a value of the primary key associated with the second event,

wherein replaying comprises determining that the first and second rows are different rows based on the value of the primary key associated with the first event and the value of the primary key associated with the second event.

21. The system of claim 20 , wherein the slave replay module is further configured to identify a third row associated with a third event in the sequence, the third event after the first and second events, and to replay the first, second and third events on the slave database at least partially in parallel in a first batch if the first, second and third rows each are different rows with unique sets of values.

22. The system of claim 20 , wherein the slave replay module is further configured to replay the first and second events in parallel when the value of the primary key associated with the first event is different than the value of the primary key associated with the second event.

23. The system of claim 20 , further comprising a lock table, wherein the slave replay module is further configured to store the value of the primary key associated with the first event in the lock table, and wherein the slave replay module is further configured to determine that the first and second rows are different rows by determining that the value of the primary key associated with the second event is not included in the lock table.

24. The system of claim 23 , wherein the slave replay module is further configured to respond to the determination that the value of the primary key associated with the second event is not included in the lock table by adding the value of the primary key associated with the second event to the lock table.

Assignments (11)

Continuity (1)