6.824 2015 Lecture 12: Eventual Consistency, Bayou Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System Terry, Theimer, Petersen, Demers, Spreitzer, Hauser, SOSP 95 some material from Flexible Update Propagation for Weakly Consistent Replication, SOSP 97 Why this paper? Eventual consistency is pretty common git, iPhone sync, Dropbox, Amazon Dynamo Why do people like eventual consistency? fast read/write of local copy (no primary, no paxos) disconnected operation What goes wrong? doesn't look like "single copy" (no primary, no paxos) conflicting writes to different copies how to reconcile them when discovered? Bayou has the most sophisticated reconciliation story Paper context: Early 1990s (like Ficus) Dawn of PDAs, laptops, tablets H/W clunky but clear potential Commercial devices did not have wireless Devices might be off or not have network access This problem has not gone away! iPhone sync, Dropbox sync, Dynamo Let's build a conference room scheduler Only one meeting allowed at a time (one room). Each entry has a time and a description. We want everyone to end up seeing the same set of entries. Traditional approach: one server Server executes one client request at a time Checks for conflicting time, says yes or no Updates DB Proceeds to next request Server implicitly chooses order for concurrent requests Why aren't we satisfied with central server? I want to use scheduler on disconnected iPhone &c So need DB replica in each node. Modify on any node, as well as read. Periodic connectivity to net. Periodic direct contact with other calendar users (e.g. bluetooth). Straw man 1: merge DBs. Similar to iPhone calendar sync, or file sync. May need to compare every DB entry -- lots of time and net b/w. Still need a story for conflicting entries, i.e. two meetings at same time. User may not be available to decide at time of DB merge. So need automatic reconciliation. Idea for conflicts: update functions Application supplies a function, not a new value. Read current state of DB, decide best change. E.g. "Meet at 9 if room is free at 9, else 10, else 11." Rather than just "Meet at 9" Function can make reconciliation decision for absent user. Sync exchanges functions, not DB content. Problem: can't just apply update functions to DB replica A's fn: staff meeting at 10:00 or 11:00 B's fn: hiring meeting at 10:00 or 11:00 X syncs w/ A, then B Y syncs w/ B, then A Will X put A's meeting at 10:00, and Y put A's at 11:00? Goal: eventual consistency OK for X and Y to disagree initially But after enough syncing, all nodes' DBs should be identical Idea: ordered update log Ordered log of updates at each node. Syncing == ensure both nodes have same updates in log. DB is result of applying update functions in order. Same log => same order => same DB content. How can nodes agree on update order? Update ID: