Year: 1995

Authors: DB Terry, MM Theimer, K Petersen et al

Summary

“Bayou is a replicated, weakly consistent storage system designed for a mobile computing environment that includes portable machines with less than ideal network connectivity.” It contributes by defining a protocol by which the resolution of update conflicts stabilizes:

  • Methods for conflict detection: dependency checks
  • Per-write conflict resolution based on client-provided merge procedures

It’s very innovative in thinking that consistency could be pushed to the client side and leverage application specific relaxations:

  • “We believe that applications must be aware that they may read weakly consistent data and also that their write operations may conflict with those of other users and applications.”
  • “letting applications exploit domain-specific knowledge to achieve automatic conflict resolution at the granularity of individual update operations without compromising security or eventual consistency.”

It differs from previous approaches in that it doesn’t block the resources until the conflict is resolved but expose all the conflicting data to the user. An example application they mentioned is meeting room scheduler.

Dependency Checks

What it is: “Each Write operation includes a dependency check consisting of an applica- tion-supplied query and its expected result.”

Similar to vector clocks, which just detects write write conflicts, Bayou could check for read-write conflicts because each execution could optionally carry around constraints that must be satisfied at commit time. Its also different from OCC because the condition its checking is not that the value is exactly the same, but rather it still holds some invariants.

One simple example was given in the paper: “For example, suppose a Write transfers $100 from account A to account B. The applica- tion, before issuing the Write, reads the balance of account A and discovers that it currently has $150. Traditional optimistic concurrency control would check that account A still had $150 before performing the requested Write operation. The real requirement, however, is that the account have at least $100, and this can easily be specified in the Write’s dependency check.”

Conflict Detection

Supporting application-specific conflict detection is a major emphasis in the Bayou design

The steps taken to resolve conflicting updates once they have been detected may also vary according to the semantics of the application.

Merge Procedures

Below is an example Bayou write:

Bayou Write

Replica Consistency: Eventual

How? Determinism!

  • Writes are performed in the same, well-defined order at all servers.
  • Conflict detection and merge procedures are deterministic so that servers resolve the same conflicts in the same manner.

Why so strict?

In practice, because Bayou’s Write opera- tions include arbitrary merge procedures, it is effectively impossible either to determine whether two Writes commute or to transform two Writes so they can be reordered as has been suggested for some systems

Write Stability and Commitment

Definition: A Write is said to be stable at a server when it has been exe- cuted for the last time by that server.

In many cases, an application can be designed with a notion of “confirmation” or “commitment” that corresponds to the Bayou notion of stability.

How does the user know? Use primary commit scheme. That is, one server designated as the primary takes responsibility for committing updates.

Primary fails? Bayou design readily accommodates the temporary unavailability of the primary.

Storage System Implementation Issues

Unique needs: need for space-efficient Write logging

Tuple Store:

A unique aspect of the Tuple Store is that it must support the two distinct views of a Bayou database that are of interest to clients: committed and full.