UW-Madison Logo

The ADvanced Systems Laboratory (ADSL)
Publication abstract

Consistency-Aware Durability

Aishwarya Ganesan
Department of Computer Sciences
University of Wisconsin-Madison


Modern distributed storage systems are emerging as the primary choice for storing massive amounts of critical data that we generate today. A central goal of these systems is to ensure data durability, i.e., these systems must keep user data safe under all scenarios.

To achieve high levels of durability, most modern systems store redundant copies of data on many machines. When a client wishes to update the data, the distributed system takes a set of actions to update these redundant copies, which we refer to as the system’s durability model. At one end of the durability model spectrum, data is immediately replicated and persisted on many or all servers. While this immediate durability model offers strong guarantees, it suffers from poor performance. At the other end, data is only lazily replicated and persisted, eventually making it durable; this approach provides excellent performance but poor durability guarantees.

The choice of durability model also influences what consistency models can be realized by the system. While immediate durability enables strong consistency, only weaker models can be realized upon eventual durability. Thus, in this dissertation, we seek to answer the following question: is it possible for a durability model to enable strong consistency guarantees, yet also deliver high performance?

In the first part of this dissertation, we study the behavior of eight popular modern distributed systems and analyze whether they ensure data durability when the storage devices on the replicas fail partially, i.e., sometimes return corrupted data or errors. Our study reveals that redundancy does not provide fault tolerance; a single storage fault can result in catastrophic outcomes such as user-visible data loss, unavailability, and spread of corruption.

In the second part, to address the fundamental tradeoff between consistency and performance, we propose consistency-aware durability or CAD, a new way to achieving durability in distributed systems. The key idea behind CAD is to shift the point of durability from writes to reads. By delaying durability upon writes, CAD provides high performance; however, by ensuring the durability of data before serving reads, CAD enables the construction of strong consistency models.

Finally, we introduce cross-client monotonic reads, a novel and strong consistency property that provides monotonic reads across failures and sessions. We show that this property can be efficiently realized upon CAD, while other durability models cannot enable this property with high performance. We also demonstrate the benefits of this new consistency model.

Full Paper: PDF   BibTeX