How to Build a Distributed KV Store with Full ACID Guarantees

Database Evolution

The talk classifies database development into three stages: (1) traditional SQL/RDBMS with limited horizontal scalability; (2) sharding‑oriented systems (NoSQL, middleware) that improve scalability but sacrifice full transactional guarantees; and (3) NewSQL, which aims to retain single‑node performance while providing distributed consistency, scalability, and full ACID support.

JProxy Sharding and Seamless Migration

JProxy intercepts MySQL protocol traffic, parses incoming statements, and automatically splits them into multiple shards. Each shard is routed to a specific MySQL instance according to a routing table stored in a central JManager node. The routing table is synchronized across proxies using a two‑phase comparison protocol.

To add capacity, shards can be migrated without downtime:

Submit a transfer request that records source and destination nodes.

Copy a full snapshot of the source shard to the target (MySQL snapshot).

Track incremental writes on the source while the snapshot is being transferred.

When the incremental logs are consistent, switch the routing entry so new traffic is directed to the target.

Notify all proxies of the updated routing, completing the migration with zero impact on live queries.

Limitations of Sharding‑Only Approaches

While JProxy solves data partitioning and migration, it does not provide transactional isolation or strong consistency across shards. This mirrors a common limitation of many NoSQL systems that rely on passive or active replication without coordinated commit protocols.

Fundamental Requirements for ACID in a Distributed KV Store

Snapshot isolation implemented via a two‑phase commit (2PC) that atomically commits or aborts a transaction across all involved shards.

Timestamp‑based versioning: each write receives a globally ordered timestamp (or logical clock) because simple per‑node IDs cannot order updates across nodes.

Deterministic lock ordering: locks are acquired in a fixed key order (e.g., lexical order) to prevent deadlocks when multiple transactions contend for overlapping keys.

Distributed Transaction Example (Money Transfer)

The presentation demonstrates a transfer of funds from account Bob to Joe using versioned records, per‑key locks, and a two‑phase commit.

Acquire a lock on Bob 's balance, create a new version (e.g., balance 3 with timestamp 7).

Acquire a lock on Joe 's balance, add the transferred amount, also creating version 7.

Commit: mark both new versions as visible (write‑ahead log entry), then release the locks.

This flow shows how snapshot isolation, timestamp ordering, and ordered locking together guarantee atomicity and isolation across shards.

Consensus and Replication

Strong consistency is achieved by electing a leader (Raft‑style). The leader serializes all write operations into a replicated log. Followers copy the log entries before applying them to their local state. This approach guarantees linearizable reads but incurs additional network latency and complicates node‑restart recovery.

Practical Performance Considerations

Wide tables with many columns can degrade throughput because each column translates to an additional key in the KV layer. One mitigation strategy is to offload heavy analytical queries to a dedicated search engine or columnar store, keeping the KV layer focused on transactional workloads.

Layered Architecture Overview

The proposed stack consists of:

Range/Consensus layer : provides ordering (e.g., Raft) and range partitioning.

Node/Store layer : hosts one or more KV partitions.

Monolithic Map layer : aggregates KV partitions into a logical namespace.

Distributed KV layer : implements Get, Put, ConditionalPut, Scan, and Delete with snapshot isolation.

SQL layer : translates full SQL semantics into KV operations, delivering complete ACID transactions.