3 Apr
2020
3 Apr
'20
4:12 p.m.
Hi,
I am trying to understand **Straw2** bucket used in **CRUSH algorithm** of
**Ceph**. I have some specific questions. The code is given below:
**Questions:**
- Why there is a need of taking **log** of **hash value**?
- Is **x** the **placement ps** calculated by **crush_hash32_2** function?
- What function **crush_ln()** in the given code (mapper.c) is actually
computing? I am confused by the comment **2^44*log2(input+1)**.
- Why there is a need of creating a negative number based on **ln (natural
log)** of hash value?
Please help me understand these points.
Thanks in advance
3 Apr
3 Apr
6:05 p.m.
Here's Sage's initial writeup:
https://www.spinics.net/lists/ceph-devel/msg21635.html
-Sam
On Fri, Apr 3, 2020 at 12:12 PM Bobby <italienisch1987(a)gmail.com> wrote:
Hi,
I am trying to understand **Straw2** bucket used in **CRUSH algorithm** of **Ceph**. I
have some specific questions. The code is given below:
**Questions:**
- Why there is a need of taking **log** of **hash value**?
- Is **x** the **placement ps** calculated by **crush_hash32_2** function?
- What function **crush_ln()** in the given code (mapper.c) is actually computing? I am
confused by the comment **2^44*log2(input+1)**.
- Why there is a need of creating a negative number based on **ln (natural log)** of hash
value?
Please help me understand these points.
Thanks in advance
_______________________________________________
Dev mailing list -- dev(a)ceph.io
To unsubscribe send an email to dev-leave(a)ceph.io
5 Apr
5 Apr
8:50 p.m.
cool ! That helped a lot ! Is there any more source or sources that can
explain Straw2 bucket more in detail. Or lets say mapper.c code
walkthrough?
Bobby
On Fri, Apr 3, 2020 at 11:05 PM Sam Just <sjust(a)redhat.com> wrote:
Here's Sage's initial writeup:
https://www.spinics.net/lists/ceph-devel/msg21635.html
-Sam
On Fri, Apr 3, 2020 at 12:12 PM Bobby <italienisch1987(a)gmail.com> wrote:
Hi,
I am trying to understand **Straw2** bucket used in **CRUSH algorithm**
of
**Ceph**. I have some specific questions. The code is given below:
**Questions:**
- Why there is a need of taking **log** of **hash value**?
- Is **x** the **placement ps** calculated by **crush_hash32_2**
function?
- What function **crush_ln()** in the given code
(mapper.c) is actually
computing? I am confused by the comment
**2^44*log2(input+1)**.
- Why there is a need of creating a negative
number based on **ln
(natural log)** of hash value?
Please help me understand these points.
Thanks in advance
_______________________________________________
Dev mailing list -- dev(a)ceph.io
To unsubscribe send an email to dev-leave(a)ceph.io
7 Apr
7 Apr
12:24 p.m.
New subject: 回复： Straw2 Bucket related questions
Hi,
Here is my understanding for the straw2 algorithms, may it would help:
The straw2 algorithms is pseudo-random route algorithms for each pg to determine which osd
to store it. Maybe the straw2 algorithms’ name comes from the phrase `drawing
straws` https://en.wikipedia.org/wiki/Drawing_strawsraws, as the process for
determining which osd to store the pg is all osds drawing straws, and the osd who gets the
longest/highest straw wins and store the pg. Each osd’s straw is computed by its own
characteristics, it has nothing to do with other osds, so when adding or removing
osd, the least pgs will be moved.
And we know, in ceph's cluster, we can have osds with different disk size, for example
some osds with 4TB disk size, and some osds with 8TB disk size, how the straw2 algorithms
distribute all the pgs among these osd to keep 8TB’s osd has two times pgs than 4TB’s osd.
Here is the brilliant, for each osd, there is a `crush weight`, for example, the crush
weight of 8TB’s osd is about 8, and the crush weight of 4TB’s osd is about 4. And if each
straw is computed by using uniform distribution between 0 and crush weight, the
probability of 8TB's osd winning over 4TB's osd is MORE THAN two
times. But if each straw is computed by using exponential distribution with the
crush weight as its lambda λ, the probability of 8TB’s osd winning over 4TB’s osd
is JUST two times. The main code lies:
https://github.com/ceph/ceph/blob/master/src/crush/mapper.c#L334
And beside crush weight, there is `osd weight` for each osd, osd weight is between 0.0 and
1.0. If osd weight is zero, it means this osd is out, and if osd weight is 1.0, this means
is fully in. If the osd who's state is out wins the draw straws process, this pg will
be retryed to choose a different osd. And if osd weight is between this, for
example, if osd weight is 0.8, this mean this osd is 80% partially in. This
means 20% of all the pgs that this osd wins to store will be retryed to choose a different
osd.
https://github.com/ceph/ceph/blob/master/src/crush/mapper.c#L424
Best wishes,
Yao Zongyou
------------------ 原始邮件 ------------------
发件人: "Bobby"<italienisch1987@gmail.com>;
发送时间: 2020年4月6日(星期一) 上午7:50
收件人: "Sam Just"<sjust(a)redhat.com&gt;hat.com>;
抄送: "dev"<dev@ceph.io>;
主题: Re: Straw2 Bucket related questions
cool ! That helped a lot ! Is there any more source or sources that can
explain Straw2 bucket more in detail. Or lets say mapper.c code
walkthrough?
Bobby
On Fri, Apr 3, 2020 at 11:05 PM Sam Just <sjust(a)redhat.com&gt; wrote:
Here's Sage's initial writeup:
https://www.spinics.net/lists/ceph-devel/msg21635.html
-Sam
On Fri, Apr 3, 2020 at 12:12 PM Bobby <italienisch1987(a)gmail.com&gt; wrote:
>
> Hi,
>
> I am trying to understand **Straw2** bucket used in **CRUSH algorithm** of
**Ceph**. I have some specific questions. The code is given below:
>
> **Questions:**
>
> - Why there is a need of taking **log** of **hash value**?
> - Is **x** the **placement ps** calculated by **crush_hash32_2** function?
> - What function **crush_ln()** in the given code (mapper.c) is actually
computing? I am confused by the comment **2^44*log2(input+1)**.
> - Why there is a need of creating a negative number based on **ln (natural
log)** of hash value?
>
> Please help me understand these points.
>
> Thanks in advance
> _______________________________________________
> Dev mailing list -- dev(a)ceph.io
> To unsubscribe send an email to dev-leave(a)ceph.io
3:50 p.m.
Hi,
Thanks a lot Yao !...Perfect explanation ! Also I dig some old posts to
understand. Luckily this concept is clear :-). Now taking it further.
I am stuck at this natural log and lookup table point. The question is:
What is the current implementation? Does the current implementation uses*
natural log* or *look up table*? Or there is any log hack?
I have read following Sage's comment from 2014:
"*Unfortunately, we need a natural log, which is expensive. We use a
lookup table here*."
I will be really grateful if some of you can explain me briefly about this
confusion. Totally confused on this log and look up table point :-)
BR
Bobby !
On Tue, Apr 7, 2020 at 5:24 PM 姚宗友 <yaozongyou(a)vip.qq.com> wrote:
Hi,
Here is my understanding for the straw2 algorithms, may it would help:
The straw2 algorithms is pseudo-random route algorithms for each pg to
determine which osd to store it. Maybe the straw2 algorithms’ name comes
from the phrase `drawing straws`
https://en.wikipedia.org/wiki/Drawing_straws, as the process for
determining which osd to store the pg is all osds drawing straws, and the
osd who gets the longest/highest straw wins and store the pg. Each osd’s
straw is computed by its own characteristics, it has nothing to do with
other osds, so when adding or removing osd, the least pgs will be moved.
And we know, in ceph's cluster, we can have osds with different disk size,
for example some osds with 4TB disk size, and some osds with 8TB disk size,
how the straw2 algorithms distribute all the pgs among these osd to keep
8TB’s osd has two times pgs than 4TB’s osd. Here is the brilliant, for each
osd, there is a `crush weight`, for example, the crush weight of 8TB’s osd
is about 8, and the crush weight of 4TB’s osd is about 4. And if each straw
is computed by using uniform distribution between 0 and crush weight, the
probability of 8TB's osd winning over 4TB's osd is MORE THAN two times. But
if each straw is computed by using exponential distribution with the crush
weight as its lambda λ, the probability of 8TB’s osd winning over 4TB’s
osd is JUST two times. The main code lies:
https://github.com/ceph/ceph/blob/master/src/crush/mapper.c#L334
And beside crush weight, there is `osd weight` for each osd, osd weight is
between 0.0 and 1.0. If osd weight is zero, it means this osd is out, and
if osd weight is 1.0, this means is fully in. If the osd who's state is out
wins the draw straws process, this pg will be retryed to choose a different
osd. And if osd weight is between this, for example, if osd weight is
0.8, this mean this osd is 80% partially in. This means 20% of all the
pgs that this osd wins to store will be retryed to choose a different osd.
https://github.com/ceph/ceph/blob/master/src/crush/mapper.c#L424
Best wishes,
Yao Zongyou
------------------ 原始邮件 ------------------
*发件人:* "Bobby"<italienisch1987(a)gmail.com>87@gmail.com>;
*发送时间:* 2020年4月6日(星期一) 上午7:50
*收件人:* "Sam Just"<sjust(a)redhat.com>hat.com>;
*抄送:* "dev"<dev(a)ceph.io>;dev@ceph.io>;
*主题:* Re: Straw2 Bucket related questions
cool ! That helped a lot ! Is there any more source or sources that can
explain Straw2 bucket more in detail. Or lets say mapper.c code
walkthrough?
Bobby
On Fri, Apr 3, 2020 at 11:05 PM Sam Just <sjust(a)redhat.com> wrote:
> Here's Sage's initial writeup:
> https://www.spinics.net/lists/ceph-devel/msg21635.html
> -Sam
>
> On Fri, Apr 3, 2020 at 12:12 PM Bobby <italienisch1987(a)gmail.com> wrote:
> >
> > Hi,
> >
> > I am trying to understand **Straw2** bucket used in **CRUSH algorithm**
> of **Ceph**. I have some specific questions. The code is given below:
> >
> > **Questions:**
> >
> > - Why there is a need of taking **log** of **hash value**?
> > - Is **x** the **placement ps** calculated by **crush_hash32_2**
> function?
> > - What function **crush_ln()** in the given code (mapper.c) is actually
> computing? I am confused by the comment **2^44*log2(input+1)**.
> > - Why there is a need of creating a negative number based on **ln
> (natural log)** of hash value?
> >
> > Please help me understand these points.
> >
> > Thanks in advance
> > _______________________________________________
> > Dev mailing list -- dev(a)ceph.io
> > To unsubscribe send an email to dev-leave(a)ceph.io
>
>
1486
days inactive
1490
days old
4 comments
3 participants
participants (3)
-
Bobby -
Sam Just -
姚宗友