SQL SQL In Depth
0%
Guided SQL & Engine Coding Lab

Consistent-Hash Shard Router with Partition Pruning & Scatter-Gather

A distributed SQL proxy router implementing FNV-1a consistent hash ring routing, single-shard vs scatter-gather query planning, LSN-fenced read-your-writes replica selection, and distributed Top-K merge.

~45 min Advanced Lessons: Hands-On Build: Consistent-Hash Shard Router with Partition Pruning & Scatter-Gather, Single-Leader Replication: Physical WAL Streaming vs Logical Replication & Sync/Async, Scaling Reads with Replicas: Read-Your-Writes, Monotonic Reads & Lag Anomalies, Automated High-Availability Failover, Split-Brain Hazards & Fencing Tokens, Declarative Table Partitioning (Range, List, Hash) & Instant Retention Drops, Horizontal Sharding (Vitess / Citus): Shard Keys, Consistent Hashing & Scatter-Gather
Guided Algorithm Coding Lab 0/4 Steps Completed

Code & Verify SQL & Storage Engine Invariants in the Browser Workbench

Complete 4 progressive algorithmic steps with guided hints in C++20 (WebAssembly), TypeScript, or JavaScript against automated unit test assertions — zero local setup required.

Architectural Overview

A distributed SQL proxy router implementing FNV-1a consistent hash ring routing, single-shard vs scatter-gather query planning, LSN-fenced read-your-writes replica selection, and distributed Top-K merge.

In production relational and analytical database systems—spanning PostgreSQL, SQLite, MySQL/InnoDB, and DuckDB—understanding how query clauses, schema constraints, index structures, and storage engines execute under the hood separates surface-level query authors from staff-level database engineers. This capstone build lab guides you through implementing Consistent-Hash Shard Router with Partition Pruning & Scatter-Gather from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: FNV-1a Virtual-Node Consistent Hash Ring Routing

  • Core Database Concept: Mapping Shard Keys Around a 32-Bit Hash Ring via Binary Search
  • Target Module: index.js (ShardedQueryRouter.routeShardKey)
  • Engineering Specification: Implement routeShardKey(shardKey) to hash shardKey with FNV-1a and binary-search the sorted virtual-node ring, wrapping around to index 0 when keyHash exceeds the last ring token.
  • Implementation Hint: Hash shardKey and pick the first ring entry with ringEntry.hash >= keyHash (wrapping around to index 0).
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Single-Shard Pruning vs Scatter-Gather Planner

  • Core Database Concept: Avoiding Cross-Shard Fan-Out When the Partition Key Is Specified
  • Target Module: index.js (ShardedQueryRouter.planQuery)
  • Engineering Specification: Implement planQuery(query) to return { mode: "SINGLE_SHARD" | "SCATTER_GATHER", targetShards }.
  • Implementation Hint: If query.shardKey is present, target [routeShardKey(query.shardKey)]; otherwise target all physical shards.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: Distributed Scatter-Gather Top-K Coordinator Merge

  • Core Database Concept: Pushing ORDER BY + LIMIT K to Each Shard and Merging Sorted Streams at the Proxy
  • Target Module: index.js (ShardedQueryRouter.scatterGatherTopK)
  • Engineering Specification: Implement scatterGatherTopK(shardDataMap, sortCol, k) to pull at most k pre-sorted tuples from each shard and merge them into the exact global top-kk.
  • Implementation Hint: Take top k from each target shard, combine candidates, sort globally by sortCol DESC, and slice(0, k).
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: LSN-Fenced Read-Your-Writes Replica Selector

  • Core Database Concept: Routing Follower Reads Only to Replicas Caught Up Past the Client’s High-Water Mark LSN
  • Target Module: index.js (ShardedQueryRouter.selectReadNode)
  • Engineering Specification: Implement selectReadNode(replicas, requiredLsn) to select the lowest-latency replica whose replayLsn >= requiredLsn, falling back to "PRIMARY" when all replicas lag.
  • Implementation Hint: Filter replicas with replica.replayLsn >= requiredLsn; pick lowest-latency caught-up replica or fall back to "PRIMARY".
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Distributed SQL, Partitioning & Sharding
  • Difficulty & Time Budget: Advanced (~45 minutes)
  • Key Architectural Highlights:
    • Deterministic FNV-1a virtual-node consistent hash ring routing tenant keys with minimal rebalancing movement
    • Single-shard pruning when tenant_id is constrained vs parallel Scatter-Gather merge across shards
    • Read-Your-Writes causal consistency router selecting replicas with replayLsn >= clientWriteLsn
  • Core Primitives & Tags: Consistent Hashing, Shard Router, Scatter-Gather, Read-Your-Writes, Partition Pruning

Related Curriculum Units

Production Database Context & Verification

This from-scratch relational engine component is engineered with zero external dependencies and deterministic verification harnesses. Every internal database invariant—from three-valued logic (TRUE / FALSE / UNKNOWN), referential integrity, and fan-out-free join pre-aggregation to B+Tree page splits, MVCC snapshot visibility (xmin / xmax), slotted-page compaction, and ARIES write-ahead log crash recovery—is asserted directly in test.js. Use the interactive browser workbench above to complete the 4 guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.