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.