Dolt: Git for Data | Yinzuo Jiang

Concepts

Dolt is a SQL database you can fork, clone, branch, merge, push and pull just like a Git repository.¹

a version controlled database.
- SQL
- system tables, functions, procedures…
Git for Data.
- dolt add
- dolt commit
- DoltHub, a place to share Dolt databases. Host public data for free!
- …
a Versioned MySQL Replica.
- MySQL compatible, deployed as a Versioned MySQL Replica.

Why Dolt (Git + SQL + RDBMS)? ²

Git-style Distributed Version Control: collaborate on open source software -> collaborate on data.
SQL: worldwide standard for data description and querying.

Share the same view of the data
Do not copy -> only one write could happen at a time.
Make a copy -> no tractable way to compare & merge the two copies.

DoltHub: copy a database, make changes, compare the database copies, and merge the changes.

Use case

roll back the change when someone made a mistake
clone the production data for debugging
open your data up to the world

Dolt’s Axioms

Git versions files. Dolt versions table schema and table data.
Dolt will copy the Git command line exactly.
Dolt will be MySQL compatible.
Git features in SQL will extend MySQL SQL. Write operations will be procedures. Read operations will be system tables.

Git

commmits
diff
branch
merge
conflicts
remotes
working set

see Git Comparison.

Commit³

Commit: save the state of the current database permanently for future reference.

Commit stores the root hash (or reference) of the database. A graph of all the commits

A merge commit will have multiple parents.

How to Use Commits

Dolt uses commits as the basis of comparison between two versions of a database.

Show me the differences between these two commits
Give me the common ancestor of these two commits
Make my current database look like this commit
Show me the difference between my current database and the last commit
Show me all the commits since this database was created
Show me who created this commit and the message they left when he or she made it

Example

CLI

docs $ dolt sql -q "create table docs (pk int, primary key(pk))"
docs $ dolt add .
docs $ dolt status
On branch main
Changes to be committed:
  (use "dolt reset <table>..." to unstage)
	new table:      docs
docs $ dolt commit -m "Added example table docs"
commit 7vureh3qotrr02sog3tjgjk73sqmc2de
Author: Tim Sehn <tim@dolthub.com>
Date:   Mon Dec 06 13:25:55 -0800 2021

	Added example table docs

SQL

docs $ dolt sql -q "create table docs_sql (pk int, primary key(pk))"
docs $ dolt sql -q "call dolt_commit('-a', '-m', 'Added docs_sql example table. Use -a to stage all changes for commit ie. skip dolt add')"
+-------------------------------------------------------------------------------------------------------------------+
| dolt_commit('-a', '-m', 'Added docs_sql example table. Use -a to stage all changes for commit ie. skip dolt add') |
+-------------------------------------------------------------------------------------------------------------------+
| v42og53ru3k3hak3decm23crp5p6kd2f                                                                                  |
+-------------------------------------------------------------------------------------------------------------------+

Architecture

Overview

Dolt leveraged three existing open source packages:

Noms for version controlled storage.
go-mysql-server for our SQL engine.
Vitess for MySQL compatible parsing and serving.

Noms: a data storage engine with Git properties

Prolly tree: A content-addressed B-tree

seek performance characteristics of a B-tree
fast diff

Prolly Trees + Commit Graph = Dolt Storage Engine

Requirements

tables
performance at scale
fast diff
- Displaying diffs to a user is a common operation.
- Merge relies on diffs
structual sharing
- All versions of the data must be stored.
- Data that does not change between versions must share storage.

Prolly Trees

1 table <-> 1 prolly tree

dolt-prolly-trees dolt-prolly-trees-update10

Operation	B-Trees	Prolly Trees
1 Random Read	log_k(n)	log_k(n)
1 Random Write	log_k(n)	(1+k/w)*log_k(n)
Ordered scan of one item with size z	z/k	z/k
Calculate diff of size d	n	d
Structural sharing	❌	✅

n: total leaf data in tree, k: average block size, w: window width

Commit Graph

dolt-schema-data-hashed dolt-database-hashed dolt-commit-graph-head-pointer

And, thus, you end up with Dolt’s storage engine. dolt-commit-graph

commit graph⁴, branches, merge dolt-commit-graph-merge

Prolly Tree⁵

https://www.prollytree.com/

Property 1: History Independence

order-5 B-tree：different insertion orders => different final structures

elements: {10, 20, 30, 40, 50, 60, 70, 80}

Insertion order 1: 10, 20, 30, 40, 50, 60, 70, 80

Final structure:
          [30,60]
        /    |    \
 [10,20] [40,50] [70,80]

Insertion order 2: 50, 40, 60, 30, 70, 20, 80, 10

Final structure:
           [ 50 ]
          /     \
 [10,20,30,40] [60,70,80]

History independence is guaranteed by:

Chunked by hash value
The parent node contains the highest keys of its children.

prolly-tree-order1 prolly-tree-order2

Content-Defined Chunking⁶

Property 2: Fast Diffs

Compare hashes starting from the root node.

Detail 1: Controlling Chunk Size

The Original Noms Chunking Method

Noms splits a key-value byte stream into chunks using a rolling hash.
At each position, it computes a rolling hash of the recent bytes.
If the hash meets a fixed condition (e.g., low $k$ bits are zero), it creates a chunk boundary.
This condition triggers with a constant probability $p$ .
For an average chunk size of 4 KB, $p = 1/4096$ .

The Chunk Size Is Geometric

Each position is an independent Bernoulli trial:
- Success = trigger a boundary
- Probability of success = $p$
Chunk length $L$ = number of bytes until the first success.
Therefore:

  L \sim \text{Geometric}(p)

  P(L = n) = (1-p)^{n-1} p

The expected length is:

  E[L] = \frac{1}{p} = 4096 \text{ bytes}

Consequence: Many Small Chunks

Many chunks are much smaller than 4 KB.
Long tail: A few chunks are very large.
- hurt read performance because binary search within a chunk costs (O(\log n)).

Dolt’s Optimization

Target Distribution

We want the chunk length $L$ to follow a target distribution.

cumulative distribution function (CDF): $\operatorname{CDF}(x) = P(L \le x)$

For example, the target can be a normal distribution centered at 4 KB.

Online Splitting Condition

Suppose the current chunk size is $start$ , and the chunk has not been split yet: $L > start$ .

We append a key-value pair of size $\Delta$ , so the new size is: $end = start + \Delta$ .

Given $L > start$ , the probability that the chunk ends in $(start, end]$ is:

p = P(start < L \le end \mid L > start)
= \frac{P(start < L \le end)}{P(L > start)}
= \frac{\operatorname{CDF}(end) - \operatorname{CDF}(start)}{1 - \operatorname{CDF}(start)}

Dolt uses this probability to decide whether to split at this point.

Detail 2: Two Kinds of hashes in a Prolly Tree

There are at least two kinds of hashes in a Prolly Tree:

Purpose	Computed over	Role
Rolling hash	Keys only	Determines where chunk boundaries are
Content hash / Merkle hash	Key + value	Identifies the chunk and is used for diff

Rolling hash is a hashing technique that supports incremental updates: when a sliding window shifts by one position, it computes the new window’s hash from the old one in O(1) time instead of recomputing the entire window.

Block Store（Content Addressed Store, CAS）

See 内容寻址存储（Content Addressed Store, CAS）

https://www.dolthub.com/docs/introduction/what-is-dolt/ ↩
https://www.dolthub.com/docs/concepts/dolt/ ↩
https://www.dolthub.com/docs/concepts/dolt/git/commits/ ↩
https://www.dolthub.com/docs/architecture/storage-engine/commit-graph/ ↩
https://www.dolthub.com/docs/architecture/storage-engine/prolly-tree/ ↩
从文件到块: 提高 Hugging Face 存储效率 - Hugging Face的文章 - 知乎 https://zhuanlan.zhihu.com/p/27906353824 ↩