main.rs

#![allow(dead_code)]
use rendezvous_hash::RendezvousNodes;
use rendezvous_hash::{Capacity, WeightedNode};
use std::collections::hash_map::DefaultHasher;
use std::collections::{HashMap, HashSet};
use std::hash::{BuildHasher, BuildHasherDefault, Hash, Hasher};

const JUMP: u64 = 1 << 31;

/// Takes a 64 bit key and the number of buckets, outputs a bucket number `0..buckets`.
///
/// # Examples
///
/// ```
/// extern crate jump_consistent_hash as jch;
/// assert_eq!(jch::hash(0, 60), 0);
/// assert_eq!(jch::hash(1, 60), 55);
/// assert_eq!(jch::hash(2, 60), 46);
/// ```
///
pub fn jump_hash(key: u64, buckets: usize) -> u32 {
    let len = if buckets == 0 { 1 } else { buckets as i64 };
    let mut k = key;
    let mut b = -1;
    let mut j = 0;
    while j < len {
        b = j;
        k = k.wrapping_mul(2862933555777941757) + 1;
        j = ((b + 1) as f64 * (JUMP as f64 / ((k >> 33) + 1) as f64)) as i64;
    }
    return b as u32;
}

struct JumpHasher<B: BuildHasher> {
    hasher: B,
}

impl<B: BuildHasher> JumpHasher<B> {
    fn hash<K: Hash>(&self, k: K, buckets: usize) -> u32 {
        let mut hasher = self.hasher.build_hasher();
        k.hash(&mut hasher);
        jump_hash(hasher.finish(), buckets)
    }
}

type MyBuildHasher = BuildHasherDefault<DefaultHasher>;

fn main() {
    hrw();
    //anchor();
    anchor_incr();
    jump();
}

fn jump() {
    println!("# jump hash:");
    let hasher = JumpHasher {
        hasher: MyBuildHasher::default(),
    };
    let buckets = 4;

    let mut foos = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = hasher.hash(item, buckets);
        *counts.entry(node).or_insert(0) += 1;
        if node == 0 {
            foos.insert(item);
        }
    }
    println!("{}", (counts[&0] as f64).round());
    println!("{}", (counts[&1] as f64).round());
    println!("{}", (counts[&2] as f64).round());
    println!("{}", (counts[&3] as f64).round());

    let buckets = buckets - 1;
    let mut foos_2 = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = hasher.hash(item, buckets);
        *counts.entry(node).or_insert(0) += 1;
        if node == 0 {
            foos_2.insert(item);
        }
    }
    println!(
        "remapped into foo {}%",
        foos_2.difference(&foos).collect::<Vec<_>>().len() as f64 / (counts[&0] as f64) * 100.0
    );
    println!(
        "remapped from foo {}%",
        foos.difference(&foos_2).collect::<Vec<_>>().len() as f64 / (counts[&0] as f64) * 100.0
    );
}

fn hrw() {
    println!("# HRW:");
    let mut nodes = RendezvousNodes::default();
    nodes.insert(WeightedNode::new("foo", Capacity::new(1.0).unwrap()));
    nodes.insert(WeightedNode::new("bar", Capacity::new(1.0).unwrap()));
    nodes.insert(WeightedNode::new("baz", Capacity::new(1.0).unwrap()));
    nodes.insert(WeightedNode::new("qux", Capacity::new(1.0).unwrap()));

    let mut foos = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = nodes.calc_candidates(&item).nth(0).unwrap();
        *counts.entry(node.node.to_string()).or_insert(0) += 1;
        if node.node == "foo" {
            foos.insert(item);
        }
    }
    println!("{}", (counts["foo"] as f64).round());
    println!("{}", (counts["bar"] as f64).round());
    println!("{}", (counts["baz"] as f64).round());
    println!("{}", (counts["qux"] as f64).round());

    let mut nodes = RendezvousNodes::default();
    nodes.insert(WeightedNode::new("foo", Capacity::new(1.0).unwrap()));
    nodes.insert(WeightedNode::new("bar", Capacity::new(1.0).unwrap()));
    nodes.insert(WeightedNode::new("baz", Capacity::new(1.0).unwrap()));
    //nodes.insert(WeightedNode::new("qux", Capacity::new(1.0).unwrap()));
    //nodes.insert(WeightedNode::new("qux2", Capacity::new(1.0).unwrap()));

    let mut foos_2 = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = nodes.calc_candidates(&item).nth(0).unwrap();
        *counts.entry(node.node.to_string()).or_insert(0) += 1;
        if node.node == "foo" {
            foos_2.insert(item);
        }
    }

    println!(
        "remapped into foo {}%",
        foos_2.difference(&foos).collect::<Vec<_>>().len() as f64 / (counts["foo"] as f64) * 100.0
    );
    println!(
        "remapped from foo {}%",
        foos.difference(&foos_2).collect::<Vec<_>>().len() as f64 / (counts["foo"] as f64) * 100.0
    );
}

fn anchor() {
    println!("# Anchor hash rebuild:");
    // The capacity has to stay the same otherwise it will reshard everything
    // Empirically, some values of capacity produce better effects on rebalancing spread
    // than others. In any case anchorhash seems worse than HRW
    let capacity = 1024 * 32;
    let anchor = anchorhash::Builder::with_hasher(MyBuildHasher::default())
        .with_resources(vec!["foo", "bar", "baz", "qux"])
        .build(capacity);

    let mut foos = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = anchor.get_resource(item).unwrap();
        *counts.entry(node.to_string()).or_insert(0) += 1;
        if node == &"foo" {
            foos.insert(item);
        }
    }
    println!("{}", ((counts["foo"] as f64) / 100.0).round());
    println!("{}", ((counts["bar"] as f64) / 100.0).round());
    println!("{}", ((counts["baz"] as f64) / 100.0).round());
    println!("{}", ((counts["qux"] as f64) / 100.0).round());

    let anchor = anchorhash::Builder::with_hasher(MyBuildHasher::default())
        .with_resources(vec!["foo", "bar", "baz", "qux", "quz2"])
        .build(capacity);

    let mut foos_2 = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = anchor.get_resource(item).unwrap();
        *counts.entry(node.to_string()).or_insert(0) += 1;
        if node == &"foo" {
            foos_2.insert(item);
        }
    }

    println!(
        "remapped in foo {}%",
        foos.difference(&foos_2).collect::<Vec<_>>().len() as f64 / (counts["foo"] as f64) * 100.0
    );
}

fn anchor_incr() {
    println!("# Anchor hash incremental:");

    // The capacity has to stay the same otherwise it will reshard everything
    // Empirically, some values of capacity produce better effects on rebalancing spread
    // than others. In any case anchorhash seems worse than HRW
    let capacity = 1024 * 32;
    let mut anchor = anchorhash::Builder::with_hasher(MyBuildHasher::default())
        .with_resources(vec!["foo", "bar", "baz", "qux"])
        .build(capacity);

    let mut foos = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = anchor.get_resource(item).unwrap();
        *counts.entry(node.to_string()).or_insert(0) += 1;
        if node == &"foo" {
            foos.insert(item);
        }
    }
    println!("{}", (counts["foo"] as f64).round());
    println!("{}", (counts["bar"] as f64).round());
    println!("{}", (counts["baz"] as f64).round());
    println!("{}", (counts["qux"] as f64).round());

    //anchor.add_resource("qux2").unwrap();
    anchor.remove_resource(&"qux").unwrap();

    let mut foos_2 = HashSet::new();
    let mut counts = HashMap::new();
    for item in 0..100000 {
        let node = anchor.get_resource(item).unwrap();
        *counts.entry(node.to_string()).or_insert(0) += 1;
        if node == &"foo" {
            foos_2.insert(item);
        }
    }

    println!(
        "remapped into foo {}%",
        foos_2.difference(&foos).collect::<Vec<_>>().len() as f64 / (counts["foo"] as f64) * 100.0
    );
    println!(
        "remapped from foo {}%",
        foos.difference(&foos_2).collect::<Vec<_>>().len() as f64 / (counts["foo"] as f64) * 100.0
    );
}

fn anchor_ordering() {
    println!("ordering A");
    {
        let mut anchor = anchorhash::Builder::with_hasher(MyBuildHasher::default())
            .with_resources(vec![1, 2, 3])
            .build(20);

        println!("{}", anchor.get_resource("key1").unwrap());
        anchor.add_resource(4).unwrap();
        println!("{}", anchor.get_resource("key1").unwrap());
        anchor.add_resource(5).unwrap();
        println!("{}", anchor.get_resource("key1").unwrap());
        anchor.remove_resource(&4).unwrap();
        anchor.remove_resource(&5).unwrap();
        println!("final: {}", anchor.get_resource("key1").unwrap());
    }
    println!("ordering B:");
    {
        let mut anchor = anchorhash::Builder::with_hasher(MyBuildHasher::default())
            .with_resources(vec![1, 2, 3])
            .build(20);

        println!("{}", anchor.get_resource("key1").unwrap());
        anchor.add_resource(5).unwrap();
        println!("{}", anchor.get_resource("key1").unwrap());
        anchor.add_resource(4).unwrap();
        println!("{}", anchor.get_resource("key1").unwrap());
        anchor.remove_resource(&4).unwrap();
        anchor.remove_resource(&5).unwrap();
        println!("final: {}", anchor.get_resource("key1").unwrap());
    }

    println!("direct A");
    {
        let anchor = anchorhash::Builder::with_hasher(MyBuildHasher::default())
            .with_resources(vec![1, 2, 3, 4, 5])
            .build(20);

        println!("{}", anchor.get_resource("key1").unwrap());
    }

    println!("direct A");
    {
        let anchor = anchorhash::Builder::with_hasher(MyBuildHasher::default())
            .with_resources(vec![1, 2, 3, 5, 4])
            .build(20);

        println!("{}", anchor.get_resource("key1").unwrap());
    }
}