Hi Sage, On 12/09/2014 12:48 AM, Sage Weil wrote: > The new straw2 bucket works like this: > > max_x = -1 > max_item = -1 > for each item: > x = random value from 0..65535 > x = ln(x / 65536) / weight > if x > max_x: > max_x = x > max_item = item > return item > > That ln() is a natural log (well, a 16-bit fixed-point approximation of > it) and as you can see it's a simple function of the weight of that item. > That means that changing one item's weight won't have any effect on the > straw lengths for other items, so a change will either make the item win > or not win but won't change who the other winner is in the not-win case. > > Somewhat embarassingly, I stumbled onto this solution half by accident. > Sam found the underlying principle that makes it work: > > http://en.wikipedia.org/wiki/Exponential_distribution#Distribution_of_the_minimum_of_exponential_random_variables I dont' understand what that works :-) Is there some documentation I could read to better understand the principle ? Cheers [1] bucket_straw2_choose http://libcrush.org/main/libcrush/blob/master/crush/mapper.c#L309 -- Loïc Dachary, Artisan Logiciel Libre -- To unsubscribe from this list: send the line "unsubscribe ceph-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
