Analysis of Strong Consistency Models in Distributed Key-Value Stores

Sudhir Ravi
Suril Dhruv

ABSTRACT

Over the last couple of years, distributed key-value stores are
gaining importance as relational databases are becoming harder to
scale. A few of these stores provide high availability and performance
at the cost of strong consistency. Strong consistency leads to
increased latency but ensures correctness of the data
retrieved. Various mechanisms exist today to enforce strong
consistency led by the popular consensus based RAFT protocol. Other
ways in which strong consistency can be enforced are via
Primary-Backup protocol or chain replication.

In this work, we compare and contrast these methods by which strong
consistency can be enforced in a distributed KV store setting. We
focus on a single key range that is globally replicated for the
purpose of our experiments rather than understand how sharded data
might help; especially in the case of chain replication, in which case
every shard would be a different set of replicas.

We have used Amazon’s EC2 instances to have a distributed setting. We
use Voldemort KV store as the storage layer on each of the nodes and
measure the three different systems for performance. We have
successfully compared the above implementations based on throughput
and latency under various workloads. In this work, we implement
Primary- Backup, Chain-Replication and Raft to enforce strong
consistency on replicated Voldemort instances. We then analyze the
read and write latencies that these three replication mechanisms
provide when induced with workloads of different proportions of read
and write. We finally measure the scalability of these systems as the
replication size is increased.