Multi-row transactions

• US 8,954,410 B2
• Filed: 08/05/2013
• Issued: 02/10/2015
• 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
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Allen, Nicholas
• Application Number:
  US13/958,817
• Publication Number:
  US 20130318060A1
• Time in Patent Office: 554 Days
• Field of Search: None
• 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 comprising:

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

after acquiring the lock, writing data to a plurality of database rows as part of the transaction, the plurality of database rows not including the row representing the transaction;

querying the lock service to validate the lock after writing the data to the plurality of database rows;

attempting to commit the transaction after successfully validating the lock;

wherein attempting to commit the transaction comprises attempting to atomically add the row representing the transaction to the database table;

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 an order for the plurality of database rows, and

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

4. The method of claim 1, further comprising:

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

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:

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

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

obtaining a second timestamp value from the timestamp service prior to attempting to atomically add the row to the table;

wherein the second timestamp value represents a commit timestamp of the transaction;

wherein attempting to atomically add the row to the database table comprises successfully adding the row to the database table and including the first timestamp value and the second timestamp value as at least part of the added row.

6. The method of claim 1, wherein attempting to atomically add the row to the table comprises performing a put if absent operation.

7. The method of claim 1, further comprising:

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

wherein the first timestamp value represents a start timestamp of a 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:

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

9. The method of claim 1, further comprising:

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

wherein the first timestamp value represents a start timestamp of a first database 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, and

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

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

wherein the second timestamp value represents a start timestamp of the second transaction;

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

comparing the third timestamp value with the first timestamp value to determine whether there is a write-write conflict between the first transaction and the second transaction;

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

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

11. A system comprising:

one or more computing devices having at least a processor and memory and including a transaction orchestrator that;

acquires, from a lock service, a lock on a row of a database table, the row representing transaction;

writes data to a plurality of database rows after acquiring the lock, wherein the plurality of database rows do not include the row representing the transaction;

queries the lock service to validate the lock after writing the data to the plurality of database rows;

attempts to atomically add the row to the database table after successfully validating the lock in an attempt to commit the transaction.

12. The system of claim 11, wherein the lock service is a leased-based lock service that maintains lease records in volatile computer memory.

13. The system of claim 11, wherein the transaction orchestrator:

before writing the data to the plurality of database rows,

determines an order for the plurality of database rows, and

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

14. The system of claim 11, wherein the transaction orchestrator:

obtains a timestamp value from a timestamp service prior to acquiring the lock;

acquires the lock from the lock service by at least sending the timestamp value to the lock service;

queries the lock service by at least sending the timestamp value to the lock service.

15. The system of claim 11, wherein the transaction orchestrator:

obtains a first timestamp value from a timestamp service prior to acquiring the lock, wherein the first timestamp value represents a start timestamp of a transaction;

obtains a second timestamp value from the timestamp service prior to attempting to atomically add the row to the table, wherein the second timestamp value represents a commit timestamp of the transaction;

successfully adds the row to the table; and

includes the first timestamp value and the second timestamp value as part of the added row.

16. The system of claim 11, wherein the transaction orchestrator attempts to atomically add the row to the table by at least performing a put if absent operation.

17. The system of claim 11, wherein the transaction orchestrator:

obtains a first timestamp value from a timestamp service prior to acquiring the lock, wherein the first timestamp value represents a start timestamp of a transaction; and

writes the data to the plurality of database rows by at least writing the first timestamp value to each of the plurality of database rows.

18. The system of claim 11, wherein the transaction orchestrator receives the data from a client application prior to writing the data to the plurality of database rows.

19. The system of claim 11, wherein the transaction orchestrator:

obtains a first timestamp value from a timestamp service prior to acquiring the lock, wherein the first timestamp value represents a start timestamp of a first database transaction;

before writing the data to the plurality of database rows,

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

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

uses the second timestamp value to read a third timestamp value from the table, wherein the second timestamp value was written to the particular database row by a second transaction, wherein the second timestamp value represents a start timestamp of the second transaction, wherein the third timestamp value represents a commit timestamp of the second transaction;

compares the third timestamp value with the first timestamp value to determine whether there is a write-write conflict between the first transaction and the second transaction; and

writes the data to the plurality of database rows after determining that there is not a write-write conflict between the first transaction and the second transaction.

20. The system of claim 19, wherein the comparing indicates that the second transaction committed before the first transaction started.