Improving Wide-Area Replication Performance through Informed Leader Election and Overlay Construction

Replication is an important building block to achieve high availability in the presence of failures. Until recently, wide-area replication with strong consistency guarantees was regarded as impractical due to performance constraints. We investigate how informed leader election combined with a network overlay can improve the performance of distributed consensus, which is at the heart of every replicated data store. Leader election and overlay construction are particularly relevant when replicating data at global scale where network links exhibit diverse performance characteristics. We propose to incorporate knowledge about the link quality and network overlay topology into the leader election algorithm. In particular, we show how optimizing only for a quorum, instead of all replicas, we can increase replication throughput or decrease the request latency. Our measurements show a throughput increase of 1.5x when optimizing for throughput of all replicas and a 3x improvement when the throughput is optimized only for a quorum.