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

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

[胡瀚森]

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.

Thanks.

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

[Sage Weil]

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

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

[zhurongze]

于 2012年03月29日 17:16, 胡瀚森 写道:
> 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.
>
> Thanks.
> --
> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
Are you chinese?  I wrote 2 articles about  CRUSH design and source code 
analysis in Chinese, I think this is useful for you.
The Link is http://toplab.sinaapp.com
--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html