CRUSHControlled replication
按层级拓扑、权重和规则计算副本放置。
- 核心约束
- 副本选择需满足指定故障域和放置规则。
- 适用问题
- 分布式存储的数据放置。
- 边界与取舍
- 改变拓扑或权重会引起重映射；并非普通哈希环。
时间与空间#
r 为副本数，h 为拓扑深度；bucket 算法、权重、排除项和重试次数均会影响成本。
- 时间复杂度
- 拓扑逐级选择 × 副本 / 重试次数
- 辅助空间
- CRUSH map、规则、权重和本次选择状态
计算数据到设备的确定性映射，按规则跨主机、机架等故障域放置。不同 bucket 的选择成本不同，失效设备与冲突会引起重试；不能统一写成 或只与设备总数成对数关系。
工程中的应用#
1 个案例 · 附源码Ceph 的 CRUSH 使用拓扑、权重与规则，为数据放置计算候选设备集合。
附源码片段 · 存储与数据放置
基础原理参考资料
Ceph Squid · CRUSH Maps设备层级、规则、权重和 failure domain。
Ceph · CRUSH paper可扩展确定性放置、bucket 选择和映射迁移分析。