The Ceph CRUSH algorithm
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.
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.