The AetherStore Challenge: A Long-Horizon Systems Engineering Benchmark for Frontier AI

Prompt

[ROLE & CONTEXT] You are a Principal Distributed Systems Engineer and Kernel/Performance Architect. You have been tasked with designing and implementing the foundational core of "AetherStore": an ultra-low-latency, distributed, multi-version transactional key-value storage engine engineered for bare-metal deployment on NVMe-oF and 100GbE RoCEv2 infrastructure. [THE PROBLEM ENVIRONMENT & CONSTRAINTS] - Infrastructure: Bare-metal x86_64, non-uniform memory access (NUMA) architecture (2 sockets, 64 cores/socket), PCIe Gen 5 NVMe drives, RoCEv2 (RDMA over Converged Ethernet). - Performance SLAs: - Write path p99 latency < 1.5ms under 500,000 distributed IOPS. - Read path p99 latency < 200µs for point lookups. - Zero allocations on the critical hot path (zero dynamic heap allocation inside request handlers). - Network & Fault Assumptions: - Asynchronous, untrusted network with arbitrary packet delays, reordering, and asymmetric partitions (Node A can send to Node B, but Node B cannot send to Node A). - Hard clock skew: Wall clocks drift by up to ±200ms across nodes. No specialized hardware (no TrueTime/GPS atomic clocks). - Disk failures include silent data corruption (bit rot) and transient fsync stalls exceeding 10 seconds. - External Dependencies: ZERO external third-party consensus orchestrators or storage engines (no ZooKeeper, etcd, RocksDB, Kafka, or Raft crates/libraries). All state machines and engines must be designed from scratch. --- ### MANDATORY DELIVERABLES You must produce a mathematically rigorous, fully detailed technical design and implementation specification covering the 5 modules below. Do NOT summarize, skip edge cases, or output pseudocode with comments like "// implement logic here". Provide concrete, production-grade solutions. --- #### MODULE 1: CACHE-AWARE, LOCK-FREE STORAGE ENGINE (LOCAL NODE) 1. Memory & Disk Architecture: - Detail the memory layout and data structures for an in-memory MVCC MemTable optimized for NUMA-local execution and cache-line alignment (preventing false sharing). - Design an append-only, zero-copy Write-Ahead Log (WAL) that leverages Linux `io_uring` with fixed registered buffers (`IORING_REGISTER_BUFFERS`) and poll-mode (`IORING_SETUP_SQPOLL`). 2. Concurrency & Synchronization: - Define a single-producer, multi-consumer (SPMC) or lock-free ring-buffer pipeline bridging network ingestion to NVMe flush. Specify the exact memory fences/orderings (`acquire`, `release`, `relaxed`, `seq_cst`) required at each state transition. 3. Compaction & Tombstone Reclamation: - Describe the concurrent SSTable/LSM-tree compaction protocol that allows snapshot reads to continue unblocked without memory leaks or pointer degradation (dealing with the ABA problem and safe memory reclamation via Epoch-Based Reclamation or Hazard Pointers). --- #### MODULE 2: REPLICATION PROTOCOL UNDER ASYMMETRIC PARTITIONS 1. Multi-Raft / Multi-Paxos Core: - Design a Multi-Group consensus protocol where log entries are sharded across disjoint ranges. - Address the **Asymmetric Partition Problem**: Suppose Node A is partitioned such that it can receive heartbeats from Leader L, but Leader L cannot receive A's acks. Describe the failure detection and election safety mechanisms that prevent continuous term disruption without sacrificing liveness. 2. Lease Reads Without Atomic Clocks: - Formulate a provably safe Leader Lease mechanism for local reads using **Hybrid Logical Clocks (HLC)** despite up to ±200ms physical clock drift. Provide the mathematical inequality that governs lease renewal, read expiration, and safe bounds against silent clock jumps. 3. Joint Consensus Dynamic Membership Changes: - Formalize the two-phase state transition matrix for migrating a shard from configuration $C_{old}$ to $C_{new}$ (via $C_{old,new}$) without violating the state machine safety invariant. --- #### MODULE 3: DISTRIBUTED TRANSACTIONS & CONCURRENCY CONTROL 1. Distributed Snapshot Isolation & 2-Phase Commit (2PC): - Design a decentralized transaction coordinator using HLC timestamps to provide Snapshot Isolation (SI) with Write-Snapshot Conflict resolution. 2. Failure Scenarios & Non-Blocking Recovery: - What happens when the Transaction Coordinator crashes halfway through broadcasting `Commit` decisions in Phase 2? Specify the algorithmic protocol an arbitrary participant must execute to safely determine the fate of the transaction (Commit or Abort) without blocking reads or creating distributed deadlocks. 3. Deadlock Resolution: - Specify a deterministic distributed deadlock prevention scheme (e.g., wound-wait or wait-die adapted for HLC) that accounts for out-of-order arrival of lock requests across network partitions. --- #### MODULE 4: FORMAL INVARIANTS & FAILURE MODE MATRIX 1. Formal Invariants: - Define at least 3 global safety invariants (e.g., Linearizability, Atomicity, Internal Consistency) using strict mathematical or TLA+-style logic notation. 2. Failure Mode State Matrix: - Provide an exhaustive markdown table with the following columns: `| Failure Scenario | Immediate Detection Mechanism | Consensus/Quorum State | Transaction Impact | Recovery & Re-convergence Procedure |` - Scenarios to explicitly include: 1. Gray network failure (95% packet drop + 500ms jitter). 2. Asymmetric network partition isolating the Raft leader from a minority follower. 3. Concurrent crash of the Transaction Coordinator and one Prepared participant during 2PC. 4. Sudden backward physical clock jump of 150ms on a leaseholder node. 5. Corrupted partial block write in the WAL during an ungraceful power loss. --- #### MODULE 5: PRODUCTION-GRADE REFERENCE IMPLEMENTATION Provide a fully written, compilable, and syntactically valid **Rust (or modern C++20)** implementation of the **Hybrid Logical Clock (HLC)** and the **Concurrent Lock-Free MVCC Version Resolver**. Requirements for the code: 1. Complete struct/class definitions, atomic memory operations with explicit `std::sync::atomic::Ordering` (or `std::memory_order`). 2. Implemented collision handling, timestamp advancement on send/receive events, and bounded physical drift verification. 3. A complete lookup function: `fn read_at_timestamp(key: &Key, read_hlc: HLC) -> Option<Value>` that resolves versions from an atomic linked-list or array of version records, correctly handling concurrent writers, tombstone records, and uncommitted transactions without using global mutexes. 4. ABSOLUTELY NO pseudocode, NO truncated blocks, NO `// TODO: left as exercise`. The code must be production-ready and fully written out.