This morning puzzle: avoid accumulating rounding errors when fixing crush weights. The goal is to do something like weight * correction intsead of weight * correction1 * correction2 * correction3 * ...
But it's easier said than done, specially when mixing integers, Q16.16 and doubles.
First draft of the crush algorithm implementation in C, using straws and moving exactly one item at a time. It should be at least an order of magnitude faster than the current python-crush implementation.
I got an idea about CRUSH optimization. When we know all the values to be distributed, rebalancing an uneven distribution should not be an optimization problem. We should be able to calculate exactly which weights lead to a perfect distribution.
Running a simulation with all known values at each step of the optimization is going in the right direction but is unnecessarily complicated.
I'll modify CRUSH to expose the values influenced by weights and see where it leads us.
Finished rewriting python-crush to use Q16.16 internally instead of floats. The optimization is stable and passes tests. Now to documentation !
The python-crush optimize command can now be given a Ceph report. It's definitely the easiest way to optimize a crushmap. Not only because it can read the PG num, pool size etc. from the OSDMap. But also because it can verify that all mappings in the OSDMap match with the python-crush generated mappings.
I now need to complete the last (?) piece of the puzzle which is incremental optimization.
Which distributed systems would benefit from a better placement algorithm ? Except for storage and caching, these are covered :-) I'm looking for contexts where CRUSH would be useful.