dbfromscratch

A SQL database written from scratch in Go, using only the standard library.

It runs as a TCP server, stores data in an LSM tree (the same design family as RocksDB and Cassandra), and recovers from crashes. On single-row inserts it is faster than Postgres when neither waits on fsync.

Status: early. This is a learning project and is not ready for production data. See Limitations for what is missing.

Quick start

Requires Go 1.27+.

make run                         # server on :7070, data in ~/dbfromscratch
go run ./cmd -addr :9000 -dir ./data

Connect with nc and type one query per line:

nc localhost 7070

CREATE TABLE users (id INT, name TEXT, age INT)
INSERT INTO users VALUES (1, 'bob', 30)
INSERT INTO users VALUES (2, 'it''s amy', 25)
SELECT name, age FROM users WHERE age >= 25 AND id <> 3
UPDATE users SET age = 31 WHERE id = 1
DELETE FROM users WHERE age < 26

Supported SQL

Statement	Example
CREATE TABLE	CREATE TABLE users (id INT, name TEXT)
INSERT	INSERT INTO users VALUES (1, 'bob')
SELECT	SELECT * FROM users or SELECT id, name FROM users WHERE id > 10
UPDATE	UPDATE users SET name = 'bobby' WHERE id = 1
DELETE	DELETE FROM users WHERE id = 1

• Types: INT (64-bit) and TEXT.
• The first column is the primary key. Rows are stored sorted by it, and duplicates are rejected.
• WHERE supports = != <> < > <= >= joined by AND.
• Strings use single quotes. A quote inside a string is written twice: 'it''s'.
• Names are case-insensitive. A trailing ; is optional.

Protocol

Plain text over TCP, one query per line.

> SELECT * FROM users
< OK 3
< id | name
< 1 | bob
< (1 row(s))
> SELEC x
< ERR unsupported statement "SELEC"

A successful reply is OK <n> followed by n lines. An error is a single ERR <message> line. Error messages are written for humans, for example syntax error at position 22: expected ")", got end of query.

How it works

client → TCP server → lexer → parser → handler → LSM storage

Part	File	Job
TCP server	cmd/main.go	One goroutine per connection, graceful shutdown on Ctrl+C
Lexer	db/lexer.go	Turns SQL text into tokens, each with its position for error messages
Parser	db/parser.go	Hand-written recursive descent parser. Detects the statement and checks the syntax
Handler	db/handler.go	Single entry point, HandleSQL. Takes the right lock and runs the statement
Storage	db/storage.go	Table schemas, row encoding, WHERE filtering
LSM tree	db/lsm.go	WAL, memtable, SSTables, compaction

Storage

Each table has its own LSM tree. On disk, in the data directory:

File	Contents
users.tbl	Schema, in a binary format with a magic number and version
users.wal	Write-ahead log of changes not yet flushed
users.000001.sst	Sorted, immutable file of rows

Writes go to the write-ahead log first, then into the memtable, an in-memory skip list sorted by key. When the memtable reaches 4 MB it is flushed to a new SSTable and the WAL is emptied. When a table has 4 SSTables, they are compacted into one.

Reads check the memtable, then the SSTables from newest to oldest, and the first match wins. Each SSTable keeps an index of its keys in memory, so a lookup is a binary search plus one disk read.

Deletes write a tombstone: the key with an empty value. Real rows always encode to at least one byte, so an empty value can only mean "deleted". Compaction removes tombstones for good.

Keys are encoded so that byte order matches value order. Integers are stored big-endian with the sign bit flipped, so -5 sorts before 1.

Crash safety

• On startup, the WAL is replayed into the memtable.
• If a crash cut a WAL record in half, replay stops there and the broken tail is cut off, so later writes are never lost behind it.
• New files are written to a temp file and renamed into place, so a file never appears half-written.
• If a crash interrupts a compaction, the leftover old files are removed on the next start.

Concurrency

The database has one sync.RWMutex. Writes take it exclusively, and reads share it, so many SELECTs run at the same time. Parsing happens before the lock, so it runs in parallel too.

Benchmark

100,000 single-row INSERTs over TCP, one query per round trip, on an Apple M5:

Clients	dbfromscratch	Postgres 18 (sync commit off)	Postgres 18 (default, durable)
1	43,492 rows/s	35,768 rows/s	13,755 rows/s
8	97,674 rows/s	92,755 rows/s	57,655 rows/s
32	106,787 rows/s	91,251 rows/s	75,840 rows/s

• The fair comparison is the middle column. dbfromscratch does not fsync, so it is compared against Postgres with synchronous_commit = off, where Postgres does not wait on fsync either.
• Both use the same Go client. Postgres uses the simple query protocol, so it parses every query just as dbfromscratch does.
• It stops scaling past 8 clients. The single write lock means only one insert runs at a time. At 32 clients, p99 latency is about 1 ms, against about 0.6 ms for Postgres.
• The benchmark is small. 100,000 rows fit in the memtable, so it does not measure flushes or compaction.

Run it yourself against a local Postgres:

make bench PG=postgres://user@localhost:5432/dbname

The benchmark lives in bench/, in its own Go module, so the Postgres driver is not a dependency of the database.

Development

make test     # go test -race ./...
make check    # gofmt, go vet, and tests, the same as CI
make build    # binary in bin/dbfromscratch

The tests cover every statement and error message, reopening the database, forced flushes and compaction, a torn WAL write, a crashed compaction, concurrent writers under the race detector, and the TCP server end to end.

Limitations

• No fsync. Data survives the process crashing, but the last few seconds of writes can be lost on power loss.
• No transactions. A multi-row UPDATE or DELETE that crashes halfway leaves some rows changed.
• Two types only, and no NULL.
• WHERE reads every row, even when it filters on the primary key.
• Scans and compaction hold the whole table in memory.
• One global write lock, so writes do not scale across cores.
• Compaction blocks writes while it runs.
• One query per line, so a query cannot span lines.

What's next

1. Durability: an fsync option with group commit, and checksums on every record.
2. Transactions: BEGIN, COMMIT and ROLLBACK, with all-or-nothing multi-row changes.
3. More SQL: NULL, more types, ORDER BY, LIMIT and aggregates.
4. Fast reads: range scans on the primary key, bloom filters, and a merge iterator that does not load whole tables.
5. An embedded Go API and a database/sql driver.
6. Concurrent writers with MVCC.
7. The Postgres wire protocol, so psql and existing drivers can connect.

Support

If you like what I'm building, you can support my work:

License

See LICENSE. Use and modification are allowed with credit to the original author.