KCensus improves geo-replication latency with optimized fast paths
KCensus: Synthesizing Latency-Optimal Consensus Fast Paths (Extended Version)
Distributed, Parallel, and Cluster Computing
Summary
Systems that copy data across distant locations need to agree on changes quickly to keep everything consistent. Usually, special shortcuts called fast paths help reduce the waiting time when there are no problems, but existing shortcuts only work well in certain situations. The authors looked deeper at how information about decisions spreads across the network and created KCensus, a tool that finds the best shortcuts for different setups. They built a key-value store using KCensus and showed it runs faster than other methods by up to 16%.
What this means in practice
- •For cloud infrastructure engineers: Create geo-replicated storage solutions with lower latency by automatically designing optimal fast paths based on network and workload.
- •For database architects: Build distributed databases that reduce consensus delays through tailored fast-path protocols tailored to specific deployment conditions.
Authors
Clément Burgelin, Antoine Murat, Gal Sela, Marcos K. Aguilera, Rachid Guerraoui
Abstract
Strongly consistent geo-replication often relies on fast paths to reduce latency in the common case of no failures or contention. Existing fast-path schemes, however, are ad hoc and restrictive: each corresponds to a point in a broad design space shaped by network topology, workload, and latency objective, so no single scheme works best across settings. This paper looks at fast-path schemes from a new perspective, as mechanisms that spread knowledge about proposals. With this view, we identify a fundamental condition on the spread of knowledge for a fast-path scheme to work. We then introduce KCensus, a framework that turns this condition into an optimization problem, synthesizing new fast-path schemes that are optimal for a given setting. We use KCensus to build a geo-replicated key-value store and evaluate it across AWS regions. Our system outperforms competing protocols, with up to 16% lower average latency.