如何用C++在10秒内建立含3亿虚拟节点的一致性哈希环

核心问题分析 #

你之前用std::map循环插入的方式之所以慢，本质是红黑树每次插入都要做O(logn)的平衡操作，3亿次操作的累计开销完全扛不住。多线程没效果甚至更慢，大概率是直接在多线程里操作同一个std::map，锁竞争把并行的优势完全抵消了。

具体优化建议 #

• 换掉std::map，改用排序后的std::vector
  不要边生成边插入有序容器，先把所有虚拟节点的哈希值批量计算出来，存入std::vector，最后一次性调用std::sort排序。排序的时间复杂度是O(nlogn)，但实际执行效率远高于3亿次红黑树插入——毕竟排序是高度优化的底层实现，红黑树插入的常数项开销大太多。
  记得提前用reserve(300000000)给vector预分配内存，避免扩容时的内存拷贝开销。

• 选用高速哈希函数
  别用默认的std::hash，换成MurmurHash3、CityHash这类专门优化过的非加密哈希函数，计算速度能提升好几倍，而且碰撞概率足够低，完全满足分布式存储的需求。比如MurmurHash3的64位版本，单线程就能每秒处理数千万级别的哈希计算。

• 正确的多线程拆分方式
  不要让多线程共享同一个容器，而是给每个线程分配一段虚拟节点的生成任务：

  1. 按CPU核心数拆分3亿节点，比如8核就分成8份，每份3750万节点；
  2. 每个线程独立计算自己负责的虚拟节点哈希值，存入各自的局部std::vector；
  3. 所有线程完成后，把所有局部vector合并成一个大vector；
  4. 对大vector做一次性排序。
     这种方式完全避免了锁竞争，把并行的优势发挥到最大，合并和排序的开销相比单线程的插入操作可以忽略。

• 编译优化
  开启最高级别的编译优化，比如GCC的-O3，编译器会自动做循环展开、指令重排等优化，能进一步提升哈希计算和排序的速度。

可用的开源实现思路 #

很多成熟的分布式存储项目都有高效的一致性哈希实现可以参考：

• Redis的一致性哈希模块：虽然它的虚拟节点数通常没这么大，但核心思路是用排序后的数组替代有序树，你可以借鉴它的批量生成+排序逻辑；
• LevelDB的哈希工具类：里面封装了高速哈希函数的实现，直接拿来用能省掉自己造轮子的时间；
• libconsistenthash：专门的一致性哈希库，支持批量生成虚拟节点，内部也是用排序后的数组来实现哈希环，性能表现不错。

内容的提问来源于stack exchange，提问作者Janos