CONVERTING A SERIAL TRANSACTION SCHEDULE TO A PARALLEL TRANSACTION SCHEDULE

• US 20160085639A1
• Filed: 09/19/2014
• Published: 03/24/2016
• Est. Priority Date: 09/19/2014
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Daniil Golod, Mohammed Abouzour
• Inventors: Bumbulis, Peter, Goel, Anil Kumar, Bowman, Ivan Thomas, Farrar, Daniel James, Abouzour, Mohammed, Smirnios, John, Golod, Daniil
• Granted Patent: US 9,594,644 B2
• Time in Patent Office: 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:

storing a list of data transactions in a transaction log;

reading, using one or more processors at a computer system, a respective data transaction from the transaction log;

adding the respective data transaction into a first transaction queue in a plurality of concurrent transaction queues;

reading the respective data transaction from the first transaction queue, wherein a plurality of data transactions are concurrently read off the plurality of concurrent transaction queues;

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

applying the respective data transaction to a reconstructed data set; and

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

delaying commitment of the respective data transaction until the second data transaction has been applied to the reconstructed data set.

2. The method of claim 1, wherein the list of data transactions represents data changes made to a data set over a period of time.

3. The method of claim 1, wherein a data transaction is represented by a data transaction record.

4. The method of claim 3, wherein a data transaction record includes at least one data change and a target data address.

5. The method of claim 1, wherein a data transaction is currently pending if it has been read from the transaction log but not applied to the reconstructed data set.

6. The method of claim 1, wherein the respective data transaction is determined to be dependent on the second data transaction if both the respective data transaction and the second data transaction have the same associated target data address and the second data transaction has priority over the respective data transaction.

7. The method of claim 1, wherein adding the respective data transaction to a first transaction queue in a plurality of concurrent transaction queues further includes:

selecting the first transaction queue from the plurality of concurrent transaction queues based on metadata associated with the respective data transaction.

8. The method of claim 3, wherein determining whether the respective data transaction is dependent on any other currently pending data transaction further includes:

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

based on the target data address stored in a data transaction record associated with the respective data transaction, accessing an entry in the data dependency table that is associated with the target data address and determining whether the entry includes an identifier of a currently pending data transaction; and

in accordance with a determination that the entry includes an identifier of a currently pending data transaction,

updating the data transaction record associated with the respective data transaction to include dependency data.

9. 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;

storing a list of data transactions in a transaction log;

reading a respective data transaction from the transaction log;

adding the respective data transaction into a first transaction queue in a plurality of concurrent transaction queues;

reading the respective data transaction from the first transaction queue, wherein a plurality of data transactions are concurrently read off the plurality of concurrent transaction queues;

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

applying the respective data transaction to a reconstructed data set; and

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

delaying commitment of the respective data transaction until the second data transaction has been applied to the reconstructed data set.

10. The system of claim 9, wherein the list of data transactions represents data changes made to a data set over a period of time.

11. The system of claim 9, wherein a data transaction is represented by a data transaction record.

12. The system of claim 11, wherein a data transaction record includes at least one data change and a target data address.

13. The system of claim 9, wherein a data transaction is currently pending if it has been read from the transaction log but not applied to the reconstructed data set.

14. The system of claim 9, wherein the respective data transaction is determined to be dependent on the second data transaction if both the respective data transaction and the second data transaction have the same associated target data address and the second data transaction has priority over the respective data transaction.

15. The system of claim 9, wherein the instructions for adding the respective data transaction to a first transaction queue in a plurality of concurrent transaction queues further include instructions for:

selecting the first transaction queue from the plurality of concurrent transaction queues based on metadata associated with the respective data transaction.

16. The system of claim 11, wherein determining whether the respective data transaction is dependent on any other currently pending data transaction further includes:

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

based on the target data address stored in a data transaction record associated with the respective data transaction, accessing an entry in the data dependency table that is associated with the target data address and determining whether the entry includes an identifier of a currently pending data transaction; and

in accordance with a determination that the entry includes an identifier of a currently pending data transaction,

updating the data transaction record associated with the respective data transaction to include dependency data.

17. 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:

storing a list of data transactions in a transaction log;

reading a respective data transaction from the transaction log;

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

applying the respective data transaction to a reconstructed data set;

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

delaying commitment of the respective data transaction until the second data transaction has been applied to the reconstructed data set.

18. The non-transitory computer-readable storage medium of claim 17, wherein the list of data transactions represents data changes made to a data set over a period of time.

19. The non-transitory computer-readable storage medium of claim 17, wherein a data transaction is represented by a data transaction record.

20. The non-transitory computer-readable storage medium of claim 19, wherein a data transaction record includes at least one data change and a target data address.