Jumphash consistent hashing implementation in jsonnet

jumphash.jsonnet

// A Fast, Minimal Memory, Consistent Hash Algorithm: https://arxiv.org/pdf/1406.2294.pdf

local MAX_INT = 281474976710656;  // 48-bit integers are ok in jsonnet.
local NIBBLES = 12;  // 12 hex digits in a 48-bit number.

// "random numbers should not be generated with a method chosen at random. -- D. Knuth
// And yet, due to lack of 64-bit integer arithmetic in jsonnet, this seems to work decently.
local nextRandom(n) = std.parseHex(std.slice(std.md5(std.toString(n)), 0, NIBBLES, 1));

{
  local jumphash(key, num_buckets, b=0, j=0) = if j >= num_buckets then b else (
    local keyP = nextRandom(key);
    local bP = if (keyP / MAX_INT) < (1.0 / (j + 1)) then j else b;
    jumphash(keyP, num_buckets, bP, j + 1) tailstrict  // https://github.com/google/jsonnet/issues/343
  ),
  jumphash:: jumphash,
}