Max value comparator - Githubissues

The new logging and caching module for antidote, will use eleveldb as one of its possible backends. In order to use eleveldb, we needed to code a new comparator, so keys get sorted as we want.

Keys are composed as follows:

{antidote_key, max_value_in_vc, vc_hash, op/snap, vc}

antidote_key: Same key as in Antidote.
max_value_in_vc: The max value for all DCs in the VC.
vc_hash: A hash of the VC. This is done in order to provide a more performant sorting algorithm, since we don't need to compare all the VC, to find that keys are different. If the hash matches, we also compare the VC, just to make sure it's not a collision.
op/snap: an atom indicating if the stored value corresponds to an operation or a snapshot.
vc: the vc of when the op/snap ocurred.

Sorting of keys

Keys get sorted first by the Antidote key. Then we look at the MAX value of it's VC, sorting first the biggest one. We reverse the "natural" order, so we can have the most recent operations first. If the max value for two keys matches, we sort taking into account the hash value. For matching hashes, we check the rest of the key, sorting accordingly.

As Erlang serialises objects sent to eleveldb, according http://erlang.org/doc/apps/erts/erl_ext_dist.html, so what we do is check those code to compare keys.

basho / eleveldb

Max value comparator #224