MULTI-ROW TRANSACTIONS

• US 20130060742A1
• Filed: 09/02/2011
• Published: 03/07/2013
• Est. Priority Date: 09/02/2011
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Chang, Allen, Carrino, John Antonio
• Granted Patent: US 8,504,542 B2
• Time in Patent Office: Days
• US Class Current: 707/704
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data

Abstract

Techniques are provided for more efficient multi-row atomic, consistent, isolated and durable (ACID)-compliant transactions with snapshot isolation semantics (or just “multi-row transactions” for short). In some embodiments, the techniques are implemented in a computing system that includes a client application, a lightweight in-memory lease-based lock service, a multi-row transaction orchestrator, and an underlying database system. The transaction orchestrator implements a read protocol and a write protocol that provides support to the client application for carrying out multi-row transactions against the underlying database system irrespective of whether the database system itself supports multi-row transactions. The transaction orchestrator explicitly maintains transaction-level locks obtained from the lease-based lock service as part of the transaction protocol. Further, the transaction orchestrator is tolerant to lock service failure and unavailability without compromising ACID-compliance and snapshot isolation guarantees to the client application.

Claims

1. A method for writing data to a plurality of database rows as part of a multi-row transaction, the method comprising the steps of:

acquiring, from a lock service, a lock on a row of a transaction table;

after acquiring the lock, writing the data to the plurality of database rows;

after writing the data to the plurality of database rows, querying the lock service to determine whether the lock was in fact held by the lock service for the multi-row transaction since the lock was acquired from the lock service and while writing the data to the plurality of database rows; and

adding the row to the transaction table in response to determining, based on the querying, that the lock was in fact held by the lock service for the multi-row transaction since the lock was acquired from the lock service and while writing the data to the plurality of database rows;

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

2. The method of claim 1, wherein the lock service is a leased-based lock service that maintains lease records in volatile computer memory.

3. The method of claim 1, further comprising:

before writing the data to the plurality of database rows,

determining a total order for the plurality of database rows, and

acquiring, from the lock service, in the total order, a plurality of locks on the plurality of database rows.

4. The method of claim 1, further comprising:

prior to acquiring the lock, obtaining a timestamp value from a timestamp service;

wherein acquiring the lock from the lock service includes sending the timestamp value to the lock service;

wherein querying the lock service includes sending the timestamp value to the lock service.

5. The method of claim 1, further comprising:

prior to acquiring the lock, obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the multi-row transaction;

prior to adding the row to the transaction table, obtaining a second timestamp value from the timestamp service;

wherein the second timestamp value represents a commit timestamp of the multi-row transaction;

wherein the row added to the transaction table comprises the first timestamp and the second timestamp.

6. The method of claim 1, wherein adding the row to the transaction table comprises a put if absent operation.

7. The method of claim 1, further comprising:

prior to acquiring the lock, obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the multi-row transaction;

wherein writing the data to the plurality of database rows includes writing the first timestamp value to each of the plurality of database rows;

8. The method of claim 1, further comprising:

prior to writing the data to the plurality of database rows, receiving the data from a client application.

9. The method of claim 1, further comprising:

prior to acquiring the lock, obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the multi-row transaction;

before writing the data to the plurality of database rows,

acquiring, from the lock service, a plurality of locks on the plurality of database rows,

reading a second timestamp value from a particular database row of the plurality of database rows,

using the second timestamp value to read a third timestamp value from the transaction table;

wherein the multi-row transaction is a first multi-row transaction;

wherein the second timestamp value was written to the particular database row by a second multi-row transaction;

wherein the second timestamp value represents a start transaction timestamp of the second multi-row transaction;

wherein the third timestamp value represents a commit transaction timestamp of the second multi-row transaction; and

before writing the data to the plurality of database rows, comparing the third timestamp value with the first timestamp value to determine whether there is a write-write conflict between the first multi-row transaction and the second multi-row transaction; and

writing the data to the plurality of database rows after determining, based on the comparing, that there is not a write-write conflict between the first multi-row transaction and the second multi-row transaction.

10. The method of claim 9, wherein the comparing indicates that the second multi-row transaction committed before the first multi-row transaction started.

11. A method for reading data from a cell of a database table as part of a particular transaction, the cell having a plurality of values, each value associated in the cell with a corresponding write timestamp value, the method comprising the steps of:

obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the particular transaction;

reading a particular value of the plurality of values and the write timestamp value corresponding to the particular value from the cell;

wherein the write timestamp value corresponding to the particular value represents a start transaction timestamp of another transaction that wrote the particular value to the cell;

using the write timestamp value corresponding to the particular value to read a second timestamp value from a transaction table;

wherein the second timestamp value represents a commit timestamp of the other transaction that wrote the particular value to the cell;

providing the particular value to a client application in response to determining, based on a comparison between the first timestamp value and the second timestamp value, that the other transaction that wrote the particular value to the cell committed before the particular transaction started;

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

12. A non-transitory computer-readable medium storing instructions which, when executed by one or more computing devices, causes the one or more computing devices to perform a method for writing data to a plurality of database rows as part of a multi-row transaction, the method comprising the steps of:

acquiring, from a lock service, a lock on a row of a transaction table;

after acquiring the lock, writing the data to the plurality of database rows;

after writing the data to the plurality of database rows, querying the lock service to determine whether the lock was in fact held by the lock service for the multi-row transaction since the lock was acquired from the lock service and while writing the data to the plurality of database rows; and

adding the row to the transaction table in response to determining, based on the querying, that the lock was in fact held by the lock service for the multi-row transaction since the lock was acquired from the lock service and while writing the data to the plurality of database rows;

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

13. The medium of claim 12, wherein the lock service maintains lock metadata for the lock in one or more volatile memories operatively coupled to the lock service.

14. The medium of claim 12, wherein prior to adding the row to the transaction table, the row did not exist in the transaction table.

15. The medium of claim 12, the method further comprising:

prior to acquiring the lock, obtaining a timestamp value from a timestamp service;

wherein acquiring the lock from the lock service includes sending the timestamp value to the lock service;

wherein querying the lock service includes sending the timestamp value to the lock service.

16. The medium of claim 12, the method further comprising:

prior to acquiring the lock, obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the multi-row transaction;

prior to adding the row to the transaction table, obtaining a second timestamp value from the timestamp service;

wherein the second timestamp value represents a commit timestamp of the multi-row transaction;

wherein the row added to the transaction table comprises the first timestamp and the second timestamp.

17. The medium of claim 12, wherein adding the row to the transaction table comprises a put if absent operation.

18. The medium of claim 12, the method further comprising:

prior to acquiring the lock, obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the multi-row transaction;

wherein writing the data to the plurality of database rows includes writing the first timestamp value to each of the plurality of database rows;

19. The medium of claim 12, the method further comprising:

prior to writing the data to the plurality of database rows, receiving the data from a client application.

20. The medium of claim 12, the method further comprising:

prior to acquiring the lock, obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the multi-row transaction;

before writing the data to the plurality of database rows,

acquiring, from the lock service, a plurality of locks on the plurality of database rows,

reading a second timestamp value from a particular database row of the plurality of database rows,

using the second timestamp value to read a third timestamp value from the transaction table;

wherein the multi-row transaction is a first multi-row transaction;

wherein the second timestamp value was written to the particular database row by a second multi-row transaction;

wherein the second timestamp value represents a start transaction timestamp of the second multi-row transaction;

wherein the third timestamp value represents a commit transaction timestamp of the second multi-row transaction; and

before writing the data to the plurality of database rows, comparing the third timestamp value with the first timestamp value to determine whether there is a write-write conflict between the first multi-row transaction and the second multi-row transaction; and

writing the data to the plurality of database rows after determining, based on the comparing, that there is not a write-write conflict between the first multi-row transaction and the second multi-row transaction.

21. The medium of claim 20, wherein the comparing indicates that the second multi-row transaction committed before the first multi-row transaction started.

22. A non-transitory computer-readable medium storing instructions which, when executed by one or more computing devices, causes the one or more computing devices to perform a method for reading data from a cell of a database table as part of a particular transaction, the cell having a plurality of values, each value associated in the cell with a corresponding write timestamp value, the method comprising the steps of:

obtaining a first timestamp value from a timestamp service;

wherein the first timestamp value represents a start transaction timestamp of the particular transaction;

reading a particular value of the plurality of values and the write timestamp value corresponding to the particular value from the cell;

wherein the write timestamp value corresponding to the particular value represents a start transaction timestamp of another transaction that wrote the particular value to the cell;

using the write timestamp value corresponding the particular value to read a second timestamp value from a transaction table;

wherein the second timestamp value represents a commit timestamp of the other transaction that wrote the particular value to the cell;

providing the particular value to a client application in response to determining, based on a comparison between the first timestamp value and the second timestamp value, that the other transaction that wrote the particular value to the cell committed before the particular transaction started;

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

23. A system comprising:

a lock service;

one or more processors; and

one or more non-transitory computer-readable media storing instructions which, when executed by the one or more processors, cause the one or more processors to perform a method for writing data to a plurality of database rows as part of a multi-row transaction, the method comprising the steps of;

acquiring, from the lock service, a lock on a row of a transaction table;

after acquiring the lock, writing the data to the plurality of database rows;

after writing the data to the plurality of database rows, querying the lock service to determine whether the lock was in fact held by the lock service for the multi-row transaction since the lock was acquired from the lock service and while writing the data to the plurality of database rows; and

adding the row to the transaction table in response to determining, based on the querying, that the lock was in fact held by the lock service for the multi-row transaction since the lock was acquired from the lock service and while writing the data to the plurality of database rows.