Synchronizing: Part 3

A story about some edge cases…

So in the previous post we talked about how we can work with sorted lists in a realtime collaboration scenario. Here are the main takeaways:

  1. Having introduced the order property on the sections of the document in our app, we can store the sections out of order on the server (in the data model) and only sort them locally on the client (in the view model).
  2. By having the order property differ by a large number between sections, we can implement reordering of sections with only one atomic operation.

This blog post is going to expand on the second point here by addressing some of the edge cases that come up.

The first edge case is when a section is added to the beginning or the end of the document. This means we cannot find a number between two order values of the sibling sections.

The solution to this is really simple: just increment the order of the last section by 3000 if adding to the end of the document, or decrement by 3000 the order of first section if adding to the beginning of the list.

The curve ball here is that most people find it odd to have a negative value for the order, but if you think about it, it’s perfectly fine.

The second edge case happens when two users are trying to put two different sections in the same position in the document at the same time. We can’t just take exactly the average value of the order property of the previous and the next section and call it a day! If we do that, we will have collisions happen.

The solution is simple: we can significantly reduce the chances for a collision, if we randomize a little bit around the average value before we set the order property. But is still some small chance for a collision, which brings us to the third edge case.

The third edge case happens if there is a collision, meaning there are two sections with exactly the same order property.

We need a way of sorting them in a stable way. What does this mean? It means that they appear in the same order for all the users that are editing the document, even they have exactly the same value of the order property.

Why is this important? Well there are two possible outcomes if a collision happens:

  1. All users see the sections in the same order and they like the way they are ordered. Because the sorting is stable, it will stay that way, and everyone is happy.
  2. All users see the sections in the same order, and they don’t like it. They will then just change the order, and by doing that eliminate the collision. So again everyone is happy. :)

How can we do this? Well, we need to introduce a secondary sort key. Something that must be unique for each section.

A timestamp is a good candidate. But by using the id of the user who created the section together with the timestamp is even better! So we settled for this solution.

And there you have it! Now you know the secret to creating a sorted list in your realtime collaboration app.

In the next blog post we will look at why it is easier to mark things as deleted than to actually delete them.