一致性哈希算法实操

一致性哈希是在工程上运用非常多的算法，网上有非常多的理解，这边就不再赘述了（~~因为懒~~）。

但实操的代码较少，于是我就按照自己的理解写了一个。

理论上在多线程上面是能用的，虽然我没有进行测试，但我在每一个函数都加了个锁，总不能这都能有问题吧。

下面的代码随便拿去用，反正我也是随便写写的而已。

// consistent_hashing.hpp
#pragma once

#include <cstdint>
#include <atomic>
#include <string>
#include <mutex>
#include <map>

namespace ext {

namespace detail {

// 一个非常强大的哈希算法
class SplitMix64 {
 public:
  uint64_t operator() (uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
};

}  // namespace detail

// 一致性哈希类
template<typename ValueType,
         typename Hash = detail::SplitMix64,
         uint16_t kVirtualNodeNumber = 32>
class ConsistentHashing {
 public:
  ConsistentHashing() {
    // 总不能一个节点都没有吧
    static_assert(kVirtualNodeNumber > 0);
    count_ = 0;
  }
  // 增加节点 返回节点编号
  uint64_t AddNode(const ValueType& value) {
    // 不管怎样 锁上再说
    std::lock_guard<std::mutex> lock_(mutex_);
    // 获取节点编号（虽然这一步是无锁的，但后面的map是需要上锁的，顺便锁上吧）
    const uint64_t node_number = ++count_;
    // 放进std::map中
    values_[node_number] = value;
    // 在红黑树中插入节点并返回其value
    std::vector<uint64_t>& pos = hashes_[node_number];
    // 放入kVirtualNodeNumber个虚拟节点
    for (uint16_t i = 1; i <= kVirtualNodeNumber; i++) {
      // 获取每一个虚拟节点在环中的位置
      uint64_t hash = Hash()(node_number * kVirtualNodeNumber + i);
      // 放入环中（有可能有哈希冲突，即使概率极低，这时候用再哈希的方法）
      while (circle_.find(hash) != circle_.end()) {
        hash = Hash()(hash);
      }
      circle_[hash] = node_number;
      pos.emplace_back(hash);
    }
    return node_number;
  }
  // 传入节点编号 返回是否删除成功
  bool DropNode(uint64_t node_number) {
    // 不管怎样 锁上再说
    std::lock_guard<std::mutex> lock_(mutex_);
    // 看看是不是存在这个节点
    const auto& iter = values_.find(node_number);
    // 不存在就直接返回
    if (iter == values_.end()) {
      return false;
    }
    // 删除节点
    values_.erase(iter);
    // 删除在circle中的位置 用at是因为如果不存在就没救了
    const std::vector<uint64_t>& pos = hashes_.at(node_number);
    for (const uint64_t& hash : pos) {
      // 直接删除 如果不存在就没救了
      circle_.erase(hash);
    }
    // 别忘记把这里也删除了 同样也直接删除 不存在就没救了
    hashes_.erase(node_number);
    return true;
  }
  ValueType& GetNode(uint64_t data) {
    // 重新哈希一遍
    data = Hash()(data);
    // 不管怎样 锁上再说
    std::lock_guard<std::mutex> lock_(mutex_);
    // 没有节点 没法做了
    if (circle_.empty()) {
      throw std::runtime_error("Empty node set.");
    }
    // 找到下一个节点 即在std::map上二分
    auto iter = circle_.lower_bound(data);
    // 如果二分找不到下一个节点 那么其实是第一个节点
    if (iter == circle_.end()) {
      iter = circle_.begin();
    }
    // 使用at 不存在就没救了
    return values_.at(iter->second);
  }
 private:
  // 节点计数器
  std::atomic<uint64_t> count_;
  // key为节点编号，value为节点的值（虽然有很多个虚拟节点，但只需要存一个value即可）
  std::map<uint64_t, ValueType> values_;
  // key为节点编号，value为这个节点的所有虚拟节点的在环上的位置
  std::map<uint64_t, std::vector<uint64_t>> hashes_;
  // key为环上节点哈希值，value为节点编号（由于有虚拟节点，节点编号有可能重复）
  std::map<uint64_t, uint64_t> circle_;
  // 互斥锁 并发编程必备
  std::mutex mutex_;
};

}  // namespace ext

以下是测试的代码：

#include <chrono>
#include <iostream>
#include <random>
#include <set>
#include <map>

#include "consistent_hashing.hpp"

int main() {
  ext::ConsistentHashing<int> consistent_hashing;
  consistent_hashing.AddNode(1);
  consistent_hashing.AddNode(2);
  consistent_hashing.AddNode(3);
  consistent_hashing.AddNode(4);
  consistent_hashing.AddNode(5);
  std::cout << consistent_hashing.GetNode(1311) << std::endl; // 1
  std::cout << consistent_hashing.GetNode(1311) << std::endl; // 1
  std::cout << consistent_hashing.GetNode(32343241) << std::endl; // 3
  consistent_hashing.AddNode(6);
  consistent_hashing.AddNode(7);
  std::cout << consistent_hashing.GetNode(1311) << std::endl; // 1
  consistent_hashing.DropNode(2);
  consistent_hashing.DropNode(1);
  std::cout << consistent_hashing.GetNode(1311) << std::endl; // 7
  std::cout << consistent_hashing.GetNode(32343241) << std::endl; // 3
  consistent_hashing.AddNode(8);
  consistent_hashing.AddNode(9);
  consistent_hashing.AddNode(10);
  consistent_hashing.AddNode(11);
  consistent_hashing.AddNode(12);
  std::cout << consistent_hashing.GetNode(1311) << std::endl; // 7
  std::cout << consistent_hashing.GetNode(32343241) << std::endl; // 3
  consistent_hashing.AddNode(13);
  consistent_hashing.AddNode(14);
  std::cout << consistent_hashing.GetNode(1311) << std::endl; // 14
  std::cout << consistent_hashing.GetNode(32343241) << std::endl; // 3
}

暂时非常符合预期，如果有bug请在评论区中提出。

#C/C++#