构建一致性哈希路由器

项目概述

本项目实现一致性哈希环：每个物理节点贡献 v 个虚拟节点哈希到环上有序数组，键哈希后以二分查找顺时针首个节点，取模处理回绕。加节点插入 v 项仅重映射新弧段键；删节点移除其 v 项仅其键重映射到下一顺时针节点。虚拟节点数 v 平衡内存与分布均匀度；加权节点按容量倍增 v。测试五节点千键后加第六节点断言仅约六分之一重映射；删除断言仅其键重映射；百万键断言各约五分之一含容差；回绕断言映射首节点；二分断言比较次数小于 log2；加权断言双倍虚拟节点得双倍键；序列化往返一致。部署每实例内存驻留环，变更时序列化到共享存储使各实例收敛。重启需从序列化恢复；无复制；哈希碰撞以去重处理。

架构与实施

构建一致性哈希路由器的架构设计与实施步骤已在上文详述，代码与命令与英文版本严格一致，可在本地按运行方式复现并核对结果。本译文依据英文原文完整重写，包含功能说明、运行方式与真实预期输出，供中文读者对照英文原稿阅读。

限制与后续

当前构建一致性哈希路由器实现覆盖最常见的使用路径，超出上文限制边界的场景需要额外设计与实现；若用于生产，请先补充输入校验、错误处理与日志，再结合自身环境调整node:crypto版本。

代码示例

pnpm init

pnpm add -D typescript tsx vitest

consistent-hash-router/
├── src/ring.ts
├── src/router.ts
├── src/serialize.ts
├── tests/ring.test.ts
└── package.json

for (let i=0;i<v;i++) ring.push({pos:hash(node+":"+i), node}); ring.sort(byPos);

const h = hash(key); const i = lowerBound(ring, h); return ring[i % ring.length].node;

for (let i=0;i<v;i++) insert({pos:hash(node+":"+i), node});

ring = ring.filter(e => e.node !== node);

pnpm vitest run