Linearizability, Raft, and CB‑SQL Consistency: Range Lease and Node Lease Optimizations

When discussing distributed systems, the CAP theorem tells us that consistency, availability, and partition tolerance cannot be simultaneously guaranteed; the "C" in CAP refers to linearizability (strong consistency). The article begins by defining linearizability and illustrating it with a real‑world example where two clients observe different outcomes of a live sports broadcast.

From a client’s perspective, linearizability requires that operations appear to execute atomically on a single logical copy, ensuring that once a new value is observed, all subsequent reads return that value. The article lists three client‑side constraints that must hold for a system to be linearizable.

The Raft consensus algorithm is introduced as a strong‑consistency protocol with three roles (Leader, Candidate, Follower). While Raft guarantees linearizability for writes, reads are more complex due to leader changes and possible split‑brain scenarios. Three Raft‑based read methods are described:

Raft log read – every read is treated like a write, requiring log replication and incurring high latency.

ReadIndex – the leader validates its leadership via a heartbeat before reading, avoiding log replication but still adding network overhead and risking stale data.

Lease Read – the leader leases its authority for a short period, eliminating heartbeat checks and improving throughput, though it depends on tightly synchronized clocks.

CB‑SQL adopts Raft for strong consistency across range replicas. To support consistent reads, CB‑SQL introduces a range lease, but the naive approach creates excessive Raft log traffic as the number of ranges grows.

To mitigate this, CB‑SQL adds a node‑level lease (Node lease) stored in a Node liveness table. A range lease is considered valid if the hosting node’s lease is still active, the epochs match, and the lease timeout exceeds the request timestamp plus the maximum clock offset. This design reduces the frequency of lease renewals because a range only needs to renew its lease when a client accesses it, not periodically.

When a node fails or a lease expires, CB‑SQL triggers a lease transfer, ensuring that the new lease holder applies the lease update via Raft before becoming active, thus preserving data consistency. The article concludes by highlighting the economic reasoning behind these engineering choices, emphasizing trade‑offs between latency, throughput, and system overhead.