XB exposes an ordered key/value API similar to an :ordered_set ETS table, with put(), delete(), get(), and scan() operations. See Usage below for details.

Installation #

You are free to vendor XB by copying xb.ex directly into your project. Alternatively, you can add this repository as a git depdency in your project's mix.exs. A Hex package will be released eventually.

Usage #

Basics #

# Open a database
xb = XB.open(path: "database.xb")

# Writes are buffered in-memory until commit
XB.put(xb, "foo", "bar")
# Keys and values can be arbitrary Elixir terms
XB.put(xb, :hello, :world)

# Reads will observe buffered (uncommitted) writes
XB.get(xb, "foo") # => "bar"
XB.get(xb, :unknown) # => nil
# Use fetch/2 if you want to know whether a key exists
XB.fetch(xb, :unknown) # => :error

# Commit atomically persists buffered writes to disk
XB.commit(xb)

# Close releases in-memory state and closes the file
XB.close(xb)

Range scans #

xb = XB.open(path: "database.xb")

for i <- 1..1_000 do
  XB.put(xb, i, i * 10)
end

# Scans the database from a start key (inclusive) to an end key (exclusive)
XB.scan(xb, 10, 13) # => [{10, 100}, {11, 110}, {12, 120}]

# Set a limit to stop the scan early
XB.scan(xb, 10, 1001, limit: 1) # => [{10, 100}]

# Scans can be performed in reverse, which is useful with a limit
XB.scan(xb, 10, 1001, limit: 1, reverse: true) # => [{999, 9990}]

# The atom :"$end_of_table" can be used as a sentinel on both sides
XB.scan(xb, :"$end_of_table", :"$end_of_table") # => [{1, 10}, {2, 20}, ..., {1000, 10000}]

Backups #

Physical backups #

It's safe to physically copy the database file as long as you do not commit concurrently with the copy. You can still safely perform reads and writes (which are buffered until commit) during the copy.

xb = XB.open(path: "database.xb")

# Back the database up asynchronously
task = Task.async(fn ->
  File.copy!("database.xb", "backup.xb")
end)

# It's safe to perform reads and writes during the backup
for i <- 1..1000 do
  j = XB.get(xb, i, 1) * 2
  XB.put(xb, i, j)
end

# ...but we MUST wait for the copy to finish before calling commit()
Task.await(task)
XB.commit(xb)

Logical backups #

The database's keyspace can be dumped with a simple range scan.

xb = XB.open(path: "database.xb")

pairs = XB.scan(xb, :"$end_of_table", :"$end_of_table")
File.write!("database.backup", :erlang.term_to_binary(pairs))

However, if the database is large this could lead to memory exhaustion. To keep memory usage bounded, you can dump the keyspace in chunks using XB.scan_chunked/5.

Note: you should never peform writes while enumerating the scan_chunked/5 generator, as you will not observe a consistent snapshot.

xb = XB.open(path: "database.xb")

XB.scan_chunked(xb, :"$end_of_table", :"$end_of_table", 100)
|> Stream.with_index()
|> Enum.each(fn {chunk, i} ->
  File.write!("chunk_#{i}.backup", :erlang.term_to_binary(chunk))
end)

Compaction #

Btrees naturally fragment over time. XB keeps a list of free pages and won't grow unbounded, but after a while parts of the keyspace may become sparse, particularly if your workload contains a lot of random deletes.

To perform compaction, simply read the pairs from the old database and write them to a new one.

xb_old = XB.open(path: "database.xb")
xb_new = XB.open(path: "compacted.xb")

XB.scan_chunked(xb_old, :"$end_of_table", :"$end_of_table", 100)
|> Enum.each(fn chunk ->
  Enum.each(chunk, fn {key, value} ->
    XB.put(xb_new, key, value)
  end)

  # Commit each chunk to avoid buffering too many writes in-memory
  XB.commit(xb_new)
end)

XB.close(xb_old)
XB.close(xb_new)

Safety #

XB is resilient to disk corruption. All on-disk data and metadata are strongly checksummed, and page checksums are stored out-of-place to protect against misdirected reads and writes.

Put simply:

XB will not return corrupted data; that is, data which was never written to the database
XB will not lose writes, except in the unlikely event of a corrupted or misdirected superblock, in which case the database may revert to a previous state

These guarantees are stronger than those provided by most databases.

Note: XB will raise if it encounters a corrupted page. Recovery is left to the operator; for important data, backups are recommended.

Design #

XB is a copy-on-write (CoW) B+ tree. Keys and values are written into leaf pages on disk, which are in turn are pointed to by branch pages, forming a tree structure. Leaves and branches are split if they exceed the page size. Values too large to fit comfortably in a leaf page are split into a number of overflow pages, and pointers to those pages are written into the leaf.

On-disk, the database consists of two superblocks followed by an arbitrary number of pages. New pages are allocated as needed (by extending the file), and outdated pages are added to a free list to be reused after the next commit. To commit, one of the superblocks (alternating with each commit) is updated with a pointer to the new root of the tree. If the superblock update were to tear (e.g. due to a crash), its checksum would be invalid, and XB would automatically load the other (previous) superblock at startup. This alternating design is inspired by LMDB.

The free list is written as a linked list of pages (with each page pointing to the last), and the tail of this list is recorded in the superblock. Outdated pages from the commit cycle are only freed after commit, ensuring they can't be overwritten before the new tree is fully persisted. At the time of commit, both the old and new trees exist fully on-disk. The superblock update is atomic, so the commit itself is atomic.

Because Elixir is a language with immutable values, rewriting a page in-place is very expensive, as the entire page must be copied (in-memory) for every mutation. To avoid this, XB buffers all writes into an in-memory tree (an :ets table) and merges them with the on-disk btree during reads. During commits, the in-memory tree is merged into the btree on disk; because we know ahead of time how many writes will fall in a given page, each page only has to be rewritten once. This design is remarkably similar to the "two component" tree from the original LSM Tree paper, though modern LSMs are usually more complex.

All pages (branch, leaf, and overflow) are strongly checksummed, and checksums are stored out-of-place (with the pointers, not the data) to protect against misdirected reads and writes. For example, the checksum for a leaf page is stored in the branch that points to it, and so on. Superblock checksums, however, are stored within the superblocks themselves.

Format #

The database consists of two superblocks followed by an arbitrary number of pages. The page size is configurable (and stored in the superblocks, under opts), but the superblock size is fixed as they must be read and validated before any configuration can be loaded.

Pages are never modified in-place after being written; they are always copied. Superblocks are modified in-place, but only one (alternating) is updated during each commit cycle.

Superblocks #

magic    (8 bytes)
version  (8 bytes)
copy     (8 bytes)
sequence (8 bytes)
max_page (8 bytes)
height   (8 bytes)

free_list_index    (8 bytes)
free_list_checksum (16 bytes)

root_index    (8 bytes)
root_checksum (16 bytes)

opts_size (8 bytes)

opts (repeating, opts_size bytes):
- id    (8 bytes)
- value (8 bytes)

...padding...

superblock_checksum (16 bytes)

magic is always the string CORPXBTR
version is currently 0
copy identifies the superblock and is always 0 or 1
sequence increases monotonically with each commit; the first superblock's sequence is always even, and the second always odd
max_page stores the largest allocated page index (inclusive), used by the free list to allocate new pages
height is the height of the b+ tree on disk, starting at 0 if the tree consists of a single leaf
free_list_index and free_list_checksum point to the tail page of the free list
root_index and root_checksum point to the root page of the b+ tree
opts_size is the byte size of the following opts section
for each opt, id is the id (see the Opts module) and value is the signed integer value

Free list #

Free list pages store a snapshot of the free list at the time of commit. They form a linked list of pages on disk, with each page containing a pointer to the last. To load the free list at startup, this linked list is traversed from the tail page. The pointer in the head page is the null address (all zeros).

entries (repeating, entries_size bytes):
- page_index (8 bytes)

entries_size (8 bytes)

prev_page_index    (8 bytes)
prev_page_checksum (16 bytes)

for each entry, page_index is the index of the free page
entries_size is the byte size of the preceding entries array (in case it does not fill the page)
prev_page_index and prev_page_checksum point to the previous free list page, or the null address (all zeros) if this page is the head

Branch #

Branch pages store pointers to child pages: other branches or, at the bottom of the tree, leaves. Keys separate pointers, so the key at any index is implied to be the end bound of the pointer at that index. The last pointer does not need an end bound because its bound is implied by the parent branch, and so on, up to the root of the tree.

If a branch has only one pointer it will have no keys. A branch cannot have zero pointers (such a branch would be pruned from the tree).

keys (repeating, (pointer_count - 1) times):
- key_size (4 bytes)
- key      (key_size bytes)

...padding...

pointers (repeating, pointer_count times):
- page_index    (8 bytes)
- page_checksum (16 bytes)

key_offsets (repeating, (pointer_count - 1) times):
- offset (4 bytes)

pointer_count (4 bytes)

for each key, key_size is the size of the following key and key is the key data
for each pointer, page_index and page_checksum point to the child page
for each key offset, offset is the byte offset of that key within the page
pointer_count is the number of pointers; there is always at least one pointer, and there is always one fewer key than there are pointers

Leaf #

Leaf pages store the database's key/value pairs. If a value is too large to store directly within the page, it's split across a number of overflow pages; the value within the leaf then points to those pages.

pairs (repeating, pair_count times):
- key_size    (4 bytes)
- large_value (1 bit)
- value_size  (31 bits)
- key         (key_size bytes)
- value       (value_size bytes)

...padding...

pair_offsets (repeating, pair_count times):
- offset (4 bytes)

pair_count (4 bytes)

for each pair:
- key_size is the byte size of the key
- large_value is 0 if the value is stored inline, or 1 if the inline value consists of pointers to overflow pages
- value_size is the byte size of the inline value (which may consist only of pointers)
- key is the key data
- value is the value data (which may consist only of pointers)

Large value metadata (inline) #

When a value is too large to fit comfortably in a page, it gets split across a number of overflow pages. An inline value, consisting of metadata and pointers, is stored in its place within the page. The overflow pages themselves contain no metadata.

checksum   (16 bytes)
value_size (8 bytes)

pointers (repeating):
- page_index (8 bytes)

checksum is the checksum of the real value, which is split across overflow pages
value_size is the byte size of the real value
for each pointer, page_index is the index of the overflow page

Clone this repository

XB #