TRANSACTION PROTOCOL FOR READING DATABASE VALUES

• US 20150112956A1
• Filed: 12/23/2014
• Published: 04/23/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
• Granted Patent: US 9,619,507 B2
• Time in Patent Office: Days
• US Class Current: 707/703
• 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 the steps of:

obtaining a first timestamp value from a timestamp service;

reading a database value stored in a database table cell;

obtaining a write timestamp value associated with the database value;

using the write timestamp value associated with the database value to read a second timestamp value from a row of a transaction table;

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

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

2. The method of claim 1, wherein the first timestamp value represents a start transaction timestamp of the first transaction.

3. The method of claim 1, wherein the write timestamp value corresponding to the database value represents a start transaction timestamp of the second transaction that wrote the database value to the cell.

4. The method of claim 1, wherein the second timestamp value represents a commit timestamp of the second transaction that wrote the database value to the cell.

5. The method of claim 1, wherein the database value is associated with the write timestamp value in the cell.

6. The method of claim 1, wherein obtaining the write timestamp value associated with the database value includes reading the write timestamp value from the cell.

7. The method of claim 1, further comprising acquiring a lock on the row of the transaction table prior to reading the second timestamp value from the row.

8. The method of claim 7, wherein the lock is a read lock.

9. The method of claim 7, wherein the row is keyed in the database table by the write timestamp value.

10. The method of claim 7, further comprising releasing the lock on the row prior to reading the second timestamp value from the row.

11. The method of claim 1, wherein the cell comprises a plurality of database values one of which is the database value.

12. A system comprising:

one or more processors;

one or more computer-readable media storing instructions which, when executed by the one or more processors, causes performance of the steps of;

obtaining a first timestamp value from a timestamp service;

reading a database value stored in a database table cell;

obtaining a write timestamp value associated with the database value;

using the write timestamp value associated with the database value to read a second timestamp value from a row of a transaction table;

providing the database value to a client application in context of a first transaction in response to determining, based on a comparison between the first timestamp value and the second timestamp value, that a second transaction that wrote the database value to the cell committed before the first transaction started.

13. The system of claim 12, wherein the first timestamp value represents a start transaction timestamp of the first transaction.

14. The system of claim 12, wherein the write timestamp value corresponding to the database value represents a start transaction timestamp of the second transaction that wrote the database value to the cell.

15. The system of claim 12, wherein the second timestamp value represents a commit timestamp of the second transaction that wrote the database value to the cell.

16. The system of claim 12, wherein the database value is associated with the write timestamp value in the cell.

17. The system of claim 12, wherein obtaining the write timestamp value associated with the database value includes reading the write timestamp value from the cell.

18. The system of claim 12, the one or more computer-readable media further comprising instructions which, when executed by the one or more processors, cause performance of the step of acquiring a lock on the row of the transaction table prior to reading the second timestamp value from the row.

19. The system of claim 18, wherein the lock is a read lock.

20. The system of claim 18, wherein the row is keyed in the database table by the write timestamp value.

21. The system of claim 18, the one or more computer-readable media further comprising instructions which, when executed by the one or more processors, cause performance of the step of releasing the lock on the row prior to reading the second timestamp value from the row.

22. The system of claim 12, wherein the cell comprises a plurality of database values one of which is the database value.