🬟 🬑 🬂🬰🬂 🬂🬰🬂 🬒🬂🬟 🬒🬂🬟 ╭────╮ 🬋 🬋 🬋 🬃 🬇 🬋🬋🬃 zig │java│ clojure typescript go 🬑 🬟 🬭🬰🬭 🬰 🬮🬭🬑 🬮🬭🬑 ╰────╯ See xit-vcs/xitdb-java 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. 🬕🬧 🬳🬶 🬨🬕 🬳🬶 🬤🬒 🬨🬕 🬴🬗 ▌▐ 🬔🬂 🬨🬕 ▌▐ 🬴🬗 🬴🬒 🬤🬒 🬳🬶 🬴🬗 🬴🬒 🬳🬶 ▌ ▌ 🬣🬘 🬔🬧 ▌▐ 🬺▐ 🬴🬒 🬴🬒 🬕🬧 🬲🬘 ▌▐ ▐▌ ▌▐ 🬱🬘 ▐▌ 🬕🬢 🬣🬘 🬣🬭 ▐▌ 🬣🬘 🬕🬢 🬲🬭 🬱🬘 ▌▐ 🬕🬢 🬲🬭 ▌▐ 🬲🬭 🬲🬭 ▐▌ 🬣🬘 🬣🬘 ▌🬬 🬲🬭 🬲🬭 🬲🬘 ╭──────────────────────────────────────────────────────────────────────────╮ │var orders = new ReadHashMap(moment.getCursor("orders")); │ │var index = new ReadHashMap(moment.getCursor("customer->status->orders"));│ │var statuses = new ReadHashMap(index.getCursor("42")); │ │var shipped = new ReadSortedMap(statuses.getCursor("shipped")); │ │ │ │var iter = shipped.iterator(); │ │for (int i = 0; i < 10 && iter.hasNext(); i++) { │ │ var kv = iter.next().readKeyValuePair(); │ │ var orderId = new String(kv.valueCursor.readBytes(1024L)); │ │ var 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: ╭────────────────────────────────────────────────────────╮ │var rows = conn.createStatement().executeQuery(""" │ │ SELECT users.name, tags.tag │ │ FROM users LEFT JOIN tags ON tags.user_id = users.id│ │ WHERE users.id = 1 │ │ """); │ │ │ │String name = null; │ │var tags = new ArrayList<String>(); │ │while (rows.next()) { │ │ name = rows.getString("name"); │ │ var tag = rows.getString("tag"); │ │ if (tag != null) tags.add(tag); │ │} │ ╰────────────────────────────────────────────────────────╯ xitdb stores your data in the shape you already use: ╭─────────────────────────────────────────────────────╮ │var user = new ReadHashMap(users.getCursor("1")); │ │var 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 │ │var history = new ReadArrayList(db.rootCursor()); │ │ │ │// get the hash-map inside of it │ │var moment = new ReadHashMap(history.getCursor(-1)); │ │ │ │// get the "users" sorted map inside of that │ │var users = new ReadSortedMap(moment.getCursor("users"));│ │ │ │// get "bob" │ │var 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: ╭─────────────────────────────────────────────────────────────────────────╮ │var users = new WriteHashMap(moment.putCursor("users")); │ │var usernameIndex = new WriteSortedMap(moment.putCursor("username->id"));│ │ │ │var alice = new WriteHashMap(users.putCursor("1")); │ │alice.put("username", new Database.Bytes("alice")); │ │alice.put("name", new Database.Bytes("Alice Jones")); │ │usernameIndex.put("alice", new Database.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 │ │var history = new WriteArrayList(db.rootCursor()); │ │ │ │// save the current index so we can revert back to it │ │var historyIndex = history.count() - 1; │ │ │ │// ...add some new transactions here │ │ │ │// read the old copy of the db from before the new transactions│ │var 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: ╭──────────────────────────────────────────────────────────────────────────────────╮ │// each thread gets its own read-only Database │ │var db = ThreadLocal.withInitial(() -> { │ │ try { │ │ var core = new CoreFile(new RandomAccessFile("main.db", "r")); │ │ return new Database(core, new Hasher(MessageDigest.getInstance("SHA-1")));│ │ } catch (Exception e) { │ │ throw new RuntimeException(e); │ │ } │ │}); │ │ │ │// read from any thread, even while another thread is writing │ │var history = new ReadArrayList(db.get().rootCursor()); │ │var 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 │ │var state = replica.replicaState(); │ │ │ │// on the source: decide which bytes to send │ │var start = source.replicationStart(state); │ │var end = source.committedSize(); │ │ │ │// copy the new bytes from the source to the replica │ │try (var in = source.openCommitted(start, end); │ │ var out = replica.openReplicated(start, end - start)) {│ │ in.transferTo(out); │ │} │ ╰────────────────────────────────────────────────────────────╯ 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