Dolt is the world’s first and only version-controlled Online Transaction Processing (OLTP) database. OLTP databases support Multi-Version Concurrency Control (MVCC), also known as transactions. Dolt supports standard SQL transaction semantics.

But Dolt also has an additional layer of concurrency control. Dolt commits, branches, and merges have special concurrency concerns. This article explains.

Transactions#

If multiple clients are connected to the same branch, Dolt handles concurrency via standard SQL transactions.

In a standard transactional database workflow, multiple clients are connected to the database server each with its own session. These clients desire to make concurrent reads and writes to the same set of rows in tables. To facilitate concurrent access, SQL provides the following SQL to control the flow:

1. BEGIN TRANSACTION
2. COMMIT
3. ROLLBACK

In the simplest scenario, each individual SQL statement is wrapped by BEGIN TRANSACTION and COMMIT. If the COMMIT statement encounters a conflict an implicit ROLLBACK is issued. This simple scenario is implemented by the AUTOCOMMIT setting. AUTOCOMMIT is now the default setting of most database clients, except notably, Python. Thus, most developers these days never worry about starting and committing transactions.

If you have multiple SQL statements that must execute together you can wrap them in a transaction to make sure they all succeed or all fail. Take the case of a simple money transfer.

BEGIN TRANSACTION;

-- Deduct $150 from Account A
UPDATE Accounts
SET Balance = Balance - 150
WHERE AccountID = 'A';

-- Add $150 to Account B
UPDATE Accounts
SET Balance = Balance + 150
WHERE AccountID = 'B';

-- Commit the transaction if both operations succeed
COMMIT;

For the purposes of concurrency, a client’s view of the database is locked when the BEGIN TRANSACTION statement is issued and unlocked when the COMMIT or ROLLBACK statement is issued. Other clients may be modifying the database concurrently, but the transactions view is consistent. If updates are being made inside a transaction, the database is responsible for detecting conflicting writes and handling them appropriately on COMMIT. The database is also responsible for stitching together non-conflicting concurrent writes on COMMIT.

Dolt handles conflict detection and resolution slightly differently than other database engines. When a COMMIT is issued, Dolt performs a three-way Dolt merge on the transaction against the head of the branch. This means if multiple clients updated different cells in the database concurrently, the merge succeeds. If multiple clients updated the same cell to the same value, the merge succeeds. If multiple clients updated the same cell to different values, a conflict is detected and the transaction is rolled back. This makes Dolt’s transaction isolation level repeatable read and thus, Dolt is susceptible to the lost update problem. Other databases usually fail or serialize concurrent writes to the same row. Dolt’s merge approach can produce some unexpected results.

Dolt Commit Graph#

Dolt has an additional layer of concurrency control beyond transactions. Dolt’s version control functionality is implemented as a Git-style commit graph. Write operations to Dolt’s commit graph are single threaded. Each write to Dolt’s commit graph takes a global lock, performs the write, and releases the lock when the write succeeds or fails. Writes to the commit graph include Dolt commits, branch creation, branch deletion, merges, rebases, cherry-picks, reverts, and resets.

Dolt’s version control operations are designed to be lightweight and fast. In testing, we see hundreds of Dolt commit graph operations per second in normal operation. For heavy operations like Dolt merge, the merge work is performed outside of the commit graph write. Only when the merge work is complete is the commit graph written to.

A common Dolt version control concurrency pattern we see is a user wanting each client to Dolt commit its own writes. To achieve this with a number of concurrent writers, each client must make writes in a SQL transaction and finish each transaction with a Dolt commit. Without transactions, each client will jointly modify the branch’s working set and a Dolt commit will commit all changes in the working set, effectively committing other client’s concurrent changes.

BEGIN TRANSACTION;

-- Deduct $150 from Account A
UPDATE Accounts
SET Balance = Balance - 150
WHERE AccountID = 'A';

-- Add $150 to Account B
UPDATE Accounts
SET Balance = Balance + 150
WHERE AccountID = 'B';

-- Dolt Commit if both operations succeed
-- Dolt Commit implicitly call transaction COMMIT
CALL DOLT_COMMIT('-Am', 'Transferred Money');

Another option to manage clients Dolt committing their own writes is to create a branch for each client.

Dolt Branches#

Branches have additional concurrency implications because each branch operates as a separate bucket of transaction concurrency. In other words, each branch can have multiple clients connected to it synchronizing work via transactions. Concurrency between branches is managed via commit graph writes. Thus, each individual branch acts as an additional layer of transaction concurrency, allowing more isolated writes for a set of clients.

We have a long-standing optimization to make the global commit graph lock a branch specific lock, allowing commit graph write concurrency per branch. In practice, no user has ever reported overwhelming the commit graph write lock with concurrent writes.

Conclusion#

To summarize, Dolt handles concurrency to individual branches via standard SQL transactions and has an additional layer of concurrency management to deal with version control functionality. Version control operations are serialized through a single global lock. Version control operations are lightweight and fast, allowing Dolt to scale. Branches act as an additional bucket of transaction concurrency.

More questions? Come by our Discord and just ask.