Skip to content
coolstack-coderPublic

About

A Fault Tolerant Distributed Key Value Database

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

Β 

History

15 Commits

Folders and files

Repository files navigation

πŸ›‘οΈ AegisDB

A fault-tolerant, sharded, linearizable key-value database, built from scratch in Go.

Raft consensus per shard Β· consistent-hash partitioning Β· write-ahead log + snapshots Β· automatic failover and crash recovery

ci Go deps license

AegisDB lab: killing a leader, automatic failover, WAL recovery

▢️ Watch the full 2-minute demo (MP4): kill -9 a leader, recovery from the WAL, a network partition, then a chaos monkey. Over 200k writes acknowledged, 0 lost.


Why this exists

Every serious backend eventually hits the same wall. One database server is a single point of failure, and the moment you add replicas you have to answer hard questions:

Real problem What goes wrong in practice How AegisDB handles it
A server crashes Downtime, or a manual failover at 3am Raft elects a new shard leader in ~1s, automatically
Split brain Two nodes both think they are primary and accept conflicting writes One leader per term, majority quorums, CheckQuorum step-down
Lost acknowledged writes The primary acks, then dies before replicating (classic async replication) A write is acked only after a majority has it fsynced
Stale reads A deposed leader keeps serving old data ReadIndex: the leader confirms with a quorum (or a safe lease) before reading
Crash mid-write Torn or corrupt log tail, an unbootable node CRC32-C on every WAL record; the torn tail is detected and truncated
Retries double-apply A client times out, retries, and money moves twice Client sessions + sequence numbers give exactly-once semantics
One machine can't hold the load Vertical scaling hits a ceiling Data is split into shards on a consistent-hash ring; each shard has its own leader
Flaky node rejoins A partitioned node bumps its term and forces needless elections PreVote: it must prove it could win before it disrupts anyone

The full problem analysis, with the papers and postmortems behind each row (Dynamo 2007, Raft 2014, the DynamoDB 2022 USENIX paper, Jepsen's etcd and MongoDB analyses), is in docs/RESEARCH.md.

What's inside

  • Raft from scratch (internal/raft): leader election, log replication, persistence, plus the extensions production systems actually rely on:
    • PreVote and CheckQuorum with leader stickiness (no disruptive elections, no zombie leaders)
    • Conflict-term fast backtracking, so a lagging follower is repaired in O(terms) round trips instead of O(entries)
    • Snapshots + InstallSnapshot for log compaction and catching up nodes that fell far behind
    • Linearizable reads via ReadIndex, with a leader-lease fast path (bounded by the election timeout, with clock-drift margin)
    • Group commit on the leader: proposals don't wait on each other's fsync
  • Multi-Raft sharding (internal/cluster). Keys map to shards via a consistent-hash ring (64 vnodes/shard). Shards map to replicas via rendezvous hashing, so placement is deterministic with zero coordination.
  • Write-ahead log (internal/wal): length-prefixed, CRC32-C checksummed records, torn-tail truncation, atomic rewrite (temp file β†’ fsync β†’ rename β†’ fsync dir).
  • KV state machine (internal/kv): versioned values, compare-and-swap, TTL (expiry uses the leader's log timestamp so replicas stay deterministic), and an exactly-once session table.
  • Smart routing: hit any node. Requests are forwarded to the right shard leader, with a hop limit and no request storms when a shard is leaderless.
  • Fault injection built in: every node can be told to drop traffic to and from peers, add latency, or lose packets (POST /admin/faults), so partitions are testable without iptables.
  • Observability: Prometheus /metrics (request latency histograms, term, commit/apply lag, elections, WAL size) and a JSON /v1/status.
  • Go SDK (client) with retries, endpoint rotation and idempotent writes. CLI with a built-in benchmark.
  • The Lab (cmd/aegis-lab): runs a real 5-process cluster with a live dashboard, kill/partition buttons, a chaos monkey, and a self-verifying load generator.

Zero runtime dependencies. Only the Go standard library. The single external module, porcupine, is test-only.

Architecture

flowchart LR
    C[Client / SDK / aegisctl] -->|any node| N1
    subgraph N1[node n1]
      R1[router] --> S0a[s00 raft β˜…]
      R1 --> S3a[s03 raft]
    end
    subgraph N2[node n2]
      R2[router] --> S0b[s00 raft]
      R2 --> S3b[s03 raft β˜…]
    end
    subgraph N3[node n3]
      R3[router] --> S0c[s00 raft]
      R3 --> S3c[s03 raft]
    end
    R1 -. forward to shard leader .-> R2
    S0a <-->|AppendEntries / votes| S0b & S0c
    S3b <-->|AppendEntries / votes| S3a & S3c
Loading

Each shard is an independent Raft group (β˜… = current leader). A node hosts several shards and leads some of them, so write load spreads across the cluster. A background balancer hands off leadership when a node leads more than its fair share.

Write path: client β†’ any node β†’ router finds shard = ring(hash(key)) β†’ forwards to the shard leader β†’ leader appends to its log and replicates β†’ once a majority has fsynced, the entry commits and is applied β†’ reply.

Read path (linearizable): leader records its commit index β†’ confirms it is still leader (valid lease, or a heartbeat round with a majority) β†’ waits until applied β‰₯ that index β†’ reads locally. ?consistency=stale reads any replica without the round trip.

Deeper dive into every component, plus the correctness argument: docs/DESIGN.md.

Quick start

Requires Go 1.23+.

git clone https://github.com/coolstack-coder/AegisDB-A-Fault-Tolerant-Distributed-Key-Value-Database.git aegisdb
cd aegisdb
make build        # bin/aegisd, bin/aegisctl, bin/aegis-lab
make lab          # 5 nodes + dashboard on http://localhost:8080

Then, in another terminal:

./bin/aegisctl put user:42 '{"name":"ada"}'
./bin/aegisctl get user:42
./bin/aegisctl put session:abc token --ttl 30s
./bin/aegisctl cas lock:job 0 worker-7          # create-if-absent lock
./bin/aegisctl scan user:
./bin/aegisctl status                           # who leads what, per shard
./bin/aegisctl bench --duration 15s --workers 32

Or with Docker:

docker compose up --build
docker compose kill n2       # the cluster keeps serving

HTTP API

Method Path Notes
GET /v1/kv/{key} linearizable; ?consistency=stale for any-replica reads
PUT /v1/kv/{key} body = value; ?ttl=30s, ?if_version=N (CAS, 0 = must not exist)
DELETE /v1/kv/{key} supports ?if_version=N
GET /v1/scan?prefix=p&limit=n fans out to every shard
GET /v1/status, /v1/topology, /metrics introspection
POST /admin/faults {"blocked":["n2"],"delay_ms":50,"drop_rate":0.1}
POST /admin/stepdown give up leadership (?shard=N for one shard)

Send X-Aegis-Client-ID + X-Aegis-Seq headers to make writes exactly-once across retries. The Go client does this for you.

db := client.New([]string{"127.0.0.1:7101", "127.0.0.1:7102"})
w, _ := db.Put(ctx, "cart:9", []byte("3 items"))
_, err := db.Put(ctx, "cart:9", []byte("4 items"), client.IfVersion(w.Version)) // optimistic concurrency

How it's tested

Correctness evidence matters more than feature count, so most of the effort went here.

Test What it proves
internal/raft (simulated network, 6.824-style) election safety (never 2 leaders in a term), re-election, PreVote stops disruption, no progress without quorum, recovery after full-cluster crash, snapshot catch-up, ReadIndex refuses reads when isolated
TestChaos 5 nodes, 25 rounds of random crashes, restarts and partitions on a lossy, reordering network. Every acknowledged command is present exactly once on every node
test/jepsen TestLinearizableUnderFaults real HTTP servers with real WALs, 10 concurrent clients, a nemesis that crashes, restarts, partitions and forces leader changes. The full history (~75,000 ops) is checked with the Porcupine linearizability checker
test/jepsen API tests CAS, TTL, scan, durability across a full-cluster restart, idempotent retries
internal/wal torn tail truncation, bit-flip corruption stops replay, atomic rewrite
Lab load generator every read is checked against the last acknowledged write, live, during chaos
make test     # everything (~45s)
make race     # same, with the race detector

Sample output from the linearizability run:

nemesis: [crash n5 step down all leaders heal partition [n5 n1] | [n2 n3 n4] ... crash n2 heal]
75493 operations recorded (17 writes with unknown outcome)
history is linearizable
--- PASS: TestLinearizableUnderFaults (17.02s)

Performance

On a MacBook (Apple Silicon), 5 local processes, 6 shards, RF=3, fsync on every commit, 32 concurrent clients, 50/50 read/write, 128-byte values:

115606 ops in 8.004s = 14444 ops/s (0 errors)

     op  count     p50     p90      p99    p99.9
   read  57699   740Β΅s  4.18ms  11.04ms  24.08ms
  write  57907  1.41ms  5.87ms  13.64ms  25.87ms

Failover: when a leader is kill -9ed, its shards elect a new leader in ~1 second (300ms base election timeout plus detection). Clients see slower requests during that window, not errors, because the SDK retries idempotently.

These are laptop numbers over HTTP/JSON. Read them as a demonstration that the design isn't naive, not as a benchmark claim.

Design decisions & trade-offs

  • CP, not AP. During a partition, the minority side refuses writes rather than accept conflicting ones. That is the right call for a system of record (DynamoDB itself uses a leader per partition, not Dynamo-style sloppy quorums). Losing 2 of the 3 replicas of a shard makes that shard unavailable. Other shards keep serving.
  • Raft per shard (Multi-Raft) instead of one global log: independent failure domains and write parallelism, the same shape as TiKV, CockroachDB and DynamoDB.
  • HTTP/JSON transport. It's easy to debug with curl and fast enough for this scale. A binary protocol and batching across groups would be the first optimization.
  • Leases are optional and conservative. A lease is 75% of the election timeout, measured from when the heartbeat was sent. Nodes also refuse pre-votes for one election timeout after booting, so a fast restart can't shorten a live lease.
  • In-memory state machine. The dataset must fit in RAM, and durability comes from the WAL + snapshots. An LSM engine is the natural next step.

Known limitations (honest list)

  • Static membership: no adding or removing nodes at runtime (no joint consensus yet)
  • Shards don't split or merge automatically
  • Snapshots are sent in one RPC (fine for MBs, not GBs)
  • Client sessions are never garbage-collected (bounded by client concurrency)
  • No authentication or TLS

Roadmap

  • Membership changes (single-server or joint consensus) and a placement-driver shard
  • Shard splitting for hot keys / hot ranges (the DynamoDB "split for heat" idea)
  • LSM-tree storage engine (memtable β†’ SSTables, bloom filters, compaction)
  • Heartbeat coalescing across Raft groups; gRPC/binary transport
  • Watch API (stream changes on a key prefix)

Project layout

cmd/aegisd        the database server
cmd/aegisctl      CLI + benchmark
cmd/aegis-lab     local cluster supervisor + live dashboard
client/           Go SDK
internal/raft     consensus (node.go, storage.go, types.go)
internal/wal      write-ahead log
internal/kv       replicated state machine
internal/cluster  hash ring + replica placement
internal/server   routing, HTTP API, metrics, admin
internal/transport raft RPC over HTTP + fault injection
internal/simnet   in-memory lossy network for raft tests
test/jepsen       real-cluster fault + linearizability tests
docs/             design notes, research, demo video

References

  • Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm (USENIX ATC 2014), and Ongaro's PhD thesis (PreVote, ReadIndex, leases)
  • DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007)
  • Elhemali et al., Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service (USENIX ATC 2022)
  • Kingsbury, Jepsen analyses of etcd 3.4.3 and MongoDB 4.2.6
  • MIT 6.5840 (6.824) Distributed Systems labs
  • Athalye, Testing Distributed Systems for Linearizability (Porcupine)

License

MIT

About

A Fault Tolerant Distributed Key Value Database

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages