Converting a serial transaction schedule to a parallel transaction schedule

• US 9,594,644 B2
• Filed: 09/19/2014
• Issued: 03/14/2017
• Est. Priority Date: 09/19/2014
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Abouzour, Mohammed, Smirnios, John, Golod, Daniil, Bumbulis, Peter, Goel, Anil Kumar, Bowman, Ivan Thomas, Farrar, Daniel James
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US14/491,269
• Publication Number:
  US 20160085639A1
• Time in Patent Office: 907 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06Q 20/389 Keeping log of transactions for guaranteeing non-repudiation of a transaction

Abstract

A method and system for transforming a serial schedule of transactions into a parallel schedule of transaction is disclosed. In one example, a computer system stores a list of data transactions in a transaction log. The computer system then reads a respective data transaction from the transaction log. The computer system determines whether the respective data transaction is dependent on any other currently pending data transaction. In accordance with a determination that the respective data transaction is not dependent on any other currently pending data transaction, the computer system applies the data changes to a reconstructed data set. In accordance with a determination that the respective data transaction is dependent on a currently pending second data transaction, the computer system delays commitment of the respective data transaction until the second data transaction has been applied to the reconstructed data set.

Claims

1. A method comprising:

reading each of a plurality of data transaction records from a single transaction log in a sequence in which the plurality of data transaction records were added to the transaction log, each of the plurality of data transaction records indicating a change to be applied to a section of a data set;

for each respective data transaction record read from the transaction log in the sequence in which the plurality of data transaction records were added to the transaction log;

selecting, based on metadata associated with the respective data transaction record, a single transaction queue from a plurality of first in, first out (FIFO) transaction queues for the respective data transaction record; and

adding a pending data transaction for the respective data transaction record into the selected transaction queue; and

concurrently processing the plurality of FIFO transaction queues, the processing comprising, for each associated transaction queue of the plurality of FIFO transaction queues;

determining whether a next pending data transaction of the associated transaction queue is dependent on any other pending data transaction in the plurality of FIFO transaction queues based on the section of the data set indicated in the next pending data transaction;

in accordance with a determination that the next pending data transaction is not dependent on any other pending data transaction in the plurality of FIFO transaction queues;

applying the next pending data transaction to the data set; and

removing the next pending data transaction from the associated transaction queue; and

in accordance with a determination that the next pending data transaction is dependent on another pending data transaction in the plurality of FIFO transaction queues;

waiting until the other pending data transaction has been applied to the data set; and

after waiting until the other pending data transaction has been applied;

applying the next pending data transaction to the data set; and

removing the next pending data transaction from the associated transaction queue.

2. The method of claim 1, wherein the plurality of data transaction records represent data changes made to the data set over a period of time.

3. The method of claim 1, wherein, in each of the plurality of data transaction records, the section of the data set is indicated by a target data address.

4. The method of claim 1, wherein the next pending data transaction is determined to be dependent on the other pending data transaction when both the next pending data transaction and the other pending data transaction are to be applied to a same section of the data set and the other pending data transaction has priority over the next pending data transaction.

5. The method of claim 1, further comprising, for each respective data transaction record read from the transaction log:

accessing a data dependency table that stores dependency data for the data set;

based on the section of the data set indicated in the respective data transaction record, accessing an entry in the data dependency table that is associated with the section of the data set and determining whether the entry includes an identifier of a pending data transaction in the plurality of FIFO transaction queues; and

in accordance with a determination that the entry includes an identifier of the pending data transaction in the plurality of FIFO transaction queues, updating the pending data transaction for the respective data transaction record to include dependency data.

6. A system comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions that, when executed by the one or more processors, cause the system to perform operations comprising;

reading each of a plurality of data transaction records from a single transaction log in a sequence in which the plurality of data transaction records were added to the transaction log, each of the plurality of data transaction records indicating a change to be applied to a section of a data set;

for each respective data transaction record read from the transaction log in the sequence in which the plurality of data transaction records were added to the transaction log;

selecting, based on metadata associated with the respective data transaction record, a single transaction queue from a plurality of first in, first out (FIFO) transaction queues for the respective data transaction record; and

adding a pending data transaction for the respective data transaction record into the selected transaction queue; and

concurrently processing the plurality of FIFO transaction queues, the processing comprising, for each associated transaction queue of the plurality of FIFO transaction queues,

determining whether a next pending data transaction of the associated transaction queue is dependent on any other pending data transaction in the plurality of FIFO transaction queues based on the section of the data set indicated in the next pending data transaction;

in accordance with a determination that the respective data transaction is not dependent on any other currently pending data transaction;

applying the next pending data transaction to the data set; and

removing the next pending data transaction from the associated transaction queue; and

in accordance with a determination that the next pending data transaction is not dependent on any other pending data transaction in the plurality of FIFO transaction queues;

waiting until the other pending data transaction has been applied to the data set; and

after waiting until the other pending data transaction has been applied;

 

applying the next pending data transaction to the data set; and

 

removing the next pending data transaction from the associated transaction queue.

7. The system of claim 6, wherein the plurality of data transaction records represent data changes made to the data set over a period of time.

8. The system of claim 6, wherein, in each of the plurality of data transaction records, the section of the data set is indicated by a target data address.

9. The system of claim 6, wherein the next pending data transaction is determined to be dependent on the other pending data transaction when both the next pending data transaction and the other pending data transaction are to be applied to a same section of the data set and the other pending data transaction has priority over the next pending data transaction.

10. The system of claim 6, the operations further comprising, for each respective data transaction record read from the transaction log:

accessing a data dependency table that stores dependency data for the data set;

based on the section of the data set indicated in the respective data transaction record, accessing an entry in the data dependency table that is associated with the section of the data set and determining whether the entry includes an identifier of a pending data transaction in the plurality of FIFO transaction queues; and

in accordance with a determination that the entry includes an identifier of the pending data transaction in the plurality of FIFO transaction queues, updating the pending data transaction for the respective data transaction record to include dependency data.

11. A non-transitory computer-readable storage medium storing one or more programs for execution by one or more processors of a machine, the one or more programs comprising instructions that, when executed by the one or more processors, cause the machine to perform operations comprising:

reading each of a plurality of data transaction records from a single transaction log in a sequence in which the plurality of data transaction records were added to the transaction log, each of the plurality of data transaction records indicating a change to be applied to a section of a data set;

for each respective data transaction record read from the transaction log in the sequence in which the plurality of data transaction records were added to the transaction log;

selecting, based on metadata associated with the respective data transaction record, a single transaction queue from a plurality of first in, first out (FIFO) transaction queues for the respective data transaction record; and

adding a pending data transaction for the respective data transaction record into the selected transaction queue; and

concurrently processing the plurality of FIFO transaction queues, the processing comprising, for each associated transaction queue of the plurality of FIFO transaction queues;

determining whether a next pending data transaction of the associated transaction queue is dependent on any other pending data transaction in the plurality of FIFO transaction queues based on the section of the data set indicated in the next pending data transaction;

in accordance with a determination that the next pending data transaction is not dependent on any other pending data transaction in the plurality of FIFO transaction queues;

applying the next pending data transaction to the data set; and

removing the next pending data transaction from the associated transaction queue; and

in accordance with a determination that the next pending data transaction is dependent on another pending data transaction in the plurality of FIFO transaction queues;

waiting until the other pending data transaction has been applied to the data set; and

after waiting until the other pending data transaction has been applied;

applying the next pending data transaction to the data set; and

removing the next pending data transaction from the associated transaction queue.

12. The non-transitory computer-readable storage medium of claim 11, wherein the plurality of data transaction records represent data changes made to the data set over a period of time.

13. The non-transitory computer-readable storage medium of claim 11, wherein, in each of the plurality of data transaction records, the section of the data set is indicated by a target data address.