Re: Question about the implementation of bucket_straw_choose in src/crush/mapper.c

[Sage Weil <sage@newdream.net>]

On Thu, 29 Mar 2012,  wrote:
> Hi everyone, i'm proceeding reading source code of crush
> 
> i'm reading src/crush/mapper.c which is describing the core
> implementation of crush alg.
> in reading function bucket_straw_choose, i compare the implementation
> with the idea written in the thesis and have some problem
> understanding it.
> 
> in the thesis, it said that the length of straw should multiply the
> weight of bucket item so that heavier items are more likely to be
> selected.
> in bucket_straw_choose, i see bucket->straws multiplying the hash value only.
> 
> next, i referred to crush.h to take a look at the data structure of
> crush_bucket_straw, and found two members named 'straws' and
> 'item_weights'.
> 
> i just don't know whether 'weight' and 'straw' in the implementation
> mean the same thing as in thesis. if so, why item_weights is not used
> in bucket_straw_choose.

The length of the straw is not directly proportional to the weight, and is 
non-trivial.  When the bucket is built/adjusted, the straw lengths are 
calculated so that the actual choose/placement calculation is fast and 
simple.

See crush_calc_straw() in src/crush/builder.c for the straw calculation.  
I needed to draw a picture for it to make any sense.

sage