UC Irvine

Synchronization in distributed applications with shared, highly mutable replicated state often requires complex engineering to maintain low latency for the propagation of updates. At their core, distributed applications with replicated state need to implement some form of version control to be able to deal with concurrent updates and still maintain some notion of consistency. This need leads to complex and ad-hoc code that is hard to maintain and easy to break. To simplify the creation of such applications, I propose the Global Object Tracker (GoT) model, an object-oriented programming model based on causal consistency, whose design and interfaces mirror those found in decentralized version control systems: a version graph, working data, diffs, commit, checkout, fetch, push, and merge. I have implemented GoT in a framework called Spacetime, written in Python.

GoT is designed to ensure causal consistency with low latency updates in all sorts of distributed application topologies. These include peer-to-peer and applications subject to, or requiring, temporary isolation of nodes. The key to being able to do this is a novel approach to storing and merging concurrent updates within the version graph. GoT stores the version history as a graph of updates instead of calculating the whole state at each version. This allows GoT to send delta updates between nodes without having to calculate the deltas. The ability to send delta updates along with the lack of heavy serialization and deserialization allows for the updates to be quickly available. The final state at each node is only constructed when needed.

In addition to the lower latency of updates, GoT addresses three concerns. First, object-based version control systems are typically not suitable for peer to peer networks. The merge strategies used are incompatible with the communication patterns seen in peer to peer. GoT addresses this concern with a novel approach to merging concurrent updates, called the small-step merge. Second, GoT makes the state changes in the system more visible, allowing for powerful tools such as interactive debuggers to be built and integrated, helping developers find and fix errors. Finally, GoT provides these benefits to not just push-style communication but also pull-style, allowing for isolation and partition recovery.

In its traditional form, GoT is impractical for real systems, because of the unbounded growth of the version graph. I present my solution to this problem that adds constraints to GoT applications but makes the model feasible in practice. I show that Spacetime is not just feasible, but viable for real applications, and present performance results showing low update latency.