PallasDB

PallasDB is a key-value database written in Go, built from first principles. It provides crash-safe persistence, sorted string tables, multi-level compaction, a SQL layer, gRPC transport, and Raft-backed replication.

What it is

At its core PallasDB is an LSM-tree storage engine layered with:

• A Write-Ahead Log (WAL) for crash safety
• SSTables (Sorted String Tables) for durable sorted storage
• A merge iterator that unifies multiple sorted levels into a single view
• An MVCC transaction model with snapshot isolation and conflict detection
• A recursive-descent SQL parser and expression evaluator
• A gRPC server for remote key-value access
• A Raft consensus layer (via HashiCorp Raft) for replicated, strongly-consistent writes
• Serf gossip for automatic cluster member discovery

Source layout

Design goals

• Crash-safe by default - every committed write is fsync'd before returning.
• Sorted access - all structures (memtable, SSTables, merge iterators) maintain lexicographic order, enabling efficient range scans.
• Strong consistency in cluster mode - all mutating operations route through the Raft leader; reads can be served locally.
• Self-contained binary - a single pallasdb binary covers local embed, standalone gRPC server, and full Raft cluster node.

Getting Started

Installation

Requires Go 1.25 or later.

git clone https://github.com/teddymalhan/pallasdb.git
cd pallasdb
go mod download
go build -o pallasdb ./cmd/pallasdb

Run the test suite:

go test ./...

Configuration

PallasDB reads configuration from three sources with the following precedence:

CLI flags  >  environment variables  >  config file  >  built-in defaults

Load an explicit config file:

pallasdb --config ./pallasdb.example.yaml serve grpc

Environment variables use the PALLASDB_ prefix; dots and dashes become underscores:

PALLASDB_LOG_FORMAT=json \
PALLASDB_SERVE_GRPC_ADDR=:50052 \
pallasdb serve grpc

Config key reference

Example YAML config

log:
  format: text

shutdown:
  timeout: 15s

local:
  data_dir: data

serve:
  grpc:
    addr: ":50051"
    data_dir: data

cluster:
  grpc_addr: ":50051"
  data_dir: data
  raft_addr: ":7001"
  raft_dir: raft
  node_id: node-1
  join: ""
  apply_timeout: 10s
  serf:
    enabled: true
    addr: ":7946"
    advertise_addr: ""
    join: []
    event_buffer: 64

CLI Reference

pallasdb local - local key-value operations

All local commands accept --data-dir to specify where data is stored.

# Insert or update a key
pallasdb local put <key> <value> --data-dir ./data

# Fetch a key
pallasdb local get <key> --data-dir ./data

# Scan a key range [start, stop]
pallasdb local range <start> <stop> --data-dir ./data

# Delete a key
pallasdb local delete <key> --data-dir ./data

# Trigger compaction
pallasdb local compact --data-dir ./data

pallasdb local benchmark - disk-backed benchmark

pallasdb local benchmark \
  --data-dir /tmp/bench \
  --reset \
  --keys 2000000 \
  --value-size 128 \
  --batch-size 1000 \
  --read-ops 500000 \
  --compact \
  --format text \
  --output results.txt

pallasdb serve grpc - standalone gRPC server

pallasdb serve grpc --addr :50051 --data-dir ./data

pallasdb cluster start - Raft cluster node

Bootstrap the first node:

pallasdb cluster start \
  --node-id node-1 \
  --grpc-addr :50051 \
  --raft-addr :7001 \
  --serf-addr :7946 \
  --data-dir ./data/node-1 \
  --raft-dir ./raft/node-1

Join a running cluster via Serf gossip:

pallasdb cluster start \
  --node-id node-2 \
  --grpc-addr :50052 \
  --raft-addr :7002 \
  --serf-addr :7947 \
  --serf-join localhost:7946 \
  --data-dir ./data/node-2 \
  --raft-dir ./raft/node-2

Join explicitly via gRPC (no Serf):

pallasdb cluster start \
  --node-id node-2 \
  --grpc-addr :50052 \
  --raft-addr :7002 \
  --serf-enabled=false \
  --join localhost:50051 \
  --data-dir ./data/node-2 \
  --raft-dir ./raft/node-2

pallasdb completion - shell completions

pallasdb completion bash
pallasdb completion zsh
pallasdb completion fish
pallasdb completion powershell

pallasdb version

pallasdb version
# pallasdb dev
# commit: none
# built: unknown

Architecture Overview

PallasDB is structured as three independent layers that can be used separately or stacked together.

Data flow - write path

1. Client calls KV.Set(key, val) (or via gRPC Put, or SQL INSERT).
2. A transaction (KVTX) is opened with a snapshot of the current state.
3. The mutation is staged in tx.updates (a SortedArray).
4. On Commit(): a. A conflict check compares updated keys against keys modified by concurrent transactions since this snapshot. b. Each mutation is appended to the WAL (Log.Write) as a EntryAdd or EntryDel record. c. A EntryCommit record is written and fsync'd - the write is now durable. d. The transaction's updates are merged into the in-memory memtable (kv.mem).
5. If auto-compact is enabled, a compaction signal is sent on kv.updated.

In cluster mode, mutating commands are first encoded as a Command protobuf, submitted to raft.Apply, and only reach the FSM's Apply() method after consensus. The FSM then calls db.KV.SetEx / db.KV.Del directly.

Data flow - read path

1. KV.Get(key) checks the optional Ristretto LRU cache first.
2. A transaction is opened, creating a MergedSortedKV view spanning:
   • tx.updates (pending mutations, if any)
   • kv.mem (memtable snapshot)
   • kv.main[0..n] (SSTable snapshots, newest first)
3. The merged view performs getExact(key):
   • For SortedArray: binary search on the in-memory key slice.
   • For SortedFile: bloom filter pre-check, then binary search using the on-disk offset index.
4. The first level that returns found=true wins; deleted markers suppress the result.
5. On cache miss the result is inserted into the Ristretto cache.

Compaction

Compaction has two sub-operations that are triggered by KV.Compact():

Both operations update the double-buffered metadata files atomically before closing old files.

Key dependencies

Storage Engine

The storage engine lives entirely in db/. It is a classic LSM-tree (Log-Structured Merge-tree) with a custom binary encoding layer.

Components at a glance

On-disk layout

For a data directory ./data, PallasDB creates:

SSTable filenames are sstable_<version> where version is a monotonically increasing uint64 tracked in the metadata.

Data flow summary

The sections below document each component in detail.

Cells and Rows

Source: db/cell.go, db/row.go

PallasDB's lowest encoding layer provides two abstractions: Cell (a single typed value) and Row (an ordered collection of Cells).

Cell

A Cell holds one of two types:

type CellType uint8

const (
    TypeI64 CellType = 1  // int64
    TypeStr CellType = 2  // []byte (variable-length string)
)

type Cell struct {
    Type CellType
    I64  int64
    Str  []byte
}

Key encoding

Keys must sort correctly when compared as raw bytes. PallasDB encodes each type differently:

TypeI64 - big-endian with sign bit flipped:

uint64(i64) XOR (1 << 63)  →  8 bytes, big-endian

The XOR flips the sign bit so that negative integers sort before positive integers in unsigned byte order (e.g., -1 sorts before 0).

TypeStr - null-terminated with escape sequences:

This scheme preserves lexicographic order and allows variable-length strings to be compared without knowing their length in advance.

Value encoding

Values do not need to sort, so a simpler encoding is used:

TypeI64 - 8 bytes, little-endian.

TypeStr - 4-byte little-endian length prefix followed by the raw bytes.

Row

A Row is a []Cell whose length matches the schema's column count.

type Schema struct {
    Table   string
    Cols    []Column    // column definitions
    Indices [][]int     // each index is a list of column positions
}

type Column struct {
    Name string
    Type CellType
}

Key encoding for rows

[table_name] 0x00 [index_number(1 byte)]
  [type_byte(1)] [encoded_cell] ...  (for each indexed column)
0x00

The table name prefix and index number isolate keys for different tables and different indices in the same KV namespace.

Value encoding for rows

Only non-primary-key columns are stored in the value. Primary key columns are already encoded in the key. Each non-PK column appends its EncodeVal output in column order.

Index keys

Secondary indices encode the indexed columns plus the primary key columns (to keep keys unique). The value for a secondary index entry is empty - the primary key is already in the key itself, so a secondary index lookup requires a follow-up primary key lookup to fetch the full row.

Example

For a schema with columns (id int64, name string) and primary key (id):

Key:   "users" 0x00 0x00  TypeI64 [big-endian id ^ sign]  0x00
Value: [4-byte length] [name bytes]

A secondary index on (name, id) would produce:

Key:   "users" 0x00 0x01  TypeStr [escaped name bytes] 0x00  TypeI64 [big-endian id ^ sign]  0x00
Value: (empty)

Write-Ahead Log (WAL)

Source: db/log.go, db/kv_entry.go

The Write-Ahead Log (WAL) provides crash-safe persistence. Every committed transaction is written and fsync'd to the WAL before the in-memory state is updated. On restart, PallasDB replays all committed entries to reconstruct the memtable.

Log entries

Each WAL record is a single Entry:

type EntryOp uint8

const (
    EntryAdd    EntryOp = 0  // set key → value
    EntryDel    EntryOp = 1  // delete key
    EntryCommit EntryOp = 2  // transaction boundary
)

type Entry struct {
    key []byte
    val []byte
    op  EntryOp
}

Wire format

Each entry is encoded as:

[4 bytes] CRC32-IEEE checksum of everything after these 4 bytes
[4 bytes] key length (little-endian uint32)
[4 bytes] value length (little-endian uint32)
[1 byte]  op (EntryAdd=0, EntryDel=1, EntryCommit=2)
[key len] key bytes
[val len] value bytes

The CRC32 checksum covers all bytes starting from the key-length field. An EntryCommit record has zero-length key and value. The maximum entry size is 64 MiB.

Transaction protocol

A single transaction writes:

EntryAdd  key=k1  val=v1
EntryDel  key=k2  val=nil
EntryAdd  key=k3  val=v3
EntryCommit

The Commit() call:

1. Writes the EntryCommit record.
2. Calls file.Sync() - the writes are now durable.
3. Advances writer.committed to the current offset.

If the process crashes before Sync() returns, the uncommitted records are ignored on recovery because the commit marker was never persisted.

ResetTX() rolls back an uncommitted transaction by resetting the write offset to writer.committed, overwriting any partially written records on the next write.

Recovery on startup

openLog() in kv.go:

1. Reads entries sequentially from offset 0.
2. Accumulates EntryAdd / EntryDel records in a buffer.
3. On EntryCommit, records the committed count.
4. On EOF, bad checksum, or truncated read, stops - only committed entries survive.
5. Sorts the committed entries by key (stable sort), then replays them into the memtable, deduplicating by keeping the last write per key.

Log truncation

When the memtable is compacted into an SSTable (compactLog()), the WAL is truncated to zero with file.Truncate(0). The SSTable now contains the durable representation of what was in the log.

File management

The WAL file is created via createFileSync which opens with O_CREATE | O_RDWR and calls Sync() after creation to ensure the directory entry is durable. Reads use ReadAt (positioned reads) via OffsetReader, avoiding seek races when reading and writing concurrently.

Sorted Array (Memtable)

Source: db/sorted_array.go

The memtable is an in-memory sorted key-value store backed by three parallel slices. It is the mutable hot tier of the LSM tree - all committed writes land here before being compacted to disk.

Data structure

type SortedArray struct {
    keys    [][]byte
    vals    [][]byte
    deleted []bool
}

The three slices are kept in strict lexicographic key order. A deleted=true entry is a tombstone - it records that a key was deleted without removing it from the array, so that merging with older SSTables correctly shadows the older value.

Interface

SortedArray implements the SortedKV interface:

type SortedKV interface {
    EstimatedSize() int
    Iter() (SortedKVIter, error)
    Seek(key []byte) (SortedKVIter, error)
}

And additionally implements sortedKVExactGetter for O(log n) point lookups without creating a full iterator.

Key operations

Iterator

SortedArrayIter holds a snapshot of the slice headers at creation time. It supports Next() and Prev() for bidirectional iteration.

Fast-path append during commit

When committing a transaction and there are no concurrent transactions, appendSortedArray is attempted first:

// If all keys in src sort after all keys in dst, just append.
if dst.Size() != 0 && bytes.Compare(dst.keys[last], src.keys[0]) >= 0 {
    return false  // fall back to merge
}
dst.keys = append(dst.keys, src.keys...)
// ...

This is a common case for sequential key populations and avoids the O(n) merge path.

Merge into memtable

When the fast-path append is not safe (e.g., overlapping key ranges or concurrent transactions), the commit merges the transaction updates with the current memtable using MergedSortedKV:

merged := SortedArray{}
iter, _ := MergedSortedKV{&tx.updates, &kv.mem}.Iter()
for ; iter.Valid(); iter.Next() {
    merged.Push(iter.Key(), iter.Val(), iter.Deleted())
}
kv.mem = merged

The merge iterator gives priority to the first (newer) level, so transaction updates shadow older memtable entries.

SSTables (Sorted String Tables)

Source: db/sorted_file.go

SSTables are immutable, on-disk sorted key-value files. They represent the durable tier of the LSM tree. Once written, an SSTable is never modified - compaction merges multiple SSTables into a new one and then deletes the old files.

File format

Byte offset 0:
  [8 bytes]   nkeys  (little-endian uint64) - number of entries

Bytes 8 to 8 + nkeys*8:
  [8 bytes each]  entry offsets (little-endian uint64)
                  offsetIndex[i] = file offset of entry i

Entry at offset[i]:
  [4 bytes]  key length (little-endian uint32)
  [4 bytes]  value length (little-endian uint32)
  [1 byte]   deleted flag (0 = live, 1 = tombstone)
  [key len]  key bytes
  [val len]  value bytes

After all entries:
  [bloom len bytes]  marshaled bloom filter
  [8 bytes]          bloom filter byte length (little-endian uint64)
  [8 bytes]          magic: 'P' 'D' 'B' 'B' 'L' 'M' '1' '\n'

The file starts with an offset index - one 8-byte file offset per entry - enabling O(1) random access to any entry given its position. The maximum supported keys per file is 1 << 26 (~67 million).

The offset index is loaded into memory (file.offsetIndex) during Open() if it fits within 64 MiB. For larger files the offset index falls back to an individual ReadAt per lookup.

Bloom filter

Each SSTable embeds a Bloom filter (github.com/bits-and-blooms/bloom/v3) at the end of the file:

• False positive rate: 1% (sortedFileBloomFalsePositiveRate = 0.01)
• Keys are added during writeSortedFile
• On Open(), the bloom filter is deserialized from the file footer
• Before any binary search, mayContainKey(key) is called - if the bloom filter definitively says the key is absent, the binary search is skipped entirely

This is critical for performance: a Get for a key that does not exist in a given SSTable requires only a bloom filter check (a few memory accesses) rather than a full binary search with disk reads.

Seeking and binary search

findPos(target) performs a binary search using compareKeyAt(mid, target):

1. Computes the file offset of entry mid (from the in-memory offset index or a ReadAt).
2. Reads only the key header + key bytes (not the value).
3. Compares with bytes.Compare(target, key).

This means values are never read during binary search - only keys. This optimization significantly reduces I/O for large values.

findPosExact(target) returns (pos, found, error) and is used for exact-match Get operations.

Seek(key) returns an iterator positioned at or after key.

Reading values separately

valueAt(pos) reads only the value (and deleted flag) for a given position, by:

1. Looking up the file offset via the offset index.
2. Reading the header to get klen and vlen.
3. Seeking past the key bytes to read only the value.

This is used in getExact after a successful binary search - the key comparison during search never touches value bytes.

Writing an SSTable

CreateFromSorted(kv SortedKV) writes a new SSTable from any SortedKV source:

1. Pre-allocates an offset index slot for each estimated key.
2. Iterates the source, writing each entry and recording its offset.
3. After all entries, writes the final nkeys count at offset 0.
4. Appends the bloom filter and its footer.
5. Calls file.Sync() to ensure durability before the caller updates metadata.

Limits

LSM Tree & Compaction

Source: db/kv.go, db/merge.go

PallasDB's storage engine is an LSM-tree (Log-Structured Merge-tree). Writes go to an in-memory memtable (backed by a WAL) and are periodically flushed and merged to disk as SSTables.

Levels

The LSM structure has a flat list of levels:

Level 0: kv.mem      (SortedArray - in-memory, mutable)
Level 1: kv.main[0]  (SortedFile - newest SSTable)
Level 2: kv.main[1]  (SortedFile)
...
Level N: kv.main[N-1] (SortedFile - oldest SSTable)

A read must check all levels in order (newest first) because a newer level may contain an update or deletion that shadows an older entry.

Merge iterator

MergedSortedKV unifies multiple SortedKV sources into a single sorted stream:

type MergedSortedKV []SortedKV

MergedSortedKVIter maintains one iterator per level and at each step selects the level with the lexicographically smallest current key. On Next(), only levels that are at or behind the current key are advanced.

For point lookups (getExact), MergedSortedKV short-circuits: it queries each level in order and returns the first hit, so lower (older) levels are not accessed if an upper level has the key.

Compaction triggers

KV.Compact() is called:

• Explicitly via pallasdb local compact
• Automatically after each commit when AutoCompact=true (via a background goroutine)
• Automatically after each gRPC write in serve grpc mode

func (kv *KV) Compact() error {
    if memSize >= kv.Options.LogThreshold {
        return kv.compactLog()   // flush memtable → new SSTable
    }
    for i := 0; i < len(kv.main)-1; i++ {
        if kv.shouldMerge(i) {
            return kv.compactSSTable(i)  // merge two adjacent SSTables
        }
    }
    return nil
}

Log compaction (memtable flush)

Triggered when memtable.Size() >= LogThreshold (default: 1,000 entries).

1. Increment kv.version, compute SSTable filename sstable_<version>.
2. Write the memtable as a new SortedFile at kv.main[0] position.
   • If this is not the last SSTable level, tombstones are preserved (older levels may have live entries that need to be hidden).
   • If it would be the only SSTable, tombstones are stripped (NoDeletedSortedKV wrapper).
3. Atomically update metadata: prepend the new SSTable name to the list.
4. Insert the new SortedFile at position 0 in kv.main.
5. Clear the memtable and truncate the WAL.

SSTable merge

Triggered when sstable[i].EstimatedSize() * GrowthFactor >= sstable[i+1].EstimatedSize().

The default GrowthFactor is 2.0, implementing a 2× size ratio between adjacent levels - similar to LevelDB's tiered compaction.

1. Merge kv.main[i] and kv.main[i+1] using MergedSortedKV.
2. Write the merged result as a new SortedFile.
   • If the two files are the last in kv.main, tombstones are stripped.
3. Update metadata atomically.
4. Close and delete the two old SSTable files.
5. Replace the two entries in kv.main with the single new file.

Growth factor and compaction policy

With GrowthFactor=2.0:

Level 1: ~1,000 entries  (log threshold)
Level 2: ~2,000 entries  (after first merge: 1+2)
Level 3: ~4,000 entries
Level 4: ~8,000 entries
...

Each compaction at level i merges levels i and i+1, producing a file roughly 2× the size. This bounds the total number of levels to O(log N) for N total entries.

Tombstone garbage collection

Tombstones (deleted=true entries) are only safe to remove when they are in the last (oldest) SSTable level. If a tombstone were removed from a non-bottom level, an older SSTable might surface the deleted entry.

NoDeletedSortedKV is applied as a wrapper around the source when writing the bottom level SSTable:

type NoDeletedSortedKV struct{ SortedKV }

func (kv NoDeletedSortedKV) Iter() (SortedKVIter, error) {
    iter, _ := kv.SortedKV.Iter()
    return NoDeletedIter{iter}, nil  // skips tombstones
}

Options

Metadata Management

Source: db/metadata.go

The metadata subsystem tracks which SSTable files currently make up the persistent storage. It uses a double-buffered write strategy to guarantee that a metadata update is either fully applied or fully absent - never partially written - even if the process crashes mid-write.

Data model

type KVMetaData struct {
    Version  uint64   // monotonically increasing, identifies the current generation
    SSTables []string // ordered list of SSTable filenames, newest first
}

Version starts at 0 and increments on every compaction. SSTable filenames are relative to the data directory (e.g., "sstable_7").

Double-buffered files

Two metadata files (meta0, meta1) are maintained. At any point, the file with the higher Version is the authoritative current state:

func (meta *KVMetaStore) current() int {
    if meta.slots[0].data.Version > meta.slots[1].data.Version {
        return 0
    }
    return 1
}

Write protocol

Set(data):

1. Determine the current slot (c).
2. Write data to the other slot (1-c).
3. Update the in-memory state of that slot.

The current slot is never overwritten until the new slot has been successfully fsynced. This means:

• If a crash occurs during step 2, the current slot is still valid.
• After recovery, current() returns the slot with the higher version, which is always a consistent state.

Metadata file format

Each metadata file holds:

[4 bytes]  CRC32-IEEE checksum of bytes 4 onward
[4 bytes]  JSON payload length (little-endian uint32)
[N bytes]  JSON-encoded KVMetaData

On read, if the checksum does not match or the file is too short, KVMetaData{} (zero value with Version=0) is returned - this is treated as an empty/uninitialized slot.

Integration with compaction

During compactLog() (memtable flush):

meta := kv.meta.Get()            // read current metadata
meta.Version = kv.version        // increment version
meta.SSTables = slices.Insert(meta.SSTables, 0, sstable)  // prepend new SSTable
kv.meta.Set(meta)                // write to the other slot (fsynced)

During compactSSTable(level) (SSTable merge):

meta.SSTables = slices.Replace(meta.SSTables, level, level+2, sstable)
kv.meta.Set(meta)

Both operations complete atomically from the metadata perspective: the old SSTable names are still referenced until meta.Set succeeds, so the data files are not deleted until after the metadata update.

Recovery on startup

openSSTable() calls kv.meta.Get() to find the current SSTable list, then opens each file in order. If a file listed in metadata does not exist on disk, Open() returns an error.

Transactions

Source: db/kv.go

PallasDB implements snapshot-isolated, optimistic MVCC transactions. Each transaction sees a consistent snapshot of the store at the time it was opened. Concurrent transactions can proceed in parallel; conflicts are detected only at commit time.

Transaction types

Both types support nested transactions: tx.NewTX() creates a child transaction whose updates are applied to the parent on commit rather than directly to the store.

Opening a transaction

tx := kv.NewTX()

NewTX() under kv.mu:

1. Takes a snapshot of kv.snapshot (a monotonically increasing counter).
2. Copies the memtable reference and SSTable list (copy-on-read - the slices are shared but immutable from the transaction's perspective).
3. Constructs a MergedSortedKV view: [tx.updates, memtable_snapshot, sstable_0, ...]
4. Registers the transaction in kv.ongoing.

Reading in a transaction

val, ok, err := tx.Get(key)

Delegates to tx.levels.getExact(key) which scans levels newest-first. Tombstones (deleted=true) cause ok=false. The result reflects the state at the snapshot time plus any updates staged in tx.updates.

Range scans:

iter, err := tx.Range(start, stop, descending)

Returns a RangedKVIter that stops when the key moves past stop (ascending) or before stop (descending). Tombstones are filtered by NoDeletedIter.

Writing in a transaction

tx.Set(key, val)          // upsert
tx.SetEx(key, val, mode)  // ModeInsert, ModeUpdate, or ModeUpsert
tx.Del(key)               // delete (stages a tombstone)

All mutations go into tx.updates (a SortedArray) and are invisible to other transactions until Commit().

Committing

err := tx.Commit()

Under kv.commit (a separate mutex from kv.mu):

1. Conflict check - if tx.updates is non-empty, compare each updated key against kv.history. If any key was updated by another transaction after this transaction's snapshot, return ErrTXConflict.

2. WAL write - iterate tx.updates, write one EntryAdd or EntryDel per key, then write EntryCommit and call Sync().

3. Memtable update (under kv.mu):

   • Fast path: if no other transactions are open, try appendSortedArray (O(1) if updates sort after existing keys).
   • Merge path: build a new merged SortedArray from MergedSortedKV{tx.updates, kv.mem}.

4. History update - increment kv.snapshot and record updated keys in kv.history (if other transactions are open and might conflict).

Conflict detection

kv.history is a log of (snapshot, key) pairs for every key written since the oldest open transaction's snapshot:

type UpdatedKey struct {
    snapshot uint64
    key      []byte
}

A conflict occurs if any key in tx.updates appears in kv.history with a snapshot newer than tx.snapshot. This is a write-write conflict: another transaction committed a write to the same key after this transaction read it.

kv.history is pruned when transactions close: entries older than the oldest open transaction's snapshot are removed, as they can no longer cause conflicts.

Aborting

tx.Abort()

Removes the transaction from kv.ongoing and prunes kv.history. No WAL entry is written. The staged tx.updates are discarded.

Nested transactions

tx.NewTX() creates an inner transaction whose levels include the parent's tx.updates at the front:

inner := &KVTX{target: tx}
inner.levels = slices.Concat(MergedSortedKV{&inner.updates}, tx.levels)

On inner.Commit(), the inner updates are merged into tx.updates (not written to the WAL). On inner.Abort(), the inner updates are silently dropped. This is used by the SQL layer to implement statement-level atomicity within a larger transaction.

Synchronization

kv.commit is held for the duration of the write pipeline, ensuring WAL entries are appended in commit order. kv.mu is held only briefly to update in-memory state after the WAL write completes.

UpdateMode

SetEx and KV.SetEx accept an UpdateMode:

If the mode's precondition is not met, updated=false is returned and no WAL entry is written.

SQL Parser & Evaluator

Source: db/sql_parser.go, db/eval.go, db/table.go

PallasDB includes a hand-written recursive-descent SQL parser and expression evaluator. The SQL layer runs on top of the KV store and uses the DB / DBTX types to manage schemas and data.

Supported statements

Column types: int64, string.

Parser

Parser is a struct holding the input string and current position:

type Parser struct {
    buf   string
    pos   int
    depth int  // guards against deeply nested expressions
}

NewParser(s string) creates a parser. parseStmt() dispatches to the appropriate parse function based on the first keyword.

Token model

The parser does not produce a separate token stream - it operates directly on the input string with helper methods:

• tryKeyword(kws ...string) - case-insensitive keyword match (requires separator after)
• tryPunctuation(tok string) - exact string match
• tryName() - identifier: starts with letter or _, continues with [a-zA-Z0-9_]
• parseValue(out *Cell) - integer or string literal

Expression grammar

expr   ::= or
or     ::= and ("OR" and)*
and    ::= not ("AND" not)*
not    ::= "NOT" not | cmp
cmp    ::= add (("=" | "!=" | "<>" | "<=" | ">=" | "<" | ">") add)*
add    ::= mul (("+" | "-") mul)*
mul    ::= neg (("*" | "/") neg)*
neg    ::= "-" neg | atom
atom   ::= "(" expr ")" | name | value

The maximum expression depth is 1,000 (maxExprDepth) to prevent stack overflow from deeply nested NOT or negation chains.

AST nodes

type ExprBinOp struct { op ExprOp; left, right any }
type ExprUnOp  struct { op ExprOp; kid any }
type ExprTuple struct { kids []any }
// leaf nodes: string (column name) or *Cell (literal value)

Operators:

Expression evaluator

evalExpr(schema *Schema, row Row, expr any) (*Cell, error) evaluates an AST node against a row:

• String (column name) - looks up the column index in the schema and returns the cell from the row.
• *Cell (literal) - returns the literal directly.
• ExprUnOp - applies OP_NEG (negate integer) or OP_NOT (boolean not).
• ExprBinOp - evaluates both sides and applies the operator.

Arithmetic operations (+, -, *, /) require both sides to be TypeI64. Division by zero returns an error.

Comparison operations support both TypeI64 and TypeStr. Comparing different types returns an error.

Logical operators (AND, OR) work on TypeI64 values: 0 is false, anything else is true.

Schema management

Schemas are stored as JSON-encoded Schema values in the KV store under the key @schema_<table>:

val, _ := json.Marshal(schema)
tx.kv.Set([]byte("@schema_"+table), val)

GetSchema(table) checks a per-transaction cache (tx.tables) first, then falls back to a KV lookup. This avoids repeated schema deserialization within a transaction.

WHERE clause optimization

The SQL executor does not use a full-table scan. Instead, makeRange(schema, cond) analyzes the WHERE clause and attempts to convert it into a RangeReq:

1. Point lookup: if the WHERE is a conjunction of col = literal equalities that exactly matches the primary key columns, produces a single-key range [pk, pk].

2. Range scan: if the WHERE is a comparison (<, <=, >, >=) or a conjunction of two opposite comparisons on a primary-key prefix, produces a bounded range scan. Secondary indices are also tried.

3. Unimplemented: if neither pattern matches, returns "unimplemented WHERE". Full table scans are not supported.

This design means SQL queries must always be anchored to an index - a WHERE clause that cannot be resolved to an index range is rejected.

Table operations

DBTX wraps KVTX and adds schema-aware methods:

All mutating operations maintain secondary indices: an update first deletes all existing index entries (using the old values), then inserts new ones.

Executing SQL

p := db.NewParser("SELECT id, name FROM users WHERE id >= 1 AND id <= 100;")
stmt, err := p.parseStmt()
result, err := dbHandle.ExecStmt(stmt)

ExecStmt wraps the execution in a transaction. SQLResult contains:

type SQLResult struct {
    Updated int    // rows affected (INSERT/UPDATE/DELETE)
    Header  []string // column names (SELECT)
    Values  []Row    // result rows (SELECT)
}

gRPC API

Source: grpc/server.go, grpc/cluster_server.go, proto/pallasdb/v1/kv.proto

PallasDB exposes its key-value store and cluster management over gRPC using Protocol Buffers v3.

Services

service KVService {
  rpc Get(GetRequest) returns (GetResponse);
  rpc Put(PutRequest) returns (PutResponse);
  rpc Delete(DeleteRequest) returns (DeleteResponse);
  rpc Range(RangeRequest) returns (stream RangeResponse);
}

service ClusterService {
  rpc Join(JoinRequest) returns (JoinResponse);
  rpc ListMembers(ListMembersRequest) returns (ListMembersResponse);
  rpc GetLeader(GetLeaderRequest) returns (GetLeaderResponse);
}

KVService

Get

message GetRequest  { bytes key = 1; }
message GetResponse { bytes value = 1; }

Fetches the value for key. Returns codes.NotFound if the key does not exist. Returns codes.InvalidArgument if key is empty.

Put

enum PutMode {
  PUT_MODE_UNSPECIFIED = 0;  // treated as UPSERT
  PUT_MODE_UPSERT = 1;
  PUT_MODE_INSERT = 2;
  PUT_MODE_UPDATE = 3;
}

message PutRequest  { bytes key = 1; bytes value = 2; PutMode mode = 3; }
message PutResponse { bool updated = 1; }

Inserts or updates key according to mode:

updated=true if the store was actually modified.

Delete

message DeleteRequest  { bytes key = 1; }
message DeleteResponse { bool deleted = 1; }

Deletes key. Returns codes.NotFound if the key does not exist.

Range (server-streaming)

message RangeRequest  { bytes start = 1; bytes stop = 2; bool descending = 3; }
message RangeResponse { bytes key = 1; bytes value = 2; }

Streams all live key-value pairs in [start, stop] (ascending) or [stop, start] (descending). Both start and stop are required. The stream ends when the key range is exhausted or the client cancels.

ClusterService

Join

message JoinRequest  { string node_id = 1; string raft_addr = 2; }
message JoinResponse {}

Called by a new node to register itself with the leader. The leader calls raft.AddVoter to add the joining node to the Raft configuration.

ListMembers

message ListMembersResponse {
  repeated ClusterMember members = 1;
}

message ClusterMember {
  string node_id = 1;
  string grpc_addr = 2;
  string raft_addr = 3;
  string serf_addr = 4;
  ClusterMemberStatus status = 5;
  bool raft_voter = 6;
  bool leader = 7;
}

Returns all known cluster members, merging information from both Raft's server list and Serf's member list.

GetLeader

message GetLeaderResponse { string node_id = 1; string raft_addr = 2; }

Returns the current Raft leader's node ID and Raft transport address.

Server implementation

KVServer

KVServer in grpc/server.go wraps a *db.KV and implements KVServiceServer.

For Get / Put / Delete, the flow is:

1. Validate that key is non-empty.
2. Check ctx.Err() (cancelled/deadline exceeded).
3. Call the corresponding db.KV method.
4. Map errors to gRPC status codes.

For Range, a transaction is opened (store.NewTX()) and held for the duration of the stream. The transaction provides a point-in-time consistent view of the store.

Health check

NewGRPCServer also registers the standard gRPC health service (grpc/health/grpc_health_v1):

healthSrv := health.NewServer()
healthSrv.SetServingStatus("", healthpb.HealthCheckResponse_SERVING)

Logging interceptor

LoggingUnaryInterceptor is available for unary RPCs. It logs the method name, gRPC status code, and duration using log/slog.

srv := grpcapi.NewGRPCServer(store, grpc.ChainUnaryInterceptor(
    grpcapi.LoggingUnaryInterceptor(logger),
))

Graceful shutdown

Serve(ctx, lis, srv) blocks until ctx is cancelled. On cancellation, GracefulStop is called with a 15-second timeout. If graceful stop does not complete within the timeout, srv.Stop() is called.

Regenerating protobuf code

go install github.com/bufbuild/buf/cmd/buf@latest
go install google.golang.org/protobuf/cmd/protoc-gen-go@latest
go install google.golang.org/grpc/cmd/protoc-gen-go-grpc@latest
buf generate

The buf.yaml and buf.gen.yaml in the repository root configure the buf toolchain.

Cluster & Raft

Source: cluster/node.go, cluster/fsm.go, cluster/fsm_snapshot.go, cluster/command.go, cluster/discovery/serf.go

PallasDB's cluster mode provides strongly-consistent replicated writes using the HashiCorp Raft library. Member discovery uses Serf gossip.

Architecture

All mutating writes (Put, Delete) go through the Raft leader. Reads can be served locally from any node's FSM state (eventual consistency for reads, strong consistency for writes).

Node lifecycle

cluster.Open(kvStore, cfg)

1. Creates the Raft data directory (cfg.RaftDir).
2. Configures the Raft instance with cfg.NodeID as the local server ID.
3. Opens a TCP transport on cfg.RaftAddr.
4. Opens a BoltDB store at cfg.RaftDir/raft.db (with a 5-second file lock timeout to avoid blocking on a crashed predecessor).
5. Creates a file-based snapshot store (keeps 2 snapshots).
6. Creates the FSM wrapping kvStore.
7. Starts the raft.Raft instance.
8. If cfg.Bootstrap=true, bootstraps the cluster with this node as the sole voter.
9. If cfg.SerfEnabled=true, starts Serf and begins handling discovery events.
10. If cfg.JoinAddr != "", sends a gRPC Join request to the existing cluster.

Node.Shutdown()

1. Stops Serf (if enabled).
2. Shuts down the Raft instance.
3. Closes the TCP transport.
4. Closes the BoltDB store.

Finite State Machine (FSM)

FSM implements raft.FSM and wraps *db.KV with a sync.RWMutex to allow atomic state replacement during Restore.

Apply(log *raft.Log) interface{}

Called by Raft after a log entry is committed to a quorum. The entry is decoded as a Command:

type Command struct {
    Op   OpType      // OpPut or OpDel
    Key  []byte
    Val  []byte
    Mode uint8       // maps to db.UpdateMode
}

• OpPut → store.SetEx(key, val, mode)
• OpDel → store.Del(key)

Returns *FSMResult{Updated: bool, Err: error}. The caller (cluster gRPC server) surfaces the error to the client.

Snapshot() (raft.FSMSnapshot, error)

Calls store.IterAll() to get a consistent point-in-time iterator. The iterator and its cleanup function are passed to FSMSnapshot, which streams all key-value pairs to the snapshot sink.

Restore(rc io.ReadCloser) error

Atomically replaces the entire FSM state:

1. Reads all (key, val) pairs from the snapshot stream.
2. Opens a fresh db.KV at a temp directory (dirpath + ".restore").
3. Writes all pairs to the fresh store.
4. Under f.mu.Lock():
   • Closes the existing store.
   • Removes the old data directory.
   • Renames the temp directory to dirpath.
   • Opens a new db.KV from dirpath.
5. The entire directory swap is the atomic unit.

Serf discovery

cluster/discovery/serf.go wraps the Serf library for automatic peer discovery:

type Config struct {
    NodeID            string
    GRPCAddr          string  // advertised in member metadata
    RaftAddr          string  // advertised in member metadata
    SerfAddr          string  // bind address
    SerfAdvertiseAddr string  // for NAT traversal
    JoinAddrs         []string
    EventBuffer       int
}

Each Serf member advertises its NodeID, GRPCAddr, and RaftAddr as member tags.

When a EventMemberJoin or EventMemberUpdate event is received and this node is the Raft leader, Node.addDiscoveredVoter calls n.raft.AddVoter(member.NodeID, member.RaftAddr). This means new nodes can join a cluster automatically without knowing the leader's address - they only need to know any existing Serf member's address.

SerfDiscovery.Members()

Returns []NodeInfo with the current known members, their gRPC and Raft addresses, and their Serf status.

Join via gRPC

When cfg.JoinAddr is set (and Serf is not handling join automatically), a gRPC Join request is sent to the target:

client.Join(ctx, &pbv1.JoinRequest{NodeId: nodeID, RaftAddr: raftAddr})

The target calls node.AddVoter(nodeID, raftAddr) on the Raft leader. If the target is not the leader, the Join call will still work as long as the target can forward or the caller retries.

Write path in cluster mode

The cluster gRPC server (grpc/cluster_server.go) intercepts Put and Delete:

1. Encodes the operation as a Command.
2. Calls raft.Apply(encodedCommand, timeout).
3. Waits for the future to resolve (consensus reached and FSM applied on the leader).
4. Extracts *FSMResult from the future's response.
5. Returns the result to the caller.

If the node is not the leader, raft.ErrNotLeader is returned and the client should retry against the leader.

Configuration reference

Go API Reference

Import path: github.com/teddymalhan/pallasdb/db

KV - key-value store

Opening a store

kv, err := db.NewKV("path/to/data",
    db.WithLogThreshold(2000),
    db.WithGrowthFactor(2.0),
    db.WithAutoCompact(true),
    db.WithCache(64<<20, 640000),  // 64 MiB cache, 640k counters
)
if err != nil {
    log.Fatal(err)
}
defer kv.Close()

Options

Point operations

// Get
val, ok, err := kv.Get([]byte("hello"))

// Set (upsert)
updated, err := kv.Set([]byte("hello"), []byte("world"))

// SetEx - explicit mode
updated, err := kv.SetEx([]byte("hello"), []byte("world"), db.ModeInsert)
updated, err := kv.SetEx([]byte("hello"), []byte("world"), db.ModeUpdate)
updated, err := kv.SetEx([]byte("hello"), []byte("world"), db.ModeUpsert)

// Delete
deleted, err := kv.Del([]byte("hello"))

Iteration

// Iterate all live keys
iter, cleanup, err := kv.IterAll()
defer cleanup()
for ; iter.Valid(); iter.Next() {
    fmt.Printf("%s = %s\n", iter.Key(), iter.Val())
}

Compaction

err := kv.Compact()

Flushes the memtable if it exceeds the threshold and merges adjacent SSTables if the size ratio triggers. Safe to call concurrently with reads and writes.

Close

err := kv.Close()

Waits for background goroutines (compaction thread, open transactions), closes the cache, and closes all open files.

KVTX - key-value transaction

tx := kv.NewTX()
defer tx.Abort()  // no-op if already committed

// Read
val, ok, err := tx.Get([]byte("key"))

// Write
updated, err := tx.Set([]byte("key"), []byte("val"))
updated, err := tx.SetEx([]byte("key"), []byte("val"), db.ModeInsert)
deleted, err := tx.Del([]byte("key"))

// Range scan
iter, err := tx.Range([]byte("a"), []byte("z"), false /* ascending */)
for ; iter.Valid(); iter.Next() {
    fmt.Printf("%s\n", iter.Key())
}

// Seek
iter, err := tx.Seek([]byte("prefix"))

// Commit
if err := tx.Commit(); err == db.ErrTXConflict {
    // retry
}

Nested transactions:

inner := tx.NewTX()
inner.Set(...)
inner.Commit()  // merges into parent tx.updates, not the store

DB - higher-level table database

DB wraps KV and adds schema management and SQL execution.

Opening

d, err := db.NewDB("path/to/data")
defer d.Close()

NewDB accepts the same KVOption functions as NewKV.

Schema definition

schema := &db.Schema{
    Table: "users",
    Cols: []db.Column{
        {Name: "id",   Type: db.TypeI64},
        {Name: "name", Type: db.TypeStr},
        {Name: "age",  Type: db.TypeI64},
    },
    Indices: [][]int{
        {0},    // primary key: id
        {2, 0}, // secondary index: (age, id)
    },
}

Row operations

row := schema.NewRow()
row[0] = db.Cell{Type: db.TypeI64, I64: 42}
row[1] = db.Cell{Type: db.TypeStr, Str: []byte("alice")}
row[2] = db.Cell{Type: db.TypeI64, I64: 30}

tx := d.NewTX()
defer tx.Abort()

updated, err := tx.Insert(schema, row)   // fails if id=42 exists
updated, err := tx.Upsert(schema, row)   // create or replace
updated, err := tx.Update(schema, row)   // fails if id=42 absent
deleted, err := tx.Delete(schema, row)   // deletes all index entries

ok, err := tx.Select(schema, row)        // fetch by primary key (row[0] must be set)

tx.Commit()

Range iteration

iter, err := tx.Seek(schema, row)  // forward scan from row's primary key
for ; err == nil && iter.Valid(); err = iter.Next() {
    r := iter.Row()  // []db.Cell
}

req := &db.RangeReq{
    StartCmp: db.OP_GE,
    StopCmp:  db.OP_LE,
    Start:    []db.Cell{{Type: db.TypeI64, I64: 10}},
    Stop:     []db.Cell{{Type: db.TypeI64, I64: 50}},
    IndexNo:  0,  // primary key index
}
iter, err := tx.Range(schema, req)

SQL execution

p := db.NewParser(`
    CREATE TABLE users (
        id int64,
        name string,
        age int64,
        PRIMARY KEY (id),
        INDEX (age)
    );
`)
stmt, err := p.parseStmt()
_, err = d.ExecStmt(stmt)

p = db.NewParser(`SELECT id, name FROM users WHERE id >= 1 AND id <= 100;`)
stmt, _ = p.parseStmt()
result, err := d.ExecStmt(stmt)
for _, row := range result.Values {
    fmt.Printf("id=%d name=%s\n", row[0].I64, row[1].Str)
}

SQLResult:

type SQLResult struct {
    Updated int      // rows affected by INSERT / UPDATE / DELETE
    Header  []string // column names for SELECT
    Values  []Row    // result rows for SELECT
}

UpdateMode

const (
    ModeUpsert UpdateMode = iota + 1  // insert or update
    ModeInsert                         // insert only (no-op if exists)
    ModeUpdate                         // update only (no-op if absent)
)

Error values

SortedKV interface

For advanced use, you can implement SortedKV to plug custom data sources into the merge iterator:

type SortedKV interface {
    EstimatedSize() int
    Iter() (SortedKVIter, error)
    Seek(key []byte) (SortedKVIter, error)
}

type SortedKVIter interface {
    Valid() bool
    Key() []byte
    Val() []byte
    Deleted() bool
    Next() error
    Prev() error
}

Benchmarks

Recorded benchmark results from an Apple M4 MacBook Air (arm64, 10 cores, Go 1.26.3).

Source: benchmarks/m4-macbook-air-results.txt, benchmarks/PallasDB-M4-Benchmark.md, benchmarks/performance-optimizations-2026-06-03.md

Summary results

All runs reported missing: 0 and errors: 0.

Benchmark phases

Each benchmark run executes the following sequential phases:

Detailed results

128-byte values, 2 million keys

populate:      19,993 ops/sec  (1m40s total)
compact:       12.7s
reopen:        890 µs
random_read:   26,588 ops/sec  (18.8s for 500k reads)
iterate_keys:  1,014,357 ops/sec
iterate_values: 974,720 ops/sec
data_dir_size: 324,396,366 bytes (~309 MiB)

1 KiB values, 500k keys

populate:      43,362 ops/sec  (11.5s total)
compact:       5.6s
reopen:        425 µs
random_read:   33,529 ops/sec  (8.9s for 300k reads)
iterate_keys:  911,829 ops/sec
iterate_values: 732,912 ops/sec
data_dir_size: 529,099,166 bytes (~505 MiB)

16 KiB values, 50k keys

populate:      12,281 ops/sec  (4.1s total)
compact:       3.7s
reopen:        222 µs
random_read:   5,364 ops/sec   (18.6s for 100k reads)
iterate_keys:  322,315 ops/sec
iterate_values: 141,650 ops/sec
data_dir_size: 820,910,006 bytes (~783 MiB)

Performance optimizations (2026-06-03)

Two optimizations were applied after the initial benchmark run, resulting in significant improvements for large-value workloads:

1. Binary search key-only reads

Previously, compareKeyAt read both key and value bytes during binary search. The fix reads only the key during comparison, fetching the value separately only after the binary search confirms a match.

2. Fast-path append for ordered writes

When a transaction's updates are ordered after all existing memtable keys and no concurrent transactions are open, the commit appends directly to the memtable slices instead of performing a full merge. This eliminates O(n) work for sequential-key batch inserts.

Before vs. after (16 KiB values):

Running benchmarks

Smoke test (fast verification)

go run ./cmd/pallasdb local benchmark \
  --data-dir /tmp/smoke \
  --reset --keys 20000 --value-size 128 \
  --batch-size 500 --read-ops 20000 \
  --scan-limit 20000 --compact \
  --format text

Full scaled benchmark

go run ./cmd/pallasdb local benchmark \
  --data-dir /tmp/bench-v128 \
  --reset --keys 2000000 --value-size 128 \
  --batch-size 1000 --read-ops 500000 \
  --compact --format text \
  --output benchmarks/results.txt

Verifying the benchmark implementation

go test ./cmd/pallasdb -run 'TestLocalBenchmark'
go test ./db ./cmd/pallasdb

Environment

All recorded results were produced on: