New algorithm improves read speed on distributed data systems
Ditto: Generalized Reconfigurable Linearizable Reads
Distributed, Parallel, and Cluster ComputingDatabases
Summary
This work tackles the problem of making data reads faster in systems where many computers share data but need to keep everything consistent as if run on one machine. The authors show that existing methods can't be the best in all conditions because of tradeoffs between how fast reads and writes happen and how they handle network issues. They created a new approach called Pairwise Quorums, along with a system named Ditto, which changes its behavior based on network and workload changes. Together, these improve or match existing methods, making data reads more efficient without slowing writes.
What this means in practice
- •For distributed systems engineers: Run scalable data storage systems that adjust read and write methods dynamically to maintain speed and consistency under varying network conditions.
- •For cloud service providers: Improve user experience by reducing delays in frequent read requests while maintaining consistency across geographically distributed data centers.$Commercial implications: Enables cloud providers to offer faster and more reliable data services by dynamically adapting read/write protocols to network changes.
Authors
Aleksey Panas
Abstract
Linearizability gives developers the illusion that operations on a distributed datastore execute sequentially on a single machine. Providing it is expensive, so numerous specialized reads algo- rithms have been proposed to make reads significantly faster without sacrificing linearizability, which matters because most workloads are read-dominant by orders of magnitude. Yet, none of these algorithms is the best choice for every deployment. We show why with a framework that classifies these algorithms into a generalized space together with a mathematical analysis of their latencies as a function of this generalization. The analysis exposes two fundamental tradeoffs, one between read and write latency and one between read and write tolerance to network variance, which together leave the best algorithm dependent on network and workload conditions that vary over time. It also exposes a gap: there is a way to minimize the delay a read incurs when it overlaps a concurrent write, at no cost to writes, yet exist- ing algorithms can apply it only for a subset of the tradeoff space, forcing any deployment that needs the full space to settle for a strictly worse solution. We close this gap with a new algorithm, Pairwise Quorums, and build a second, Ditto, that reconfigures across the space at runtime as conditions change. Together they subsume every existing algorithm under our model: against each, the combination is either strictly better, or reconfigures to match it where a genuine tradeoff applies.