Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System
📜 Abstract
Bayou is a replicated, weakly consistent storage system designed for a mobile computing environment that includes portable machines with less than ideal network connectivity. To maximize availability, users can read and write any accessible replica. Bayou’s design has focused on supporting application-specific mechanisms to detect and resolve the update conflicts that naturally arise in such a system, ensuring that replicas move towards eventual consistency, and defining a protocol by which the resolution of update conflicts stabilizes. It includes novel methods for conflict detection, called dependency checks, and per-write conflict resolution based on client-provided merge procedures. To guarantee eventual consistency, Bayou servers must be able to roll-back the effects of previously executed writes and redo them according to a global serialization order. Furthermore, Bayou permits clients to observe the results of all writes received by a server, including tentative writes whose conflicts have not been ultimately resolved. This paper presents the motivation for and design of these mechanisms and describes the experiences gained with an initial implementation of the system.
✨ Summary
Bayou presents a weakly consistent, fully replicated storage system for mobile and intermittently connected environments. Clients may read from and write to any reachable replica, while servers exchange updates through pair-wise anti-entropy sessions. Each write carries an application-defined dependency check and a per-write merge procedure, allowing conflicts to be detected and resolved according to application semantics rather than only at the file or record level. Writes are initially tentative; deterministic execution in a globally defined order, together with rollback and replay, drives replicas toward eventual consistency. A primary server commits writes and thereby stabilizes their results, while clients may inspect either tentative or committed data. The prototype demonstrated these ideas using a meeting-room scheduler and a bibliographic database, with security provided through public-key authentication and signed access-control certificates. The design’s principal trade-off is that applications must explicitly tolerate tentative, weakly consistent results and participate in conflict handling.
The paper influenced subsequent highly available storage research. Amazon’s Dynamo paper explicitly cites Bayou as a system supporting disconnected operation, eventual consistency, and application-level conflict resolution, while distinguishing Dynamo’s key-value and large-scale service-oriented design from Bayou’s relational and mobile-computing focus. Dynamo also adopted the broader design pattern of allowing continued reads and writes during failures and resolving divergent versions through application-assisted mechanisms. (doi.org)