Add random jitter to selected indexes?

[aboodman]

See https://madebyevan.com/algos/crdt-fractional-indexing/

I wonder if there is a principled way to choose the amount of jitter such that collisions are ~impossible.

[tantaman]

You can also just allow conflicts and repair them iff someone tries to insert between conflicting items. You'd have to of course order by fract_index, primary_key (or something similar) to ensure a stable sort in the face of conflicts.

[aboodman]

Yeah I think we discovered this ourselves too. There are a number of patterns to deal with conflicts and I'm not sure which is best, I keep oscillating between options :).

[quolpr]

Would it be possible to add support for random jitter as an option?

[codsane]

@quolpr if you are still looking, this seems promising: https://github.com/TMeerhof/fractional-indexing-jittered.

While not a fork, it is apparently inspired by this package.

[nathanhleung]

@quolpr if you are still looking, this seems promising: https://github.com/TMeerhof/fractional-indexing-jittered.

While not a fork, it is apparently inspired by this package.

Wanted to use this package but couldn't due to https://github.com/TMeerhof/fractional-indexing-jittered/issues/6 so I wrote https://github.com/nathanhleung/jittered-fractional-indexing instead.

It uses this rocicorp/fractional-indexing package under the hood and generates jitter by binary splitting the key range until the desired number of bits of entropy is reached. E.g. (copied from README):

1. First, we generate an initial index, midpoint, between the specified lower bound a and upper bound b using the original, unjittered fractional-indexing package.
2. Then, with 50% probability each, we either generate a key between the original lower bound a and the midpoint, or a key between the midpoint and the original upper bound b.
3. The process is repeated with the newly-generated key as the new lower or upper bound, with 50% probability each.

I pretty much defer all fractional-indexing logic to the underlying lib here to avoid issues like https://github.com/TMeerhof/fractional-indexing-jittered/issues/6 — the lib does no actual fractional indexing calculation itself — and tack jitter on top. It's probably not the most performant implementation (each jittered key calls the underlying lib $b$ times, once for each bit of entropy) but if you just need to get jittered indexes at human scale, hopefully this can help.