mpchash

基于《多探测一致性哈希》论文的一致性哈希算法实现。

特性

• 多探测一致性哈希。
• 键的平衡分布，峰值与平均负载比率为1 + ε，每个键只需查找1 + 1/ε次。
• 没有虚拟节点，因此不需要额外空间 -- O(n)空间复杂度。高空间需求是原始Karger环的主要缺点。
• 所有传统一致性哈希方法，如环中移动（双向）、添加和删除节点、查找键的最近节点、查找节点拥有的键范围等。

用法

实现支持传统一致性哈希算法的所有功能，因此可以作为任何现有实现的直接替换。

定义一个节点

任何实现以下特质的都可以作为节点放置在环中

Hash + Clone + Debug + Eq + PartialEq + Ord + PartialOrd

以下是一个使用自定义类型作为节点的示例

#[derive(Hash, Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
struct Node {
    id: u64,
}

impl Node {
    fn new(id: u64) -> Self {
        Self { id }
    }
}

创建一个环

要创建一个环并用节点填充

fn main() {
    use mpchash::HashRing;

    let mut ring = HashRing::new();
    ring.add(Node::new(1));
    ring.add(Node::new(2));
    ring.add(Node::new(3));
}

查找拥有键的节点

任何实现Hash的都可以用作键

fn main() {
    // ... ring initialization code

    // Anything that implements `Hash` can be used as a key.
    let key = "hello world";

    // Node that owns the key.
    //
    // It is the first node when moving in CW direction from the 
    // position where key is hashed to.
    let owning_node = ring.primary_node(&key);

    // If we are interested in both ring position and owning node, 
    // we can get them with `primary_token`. 
    // 
    // A token is just a tuple of `(position, node)`.
    let token = ring.primary_token(&key);
}

在复制设置中，我们希望有一个键的多个副本，因此需要多个目标/拥有节点。

为了获得此类副本节点列表，我们可以从给定位置遍历环

fn main() {
    use mpchash::HashRing;
    use mpchash::RingDirection::Clockwise;

    let mut ring = HashRing::new();
    ring.add(Node::new(1));
    ring.add(Node::new(1));

    let key = "hello world";
    let tokens = ring
        .tokens(ring.position(&key), Clockwise)
        .collect::<Vec<_>>();

    for (pos, node) in ring.tokens(&key, Clockwise) {
        println!("node {} is at position {}", node, pos);
    }
}

通常，你会收集/遍历replication factor数量的令牌，这样你就有replication factor个目标节点。

查找由节点拥有的键范围

有时需要找到由节点拥有的键的范围。例如，当某些节点数据需要重新平衡到另一个节点时。在这种情况下，我们是从节点在环中的位置以逆时针方向移动，直到找到一个前一个节点。由于我们在环上操作，我们需要考虑环绕问题。所有这些都由key_range方法处理。

fn main() {
    use mpchash::RingPosition;
    use mpchash::HashRing;

    let mut ring = HashRing::new();

    // Define nodes.
    let node1 = "SomeNode1";
    let node2 = "SomeNode2";

    // Add nodes to the ring.
    ring.add(node1);
    ring.add(node2);

    // Get the range owned by node1.
    let pos = ring.position(&node1);
    let range = ring.key_range(pos).unwrap();

    // The range starts at the position to the left of node1,
    // till (and not including) its own position.
    assert_eq!(range.start, ring.position(&node2));
    assert_eq!(range.end, ring.position(&node1));
}

许可证

MIT