🬟 🬑 🬂🬰🬂 🬂🬰🬂 🬒🬂🬟 🬒🬂🬟 ╭──────────╮ 🬋 🬋 🬋 🬃 🬇 🬋🬋🬃 zig java clojure │typescript│ go 🬑 🬟 🬭🬰🬭 🬰 🬮🬭🬑 🬮🬭🬑 ╰──────────╯ See xit-vcs/xitdb-ts on GitHub 🬳🬶 🬕🬧 🬳🬶 🬨🬕 🬳🬶 🬴🬗 🬳🬶 🬤🬒 🬴🬒 🬴🬒 🬴🬗 🬔🬧 🬺🬻 🬨🬕 🬲🬷 🬴🬒 🬴🬒 ▌▐ 🬨🬕 ▌▐ 🬴🬗 🬴🬒 🬞🬏 🬴🬗 🬳🬶 🬤🬒 🬨🬕 ▌▐ 🬲🬘 ▌▐ ▐▌ ▌▐ 🬲🬘 ▌▐ 🬱🬘 🬲🬭 ▌ 🬕🬢 🬣🬘 ▌▐ ▐▌ ▌▐ 🬲🬭 ▌ 🬣🬘 ▐▌ 🬣🬘 🬕🬢 🬲🬭 🬁🬀 ▌ ▌▐ 🬱🬘 ▐▌ xitdb is a database that... • Is embedded, like SQLite • Single file database • Runs as a library • Exposes data structures rather than a query language • SQL and other query languages are too high level • "Build your own database" with data structures instead • Is immutable, like Datomic • Lock-free reads • Easy replication • Has dependency-free variants in Zig, Java, TypeScript, and Go • Also a slick Clojure wrapper • Each is only 4-5k lines of code 🬤🬒 🬳🬶 🬣🬘 🬺▐ 🬔🬧 🬨🬕 🬔🬧 🬔🬧 ▌▐ 🬴🬒 🬴🬗 🬣🬘 ▌ 🬳🬶 🬺▐ 🬔🬰 ▌▐ 🬳🬶 🬔🬰 🬴🬒 🬤🬒 🬱🬘 ▌▐ ▐▌ ▌🬬 🬣🬘 ▐▌ 🬣🬘 🬈🬥 🬣🬘 🬲🬭 🬕🬢 ▐▌ 🬲🬭 ▌▐ ▌🬬 🬣🬷 🬣🬘 ▌▐ 🬣🬷 🬲🬭 🬱🬘 Pop quiz: is this query doing a full table scan? ╭────────────────────────╮ │SELECT * │ │FROM orders │ │WHERE customer_id = 42 │ │ AND status = 'shipped'│ │ORDER BY created_at DESC│ │LIMIT 10; │ ╰────────────────────────╯ It's impossible to tell without asking the query planner! In SQLite, that would be EXPLAIN QUERY PLAN SELECT. SQL is a high-level language, and the efficiency of a query can suddenly change without you noticing. 🬕🬧 🬳🬶 🬨🬕 🬳🬶 🬤🬒 🬨🬕 🬴🬗 ▌▐ 🬔🬂 🬨🬕 ▌▐ 🬴🬗 🬴🬒 🬤🬒 🬳🬶 🬴🬗 🬴🬒 🬳🬶 ▌ ▌ 🬣🬘 🬔🬧 ▌▐ 🬺▐ 🬴🬒 🬴🬒 🬕🬧 🬲🬘 ▌▐ ▐▌ ▌▐ 🬱🬘 ▐▌ 🬕🬢 🬣🬘 🬣🬭 ▐▌ 🬣🬘 🬕🬢 🬲🬭 🬱🬘 ▌▐ 🬕🬢 🬲🬭 ▌▐ 🬲🬭 🬲🬭 ▐▌ 🬣🬘 🬣🬘 ▌🬬 🬲🬭 🬲🬭 🬲🬘 ╭─────────────────────────────────────────────────────────────────────────────╮ │const orders = new ReadHashMap(moment.getCursor('orders')!); │ │const index = new ReadHashMap(moment.getCursor('customer->status->orders')!);│ │const statuses = new ReadHashMap(index.getCursor('42')!); │ │const shipped = new ReadSortedMap(statuses.getCursor('shipped')!); │ │ │ │const iter = shipped.iterator(); │ │for (let i = 0; i < 10 && iter.hasNext(); i++) { │ │ const kv = iter.next()!.readKeyValuePair(); │ │ const orderId = new TextDecoder() │ │ .decode(kv.valueCursor.readBytes(MAX_READ_BYTES)); │ │ const order = new ReadHashMap(orders.getCursor(orderId)!); │ │ // do something with the order │ │} │ ╰─────────────────────────────────────────────────────────────────────────────╯ I can tell it's efficient just by reading the code! 🬨🬕 🬺🬻 🬴🬗 🬴🬒 🬕🬧 🬳🬶 🬺▐ 🬔🬂 🬴🬒 🬺🬻 🬨🬕 🬤🬒 🬺🬻 🬳🬶 🬨🬕 🬔🬂 🬲🬷 🬷🬲 ▌▐ ▌ 🬲🬭 🬲🬘 ▌▐ ▌🬬 🬣🬭 🬲🬭 ▌▐ 🬷🬲 🬱🬘 ▌▐ ▌▐ ▐▌ 🬣🬭 ▌▐ SQL returns flat rows, so you write glue code to rebuild your data: ╭──────────────────────────────────────────────────────╮ │const rows = db.prepare(` │ │ SELECT users.name, tags.tag │ │ FROM users LEFT JOIN tags ON tags.user_id = users.id│ │ WHERE users.id = 1 │ │`).all() as { name: string; tag: string | null }[]; │ │ │ │let name: string | null = null; │ │const tags: string[] = []; │ │for (const row of rows) { │ │ name = row.name; │ │ if (row.tag !== null) tags.push(row.tag); │ │} │ ╰──────────────────────────────────────────────────────╯ xitdb stores your data in the shape you already use: ╭────────────────────────────────────────────────────────╮ │const user = new ReadHashMap(users.getCursor('1')!); │ │const tags = new ReadArrayList(user.getCursor('tags')!);│ ╰────────────────────────────────────────────────────────╯ 🬣🬘 🬨🬕 🬨🬕 🬕🬧 🬴🬗 🬁🬄 🬤🬒 🬕🬧 🬳🬶 🬨🬕 🬳🬶 🬤🬒 🬨🬕 🬴🬗 ▌▐ 🬔🬂 🬨🬕 ▌▐ 🬴🬗 🬴🬒 🬤🬒 🬔🬧 🬷🬲 ▐▌ 🬲🬘 🬲🬘 🬱🬘 🬲🬘 ▌▐ ▐▌ ▌▐ 🬱🬘 ▐▌ 🬕🬢 🬣🬘 🬣🬭 ▐▌ 🬣🬘 🬕🬢 🬲🬭 🬱🬘 Array mapped trie • ArrayList is a growable array • HashMap contains key-value pairs stored with a hash • HashSet contains unique values stored with a hash B+tree • LinkedArrayList is a growable array that can be efficiently sliced and concatenated • SortedMap contains key-value pairs whose keys are byte arrays kept in lexicographic order • SortedSet contains byte arrays kept in lexicographic order 🬺▐ 🬴🬒 🬤🬒 🬨🬕 🬳🬶 ▌ ▌ 🬣🬘 🬔🬧 ▌▐ ▌▐ 🬳🬶 🬺▐ 🬨🬕 ▌🬬 🬲🬭 🬱🬘 ▐▌ ▌▐ 🬲🬭 🬲🬭 ▐▌ 🬣🬘 🬣🬘 🬬🬝 ▌▐ ▌🬬 ▐▌ ╭───────────────────────────────────────────────────────╮ │[{"users": {"alice": "Alice Jones", "bob": "Bob Lee"}}]│ ╰───────────────────────────────────────────────────────╯ In xitdb you can nest data like in the JSON above easily: ╭────────────────────────────────────────────────────────────╮ │// get the top-level list │ │const history = new ReadArrayList(db.rootCursor()); │ │ │ │// get the hash-map inside of it │ │const moment = new ReadHashMap(history.getCursor(-1)!); │ │ │ │// get the "users" sorted map inside of that │ │const users = new ReadSortedMap(moment.getCursor('users')!);│ │ │ │// get "bob" │ │const bobCursor = users.getCursor('bob'); │ ╰────────────────────────────────────────────────────────────╯ It's just like how you'd do it using in-memory data structures! 🬴🬗 ▌▐ 🬨🬕 ▌ 🬕🬧 🬣🬘 🬔🬧 ▌▐ 🬴🬗 🬔🬧 ▌▐ 🬺▐ 🬕🬧 🬳🬶 🬨🬕 🬳🬶 🬴🬗 🬳🬶 🬤🬒 🬴🬒 🬲🬘 🬣🬘 🬷🬲 🬲🬭 🬲🬘 ▐▌ 🬣🬘 🬣🬘 🬕🬢 🬣🬘 🬬🬝 ▌🬬 🬲🬘 ▌▐ ▐▌ ▌▐ 🬲🬘 ▌▐ 🬱🬘 🬲🬭 ╭──────────────────────────────────────────────────────────────────────────╮ │CREATE TABLE users (id INTEGER PRIMARY KEY, username TEXT, name TEXT); │ │CREATE INDEX users_username ON users (username); │ │ │ │INSERT INTO users (id, username, name) VALUES (1, 'alice', 'Alice Jones');│ ╰──────────────────────────────────────────────────────────────────────────╯ In xitdb, an index is just another map: ╭───────────────────────────────────────────────────────────────────────────╮ │const users = new WriteHashMap(moment.putCursor('users')); │ │const usernameIndex = new WriteSortedMap(moment.putCursor('username->id'));│ │ │ │const alice = new WriteHashMap(users.putCursor('1')); │ │alice.put('username', new Bytes('alice')); │ │alice.put('name', new Bytes('Alice Jones')); │ │usernameIndex.put('alice', new Bytes('1')); │ ╰───────────────────────────────────────────────────────────────────────────╯ With these data structures you can "build" your own database. 🬤🬒 🬴🬒 🬳🬶 🬴🬗 🬔🬂 🬲🬷 🬱🬘 🬲🬭 ▌▐ 🬕🬢 🬣🬭 ▌▐ Another nice built-in feature of SQLite is search: ╭─────────────────────────────────────────────────────────────────────╮ │CREATE VIRTUAL TABLE posts USING fts5(title, body); │ │INSERT INTO posts (title, body) │ │ VALUES ('hello world', 'xitdb is a database from the future-past');│ │SELECT title FROM posts WHERE posts MATCH 'database'; │ ╰─────────────────────────────────────────────────────────────────────╯ In xitdb you need to manually set it up: Build an "inverted index": a SortedMap from each word to a SortedSet of the posts containing it. ╭────────────────────────────────────────────────────────╮ │{"database": [1, 7], "future": [1], "past": [1, 3], ...}│ ╰────────────────────────────────────────────────────────╯ • One word: a single lookup in the SortedMap returns every matching post • Prefixes: the words are sorted, so seek to "data" and walk forward while words still start with it • Multiple words: walk each word's SortedSet in step, seeking past posts the others don't have • Updates: when a post changes, only add or remove the words that changed • Build your own: haxy implements all of this in about 230 lines of Zig 🬨🬕 🬨🬕 🬁🬄 🬤🬒 🬳🬶 ▌ ▌ 🬨🬕 🬺▐ 🬔🬂 🬴🬗 🬴🬒 🬺🬻 🬴🬒 🬺▐ 🬨🬕 🬳🬶 ▌ 🬷🬲 ▐▌ 🬱🬘 ▌▐ 🬲🬭 🬲🬭 🬷🬲 ▌🬬 🬣🬭 🬕🬢 🬲🬭 ▌▐ 🬲🬭 ▌🬬 ▐▌ ▌▐ 🬲🬭 This isn't "object serialization". Every language has a way to write objects to disk, but that only works for tiny datasets that fit in memory. A xitdb database can be terabytes in size and still perform well, because all reads and writes are incremental. 🬨🬕 🬨🬕 🬺🬻 🬴🬒 🬨🬕 🬴🬗 🬳🬶 ▌▐ 🬴🬒 ▌ ▐▌ 🬷🬲 ▌▐ 🬲🬭 ▐▌ 🬕🬢 ▌▐ 🬧🬔 🬲🬭 🬲🬭 Revert to any previous state of the database: ╭─────────────────────────────────────────────────────────────────╮ │// the list of all transactions made in the database │ │const history = new WriteArrayList(db.rootCursor()); │ │ │ │// save the current index so we can revert back to it │ │const historyIndex = history.count() - 1; │ │ │ │// ...add some new transactions here │ │ │ │// read the old copy of the db from before the new transactions │ │const moment = new ReadHashMap(history.getCursor(historyIndex)!);│ │ │ │// revert back to the old copy of the db │ │history.append(history.getSlot(historyIndex)!); │ ╰─────────────────────────────────────────────────────────────────╯ ▌ 🬔🬧 🬔🬂 🬲🬅 🬴🬒 🬴🬗 🬴🬒 🬴🬒 🬲🬭 🬣🬘 🬣🬭 🬕🬢 ▌ 🬕🬢 🬲🬭 🬲🬭 Read xitdb from multiple threads without locks: ╭────────────────────────────────────────────────────────────────────────╮ │import { Worker, isMainThread } from 'node:worker_threads'; │ │ │ │if (isMainThread) { │ │ // start reader threads; this thread can keep writing meanwhile │ │ for (let i = 0; i < 4; i++) new Worker(new URL(import.meta.url)); │ │} else { │ │ // each worker thread gets its own Database, which it only reads │ │ const db = new Database(new CoreFile('main.db'), new Hasher('SHA-1'));│ │ │ │ // read from any thread, even while another thread is writing │ │ const history = new ReadArrayList(db.rootCursor()); │ │ const moment = new ReadHashMap(history.getCursor(-1)!); │ │} │ ╰────────────────────────────────────────────────────────────────────────╯ Mutable databases like SQLite must use locks. (Yes, even in WAL mode.) 🬴🬗 🬴🬒 🬴🬗 ▌ 🬨🬕 🬔🬂 🬳🬶 🬨🬕 🬨🬕 🬔🬧 🬺▐ 🬕🬢 🬲🬭 ▌ 🬲🬭 🬷🬲 🬣🬭 ▌▐ ▐▌ 🬷🬲 🬣🬘 ▌🬬 Append-only databases are trivial to replicate: ╭───────────────────────────────────────────────────────╮ │// on the replica: describe what it already has │ │const state = replica.replicaState(); │ │ │ │// on the source: decide which bytes to send │ │const start = source.replicationStart(state); │ │const end = source.committedSize(); │ │ │ │// copy the new bytes from the source to the replica │ │const out = replica.openReplicated(start, end - start);│ │source.readCommitted(start, end, out); │ │out.close(); // commits the bytes │ ╰───────────────────────────────────────────────────────╯ SQLite requires complicated external tools like LiteStream (20k+ LOC) 🬴🬗 🬔🬧 ▌ 🬣🬘 🬔🬰 ▌ 🬔🬧 🬨🬕 ▌ 🬣🬘 🬲🬭 ▐▌ 🬣🬷 🬲🬭 🬣🬘 ▐▌ There are 4 dependency-free implementations: • Zig: xit-vcs/xitdb • Java: xit-vcs/xitdb-java • TypeScript: xit-vcs/xitdb-ts • Go: xit-vcs/xitdb-go Each one is 4-5k lines of code, compared to 150k lines in SQLite. Yes, SQLite is more featureful. But the impedance mismatch often leads you to write more code despite the extensive built-in features. And a nice Clojure wrapper around xitdb-java as well: • Clojure: codeboost/xitdb-clj