Managing Update Conflicts In BayouDouglas B. Terry, Marvin M. Theimer, Karin Petersen, Alan J. Demers,Mike J. Spreitzer and Carl H. HauserPresented to cs294-4 by Owen CooperBayou’s Goals• Support distributed workgroup applications– No continuous network connectivity– Clients update the database while disconnected– Clients synchronize with one another when convenient• Allow the application to manage inconsistency– Differentiate between stable and unstable data– Allow applications to define conflicts & resolutions• Eventually provide a consistent view of writesSample Applications• Book a room for a meeting– Clients select a non-conflicting time & backups– At most one of these times will be official• Bibliographic database– Clients enter a name and body for the referenceSystem Model • Data managed in replication objects– Multiple servers keep copies of these objects– Apply their own writes immediately – Learn about other writes through interchange– Writes contain conflict resolution & detection informationData Exchanges• Data is exchanged via epidemic protocol– Data data propagated between pairs of machines– Data is transferred in order• Easy to summarize the writes receivedConflicts & Resolutions• Updates at different replicas lead to conflicts• What is a conflict?– It depends on the application • E.g. overlapping appointments for a scheduling app• Key -> value apps– Assignment of the same key to different items– Assignment of the same value to multiple keys• Resolution also depends on the application– Select from the backup list (for calendar)– Assign a new key or merge values for bibliographic dbConflict Aware Writes• Writes include code– To detect if they conflict with the db.• Via queries and expected results• Allows arbitrary validation of “before state”– To merge the write in case validation fails• Like conflict detection, can make arbitrary reads to perform themerge• Must be deterministic• Code is interpreted• And in a library (to avoid copy/write)– But may differ slightly (I.e. parameterized)• Write actions atomicWrite Processing• Writes are either tentative or committed• Writes applied immediately– Are stamped with an accept time and serverid– Are applied tentatively• Writes are ordered across servers – By by committime, accepttime, serverid– Tentative writes always after committed writes• Tentative writes may be reordered– Due to data obtained from other replicas– When the tentative write is committedWrite Processing (2)• Processing writes from an exchange– Receive writes and identify time of first write– Rollback local database – Apply writes to write log (time-ordered merge)– Roll forwardWrite Processing (3)• To achieve consistency– Write logs need to contain the same writes– Results equal for same starting state, write• Conflict detection, merge procedures deterministicWrite Stability• Write position will no longer change• Two ways to achieve it– clocks for all servers > write timestamp– Designate a primary to fix the position• Bayou adopts the latter approachStorage• Three components– Ordered log of writes– Undo log to rollback tentative writes– Tuple store • Implemented as a relational db• Tracks multiple views of a tuple– Commited or full• Tuple store checkpoint• Version vectors– Track latest write received from each replica– Track log truncationAccess Control• Granted at the level of a replica– Read and write privledges• Done using public key encryption– Relies on well-known signing authority• Operations– Grant privilege: give user privilege on a replica• Signed by central authority– Delegate: a user grants privilege to another user• Signed by delegating user– Revoke: revoke privilege • Signed by grantor Access Control (2)• Checks done at beginning of exchange– Access is granted if valid certificate presented– And it is not known to have been revoked• Validation done twice for writes– Once accepted by one exchange, it is propagated– Check again at the primaryPerformance (1)• Experiment using bibliographic app– 1550 record databasePerformance
View Full Document
Unlocking...