Consistent hashing

use consistent_hash.qweruse hash_shard, hash_server from consistent_hash      // Quillo 0.6: only these

// Users spread over cache servers, and what moves when a server is added or taken away.////   quillo run consistent_hash.qwe      then open http://localhost:8080/movesuse "consistent_hash.qwer"let users = range(0, 1000) | map((i) => `user-${i}`)route GET /server ? { key: str } = { server: hash_server(key, ["cache-a", "cache-b", "cache-c"]), copies: hash_servers(key, ["cache-a", "cache-b", "cache-c"], 2), shard: hash_shard(key, 16)? }route GET /moves {    let three = users | map((u) => hash_server(u, ["a", "b", "c"]))    let four = users | map((u) => hash_server(u, ["a", "b", "c", "d"]))    let moved = zip(three, four) | filter((p) => p[0] != p[1])    let shards10 = users | map((u) => hash_shard(u, 10)?)    let shards11 = users | map((u) => hash_shard(u, 11)?)    {        moved_adding_d: len(moved),        all_went_to_d: all(moved, (p) => p[1] == "d"),        shard_moves_10_to_11: len(zip(shards10, shards11) | filter((p) => p[0] != p[1])),        weighted_big: len(users | filter((u) => hash_server_weighted(u, { big: 3.0, small: 1.0 }) == "big")),    }}

//! Which server a key goes to, stable as servers come and go: jump consistent hashing for numbered shards, rendezvous hashing for named servers (with weights and replicas), so a cache or a shard moves as few keys as possible.//! version: 1.0.0//!//! [dependencies]/// FNV-1a over the bytes, then the splitmix64 finalizer: the same on every machine and version.fn hash(s: &str) -> u64 {    let mut h: u64 = 0xcbf2_9ce4_8422_2325;    for b in s.bytes() {        h ^= b as u64;        h = h.wrapping_mul(0x0000_0100_0000_01b3);    }    let mut z = h;    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);    z ^ (z >> 31)}fn score(key: &str, server: &str) -> u64 {    hash(&format!("{}\u{0}{}", server, key))}/// The shard of `key` among `shards` numbered 0 to shards-1, by jump consistent hashing (Lamping and Veach): going from 10 shards to 11 moves only a tenth of the keys, all to the new one. For shards that are only ever added or removed at the end.pub fn hash_shard(key: &str, shards: i64) -> Result<i64, String> {    if !(1..=1_000_000).contains(&shards) {        return Err("shards from 1 to 1,000,000".into());    }    let mut k = hash(key);    let (mut b, mut j): (i64, i64) = (-1, 0);    while j < shards {        b = j;        k = k.wrapping_mul(2862933555777941757).wrapping_add(1);        j = ((b + 1) as f64 * ((1u64 << 31) as f64 / ((k >> 33) + 1) as f64)) as i64;    }    Ok(b)}/// The server of `key` among `servers` (names, in any order), by rendezvous (highest random weight) hashing: removing a server moves only its keys, spread over the others; adding one takes a fair share. Null when the list is empty.pub fn hash_server(key: &str, servers: Vec<String>) -> Option<String> {    servers.into_iter().max_by_key(|s| score(key, s))}/// The `n` servers for `key`, best first, for keeping copies on several: the first is `hash_server`'s, and when it fails the second takes over with no other key moving.pub fn hash_servers(key: &str, servers: Vec<String>, n: i64) -> Vec<String> {    let mut v: Vec<(u64, String)> = servers.into_iter().map(|s| (score(key, &s), s)).collect();    v.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(&b.1)));    v.dedup_by(|a, b| a.1 == b.1);    v.into_iter().take(n.max(0) as usize).map(|(_, s)| s).collect()}/// The server of `key` by weight: `weights` maps server names to how much they take (a server of weight 2 gets about twice the keys of one of weight 1); weights of 0 or less take none. Null when none can.pub fn hash_server_weighted(key: &str, weights: std::collections::HashMap<String, f64>) -> Option<String> {    weights        .into_iter()        .filter(|(_, w)| *w > 0.0 && w.is_finite())        .map(|(s, w)| {            // Weighted rendezvous: -w / ln(u), u uniform in (0, 1).            let u = ((score(key, &s) >> 11) as f64 + 0.5) / (1u64 << 53) as f64;            (-w / u.ln(), s)        })        .max_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal).then(b.1.cmp(&a.1)))        .map(|(_, s)| s)}