Mobile & Synchronisation - part 2 / 3

Last blog post I talked about the different approaches to mobile synchronisation. In this article, I will focus on synchronisation without prior context. With two data sets, let's say my local data set (data on my offline mobile) and a remote data set (data from the remote server, changed by other users of my mobile app), that are out of sync after an offline period. I want to be able to get a difference from those two. In this approach, we don't have any prior context. Information like when was the last synchronisation, what happened during offline (logs etc...) is not available.

Bloom Filter

A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. You basically compare 2 hashed codes, because of the nature of hash function you can tell an element is either definitely not in the set or may be in the set.

Invertible Bloom Filter (IBF): Let Magic Happen

For the purpose of synchronisation, we want to know which elements were added and which ones were removed. Replacing a set of hashed values by a more complete data structure we can achieve a clever filter. Instead of storing hashed values, we can use Bucket structure adding information like number of items, key of the item, and hashed value of the item. Using the magic XOR operator with its reversibility nature. We can xor a sum of element together.

xor 2 elements together, xor again and you get our initial element!

Hashing into buckets

In a bucket, the number of items is increased by one, each time we add an item in the bucket. The key is xored with the other keys. A hash function is used to hash the key into an hashed value, itself xored to the hashed sum.

With this same technique, you can spread hashed items into different buckets increasing odds to compare them. The bucket distribution should be uniform and reproducible on both sides (local client and remote server in our exemple).

Using recursive approach, incrementing bucket numbers each time, we build buckets set locally and remotely. With 2 sets, we compute the difference subtracting number of items. In the difference, if the count of elements is 1, we know one element was added (similarly if the count is -1, one element was removed). From the key element, we can hash it, xor it to the hash sum bucket field and get the hashed sum without it (because of the xor reversibility).

Compute difference

The whole purpose of the algorithm is to get a difference with number of item -/+1. You can iterate until you get to that point increasing by 2^level.

How to treat difference

Let's say, I have an item "green circle" that was hashed and spread into 3 different buckets (3 being the default number of hashed functions used for distributing items into buckets). With this difference set, I'm looking for item number equal to 1. I know the green circle was added, so I can removed it from the buckets index 1, 4 and 6 and add it to the set of added items. In index 2, the number of items is 2, so we carry on to index 3. I can remove blue circles from index 3, 4 and 5. etc... At the end of iteration, if I get an empty difference set, I've retrieved of differences. If the set is not empty, I don't have enough information so I need to increase numbers of buckets.

Implementation

Using "What’s the Difference? Efficient Set Reconciliation without Prior Context" paper, 3musket33rs libraires implements the IBF algorithm in Java, JavaScript and iOS.

The different players: Resolver is responsible of computing difference, increasing number of bucket (level) as needed. Set of buckets are called Summary. Summary comparaison produces Difference which hold removed and added set. BucketSelector produces a set of hash functions to uniformly distribute items with buckets. Bucket is the data structure to hold number of items, xored key and xored hashed value.

Want to see it in action? See my next blog post for an example involving JavaScript backend and iOS client.

Tweet