Wide-area replication using continuous consistency: Theory and practice

Replication is a key approach for scaling wide-area applications and for achieving high-performance and high-availability. However, because of wide-area latency and potential Internet congestion/failures, a naive replication system may actually decrease rather than increase performance and availability by incurring excessive consistency overhead. Given such duality, the practical use of replication in the Internet has been much hindered by the lack of appropriate models and realistic experiences. The thesis of this dissertation is that replication system consistency is continuous rather than binary for many applications, and these applications can significantly benefit from exploring the semantics space between strong consistency and optimistic consistency.; I make the following contributions in support of my thesis: (i) As the first step, I propose a continuous consistency model that allows applications to dynamically tune replication system consistency. The model explores the semantic space between traditional strong and optimistic consistency models for wide-area replication. (ii) Next, I design efficient consistency protocols to enforce the model. I also discuss how aggressive optimizations can be used on these protocols for scalability. (iii) To verify the feasibility of the model and gain realistic experience, I build a TACT middleware toolkit for wide-area replication. Using three sample applications, I evaluate the system performance and demonstrate significant semantics and performance benefits relative to traditional approaches. (iv) To further understand my model's effects on system availability, I derive tight theoretical availability upper bound as a function of consistency level, workload and faultload. (v) Using live wide-area deployment and LAN emulation, I extensively evaluate the availability achieved by various consistency protocols. I find that simple optimizations can significantly improve system availability. I also observe that using my optimizations, simply protocols can approach the theoretical availability upper bound in my target scenarios. (vi) Finally, in the context of dynamic replica placement, to understand my model's effects on replication cost, I derive a replication cost lower bound for a given availability and performance target under continuous consistency.; In summary, by establishing an appropriate model, providing theoretical understanding and reporting practical experience, this dissertation enables wide-area replication through continuous consistency.