1. Introduction

37 min readFeb 3, 2016

I’d like to talk about a very specific approach on how to synchronize shared data across devices using Stream-Based Data Synchronization. It’s not a common concept, but it has been implemented in various ways in the past decades. I wanted to present this concept in a more attractive way, from a little different angle, along with the code examples and lovely diagrams.

So in this publication, I’ll guide you through what data synchronization is, how to implement a very basic app that synchronizes with the server, essentially do all the ground work first, so that you’ll get the idea what kind of data we even deal with, how to transmit it across the network, then slowly build up to the full solution where I’ll demonstrate the behavior, expose caveats and talk a little about where this concept works best and where it falls short.

1.1 Update 02–11–2016

I also did a talk on this subject at the KeepSafe’s Tech Talk event, video and slides available here.

2. Data Synchronization

2.1 What is Data Synchronization?

Term synchronization in computer science is a bit ambiguous, it can for example, mean coordination of simultaneous processes to complete a task in the correct order (to avoid any potential race conditions). But in this topic, we’ll be mainly talking about data synchronization, as in having the same state across multiple clients.

2.1.1 Example

An example would be a mobile app with a toggle switch, say a light switch. Now, if I have 5 devices in front of me, I’d like to have the light switch state shared across all those devices. If I turn the lights ON or OFF on one device, other four devices should reflect that change. That’s a pretty basic example of data synchronization over network.

Solutions for such problem come pretty naturally to experienced engineers, but for some it may not be as trivial. So let’s play with the Light Switch sample app idea for a little. To narrow down the requirements for this app, let’s say that the light switch state has to be shared across devices via TCP/IP network.

Note: Instead of TCP/IP we could, of course, use any other available technology/protocol such as Bluetooth, AdHoc WiFi, Multi-peer Connectivity on Apple devices, etc.

2.1.2 How Would We Design Such a System?

Let’s make a list of components we need to have to achieve this:

a simple server — which can be a lightweight service (process) written in C using the standard library, or something written in higher-level languages (Scala, Ruby, Python, Java, etc.) using off-the-shelf libraries. For the sake of simplicity, we’ll use a simple web socket server in Ruby that accepts a JSON structure from clients with Light Switch state information, and fans out the new state to other clients. No persistence of the Light Switch state is required.
mobile clients — an app that connects to our lightweight server capable of receiving and sending Light Switch state changes through the web socket. For visualization of these state changes we’ll switch between two different background images (one indicating lights are on, and the other one for when the switch is off).

Both client side and server side code should be very simple to implement.

2.1.3 Client Side

Let’s check the client side code first. We mentioned we’re going to use WebSockets to keep a persistent connection between the client and the server. For me the one that kind of sticks out is Starscream, it’s clean, very easy to use WebSocket client written in Swift.

We shouldn’t need more than two functions to do the job of sending and receiving Light Switch state updates in our transport layer.

What the function above does is it wraps the Boolean value into a dictionary, serializes it into a JSON structure (which is a String) and then sends it over the open Web Socket connection.

Now we need a function to do the similar operation on the inbound side. In an event of receiving a JSON structure, it should try deserializing it into a dictionary object and call a delegate method to let the app data model know of the new Light Switch state.

The UI controller implementation should be symmetrical to the transport layer implementation. Again, two functions — one sending the controller’s Light Switch state to the transport layer whenever the user taps the button, and the other one should be an implementation of the delegate callback that the transport layer calls, which toggles the switch in the UI.

This pretty much sums up the client side implementation.

2.1.4 Server Side

Let’s take a quick look at how the server-side implementation should look like. I chose to write the server side implementation in Ruby using a library called em-websocket.

There’re two main parts to the code above. We used channels to construct a notion of followers (or subscribers, if you will), and when a client connects to the server it gets added to the channel (@channel.subscribe). Then, as soon as the server receives a light switch change (ws.onmessage) from a client, it unwraps the JSON structure, takes out the Light Switch state (:lightsOn), stores it into the globally variable (@lightSwithcState) and then pushes a newly constructed JSON object to the channel, which then gets emitted to all of the channel participants. This is how we achieve the fan-out.

So there you go, a pretty basic approach to data synchronization.

2.2 Other Use Cases

In our example (chapter 2.1.1) we demonstrated how to synchronize an ON/OFF switch across multiple devices — it’s not a common use case, but it was good enough to demonstrate the basic concept.

There are a lot of applications we use every day that use data synchronization to share the same state across devices, let’s identify a few with examples:

e-mail — most IMAP clients get up to date by fully synchronizing the list of all e-mails and their unread state. All clients for the same user receive new messages at the same time; marking a message on one client as read reflects the change on other clients as well.
messaging — having the same view of messages and conversations across clients; web, mobile, etc. Receiving messages and their delivery and read receipts from other participants on all the clients.
photo sharing — shared photo stream with all subscribers.
file sharing — backing up a content of a folder from the local filesystem to the cloud.
online text and spreadsheet editors — having multiple users editing the same text or spreadsheet document at the same time. Seeing the text coming in as users type in different paragraphs.
multiplayer games — same state of the world for all players on the same server. Things as trivial as picking up ammo or weapons from the ground, etc.

The list goes on…

2.3 Types of Data Synchronization

Now that we had identified a few of these use cases, let’s figure out what kind of data we even deal with in those cases.

We mentioned file sharing — that means file content and directory structure replication across clients. If I add a file to the shared folder on one of my computers, I’d like that file to appear on the other computer too. Same if I modify that file on one computer, I want that file along with its content to be copied to other machines too. The easiest way to implement this would be to copy the whole directory (along with all the files and sub-directories) every time we change something (add or remove a file, change the content in a file). This would work, but that simply does not scale. If I keep adding files to the directory, the copy process would become longer with the count of files.

A better way to synchronize a file / directory structure is to compare them, recognize differences and only copy what doesn’t match. This is what we call file-synchronization, Rsync is a very nice example of this. It’s similar to how Dropbox, iCloud Drive and all these file hosting solutions minimize the work in order to get the files in sync with all machines.

Copying file’s content over to other clients every time we touch it on one machine can be a rather expensive operation — well, it depends on the size and type of the content — but let’s say we’re dealing with a multiline text document, a source code file for example. Why copy 10 kilobytes of content, represented by hundreds of lines of code, where we just wanted to change a single line of code:

In above example, I forgot to specify optional chaining in the line 89:. That is just a single line of change. One way of describing this content change could be through the unified diff annotation, which is still lighter than copying the whole file over.

Due to the nature of the document’s data structure (lines of text separated by newline characters \0x0a), this was fairly easy. That’s how distributed revision control systems describe and apply changes to text files. But at the end of the day, we synchronized document’s content change.

What about our Light Switch app example (from chapter 2.1.1)? It’s nothing more than data model synchronization.

As with file and document synchronization, we can just make a copy of the data model and transfer it over the wire to other clients, which is exactly what we did in our example app. We could afford this in our Light Switch example app, seeing that the model was extremely small — it’s a single instance of a boolean value private var lightSwitchState:Boolean, you can’t get smaller than that.

Should the model be more sophisticated (having multiple fields, mutable collections, relationships with other structures), copying the whole structure along with its values (whole object graph) over and over again becomes expensive.

2.4 Approaches to Data Synchronization

There are different ways to make our data up-to-date, as we’ve learned in the previous chapter. The most naive way is to just copy it, which in a lot of cases, is less than ideal. A better way to get the existing data up-to-date is to only apply changes to it. Let’s examine both approaches.

2.4.1 Absolute Synchronization (copying)

Copying and replacing the data (file, document, data model) is perfectly fine, when we don’t care for the amount of data we need to transfer since the server will always return a fully populated dataset. Also works well when the synchronization is uni-directional, meaning the client always asks the server for the source of truth (e.g. refreshing the weekly weather forecast, or refreshing a list of RSVPs).

This type of synchronization is also known as the wholesale transfer.

The other drawback of copy based synchronization for clients is not only the potential higher bandwidth cost due to transmitting the same data for the most part (which we call data redundancy), but also if we need to be aware of the changes when replacing our old dataset with the newly up-to-date one, we’d need to locally compare (differentiate) the two datasets first, before replacing the old one. That process burns twice as much memory (since you need to hold both sets in memory) and CPU time for as much as there are elements in both sets (which gives us the O(n ⋁ m)).

Suppose you’re invited to a dinner party and you ask the receptionist “Who’s here?”. That person will respond: “There’s Alex, Blake, Caroline, Dan, Emily and George.”. In your mind, you’ve made a list of guests from what you just heard. Now one of the guests leaves, but you weren’t paying attention, so you go ask the receptionist, “What about now?”, and the person responds: “There’s Alex, Caroline, Dan, Emily, and George” — it’s like talking to an idiot. So in order to figure out what has changed, if anyone left or someone new joined the party, you’d need to remember the list of guests from before and run it against the one you just heard and check for differences.

2.4.2 Relative Synchronization (based on changes)

You’d be better off with an answer like: “Blake just left”, instead of listen to the person go through the whole list of people that are still at the party. That’s assuming the person you’re asking knew when was the last time you were paying attention. It just seems like a lot of work for the receptionist to keep track of what others take notice off. So, to make it a little easier you should rephrase the question to: “What has happened after I arrived?”.

The receptionist would just go through the list where he keeps the names of the guests joining and leaving the party, look for the record when you arrived and narrate all the events that happened after that.

That is an example, when you update data only with small differences, based on previous events that you’re already familiar with, to avoid copying the whole data set. These small differences or changes are also known as deltas.

2.5 What are Deltas?

Delta encoding is a way to describe differences between two datasets (file, document, data model, etc.). We can use these short pieces of information to apply to our dataset (in a form of mutations) to get it up-to-date and from what we’ve just learned, is that it can significantly reduce the data redundancy in synchronization processes.

2.5.1 How to Encode Deltas?

Of course, depending on our application, we’d want to encode the deltas in the way that is suitable for our application data model. Taking a look at the few examples we’ve set out in chapter 2.3, applications can work with pure arbitrary data (binary files), document (text files, XML, spreadsheets), data model (data structures), etc.

But generally, we’d want our deltas to give us instructions on how to modify our old data set, so that it will match the new one, based on three simple operation types:

insert — adds new values to our data set
update — updates existing values in our data set
delete — deletes existing values from our data set

If you remember chapter 2.3 already demonstrated one of the delta encoding approaches suitable for text changes — it was the example, where we had to change a single line of text in a multi-line text file (swift source code). How do we deal with other kinds of data structures? Let’s got over a couple:

Delta Encoding Example of Binary Data

Given a file of arbitrary data (of 80 bytes):

we’d like to change the value of tree bytes starting at offset 0x03, and append 16 more bytes at the end of the array. We could encode the delta as:

Note that I chose to describe the data structure above using a JSON format. We can serialize the delta information in any format that suits the purpose. Here are a few from the top of my head: Thrift, Protobuff, CapnProto, however, you can choose to implement your own proprietary serialization protocol.

We could use the exact same delta encoding approach to describe a change in a text file — if we bring the example from chapter 2.3 to mind, the one where we used the unified diff patch to update a single line of code.

Don’t be mistaken, the unified diff patch is still a delta, encoded differently, though, but we could get rid of both, the before and after values (the lines that start with --- and +++) in favor of inserting a single character at the right location, which gives us the same result:

Delta Encoding Example of a Custom Data Model

Back to our guest list from the previous chapter 2.4. Client’s data model shouldn’t be more than just a set containing the names of the guests that are present at the party. Based on the first response from the receptionist, the set would contain the following names:

Asking the recipient for any changes that have occurred after a certain period, the response would contain an encoded delta telling the client to remove “Blake” from its set.

When applying the delta onto our model, the dataset should contain following names:

3. Stream-Based Synchronization

There are plenty of approaches to get our data model synchronized with the server, we’ll be taking a closer look at the synchronization approach that takes the advantage of persistent streams. Now, before we dwell on what stream based synchronization is and how we can leverage it, I’d like to discuss the motivation behind it — specify the requirements, if you will.

3.1 The Motivation

In most cases, developers want to solve the synchronization of shared data model between clients and the server with minimum data redundancy. This not only lowers the storage and bandwidth costs of a hosted system, but also saves CPU time. We already discussed this a little in chapter 2.4.1 — Absolute Synchronization, and chapter 2.5 — What are Deltas?.

One of the important requirements to most folks is also speed. How fast we can get a user action delivered to the server — by “user action”, I mean a mutation that a user caused to his data model that needs to be distributed across other devices. So in other words, get the deltas off of the clients, onto the server and back to other users’ devices as quick as possible.

figure 9 — Real Time Distribution of Deltas

Another key thing is having short and fast writes on the server, which lowers the response time of a client’s request and also reduces the load on the system — all these things aim toward good concurrency characteristics.

A very important aspect to system design is scalability. A system can grow with the number of users it serves, as does with the amount of the content generated its by users. So when modeling the data structures (schema), we must also account for data distribution and replication, which should be easy and painless. Having a distributable system not only provides fail safety — in a case of outages and data corruption — but it also makes it easy to employ load balancing approaches.

A feature we tend to forget about is also offline support. Synchronization logic should not prevent the application logic from operating autonomously. Your synchronized photo library (camera roll) is accessible on all your mobile device. Imagine if you couldn’t take photos, edit or remove them from your library, when you’re out of the network connectivity?

3.2 Stream of Mutations

Finally, we get to talk about stream-based synchronization. Remember how we synchronize our Light Switch apps in chapter 2.1? Clients have a bi-directional TCP connection to the server, and every time a user flips the switch, that change — the mutation on the model — is sent to the server that distributes the change to other clients.

Put differently, clients with an open connection to the server are receiving a stream of live events — events that describe the changes to the model. As long as the clients retain the connection with the server, their model will be up-to-date.

Cold Light Switch clients, those are the clients that have never been synced with the server, will get updated as soon as they establish a connection and receive their first event. We had already learned, this argument is true because our Light Switch data structure is very light. It only shares a single primitive value, a scalar, or more specifically, a boolean state — is the switch turned ON or OFF. Encoded delta for a scalar property by it self represents a new value, you don’t need the previous state of that property where you’d apply the delta onto, to get it to a true up-to-date state.

But, imagine a data structure for an app that operates on a little more advanced data model, and since we’re in the spirit of exercising our theory knowledge on examples, let’s try it on a different kind of application. Let’s build a To-do List app!

3.2.1 Example (To-do List App Data model)

Let’s write down use cases and support them with a data model:

Application provides a live synchronized list of to-do tasks;

2. A task element contains:

A true or false value indicating it’s been marked as complete;
It also contains a string description of the task;
And a numeric value annotating a color coded label (0 = black, 1 = red, 2 = orange, 3 = yellow, etc.)

3. Tasks can be added to the list, edited or removed from the list;

These three methods should be enough to operate a list of tasks on the client. They support all user actions we care for:

creating and inserting a new task to the end of the list;
editing an existing task with new a new completion state, task description, or a new color coded label;
deleting an existing task from the list;

3.2.2 Example (To do List Sync Data model)

So how do we describe these user actions, so that we can transmit them over the network? User actions cause mutations to our model (which are Todo.Task and Todo.List), and we need to encode these mutations as deltas. Well, I prefer to use the word Sync.Event to symbolize an action.

How would an event structure look like in our code? It is pretty close to the Todo.Taskmodel. Also, keep in mind that objects we want to use in our synchronization logic should be simple concrete objects conforming to some serializable and de-serializable protocol (of your choice) since we’ll be transmitting them over the network.

You might be wondering, why couldn’t we just use or extend the existing model (Todo.Task), since they are pretty much symmetrical? It’s because we’ll need a little more data that will help us at the sync process, but we’ll get to that later.

So, if a user creates a new task in the app, the app will emit a Sync.Event over the network. Note: again, I’m going to use JSON-like notation to describe objects with values.

If a user marks the task as completed, app will generate and emit an event looking like so:

figure 16 — Marking an Item as Completed

3.2.3 Example (To-do List Transport)

Of course, our synchronization logic also needs an access to the transport, how else are we going to send and receive the events?

3.3 Let the Streaming Begin

We now have an idea, how events transmitted to a stream look like. Client generating the events sends them to the server, then server’s responsibility is to broadcast those exact changes to other peers. These events are received by all active clients, and as long as the clients remain connected to the server, they are going to have a consistent dataset.

figure 17 — Streaming To-do List Mutations

However, if a client comes online a few moments later, it might’ve missed events which are important to reconstruct the dataset. What good is a Sync.Event telling that a task was completed to a client that never saw the original task to begin with?

Such client is considered “out-of-sync”.

3.4 Persistent Stream

Don’t worry, having clients being wedged in an out-of-sync state is recoverable. One way, of bringing an out-of-sync client back to a consistent state would be to replay all the events, that have happened while the client was away. Which means that the server’s responsibility besides broadcasting the events should also be recording all the events that come in. In other words, we need to persist the stream of events.

We can think of a persistent stream as a linear magnetic tape, a storage with WORM behavior. It’s where we’re only allowed to append the events at the end, and we can’t mutate any of the existing events once they have been written down. Or another way to look at the persistent stream is like a journal of all the events that have happened.

A lot of distributed databases are married to this idea, their performance is better, when you don’t mutate existing records. In the NoSQL world, more specifically in column-oriented databases, the data structure is (naively) considered as a table with ever growing rows. Unfortunately, our data might not be replicated in the same manner across all distributed database nodes and clusters — there’s no way to guarantee the same order in them as values get written, this is due to the concept known as eventual consistency.

Asking an eventually consistent database for a record based on an offset inside its row might yield a different answer, depending which database node or cluster you end up talking to. That’s why you ask for the records based on their values, and you can decide which values you want indexed as records get written. But still, eventually consistent database cluster cannot guarantee it will yield the same or any result when asking it for a record based on certain key, since the record might’ve not been written nor indexed yet.

In our To-do List app example, we gave our Todo.Task objects their own identifiers, client generated UUIDs. This let’s us reference Todo.Tasks in Sync.Events when applying mutations onto to model. These identifiers could also be useful to fetch all. Sync.Events representing the final state of a Todo.Task from the database, if database kept an index of these identifier values. But as we figured out, in certain edge cases (due to eventual consistency), a replicated database cluster might return a different result set from another.

So, how does a client know for sure it’s got all the events? If you remember, one way is to always copy the whole dataset (absolute sync, chapter 2.4.1). Or we could implement some sort of integrity check, that would calculate a hash based on Events’ values. But still, that would only indicate there’s a mismatch between our datasets, we’d still need to copy the whole set. Sure, we could order and section our dataset based on a key, and hash each section individually, but let’s be honest, we’d still be calculating and transferring a lot more data, than it’s truly necessary.

3.5 Event Discovery

This is where sequencing comes in handy. Giving a Sync.Event a unique server-generated cardinal value, we could leverage it as a lightweight index to our events. In math, this is also called a countable ordered index set, where the value of the n-th element is equal to its zero-based index n. The maximum value which is also the value of the last element in such index set denotes its size (the count of elements).

Let’s extend our Sync.Event model with a new property called seq:

As clients generate and upload Sync.Events, the server picks them up, assigns them a sequence value and persists them to storage. With every event written to storage, the sequence value is incremented. The first event written to the stream has a sequence value of seq: 0, second one get the value of seq: 1, etc. You get the idea how incrementing integers goes. And yes, the work of assigning sequence values can be put off on the database, if the database supports auto incremented record sequencing.

For a recently online client to figure out which events it might’ve missed, a basic inquiry of “what’s the last sequence value written to the stream?” is enough. With the server response client takes the number and stores it. The best place to store it would be in an object, where we’d keep all information associated with a stream. For now, we’re only interested in what is the most recent event’s seq value written to the stream:

With that information, a client can run through a list of seq values of the events it’s got on itself from before, and diff it against a set of integers going from zero 0 to whatever the number of events server told us it has. Now client knows exactly which events it needs to pull from the server (based on a diffed set of seq) in order to get to a consistent state with other peers.

What better way to test this theory, than through an example, huh? Say we’ve got a few clients connected to the server, and server’s stream is completely empty. I’m going to numerate the steps in this example, because I’ll be reference them.

1. Through the use of the To-do List app, clients have generated 10 events. All these connected clients were fortunate to receive the Sync.Events as they got published to the stream in real-time.

2. One of the clients went offline (due to either poor connectivity, or because, the user decided to put the app away).

3. Meanwhile, other clients have generated and published 5 more events to the stream.

4. The offline client (from 2. step) comes back online, when 5 more events get published. This now makes it a total of 20 events.

5. The same client, that’s been offline for a while has got a few events missing:

We described such client as being in an out-of-sync state. It’s got a few Sync.Events that don’t mean anything without their predecessors.

6. Client creates a set of seq values from all the events it has and subtracts it with a set of integers ranging from 0 to 19. Which results in a following set of integers:

Note: working with NSIndexSet would be far more efficient, but I wanted to use classic sets for the sake of simplicity.

7. With the set of seq annotating the missing events, client asks the server to hand out these events, which brings the client back to a consistent state.

4. Event and Model Reconciliation

By now, we’ve answered the question on how to design our application data model (Todo.List, Todo.Tasks), how to design the synchronization model (Sync.Stream and Sync.Events), we also know how to discover new events in case we missed some (based on stream.latestSeq and Sync.Event.map({ $0.seq })).

But we never asked which part of the client side code is actually responsible for vending these Sync.Events, nor how do we turn incoming Sync.Events back to our objects.

4.1 Outbound Reconciliation

If we have to pick a name for this process of turning model mutations into synchronize-able (syncable for short) Sync.Events, let’s call it “Outbund Reconciliation”.

One of the spots to put the Sync.Event creation logic is where we take the user actions, in the heart of our application’s logic — that’s in the to-do Todo.List class. In our case, this is really affordable, because the Sync.Event model can hold the exact information to describe user actions the Todo.List logic provides. If you take a close look at the Todo.Listinstance methods and the Sync.Event model, you’ll find some resemblance. Sync.Event.type defines the method calls, and the rest of Sync.Event’s properties define the arguments we pass into the methods.

figure 22 — Resemblance Between Event and List

Let’s see how these methods play out:

Creating Todo.Tasks

Telling the to-do Todo.List object to create and put a new Todo.Task on list will now also vend an Sync.Event:

Updating Todo.Tasks

Invoking the update(identifier:completed:title:label:) method on Todo.Listinstance will give us an Sync.Event of type update:

Removing Todo.Tasks

And removing a task from a Todo.List is no different:

Publishing Sync.Events

And this is how we turn model mutation into events. The only thing that’s left for these Sync.Events is shipping them off to the server and on to the stream, so that the other clients can receive them.

4.2 Inbound Reconciliation

What do other clients do with Sync.Events, once they receive them from the server? These Sync.Events have to be turned back into objects. It’s a process we can name “Inbound Reconciliation”.

The incoming events (pushed via transport) come in through the transport delegate method, implemented in the sync client:

As with the Outbound Reconciliation logic, described in chapter 4.1, Inbound Reconciliationlogic can reside in the to-do Todo.List class.

We’ve made a little mess here, haven’t we? By adding the extra logic of vending Sync.Events to the Todo.List manipulation logic in chapter 4.1, we’re not sure anymore which part of the Todo.List class logic should be in charge of mutating the model, should it be the apply() method or the other three methods? We don’t want to write the same code twice, nor we want the logic responsible for calling apply() knowing anything about the Todo.List model, except that it’s capable of applying events. What we’ve done there could be considered an anti-pattern by some critics.

The three methods (create(), update() and remove()) have two parts to it: manipulation of the model and generating and returning the Sync.Event. Therefore, whoever owns the Todo.List instance, is by this definition responsible for sending the event returned by those methods to the stream — this is also considered an anti-pattern.

See for yourself:

One way to refactor the code would be to extract the model manipulation logic out of those three “user action” methods, so that the apply() function can also use it. The other way would be to make the apply() method be in charge of model manipulation.

This way, the user action methods are now only in charge of vending Sync.Events, which solves the first anti-pattern. We can also delegate the Sync.Event sending by using protocols, this way whoever owns the Todo.List instance, doesn’t have to be in charge of sending the Sync.Event to the transport logic (event publication) — this solves the second anti-pattern.

With these two protocols, the synchronization logic doesn’t need to know anything about the Todo.List type, and whatever owns the Todo.List instance, doesn’t need to be responsible for taking the vended Sync.Events and passing them to the Sync.Client.publish(event) for publication.

Here’s the implementation (I’ll strip out the method comments, to make it a little shorter):

On the synchronization logic side, Sync.Client now just has to implement the method dictated by the OutboundEventReceiver protocol, this frees the Todo.List instance owner from responsibility of sending the event to Sync.Client.

4.3 Offline Support

Sync logic (Sync.Client.publish()) might be sending the events to void, in case the connection to server’s down. And when clients miss relevant events, they get in an out-of-sync state.

One way to avoid this is by not allowing any user action on the Todo.List data model, but this completely disables the use of the app while the user doesn’t have connectivity.

We have to make sure those events get published at all costs. Instead of trying to publish the events directly, we can put them into a queue (Sync.enqueue(event)) that gets drained with publication (Sync.client.pulish()).

Here’s the small piece of code to support the theory:

With offline support, we can now create tasks, modify them (update the complete state, color label, and its title) even when the client doesn’t have the connection to the server.

4.4 Reducing the Edit Distance

Picture a scenario where the client is offline and we create a new task. And while the client is still offline, we toggle the “complete” check on the task on and off — we do this a few times.

Client generated as many events as there are times we tapped the checkbox. Why would we want other clients to know of our indecisions with the task completeness? We don’t want to pollute the stream with these intermediate events.

In order to avoid that, we’d have to coalesce the changes we made on the model. This is a process known as reducing the edit distance. Again, this raises the question, where should we implement this logic? We could do it in the model logic itself (Todo.List), but what if we have more than just one app model, then we’d have to write this logic twice for different models?

The best place to perform the coalescing process would be where we collect (queue) our events for publication, which is in our Sync.Client.enqueue(event) method. The coalescing logic, however, we can implement straight in the Sync.Event class itself. The algorithm should be relatively simple, it just needs to follow a small set of rules:

Update Event for an object should merge the values of the Insert Event and other Update Events into a single Insert Event.
If there are only Update Events in the queue, and no Insert Events beforehand, values are merged into a single Update Event.
Last Update Event defines the final state of the property it mutates on the object.
Delete Event for an object clobbers any previous Insert Event or an Update Event.

With event merging process, the client will try to reduce the edit distance of queued events, thus making the stream a little cleaner.

4.5 Conflict Resolution

In concurrent systems, a conflict arises every time two or more nodes (clients in our scenario) work on the same resource at the same time, and one of the nodes takes the action before the other one does. You can also call this a race condition or even say that one of the nodes wasn’t fully up-to-date with the resource’s state, before doing the mutation and then publication.

Our example application could potentially have to deal with a conflict where one of the clients wants to update the completed state of a Todo.Task when one of the other clients had already deleted the same task. The Sync.Event.Type.Update event could get written to the stream, which would surface upon other clients and cause conflicts in the inbound reconciliation process.

Here are a few ways to resolve a conflict like that:

Bring the deleted task back to life, by ignoring the delete event that caused the Todo.Task to disappear, since update event came in later — also known as, the last writer wins.
Delete event tops any other events that come in later for the same task — known as, the first writer wins.
Surface the conflict to the user in a form of a UI dialog, and letting the user decide what to do: “Task was deleted by another user, revert the change?”

All are valid conflict resolutions, but most would agree, bothering users to manually resolve conflicts is not the best experience. It’s safe to say that people are used to the second conflict resolution approach — trying to write a comment on Facebook under a post that just got would be an exact analog to this. And our logic already supports this. If we go back to our Todo.List.apply(event: Sync.Event) implementation, you’ll see that case .Update is impossible, as the task cannot even be found anymore.

Depending on the model of the application, conflicts can vary and resolutions could be more sophisticated.

5. Order of Events

The event order is a very important subject and needs it’s own chapter. Sync.Events are written and read to and from the stream in a linear fashion. In fact, the server sequence can tell us the exact order of the events as they were written to the stream. This type of order is also known as the total order. The good thing about it is, that it’s easy to work with. It’s predictable and requires no additional logic on the server nor the clients. When the model reconciles with events the outcome will always be the same:

task objects will be in the exact same order, dictated by the server defined Sync.Event.seq;
task object mutations will be applied in the same manner on all clients;

5.1 Total Order With Batched Sequential Writes

In this type of event order we need to assure that queued events get published by the clients in the same order they were put on the queue (client-side). Therefore exclusive write access is required by any client wanting to send their queued events to the server. Allowing other clients to write their events during that time would risk interleaving the events on stream and could cause the model inconsistency (race-conditions).

This does not satisfy our requirement we set out in the chapter 3.1 having fast writes on the server. As I’ve pointed out, having an exclusive write access blocks other clients, which can ruin the experience for other users.

Note: Total order also doesn’t guarantee, the events will be put on stream as they were generated by all clients, what a FIFO order, on the other hand, would. But FIFO order can’t be implemented with an undetermined number of clients, nor does it provide a good experience, due to the requirement that batches be written in the same order as they were generated.

The other problem with this kind of ordering is also, that it doesn’t work well with offline support — when users generate mutations while under poor network conditions or no network connection at all.

And here’s why… Remember why conflicts occur? Because of the race-conditions that happen in concurrency. Put differently, it’s because some clients have the privilege to get their events written to the stream faster than the other underprivileged clients? That could render the queued Sync.Events that come on stream later nonsensical (e.g. applying an update Sync.Event onto an object, that was previously deleted).

If queued events by an offline client got published with a significant delay (for example a day, or even worse, a week after a user generated them), the Todo.Tasks would appear at the bottom of the list, since those late events would receive a high seq value from the server. That might make such Todo.Tasks fall out of context, and we don’t want that — assuming of course the order of Todo.Tasks tasks is important.

5.2 Causal Order

And since the order of Todo.Tasks should reflect the same order that the user percieved while creating them, then the total order comes out of the question. Events need to be reconciled with the model in the same order as the events were generated by the clients, and not in the order as they were published in the stream. I know, it’s hard wrapping your head around that statement. So, does that mean that different clients may see a different order? That’s exactly what that means.

Due to the fact that the generated Sync.Events is the effect of the user responding to the UI and taking action, basically requires the Sync.Events to be applied onto the model under the same condition it was in when the events were generated by the author.

In a perfect world, where we’d have a constant connection to the server and the information would be universally available in an instant (also known as faster than the speed of light), we wouldn’t have these problems. But since that doesn’t exist, we need to work with what we have.

5.2.1 Don’t Even Think About Timestamps!

So, if we can’t rely on the server generated seq to give us the correct order the Sync.Events should be processed in, what other key could we order them by?

You’re thinking about timestamps aren’t you? Even though the title of this chapter said not to. Alright, let’s have it your way. Say we do rely on client dictated timestamps based on the system’s real-time-clock. How can we guarantee that all client’s synchronized against the same Sync.Stream have their RTCs set to exact same time? Sadly neither the NTP nor GPS time synchronization can guarantee perfect sync without any time skew. Additionally, relying on external synchronization processes results in an extra moving piece in the whole machinery and presents a potential point of failure.

Another argument against timestamp approach is that users could mess with their system time, by manually overriding it during the use of the app. If only a simple system clock change can mess with the final model outcome for other peers, that makes for a very fragile app. And we don’t want that.

5.2.2 Version Vectors

There is a way to reconstruct the Sync.Event order as it was perceived by the author (the client that generated it). All we need to know is what the client saw before it generated the Sync.Event. That little extra information is also known as “happened-before” relation. It allows us to track the event causality, which is the basic principle in a few of the optimistic (lazy) replications algorithms.

From Wikipedia on optimistic replications:

Optimistic replication (also known as lazy replication) is a strategy for replication in which replicas are allowed to diverge.

With this notion in place, we allow clients to operate independently from the server and perform mutations on what their view of the model is. When clients do eventually come back online and publish all the Sync.Events they generated, it will bring other online clients to a consistent state — we know this concept as eventual consistency.

How does the “happened-before” information look like? It’s as simple as the client stating: “for the event I’m about to generate, this is the last event I saw” — this establishes the happened-before relation between events. This extra piece of data could piggyback on the events, and we can take the advantage of the seq value to point to Sync.Events that happened-before, due to seq being a constant value generated by the server. We can call this value the precedingSeq and add it to our Sync.Event model:

Unfortunately, we’re not done yet… As I’ve mentioned, having long batched publications can affect the server performance and block other clients from publishing. If we break the publication into a little more granular posts, it’ll give other clients a fair chance to publish their events on stream due to short and faster writes to the database. But then we lose the information of the partial order of events, previously held together by a batch.

The solution is simple, we just need to add a client generated seq which will tie the events that would otherwise be sent together in a batch. We can call this property clientSeq. It’s similar to seq, the value maintained and incremented by the server, but in clientSeq’s case, it’s the client that increments the value. But in order to prevent the value from growing out of bounds, we can reset it in an event when we assign a new precedingSeq value.

This gets us to the final Sync.Event structure:

Our model doesn’t require this, but we could equip the Sync.Event structure with an additional clientId, a value that’d be unique across the clients. That would allow us to cluster events published by a distinct client together, even when events are interleaved with the same precedingSeq and clientSeq.

With causality tracking, our Sync.Events can finally be reconciled in the exact order as they were generated — or what we like to call “causal order”. That’s true even if the events on stream are written completely out-of-order. Since this allows us to publish the Sync.Events on the stream in an unordered fashion, there is no more need for sequential batched writes to our database, meaning that we comply with the “fast-writes” requirement that we mentioned in the chapter 3.1.

The other benefit of the casual order is also that it minimize the conflicts that can occur in concurrent systems, since the order will assure outdated events (queued and published later) are applied onto the Todo.List model after the events the client saw when it generated.

figure 32 — Outdated Events in the Right Spot

Due to the new ordering regime, we need to fix a few parts of our code. The code that reduces the edit distance:

and the code that applies the events onto the model:

Now, both inbound and outbound processes take the Sync.Events in an order that makes a little more sense.

The whole inbound and outbound reconciliation process and our data structure is essentially what version vectors describe, we just used different names and terms:

Sync.Event.precedingSeq pointing to happened-before event’s seq is == vector pointing at a certain version of the object.
Reconciliation process that gets our model up to date == update rules replicas use to synchronize their data.
The other difference compared to other implementations that use version vectors for causality tracking is that we don’t encode the happened-before information as a copy of a previously reconciled state of the object.

6. Advantages

We can just check off the requirements we set out in the chapter 3.1.

Stream-based synchronization is a nice way to have a single shared source of truth where numerous clients can synchronize against. This kind of model reduces the data redundancy compared to the user-centric data model, where most of the data is duplicated. If a server needs to fan-out the same Todo.Task to all participants, it not only takes a lot of storage space, but also burns more CPU time.
Deltas (Sync.Event) generated by clients are cheap. It is a very lightweight data-structure, which means it leaves a very small footprint in either memory or the database (depending on what we use), and doesn’t take much CPU to serialize it, nor bandwidth to transmit it over the network. User actions can therefore be sent off a device relatively fast.
Server implementation is short. Generally, it’s job is to provide clients a place to put and read the events to from. This means minimal CPU usage.
Due to the small Sync.Event footprint, server writes are short and fast. This allows for higher concurrency, compared to writing fully hydrated application model into the database.
The data model where we only append elements at the end of the stream is easy on the data replication processes. Most distributable databases work well with this, which makes our backend scalable.
Event discovery and causal order in our reconciling logic can account for missing events and will eventually catch up, thus making our clients work well with distributable systems having an eventual consistency model.
Attributable to the distributable data and simplicity of the data structures, implementing load balancing is fairly easy.
For the same reason, that also makes our clients eventual consistent, which means that we allow clients to continue operating offline. Once the client comes back online, it will reconcile with the rest of the peers.

7. Disadvantages

There’s also cases where stream-based synchronization falls short:

Where server side implementation might be small and simple, client’s synchronization logic is far more sophisticated.
Rogue clients can pollute the stream with unnecessary event publications, which could slow down clients that need to catch up.
Cold clients must read the entire stream to get into a fully reconciled state. But since the streams can only grow with the use of the app, cold clients will take longer to get fully synced. That costs time, bandwidth and CPU for clients, which might not be ideal, depending on the application model.
Implementing partial-sync to avoid reading the entire stream is not straightforward. Partially read stream is the same as if the client did not get all the events, which renders the model inconsistent.

8. Possible Optimizations

Most drawbacks of the stream-based synchronization are related to clients doing too much work. Partial-sync, which I mentioned as a solution to this nuisance, is not easy to implement. In most cases, it’s an application specific problem, there’s no generic approach to solve all cases.

A partial-sync approach for our To-do List example app could be as simple as just fetching 10 most recent Todo.Tasks on the first launch (cold-state), and let users “pull to load more tasks”.

But unfortunately, it’s not as straightforward, as you might think. In our case, where we have a list of Todo.Tasks and the order is prescribed by the clients, it’s difficult to know exactly what to pull down from the stream, since all a cold-client knows is how many events have been written to the stream.

If a client wants to load 10 most recent Todo.Tasks, it cannot simply load the last 10 events from the stream, since seq values don’t relate to our Todo.Task objects. What the client could do is to carefully backtrack the stream — read it in reverse in small chunks and stop, once the model satisfies the condition. This is not the ideal approach to implementing partial-sync, we allow for streams to have a sparse and unordered distribution of events. Backtracking such a stream means that the client may run into a lot of un-processable events, because their preceding events are missing.

As I pointed out in the Event Discovery, chapter 3.5, clients address events by their seq value, since that kind of an index is easy to replicate with a simple math formula (linear function). Unfortunately this index only helps us discover missing events, and not the actual Todo.Task objects and their mutations.

A possible solution to knowing where the object inserts (Sync.Event.Type.Inserts) and their mutations (Sync.Event.Type.Updates) are by building a secondary index to the stream. An ordered index that would point straight to the events client would need to grab in order to reconcile them into a fully up-to-date objects. However, such approach introduces an additional layer in the whole synchronization process — but that’s for another time.

Who Am I, What I Do?

My name is Klemen Verdnik. I’ve been programming from a very young age, and I’ve quickly become fascinated with low-level programming — things like writing audio and image processing routines, tight loop optimizations, anything where there’s something to be processed and delivered in near real-time.

As a teenager I built a ton of hobby projects, including my very own DSP-powered digital graphic equalizer. One of my early employers was a high tech company from Slovenia called Ultra, where I had an opportunity to work with many teams on various cool tech projects, such as a fleet management system called TalkTrack (before smartphones were a thing) and later on, a team that developed a mobile payment solution called Margento (before Apple pay was a thing).

Later I joined a start-up called vox.io, where we built a pretty cool telephony / messaging solution for the web and mobile devices. A few years later I helped start a company together with my colleagues called layer.com, where we built an awesome messaging platform. It’s at Layer where I helped build the various synchronization protocols with a devotion bordering on obsession.

Big thanks to Tjaša Plesec for turning my whiteboard doodles into beautiful graphics and putting up with me.