知识卡片
哈希冲突靠递增副本序号重算解决
内容
[[四种Bucket选择算法的复杂度权衡|Bucket 选择算法]]依赖三元组 hash(x, r, i)(x 是 PG id,r 是副本序号,i 是 bucket id)算出结果;如果选出的 OSD 和之前已选的重复、已失效或过载,就需要重选。重选的方式不是换一种哈希算法或加随机数,而是把参数 r(副本序号)顺序递增后再算一次——因为整个函数是确定性的,只要输入变了,输出的伪随机结果就会变,同时保证同一个 PG 在同一份 Cluster Map 下每次计算结果完全一致、可复现。这是”用输入的可控变化换取确定性重试”的典型手法,避免引入真正的随机性破坏算法的可重复计算特性。
参考来源
《Ceph源码分析》第4章《CRUSH数据分布算法》