GoT: An Architectural Style for Replicated Objects

Global tracking systems, multi-user games, collaborative editors, geo-replicated databases, and real-time collaborative tools are designed around the concept of replicated objects. A replicated object is a single conceptual data unit for which multiple copies exist, one in each node of the distributed application. The reasons for replication are simple: we want the nodes to be highly responsive to local manipulations of the data. Waiting for round-trips to a single, central object would make for a terrible experience at the terminal nodes. Hence, replicas that are, at least partially, autonomous.

However, replicated objects add considerable complexity to distributed applications. Because they are meant to represent a single conceptual data unit, the state of the replicas must be synchronized. This synchronization opens up a Pandora’s box of design and implementation details that are extremely hard to get right. What if two or more nodes change the same fields of the replicas in incompatible ways at the same time? How do we deal with transactional effects, that is, objects whose value depends on the state of other objects? When changes need to be propagated, how can we avoid sending the entire objects all the time to every node? Should we propagate state changes immediately as they occur, or should state updates be buffered, and even throttled? What happens to state updates on replicas upon network partitions?

A common solution to a broad category of synchronization problems in these applications is to use a server-mediated architecture; that is, have one of the nodes be the container of the authoritative replicas.

This solves the issue of inconsistent state updates by making the authoritative node decide what the true state really is. Massive multi-user games, and the ever increasing family of Web-based collaboration tools, use this approach. But even with this approach, the problems around when and what to send to whom make these systems complicated, stateful, and error-prone. Additionally, central servers, although useful for many purposes, are always bottlenecks. Peer-to-peer architectures help in offloading work from central servers, and could be used, if state synchronization wasn’t so tricky in those architectures.

Prof. Cristina Lopes and her Ph.D. student Rohan Achar have been working on this problem for a few years. Their work comes on the heels of Prof. Lopes’ hands-on experience with OpenSimulator, a virtual word server similar to Second Life. Lopes and Achar’s new approach to replicated objects is to embrace the problem as one of version control, specifically decentralized version control. Their conceptual framework is called GoT, the Global Object Tracker. GoT takes inspiration from Git, one of the most popular decentralized version control systems for files. GoT is Git, but for objects.

Programming under the GoT architectural style makes use of an API that is very similar to that of Git: commit, checkout, push, pull, add, etc. Incompatible changes to the same object are detected in the same way that merge conflicts in Git are detected. Unlike Git, however, these applications cannot ask the end user what to do – that would not make sense! Instead, GoT supports programmer-facing three-way merge functions, by which programmers establish what happens when there are merge conflicts in certain objects, types of objects, and even at the scale of the entire application state. These merge functions are of the form merge(original, mine, theirs).

Figure 1 shows one example of two nodes, each with replicas of an object with fields “alive” and “health”. The nodes already share part of the history, specifically the root node and version 1 (Ver1). From then on, they proceed independently with local commits Ver2 and Ver3, respectively. At that point, node 1 pushes its changes to node 2, which detects a merge conflict due to the fact that both nodes independently decreased the value of the field health from 2 to 1. The conflict is detected because both Ver2 and Ver3 have the same parent, Ver1, and both edges include that field. In this case, the programmer-provided function merge is called, in which the merge conflict is resolved by adding both changes and testing if the result is 0, in which case the field alive is set to False.

Just like Git, GoT establishes a separation between the working data (snapshot) that is immediately available to application code in every node, and which may be mutually inconsistent, and the graph of versions that have been committed via commit and shared via push/pull. The version graph is guaranteed to be causally consistent, and, under some constraints, can also be globally consistent. Causal consistency means that every node has the same understanding of the order of state updates, even if the updates end up with diverging replicas (like the resolution of certain merge conflicts in Git, for example). Replica divergence can also be avoided in GoT if the programmers define merge functions that are both commutative (the order of the mine and theirs parameters does not matter for the resolution of the conflict) and associative (given two different conflicts for the same version, sent by two different nodes, the merge order does not matter, i.e. [original, (original, mine, theirs1), theirs2] = [original, (original, mine, theirs2), theirs1]). Under those constraints, GoT is guaranteed to support convergent replicas, even in peer-to-peer architectures.

GoT has been implemented in a framework called Spacetime (https://github.com/Mondego/spacetime). Spacetime addresses several challenges of the GoT implementation in practice, namely the potentially unbound growth of the version graph and the delta-style communication of state updates. Spacetime comes with an interactive debugger, something that is only feasible when node interactions are well defined. That is the case in GoT.

For more information, contact Prof. Lopes.