The Ceph CRUSH algorithm

ID: ce3e8f5e-510b-4159-a117-773639c3731f
REVIEW_SCORE: 0.0
MTIME: [2024-12-25 Wed 15:54]

Allocation algorithm. given an input value, CRUSH deterministically outputs an ordered list of distinct storage targets.

Create a cluster map, which is a tree where the leaves are storage devices; call the internal nodes buckets.

Buckets have associated weights and are of four different types:

• uniform (children are identical; constant-time allocation)
• list (children are arbitrary weights; we step through it until the current node is heavier than the sum of the remaining)
• tree (children have arbitrary weights)
• straw (children are assigned numbers which are multiplied by weights, and the "longest straw" is chosen)

This plus implementation of allocation rules, which act as filters.

This node is a singleton!