Scratch DB — A Fault-Tolerant Distributed SQL Database

Scratch DB is a miniature distributed SQL database inspired by CockroachDB and etcd, engineered from scratch with a layered architecture ranging from LSM-tree binary storage to Raft consensus, MVCC snapshot isolation, and chaos fault injection.

---

🏛 Architecture Diagram

                    ┌──────────────┐
                    │ SQL Client   │
                    └──────┬───────┘
                           │
                    ┌──────▼───────┐
                    │ Query Parser │
                    └──────┬───────┘
                           │
                    ┌──────▼───────┐
                    │ Query Planner│
                    └──────┬───────┘
                           │
              ┌────────────▼────────────┐
              │ Distributed KV Layer    │
              └────────────┬────────────┘
                           │
          ┌────────────────┼────────────────┐
          ▼                ▼                ▼
      ┌────────┐       ┌────────┐       ┌────────┐
      │ Node 1 │◄─────►│ Node 2 │◄─────►│ Node 3 │
      │ Leader │       │Follower│       │Follower│
      └────────┘       └────────┘       └────────┘
           │                │                │
           └────────────┬───┴────────────────┘
                        ▼
                  WAL / Storage

---

⚡ Features & Progressive Phases

Phase 1 — Storage Engine (LSM-Tree + WAL)

• Write-Ahead Logging (WAL): Binary append-only log format with CRC32 checksums for record integrity and deterministic crash recovery.
• MemTable: In-memory sorted skiplist dictionary with byte size threshold tracking.
• SSTables: Block-based disk files with sparse index binary search, bloom filter lookup, and tombstone handling.
• Compaction: Multi-way merge sorting engine consolidating SSTables and pruning deleted keys.

Phase 2 — SQL Query Engine

• Lexer & Recursive Descent Parser for ANSI SQL subset.
• Support for: CREATE TABLE, INSERT, SELECT, UPDATE, DELETE, WHERE, ORDER BY, GROUP BY, JOIN.
• Relational query execution planner mapping SQL rows to byte key-value schemas (table_name/primary_key).

Phase 3 — Transactions & Concurrency Control

• Multi-Version Concurrency Control (MVCC): Versioned key format key@commit_timestamp.
• Snapshot Isolation: Point-in-time read consistency against logical clock timestamps.
• First-Committer-Wins: Write-write conflict detection automatically aborting conflicting concurrent transactions.

Phase 4 & 5 — Raft Distributed Consensus & Fault Tolerance

• Raft Finite State Machine: Leader elections, randomized election timeouts, candidate votes, heartbeats, and AppendEntries log replication.
• Request Routing: Transparent query forwarding to current Raft cluster leader.
• Chaos Injection Framework:
  • Node Crash & Recovery.
  • Network Partitions (Split-Brain isolation).
  • Packet Loss, Packet Delay (Jitter), Duplicate Messages.
  • Disk Corruption simulation.
• Failover Guarantee: 3-node cluster seamlessly continues serving reads and writes after leader crash.

---

🚀 Quickstart & Usage

1. Run Unit & Fault Tolerance Tests

PYTHONPATH=. pytest

2. Run Progressive Phase Demo

python3 run_demo.py

3. Launch Interactive Command Line SQL REPL

python3 scratchdb/api/cli.py

4. Start HTTP Gateway & Control Center Web UI

python3 scratchdb/api/server.py

Open http://localhost:8080 in your browser to view cluster topology, test live SQL queries, and inject network chaos with one click.