Processing transactions in a distributed computing system

Patent metadata

Field	Value
Publication number	US-10140329-B2
Application number	US-201615077108-A
Country	US
Kind code	B2
Filing date	Mar 22, 2016
Priority date	Apr 1, 2015
Publication date	Nov 27, 2018
Grant date	Nov 27, 2018

Abstract

Processing transactions in a distributed computing system that includes multiple processing modules includes: storing data items in a data storage system accessible to multiple processes running in the distributed computing system, where the data items are totally ordered according to an ordering rule, and at least some of the processes are running on different processing modules; and processing transactions using a plurality of the multiple processes. Processing a transaction using one of the plurality of the multiple processes includes: receiving a set of requests for accessing data items stored in the data storage system (where the requests are in a first order), obtaining locks on the data items sequentially in the first order if each of the locks is obtained within a first time interval, and, if any of the locks is not obtained within the first time interval, restarting the transaction being processed.

First claim

What is claimed is:

1. A method for processing transactions in a distributed computing system including multiple processing modules to achieve deadlock-free transaction processing, the method including:
storing data items in a data storage system accessible to multiple processes running in the distributed computing system, where the data items are totally ordered according to an ordering rule, and at least some of the processes are running on different processing modules; and
processing transactions using a plurality of the multiple processes, where processing a transaction using one of the plurality of the multiple processes includes
receiving a set of requests for accessing data items stored in the data storage system, where the requests are in a first order,
obtaining locks on the data items sequentially in the first order if each of the locks is obtained within a first time interval,
determining a second order that is consistent with the ordering rule for at least two of the locks if any of the locks is not obtained within the first time interval, and
restarting the transaction being processed, including obtaining locks on data items sequentially in the second order.

2. The method of claim 1 , wherein restarting the transaction being processed includes rolling back the transaction, releasing any existing locks on the data items.

3. The method of claim 2 , wherein the second order is consistent with the ordering rule for at least data items for which locks were obtained within the first time interval.

4. The method of claim 2 , wherein the processing further includes storing information identifying positions based on the ordering rule of data items for which locks were obtained within the first time interval, and determining the second order includes determining the second order based at least in part on the stored information identifying the positions.

5. The method of claim 2 , wherein determining the second order includes sorting a list of operations for obtaining the locks according to the ordering rule.

6. The method of claim 1 , wherein the processing further includes determining whether or not the first order is consistent with the ordering rule, and waiting longer than the first time interval for locks on any data items for which a lock was not obtained within the first time interval if the first order is consistent with the ordering rule.

7. The method of claim 1 , wherein the processing further includes determining a priority of the process that received the set of requests relative to other processes of the plurality of the multiple processes.

8. The method of claim 7 , wherein restarting the transaction being processed is performed after determining the priority.

9. The method of claim 1 , wherein restarting the transaction being processed is performed after determining that a state of a lock on at least one data item for which access was requested by the set of requests has changed.

10. The method of claim 1 , wherein the processing further includes determining whether or not the first order is consistent with the ordering rule, and restarting the transaction being processed is performed after a second time interval from determining that first order is not consistent with the ordering rule.

11. The method of claim 10 , wherein the second time interval is longer than the first time interval.

12. The method of claim 1 , wherein the first time interval is less than one second.

13. The method of claim 1 , wherein the processing further includes: holding any locks obtained on the data items until the transaction being processed is committed, aborted, or restarted; and releasing the locks on the data items when the transaction being processed is committed, aborted, or restarted.

14. The method of claim 1 , wherein the locks on the data items include at least two states including a single unlocked state and one or more locked states.

15. The method of claim 14 , wherein obtaining a lock on a data item includes changing the state of a lock associated with the data item into one of the locked states.

16. The method of claim 14 , wherein releasing a lock on a data item includes changing the state of a lock associated with the data item from one of the locked states into the unlocked state.

17. The method of claim 14 , wherein the locks on the data items include at least one exclusive locked state that permits only a single process full access to a locked data item.

18. The method of claim 17 , wherein the locks on the data items include at least one shared locked state that permits multiple processes read-only access to a locked data item.

19. The method of claim 1 , wherein at least some of the multiple processes are running asynchronously from each other.

20. The method of claim 1 , wherein the transactions include database transactions and the data items are records in a database.

21. The method of claim 20 , wherein the database is an in-memory database.

22. The method of claim 20 , wherein the data storage system is distributed among multiple nodes of the database.

23. The method of claim 1 , wherein at least some of the plurality of the multiple processes are running on different ones of the processing modules.

24. Software stored in a non-transitory form on a computer-readable medium, for processing transactions in a distributed computing system including multiple processing modules to achieve deadlock-free transaction processing, the software including instructions for causing a computing system to:
store data items in a data storage system accessible to multiple processes running in the distributed computing system, where the data items are totally ordered according to an ordering rule, and at least some of the processes are running on different processing modules; and
process transactions using a plurality of the multiple processes, where processing a transaction using one of the plurality of the multiple processes includes
receiving a set of requests for accessing data items stored in the data storage system, where the requests are in a first order,
obtaining locks on the data items sequentially in the first order if each of the locks is obtained within a first time interval,
determining a second order that is consistent with the ordering rule for at least two of the locks if any of the locks is not obtained within the first time interval, and
restarting the transaction being processed, including obtaining locks on data items sequentially in the second order.

25. The software of claim 24 , wherein the processing further includes storing information identifying positions based on the ordering rule of data items for which locks were obtained within the first time interval, and determining the second order includes determining the second order based at least in part on the stored information identifying the positions.

26. The software of claim 24 , wherein the processing further includes determining whether or not the first order is consistent with the ordering rule, and waiting longer than the first time interval for locks on any data items for which a lock was not obtained within the first time interval if the first order is consistent with the ordering rule.

27. The software of claim 24 , wherein the transactions include database transactions and the data items are records in a database.

28. The software of claim 27 , wherein the data

Assignees

• Ab Initio Technology Llc

Inventors

• Stanfill Craig W

Classifications

• G06F16/2343 Primary

  Locking methods, e.g. distributed locking or locking implementation details · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F9/466

  Transaction processing · CPC title

• G06F17/30371 Primary

  Physics · mapped topic