🬟 🬑 🬂🬰🬂 🬂🬰🬂 🬒🬂🬟 🬒🬂🬟 ╭──╮ 🬋 🬋 🬋 🬃 🬇 🬋🬋🬃 zig java clojure typescript │go│ 🬑 🬟 🬭🬰🬭 🬰 🬮🬭🬑 🬮🬭🬑 ╰──╯ See xit-vcs/xitdb-go 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. 🬕🬧 🬳🬶 🬨🬕 🬳🬶 🬤🬒 🬨🬕 🬴🬗 ▌▐ 🬔🬂 🬨🬕 ▌▐ 🬴🬗 🬴🬒 🬤🬒 🬳🬶 🬴🬗 🬴🬒 🬳🬶 ▌ ▌ 🬣🬘 🬔🬧 ▌▐ 🬺▐ 🬴🬒 🬴🬒 🬕🬧 🬲🬘 ▌▐ ▐▌ ▌▐ 🬱🬘 ▐▌ 🬕🬢 🬣🬘 🬣🬭 ▐▌ 🬣🬘 🬕🬢 🬲🬭 🬱🬘 ▌▐ 🬕🬢 🬲🬭 ▌▐ 🬲🬭 🬲🬭 ▐▌ 🬣🬘 🬣🬘 ▌🬬 🬲🬭 🬲🬭 🬲🬘 ╭──────────────────────────────────────────────────────────────╮ │ordersCursor, _ := moment.GetCursor("orders") │ │orders, _ := xitdb.NewReadHashMap(ordersCursor) │ │indexCursor, _ := moment.GetCursor("customer->status->orders")│ │index, _ := xitdb.NewReadHashMap(indexCursor) │ │statusesCursor, _ := index.GetCursor("42") │ │statuses, _ := xitdb.NewReadHashMap(statusesCursor) │ │shippedCursor, _ := statuses.GetCursor("shipped") │ │shipped, _ := xitdb.NewReadSortedMap(shippedCursor) │ │ │ │n := 0 │ │for cursor, _ := range shipped.All() { │ │ if n == 10 { │ │ break │ │ } │ │ n++ │ │ kv, _ := cursor.ReadKeyValuePair() │ │ orderID, _ := kv.ValueCursor.ReadBytes(maxReadBytes) │ │ orderCursor, _ := orders.GetCursor(string(orderID)) │ │ order, _ := xitdb.NewReadHashMap(orderCursor) │ │ // 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: ╭────────────────────────────────────────────────────────╮ │rows, _ := db.Query(` │ │ SELECT users.name, tags.tag │ │ FROM users LEFT JOIN tags ON tags.user_id = users.id│ │ WHERE users.id = 1 │ │ `) │ │defer rows.Close() │ │ │ │var name string │ │var tags []string │ │for rows.Next() { │ │ var tag sql.NullString │ │ rows.Scan(&name, &tag) │ │ if tag.Valid { │ │ tags = append(tags, tag.String) │ │ } │ │} │ ╰────────────────────────────────────────────────────────╯ xitdb stores your data in the shape you already use: ╭─────────────────────────────────────────────╮ │userCursor, _ := users.GetCursor("1") │ │user, _ := xitdb.NewReadHashMap(userCursor) │ │tagsCursor, _ := user.GetCursor("tags") │ │tags, _ := xitdb.NewReadArrayList(tagsCursor)│ ╰─────────────────────────────────────────────╯ 🬣🬘 🬨🬕 🬨🬕 🬕🬧 🬴🬗 🬁🬄 🬤🬒 🬕🬧 🬳🬶 🬨🬕 🬳🬶 🬤🬒 🬨🬕 🬴🬗 ▌▐ 🬔🬂 🬨🬕 ▌▐ 🬴🬗 🬴🬒 🬤🬒 🬔🬧 🬷🬲 ▐▌ 🬲🬘 🬲🬘 🬱🬘 🬲🬘 ▌▐ ▐▌ ▌▐ 🬱🬘 ▐▌ 🬕🬢 🬣🬘 🬣🬭 ▐▌ 🬣🬘 🬕🬢 🬲🬭 🬱🬘 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 │ │history, _ := xitdb.NewReadArrayList(db.RootCursor().ReadCursor)│ │ │ │// get the hash-map inside of it │ │momentCursor, _ := history.GetCursor(-1) │ │moment, _ := xitdb.NewReadHashMap(momentCursor) │ │ │ │// get the "users" sorted map inside of that │ │usersCursor, _ := moment.GetCursor("users") │ │users, _ := xitdb.NewReadSortedMap(usersCursor) │ │ │ │// get "bob" │ │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: ╭────────────────────────────────────────────────────────╮ │usersCursor, _ := moment.PutCursor("users") │ │users, _ := xitdb.NewWriteHashMap(usersCursor) │ │indexCursor, _ := moment.PutCursor("username->id") │ │usernameIndex, _ := xitdb.NewWriteSortedMap(indexCursor)│ │ │ │aliceCursor, _ := users.PutCursor("1") │ │alice, _ := xitdb.NewWriteHashMap(aliceCursor) │ │alice.Put("username", xitdb.NewString("alice")) │ │alice.Put("name", xitdb.NewString("Alice Jones")) │ │usernameIndex.Put("alice", xitdb.NewString("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 │ │history, _ := xitdb.NewWriteArrayList(db.RootCursor()) │ │ │ │// save the current index so we can revert back to it │ │count, _ := history.Count() │ │historyIndex := count - 1 │ │ │ │// ...add some new transactions here │ │ │ │// read the old copy of the db from before the new transactions│ │momentCursor, _ := history.GetCursor(historyIndex) │ │moment, _ := xitdb.NewReadHashMap(momentCursor) │ │ │ │// revert back to the old copy of the db │ │oldSlot, _ := history.GetSlot(historyIndex) │ │history.Append(oldSlot) │ ╰───────────────────────────────────────────────────────────────╯ ▌ 🬔🬧 🬔🬂 🬲🬅 🬴🬒 🬴🬗 🬴🬒 🬴🬒 🬲🬭 🬣🬘 🬣🬭 🬕🬢 ▌ 🬕🬢 🬲🬭 🬲🬭 Read xitdb from multiple threads without locks: ╭────────────────────────────────────────────────────────────────────╮ │// each goroutine gets its own read-only Database │ │openDB := func() (*xitdb.Database, error) { │ │ f, err := os.Open("main.db") │ │ if err != nil { │ │ return nil, err │ │ } │ │ hasher := xitdb.Hasher{Hash: sha1.New} │ │ return xitdb.NewDatabase(xitdb.NewCoreFile(f), hasher) │ │} │ │ │ │// read from any goroutine, even while another one is writing │ │go func() { │ │ db, _ := openDB() │ │ history, _ := xitdb.NewReadArrayList(db.RootCursor().ReadCursor)│ │ momentCursor, _ := history.GetCursor(-1) │ │ moment, _ := xitdb.NewReadHashMap(momentCursor) │ │}() │ ╰────────────────────────────────────────────────────────────────────╯ 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 │ │state, _ := replica.ReplicaState() │ │ │ │// on the source: decide which bytes to send │ │start, _ := source.ReplicationStart(state) │ │end, _ := source.CommittedSize() │ │ │ │// copy the new bytes from the source to the replica │ │pr, pw := io.Pipe() │ │go func() { pw.CloseWithError(source.ReadCommitted(start, end, pw)) }()│ │replica.ApplyReplicated(start, pr, end-start) │ ╰───────────────────────────────────────────────────────────────────────╯ 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