一致性哈希是分布式系統領域中被廣泛應用的核心算法，Amazon Dynamo、Memcached、Riak 等知名分布式系統均採用了該算法。其核心思想是將數據和節點映射到同一個哈希環上，通過順時針查找最近的節點來實現負載均衡，並在節點增減時將數據遷移影響降至最低。
網路上雖然有不少關於一致性哈希的介紹文章和代碼實現，但大多或過於理論化、或代碼結構不夠優雅。本文將分享一個基於 STL 模板設計的 consistent_hash_map 實現，代碼已開源於 GitHub，具有介面簡潔、擴展性強、無依賴等特點。
一致性哈希的功能被封裝在模板類 consistent_hash_map 中，採用 STL map 風格的介面設計，內部基於 std::map 維護哈希環上的所有節點：
template <typename T,
typename Hash,
typename Alloc = std::allocator<std::pair<const typename Hash::result_type, T>> >
class consistent_hash_map;
operator() 和 result_type 類型定義| 類型 | 定義 | 說明 |
|---|---|---|
| size_type | Hash::result_type | 哈希函數返回值類型 |
| value_type | std::pair<const size_type, T> | first 為節點哈希值，second 為節點對象 |
| iterator | 雙向迭代器 | 指向 value_type 的雙向迭代器 |
| reverse_iterator | 反向迭代器 | reverse_iterator<iterator> |
size() / empty()：查詢節點數量與是否為空insert(const T& node)：插入節點，返回 pair<iterator, bool>，失敗原因包括節點已存在或哈希值衝突erase(iterator) / erase(const T&)：通過迭代器或節點值刪除find(size_type hash)：根據哈希值查找對應節點（順時針最近節點）begin() / end() / rbegin() / rend()：標準迭代器介面consistent_hash_map 本身不直接內建虛擬節點機制，但通過自定義 T 和 Hash 即可靈活實現。這種設計使核心邏輯極度簡潔，同時賦予用戶最大靈活度。
#include <cstdint>
#include <boost/format.hpp>
#include <boost/crc.hpp>
#include "consistent_hash_map.hpp"
// 物理節點列表
const char* nodes[] = {
"192.168.1.100", "192.168.1.101", "192.168.1.102",
"192.168.1.103", "192.168.1.104"
};
// 虛擬節點結構
struct vnode_t {
vnode_t() {}
vnode_t(std::size_t n, std::size_t v) : node_id(n), vnode_id(v) {}
std::string to_str() const {
return boost::str(boost::format("%1%-%2%") % nodes[node_id] % vnode_id);
}
std::size_t node_id; // 物理節點索引
std::size_t vnode_id; // 虛擬節點 ID
};
// CRC32 哈希函數
struct crc32_hasher {
uint32_t operator()(const vnode_t& node) {
boost::crc_32_type ret;
std::string vnode = node.to_str();
ret.process_bytes(vnode.c_str(), vnode.size());
return ret.checksum();
}
typedef uint32_t result_type;
};
typedef consistent_hash_map<vnode_t, crc32_hasher> consistent_hash_t;
consistent_hash_t consistent_hash_;
// 為每個物理節點創建 100 個虛擬節點
for (std::size_t i = 0; i < 5; ++i) {
for (std::size_t j = 0; j < 100; ++j) {
consistent_hash_.insert(vnode_t(i, j));
}
}
consistent_hash_t::iterator it = consistent_hash_.find(290235110);
// it->first 為節點哈希值，it->second 為虛擬節點對象
std::cout << boost::format("node:%1%, vnode:%2%, hash:%3%")
% nodes[it->second.node_id] % it->second.vnode_id % it->first
<< std::endl;
std::size_t sums[5] = {0};
auto i = consistent_hash_.begin(); // 第一個節點
auto j = consistent_hash_.rbegin(); // 最後一個節點
// 計算第一個節點負載（環首尾相連）
std::size_t n = i->first + UINT32_MAX - j->first;
std::cout << boost::format("vnode:%1%, hash:%2%, contains:%3%")
% i->second.to_str() % i->first % n << std::endl;
sums[i->second.node_id] += n;
// 計算其餘節點負載
uint32_t prev = i->first;
auto end = consistent_hash_.end();
while (++i != end) {
uint32_t cur = i->first;
n = cur - prev;
std::cout << boost::format("vnode:%1%, hash:%2%, contains:%3%")
% i->second.to_str() % cur % n << std::endl;
sums[i->second.node_id] += n;
prev = cur;
}
// 輸出各物理節點總負載
for (std::size_t i = 0; i < 5; ++i) {
std::cout << boost::format("node:%1% contains:%2%") % nodes[i] % sums[i] << std::endl;
}
std::map，查找/插入/刪除均為 O(log N)完整代碼請參考 GitHub 倉庫。歡迎星標、Fork 及提交 Issue 改進。
