MULTI-ROW TRANSACTIONS

• US 20130318060A1
• Filed: 08/05/2013
• Published: 11/28/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,954,410 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 comprising:

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

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

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

adding the row to the database table after successfully validating the lock;

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 adding the row to the table;

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

wherein adding the row to the database table comprises 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 adding the row to the table comprises 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;

writes data to a plurality of database rows after acquiring the lock;

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

adds the row to the database table after successfully validating the lock.

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 adding the row to the table, wherein the second timestamp value represents a commit timestamp of the transaction;

adds the row to the table by at least including 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 adds 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.