Ionia: High-Performance Distributed Write-Optimized Key-Value Stores

1. B-Tree (Traditional)

Structure:

        [50|100]
       /    |    \
[20|30]  [60|80]  [110|120]
 /  |  \   /  |  \   /  |  \
leaf leaf leaf leaf ...

Write Operation Flow:

1. Search: Traverse root → leaf (requires random disk reads).
2. Update: Insert key into leaf.
3. Split: If node is full, split and propagate up (requires multiple random disk writes).

Characteristics:

• Symmetric Performance: Reads and writes are roughly equally fast/slow.
• Bottleneck: Limited by Random IOPS (e.g., ~600K IOPS on SSD).

2. LSM Tree (Log-Structured Merge Tree)

Core Insight: Convert random writes into sequential writes to maximize throughput.

Structure:

• Memory Tier: MemTable (Sorted, ~256 MB).
• Disk Tier (SSTables):
  • Level 0: ~256 MB
  • Level 1: ~2.5 GB
  • Level 2: ~25 GB ...

Write Operation Flow:

1. Buffer: Write to MemTable (RAM) + Append to Write-Ahead Log (Sequential).
2. Flush: When MemTable fills, flush to disk as SSTable (Sequential write, 3-7 GB/s).
3. Merge: Background process merges sorted files to clean up invalid data.

Characteristics:

• Asymmetric Performance: Excellent write throughput (sequential) but reads can be slower (checking multiple levels).
• Write-Optimized Key-Value (WO-KV): Prioritizes write speed over read speed.

Background & Motivation

• WO-KV Speed: Single-node WO-KV stores have massive write throughput.
• Replication Bottleneck: Traditional replication protocols kill this performance because:
  • They apply writes sequentially on a single thread to ensure identical replicas.
  • They require coordination for write ordering (high latency).
  • Followers are unused (wasted resources).
• The Goal: An ideal protocol must preserve WO-KV write performance (throughput/latency) while ensuring consistency.

Shortcomings of Existing Systems

1. Trade-offs: Systems usually force a choice between scalable reads (low latency) vs. availability.
2. Batching Latency: Systems like CBASE/Eve use multi-threading but rely on large batches to find concurrency, increasing latency.
3. Sequential Write Bottlenecks: Systems using commutativity or network ordering often still suffer from sequential write limitations.
4. Read Latency: Systems routing reads to the leader (Gaios, Gnothi) suffer from high RTT.

Core Philosophy

1. Parallel Execution: Concurrently execute non-conflicting writes to avoid inconsistencies.
2. Deferred Ordering: Guarantees durability immediately (1 RTT) but defers strict ordering and execution to the background.
3. Decoupling Locality:
   • Traditional In-Memory bottleneck: Network.
   • WO-KV bottleneck: SSD Random IOPS.
   • Insight: Reads can scale non-locally as long as validation checks are done in-memory without hitting the SSD.
4. Client-Side Consistency: To solve stale reads at followers, the client performs the final validity check using metadata from the leader.

A. Write Operations (Fast Durability)

Ionia separates durability from execution to achieve speed.

B. Read Operations (Scalable & Consistent)

Failures and View Changes

• Recovery: Replicas restore Consensus and Durability logs from the leader.
• Why Supermajority?
  • Standard majority isn't enough for the Durability Log because writes are uncoordinated (Log A: [a,b], Log B: [b,a]).
  • Supermajority Quorum: f + ⌈f/2⌉ + 1.
  • Ensures that after f failures, at least one remaining replica has the correct order of writes.
• View Change Process: New leader collects logs, builds a dependency DAG from pairwise comparisons, topologically sorts it to finalize order, and enters the new view.

Correctness Proof Sketch