CRUSH桶选择算法在计算速度与迁移量之间的权衡

CRUSH Map是一棵描述OSD物理组织结构的树，非叶子节点叫桶，选择数据该落在哪个OSD要沿着树逐层递归选择子桶，具体用哪种算法选子节点可以配置：Uniform假设权重均等且很少增删，直接哈希，速度最快但适用场景极窄；List/Tree属于分治算法，能感知权重但子元素的选择概率彼此关联，一旦某个元素变化会牵连全局的数据分布，带来不必要的迁移；Straw/Straw2让所有子元素独立”抽签”竞争，签长按权重伪随机生成，某个元素的增删只影响自己相关的少量数据，其中Straw2修正了Straw签长仍会依赖其他元素状态的缺陷，实测数据迁移量能从20%降到12%左右，接近理论最优。发散：这组算法演进的核心矛盾一直是”每个元素的选择概率能不能做到彼此独立”——只要选择结果彼此纠缠，局部变化就会波及全局，这个教训对任何要做”增量友好”的哈希分布方案都适用。