لایه‌های پایینی (۵): ریاضیات ‏erasure coding‏، از ‏GF‏(۲⁸) تا ‏FastEC‏

۲۷-۱ مقدمه: از ‏XOR‏ تا ‏Reed-Solomon‏#

در فصل ۱۳ دیدیم یک ‏pool‏ با ‏erasure coding‏ چگونه ساخته می‌شود و پروفایل‌ها چه معنایی دارند. این فصل یک لایه پایین‌تر می‌رود: ریاضیات میدان متناهی ‏$\mathrm{GF}(2^8)$‏، ساخت ماتریس تولید ‏Reed-Solomon‏ (به روش ‏Vandermonde‏ و ‏Cauchy‏)، پیاده‌سازی ‏SIMD‏ در ‏ISA-L‏، و این‌که ‏Ceph‏ چگونه شیء را به ‏stripe‏ و ‏chunk‏ تقسیم می‌کند، نوشتن جزئی را با ‏read-modify-write‏ انجام می‌دهد و در ‏Tentacle‏ با ‏EC‏ بهینه‌شده (که معمولاً ‏FastEC‏ نامیده می‌شود) چه چیزی تغییر کرده است. یک مثال عددی کامل ‏encode‏ و ‏decode‏ هم با دست حل می‌کنیم.

۲۷-۲ ‏GF‏(۲⁸): حساب بایت‌ها#

‏erasure coding‏ باید روی بایت‌ها «ضرب و تقسیم» کند، به‌طوری که هر عدد غیرصفر معکوس داشته باشد و نتیجه همیشه یک بایت بماند. میدان گالوا ‏$\mathrm{GF}(2^8)$‏ دقیقاً همین را فراهم می‌کند. عناصر آن ۲۵۶ بایت‌اند که به‌صورت چندجمله‌ای‌هایی از درجه‌ی کمتر از ۸ با ضرایب ۰ و ۱ دیده می‌شوند.

• جمع و تفریق: هر دو ‏XOR‏ هستند، پس ‏a‏ + ‏a‏ = ۰.
• ضرب: ضرب چندجمله‌ای‌ها و سپس باقیمانده بر یک چندجمله‌ای تحویل‌ناپذیر درجه ۸ گرفته می‌شود. ‏ISA-L‏ از ۰‏x11D‏ (x⁸ + ‏x‏⁴ + ‏x‏³ + ‏x‏² + ۱) استفاده می‌کند: در هر شیفت به چپ، اگر بیت ۸ روشن شد، با ۰‏x1D XOR‏ می‌شود (در ‏ec_base.c‏ همین الگو برای ضرب در ۲ دیده می‌شود).
• جدول ‏log/exp‏: چون عدد ۲ مولد گروه ضربی است، هر بایت غیرصفر برابر ‏$2^i$‏ است. پس ‏$a \cdot b = \exp[(\log a + \log b) \bmod 255]$‏ و ‏$a^{-1} = \exp[255 - \log a]$‏.

۲۷-۳ ‏Reed-Solomon‏ سیستماتیک#

در یک کد سیستماتیک (‏k‏، ‏m‏)، ‏k chunk‏ داده بدون تغییر ذخیره و ‏m chunk parity‏ از آن‌ها محاسبه می‌شود. اگر ‏D‏ بردار داده باشد، ‏chunk‏ها از ضرب ماتریس تولید ‏G‏ با اندازه‌ی (‏k+m‏)×‏k‏ در ‏D‏ به دست می‌آیند: ‏C‏ = ‏G‏ · ‏D‏. چهار سطر اول ‏G‏ همانی‌اند. کد ‏MDS‏ است، یعنی هر ‏k chunk‏ از ‏k+m chunk‏ برای بازسازی کافی است، به شرط این‌که هر زیرماتریس ‏k‏×‏k‏ از ‏G‏ معکوس‌پذیر باشد.

‏gf_gen_rs_matrix‏ در ‏ISA-L‏ سطر ‏i‏ ام ‏parity‏ را با توان‌های ‏$\mathit{gen} = 2^{i-k}$‏ می‌سازد. این یک ماتریس «‏Vandermonde‏» ساده است که برای همه‌ی (‏k‏، ‏m‏)ها ‏MDS‏ نیست. به همین دلیل ‏ErasureCodeIsa.cc‏ اگر ‏m‏ > ۴ باشد یا ‏m‏ = ۴ و ‏k‏ > ۲۱، با پیامی در لاگ به ‏gf_gen_cauchy1_matrix‏ تغییر می‌دهد که درایه‌هایش ۱/(‏i‏ ⊕ ‏j‏) هستند و همیشه ‏MDS‏‌اند. سقف ‏k‏ هم ‏MAX_K = 32‏ است.

۲۷-۳-۱ مثال کامل: ‏encode‏ یک ‏stripe‏ کوچک#

فرض کنید هر ‏chunk‏ فقط یک بایت دارد و داده ‏D‏ = (۰‏x12, 0x34, 0x56, 0x78‏) است (در واقع همین محاسبه برای هر بایت از ‏chunk‏های ۴‏K‏ تکرار می‌شود):

P0 = 1·12 ⊕ 1·34 ⊕ 1·56 ⊕ 1·78 = 12 ⊕ 34 ⊕ 56 ⊕ 78           = 0x08
P1 = 1·12 ⊕ 2·34 ⊕ 4·56 ⊕ 8·78 = 12 ⊕ 68 ⊕ 45 ⊕ E7           = 0xD8
chunks = [12, 34, 56, 78 | 08, D8]   (shard 0..5)

۲۷-۳-۲ ‏decode‏: از دست رفتن دو ‏shard‏#

فرض کنید ‏OSD‏های حاوی ‏D1‏ و ‏D3‏ از دست رفته‌اند و ‏shard‏های سالم {‏D0‏، ‏D2‏، ‏P0‏، ‏P1}‏ هستند. سطرهای متناظر از ‏G‏ یک ماتریس ۴×۴ می‌سازند. معکوس آن در ‏$\mathrm{GF}(2^8)$‏ حساب می‌شود (‏ISA-L‏ از ‏gf_invert_matrix‏ استفاده می‌کند) و سطرهای مربوط به داده‌های گم‌شده با بایت‌های سالم ضرب می‌شوند:

D1 = 7B·D0 ⊕ F5·D2 ⊕ A6·P0 ⊕ DD·P1 = 0x34   ✓
D3 = 7A·D0 ⊕ F4·D2 ⊕ A7·P0 ⊕ DD·P1 = 0x78   ✓

همه‌ی اعداد این دو بخش با یک پیاده‌سازی پایتونی مستقل از ‏$\mathrm{GF}(2^8)$‏ با ۰‏x11D‏ و همان الگوریتم ساخت ماتریس ‏ISA-L‏ محاسبه و بررسی شده‌اند. ضرایب ‏decode‏ فقط یک بار برای هر الگوی خرابی حساب می‌شوند و پلاگین ‏isa‏ آن‌ها را در ‏ErasureCodeIsaTableCache‏ نگه می‌دارد، چون معکوس کردن ماتریس از ‏encode‏ گران‌تر است.

۲۷-۴ ‏stripe‏، ‏chunk‏ و چیدمان روی ‏OSD‏#

۲۷-۵ ‏read-modify-write‏ در ‏EC‏ قدیمی#

تا ‏Squid‏، و در ‏pool‏های بدون بهینه‌سازی در نسخه‌های بعدی، ‏backend‏ مربوط به ‏EC‏ برای هر نوشتنی که کل ‏stripe‏ را نپوشاند و روی داده‌ی موجود باشد (‏allow_ec_overwrites=true‏، لازم برای ‏RBD‏ و ‏CephFS‏) این کارها را انجام می‌دهد:

pseudocode: overwrite جزئی در ECBackend قدیمی (خلاصه‌ی این کتاب)
  extent = round_out(write, stripe_width)              # گسترش به مرز stripe
  if cache miss: read k chunks of extent from shards   # چند رفت‌وبرگشت شبکه
  merge new bytes into stripe buffer
  encode → m parity chunks for whole stripe
  send sub-writes to all k+m shards (هر shard، تراکنش خودش)
  wait all commits → reply

چرا ‏parity delta‏ درست است؟ چون کد خطی است: ‏$P_i = \sum_j g_{ij} \cdot D_j$‏. اگر فقط ‏$D_j$‏ به ‏$D_j'$‏ تغییر کند، ‏$P_i' = P_i \oplus g_{ij} \cdot (D_j \oplus D_j')$‏. با مثال بخش قبل، اگر ‏D1‏ از ۰‏x34‏ به ۰‏x35‏ تغییر کند، ‏delta‏ برابر ۰‏x01‏ است، پس ‏P0‏′ = ۰‏x08‏ ⊕ ۱·۰‏x01‏ = ۰‏x09‏ و ‏P1‏′ = ۰‏xD8‏ ⊕ ۲·۰‏x01‏ = ۰‏xDA‏. نیازی به خواندن ‏D0‏، ‏D2‏ و ‏D3‏ نیست.

# Tentacle و بالاتر:
ceph osd erasure-code-profile set ec42 plugin=isa technique=reed_sol_van k=4 m=2 crush-failure-domain=host
ceph osd pool create ecdata erasure ec42
ceph osd pool set ecdata allow_ec_overwrites true
ceph osd pool set ecdata allow_ec_optimizations true     # برگشت‌ناپذیر
ceph osd pool get ecdata all | grep -E 'ec_optim|stripe'

۲۷-۶ کدهای با پهنای باند ترمیم کمتر#

در ‏RS‏، بازسازی یک ‏shard‏ گم‌شده به خواندن ‏k chunk‏ کامل نیاز دارد. برای ‏k=8‏، این یعنی ۸ برابر داده‌ی از دست رفته از شبکه می‌گذرد. سه پلاگین ‏Ceph‏ این هزینه را به روش‌های متفاوت کم می‌کنند:

مثال عددی ‏CLAY‏: پهنای باند ترمیم برای یک ‏shard‏ به اندازه‌ی ‏S‏ برابر ‏$d \cdot S / (d - k + 1)$‏ است. با ‏k=8‏، ‏m=4‏ و ‏d=11‏، این مقدار ۱۱‏S/4‏ = ۲.۷۵‏S‏ است، در حالی که ‏RS‏ معادل ۸‏S‏ می‌خواند (حدود ۶۶٪ صرفه‌جویی). ولی ‏q‏ = ‏d‏ − ‏k‏ + ۱ = ۴ و ‏t‏ = (‏k+m‏)/‏q‏ = ۳، پس هر ‏chunk‏ به ‏$4^3 = 64$‏ ‏sub-chunk‏ تقسیم می‌شود. با ‏stripe_unit‏ برابر ۴‏K‏، ‏sub-chunk‏ها ۶۴ بایتی می‌شوند و خواندن ترمیمی به ده‌ها خواندن کوچک و پراکنده تبدیل می‌شود. برای همین ‏CLAY‏ با ‏stripe_unit‏ بزرگ‌تر معنا پیدا می‌کند.

۲۷-۷ ‏crc‏ و یکپارچگی در ‏EC‏#

در ‏EC‏ قدیمی، برای ‏pool‏های ‏append-only‏ (بدون ‏overwrite‏)، ‏hash‏ هر ‏shard‏ (‏hinfo_key‏ در ‏xattr‏) نگه داشته می‌شد و ‏scrub‏ عمیق آن را بررسی می‌کرد. با ‏allow_ec_overwrites‏، این ‏hash‏ دیگر به‌روز نمی‌شود و یکپارچگی بر ‏checksum‏های ‏BlueStore‏ در هر ‏shard‏ (فصل ۲۳) تکیه دارد. ‏scrub‏ عمیق در ‏EC‏ هر ‏shard‏ را می‌خواند و سازگاری ‏parity‏ را با ‏encode‏ دوباره بررسی می‌کند. پرچم ‏FLAG_EC_PLUGIN_CRC_ENCODE_DECODE_SUPPORT‏ در ‏main‏ نشان می‌دهد پلاگین می‌تواند ‏crc‏ را از روی ‏crc‏ داده‌ها محاسبه کند، یعنی خاصیت خطی بودن ‏crc‏ را با کد ترکیب کند. این بخشی از کارهای در جریان روی ‏scrub‏ سریع‌تر است. پیش از تکیه بر آن، نسخه‌ی خود را بررسی کنید.

ceph osd erasure-code-profile get default
ceph osd pool ls detail | grep -E 'erasure|stripe_width'
ceph pg <pgid> query | jq '.info.stats.stat_sum.num_objects_degraded'
ceph tell osd.4 config get osd_recovery_max_active_hdd

۲۷-۸ حساب ‏GF‏(۲⁸) در سطح دستور: جدول‌های ‏log/exp‏ و ترفند نیم‌بایت#

بخش‌های پیشین ضرب در ‏$\mathrm{GF}(2^8)$‏ را تعریف کردند. این بخش نشان می‌دهد ‏ISA-L‏، که پلاگین ‏isa‏ در ‏Ceph‏ بر آن تکیه دارد، این ضرب را در حلقه‌ی داغ چگونه انجام می‌دهد. چندجمله‌ی کاهش در ‏ISA-L‏ همان ۰‏x11D‏ (یعنی ‏$x^8+x^4+x^3+x^2+1$‏) است. در کد این عدد به شکل ‏0x1d‏ دیده می‌شود: هر بار که بیت ۷ پیش از شیفت روشن باشد، حاصل با ۰‏x1d XOR‏ می‌شود.

pseudocode
# ساخت یک‌باره: exp[i] = 2^i و log[2^i] = i برای i در 0..254
x = 1
for i in 0..254: exp[i] = x; log[x] = i; x = x·2 (یعنی x≪1 و اگر سرریز شد ⊕ 0x11D)
gf_mul(a, b): if a == 0 or b == 0: return 0
              i = log[a] + log[b]; if i > 254: i −= 255
              return exp[i]
gf_inv(a):   return exp[255 − log[a]]

مثال عددی. ‏exp[0..15]‏ = ۰۱ ۰۲ ۰۴ ۰۸ ۱۰ ۲۰ ۴۰ ۸۰ ۱‏D 3A 74 E8 CD 87 13 26‏. پس ‏$2^8 = \mathtt{0x1D}$‏ است، یعنی همان سرریز اول. برای ۰‏x53‏ × ۰‏xCA‏ داریم ‏log[0x53]‏ = ۲۰۶ و ‏log[0xCA]‏ = ۷۳. جمع آن‌ها ۲۷۹ است و چون از ۲۵۴ بزرگ‌تر است، ۲۷۹ − ۲۵۵ = ۲۴ و ‏exp[24]‏ = ۰‏x8F‏. وارون ۰‏x02‏ برابر ‏exp[255‏ − ۱] = ۰‏x8E‏ است. آزمون: ۰‏x8E‏ × ۲ = ۰‏x11C‏ و ۰‏x11C‏ ⊕ ۰‏x11D‏ = ۰‏x01‏.

این روش برای هر بایت دو دسترسی تصادفی به جدول و یک شاخه دارد و در حلقه‌ی داغ کند است. برای همین ‏ISA-L‏ جدول دیگری می‌سازد که با دستورهای ‏SIMD‏ سازگار است.

دلیل درستی ترفند این است که هر بایت ‏d‏ برابر (‏d AND 0xF0‏) ⊕ (‏d AND 0x0F‏) است و ضرب در ‏c‏ روی ⊕ پخش می‌شود. پس به جای جدول ۲۵۶ خانه‌ای برای هر ‏c‏، دو جدول ۱۶ خانه‌ای کافی است. ۱۶ خانه دقیقاً اندازه‌ی یک ثبات ‏XMM‏ است و دستور ‏PSHUFB‏ با همین اندازه کار می‌کند: هر بایت از ثبات دوم را شاخصی در ثبات اول می‌گیرد.

pseudocode
init(c): for n in 0..15: tbl[n] = c·n ; tbl[16+n] = c·(n≪4)
encode_row(row r, data D0..Dk-1, length L):
    for off in 0, W, 2W, … < L:                 # W = 32 در AVX2
        acc = 0
        for j in 0..k-1:
            v  = load(Dj + off)
            lo = v AND 0x0F ; hi = (v ≫ 4) AND 0x0F
            acc ^= PSHUFB(tbl[r][j].lo, lo) ^ PSHUFB(tbl[r][j].hi, hi)
        store(P_r + off, acc)

مثال عددی. برای ‏d‏ = ۰‏xB7‏ و ‏c‏ = ۲: نیم‌بایت پایین ۷ به ‏tbl[7]‏ = ۰‏x0E‏ می‌رسد و نیم‌بایت بالا ‏B‏ به ‏tbl[27]‏ = ۰‏x7D. 0x0E‏ ⊕ ۰‏x7D‏ = ۰‏x73‏، که با ۲·۰‏xB7‏ مستقیم (۰‏x16E‏ ⊕ ۰‏x11D‏ = ۰‏x73‏) یکی است. برای ‏k=4‏، ‏m=2‏، یعنی شش ضریب، ‏ec_init_tables 6‏ × ۳۲ = ۱۹۲ بایت جدول می‌سازد. ‏Ceph‏ در ‏ErasureCodeIsaDefault::prepare‏ آرایه‌ای به اندازه‌ی ‏k‏·(‏m+k‏)·۳۲ بایت می‌گیرد و جدول‌ها را در ‏ErasureCodeIsaTableCache‏ نگه می‌دارد تا برای هر (‏k, m‏) فقط یک‌بار ساخته شوند. جدول‌های ‏decode‏ هم در یک ‏LRU‏ به طول ‏decoding_tables_lru_length‏ نگه داشته می‌شوند، چون برای هر الگوی خرابی ماتریس متفاوتی لازم است.

۲۷-۹ ماتریس‌های تولید: ‏Vandermonde‏ در برابر ‏Cauchy‏#

پلاگین ‏isa‏ دو ماتریس می‌شناسد: ‏technique=reed_sol_van‏ (پیش‌فرض) که ‏gf_gen_rs_matrix‏ را صدا می‌زند و ‏technique=cauchy‏ که ‏gf_gen_cauchy1_matrix‏ را. هر دو ماتریس (‏k+m‏)×‏k‏ با یک ماتریس همانی ‏k‏×‏k‏ در بالا می‌سازند، پس کد سیستماتیک است.

pseudocode
gf_gen_rs_matrix(a, rows=k+m, k):
    a = 0 ; for i < k: a[i][i] = 1
    gen = 1
    for i in k .. rows-1:
        p = 1
        for j < k: a[i][j] = p ; p = p·gen      # سطر i: توان‌های gen
        gen = gen·2
gf_gen_cauchy1_matrix(a, rows, k):
    همانی در بالا ; for i in k..rows-1, j < k: a[i][j] = gf_inv(i ⊕ j)

مثال عددی (‏k=4‏، ‏m=2‏). ‏Vandermonde‏: سطر ‏P‏ برابر [۱ ۱ ۱ ۱] است (‏gen‏ = ۱) و سطر ‏Q‏ برابر [۱ ۲ ۴ ۸] (‏gen‏ = ۲). پس ‏P‏ همان ‏XOR‏ ساده است. ‏Cauchy‏: سطر ۴ برابر [‏inv(4) inv(5) inv(6) inv‏(۷)] = [۴۷ ‏A7 7A BA]‏ و سطر ۵ برابر [‏inv(5) inv(4) inv(7) inv‏(۶)] = [‏A7 47 BA 7A]‏. برای داده‌ی ‏D‏ = [۳۷ ۵‏C A1 0F]‏، با ‏Vandermonde P‏ = ۰‏xC5‏ و ‏Q‏ = ۰‏x49‏، و با ‏Cauchy P‏ = ۰‏xD1‏ و ‏Q‏ = ۰‏x09‏.

چرا ‏Ceph‏ محدودیت می‌گذارد. ماتریس ‏gf_gen_rs_matrix‏ یک ‏Vandermonde‏ «واقعی» نیست: سطرهای همانی روی آن گذاشته شده‌اند و ‏MDS‏ بودنش برای همه‌ی (‏k, m‏) تضمین نمی‌شود. خود ‏ISA-L‏ ابزار ‏gen_rs_matrix_limits.c‏ را برای یافتن حدها دارد. ‏Ceph‏ در ‏ErasureCodeIsaDefault::parse‏ این حدها را اعمال می‌کند: ‏k‏ ≤ ۳۲ و ‏m‏ ≤ ۳۲ (‏MAX_K‏ و ‏MAX_M‏). برای ‏Vandermonde‏ اگر ‏m‏ > ۴ باشد، یا ‏m‏ = ۴ و ‏k‏ > ۲۱، پیام هشدار می‌دهد و ‏technique‏ را خودکار به ‏cauchy‏ تغییر می‌دهد. یعنی پروفایل ذخیره‌شده عوض می‌شود. با شبیه‌سازی جداگانه (حذف همه‌ی ترکیب‌های ‏m‏ سطری و آزمون وارون‌پذیری ‏k‏×‏k‏ باقی‌مانده) برای ۴+۲، ۶+۳، ۸+۳، ۸+۴، ۱۰+۴ و ۱۲+۴ هیچ زیرماتریس منفردی پیدا نشد (مثلاً ۱۰۰۱ ترکیب برای ۱۰+۴)، که با این حدها سازگار است.

۲۷-۱۰ ‏decode‏ با وارون ماتریس: یک مثال کامل بایت‌به‌بایت#

pseudocode
B = سطرهای ماتریس تولید برای k shard سالم انتخاب‌شده
Binv = gf_invert_matrix(B)            # گاوس-جردن: محور، ضرب سطر در gf_inv، حذف با ⊕
for each lost data shard i: c_i = سطر i از Binv
for each lost parity shard p: c_p = (سطر p از ماتریس تولید) × Binv
ec_init_tables(k, e, c, decode_tbls) ; ec_encode_data(L, k, e, decode_tbls, survivors, outputs)

مثال عددی. داده‌ی [۳۷ ۵‏C A1 0F]‏ و ‏parity‏های ‏Vandermonde P‏ = ‏C5‏ و ‏Q‏ = ۴۹ را داریم. ‏D1‏ و ‏D3‏ گم شده‌اند و ‏D0‏، ‏D2‏، ‏P‏ و ‏Q‏ باقی مانده‌اند. ابتدا سهم داده‌های معلوم را کم می‌کنیم:

• ‏P'‏ = ‏P‏ ⊕ ‏D0‏ ⊕ ‏D2‏ = ‏C5‏ ⊕ ۳۷ ⊕ ‏A1‏ = ۰‏x53‏، که برابر ‏D1‏ ⊕ ‏D3‏ است.
• ‏Q'‏ = ‏Q‏ ⊕ ‏D0‏ ⊕ ۴·‏D2‏ = ۴۹ ⊕ ۳۷ ⊕ ‏BE‏ = ۰‏xC0‏، که برابر ۲·‏D1‏ ⊕ ۸·‏D3‏ است.

با حذف ‏D1: Q'‏ ⊕ ۲·‏P'‏ = (۸ ⊕ ۲)·‏D3‏ = ۰‏x0A‏·‏D3‏. داریم ۲·‏P'‏ = ۰‏xA6‏ و ‏Q'‏ ⊕ ۰‏xA6‏ = ۰‏x66‏. پس ‏D3‏ = ۰‏x66‏ · ‏inv‏(۰x۰A) = ۰‏x66‏ · ۰‏xDD‏ = ۰‏x0F‏ و ‏D1‏ = ‏P'‏ ⊕ ‏D3‏ = ۰‏x5C‏. ماتریس وارونی که ‏gf_invert_matrix‏ برای سطرهای {۰, ۲, ‏P, Q}‏ می‌سازد، برای ‏D3‏ سطر [۷‏A F4 A7 DD]‏ و برای ‏D1‏ سطر [۷‏B F5 A6 DD]‏ دارد. ضرب آن‌ها در [۳۷ ‏A1 C5 49]‏ همین دو عدد را می‌دهد.

۲۷-۱۱ به‌روزرسانی ‏parity‏ با دلتا (‏Tentacle‏)#

در ‏EC‏ قدیمی، نوشتن جزئی کل ‏stripe‏ را می‌خواند (بخش ‏read-modify-write‏). مسیر ‏EC‏ بهینه در ‏Tentacle‏، برای پلاگین‌هایی که پرچم ‏FLAG_EC_PLUGIN_PARITY_DELTA_OPTIMIZATION‏ را اعلام می‌کنند، از خطی بودن کد استفاده می‌کند. تغییر یک ‏shard‏ داده فقط ‏parity‏ها را به اندازه‌ی ضریبِ همان ستون ضرب در دلتا تغییر می‌دهد.

pseudocode
encode_delta(old, new):  Δ = old ⊕ new                    # isa_xor با دو بردار
apply_delta(in = {i: Δ_i, p: P_p}, out):
    for each data shard i با دلتا:
        for each parity p:
            if m == 1:  P_p ^= Δ_i                          # ستون همه 1
            else: ec_encode_data_update(L, k, 1, i, tbls + 32·k·(p−k), Δ_i, &P_p)
                  # P_p ^= a[p][i]·Δ_i

مثال عددی. ‏D1‏ از ۰‏x5C‏ به ۰‏xA5‏ تغییر می‌کند، پس Δ = ۰‏x5C‏ ⊕ ۰‏xA5‏ = ۰‏xF9‏. در ‏Vandermonde‏ ضرایب ستون ۱ برای ‏P‏ و ‏Q‏ برابر ۱ و ۲ هستند: ‏P_new‏ = ‏C5‏ ⊕ ‏F9‏ = ۰‏x3C‏ و ‏Q_new‏ = ۴۹ ⊕ ۲·‏F9‏ = ۴۹ ⊕ ‏EF‏ = ۰‏xA6‏. محاسبه‌ی کامل از صفر با داده‌ی جدید هم دقیقاً ۳‏C‏ و ‏A6‏ می‌دهد. در ‏Cauchy‏ ضرایب ستون ۱ برابر ‏A7‏ و ۴۷ هستند و نتیجه ۰‏x17‏ و ۰‏x70‏ می‌شود، که آن هم با محاسبه‌ی کامل یکی است. برای نوشتن ۴‏K‏ در ۸+۳، مسیر قدیمی ۸ خواندن ۴‏K‏ (یا کل ‏stripe‏) لازم داشت، اما مسیر دلتا ۱ + ۳ = ۴ خواندن و ۴ نوشتن دارد.

۲۷-۱۲ ‏LRC‏: از ‏k‏، ‏m‏ و ‏l‏ تا رشته‌ی لایه‌ها#

pseudocode
require (k+m) % l == 0 ; g = (k+m)/l ; require k % g == 0 and m % g == 0
mapping = repeat g: 'D'×(k/g) + '_'×(m/g) + '_'
global  = repeat g: 'D'×(k/g) + 'c'×(m/g) + '_'
local_i = for j < g: (i==j) ? 'D'×l + 'c' : '_'×(l+1)
if crush-locality: steps = [choose g type locality, chooseleaf (l+1) type failure-domain]

مثال عددی. با ‏k=4‏، ‏m=2‏ و ‏l=3: g‏ = ۶/۳ = ۲ و هر گروه ۲ داده، ۱ ‏parity‏ سراسری و ۱ ‏parity‏ محلی دارد. کل ‏chunk‏ها ۴ + ۲ + ۲ = ۸ است. نتیجه: ‏mapping‏ = ‏DD__DD__‏، لایه‌ی سراسری ‏DDc_DDc_‏ و لایه‌های محلی ‏DDDc____‏ و ‏____DDDc‏. سربار فضا ۸/۴ = ۲ برابر است (در برابر ۱.۵ برای ۴+۲ ساده). در مقابل، ترمیم یک ‏chunk‏ به جای ۴ خواندن فقط ۳ خواندن از همان گروه لازم دارد.

۲۷-۱۳ ‏Clay‏: کدام ‏sub-chunk‏ها برای ترمیم خوانده می‌شوند#

pseudocode
q = d − k + 1 ; nu = (k+m) % q ? q − (k+m) % q : 0
t = (k+m+nu)/q ; sub_chunk_no = q^t
get_repair_subchunks(lost):
    y = lost / q ; x = lost % q
    seq = q^(t−1−y) ; num = q^y ; idx = x·seq
    repeat num times: emit [idx, idx+seq) ; idx += q·seq

مثال عددی. ‏k=4‏، ‏m=2‏، ‏d=5‏ ⇒ ‏q‏ = ۲، ‏nu‏ = ۰، ‏t‏ = ۳ و ‏sub_chunk_no‏ = ۸. برای گره ۰ (‏x=0‏، ‏y=0‏): ‏seq‏ = ۴ و ‏num‏ = ۱، پس ‏sub-chunk‏های ۰ تا ۳. برای گره ۲ (‏x=0‏، ‏y=1‏): ‏seq‏ = ۲ و ‏num‏ = ۲، پس {۰، ۱، ۴، ۵}. برای گره ۵ (‏x=1‏، ‏y=2‏): ‏seq‏ = ۱ و ‏num‏ = ۴، پس {۱، ۳، ۵، ۷}. هر یک از ۵ ‏helper‏ نصف ‏chunk‏ خود را می‌فرستد، یعنی ۲.۵ ‏chunk‏ در برابر ۴ ‏chunk‏ در ‏RS‏. یک ‏chunk‏ چهار مگابایتی با ۲.۵ × ۴ = ۱۰ ‏MiB‏ به جای ۱۶ ‏MiB‏ ترمیم می‌شود.

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

• پیش‌فرض پلاگین: در ‏Squid‏ ‏plugin=jerasure‏، و در ‏Tentacle‏ و ‏main‏ ‏plugin=isa‏ (هر دو با ‏technique=reed_sol_van k=2 m=2‏). این تغییر را در کد ‏global.yaml.in‏ هر دو شاخه بررسی کرده‌ایم.
• ‏EC‏ بهینه: کد ‏main‏ کلاس ‏ECSwitch‏ را دارد که به‌عنوان «سوئیچ موقت» میان ‏backend‏ قدیمی (‏ECBackendL‏) و جدید (‏ECBackend‏) توصیف شده است. طبق توضیح خود کد، پس از اطمینان کامل، ‏backend‏ قدیمی حذف خواهد شد.
• ‏EC‏ و ‏stretch cluster‏: کارهای پشتیبانی ‏EC‏ در ‏stretch mode‏ در شاخه‌ی ‏main‏ ادامه دارد. پیش از استفاده، یادداشت‌های انتشار نسخه‌ی هدف را بخوانید.

۲۷-۱۵ تمرین عملی#

1. ۱. ضرب ‏$\mathrm{GF}(2^8)$‏ با ۰‏x11D‏ را در پایتون پیاده کنید و جدول ضرب‌های این فصل را بازتولید کنید. سپس ‏decode‏ با دو خرابی را برای الگوی دیگری (مثلاً ‏D0‏ و ‏P1‏) حل کنید.
2. ۲. با ‏ceph_erasure_code_benchmark‏ (در بسته‌ی تست‌ها) سرعت ‏encode‏ پلاگین‌های ‏isa‏ و ‏jerasure‏ را برای ‏k=8‏ و ‏m=3‏ روی سرور خود مقایسه کنید.
3. ۳. روی یک ‏pool‏ آزمایشی ‏EC‏ با و بدون ‏allow_ec_optimizations‏، ‏fio‏ با نوشتن تصادفی ۴‏K‏ اجرا و ‏IOPS‏ و تأخیر را مقایسه کنید.
4. ۴. پهنای باند ترمیم ‏CLAY‏ را برای (‏k=6‏، ‏m=3‏، ‏d=8‏) محاسبه و با ‏RS‏ مقایسه کنید.

۲۷-۱۶ پرسش‌های مرور#

1. ۱. چرا جمع و تفریق در ‏$\mathrm{GF}(2^8)$‏ هر دو ‏XOR‏ هستند؟
2. ۲. ۰‏x56‏ × ۰‏x04‏ در ‏$\mathrm{GF}(2^8)$‏ با ۰‏x11D‏ چگونه محاسبه می‌شود؟
3. ۳. کد ‏MDS‏ چیست و چرا ‏Vandermonde‏ ساده‌ی ‏ISA-L‏ همیشه ‏MDS‏ نیست؟
4. ۴. ‏Ceph‏ در چه شرایطی خودکار به ‏cauchy‏ تغییر می‌دهد؟
5. ۵. در مثال این فصل، ‏P0‏ و ‏P1‏ چگونه به دست آمدند؟
6. ۶. چرا ضرایب ‏decode‏ کش می‌شوند؟
7. ۷. ‏PSHUFB‏ چگونه ضرب در ثابت را سریع می‌کند؟
8. ۸. ‏parity delta‏ چیست و چرا درست است؟
9. ۹. ‏stripe_unit‏ پیش‌فرض در ‏pool‏ بهینه چقدر است و چرا؟
10. ۱۰. پهنای باند ترمیم ‏CLAY‏ با ‏k=8‏، ‏m=4‏ و ‏d=11‏ چقدر است و هزینه‌ی آن چیست؟

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

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

• مستندات ‏erasure code‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code/
• پروفایل‌ها
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-profile/
• پلاگین ‏CLAY‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-clay/
• پلاگین ‏LRC‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-lrc/
• پلاگین ‏SHEC‏
  https://docs.ceph.com/en/latest/rados/operations/erasure-code-shec/
• ‏ErasureCodeIsa.cc‏
  https://github.com/ceph/ceph/blob/main/src/erasure-code/isa/ErasureCodeIsa.cc
• ‏ISA-L ec_base.c‏
  https://github.com/intel/isa-l/blob/master/erasure_code/ec_base.c
• مقاله‌ی ‏Clay codes‏ (FAST ۲۰۱۸
  https://www.usenix.org/conference/fast18/presentation/vajha
• آموزش ‏Reed-Solomon‏ (Plank
  https://web.eecs.utk.edu/~jplank/plank/papers/CS-96-332.html