Ceph » bluestore

When operating in best-fit mode these allocators perform chunk lookups through size-sorted "range_size_tree" container. This is done in two stages:

Use container's lower_bound() to search for the first available
long enough chunk.
Iterate sequentially to locate properly aligned chunk,
starting from the position obtained at step 1)
Step 2) might require significant efforts for bluefs allocations (which uses longer allocation unit than bluestore min_alloc_size, e.g. 64K vs. 4K) if space is highly fragmented. Plenty of potentially available chunks might be unaligned to 64K boundary and once aligned they aren't long enough any more.

This spreadsheet shows how dramatic could that be for hybrid allocator (real free map from a production cluster was used to build it):
https://docs.google.com/spreadsheets/d/1bh22JNqwTPSFUQPStYuuiKDEui6YSxZsusIln3tZ9t0/edit?usp=sharing