取模路由与一致性环
取模hash(key)%n会在n改变后重算归属。均匀覆盖周期时,4→3保留25%、搬75%,4→5保留20%、搬80%;“几乎所有键”不应替代这些具体比例。真实键集可能不同,需逐键对照。
一致性环的哈希空间保持不变。节点拥有一个或多个token,键归属于顺时针第一个token;越过最大token回到环首。新增token只接管其前驱之后到自身的区间,未接管区间的原归属不变。
一个可逐键复算的固定空间
空间0..999,A/B/C/D分别在0/250/500/750。删除D时,原属于D的250个坐标转交后继,其余750个不动,搬25%。
加入E,token放50/300/550/800,四段各接管50个坐标,共200个,搬20%。这里特意选择均匀几何布局;不是新增4个token便普遍保证20%。每个旧节点原有250个键、失去50个,即失去全库5%、自身本地20%。分母必须写清。
本卷实现与反例
Routing.Ring持有固定space和有序token表,owner用ceilingEntry并处理回绕。add拒绝碰撞,remove只删指定节点token;movedTo在同一批hash上比较实际owner。测试还断言新增引起的每个变化都指向E,删除D不改变其余旧owner。
旧ringStable比较b%oldNodes与b%newNodes,实际是取模重排,已经移除。只把函数注释改为“一致性哈希”不会改变它的性质。
均衡与迁移协议是后续问题
更多虚拟节点有助于分布,但不保证真实负载均衡:向量查询成本、热key、段大小和故障域都可能不均。归属计算也不自动完成数据迁移;需要拷贝、增量追平、路由版本和旧写者失效合同,见10.2。
架构与流程
flowchart TD
K["键哈希到固定空间"] --> C["顺时针第一个token"]
C --> O["节点归属"]
ADD["新增E的token"] --> RANGE["仅接管前驱到新token区间"]
RANGE --> CHECK["逐键对比owner;变化都应指向E"]
DEL["删除D的token"] --> NEXT["原D区间交后继;其他owner不变"]
实现与验证边界
模型在固定1000坐标完整枚举增删,验证不相关owner不变;不复刻Milvus内部路由哈希,也没有多节点自动重平衡。
下载卷十三实验包
。Java 8入口为 lab.RunAll;本节对应 routing.RoutingSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。