لایه‌های پایینی (۶): ‏CRUSH‏ در سطح بیت، از ‏rjenkins‏ تا ‏upmap‏

۲۸-۱ مقدمه: ‏CRUSH‏ چگونه «حساب» می‌کند؟#

در فصل‌های ۱ و ۸ ‏CRUSH‏ را به‌عنوان الگوریتمی دیدیم که بدون جدول مرکزی جای هر ‏PG‏ را تعیین می‌کند. این فصل تا سطح بیت پایین می‌رود: ‏hash‏های ‏rjenkins‏ که هر تصمیم را تعیین‌پذیر می‌کنند، الگوریتم ‏straw2‏ با جدول لگاریتم ‏fixed-point‏، اجرای گام‌به‌گام ‏crush_do_rule‏، تلاش‌های مجدد هنگام تصادم، و در پایان این‌که ‏choose_args‏، ‏weight-set‏ و ‏upmap‏ نتیجه‌ی خام ‏CRUSH‏ را چگونه اصلاح می‌کنند. یک مثال کامل را از نام شیء تا انتخاب ‏host‏ با اعدادی دنبال می‌کنیم که با کامپایل همان کد ‏C‏ مربوط به ‏Ceph‏ (‏src/crush/hash.c‏ و ‏mapper.c‏، ‏LGPL‏) در یک برنامه‌ی آزمایشی کوچک محاسبه شده‌اند.

۲۸-۲ از نام شیء تا ‏x‏#

‏ceph_stable_mod(x, b, bmask)‏ در ‏include/rados.h‏ تعریف شده است: اگر ‏x & bmask‏ کمتر از ‏b‏ باشد، همان را برمی‌گرداند، وگرنه ‏x & (bmask >> 1)‏. این تابع «پایدار» است، چون وقتی ‏pg_num‏ از ۱۲۸ به ۱۹۲ افزایش می‌یابد، فقط ‏PG‏هایی که بیت جدید را دارند جابه‌جا می‌شوند (‏split‏) و بقیه همان شماره را نگه می‌دارند. این دلیل ریاضی آن است که ‏split‏ فقط بخشی از داده را حرکت می‌دهد.

۲۸-۲-۱ ‏hash‏ مربوط به ‏rjenkins‏#

‏crush_hashmix(a, b, c)‏ نُه دور تفریق، ‏XOR‏ و شیفت روی سه کلمه‌ی ۳۲ بیتی است، برگرفته از تابع ترکیب ‏Bob Jenkins‏. نسخه‌ی سه‌ورودی ‏crush_hash32_rjenkins1_3(a, b, c)‏ با ‏hash = 1315423911 ^ a ^ b ^ c‏ (ثابت ‏crush_hash_seed‏) شروع می‌کند و پنج بار ‏mix‏ را با ثابت‌های ‏x = 231232‏ و ‏y = 1232‏ اجرا می‌کند. ویژگی مهم آن تعیین‌پذیری کامل روی همه‌ی معماری‌ها است: فقط عملیات صحیح بدون علامت ۳۲ بیتی دارد، بدون اعشار. به همین دلیل کلاینت هسته‌ی لینوکس (که همین فایل را در ‏net/ceph/crush/‏ دارد) و ‏librados‏ دقیقاً همان نتیجه را می‌گیرند.

۲۸-۳ ‏straw2‏: قرعه‌کشی نمایی#

فرض کنید هر آیتم ‏i‏ با وزن ‏w_i‏ یک متغیر تصادفی نمایی با نرخ ‏w_i‏ بکشد. احتمال این‌که آیتم ‏i‏ کمترین مقدار را داشته باشد، دقیقاً ‏$w_i / \sum w$‏ است. ‏straw2‏ همین را بدون عدد اعشاری پیاده می‌کند:

straw2 (منطق mapper.c، LGPL؛ نمایش ساده‌شده از این کتاب)
  for each item i in bucket:
      u    = crush_hash32_3(bucket.hash, x, id_i, r) & 0xFFFF       # 16 بیت
      ln   = crush_ln(u) − 2^48          # ≈ 2^44 · log2((u+1)/2^16) ≤ 0
      draw = ln / weight_i                # weight در 16.16 fixed-point
  return item with max draw              # کمترین −ln/w = نمایی با نرخ w

‏crush_ln(x)‏ مقدار ‏$2^{44} \cdot \log_2(x+1)$‏ را با دو جدول ‏__RH_LH_tbl‏ و ‏__LL_tbl‏ (در ‏crush_ln_table.h‏) و فقط با عملیات صحیح محاسبه می‌کند. ابتدا ورودی را نرمال می‌کند (توان)، سپس با ۸ بیت بالای ‏mantissa‏ در جدول اول (تقریب ۱/‏x‏ و ‏log2‏) و با ۸ بیت بعدی در جدول دوم (تصحیح) جست‌وجو می‌کند. نتیجه‌ها در برنامه‌ی آزمایشی ما: ‏crush_ln(0) = 0‏، ‏crush_ln(0x7FFF) = 0xF00000000000‏ (یعنی ‏$15 \cdot 2^{44}$‏) و ‏crush_ln(0xFFFF) = 0xFFFFF0000000‏ (تقریباً ‏$16 \cdot 2^{44} = 2^{48}$‏).

بررسی توزیع: در همان برنامه، با سه آیتم با وزن‌های ۱، ۱ و ۲ و ۳۰۰٬۰۰۰ مقدار ‏x‏، شمارش برنده‌ها ۷۵,۲۷۴، ۷۴,۷۵۳ و ۱۴۹,۹۷۳ بود، یعنی ۲۵٪، ۲۵٪ و ۵۰٪، همان‌طور که نظریه پیش‌بینی می‌کند.

۲۸-۴ ‏crush_do_rule‏ گام‌به‌گام#

یک قاعده آرایه‌ای از گام‌هاست (‏crush_rule_step‏ با ‏op‏، ‏arg1‏ و ‏arg2‏). ‏crush_do_rule‏ یک بردار کاری ‏w‏ و یک بردار خروجی ‏o‏ دارد:

‏numrep‏: اگر ‏arg1‏ ≤ ۰ باشد، ‏numrep‏ = ‏result_max‏ + ‏arg1‏. پس ‏0‏ یعنی «به تعداد ‏size‏» و ‏-1‏ یعنی «‏size‏ منهای یک». این برای قواعدی مثل «یکی در ‏DC‏ اول، بقیه در ‏DC‏ دوم» استفاده می‌شود.

۲۸-۴-۱ ‏firstn‏ در برابر ‏indep‏#

در ‏firstn‏، ترتیب مهم نیست. اگر ‏replica‏ دوم ناموجود شود، ‏replica‏ سوم جایش را می‌گیرد و همه‌چیز یک خانه به جلو می‌رود. برای ‏replication‏ این بهینه است، چون فقط یک کپی تازه لازم است. در ‏indep‏، جایگاه ‏r‏ ام همیشه ‏shard r‏ ام است. اگر ‏OSD‏ یک ‏shard‏ از دست برود، فقط همان جایگاه با ‏r‏ تازه (‏r‏ + ‏numrep‏ · ‏ftotal‏) دوباره انتخاب می‌شود و بقیه‌ی ‏shard‏ها جابه‌جا نمی‌شوند. برای ‏EC‏ این حیاتی است، چون ‏shard‏ها قابل‌جابه‌جایی نیستند.

ceph osd getcrushmap -o cm.bin && crushtool -d cm.bin -o cm.txt
crushtool -i cm.bin --test --rule 0 --num-rep 3 --min-x 0 --max-x 1023 --show-utilization
crushtool -i cm.bin --test --rule 0 --num-rep 3 --x 0x36d15c32 --show-mappings
crushtool -i cm.bin --test --show-bad-mappings --rule 0 --num-rep 3
ceph osd map rbd rbd_data.10ab2c3d4e5f.0000000000000000     # pg و up/acting

۲۸-۵ ‏choose_args‏، ‏weight-set‏ و ‏upmap‏#

‏choose_args‏: در ‏bucket_straw2_choose‏، تابع ‏get_choose_arg_weights‏ اگر ‏weight_set‏ موجود باشد، به‌جای ‏item_weights‏ از ‏weight_set[position]‏ استفاده می‌کند. ‏position‏ شماره‌ی ‏replica‏ در حال انتخاب است. این امکان اصلاح یک مشکل ظریف را می‌دهد: در ‏straw2‏ با وزن‌های نابرابر، ‏replica‏ دوم و سوم کمی از نسبت وزن منحرف می‌شوند، چون انتخاب‌های قبلی کنار گذاشته شده‌اند. ‏weight-set‏ برای هر ‏position‏ وزن کمی متفاوتی می‌دهد. ‏ids‏ جایگزین هم وجود دارد، تا بتوان ‏hash‏ را بدون تغییر شناسه‌ی واقعی ‏bucket‏ عوض کرد.

‏upmap‏: ‏OSDMap::_apply_upmap‏ ابتدا ‏pg_upmap‏ (جایگزینی کل فهرست) را بررسی می‌کند، سپس ‏pg_upmap_items‏ (جفت‌های ‏from‏→‏to‏) و در پایان ‏pg_upmap_primaries‏ (فقط تعیین ‏primary‏، برای ‏read balancer‏). ‏upmap‏هایی که قاعده‌ی ‏CRUSH‏ را نقض کنند (مثلاً دو ‏replica‏ در یک ‏host‏) توسط ‏mon‏ بررسی و حذف می‌شوند (‏clean_pg_upmaps‏).

ceph osd pg-upmap-items 3.15 4 11        # جایگزینی osd.4 با osd.11 برای PG 3.15
ceph osd rm-pg-upmap-items 3.15
ceph osd crush weight-set ls
ceph balancer status && ceph balancer eval
ceph osd dump | grep -E '^pg_upmap(_items|_primary)?' | head

۲۸-۶ ‏is_out‏ و ‏reweight‏: یک مثال عددی#

‏is_out‏ در ‏mapper.c‏ وزن ‏reweight‏ یک ‏OSD‏ (عددی ۱۶.۱۶ بین ۰ و ۰‏x10000‏) را این‌طور تفسیر می‌کند: اگر وزن کامل باشد، ‏OSD‏ داخل است. اگر صفر باشد، بیرون است. در غیر این صورت، ‏crush_hash32_2(x, osd) & 0xFFFF‏ با وزن مقایسه می‌شود و اگر کمتر باشد، ‏OSD‏ برای این ‏x‏ داخل است. پس ‏reweight‏ برابر ۰.۵ یعنی تقریباً نیمی از ‏PG‏هایی که ‏CRUSH‏ به این ‏OSD‏ داده بود، رد می‌شوند و با تلاش مجدد به جای دیگری می‌روند.

۲۸-۷ ‏device class‏ و ‏shadow tree‏#

وقتی ‏OSD‏ها کلاس دارند (‏hdd‏، ‏ssd‏، ‏nvme‏)، ‏CrushWrapper‏ برای هر ‏bucket‏ و هر کلاس یک «سایه» با ‏id‏ منفی جدید و نامی مثل ‏default~ssd‏ می‌سازد که فقط ‏OSD‏های آن کلاس را دارد. قاعده‌ای مثل ‏step take default class ssd‏ در واقع ‏TAKE‏ روی ‏id‏ سایه است. چون سایه‌ها ‏id‏های خودشان را دارند، ‏hash‏ مربوط به ‏straw2‏ (که ‏id‏ آیتم در آن دخیل است) برای سایه‌ها مستقل از درخت اصلی است. افزودن یک ‏OSD‏ از نوع ‏hdd‏ هیچ ‏PG‏ی را در ‏pool‏های ‏ssd‏ جابه‌جا نمی‌کند.

ceph osd crush tree --show-shadow
ceph osd crush rule create-replicated fast default host ssd
ceph osd crush class ls-osd ssd

۲۸-۸ سه نوع ‏bucket‏ دیگر: ‏uniform‏، ‏list‏ و ‏tree‏#

‏straw2‏ امروز پیش‌فرض است، اما ‏CRUSH‏ از ابتدا پنج الگوریتم ‏bucket‏ داشت: ‏uniform‏، ‏list‏، ‏tree‏، ‏straw‏ و ‏straw2‏. هرکدام مصالحه‌ای میان سرعت انتخاب و میزان جابه‌جایی داده هنگام تغییر است. نگاشت‌های قدیمی و نقشه‌های دست‌ساز هنوز ممکن است آن‌ها را داشته باشند. برای فهم اینکه چرا ‏straw2‏ برنده شد، هر سه را با ‏hash‏ واقعی ‏rjenkins‏ اجرا کرده‌ایم. همه‌ی اعداد این بخش با یک برنامه‌ی کوچک ‏C‏ که ‏hash.c‏ و ‏crush_ln‏ را از کد ‏Ceph‏ می‌گیرد محاسبه شده‌اند.

۲۸-۸-۱ ‏uniform‏: جایگشت شبه‌تصادفی#

pseudocode (برگرفته از bucket_perm_choose)
pr = r mod size
if x changed:
    if pr == 0: return items[hash3(x, bucket_id, 0) mod size]        # میان‌بر رایج
    perm = [0..size-1]; perm_n = 0
while perm_n ≤ pr:                         # Fisher–Yates تدریجی با hash به‌جای random
    p = perm_n
    if p < size-1:
        i = hash3(x, bucket_id, p) mod (size − p)
        swap(perm[p], perm[p+i])
    perm_n += 1
return items[perm[pr]]

‏uniform‏ فقط وقتی درست کار می‌کند که همه‌ی ‏item‏ها وزن برابر داشته باشند، چون وزن اصلاً در محاسبه نیست. مشکل بزرگ‌تر این است که تغییر ‏size‏ پیمانه‌ی همه‌ی ‏hash‏ها را عوض می‌کند. شبیه‌سازی ما نشان می‌دهد افزودن ‏item‏ پنجم به چهار ‏item‏، ۸۰٪ ورودی‌ها را جابه‌جا می‌کند، در حالی که حداقل لازم ۲۰٪ است. این ‏bucket‏ برای سخت‌افزاری طراحی شد که همیشه یک‌جا و هم‌اندازه خریده و جایگزین می‌شود.

۲۸-۸-۲ ‏list‏: پیمایش از آخر#

for i = size-1 down to 0:
    h = hash4(x, items[i], r, bucket_id) & 0xFFFF                   # عدد 16 بیتی
    if (h × sum_weights[i]) >> 16 < item_weights[i]: return items[i]
return items[0]
# sum_weights[i] = Σ_{j ≤ i} item_weights[j]  ⇒ احتمال انتخاب i به شرط رسیدن به آن = w_i / sum_i

چرا درست است؟ احتمال انتخاب ‏item‏ آخر ‏w‏₂/(‏w‏₀+‏w‏₁+‏w‏₂) = ۲/۴ است. اگر رد شود، احتمال ‏item‏ میانی ‏w‏₁/(‏w‏₀+‏w‏₁) = ۱/۲ است. پس ‏P‏(۲۱) = (۱ − ۱/۲) × ۱/۲ = ۱/۴ و ‏P‏(۲۰) = ۱/۴. شمارش روی ۴۰۰ هزار ورودی همین نسبت ۱:۱:۲ را داد (۱۰۰۳۳۶، ۹۹۹۷۰، ۱۹۹۶۹۴). افزودن ‏item‏ به انتها فقط داده‌ی لازم را جابه‌جا می‌کند (۲۰٫۱٪). اما حذف یک ‏item‏ از میانه ترتیب را می‌شکند (در شبیه‌سازی ما ۳۶٪ به‌جای ۲۵٪).

۲۸-۸-۳ ‏tree‏: درخت دودویی وزن‌دار#

node(i) = 2(i+1) − 1   (برگ‌ها فرد)؛ height(n) = تعداد صفرهای انتهایی n
n = num_nodes / 2                          # ریشه
while n is even:                           # گره داخلی
    t = (hash4(x, n, r, bucket_id) × node_weights[n]) >> 32     # عدد یکنواخت در [0, w)
    n = t < node_weights[left(n)] ? left(n) : right(n)
return items[n >> 1]

ترفند زیبای ‏tree‏ شماره‌گذاری گره‌هاست. چون ‏hash‏ به شماره‌ی گره وابسته است و شماره‌ی گره‌های موجود با بزرگ شدن درخت تغییر نمی‌کند (ریشه‌ی قدیم ‏n4‏ در درخت هشت‌برگی فرزند چپ ‏n8‏ می‌شود)، افزودن ‏item‏ پنجم دقیقاً ۲۰٪ داده را جابه‌جا کرد. اما حذف از میانه و بازسازی درخت، چیدمان برگ‌ها را عوض می‌کند و در شبیه‌سازی ما ۵۴٪ جابه‌جایی داشت.

۲۸-۸-۴ مقایسه‌ی جابه‌جایی#

۲۸-۹ ‏balancer‏ در حالت ‏upmap: calc_pg_upmaps‏#

‏balancer‏ مربوط به ‏mgr‏ در حالت ‏upmap‏ (فصل ۱۹) کار اصلی را به ‏OSDMap::calc_pg_upmaps‏ در ‏C++‏ می‌سپارد. این تابع یک کپی از ‏OSDMap‏ می‌سازد، با جفت‌های ‏pg_upmap_items‏ آزمایش می‌کند و نتیجه را در یک ‏Incremental‏ برمی‌گرداند.

ppw = total_pgs / Σ weight
dev(osd) = pgs(osd) − weight(osd) × ppw
bal_score = Σ weight × (dev / target)²                  # 0 یعنی کامل
repeat up to max times:
    overfull  = {dev > max_deviation};   more_overfull  = {0 < dev ≤ max_deviation}
    underfull = {dev < −max_deviation};  more_underfull = {−max_deviation ≤ dev < 0}
    if overfull and underfull both empty: break
    for osd in OSDs by dev descending (dev > max_deviation):
        if try_drop_remap_overfull(osd): goto test       # اول upmapهای قدیمی را پس بگیر
        for pg on osd (بدون pg_upmap دستی):
            out = try_pg_upmap(pg, overfull, underfull)   # CRUSH را با وزن صفر برای overfullها دوباره اجرا کن
            pos = find_best_remap(orig, out)            # بهترین یک جایگزینی
            if pos ≥ 0: add pair (orig[pos] → out[pos]); goto test
    for osd in underfull: try_drop_remap_underfull(osd) → test
    break
test: if new_bal_score > bal_score: reject (پرش از آن PG)  else: apply

مثال عددی. چهار ‏OSD‏ هم‌وزن، یک ‏pool‏ با ۶۴ ‏PG‏ و ‏size=3‏، پس ۱۹۲ نسخه و هدف ۴۸ برای هر ‏OSD‏. شمارش‌ها [۵۶، ۵۰، ۴۴، ۴۲] و انحراف‌ها [+۸، +۲، −۴، −۶] است. با ‏upmap_max_deviation=5‏ (پیش‌فرض ماژول ‏balancer‏): ‏overfull={osd.0}‏، ‏underfull={osd.3}‏. امتیاز = (۶۴ + ۴ + ۱۶ + ۳۶)/۴۸² = ۰.۰۵۲۱.

پس از گام ۳، هیچ ‏OSD‏ی بیش از ۵ انحراف ندارد، پس ‏overfull‏ و ‏underfull‏ خالی‌اند و حلقه پایان می‌یابد. از گام ۲ به بعد ‏underfull‏ خالی است و جایگزین‌ها از ‏more_underfull‏ می‌آیند. سه ورودی ‏pg_upmap_items‏ در ‏OSDMap‏ ثبت می‌شوند. هر تغییر فقط یک جفت اضافه می‌کند. توضیح کد می‌گوید این کار عمداً «آرام» است تا هر گام کوچک توزیع را واقعاً به سمت حالت کامل ببرد. فرض این مثال آن است که قانون ‏CRUSH‏ اجازه‌ی این جایگزینی‌ها را بدهد (مثلاً ‏OSD‏ها در ‏host‏های متفاوت باشند). اگر جایگزینی قانون ‏failure domain‏ را بشکند، ‏try_pg_upmap‏ آن را رد می‌کند.

۲۸-۱۰ قانون‌های ‏MSR‏: چند ‏OSD‏ در هر ‏failure domain‏#

در ‏EC‏ با ‏k+m‏ بزرگ‌تر از تعداد ‏host‏ها (مثلاً ۴+۲ روی سه ‏host‏)، قانون کلاسیک ‏choose indep 3 type host‏ و سپس ‏chooseleaf indep 2 type osd‏ یک مشکل دارد. اگر یک ‏OSD out‏ شود، مرحله‌ی دوم فقط در همان ‏host‏ دنبال جایگزین می‌گردد. اگر آن ‏host OSD‏ سالم دیگری نداشته باشد، ‏shard‏ بی‌جا می‌ماند، چون ‏CRUSH‏ کلاسیک نمی‌تواند به مرحله‌ی قبل برگردد. قانون‌های ‏MSR‏ (‏Multi-Step Retry‏) از ‏Squid‏ با نوع‌های ‏msr_firstn‏ و ‏msr_indep‏ و گام ‏choosemsr‏ این را حل می‌کنند: کل نزول از ریشه دوباره تلاش می‌شود.

pseudocode
total = Π(arg1 of choosemsr steps)      # مثلاً 3 × 2 = 6
for descent in 0 .. msr_descents-1 while خروجی کامل نیست:
    crush_msr_choose(root, [0, total), step0, tryno = descent)
crush_msr_choose(bucket, [start, end), step):
    num_strides = step.arg1 (یا result_max اگر 0)
    stride_length = (end − start) / num_strides
    for each stride:
        if همه‌ی شاخص‌های stride پر شده‌اند: continue
        for local_try in 0 .. msr_collision_tries-1:
            r = ((descent × result_max + index) << 16) + local_try
            cand = crush_msr_descend(bucket, step.type, r)          # straw2 و ... تا نوع هدف
            if cand در stride دیگری استفاده شده (collision): continue
            if آخرین گام: اگر OSD out است ⇒ شاخص خالی بماند (undo پس از دور)
            else: crush_msr_choose(cand, [stride], step+1) برای سطح بعد

مثال عددی. با ‏choosemsr 3 host‏ و ‏choosemsr 2 osd‏، ‏total_descendants‏ = ۶، ‏num_strides‏ = ۳ و ‏stride_length‏ = ۲. در فراخوانی بازگشتی برای هر ‏host‏، ‏total_descendants‏ = ۲ و ‏stride_length‏ = ۱ است (این‌ها همان اعداد توضیح بالای ‏crush_msr_choose‏ در کد هستند). مقدار تلاش برای ‏descent=1‏، ‏result_max=6‏، ‏index=3‏ و ‏local_try=0‏ برابر ((۱×۶+۳) ≪ ۱۶) + ۰ = ۹ × ۶۵۵۳۶ = ۵۸۹۸۲۴ است. پس ‏hash‏ها در هر دور کاملاً متفاوت‌اند. تضمین گام ‏choosemsr 3 host‏ «دست‌کم» سه ‏host‏ است، نه «دقیقاً» سه: یک ‏stride‏ ممکن است پس از ‏out‏ شدن یک ‏OSD‏ از دو ‏host‏ استفاده کند، به شرط آنکه آن ‏host‏ها در ‏stride‏های دیگر نباشند.

۲۸-۱۱ تکمیلی و به‌روز#

• قواعد ‏MSR‏ (‏CRUSH_RULE_CHOOSE_MSR‏ و انواع ‏CRUSH_RULE_TYPE_MSR_FIRSTN‏ و ‏MSR_INDEP‏) در کد ‏Squid‏ و ‏main‏ وجود دارند و در ‏Reef‏ نیستند. هدف آن‌ها قرار دادن چند ‏shard‏ در یک ‏failure domain‏ با کنترل دقیق است (مثلاً ‏EC 8+6‏ روی ۴ ‏rack‏).
• هسته‌ی لینوکس همین ‏mapper.c‏، ‏hash.c‏ و ‏crush_ln_table.h‏ را در ‏net/ceph/crush/‏ دارد. پشتیبانی آن از قابلیت‌های جدید ‏CRUSH‏ (مثل ‏MSR‏) به نسخه‌ی هسته بستگی دارد و قابلیت‌های خوشه باید با ‏ceph osd set-require-min-compat-client‏ هماهنگ شود.

۲۸-۱۲ تمرین عملی#

1. ۱. برنامه‌ی آزمایشی این فصل را بازسازی کنید: فایل‌های ‏hash.c‏ و ‏crush_ln_table.h‏ را از کد ‏Ceph‏ بردارید و ‏bucket_straw2_choose‏ را برای ‏bucket‏ی با پنج آیتم و وزن‌های دلخواه اجرا کنید. توزیع را برای یک میلیون ‏x‏ بسنجید.
2. ۲. با ‏ceph osd map‏ چند شیء را نگاشت کنید و ‏ps‏ را با محاسبه‌ی دستی ‏ceph_stable_mod‏ تطبیق دهید.
3. ۳. وزن یک ‏host‏ را در یک نقشه‌ی آزمایشی ۱۰٪ زیاد کنید و با ‏crushtool --compare‏ تعداد ‏PG‏های جابه‌جاشده و مقصد آن‌ها را ببینید (باید فقط به همان ‏host‏ منتقل شوند).
4. ۴. یک ‏pg-upmap-items‏ دستی بسازید که دو ‏replica‏ را در یک ‏host‏ قرار دهد و ببینید ‏mon‏ با آن چه می‌کند.

۲۸-۱۳ پرسش‌های مرور#

1. ۱. ‏ceph_stable_mod‏ چگونه حرکت داده را هنگام افزایش ‏pg_num‏ محدود می‌کند؟
2. ۲. چرا ‏HASHPSPOOL‏ لازم است؟
3. ۳. چرا ‏CRUSH‏ فقط از عملیات صحیح استفاده می‌کند؟
4. ۴. در ‏straw2‏، ‏draw‏ چگونه محاسبه می‌شود و چرا بیشترین ‏draw‏ برنده است؟
5. ۵. ‏crush_ln‏ چه چیزی را با چه دقتی برمی‌گرداند؟
6. ۶. چرا ‏straw2‏ حرکت حداقلی دارد و ‏straw‏ قدیمی نداشت؟
7. ۷. تصادم در ‏firstn‏ چگونه حل می‌شود و سقف آن چیست؟
8. ۸. تفاوت ‏firstn‏ و ‏indep‏ برای ‏EC‏ چیست؟
9. ۹. ‏weight-set‏ در ‏choose_args‏ چه مشکلی را حل می‌کند؟
10. ۱۰. ترتیب اعمال ‏upmap‏ها چیست و ‏mon‏ با ‏upmap‏ نامعتبر چه می‌کند؟

پاسخ این پرسش‌ها در پیوست ه: پاسخ پرسش‌ها آمده است. پاسخ پرسش‌های این فصل →

۲۸-۱۴ منابع این فصل#

• مقاله‌ی ‏CRUSH‏ (Weil و همکاران، ‏SC 2006‏
  https://ceph.io/assets/pdfs/weil-crush-sc06.pdf
• ‏mapper.c‏
  https://github.com/ceph/ceph/blob/main/src/crush/mapper.c
• ‏hash.c‏
  https://github.com/ceph/ceph/blob/main/src/crush/hash.c
• ‏CRUSH maps‏
  https://docs.ceph.com/en/latest/rados/operations/crush-map/
• ویرایش ‏CRUSH map‏
  https://docs.ceph.com/en/latest/rados/operations/crush-map-edits/
• ‏upmap‏
  https://docs.ceph.com/en/latest/rados/operations/upmap/
• ‏balancer‏
  https://docs.ceph.com/en/latest/rados/operations/balancer/
• ‏crushtool‏
  https://docs.ceph.com/en/latest/man/8/crushtool/
• تابع ‏hash‏ مربوط به ‏Bob Jenkins‏
  https://burtleburtle.net/bob/hash/doobs.html