Standard library · Databases
db/kv
Imported as import "db/kv" as kv, its names are then kv.…. Every signature below is the one the checker infers.
A key–value store on disk: a B+ tree of 4 KB pages, a page cache, and a write-ahead log — the shape SQLite's file layer has, in Rill, for one process at a time.
Keys and values are byte strings; a key is at most 255 bytes and a value at most 1500, so that a page always holds three cells. Keys sort as bytes.
What is where. path is the tree: page 0 is the header, every other page a node, leaves chained left to right for range scans. Nothing is written to it except at a checkpoint. path.wal is the log: every page a transaction changed, whole, with a checksum, and a marker after the last one. A commit is those frames and one sync of the log. A checkpoint copies the logged pages into the tree, syncs it, and empties the log — after so many frames, and when the store closes. Opening a store replays what the log holds up to its last marker, so a crash between any two writes loses at most the transaction that was not committed, and never a page.
The cache is 2048 slots of one page (8 MB), found through a map from page number to slot and replaced by the clock rule: a slot is passed over once for every hit it has had since the hand last came by, so the root and the inner nodes, touched on every operation, are never the ones to go. A dirty page that is evicted is written to the log first (an uncommitted frame, which the marker at commit makes good, and which a crash before then leaves ignored). Two maps say where the latest copy of a page is — in the log since the last checkpoint, or in the log for the transaction under way — and a read goes there before it goes to the tree.
What it does not do: merge nodes that empty on delete (a leaf may sit at one key, or none), reuse freed pages, or let two processes in. The exclusive lock at open is what says so.
Every page lives in the cache buffer at base = slot * 4096, and every function below that reads or writes a node takes that base. A base is good until the next page call — which may evict what it points at — so a step that touches two pages reads what it needs of the first into a buffer of its own before it asks for the second.
import "db/kv" file_remove("/tmp/rill-doc-things.db") file_remove("/tmp/rill-doc-things.db.wal") db = kv_open("/tmp/rill-doc-things.db")? kv_put(db, "ada", "36") # => true kv_get(db, "ada") # => Some(36) kv_commit(db) # durable: in the log, synced kv_put(db, "bob", "41") kv_range(db, "a", "b") # => Cons((ada, 36), Nil) kv_range(db, "a", "") # => Cons((ada, 36), Cons((bob, 41), Nil)) kv_delete(db, "ada") # => true kv_count(db) # => 1 kv_close(db) # commits, checkpoints, unlocks
Types
Db
Db(fd: Int, wal: Int, path: Str, cache: Buf(U8), slot_pg: Buf(Int), slot_dirty: Buf(Int), slot_ref: Buf(Int), slot_map: Map(Int, Int), meta: Buf(Int), committed: Map(Int, Int), pending: Map(Int, Int), frame: Buf(U8), path_buf: Buf(Int))
Functions
fn kv_open(path: Str) -> Result(Db, Str)
import "db/kv" file_remove("/tmp/rill-doc-open.db") file_remove("/tmp/rill-doc-open.db.wal") db = kv_open("/tmp/rill-doc-open.db")? kv_count(db) # => 0 kv_close(db) res_map(kv_open("/no/such/dir/x.db"), \d -> 0) # => Err(cannot open /no/such/dir/x.db)
fn kv_commit(db: Db) -> Int
import "db/kv" file_remove("/tmp/rill-doc-commit.db") file_remove("/tmp/rill-doc-commit.db.wal") db = kv_open("/tmp/rill-doc-commit.db")? kv_put(db, "k", "v") kv_commit(db) kv_close(db) again = kv_open("/tmp/rill-doc-commit.db")? kv_get(again, "k") # => Some(v) kv_close(again)
fn kv_rollback(db: Db) -> Unit
Forget the transaction: dirty pages are dropped from the cache, and the log is cut back to where the transaction found it, so that the frames it spilled cannot ride in on the next marker.
import "db/kv" file_remove("/tmp/rill-doc-rollback.db") file_remove("/tmp/rill-doc-rollback.db.wal") db = kv_open("/tmp/rill-doc-rollback.db")? kv_put(db, "kept", "1") kv_commit(db) kv_put(db, "dropped", "2") kv_rollback(db) kv_get(db, "dropped") # => None kv_get(db, "kept") # => Some(1) kv_close(db)
fn kv_close(db: Db) -> Unit
import "db/kv" file_remove("/tmp/rill-doc-close.db") file_remove("/tmp/rill-doc-close.db.wal") db = kv_open("/tmp/rill-doc-close.db")? kv_put(db, "k", "v") kv_close(db) # what was put is committed kv_get(kv_open("/tmp/rill-doc-close.db")?, "k") # => Some(v)
fn kv_get(db: Db, k: Str) -> Option(Str)
import "db/kv" file_remove("/tmp/rill-doc-get.db") file_remove("/tmp/rill-doc-get.db.wal") db = kv_open("/tmp/rill-doc-get.db")? kv_put(db, "k", "v") kv_get(db, "k") # => Some(v) kv_get(db, "z") # => None kv_close(db)
fn kv_delete(db: Db, k: Str) -> Bool
import "db/kv" file_remove("/tmp/rill-doc-del.db") file_remove("/tmp/rill-doc-del.db.wal") db = kv_open("/tmp/rill-doc-del.db")? kv_put(db, "k", "v") kv_delete(db, "k") # => true kv_delete(db, "k") # => false kv_close(db)
fn kv_put(db: Db, k: Str, v: Str) -> Bool
import "db/kv" file_remove("/tmp/rill-doc-put.db") file_remove("/tmp/rill-doc-put.db.wal") db = kv_open("/tmp/rill-doc-put.db")? kv_put(db, "k", "one") # => true kv_put(db, "k", "two") # => true kv_get(db, "k") # => Some(two) kv_close(db)
fn kv_range(db: Db, lo: Str, hi: Str) -> List((Str, Str))
Every (key, value) with lo <= key <= hi, in key order; an empty hi means to the end.
import "db/kv" file_remove("/tmp/rill-doc-range.db") file_remove("/tmp/rill-doc-range.db.wal") db = kv_open("/tmp/rill-doc-range.db")? kv_put(db, "b", "2") kv_put(db, "a", "1") kv_put(db, "c", "3") kv_range(db, "a", "b") # => Cons((a, 1), Cons((b, 2), Nil)) kv_range(db, "b", "") # => Cons((b, 2), Cons((c, 3), Nil)) kv_close(db)
fn kv_fold(db: Db, lo: Str, hi: Str, acc: 'a, f: ('a, Str, Str) -> 'a) -> 'a
import "db/kv" file_remove("/tmp/rill-doc-fold.db") file_remove("/tmp/rill-doc-fold.db.wal") db = kv_open("/tmp/rill-doc-fold.db")? kv_put(db, "a", "1") kv_put(db, "b", "2") kv_fold(db, "", "", 0, \acc, k, v -> acc + str_to_int(v)) # => 3 kv_close(db)
fn kv_count(db: Db) -> Int
import "db/kv" file_remove("/tmp/rill-doc-count.db") file_remove("/tmp/rill-doc-count.db.wal") db = kv_open("/tmp/rill-doc-count.db")? kv_put(db, "a", "1") kv_put(db, "b", "2") kv_count(db) # => 2 kv_close(db)