Bayou is a multi-copy weakly consistent storage system. Bayou provides parallel activities to manage conflicts for collaborative applications, primarily in weakly connected mobile computing environments. In a weakly connected network environment, only weak consistency copies can be realized. In Bayou, clients can read data in any case, even if conflicts in the data are not completely resolved. The main contributions of this paper are as follows:

  • The conflict detection and resolution of application definition are introduced by dependency checking and merging process when updating data.
  • Two states of update are defined: commit and probe;
  • How to manage updates to the two states
  • How the copy leads to final agreement;
  • How to ensure security in Bayou (notes omitted).

Bayou application

  • Conference room scheduling: The conference room scheduler allows users to reserve a conference room. If the meeting room requested by the user conflicts with the specified time, the meeting room will be rescheduled to an alternate time.
  • Document database: Document database allows users to collaboratively maintain a document database, maintain a mapping of identifiers to document entries, and automatically rename conflicting labels if there are any.

Bayou basic system model

The Bayou system keeps copies of its data set on a number of servers with which applications interact through apis. The API provides two types of operations: read and write. Bayou uses the weakly consistent copy model to provide arbitrary read and write access. Clients access different servers for reading and writing, and Session Guanrantees are required to ensure consistency observed by clients.

In order to implement application level flush detection and resolution, update operations need to provide additional information needed for conflict detection and resolution. Servers exchange writes of records using the inverse entropy protocol, and as long as there is no permanent split between servers, writes eventually reach all servers.

Conflict detection and resolution

Support for conflict detection and resolution of application definition is the focus of Bayou design. The mechanisms of conflict detection and resolution are dependency check and merge process respectively.

  • The execution of a write operation:
Bayou_Write (update, dependency_check, mergeproc) {
    IF (DB_Eval (dependency_check.query) <> dependency_check.expected_result)
        resolved_update = Interpret (mergeproc);
    ELSE
        resolved_update = update;
    DB_Apply (resolved_update);
}
Copy the code
  • A write operation:
Bayou_Write(update = {insert, Meetings, 12/18/95, 1:30pm, 60min, "Budget Meeting"}, Dependency_check = {query = "SELECT key FROM Meetings WHERE day = 12/18/95 AND start < 2:30pm AND end > 1:30pm", expected_result = EMPTY}, mergeproc = { alternates = {{12/18/95, 3:00pm}, {12/19/95, 9:30am}}; newupdate = {}; FOREACH a IN alternates {# check if there would be a conflict
            IF (NOT EMPTY (
                SELECT key FROM Meetings WHERE day = a.date
 AND start < a.time + 60min AND end > a.time))
CONTINUE;
# no conflict, can schedule meeting at that timeNewupdate = {insert, Meetings, a.date, a.time, 60min, "Budget Meeting"}; BREAK; } IF (newupdate = {})# no alternate is acceptableNewupdate = {insert, ErrorLog, 12/18/95, 1:30pm, 60min, "Budget Meeting"}; RETURN newupdate; })Copy the code

Depend on the check

If the server’s query on the current data does not return the desired result, then a conflict has occurred. Bayou’s dependency checking can detect both writer-write and read-write conflicts because it can do arbitrary queries and therefore can achieve highly flexible constraints on data.

Merging process

When a conflict is detected, the server performs the merge process. When conflicts cannot be merged automatically, they are logged so that they can be resolved manually.

Copy consistency

The final consistency achieved by Bayou is mainly guaranteed by two principles:

  1. Write operations have a consistent order across all servers;
  2. The collision detection and merge processes are deterministic, so each server resolves conflicts the same way.

The Bayou server receives write requests that are initially tentative and eventually commit. Each write operation is marked with a < timestamp, marked server ID>. The server uses a logical clock, usually synchronized with real time, but needs to push its clock forward after receiving the write operation from the reverse entropy process. When the server receives a new write through the inverse entropy protocol, it needs to reapply the write in order by undoing the write.

Write stability and commit

When a write operation is last executed by the server, the write operation is considered to be in a stable state, meaning that the server has received all writes up to this write.

Checking for write stability can be done using the inverse entropy protocol, where servers exchange timestamps for the latest write operation. When a write operation timestamp is lower than all server timestamps, then the write is stable. For each data, select a master server and let the other servers exchange committed writes through it.

Storage System Implementation

The storage system consists of three parts: write logs, metadata storage, and revoke logs.

  • Write log: contains write requests received by the sorted server;
  • Meta-storage: contains the execution results of the current write;
  • Undo log: Used to undo write operations.

When the write is stable, the request can be deleted in the log. Meta-storage is implemented in an in-memory relational database, holding commit and both versions of the database together, using two bytes to mark commit or all. Undo logs can undo changes previously written to the meta-storage. To implement failover, write logs and meta-storage checkpoints need to be saved to stable storage.

  • Apply the write to the database
Receive_Writes (writeset, received_from) {
    IF (received_from = CLIENT) {
        # Received one write from the client, insert at end of WriteLog
        # first increment the server’s timestamp
        logicalclock = MAX(systemclock, logicalclock + 1);
        write = First(writeset);
        write.WID = {logicalclock, myServerID};
        write.state = TENTATIVE;
        WriteLog_Append(write);
        Bayou_Write(write.update, write.dependency_check, write.mergeproc);
    } ELSE {
        # Set of writes received from another server during anti-entropy,
        # therefore writeset is ordered
        write = First(writeset);
        insertionPoint = WriteLog_IdentifyInsertionPoint(write.WID);
        TupleStore_RollbackTo(insertionPoint);
        WriteLog_Insert(writeset);
        # Now roll forward
        FOREACH write IN WriteLog AFTER insertionPoint DO
            Bayou_Write(write.update, write.dependency_check, write.mergeproc);
        # Maintain the logical clocks of servers closewrite = Last(writeset); logicalclock = MAX(logicalclock, write.WID.timestamp); }}Copy the code

reference

  1. Terry, Douglas B., et al. “Managing update conflicts in Bayou, a weakly connected replicated storage system.” SOSP. Vol. 95. 1995.