کدگذاری پاک‌شونده (‏Erasure Coding‏) برای بهره‌وری ذخیره‌سازی

۱۳-۱ پیش از شروع#

۱۳-۱-۱ این فصل به چه سؤال‌هایی جواب می‌دهد؟#

تکثیر سه‌تایی ساده و سریع است، اما برای هر ترابایت داده‌ی کاربر سه ترابایت دیسک مصرف می‌کند. کدگذاری پاک‌شونده (‏Erasure Coding‏ یا ‏EC‏) با همان یا حتی بیشتر از سطح تحمل خرابی، سربار را به حدود ۱.۵ برابر یا کمتر می‌رساند. بهای آن پیچیدگی بیشتر، مصرف ‏CPU‏ و تأخیر بالاتر در نوشتن‌های کوچک است. از ۲۰۱۹ تا امروز ‏EC‏ در ‏Ceph‏ دو تحول بزرگ داشته: پیش‌فرض شدن ‏ISA-L‏ به جای ‏Jerasure‏ و معرفی ‏FastEC‏ در ‏Tentacle‏.

• ‏EC‏ چیست و پارامترهای ‏k‏ و ‏m‏ چه معنایی دارند؟
• ‏EC‏ درون ‏Ceph‏ چطور پیاده شده است: ‏stripe‏، ‏shard‏ و ‏chunk‏؟
• افزونه‌ها (‏ISA‏، ‏Jerasure‏، ‏LRC‏، ‏SHEC‏، ‏CLAY‏) چه تفاوتی دارند؟
• کجا از ‏EC‏ استفاده کنیم و کجا نه؟
• ‏pool EC‏ را چطور بسازیم و ‏overwrite‏ و ‏FastEC‏ را فعال کنیم؟
• خطای معروف «۲۱۴۷۴۸۳۶۴۷» از کجا می‌آید؟

۱۳-۲ ‏EC‏ چیست؟#

۱۳-۲-۱ ‏k+m‏#

در ‏EC‏، داده به ‏k‏ قطعه‌ی داده تقسیم می‌شود و از آن‌ها ‏m‏ قطعه‌ی ‏parity‏ محاسبه می‌شود. هر ‏k‏ قطعه از ‏k+m‏ قطعه برای بازسازی کامل داده کافی است؛ بنابراین تا ‏m‏ خرابی هم‌زمان قابل تحمل است.

ceph osd erasure-code-profile set prof-4-2 plugin=isa k=4 m=2 crush-failure-domain=host
ceph osd pool create ecpool erasure prof-4-2
ceph osd pool set ecpool allow_ec_overwrites true   # RBD, CephFS

۱۳-۲-۲ ریاضیات به زبان ساده#

کدهای ‏Reed-Solomon‏ (که ‏ISA-L‏ و ‏Jerasure‏ پیاده می‌کنند) روی میدان گالوا (معمولاً ‏$\mathrm{GF}(2^8)$‏) کار می‌کنند: هر بایت یک عنصر میدان است و جمع، ‏XOR‏ است. ‏k‏ بایت داده را بردار ‏d‏ در نظر بگیرید؛ ‏shard‏ها حاصل ضرب ماتریس مولد ‏G‏ با ابعاد (‏k+m‏)×‏k‏ در ‏d‏ هستند. ‏k‏ سطر اول ‏G‏ ماتریس همانی است (پس ‏shard‏های داده همان داده‌اند) و ‏m‏ سطر بعدی ضرایب ‏parity‏. برای بازسازی، از هر ‏k shard‏ در دسترس، زیرماتریس ‏k‏×‏k‏ متناظر را می‌گیریم و معکوس می‌کنیم. شرط کار این است که هر زیرماتریس ‏k‏×‏k‏ وارون‌پذیر باشد؛ ماتریس‌های ‏Vandermonde‏ (‏reed_sol_van‏) و ‏Cauchy‏ (‏cauchy‏) این ویژگی را دارند.

shard_i = Σ_j  G[i][j] ⊗ d_j      (⊗ ضرب در GF(2^8)، Σ همان XOR)
برای i < k:  G[i] = e_i  →  shard_i = d_i
decode:  d = (G_S)^-1 · shards_S     (S: هر k اندیس در دسترس)

۱۳-۳ ‏EC‏ درون ‏Ceph‏#

۱۳-۳-۱ ‏stripe‏، ‏shard‏ و ‏chunk‏#

در ‏pool EC‏، هر ‏PG‏ به جای «نسخه» ‏shard‏ دارد: ‏OSD‏ شماره‌ی ‏i‏ در ‏acting set‏، ‏shard i‏ است و فقط قطعه‌ی خودش را نگه می‌دارد. شیء به ‏stripe‏هایی به اندازه‌ی ‏k × stripe_unit‏ تقسیم می‌شود (پیش‌فرض ‏stripe_unit‏ چهار کیلوبایت). برای هر ‏stripe‏، ‏k‏ قطعه‌ی داده و ‏m‏ قطعه‌ی ‏parity‏ ساخته و قطعه‌ی ‏i‏ روی ‏shard i‏ ذخیره می‌شود. پس روی هر ‏OSD‏، شیء به شکل یک «شیء ‏shard‏» شامل همه‌ی قطعه‌های ‏i‏ آن شیء دیده می‌شود.

۱۳-۳-۲ ‏primary‏ در ‏EC‏#

‏primary‏ در ‏pool EC‏ مسئول ‏encode‏ و ‏decode‏ است: کلاینت فقط با ‏primary‏ صحبت می‌کند، ‏primary‏ داده را ‏encode‏ و قطعه‌ها را به ‏shard‏ها می‌فرستد. در خواندن، ‏primary‏ قطعه‌های لازم را از ‏shard‏ها جمع و در صورت نیاز ‏decode‏ می‌کند. این یعنی بار ‏CPU‏ و شبکه‌ی ‏EC‏ روی ‏primary‏ها متمرکز است.

۱۳-۳-۳ نوشتن جزئی و ‏overwrite‏#

‏EC‏ در ابتدا (پیش از ‏Luminous‏) فقط ‏append‏ را پشتیبانی می‌کرد و برای ‏RBD‏ و ‏CephFS‏ قابل استفاده نبود. پرچم ‏allow_ec_overwrites‏ (از ‏Luminous‏، که سرفصل قدیمی آن را با ‏Kraken‏ مرتبط کرده) بازنویسی را ممکن کرد. اما در پیاده‌سازی قدیمی، بازنویسی ۴ کیلوبایت در وسط یک ‏stripe‏ یعنی ‏read-modify-write‏ کامل: خواندن بقیه‌ی ‏stripe‏، ‏encode‏ دوباره و نوشتن همه‌ی ‏shard‏ها.

۱۳-۴ افزونه‌ها و پروفایل‌ها#

۱۳-۴-۱ ساخت پروفایل و ‏pool‏#

ceph osd erasure-code-profile ls
ceph osd erasure-code-profile get default
ceph osd erasure-code-profile set ec42 plugin=isa technique=reed_sol_van k=4 m=2 \
     crush-failure-domain=host crush-device-class=hdd
ceph osd pool create ecpool erasure ec42
ceph osd pool set ecpool allow_ec_overwrites true     # برای RBD و CephFS
ceph osd pool application enable ecpool rgw

۱۳-۴-۲ ‏LRC‏ و ‏CLAY‏#

# LRC: k=4 داده، m=2 parity سراسری، l=3 → هر ۳ قطعه یک parity محلی
ceph osd erasure-code-profile set lrc42 plugin=lrc k=4 m=2 l=3 crush-failure-domain=host
# CLAY: d تعداد shardهایی که در بازیابی یک shard مشارکت می‌کنند
ceph osd erasure-code-profile set clay42 plugin=clay k=4 m=2 d=5 crush-failure-domain=host

۱۳-۵ کجا ‏EC‏ و کجا تکثیر؟#

rbd create rbd/vm01 --size 200G --data-pool ecpool
rbd info rbd/vm01 | grep data_pool

۱۳-۶ ‏FastEC‏ در ‏Tentacle‏#

۱۳-۶-۱ چه چیزی تغییر کرد؟#

‏Tentacle‏ پیاده‌سازی تازه‌ای از مسیر ‏I/O‏ در ‏EC‏ اضافه کرد که مجموعاً ‏FastEC‏ نامیده می‌شود: خواندن جزئی (فقط ‏shard‏های لازم)، نوشتن جزئی، نوشتن ‏parity delta‏، حذف ‏padding‏ صفرها و صرفه‌جویی در فضای اشیای کوچک. با پرچم هر ‏pool‏ فعال می‌شود:

ceph osd pool set ecpool allow_ec_optimizations true
ceph osd pool get ecpool allow_ec_optimizations
# پیش‌فرض برای poolهای تازه
ceph config set global osd_pool_default_flag_ec_optimizations true

محدودیت‌ها طبق مستندات:

• همه‌ی ‏MON‏ها و ‏OSD‏ها باید ‏Tentacle‏ یا جدیدتر باشند؛ کلاینت‌ها نیازی به ارتقا ندارند.
• پرچم پس از فعال شدن خاموش‌شدنی نیست، چون شیوه‌ی ذخیره‌ی داده‌ی جدید را تغییر می‌دهد.
• فقط با ‏ISA-L‏ یا ‏Jerasure‏ با ‏reed_sol_van‏ کار می‌کند؛ ‏CLAY‏، ‏LRC‏ و ‏SHEC‏ رد می‌شوند.
• ‏stripe_unit‏ باید مضرب ۴ کیلوبایت باشد؛ مستندات برای بیشتر بارها ۱۶ کیلوبایت را توصیه می‌کند و برای بارهای عمدتاً خواندنی تا ۲۵۶ کیلوبایت.

ceph osd erasure-code-profile set ec42fast plugin=isa technique=reed_sol_van k=4 m=2 \
     stripe_unit=16K crush-failure-domain=host
ceph osd pool create rbd-ec erasure ec42fast
ceph osd pool set rbd-ec allow_ec_overwrites true
ceph osd pool set rbd-ec allow_ec_optimizations true

۱۳-۷ عیب‌یابی: خطای ۲۱۴۷۴۸۳۶۴۷#

در خروجی ‏ceph pg dump‏ یا ‏ceph pg map‏ برای ‏pool EC‏ گاهی به جای شماره‌ی ‏OSD‏ عدد ۲۱۴۷۴۸۳۶۴۷ می‌بینید. این عدد همان ثابت ‏CRUSH_ITEM_NONE‏ است:

/* from ceph/ceph, LGPL — src/crush/crush.h */
#define CRUSH_ITEM_NONE   0x7fffffff

معنی‌اش این است که ‏CRUSH‏ نتوانسته برای آن جایگاه ‏shard‏ یک ‏OSD‏ پیدا کند. در ‏pool‏ تکثیری، جایگاه خالی ساده حذف می‌شود؛ اما در ‏EC‏ جایگاه هر ‏shard‏ معنی دارد (‏shard 3‏ باید ‏shard 3‏ بماند)، پس به جای حذف، با ‏NONE‏ پر می‌شود. علت‌های رایج:

• تعداد دامنه‌های خرابی کمتر از ‏k+m‏ (مثلاً ۴+۲ با پنج میزبان).
• ‏OSD‏های ‏out‏ یا ‏down‏ که دامنه‌ای را خالی کرده‌اند.
• قانون ‏CRUSH‏ که کلاس دستگاه یا ‏root‏ اشتباهی دارد.
• تعداد تلاش‌های ‏CRUSH‏ کم است و در سلسله‌مراتب نامتوازن نتیجه نمی‌گیرد (‏set_choose_tries‏).

ceph pg ls-by-pool ecpool | grep -c 2147483647
ceph osd crush rule dump ecpool
ceph osd getcrushmap -o cm && crushtool -i cm --test --rule <id> --num-rep 6 --show-bad-mappings

۱۳-۸ درون ‏backend‏ مربوط به ‏EC‏: نوشتن، ‏rollback‏ و ‏recovery‏#

این بخش پلی است به فصل ۲۷ («ریاضیات ‏erasure coding‏»). در اینجا به‌جای ریاضیات، مکانیک ‏OSD‏ را بررسی می‌کنیم: یک نوشتن ‏EC‏ چگونه میان ‏shard‏ها هماهنگ می‌شود، اگر وسط کار خرابی رخ دهد چه می‌شود، و ‏recovery‏ دقیقاً چه چیزی را می‌خواند و می‌نویسد. کلاس‌های مرتبط در ‏src/osd/‏ شاخه‌ی ‏main‏ عبارت‌اند از ‏ECBackend‏، ‏ECCommon‏، ‏ECTransaction‏، ‏ECUtil‏ و نسخه‌های «‏L‏» (‏legacy‏) آن‌ها، که ‏ECSwitch‏ بر اساس پرچم ‏pool‏ میانشان انتخاب می‌کند.

۱۳-۸-۱ چرا ‏EC‏ به ‏rollback‏ نیاز دارد؟#

در ‏replication‏، هر ‏replica‏ یک کپی کامل است. اگر نوشتنی فقط روی برخی ‏replica‏ها ‏commit‏ شود، ‏recovery‏ می‌تواند همان نسخه‌ی جدید را از یک ‏replica‏ به بقیه کپی کند. در ‏EC‏ هیچ ‏shard‏ی کل داده را ندارد. اگر نوشتن روی ۳ ‏shard‏ از ۶ ‏shard commit‏ شده باشد و سپس ‏primary‏ بمیرد، نه نسخه‌ی قدیم و نه نسخه‌ی جدید از هیچ ‏k shard‏ سازگاری قابل بازسازی نیست. راه حل ‏Ceph‏ این است که تغییرات «برگشت‌پذیر» باشند: هر ورودی ‏pg log‏ در ‏EC‏ یک ‏ObjectModDesc‏ دارد و پس از ‏peering‏، ‏shard‏هایی که از نقطه‌ی توافق‌شده جلوترند، تغییرات را به عقب برمی‌گردانند.

‏pg_log_t‏ دو مرز دارد: ‏can_rollback_to‏ (ورودی‌های جدیدتر از آن قابل بازگشت‌اند) و ‏rollback_info_trimmed_to‏ (اطلاعات ‏stash‏ تا آنجا پاک شده است). وقتی ‏primary‏ مطمئن شود یک ورودی روی همه‌ی ‏shard‏ها ‏commit‏ شده، ‏can_rollback_to‏ جلو می‌رود و داده‌ی ‏stash‏ (مثلاً ‏extent‏های قدیمی ‏ROLLBACK_EXTENTS‏) می‌تواند پاک شود. این همان دلیلی است که ‏overwrite‏ در ‏EC‏ قدیمی نسبت به ‏replication‏ فضای موقت و نوشتن اضافه دارد.

۱۳-۸-۲ ‏min_size‏ پیش‌فرض و دلیل آن#

در ‏OSDMonitor::prepare_pool_size‏، برای ‏pool‏های ‏EC‏ مقدار پیش‌فرض ‏min_size = k + min(1, m − 1)‏ است (و ‏size = num_zones × (k + m)‏). یعنی برای ‏k=4‏، ‏m=2‏ مقدار ‏min_size‏ برابر ۵ است: ‏pool‏ تا وقتی دست‌کم ۵ ‏shard‏ در دسترس باشد، نوشتن را می‌پذیرد. بنابراین پس از از دست رفتن یک ‏shard‏، هنوز یک ‏shard‏ اضافه برای تحمل خرابی بعدی وجود دارد. برای ‏m=1‏، ‏min_size‏ = ‏k‏ است و هر خرابی دوم در حین ‏recovery‏ یعنی از دست رفتن داده. به همین دلیل ‏m=1‏ برای داده‌ی مهم توصیه نمی‌شود.

ceph osd pool set ecpool fast_read 1
ceph pg 5.1as2 query | jq '.info | {last_update, last_complete, log_tail}'   # shard 2 از PG 5.1a
ceph pg 5.1a list_unfound
ceph daemon osd.4 dump_ops_in_flight | jq '.ops[] | select(.description|test("ECSub"))'

۱۳-۹ کدگذاری پاک‌شونده با عدد: ماتریس ‏Reed-Solomon‏، حد ‏MDS‏، به‌روزرسانی دلتای ‏parity‏ و هزینه‌ی بازسازی#

این بخش ریاضیات پشت افزونه‌ی ‏ISA‏ را روی بایت‌های واقعی اجرا می‌کند. ارجاع‌ها به ‏src/erasure-code/isa‏ در ‏main‏ (نوامبر ۲۰۲۶) و به تابع ‏gf_gen_rs_matrix‏ در کتابخانه‌ی ‏ISA-L‏ (erasure_code/ec_base.c) است. حساب ‏$\mathrm{GF}(2^8)$‏ با چندجمله‌ای ۰‏x11d‏ در پایتون بازپیاده‌سازی و با جدول ‏gff_base‏ در ‏ISA-L‏ تطبیق داده شده است.

۱۳-۹-۱ کدگذاری و بازگشایی یک ستون بایت#

pseudocode
G[0..k−1] = I_k                        # systematic: shardهای داده همان داده‌اند
gen = 1
for i in k .. k+m−1: G[i][j] = gen^j ; gen = gen × 2      (در GF(2^8))
parity_i = ⊕_j G[i][j] ⊗ d_j
بازگشایی: k سطر سالم را انتخاب کن ← B ؛ d = B⁻¹ × (shardهای سالم)

مثال عددی (‏k‏ = ۴، ‏m‏ = ۲، بایت‌های «‏ABCD‏»). سطر ‏P0‏ همه یک است، پس ‏P0‏ = ۰‏x41‏ ⊕ ۰‏x42‏ ⊕ ۰‏x43‏ ⊕ ۰‏x44‏ = ۰‏x04‏. سطر ‏P1‏ برابر ۱، ۲، ۴ و ۸ است: ۲ ⊗ ۰‏x42‏ = ۰‏x84‏، ‏۴ ⊗ ۰‏x43‏ = ۰‏x11‏ و ۸ ⊗ ۰‏x44‏ = ۰‏x1a‏، پس ‏P1‏ = ۰‏xce‏. اگر ‏d1‏ و ‏d3‏ از دست بروند، سطرهای ‏d0‏، ‏d2‏، ‏P0‏ و ‏P1‏ یک ماتریس ۴×۴ می‌سازند که وارون آن ۰‏x42‏ و ۰‏x44‏ را دوباره می‌دهد. هر ۱۵ حالت از دست رفتن دو ‏shard‏ در ۴+۲ قابل بازگشایی است.

۱۳-۹-۲ چرا ‏ISA‏ گاهی به ‏Cauchy‏ برمی‌گردد؟#

pseudocode
برای هر e از 1 تا m، هر زیرمجموعه‌ی L از e shard داده و P از e سطر parity:
    سطرها = (داده‌های سالم) ∪ P
    if det = 0 در GF(2^8): الگوی L قابل بازگشایی نیست
کد MDS است اگر هیچ الگویی شکست نخورد

نتیجه‌ی بررسی کامل ما. برای ۴+۲ و ۲۱+۴ هیچ الگوی شکستی نیست. برای ۲۲+۴ دو الگو وجود دارد، مثلاً از دست رفتن ‏d0‏، ‏‏d10‏، ‏‏d21‏ و ‏P2‏، که با وجود ‏m‏ = ۴ داده را برنمی‌گرداند. برای ۸+۵ شش الگو هست (مثلاً ‏d0‏، ‏‏d2‏، ‏‏d5‏، ‏‏P1‏ و ‏P2‏). برای ۴+۵ مشکلی پیدا نشد. پس قاعده‌ی کد، یعنی تغییر به ‏Cauchy‏ برای ‏m‏ > ۴ یا ‏m‏ = ۴ با ‏k‏ > ۲۱، دقیقاً همان مرز شکست در ‏m‏ = ۴ است و برای ‏m‏ > ۴ محافظه‌کارانه عمل می‌کند. پیام هشدار آن هنگام ساخت پروفایل («‏switching to Cauchy technique‏») را جدی بگیرید: ‏technique‏ واقعی ‏pool‏ با چیزی که نوشته‌اید فرق می‌کند.

۱۳-۹-۳ به‌روزرسانی دلتای ‏parity‏#

pseudocode
delta = old_d ⊕ new_d                       # encode_delta
for هر parity i: P_i ⊕= G[i][j] ⊗ delta      # apply_delta؛ برای m=1 فقط XOR
انتخاب در OSD (ec_pdw_write_mode = 0):
    conv = shardهایی که RMW معمولی باید بخواند ؛ pdw = shard تغییرکرده + parityها
    if |pdw| ≥ k: معمولی
    elif pdw بازسازی لازم دارد: معمولی ؛ elif فقط معمولی بازسازی لازم دارد: pdw
    else: pdw اگر |pdw| ≤ |conv|  (تساوی ← pdw)

مثال عددی. ‏d2‏ از ۰‏x43‏ به ۰‏x5a‏ تغییر می‌کند. ‏delta‏ = ۰‏x19‏ است، پس ‏P0‏ = ۰‏x04‏ ⊕ ۰‏x19‏ = ۰‏x1d‏ و ‏P1‏ = ۰‏xce‏ ⊕ (۴ ⊗ ۰‏x19‏ = ۰‏x64‏) = ۰‏xaa‏، که همان نتیجه‌ی کدگذاری دوباره‌ی کامل است. برای بازنویسی ۴‏K‏ یک ‏shard‏: در ۴+۲، ‏RMW‏ معمولی سه ‏shard‏ داده‌ی دیگر را می‌خواند و ‏PDW‏ شامل ‏d2‏ قدیمی و دو ‏parity‏ است، یعنی ۳ در برابر ۳. در تساوی ‏PDW‏ انتخاب می‌شود. در ۸+۳ مقایسه ۷ در برابر ۴ و به نفع ‏PDW‏ است. در ۲+۲ مقایسه ۱ در برابر ۳ است و مسیر معمولی برنده است. این مسیر فقط در ‏pool‏ با ‏FastEC‏ (allow_ec_optimizations، ‏Tentacle‏ به بعد) و افزونه‌ای که پرچم ‏paritydelta‏ دارد (‏ISA‏ و ‏Jerasure‏) فعال است.

۱۳-۹-۴ هزینه‌ی بازسازی یک ‏shard: RS‏، ‏‏LRC‏ و ‏CLAY‏#

pseudocode
RS:   read = k chunk
LRC:  read = l chunk (گروه محلی) ؛ سربار خام = (k + m + (k+m)/l) / k
CLAY: q = d − k + 1 ؛ هر یک از d کمک‌کننده 1/q از chunk را می‌فرستد ؛ read = d / q chunk
      شرط: k + 1 ≤ d ≤ k + m − 1 ؛ sub-chunkها = q^t

مثال عددی. در ۴+۲، بازسازی ‏RS‏ چهار ‏chunk‏ می‌خواند. ‏LRC‏ با ‏l‏ = ۳ سه ‏chunk‏ می‌خواند، اما سربار خامش ۲.۰ است، نه ۱.۵. ‏CLAY‏ با ‏d‏ = ۵ (‏q‏ = ۲، ‏t‏ = ۳ و ۸ ‏sub-chunk‏) فقط ۲.۵ ‏chunk‏ می‌خواند و سربار ۱.۵ را حفظ می‌کند. در ۸+۴، اعداد برای ‏RS‏، ‏‏LRC‏ (l = ۴، سربار ۱.۸۷۵) و ‏CLAY‏ (d = ۱۱، ‏q‏ = ۴، ۶۴ ‏sub-chunk‏) به ترتیب ۸، ۴ و ۲.۷۵ ‏chunk‏ است. هزینه‌ی ‏CLAY‏ در خواندن‌های تکه‌تکه است: هر کمک‌کننده ‏sub-chunk‏های پراکنده می‌فرستد، پس روی ‏HDD‏ تعداد ‏seek‏ها بیشتر می‌شود.

۱۳-۱۰ از درون کد: ‏EC‏ در ‏OSD‏#

۱۳-۱۰-۱ نقشه‌ی فایل‌ها#

۱۳-۱۰-۲ رابط افزونه#

هر افزونه کلاسی است که ‏ErasureCodeInterface‏ را پیاده می‌کند. توابع کلیدی (امضاها خلاصه شده‌اند):

• ‏init(profile, ss)‏: پارامترهای پروفایل را می‌خواند و ماتریس را می‌سازد.
• ‏get_chunk_count()‏ و ‏get_data_chunk_count()‏: ‏k+m‏ و ‏k‏.
• ‏minimum_to_decode(want_to_read, available, minimum)‏: کمترین مجموعه‌ی ‏shard‏ برای خواندن خواسته‌شده.
• ‏encode(want_to_encode, in, encoded)‏ و ‏decode(want_to_read, chunks, decoded)‏.
• ‏get_supported_optimizations()‏: پرچم‌هایی که ‏FastEC‏ بر اساس آن‌ها تصمیم می‌گیرد.

// from ceph/ceph, LGPL — src/erasure-code/ErasureCodeInterface.h (excerpt)
FLAG_EC_PLUGIN_PARTIAL_READ_OPTIMIZATION = 1<<0,
FLAG_EC_PLUGIN_PARTIAL_WRITE_OPTIMIZATION = 1<<1,
FLAG_EC_PLUGIN_ZERO_INPUT_ZERO_OUTPUT_OPTIMIZATION = 1<<2,
FLAG_EC_PLUGIN_ZERO_PADDING_OPTIMIZATION = 1<<3,
FLAG_EC_PLUGIN_PARITY_DELTA_OPTIMIZATION = 1<<4,

این پرچم‌ها توضیح می‌دهند چرا ‏FastEC‏ فقط با برخی افزونه‌ها کار می‌کند: هر بهینه‌سازی به ویژگی ریاضی خاصی نیاز دارد. مثلاً «‏zero in, zero out‏» یعنی ‏encode‏ بلوک تمام‌صفر، ‏parity‏ تمام‌صفر می‌دهد (برای کدهای خطی درست است) تا بتوان از نوشتن ‏padding‏ صفر صرف‌نظر کرد. ‏parity delta‏ به خطی بودن کد تکیه دارد: اگر داده‌ی ‏shard j‏ از ‏d‏ به ‏d'‏ تغییر کند، ‏parity‏ جدید برابر است با ‏parity‏ قدیم به‌علاوه‌ی ‏G[i][j]‏⊗(‏d‏ ⊕ ‏d'‏).

۱۳-۱۰-۳ ‏ECSwitch‏: گذار تدریجی#

کامنت ابتدای ‏ECSwitch.h‏ صریح است: این کلاس «سوییچر موقت» بین پیاده‌سازی ‏legacy‏ و ‏optimized‏ است تا وقتی پیاده‌سازی جدید به اندازه‌ی کافی مورد اعتماد شود. ‏ECSwitch‏ هر دو شیء ‏ECLegacy::ECBackendL legacy‏ و ‏ECBackend optimized‏ را دارد و بر اساس پرچم ‏pool‏ (‏allow_ec_optimizations‏) درخواست‌ها را به یکی هدایت می‌کند. به همین دلیل پرچم برگشت‌پذیر نیست: پس از نوشتن داده با قالب جدید، پیاده‌سازی قدیمی نمی‌تواند آن را بخواند.

۱۳-۱۰-۴ تصمیم ‏RMW‏ یا ‏parity delta‏#

در ‏ECTransaction.cc‏ برای هر نوشتن، طرح (‏plan‏) ساخته می‌شود. منطق انتخاب، ساده‌شده:

// from ceph/ceph, LGPL — src/osd/ECTransaction.cc (excerpt, simplified indentation)
if (sinfo.supports_parity_delta_writes() && !object_in_cache &&
    orig_size == projected_size && !reads.empty() && !op.truncate) {
  ...
  if (pdw_write_mode != 0) {
    do_parity_delta_write = (pdw_write_mode == 2);
  } else if (pdw_read_shards.size() >= sinfo.get_k()) {
    do_parity_delta_write = false;
  } else if (!shard_id_set::difference(pdw_read_shards, readable_shards).empty()) {
    do_parity_delta_write = false;
  } else if (!shard_id_set::difference(read_shards, readable_shards).empty()) {
    do_parity_delta_write = true;
  } else {
    do_parity_delta_write = pdw_read_shards.size() <= read_shards.size();
  }
}

خوانش: ‏parity delta‏ فقط وقتی معنا دارد که اندازه‌ی شیء تغییر نکند، ‏truncate‏ نباشد و داده در ‏cache‏ نباشد. اگر ‏parity delta‏ نیازمند ‏k‏ خواندن یا بیشتر باشد، مزیتی ندارد؛ اگر برای ‏parity delta‏ بازسازی لازم باشد، کنار گذاشته می‌شود؛ اگر برای ‏RMW‏ معمولی بازسازی لازم باشد ولی برای ‏parity delta‏ نه، ‏parity delta‏ انتخاب می‌شود؛ در غیر این صورت روشی که خواندن کمتری دارد (با ترجیح ‏parity delta‏ در تساوی). متغیر ‏pdw_write_mode‏ اجازه می‌دهد برای آزمایش یکی از دو روش را اجبار کرد.

۱۳-۱۰-۵ چرا ‏shard 0‏ همیشه ‏primary‏ نیست؟#

در ‏pool‏های بهینه، برخی ‏shard‏های داده در هر ‏I/O‏ به‌روز نمی‌شوند (نوشتن جزئی فقط ‏shard‏ تغییرکرده و ‏parity‏ها را لمس می‌کند). چنین ‏shard‏ی نمی‌تواند ‏primary‏ شود، چون ‏primary‏ باید ‏log‏ کامل ‏PG‏ را داشته باشد. اما منطق انتخاب ‏primary‏ در ‏OSDMap‏ را نمی‌توان تغییر داد بدون اینکه کلاینت‌ها ارتقا یابند. راه‌حل ‏OSDMap::pgtemp_primaryfirst()‏: ‏OSDMonitor‏ هنگام تنظیم ‏pg_temp‏ ترتیب را طوری عوض می‌کند که ‏shard‏های مجاز ‏primary‏ اول بیایند.

// from ceph/ceph, LGPL — src/osd/OSDMap.cc (comment excerpt)
 * Example: Optimized EC pool 4+2
 * acting_set = {NONE, 6, 7, 8, 9, 10}
 * non_primary_shards = {1, 2, 3} # data shards other than shard 0
 * pg_temp = {NONE, 9, 10, 6, 7, 8} # non-primary shards at end
 * primary will be OSD 9(1)

۱۳-۱۰-۶ شبه‌کد خواندن تخریب‌شده#

read(obj, off, len):
  want = shards_covering(off, len)                 # ECUtil: محدوده‌ی منطقی → shard extents
  avail = shards_up_and_not_missing(obj)
  if want ⊆ avail:                                  # خواندن جزئی (FastEC)
     return gather(want)
  need = ec_impl.minimum_to_decode(want, avail)     # k shard
  chunks = gather(need)
  return ec_impl.decode(want, chunks)[off:len]

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

• ‏Luminous‏: ‏allow_ec_overwrites‏ و پشتیبانی ‏RBD‏ و ‏CephFS‏ روی ‏EC‏.
• ‏Tentacle‏: ‏FastEC‏ با ‏allow_ec_optimizations‏؛ ‏ISA-L‏ پیش‌فرض کلاسترهای تازه؛ رفع اشکال‌های برنامه‌ریزی ‏truncate+write‏.
• ‏Squid‏: قانون ‏CRUSH‏ نوع ‏MSR‏ برای پیکربندی‌های انعطاف‌پذیرتر ‏EC‏.
• کد جاری: ‏osd_pool_default_flag_ec_optimizations=false‏ (‏FastEC‏ برای ‏pool‏های تازه خودکار روشن نیست).

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

1. ۱. پروفایل‌های ۲+۱، ۴+۲ و ۸+۳ را بسازید و با ‏ceph osd erasure-code-profile get‏ مقایسه کنید. کدام روی کلاستر شما قابل اجراست؟
2. ۲. یک ‏pool 4+2‏ بسازید، شیئی بنویسید و با ‏ceph osd map‏ ببینید هر ‏shard‏ روی کدام ‏OSD‏ است. یک ‏OSD‏ را متوقف کنید و شیء را بخوانید.
3. ۳. ‏pool EC‏ را به‌عنوان ‏data-pool‏ یک ‏image RBD‏ استفاده کنید و با ‏fio‏ نوشتن تصادفی ۴ کیلوبایتی را با ‏pool‏ تکثیری مقایسه کنید.
4. ۴. در کلاستر ‏Tentacle‏ آزمایشی، همان آزمایش را با ‏allow_ec_optimizations‏ و ‏stripe_unit=16K‏ تکرار کنید.
5. ۵. ‏pool 4+2‏ را روی کلاستری با پنج میزبان بسازید و ۲۱۴۷۴۸۳۶۴۷ را در ‏ceph pg dump‏ مشاهده کنید؛ سپس با ‏crushtool --test‏ تأیید کنید.
6. ۶. در کد، تابع ‏pgtemp_primaryfirst‏ را بخوانید و با مثال خودتان (۸+۳) خروجی را پیش‌بینی کنید.

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

1. ۱. سربار و تحمل خرابی ‏EC 8+3‏ در مقایسه با تکثیر سه‌تایی چیست؟
2. ۲. چرا هر زیرماتریس ‏k‏×‏k‏ ماتریس مولد باید وارون‌پذیر باشد؟
3. ۳. تفاوت ‏shard‏ در ‏EC‏ و نسخه در تکثیر چیست؟
4. ۴. چرا نوشتن کوچک در ‏EC‏ قدیمی پرهزینه بود؟
5. ۵. ‏parity delta‏ بر چه ویژگی ریاضی تکیه دارد؟
6. ۶. محدودیت‌های فعال‌سازی ‏FastEC‏ کدام‌اند؟
7. ۷. چرا پرچم ‏allow_ec_optimizations‏ برگشت‌پذیر نیست؟
8. ۸. ‏CLAY‏ و ‏LRC‏ چطور ترافیک بازیابی را کاهش می‌دهند؟
9. ۹. عدد ۲۱۴۷۴۸۳۶۴۷ در نگاشت ‏PG‏ چه معنایی دارد و علت‌های رایج آن کدام‌اند؟
10. ۱۰. چرا در ‏pool‏ بهینه، ‏primary‏ همیشه ‏shard 0‏ نیست؟

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

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

• ‏Erasure code‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code/
• ‏Erasure code profiles‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-profile/
• ‏ISA plugin‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-isa/
• ‏LRC plugin‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-lrc/
• ‏CLAY plugin‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-clay/
• ‏SHEC plugin‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-shec/
• ‏Tentacle release notes‏
  https://docs.ceph.com/en/latest/releases/tentacle/
• ‏Source: src/erasure-code‏
  https://github.com/ceph/ceph/tree/main/src/erasure-code
• ‏Source: src/osd/ECTransaction.cc, ECSwitch.h, OSDMap.cc‏
  https://github.com/ceph/ceph/tree/main/src/osd
• ‏Intel ISA-L‏
  https://github.com/intel/isa-l
• ‏Plank, "A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems"‏
  https://web.eecs.utk.edu/~jplank/plank/papers/CS-96-332.pdf