لایه‌های پایینی (۲): قالب روی‌دیسک ‏BlueStore‏ و ‏BlueFS‏

۲۴-۱ مقدمه: ‏BlueStore‏ روی دیسک چه می‌نویسد؟#

در فصل ۲۳ دیدیم بایت‌ها چگونه از ‏bufferlist‏ به ‏io_submit‏ می‌رسند. این فصل نشان می‌دهد آن بایت‌ها روی دیسک کجا و با چه قالبی قرار می‌گیرند: از نخستین ۴ کیلوبایت دستگاه (‏label‏) تا ‏superblock‏ و لاگ ‏BlueFS‏، و از کلیدهای ‏RocksDB‏ که ‏onode‏ و ‏extent map‏ را نگه می‌دارند تا بیت‌های ‏freelist‏ و ساختار کش در حافظه. همه‌ی ساختارها از شاخه‌ی ‏main‏ کد ‏Ceph‏ (‏src/os/bluestore/‏) استخراج شده‌اند. هرجا رفتار به نسخه بستگی دارد، علامت‌گذاری شده است.

۲۴-۲ ‏label‏ دستگاه: ‏bluestore_bdev_label_t‏#

ثابت‌ها در ‏bluestore_common.h‏ تعریف شده‌اند: ‏BDEV_FIRST_LABEL_POSITION = 0‏، ‏BDEV_LABEL_BLOCK_SIZE = 4096‏، ‏BLUEFS_SUPER_POSITION = 4096‏ و ‏SUPER_RESERVED = 8192‏. محتوای ‏label‏ به این ترتیب است:

# خواندن label (فقط خواندنی؛ OSD می‌تواند در حال اجرا باشد)
ceph-bluestore-tool show-label --dev /dev/ceph-xxx/osd-block-yyy
dd if=/dev/ceph-xxx/osd-block-yyy bs=4096 count=1 2>/dev/null | hexdump -C | head -5

۲۴-۳ کدگذاری‌های فشرده: ‏varint‏، ‏lowz‏ و ‏lba‏#

پیش از رفتن سراغ ساختارها باید سه کدگذاری را شناخت که در ‏include/denc.h‏ تعریف شده‌اند و همه‌جا در فراداده‌ی ‏BlueStore‏ به کار می‌روند:

مثال گام‌به‌گام ‏lowz‏ برای ۰‏x10000‏: این عدد ۱۶ بیت صفر انتهایی، یعنی ۴ ‏nibble‏، دارد ولی سقف ۳ است. پس ۰‏x10000‏ >> ۱۲ = ۰‏x10‏ و (۰‏x10‏ << ۲) | ۳ = ۰‏x43‏ که در یک بایت جا می‌شود.

مثال ‏lba‏ برای ۰‏x12340000‏: این عدد ۱۸ بیت صفر انتهایی، یعنی ۴ ‏nibble‏ کامل، دارد. پس ‏t‏ = ۴ − ۳ = ۱، حالت «۱۶ بیت حذف» با پیشوند ‏01‏ انتخاب می‌شود: ۰‏x12340000‏ >> ۱۶ = ۰‏x1234‏ و ‏word‏ = ۰‏b01‏ | (۰‏x1234‏ << ۲) = ۰‏x48D1‏. خروجی چهار بایت ‏little-endian‏ است: ‏d1 48 00 00‏. این مقادیر را با یک پیاده‌سازی پایتونی مستقل از روی منطق ‏denc.h‏ محاسبه کرده‌ایم.

۲۴-۴ ‏BlueFS‏: فایل‌سیستمی برای ‏RocksDB‏#

‏RocksDB‏ به یک فایل‌سیستم نیاز دارد (فایل‌های ‏SST‏، ‏WAL‏، ‏MANIFEST‏، ‏CURRENT‏). ‏BlueStore‏ به‌جای ‏ext4‏ یا ‏XFS‏، فایل‌سیستم کوچک خودش یعنی ‏BlueFS‏ را دارد که از طریق ‏BlueRocksEnv‏ به ‏RocksDB‏ وصل می‌شود. ‏BlueFS‏ فقط چیزهایی را پیاده می‌کند که ‏RocksDB‏ لازم دارد: چند دایرکتوری تخت، فایل‌های فقط-افزودنی، ‏rename‏ و ‏unlink‏ و ‏fsync‏.

۲۴-۴-۱ ساختارها#

pseudocode: mount مربوط به BlueFS (خلاصه‌ی این کتاب)
  super = decode(read(bdev[DB or SLOW], 0x1000, 4096)); verify crc
  log_reader = open(super.log_fnode)
  pos = 0
  repeat:
      read header at pos; if uuid != super.uuid or seq != expected → end of log
      t = decode(bluefs_transaction_t); verify crc
      for op in t.op_bl:
          INIT        → nothing
          DIR_CREATE  → dir_map[name] = {}
          DIR_LINK    → dir_map[d][f] = ino
          FILE_UPDATE → file_map[ino].fnode = fnode
          FILE_UPDATE_INC → merge extents into file_map[ino].fnode
          FILE_REMOVE → release extents (unless shared)
          JUMP/JUMP_SEQ → pos/seq = ...
      pos = next block-aligned boundary
  # در پایان، allocator هر bdev از روی extentهای همه‌ی fnodeها ساخته می‌شود

۲۴-۴-۲ فشرده‌سازی لاگ و حالت ‏envelope‏#

‏_should_start_compact_log_L_N()‏ اندازه‌ی فعلی لاگ را با ‏_estimate_log_size_N()‏ مقایسه می‌کند. اگر هر دو شرط جدول بالا برقرار باشد، ‏_compact_log_async_LD_LNF_D()‏ اجرا می‌شود: تصویر کامل فراداده (همه‌ی دایرکتوری‌ها و ‏fnode‏ها) در یک لاگ تازه نوشته می‌شود، ‏superblock‏ با ‏log_fnode‏ جدید و ‏seq‏ بالاتر به‌روزرسانی می‌شود و ‏extent‏های لاگ قدیمی آزاد می‌شوند. ترتیب این مراحل طوری است که ‏crash‏ در هر لحظه یا لاگ قدیمی سالم یا لاگ جدید کامل را باقی بگذارد.

ceph-bluestore-tool bluefs-bdev-sizes --path /var/lib/ceph/osd/ceph-4      # OSD متوقف
ceph-bluestore-tool bluefs-log-dump --path /var/lib/ceph/osd/ceph-4
ceph daemon osd.4 bluefs stats                         # admin socket روی میزبان OSD
ceph-bluestore-tool bluefs-export --path ... --out-dir /tmp/bluefs   # فایل‌های RocksDB برای ldb

۲۴-۵ نقشه‌ی کامل پیشوندهای ‏KV‏#

تمام فراداده‌ی ‏BlueStore‏ در ‏RocksDB‏ قرار دارد. نخستین کاراکتر هر کلید «پیشوند» آن است و در ‏BlueStore.cc‏ تعریف شده است:

۲۴-۶ ‏onode‏: از کلید تا ‏extent‏#

۲۴-۶-۱ کلید شیء#

کلید طوری ساخته می‌شود که پیمایش ترتیبی ‏RocksDB‏ دقیقاً همان ترتیب اشیای یک ‏PG‏ را بدهد. بنابراین ‏collection_list‏ (که در ‏scrub‏ و ‏backfill‏ استفاده می‌شود) به یک ‏range scan‏ ساده تبدیل می‌شود:

۲۴-۶-۲ ‏bluestore_onode_t‏#

فیلدهای اصلی: ‏nid‏ (شناسه‌ی عددی محلی برای کلیدهای ‏omap‏)، ‏size‏، ‏attrs‏ (‏xattr‏ها مثل ‏_‏ برای ‏object_info_t‏ و ‏snapset‏)، ‏extent_map_shards‏ (فهرست ‏{offset, bytes}‏)، ‏expected_object_size‏، ‏expected_write_size‏، ‏alloc_hint_flags‏، ‏segment_size‏ و ‏flags‏ (‏FLAG_OMAP=1‏، ‏FLAG_PGMETA_OMAP=2‏، ‏FLAG_PERPOOL_OMAP=4‏، ‏FLAG_PERPG_OMAP=8‏). اگر ‏extent_map_shards‏ خالی باشد، کل ‏extent map‏ به‌صورت ‏inline‏ پس از ‏onode‏ در همان مقدار ذخیره می‌شود.

۲۴-۶-۳ ‏extent map‏ و کدگذاری فشرده‌ی آن#

هر ‏lextent‏ چهار عدد دارد: ‏logical_offset‏، ‏length‏، ‏blob_offset‏ و یک ارجاع به ‏blob‏. ‏ExtentMap::encode_some‏ با چهار پرچم در بیت‌های پایین ‏blobid‏ از تکرار اطلاعات پرهیز می‌کند:

بقیه‌ی بیت‌ها (پس از ‏BLOBID_SHIFT_BITS = 4‏) شناسه‌ی ‏blob‏ است. اگر ‏blob‏ محلی باشد و برای نخستین بار در این ‏shard‏ ظاهر شود، شناسه صفر نوشته می‌شود و ‏decoder‏ آن را از شمارنده‌ی خودش استنتاج می‌کند.

مثال عددی: یک تصویر ‏RBD‏ با شیء ۴‏M‏ که دو نوشتن ۶۴‏K‏ پشت‌سرهم در ‏offset‏های ۰ و ۰‏x10000‏، هرکدام در ‏blob‏ تازه، دریافت کرده است:

پس از هر ‏lextent‏، اگر ‏blob‏ تازه باشد، خود ‏blob‏ هم کدگذاری می‌شود: پرچم‌ها، ‏pextent‏ها (حدود ۵ بایت برای هرکدام) و آرایه‌ی ‏checksum‏. برای ‏blob‏ ۶۴‏K‏ با ‏crc32c‏ و ‏chunk‏ ۴‏K‏، آرایه‌ی ‏checksum‏ برابر ۱۶ × ۴ = ۶۴ بایت است. پس ‏checksum‏ غالب‌ترین بخش حجم ‏onode‏ است، نه آدرس‌ها. با ‏bluestore_csum_type=crc32c_16‏ این حجم نصف می‌شود.

۲۴-۶-۴ ‏shared blob‏ و ‏clone‏#

وقتی ‏rbd snap‏ یا ‏clone_range‏ یک ‏blob‏ را بین دو ‏onode‏ مشترک می‌کند، پرچم ‏FLAG_SHARED‏ روی ‏blob‏ گذاشته می‌شود و یک ‏sbid‏ می‌گیرد. شمارش ارجاع ‏extent‏های فیزیکی آن (‏bluestore_extent_ref_map_t‏: ‏offset‏ → {‏length‏، ‏refs}‏) در کلید ‏X‏ + ‏sbid‏ ذخیره می‌شود. حذف یکی از ‏clone‏‌ها فقط ‏refs‏ را کم می‌کند. فضای فیزیکی وقتی آزاد می‌شود که ‏refs‏ به صفر برسد.

۲۴-۷ ‏deferred write‏ روی دیسک#

برای نوشتن‌های کوچک‌تر از ‏bluestore_prefer_deferred_size‏ (در ‏HDD‏ برابر ۶۴‏K‏)، ‏BlueStore‏ داده را ابتدا همراه تراکنش فراداده در ‏RocksDB‏ می‌نویسد. ساختار آن:

pseudocode: چرخه‌ی deferred (خلاصه‌ی این کتاب)
  txc: kv.set("L" + seq, encode(deferred_txn)); kv.submit_sync()     # WAL مربوط به RocksDB = پایداری
  ack → client
  deferred_queue: جمع‌آوری تا bluestore_deferred_batch_ops یا فشار throttle (128M)
  _deferred_submit: aio_write(extents, data) روی دستگاه اصلی (بدون fsync جداگانه)
  _deferred_aio_finish → در txc بعدی: kv.rmkey("L" + seq)     # پس از flush دستگاه
  mount پس از crash: _deferred_replay() همه‌ی L* را دوباره روی دیسک می‌نویسد (idempotent)

۲۴-۸ ‏allocator‏: چه کسی فضای خالی را می‌شناسد؟#

۲۴-۸-۱ امتیاز تکه‌تکه شدن#

‏Allocator::get_fragmentation_score()‏ عددی بین ۰ (یک تکه‌ی پیوسته) و ۱ (همه‌ی فضای آزاد در تکه‌های تک‌بلوکی) برمی‌گرداند. ایده‌ی آن این است که یک تکه‌ی ۲‏X‏ بایتی ارزشمندتر از دو تکه‌ی ‏X‏ بایتی است. برای تکه‌های کوچک‌تر از ۱‏M‏ هر دو برابر شدن طول ۱٫۲ برابر وزن می‌گیرد، این ضریب تا ۱۲۸‏M‏ به‌طور خطی به ۱ می‌رسد و بالاتر از آن ثابت است. امتیاز به این شکل حساب می‌شود:

score(len) ≈ تابع افزایشی محدب (درون‌یابی خطی بین 2^k و 2^(k+1) با ضرایب بالا)
ideal    = score(sum)                          # همه‌ی آزاد در یک تکه
terrible = (sum / block_size) × score(block_size)
actual   = Σ score(len_i)
fragmentation = (ideal − actual) / (ideal − terrible)

ceph daemon osd.4 bluestore allocator score block       # {"fragmentation_rating": 0.27...}
ceph daemon osd.4 bluestore allocator fragmentation histogram block
ceph-bluestore-tool free-score --path /var/lib/ceph/osd/ceph-4    # OSD متوقف

۲۴-۸-۲ ‏freelist‏ و حالت بدون ‏freelist‏#

در ‏BitmapFreelistManager‏، ‏bytes_per_block‏ برابر واحد تخصیص (‏min_alloc_size‏) و ‏blocks_per_key = bluestore_freelist_blocks_per_key = 128‏ است. پس هر کلید ‏b‏ با ۱۶ بایت مقدار، ۱۲۸ واحد (با واحد ۴‏K‏، یعنی ۵۱۲‏K‏ دیسک) را پوشش می‌دهد. تخصیص و آزادسازی هر دو ‏XOR‏ با یک ماسک‌اند (‏XorMergeOperator‏ با نام ‏bitwise_xor‏). بنابراین بدون خواندن مقدار قبلی، فقط یک ‏merge‏ به ‏RocksDB‏ فرستاده می‌شود.

گزینه‌ی ‏bluestore_allocation_from_file‏ از ‏Quincy‏ وجود دارد (در ‏Pacific‏ نیست) و در ‏main‏ پیش‌فرض ‏true‏ است. در این حالت به‌روزرسانی ‏freelist‏ در مسیر نوشتن حذف می‌شود و ‏BlueStore‏ هنگام ‏umount‏ تمیز، نقشه‌ی ‏allocator‏ را در فایل ‏ALLOCATOR_NCB_DIR/ALLOCATOR_NCB_FILE‏ درون ‏BlueFS‏ می‌نویسد. اگر ‏shutdown‏ تمیز نباشد، ‏mount‏ بعدی با ‏read_allocation_from_onodes‏ همه‌ی ‏onode‏ها را پویش می‌کند تا فضای استفاده‌شده را بازسازی کند. این روش تراکنش‌ها را سبک‌تر می‌کند، ولی پس از ‏crash‏ زمان ‏mount‏ روی ‏OSD‏های پراز اشیا را چند دقیقه بیشتر می‌کند.

۲۴-۹ کش ‏BlueStore‏#

کش‌ها ‏shard‏بندی شده‌اند (هر ‏shard‏ عملیاتی ‏OSD‏ کش خودش را دارد) تا رقابت روی قفل کم شود. ‏onode‏ها با شمارنده‌ی ارجاع ‏pin‏ می‌شوند. ‏onode‏ی که در یک تراکنش در جریان استفاده می‌شود، تا پایان تراکنش بیرون رانده نمی‌شود، حتی اگر کش پر باشد.

ceph daemon osd.4 perf dump bluestore | jq '.bluestore | {onodes, onode_hits, onode_misses}'
ceph daemon osd.4 dump_mempools | jq '.mempool.by_pool | {o: .bluestore_cache_onode, d: .bluestore_cache_data}'

۲۴-۱۰ تخصیص فضا با عدد#

فضای آزاد دستگاه اصلی ‏BlueStore‏ را تخصیص‌دهنده (‏allocator‏) نگه می‌دارد. پیش‌فرض ‏bluestore_allocator = hybrid‏ است: یک ‏AVL allocator‏ که بخشی از بازه‌هایش را در صورت نیاز به ‏bitmap allocator‏ می‌سپارد. این بخش سه الگوریتم آن را با عدد دنبال می‌کند.

۲۴-۱۰-۱ ‏near-fit‏ و ‏best-fit‏ در ‏AVL‏#

pseudocode
max_size = بزرگ‌ترین بازه (انتهای درخت اندازه)
if max_size < want: want = p2align(max_size, unit) ; force best-fit   # تخصیص تکه‌ای
free_pct = num_free × 100 / device_size
if force or max_size < bf_threshold (128K) or free_pct < bf_free_pct (4): best-fit
else near-fit:
    align = want & −want ; cursor = lbas[cbits(align) − 1]   # یک cursor برای هر توان دو
    از lower_bound(cursor) در درخت offset جلو برو تا offset + want ≤ end
    (حداکثر ff_max_search_count = 100 بازه یا ff_max_search_bytes = 16M؛ بعد از ابتدا تا cursor)
best-fit: lower_bound({0, want}) در درخت اندازه ⇒ کوچک‌ترین بازه‌ی کافی؛ در تساوی، offset کمتر

مثال عددی. بخشی از دستگاه چهار بازه‌ی آزاد دارد: ۳۲‏K‏ در ۰‏x10000‏، ۱۲۸‏K‏ در ۰‏x40000‏، ۳۲‏K‏ در ۰‏x100000‏ و ۱‏M‏ در ۰‏x200000‏.

• درخواست ۶۴‏K‏ (near-fit): ‏align‏ = ۰‏x10000‏، پس ‏cbits‏ = ۱۷ و ‏cursor‏ = ‏lbas[16]‏ = ۰. بازه‌ی اول کوچک است و ‏cursor‏ به ۰‏x20000‏ می‌رود. بازه‌ی دوم جا دارد: ‏offset‏ = ۰‏x40000‏ و ‏cursor‏ = ۰‏x50000‏. درخواست ۶۴‏K‏ بعدی با همین ‏cursor‏ از ۰‏x50000‏ ادامه می‌دهد، پس تخصیص‌های هم‌اندازه کنار هم می‌افتند.
• درخواست ۳۲‏K‏ (best-fit): فرض کنید دستگاه بزرگ است و فضای آزاد زیر ۴٪ آمده. درخت اندازه دو بازه‌ی ۳۲‏K‏ دارد و ‏lower_bound‏ با کلید {۰، ۳۲‏K}‏ آنکه ‏offset‏ کمتر دارد را برمی‌گرداند، یعنی ۰‏x10000‏. بازه‌ی ۱‏M‏ دست نخورده می‌ماند.

جریمه‌ی ‏near-fit‏ این است که بازه‌های بزرگ را تکه‌تکه می‌کند. ‏best-fit‏ کندتر نیست، اما تخصیص‌های پیاپی را از هم دور می‌کند. به همین دلیل فقط وقتی فضا کم است فعال می‌شود.

۲۴-۱۰-۲ امتیاز تکه‌تکه شدن با عدد#

pseudocode
scale[0] = 1 ; scale[k+1] = scale[k] × w(k)    # w = 1.2 تا 2^20، خطی تا 1.0 در 2^27، بعد 1.0
score(v): sc = floor(log2 v) ; b = 2^sc ; x = (v − b)/b
          return b·scale[sc]·(1 − x) + 2b·scale[sc+1]·x       # درون‌یابی خطی
actual = Σ score(len_i) ; ideal = score(Σ len) ; terrible = (Σ len / block_size) × score(block_size)
rating = (ideal − actual) / (ideal − terrible)

مثال عددی (‏block_size‏ = ۴‏K‏، ۱ ‏GiB‏ آزاد). این اعداد با پیاده‌سازی مستقل همین فرمول حساب شده‌اند:

• یک تکه‌ی ۱‏G‏، و هر تکه‌ی بزرگ‌تر از ۱۲۸‏M‏: امتیاز ۰.
• تکه‌های ۱۶‏M: 0.093‏.
• تکه‌های ۱‏M: 0.498‏.
• تکه‌های ۶۴‏K: 0.837‏.
• تکه‌های ۱۶‏K: 0.933‏.
• تکه‌های ۴‏K: 1‏.
• ترکیب ۸۹۶ مگابایتی (دو تکه‌ی ۲۵۶‏M‏، ۲۵۶ تکه‌ی ۱‏M‏ و ۲۰۴۸ تکه‌ی ۶۴‏K‏): ۰.۲۶۲. بیشتر فضا در تکه‌های بزرگ است، پس امتیاز پایین می‌ماند، هرچند تعداد تکه‌های کوچک زیاد است.

چون ضریب بالای ۱۲۸‏M‏ برابر ۱ است، تکه‌هایی بزرگ‌تر از ۱۲۸‏M‏ هیچ جریمه‌ای ندارند. امتیاز بالای ۰.۸ روی ‏HDD‏ معمولاً یعنی ‏min_alloc_size‏ کوچک و تخصیص‌های پراکنده. در این حالت نوشتن‌های بزرگ به چند ‏extent‏ شکسته می‌شوند.

۲۴-۱۰-۳ سرریز ‏hybrid‏ به ‏bitmap‏#

pseudocode
range_count_cap = bluestore_hybrid_alloc_mem_cap (64M) / sizeof(range_seg_t)
insert(start, end):
    if size_tree.size < cap: درج در AVL
    elif end − start > کوچک‌ترین بازه‌ی AVL: درج و انتقال کوچک‌ترین به bitmap
    else: مستقیم به bitmap
allocate(want):
    primary = AVL ، مگر bitmap فضای آزاد دارد و want < کوچک‌ترین بازه‌ی AVL ⇒ primary = bitmap
    از primary بگیر ؛ کسری را از دیگری بگیر ؛ هیچ ⇒ ENOSPC

مثال عددی. هر ‏range_seg_t‏ دو عدد ۶۴ بیتی (‏start‏ و ‏end‏، روی هم ۱۶ بایت) و دو ‏hook‏ درخت ‏AVL‏ از ‏boost::intrusive‏ دارد (‏offset_hook‏ و ‏size_hook‏). ‏MEMPOOL_CLASS_HELPERS()‏ فقط ‏operator new/delete‏ تعریف می‌کند و عضو داده‌ای اضافه نمی‌کند. هر ‏avl_set_member_hook<>‏ با پارامترهای پیش‌فرض (بدون ‏optimize_size‏) سه اشاره‌گر ‏parent‏، ‏left‏ و ‏right‏ و یک فیلد ‏balance‏ دارد که با هم‌ترازی ۸ بایتی ۳۲ بایت می‌شود. پس ‏sizeof‏(range_seg_t) = ۱۶ + ۳۲ + ۳۲ = ۸۰ بایت است. این عدد را با کامپایل یک برنامه‌ی کوچک با همین چیدمان روی ‏x86-64‏ (هدرهای ‏boost.intrusive‏ شاخه‌ی اصلی، ‏Clang 22.1‏ از طریق ‏zig c++ 0.17.1‏، استاندارد ‏C++17‏) بررسی کردیم: خروجی ‏hook‏ = ۳۲، ‏seg‏ = ۸۰، ‏offsetof‏(size_hook) = ۴۸ و ‏alignof‏ = ۸ بود. سقف ۶۴ مگابایتی (‏bluestore_hybrid_alloc_mem_cap‏ = ۶۴ ‏MiB‏ = ۶۷۱۰۸۸۶۴ بایت) بنابراین ⌊۶۷۱۰۸۸۶۴ / ۸۰⌋ = ۸۳۸۸۶۰ بازه را در ‏AVL‏ نگه می‌دارد. حافظه‌ی واقعی کمی بیشتر است، چون سربار تخصیص‌دهنده‌ی ‏heap‏ در این محاسبه نیست. روی معماری‌های ۳۲ بیتی یا با هدرهای ‏boost‏ دیگر ممکن است عدد فرق کند.

• ‏HDD‏ شانزده ترابایتی با ۳۰٪ فضای آزاد و میانگین تکه‌ی ۶۴‏K‏: حدود ۴.۸‏T‏ / ۶۴‏K‏، یعنی نزدیک ۷۳ میلیون بازه وجود دارد. پس بیش از ۹۸٪ بازه‌ها، یعنی کوچک‌ترین‌ها، در ‏bitmap‏ می‌مانند و ‏AVL‏ فقط بزرگ‌ترین‌ها را نگه می‌دارد.
• تخصیص ۴‏K‏: از کوچک‌ترین بازه‌ی ‏AVL‏ کوچک‌تر است، پس مستقیم از ‏bitmap‏ گرفته می‌شود و بازه‌های بزرگ دست نخورده می‌مانند.

۲۴-۱۱ روی دیسک واقعی: ‏label‏ و نقشه‌ی فضای آزاد#

دو شکل این بخش از ‏OSD‏های ‏BlueStore‏ یک کلاستر آزمایشی با ‏Ceph 18.2.7‏ گرفته شده‌اند. دستگاه ‏block‏ هر ‏OSD‏ یک فایل ‏sparse‏ ده‌گیگابایتی بود.

۲۴-۱۱-۱ ۵۸۸ بایت نخست ‏label‏#

بایت‌ها مستقیم از فایل ‏block‏ خوانده شدند و با خروجی ‏ceph-bluestore-tool show-label‏ مقایسه شدند. این کلاستر بدون ‏cephx‏ بود، پس ‏meta‏ کلید ‏osd_key‏ نداشت. در کلاستر واقعی این فیلد را پیش از نشان دادن به کسی حذف کنید.

pseudocode
b = 4 KiB نخست دستگاه
از 60 بایت متنی بپر: "bluestore block device\n" (23) + uuid متنی + "\n" (37)
struct_v = b[60] ؛ compat = b[61] ؛ len = u32le(b[62:66])        # ENCODE_START(2, 1)
osd_uuid = b[66:82] ؛ size = u64le(b[82:90]) ؛ btime = (u32 sec, u32 nsec)
description = (u32 len, bytes) ؛ meta = u32 count و سپس count جفت (u32 len, key)(u32 len, value)
end = 60 + 6 + len ؛ crc = u32le(b[end:end+4])
درست اگر crc32c(seed = 0xffffffff, بدون xor پایانی)(b[0:end]) == crc

مقادیر واقعی.

• سرآیند ساختار: در آفست ۰‏x3c‏ مقدار ‏02 01‏ یعنی ‏struct_v‏ = ۲ و ‏compat‏ = ۱، و ‏06 02 00 00‏ یعنی طول ۵۱۸. پس بدنه تا آفست ۵۸۴ ادامه دارد.
• ‏size‏: ‏‏00 00 00 80 02 00 00 00‏ برابر ۰‏x280000000‏، یعنی ۱۰۷۳۷۴۱۸۲۴۰ بایت.
• ‏btime‏: شامل ‏sec‏ = ۱۷۹۴۷۱۲۷۴۶ و ‏nsec‏ = ۳۹۳۱۸۴۱۹۲، یعنی ۲۰۲۶-۱۱-۱۵ ۰۶:۴۹:۰۶.۳۹۳ به وقت تهران.
• ‏description‏ و ‏meta‏: مقدار ‏description‏ برابر "‏main"‏ است و ‏meta‏ چهارده جفت دارد، از جمله ‏bfm_blocks = 2621440‏، ‏bfm_bytes_per_block = 4096‏، ‏kv_backend = rocksdb‏ و ‏magic = ceph osd volume v026‏.
• ‏crc‏: چهار بایت آفست ۰‏x248‏ برابر ۰‏xb012c37d‏ است. همین مقدار را با پیاده‌سازی مستقل ‏crc32c‏ (چندجمله‌ای ‏Castagnoli‏، ‏seed‏ برابر −۱، بدون ‏xor‏ پایانی) دوباره حساب کردیم. ‏‏decoder‏ همان ۶۰ بایت را با ‏p += 60u‏ رد می‌کند.

۲۴-۱۱-۲ نقشه‌ی فضای آزاد ‏allocator‏#

ابزار مورد استفاده ‏ceph daemon osd.0 bluestore allocator dump block‏ است. این فرمان فهرست کامل ‏extent‏های آزاد را می‌دهد. ‏… allocator score block‏ هم ‏fragmentation_rating‏ را برمی‌گرداند. هر دو برای ‏allocator‏ پیش‌فرض این نسخه (‏hybrid‏) با ‏min_alloc_size‏ برابر ۴ ‏KiB‏ گرفته شدند. سه لحظه ثبت شد:

• ‏A‏: پس از حذف ‏pool‏های آزمایشی قبلی (بنچمارک‌های ۴ ‏KiB‏ و ۴ ‏MiB‏). امتیاز ۰.۰۱۶۳ بود.
• ‏B‏: پس از نوشتن ۶۰۰۰ شیء ۶۴ ‏KiB‏ در یک ‏pool‏ تک‌نسخه‌ای. امتیاز ۰.۰۱۶۷ بود.
• ‏C‏: پس از حذف تصادفی ۵۱٪ آن شیءها. امتیاز ۰.۰۲۱۵ بود.

آنچه داده نشان می‌دهد.

1. ۱. حفره‌های ۴ ‏KiB‏: حتی در ‏A‏، فضای آزاد به ۲۶۲۳۵ ‏extent‏ تکه شده بود که ۲۳۲۱۸ تای آن‌ها فقط ۴ ‏KiB‏ بودند. علت دقیق این حفره‌ها را در این آزمایش جدا نکردیم. احتمالاً به جای‌گیری درهم با داده‌ها و فراداده‌های زنده برمی‌گردد.
2. ۲. حجم فضای آزاد: حدود ۸.۵ ‏GiB‏ فضای آزاد تقریباً همه در چند ‏extent‏ بزرگ ۲۵۶ ‏MiB‏ تا ۲.۴ ‏GiB‏ است.
3. ۳. نوشتن ۶۴ ‏KiB‏: این نوشتن‌ها حفره‌های ۴ ‏KiB‏ را پر نکردند، چون ‏allocator‏ برای درخواست ۶۴ ‏KiB‏ یک ‏extent‏ پیوسته می‌خواهد. حذف تصادفی بعدی حدود ۳۳۰ حفره‌ی تازه‌ی ۶۴ تا ۵۱۲ ‏KiB‏ ساخت.
4. ۴. امتیاز کلی: ‏fragmentation_rating‏ در هر سه حالت زیر ۰.۰۳ ماند. این امتیاز با وزن بایت حساب می‌شود (الگوریتم امتیاز ‏fragmentation‏ در بخش قبل) و وقتی بیشتر بایت‌های آزاد در ‏extent‏های بزرگ‌اند، ده‌ها هزار حفره‌ی کوچک آن را بالا نمی‌برند.

پس امتیاز پایین به این معنا نیست که «حفره‌ی کوچک نداریم». تعداد ‏extent‏ها روی حافظه‌ی ‏allocator‏ و زمان جست‌وجو اثر دارد. برای دیدن آن، خود فهرست ‏extent‏ها را بشمارید.

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

• کپی‌های ‏label‏ (‏bdev_label_positions‏) در کد ‏Squid‏، ‏Tentacle‏ و ‏main‏ وجود دارند. حالت ‏envelope‏ در ‏BlueFS‏ فقط در ‏Tentacle‏ و ‏main‏ هست و در ‏Squid‏ نیست. اگر خوشه‌ی مختلط دارید، روی ‏OSD‏های قدیمی‌تر روی این ویژگی‌ها حساب نکنید.
• ‏hybrid_btree2‏ و ‏bluestore_allocator_lookup_policy‏ در ‏Squid‏ و بالاتر وجود دارند.
• شاخه‌ی ‏main‏ همچنین ساختارهای مربوط به نوشتن جدید ‏BlueStore‏ (مثل ‏segment_size‏ در ‏onode‏ و ‏FragMetric‏ در ‏bluestore_common.h‏) را دارد که بخشی از کارهای در جریان روی کاهش تکه‌تکه شدن و ‏EC‏ جدید است. جزئیات آن را پیش از انتشار نهایی در یادداشت‌های نسخه دنبال کنید.

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

1. ۱. روی یک ‏OSD‏ آزمایشی ۴‏K‏ اول دستگاه را با ‏dd‏ بخوانید. ۶۰ بایت متنی را ببینید، بقیه را با خروجی ‏ceph-bluestore-tool show-label‏ مقایسه کنید و ‏crc‏ را با تابع پایتون فصل ۲۳ دوباره حساب کنید.
2. ۲. یک تابع ‏lowz‏ و ‏lba‏ بنویسید، مقادیر جدول این فصل را بازتولید کنید و برای ‏offset‏های واقعی خروجی ‏ceph-bluestore-tool fsck --deep‏ یا ‏dump onode‏ اندازه‌ی کدگذاری را بسنجید.
3. ۳. یک تصویر ‏RBD‏ را با ‏fio‏ به‌صورت تصادفی ۴‏K‏ بنویسید و تعداد کلیدهای ‏O‏ با پسوند ‏x‏ (‏shard‏ها) را پیش و پس از آن با ‏ceph-kvstore-tool‏ بشمارید.
4. ۴. ‏bluestore allocator score block‏ را روزانه روی چند ‏OSD‏ ثبت و با درصد پر بودن آن‌ها مقایسه کنید.
5. ۵. ‏OSD‏ را با ‏kill -9‏ متوقف کنید، دوباره راه بیندازید و در لاگ زمان ‏read_allocation_from_onodes‏ را اندازه بگیرید.

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

1. ۱. ۶۰ بایت اول ‏label‏ شامل چیست و چرا ‏decoder‏ از آن می‌پرد؟
2. ۲. چرا ‏superblock‏ مربوط به ‏BlueFS‏ همیشه در ‏offset 4096‏ است؟
3. ۳. ‏denc_lba‏ برای ‏offset‏ هم‌تراز با ۴‏K‏ چند بایت مصرف می‌کند و چرا؟
4. ۴. چه شرطی فشرده‌سازی لاگ ‏BlueFS‏ را آغاز می‌کند؟
5. ۵. چرا ‏hash‏ در کلید ‏onode‏ بیت‌معکوس است؟
6. ۶. پرچم‌های ‏BLOBID‏ در ‏extent map‏ چه صرفه‌جویی‌ای ایجاد می‌کنند؟
7. ۷. چرا ‏checksum‏ بزرگ‌ترین بخش یک ‏blob‏ کدگذاری‌شده است؟
8. ۸. ‏hybrid allocator‏ چگونه مصرف حافظه را محدود می‌کند؟
9. ۹. چرا ‏freelist‏ از ‏merge‏ با ‏XOR‏ استفاده می‌کند؟
10. ۱۰. الگوریتم ۲‏Q‏ چه مشکلی از ‏LRU‏ را حل می‌کند؟

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

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

• انواع ‏BlueStore‏
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/bluestore_types.h
• انواع ‏BlueFS‏
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/bluefs_types.h
• کدگذاری ‏denc‏
  https://github.com/ceph/ceph/blob/main/src/include/denc.h
• امتیاز تکه‌تکه شدن
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/Allocator.cc
• ‏BitmapFreelistManager‏
  https://github.com/ceph/ceph/blob/main/src/os/bluestore/BitmapFreelistManager.cc
• پیکربندی ‏BlueStore‏
  https://docs.ceph.com/en/latest/rados/configuration/bluestore-config-ref/
• ‏ceph-bluestore-tool‏
  https://docs.ceph.com/en/latest/man/8/ceph-bluestore-tool/
• مقاله‌ی ‏BlueStore‏ (SOSP ۲۰۱۹
  https://www.pdl.cmu.edu/PDL-FTP/Storage/ceph-exp-sosp19.pdf
• ۲‏Q‏ (Johnson و ‏Shasha‏، ‏VLDB 1994‏
  https://www.vldb.org/conf/1994/P439.PDF