merge.md

Merge

The merge subroutine occurs during the pull synchronization procedure, and it's purpose is to consolidate the changes fetched from the server (a journal of operations performed by other nodes) with the changes performed locally since the last sychronization (last successful push call). After the merge, the local database should roughly be left in the state that could have been reached by applying the changes from the server before modifying the local state, and then changing the local database in whatever application-specific manner it was changed. The expected behaviour is somewhat similar to the consolidation performed by the various version control systems when multiple changes are applied by different authors to a single file.

Operations contained either in the server-sent message or the local journal are simply references to the object operated upon, and are split in three groups:

• U: updates
• I: inserts
• D: deletes

To differentiate sent operations from local ones, the following notation is used:

• U_m: updates in the message (sent from the server)
• U_l: local updates
• I_m: inserts in the message
• I_l: local inserts
• D_m: deletes in the message
• D_l: local deletes

Also, when mentioning 'local operations', the intention is to refer to the unversioned local operations (i.e. the ones not yet pushed to the server).

Finally, the following notation for sets, operators and quantifiers is used:

• DB: set of all objects in the local database
• MSG: set of all objects in the server-sent message
• union: set union
• inter: set intersection
• empty: the empty set
• map: map a function to a set (e.g. map( x -> x*2, { 1, 2, 3 } ) = { 2, 4, 6 })
• in: element in set (e.g. 2 in { 5, 6, 2 })
• forall: 'for all' quantifier

Detection of conflicts over object identity

An early step of the merge subroutine is to detect the conflicts that could happen if the server operations were performed directly, without checks. For example, attempting a server-sent update operation over an object already deleted locally would result in an error. On the other hand, if the local operation were to be given priority, the (local) delete would be performed last and the update sent from the server would be ignored. Regardless of the actual conflict resolution, the case needs to be detected properly.

These conflicts are 'over object identity' because they involve object existence. The other kind of conflicts resolved by dbsync are those caused by unique constraints on table columns. The detection and resolution of those is explained further ahead.

The conflicts over object identity are pairs of one server-sent operation and one local operation, both of them known to be colliding in some way, and are split into four types based on the nature of the collision:

• direct: two operations collide and both reference the same object. Both operations are non-insert operations, since inserted objects can't possibly be referenced by other applications before synchronization (e.g. node A can't update a record that was inserted in node B).

  direct := { (remote, local) forall remote in (U_m union D_m),
                              forall local in (U_l union D_l) /
              object_ref(remote) = object_ref(local) }
  

  The object_ref function takes an operation and returns the reference to the object in database. Since the object might not be present, only the reference is returned. The reference is just the value of the primary key and information of the type of object (like the table name and SQLAlchemy class name).

• dependency: two operations collide and one references an object that is the "child" of the other referenced object, where being a child means having a foreign key relationship with another object and having the foreign key column in the table (the "parent" doesn't have the foreign key). In these, the local conflicting operation references the "child".

  As notation, an object x being the "child" of an object referenced by y (y is only a reference) will be written:

  x FK y
  

  With this, the dependency conflicts can be defined as:

  dependency := { (remote, local) forall remote in D_m,
                                  forall local in (I_l union U_l) /
                  fetch_object(local, DB)) FK object_ref(remote) }
  

  Since the FK relationship doesn't match references with references (the "child" must be a real database object), an aditional 'fetch' phase is required. The function fetch_object could be defined as a container query (container meaning object store, e.g. DB or MSG) given the reference, or:

  fetch: References, Containers -> Objects
  fetch(r, c) = o, where reference(o) = r
  
  fetch_object := op, cont -> fetch(object_ref(op), cont)
  

  This works because the object being fetched exists (the operation is an insert or an update). If it doesn't, the whole merge subroutine fails as early as conflict detection.

• reversed dependency: just like the dependency conflicts, but having the "child" object referenced by the server-sent operation. The distinction is made because the resolution methods for these conflicts are different.

  reversed dependency := { (remote, local) forall remote in (I_m union U_m),
                                           forall local in D_l /
                           fetch_object(remote, MSG) FK object_ref(local) }
  

  The fetch phase here is different. The remote operation references a remote object, one that exists in the server. Thus, the query is performed over the server-sent message, which contains all possible required objects. The message is constructed in such a way that only the objects that could be needed are included. (Currently, the server has to pre-detect conflicts while building the message, as an optimization done to reduce the size of the message. Previously, the server included all "parent" objects for each object added, and the message was bloated excessively when adding objects with many foreign keys.)

• insert: insert conflicts are the product of automatic primary key assignment. When two insert operations reference the same object, the object identity assigned by the local application is simply accidentally the same as the one sent from the server. The objects themselves are known to be different, and thus the conflict will be resolved by keeping both (more on this later).

   insert := { (remote, local) forall remote in I_m,
                               forall local in I_l /
               object_ref(remote) = object_ref(local) }
  

Operation compression

There's an earlier stage in the merge subroutine that's required for the conflict detection to be optimal and stable. Without previous consideration, the operation journals are filled with every single operation performed by the application, often redundantly (note: operations don't store the actual SQL sentence). This often means sequences like the following are stored:

1. Insert object x
2. Update object x
3. Update object x
4. Update object x
5. Delete object x

In this example, object x is inserted, modified and finally deleted before ever being synchronized. Without care for these cases, the merge subroutine would detect conflicts between operations that could have been "compressed out" completely. Also, and as shown in this example, a 'fetch' call on object x would have failed since it wouldn't exist in the database any longer. This operation compression is the earliest phase in the merge subroutine.

(Worth noting from this example is that operations can be sorted in some way. The sorting criteria is the order in which they were logged in the journal, the order in which they were executed by the local application.)

The main requirement for the operation sets before conflict detection is that at most one operation exists for each database object involved in the synchronization. This means:

map(object_ref, U_l) inter map(object_ref, I_l) = empty
map(object_ref, I_l) inter map(object_ref, D_l) = empty
map(object_ref, U_l) inter map(object_ref, D_l) = empty

And for the server-sent operations, too:

map(object_ref, U_m) inter map(object_ref, I_m) = empty
map(object_ref, I_m) inter map(object_ref, D_m) = empty
map(object_ref, U_m) inter map(object_ref, D_m) = empty

Operation compression must reach these states for the merge to have a good chance of success. Of course, not any modification of the journal is a valid one. It's purpose must be preserved: to record a way to reach the current database state from the previous one.

The rules applied for compressing sequences of operations over a single object are simple, yet different when compressing the local database or the server-sent operations. The library assumes that the local database is complying with the restriction imposed on its use: primary keys cannot be recycled. When this is true, a delete operation marks the end of an object reference's lifetime. Thus, a delete operation must be the final operation of a local operation sequence, each time a delete exists at all in said sequence.

On the server-sent message, however, the operation set could be originated from various nodes. Since conflict resolution could (and currently sometimes does) re-insert objects that were deleted, the previous rule doesn't apply over server-sent sequences.

The previous example illustrates a compression rule for the local database: sequences that start with an insert and end in a delete must be wholly removed from the journal. A less intuitive rule applied to the server-sent message is: sequences that start with a delete and end with a non-delete must be reduced to a single update:

d, i, u, u => u
d, i => u

With this pattern-based notation, where to the left of the => is a comma-separated sequence of expressions that match operations, and to the right is a singleton set or the empty set, the whole set of rules can be written succinctly:

Let * be the Kleene star, . be a matching expression for any operation, ~x be a matching expression for anything but x (i.e. not x):

Local compression:

i, u*    => i
i, u*, d => empty
u, u*    => u
u*, d    => d

Compression on the server-sent message:

i         => i
u         => u
d         => d
i, .*, d  => empty
i, .*, ~d => i
u, .*, d  => d
u, .*, ~d => u
d, .*, d  => d
d, .*, ~d => u

While the rules for compressing the server-sent operations cover all possible sequences, the rules for the local operations don't. If a local operation sequence is found not to match any of those rules, a warning is emitted that notifies the user of probable database intervention, or failure to comply with the library's restriction on primary keys.

Conflict resolution

A 'merge' is a common operation in version control systems (VCSs). Usually, a VCS will detect conflicting changes and notify the users, leaving them with the choices. They don't perform automatic conflict resolution by default, since in general the criteria applied in resolving each conflict is specific and even unclear. Dbsync however is currently implemented with a fixed conflict resolution strategy. As such, incorrect choices are sometimes made, but the strategy is forgiving enough that data loss is mostly avoided. A way to abstract and let the users build their own strategies is an improvement that will be left for the next major version.

Another point worth comparing with VCSs is history tracking. In dbsync, all history is linear and irreversible. There are no branches and there's no 'revert' procedure. These features are consequence of the core design and can't be changed easily. As such, it's better to rely on backups on the server if a way to revert changes is required.

Given this weakness in the library, the strategy chosen is meant to preserve the operations performed in the node over those in the server. A merge occurs in the node, and the conflict resolution won't be reflected back to the server untill the next 'push'. With these grounds, the strategy can be written plainly as:

1. When delete operations are in any conflict with non-delete operations, revert them. Reverting them means to reinsert the deleted object (fetching from the complementary container), and also to either delete the operation from the journal (a local delete operation) or to nullify the operation with a new insert operation (a server-sent delete operation). The difference in the way to revert the delete operation is what mandates the separation of dependency conflicts in two categories.

2. When update operations collide, keep the local changes over the server-sent ones. This is strictly a case of data loss, but it can be handled, though cumbersomely, through centralized back-ups.

3. As mentioned earlier, insert operations colliding will result in the allocation of a new primary key for the server-sent object. Since primary keys are presumed to be integers, the incoming object is currently given a primary key of value equals to the successor of the maximum primary key found on the corresponding table. Even in the case the library would allow primary keys of different types in the future, this part of the current strategy would force the application to not give any meaning to them.

4. Delete-delete conflicts translate to a no-operation, and the local delete entry is removed from the journal.

The conflict resolution is done as required while attempting to perform each of the server-sent operations. Each remote operation is checked for conflicts and is finally either allowed, blocked, or added extra side-efects as consequence of the strategy defined above. Once the final remote operation is handled, the local version identifier is updated and the merge concludes successfully. Any error is reported before completion in the form of a thrown exception.

Unique constraints

As consequence of not storing the state transitions of objects, dbsync currently generates conflicts of another kind: the swapping of values tied to unique constraints at the database level. Consider the following example of a state transition sequence of two objects, x and y, each of the same type with a unique constraint enforced on the col attribute:

1. x[col=1]; y[col=2]
2. x[col=3]; y[col=2] (update x with temporal value)
3. x[col=3]; y[col=1] (update y with x's old value)
4. x[col=2]; y[col=1] (update x with y's old value)

This update sequence is one that could be generated by an application, and which complies with a unique constraint on the col attribute (col is also a column of the mapped table). Since the state transition is lost in the operations journal, simply applying the compressed operation (a single update for each object) during a merge subroutine would result in an error not previously accounted for. Also worth noting is that the given example shows only the case of a one-step swap, on a single constrained attribute. Multiple-step swaps (involving more than two objects) and multiple-column constraints are also variations to consider.

Not every case of unique constraint violation is caused by dbsync, however. It’s also possible that two insert or update operations, registered by different nodes, collide on such a constraint without it being a consequence of poor logging. These cases happen because the constraint is checked locally by the database management system or engine, and not against the synchronization server. Dbsync detects these as well, and interrupts the merge subroutine with a specialized exception that contains required details for the end user to resolve it.

To detect unique constraint conflicts, dbsync uses SQLAlchemy’s schema inspection API to iterate over the unique constraints defined in tables referenced by operations in the message. For each constraint found for each operation, a local object that matches the constraining values in the server-sent object is looked up. If found, the local object is further inspected to detect whether the case is a solvable conflict or a user error.

A solvable conflict is determined by the presence of another version of the conflicting local object in the message (a third object, in the message, that has the same primary key value as the local conflicting object). This indicates that an update swap exists in the server-sent state difference, and the three objects form a single step of it. The conflicting objects are all collected and this way, multiple-step swaps are detected in increments. The collection of conflicting objects is finally deleted and immediately inserted with their final state, thus resolving the conflict. This method of resolution was found to be applicable in many different DBMSs, although it required the temporal desactivation of foreign key cascades, as they could trigger unexpected changes to the database.

An unsolvable conflict is determined by the absence of the local conflicting object in the server-sent message. This means that operations from both devices collide, but do so exclusively in a pair. Detecting conflicts of this kind causes the interruption of the merge subroutine.

Findings

#	Source	Summary	Comments
1	Disconnected Operation in the Coda File System	The Coda File System enables clients to work with shared files while disconnected through caching. It employs an optimistic strategy, not blocking access to files but detecting and resolving conflicts after reconnection. It was designed to improve availability.	Coda operates on different modes when connected or disconnected. An interface exists to make the state change transparent to applications [3 Design Rationale]. The client holds the majority of Disconnected Operation’s complexity [4 Detailed Design And Implementation]. Batches of file identifiers are supplied by the server while connected. When disconnected, temporary identifiers are used once the batch is exhausted [4.5.1 Replay Algorithm]. It records operations on a replay log, used later to reintegrate changes to the server. Also, records of previous changes on a single file are discarded, as an optimization [4.4.1 Logging]. Unsolvable conflicts are forwarded to the user by marking the file replicas inconsistent [4.5.2 Conflict Handling].
2	Efficient PDA Synchronization	An algorithm for synchronizing unordered data sets which depends on differences between two data sets, and not on the number of records. It improves on previous mobile device synchronization algorithms in terms of bandwidth usage and latency. Tested on PDAs.	It’s a peer-to-peer communication scheme, where no hierarchy is required between devices, and no operation logs need to be maintained. The algorithm finds the symmetric difference of sets of integers in a finite field. Thus, the hashing of data is required. The algorithm depends on foreknowledge of the number of differences between two sets. It proposes, however, a probabilistic practical method to find a good estimate of a tight upper bound, based on random sampling. It consists of the construction of a characteristic polynomial that describes a data set, and the subsequent application of said polynomial on fixed evaluation points. The computed values are sent from one host to the other, which uses them to find the set differences through interpolation. An implementation can be made efficient in terms of latency (time spent), or communication (data sent).
3	Set Reconciliation with Nearly Optimal Communication Complexity	A family of algorithms for set reconciliation is presented, as in [2], which depend exclusively on the number of differences between sets.	It is shown that the algorithm is equivalent to the transmission of the redundancy of a Reed-Solomon encoding of the coefficients of the characteristic polynomial. It is implied that the problem is equivalent when stated as an error-correcting problem (differences between sets are seen as errors). An information-theoretical explanation is given as to why a probabilistic approach to finding the upper bound is required, in the interest of keeping the communication efficient.
4	Efficient Algorithms for Sorting and Synchronization	rsync is an algorithm for updating byte strings (files) remotely, over a low-bandwidth, high-latency channel. The design and special considerations in implementation are given.	Only sections 3, 4, 5 and 6 were considered. Grossly, rsync consist of the transmission of block signatures, for a fixed number of blocks in the file, and the matching of said signatures against the remote file's signatures. Only the required blocks are then sent and updated. rsync uses two signature functions, a fast signature used to filter matching blocks, and a slow, reliable signature used to discard false positives [3.2.3 Two signatures]. Special consideration is given for file formats that alter their structure broadly for generally small editions, such as compressed files. rsync can be used as the remote-update tool for distributed filesystems on high-latency networks that work with file leases, contracts that give the client write permissions over a file for a period of time. A remote update is then performed to send the local changes to the server, which is more efficient than sending the whole file [5.5 rsync in a network filesystem]. rsync is currently part of the standard unix toolset.
5	Managing update conflicts in bayou, a weakly connected replicated storage system	Bayou is a distributed storage system and platform for applications, that provides primitives for data synchronization and guarantees the eventual consistency of the datasets across devices, thanks to its update propagation protocol.	The system is hierarchical in that a client-server distinction is made, but it can support several servers, which communicate to homologize their changes. All communication is pairwise: client-server or server-server. Applications are required to provide procedures that detect write-write and read-write conflicts, which are run at the server during synchronization. These procedures must meet a specific contract and run with limited resources [4.2 Dependency checks]. Applications must also provide conflict resolvers, which are then used to resolve the detected conflicts automatically. These procedures may also fail to correct conflicts, and notify users through specific logs [4.3 Merge procedures]. Applications are encouraged to work with the notion of pending and committed transactions [6. Write Stability and Commitment]. Servers communicate with each other in an anti-entropy process that reverts, reorders and replays operations based on timestamps and a logical clock [5. Replica Consistency]. A single server is said to be the primary for a specific data set, and is the one able to finalize an update in the form of a commit [6. Write Stability and Commitment]. The custom storage system used is a relational database with an extra 2-bit column that indicates the state of each tuple [7. Storage System Implementation Issues].
6	Differential Synchronization	Differential Synchronization refers to a method for homologizing text documents over a network, that is based on continuously computing the difference between texts and patching the remote copy.	The protocol works with backup copies of the document, called shadows, that represent the previous state of the document. Shadows are used for computing document differences locally (either in the client or the server), which are then sent to the other party for patching, using a best-effort strategy [3. Differential Synchronization Overview]. Communication interruptions are accounted for through backup shadows in the server [5.1 Asymmetry]. Different multi-client, multi-server configurations can yield different performance measurements, since the diff and patch load can be distributed along the network [6. Topology]. It is entirely based on state, and thus it’s performance depends heavily on the diff and patch algorithms [7. Diff and Patch]. The messages sent are the differences computed, not the whole document. This method presents scalability enhancements in comparison to other common protocols used in collaborative editing and version control, such as the three-way-merge, or log-based approaches.
7	Oracle Lite Synchronization	Oracle Lite is a database management system (DBMS) that, in conjunction with a specialized server and a central database, gives applications the ability to synchronize a relational database with a centralized database.	The client database is a modified version of an Oracle DBMS that keeps track of operations internally. The synchronization architecture uses queues and asynchronous calls to ensure availability and consistency. Conflict resolution is determined by a customizable, single ‘winner’: either the client or the server. Operations in the log are merged together, so that only the final state of a record is sent. A specific and customizable execution order is given to the operations performed. This order takes into account the possible operation interdependencies and the weights given to the tables by the application owner. Automatic, event-based and manual synchronization can be configured. The uniqueness of sequence-generated numbers (e.g. primary keys) is guaranteed by a partition set at the server, whereby a certain range of numbers is reserved to each client. Oracle Lite provides mechanisms to separate the central database into subsets that act as a restricted dataset for each client.
8	Detecting synchronization conflicts for horizontally decentralized relational databases	Several theorems that determine presence or absence of synchronization conflicts are given. The theorems reference atomic and composite operations performed given a common initial state.	Operations are viewed as functions that, given a database state, produce a different database state. Atomic operations are defined to be single-tuple inserts, updates or deletes [4.2 Definition of atomic operations]. Composite operations are defined as a series of atomic operations that should be treated as a single unit [5.1.1 Definition of a composite operation]. Three categories of conflicts are defined, with different decision trees for each one: conflicts based on different states, intra-relational conflicts, and inter-relational conflicts [4.6 Decision graphs for conflicts]. The first category groups conflicts that are defined as a pair of operations that, when applied sequentially in a specific order, produce a different database state that when applied in a different order [4.4.1 Unequal database states after synchronization]. The second category groups conflicts stemmed from constraints or keys defined for a table [4.5.1 Violations of intra-relational integrity constraints]. The third category is composed of conflicts that violate foreign keys and inclusion dependencies [4.5.2 Violations of inter-relational integrity constraints]. Detection of conflicts for composite operations is done by inspecting each composite operation in terms of their atomic components. Also, related operations in a sequence are analysed for dependency, in that one is dependent on the state change produced by the other [5.2.1 Related atomic operations]. The conflict analysis is not based on database state, but on the operations themselves. It follows that implementations could use operation logs to detect conflicts, rather than compute state differences.
9	Microsoft Sync Framework, last consulted november 22th, 2014. Sections: Infrastructure Conflicts	The framework enables databases to synchronize in collaborative editing scenarios and occasionally connected scenarios.	Several database management systems are supported, thanks to synchronization providers, application libraries that mask the Sync Framework implementation details. ADO.NET compatible databases are generally supported. Client-server and client-client topologies are fully supported. The installation of the framework implies the construction of the Sync Framework infrastructure, as dictated by the synchronization provider. The infrastructure consists of tables, triggers and stored procedures. Conflict detection and automatic conflict resolution are performed by the provider library. Complex operation logs (tracking tables) are kept up-to-date with each database, and are populated with triggers [9.1]. Conflicts occur at the row level [9.2]. Conflict resolution is fully customizable, through access to copies of the datasets involved in synchronization [9.2].
10	Sybase MobiLink 12 Performance and MobiLink Server Administration	Sybase MobiLink forms a client-server architecture for database synchronization. Many DBMSs are supported for the server-side data store, and two Sybase DBMSs are supported for the client application: UltraLite and SQL Anywhere.	The server architecture is designed to maximize performance. It is split in multiple components, each handled by at least one separate thread. Simultaneous synchronizations are allowed by the server. Multiple synchronization techniques are supported, such as timestamp synchronization (using a ‘last-updated’ timestamp column to determine whether a row is to be included), and snapshot synchronization (which includes whole tables). All tables must have primary keys defined, and their values should be unique across all databases partaking in synchronization. The primary keys should not be modified by the applications. Primary key domains for autoincrementing keys are partitioned at the server. Primary keys are used to identify synchronization conflicts. Conflicts are detected and custom resolution can be implemented by listening to specific events. A ‘forced mode’ can be used that treats every incoming row as a conflict, which then triggers all related events. Deletes can be detected through use of shadow tables (a form of simple operations log for deletes) or logical deletes (not deleting rows but marking them as deleted with a specific column).
11	Where does Firebase fit in your app?, last consulted november 23th, 2014. Offline Capabilities - Firebase, last consulted november 23th, 2014.	Firebase is a data store service that provides event-driven libraries with synchronization capabilities. It’s specialized in real-time updates, mobile and collaborative applications. Three patterns for firebase usage are reviewed, each with a different level of involvement in architecture.	Firebase can act as a centralized data store for applications that don’t require custom server-side execution, allowing for fully client-side, multi-user, distributed applications. It can act as middleware between servers and client devices, either as a message queue or persistence service. It can also be adhered to an existing architecture by implementing a subset of real-time features dependent on it, leaving existing client-server infrastructure intact. Firebase uses a local database as cache, and transitions to a local exclusive mode of operation when a disconnection occurs. Synchronization is performed in a ‘best-effort’ manner. It’s implied that this means an always-automatic never-failing conflict resolution strategy.
12	Internet Message Access Protocol	IMAP is a mail protocol and part of the suit of Internet protocols. It includes considerations for mailbox synchronization.	IMAP requires well-formed, unique identifiers for messages. Identifiers must be generated in ascending order. The main reference doesn’t include implementation details as to how a disconnected client, or the server, may compute deltas and issue correct synchronization commands. RFC 4549 includes implementation recommendations.
13	Synchronization Operations for Disconnected IMAP4 Clients, last consulted november 23th, 2014.	A detailed revision and implementation recommendations for synchronization mechanisms in IMAP4 mail agents.	As per the recommendation, the discovery of new messages can be performed through a query that uses the property of ascending order of message IDs. Changes to old messages are detected by performing a state query (FETCH FLAGS) of all message IDs known and detecting differences locally.
14	Architecture Overview | Datomic, last consulted november 23th, 2014.	Datomic is a commercial distributed relational database that stores data as immutable facts, or transactions. Transactions are stored, and not performed until the resulting values are requested, giving all stored tuples a readable state history.	The database state is dependent on time, as a parameter, since all transactions up to a given time are considered. All historic database states are thus stored. The immutability of data allows for extensive caching in client libraries, enhancing their performance significantly since reads don’t require network traffic after the application’s working set is cached. Immutability of facts allows the database to store values in shared data structures. Transactions either succeed or fail atomically. Full ACID compliance is ensured.
15	Python Datastore API documentation - Dropbox, last consulted november 23th, 2014.	Dropbox Datastore is a library available for mobile, desktop and server platforms that uses Dropbox’s servers to synchronize simple relational databases.	Some libraries provide automatic conflict resolution, while other versions promote a mode of operation where attempts of transactions are made until the transaction succeeds or a maximum number of tries is reached. When conflicts are detected, an encouraged way of resolution is to roll back changes, apply deltas, and finally re-apply changes manually. The server reports conflicts and computes deltas. A client can request deltas at any time. A user and permission hierarchy is used, based on the Dropbox service user accounts, and document ownership. Record IDs are assigned automatically. All records have an ID. IDs are alphanumeric values. Dropbox Datastore is intended to be used for user-owned data sets. It’s not a fully SQL-compliant relational database.