Compare Small Versions that Wrap Around

Almost all stateful services (data store, cache, etc.) have versions stored along with each piece of data. The version can be in the form of a timestamp, version (a.k.a logical clock), or even better — Hybrid Logical Clock.

If it’s a data store, HLC is almost always better than timestamp or version. Because HCL is strictly more powerful than either timestamp or version and data stores are usually OK with sparing a few extra bytes to store it.

But there are legitimate cases that one might prefer versions. E.g. you might want to store a small version (2 bytes) in cache instead of HLC. Because a cache service is most likely memory-bound and spending a few extra bytes for every piece of data in cache can be very expensive. Especially if you are mostly caching small data.

Small Version Comparison

It’s not straightforward

If a stateful service considers version 0 is less than version 65535, either it is already broken and people just don't realize it, or it will break in the future.

Circle instead of axis

Comparing two versions on an axis is simple. The one on the right is the greater one. How do we compare two versions on a circle? We can’t.

Let’s consider the following example. Which one is greater? A or B?

If we consider A is greater, which means it happened after B, the gap between A and B is bigger. If considering B greater than A, the gap is smaller.

We cannot compare A and B without making assumptions. But if we assume that we are only comparing events that happened close to each other, we know B should be greater than A. This is a reasonable assumption to make as versions are often only used to order recent events during a racing window. It's unlikely that more than 2^15 events happened in a small racing window.

How to compute it

B > A iff B + D == A, where D >= 2^15
B + D == A iff A - B >= 2^15
A - B >=2^15 iff int16_t(A - B) < 0

So, at the very end, in C++, version_cmp(A, B) can be written as int16_t(A - B) > 0 -- an elegant one liner.

This is how small version comparison works.

Originally published at blog.the-pans.com on March 13, 2019.

Software Engineer at Facebook working on cache infrastructure

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store