لایه‌های پایینی (۸): ‏Crimson‏ و ‏Seastar‏، ‏OSD‏ تک‌هسته‌ای و ‏SeaStore‏

۳۰-۱ مقدمه: چرا یک ‏OSD‏ تازه؟#

‏OSD‏ کلاسیک (فصل‌های ۱۲، ۲۱ و ۲۲) در دوره‌ای طراحی شد که دیسک چرخان چند میلی‌ثانیه تأخیر داشت و چند ده میکروثانیه هزینه‌ی نرم‌افزار در برابر آن ناچیز بود. روی ‏NVMe‏ امروزی، یک خواندن ۴‏K‏ در حدود ۱۰ تا ۸۰ میکروثانیه تمام می‌شود. در همین مدت، ‏OSD‏ کلاسیک پیام را از یک ‏thread‏ شبکه به صف شارد، از آنجا به ‏thread‏ دیگری با قفل ‏PG‏ و سپس به ‏thread‏های ‏kv_sync‏ و ‏finisher‏ در ‏BlueStore‏ می‌سپارد. هر جابه‌جایی بین ‏thread‏ها هزینه‌ی ‏context switch‏، از دست رفتن ‏cache‏ پردازنده و رقابت قفل دارد. ‏Crimson‏ بازنویسی ‏OSD‏ روی چارچوب ‏Seastar‏ است تا این هزینه‌ها حذف شوند: هر هسته‌ی پردازنده یک ‏reactor‏ دارد و هر ‏PG‏ فقط روی یک هسته زندگی می‌کند.

این شکل تفاوت بنیادی دو مدل را نشان می‌دهد. در ردیف بالا، یک درخواست دست‌کم چهار بار بین ‏thread‏ها جابه‌جا می‌شود و در هر جابه‌جایی داده‌ی آن باید از ‏cache‏ هسته‌ی دیگری خوانده شود. در ردیف میانی، داده‌ی یک ‏PG‏ (log، ‏object context‏، ‏cache‏) فقط در حافظه‌ی یک هسته است و هیچ قفلی لازم نیست، چون هیچ هسته‌ی دیگری به آن دست نمی‌زند. بهای این سادگی آن است که هر تعامل بین هسته‌ها باید صریح باشد، مثل پیامی که به هسته‌ی ۰ برای پیدا کردن هسته‌ی صاحب ‏PG‏ فرستاده می‌شود.

۳۰-۲ ‏Seastar: future‏، ‏continuation‏ و ‏reactor‏#

در ‏Seastar‏ هیچ تابعی بلوکه نمی‌شود. تابعی که کار ناهم‌گام دارد (خواندن از شبکه، نوشتن روی دیسک، پرسش از هسته‌ی دیگر) بی‌درنگ یک ‏future<T>‏ برمی‌گرداند. ادامه‌ی کار با ‏.then()‏ به آن ‏future‏ وصل می‌شود. وقتی نتیجه آماده شد، تولیدکننده با ‏promise.set_value()‏ آن را آماده می‌کند و ‏continuation‏ به صف ‏task‏ همان ‏reactor‏ می‌رود. ‏reactor‏ یک حلقه‌ی بی‌پایان روی هر هسته است: ‏task‏های آماده را اجرا می‌کند، ‏backend‏ ورودی و خروجی (‏io_uring‏، ‏linux-aio‏ یا ‏epoll‏، با گزینه‌ی ‏crimson_reactor_backend‏) را ‏poll‏ می‌کند و تایمرها را بررسی می‌کند.

pseudocode: یک دور reactor (مدل مفهومی، بازنویسی این کتاب)
loop forever:
  t0 = now()
  while ready_tasks not empty and now() - t0 < task_quota:   # 0.5ms
      task = ready_tasks.pop_front(); task.run()             # continuation‌ها
  poll(io backend)          # تکمیل io_uring/aio ⇒ promise.set_value ⇒ task جدید
  poll(network)             # داده‌ی socket ⇒ task جدید
  poll(smp queues)          # پیام از هسته‌های دیگر (submit_to)
  run expired timers
  if nothing to do for idle_poll_time (200us): sleep in kernel (مگر poll_mode)

مثال عددی. فرض کنید هر خواندن ۴‏K‏ روی ‏reactor‏ حدود ۱۵ میکروثانیه ‏CPU‏ مصرف کند (‏decode‏، جست‌وجوی ‏object context‏، ساخت پاسخ). با سهم ۰.۵ میلی‌ثانیه، در هر دور حدود ۳۳ درخواست اجرا می‌شود و سپس ‏reactor‏ دوباره دستگاه و شبکه را ‏poll‏ می‌کند. پس بیشینه‌ی تأخیر اضافه برای یک تکمیل ورودی و خروجی تازه حدود ۰٫۵ میلی‌ثانیه است. اگر یک ‏continuation‏ بد ۵ میلی‌ثانیه ‏CPU‏ مصرف کند (مثلاً پیمایش یک ‏omap‏ بزرگ بدون تقسیم کار)، همه‌ی ‏PG‏های آن هسته ۵ میلی‌ثانیه متوقف می‌شوند. این همان «‏stall‏» است که ‏Seastar‏ در ‏log‏ گزارش می‌کند. در مدل تعاونی، کار طولانی باید با ‏seastar::maybe_yield()‏ یا حلقه‌های ناهم‌گام تکه‌تکه شود.

۳۰-۲-۱ ‏shared-nothing‏ در عمل#

داده‌ای که بین هسته‌ها مشترک است فقط از سه راه جابه‌جا می‌شود: ‏seastar::smp::submit_to(core, func)‏ یک تابع را روی هسته‌ی دیگر اجرا می‌کند و ‏future‏ نتیجه را برمی‌گرداند. ‏sharded<T>‏ یک نمونه از سرویس را روی هر هسته نگه می‌دارد و ‏invoke_on‏ و ‏invoke_on_all‏ آن را فرا می‌خوانند. ‏foreign_ptr‏ هم مالکیت شیئی را که روی هسته‌ی دیگر ساخته شده است منتقل می‌کند تا آزادسازی آن روی همان هسته‌ی سازنده انجام شود. در ‏Crimson‏، ‏PGShardMapping‏ یک ‏peering_sharded_service‏ است. یعنی هر هسته یک کپی محلی از نقشه‌ی ‏PG‏ به هسته دارد، ولی فقط هسته‌ی ۰ آن را تغییر می‌دهد.

۳۰-۳ الگوریتم نگاشت ‏PG‏ به هسته#

pseudocode: get_or_create_pg_mapping (خلاصه‌ی منطق کد)
on any core:
  if pgid in local.pg_to_core: return local.pg_to_core[pgid]
  return invoke_on(core 0):
     if pgid in primary.pg_to_core: core = that core
     else:
        core = argmin_c primary.core_to_num_pgs[c]    # کم‌بارترین هسته
        primary.core_to_num_pgs[core] += 1
        store_index = pick least-loaded store shard on core (اگر چند shard ذخیره‌ساز)
        primary.pg_to_core[pgid] = (core, store_index)
     broadcast mapping to all cores; return (core, store_index)

مثال عددی. ‏OSD‏ با ‏crimson_cpu_num=4‏ و هسته‌های ۰ تا ۳ را در نظر بگیرید که به‌ترتیب ۳۰، ۲۹، ۳۱ و ۲۹ ‏PG‏ دارند. ‏PG‏ تازه‌ی ۲.۱‏f‏ وارد می‌شود. ‏min_element‏ اولین کمینه را برمی‌گرداند، پس هسته‌ی ۱ انتخاب می‌شود (نه ۳) و شمارش‌ها ۳۰، ۳۰، ۳۱ و ۲۹ می‌شوند. ‏PG‏ بعدی به هسته‌ی ۳ می‌رود. این روش فقط تعداد ‏PG‏ را متوازن می‌کند، نه بار آن‌ها را. اگر دو ‏PG‏ داغ ‏RBD‏ روی یک هسته بیفتند، آن هسته اشباع می‌شود و هسته‌های دیگر بی‌کار می‌مانند، چون در مدل ‏shared-nothing‏ هیچ ‏work-stealing‏ وجود ندارد. این یکی از تفاوت‌های عملی مهم با ‏OSD‏ کلاسیک است که ‏thread‏های هر شارد بین ‏PG‏های متعدد آن شارد مشترک‌اند.

۳۰-۴ ‏pipeline‏ عملیات#

در ‏OSD‏ کلاسیک، ترتیب درخواست‌های یک ‏PG‏ با قفل ‏PG‏ و صف شارد حفظ می‌شود. ‏Crimson‏ به‌جای قفل از ‏phase‏ها استفاده می‌کند (‏src/crimson/osd/osd_operation.h‏). هر ‏phase‏ یا ‏OrderedExclusive‏ است، یعنی در هر لحظه فقط یک عملیات در آن است و ترتیب ورود حفظ می‌شود، یا ‏OrderedConcurrent‏، یعنی چند عملیات هم‌زمان در آن هستند ولی به همان ترتیب خارج می‌شوند.

استدلال تأخیر. چون ‏WaitRepop‏ هم‌زمان است، ۳۲ نوشتن متوالی روی یک شیء می‌توانند هم‌زمان منتظر ‏replica‏ها باشند. اگر رفت‌وبرگشت تا ‏replica 200‏ میکروثانیه و پردازش هر نوشتن ۲۰ میکروثانیه باشد، گذردهی یک شیء حدود ۱/۲۰µ‏s=50K‏ نوشتن در ثانیه است، نه ۱/۲۲۰µ‏s‏. اگر ‏Process‏ بلوکه شود (مثلاً منتظر خواندن ‏object context‏ از دیسک)، کل صف شیء پشت آن می‌ماند. به همین دلیل ‏crimson_osd_obc_lru_size=512‏ (اندازه‌ی ‏cache‏ مربوط به ‏object context‏) برای بار تصادفی اهمیت زیادی دارد.

۳۰-۵ پشتیبان‌های ذخیره‌سازی در ‏Crimson‏#

رابط ذخیره‌سازی ‏Crimson‏ ‏FuturizedStore‏ است (‏src/crimson/os/futurized_store.h‏). هر عمل به‌جای مقدار، ‏future‏ برمی‌گرداند. سه پیاده‌سازی در ‏src/crimson/os/‏ وجود دارد:

در ‏alien_store.cc‏، ‏thread pool‏ با ‏crimson_bluestore_num_threads‏ (پیش‌فرض ۶ در ‏main‏) ساخته می‌شود. عملیات یک ‏collection‏ با ‏ch->get_cid().hash_to_shard(tp->size())‏ همیشه به یک ‏thread‏ مشخص می‌رود تا ترتیب تراکنش‌های یک ‏PG‏ حفظ شود. این همان نقشی است که در ‏OSD‏ کلاسیک صف شارد ایفا می‌کند.

۳۰-۶ ‏SeaStore‏: معماری#

‏SeaStore‏ یک ‏ObjectStore‏ ‏log-structured‏ و تراکنشی است. هیچ داده‌ای در جای قبلی بازنویسی نمی‌شود، مگر در ‏backend‏ مربوط به ‏random block‏ (RBM). هر تراکنش به یک ‏record‏ در ‏journal‏ تبدیل می‌شود که ‏delta‏ها (تغییرات منطقی روی بلوک‌ها) و بلوک‌های تازه را در بر دارد.

دو نوع آدرس در ‏SeaStore‏ وجود دارد. ‏laddr‏ آدرس منطقی است که ‏onode‏ها و درخت‌های ‏omap‏ به آن اشاره می‌کنند و با جابه‌جایی بلوک در ‏GC‏ تغییر نمی‌کند. ‏paddr‏ آدرس فیزیکی است. تنها ساختاری که باید با جابه‌جایی بلوک به‌روز شود ‏LBA tree‏ است. این طراحی هزینه‌ی ‏GC‏ را محدود می‌کند: جابه‌جا کردن یک بلوک داده فقط یک ورودی برگ در ‏LBA tree‏ را عوض می‌کند، نه همه‌ی اشاره‌گرهای به آن.

۳۰-۶-۱ ‏paddr_t‏ بیت به بیت#

آدرس‌های نسبی (‏DEVICE_ID_RECORD_RELATIVE‏ و ‏DEVICE_ID_BLOCK_RELATIVE‏) نکته‌ی ظریفی دارند. وقتی تراکنشی ساخته می‌شود، هنوز معلوم نیست ‏record‏ آن در کجای ‏journal‏ قرار می‌گیرد. پس بلوک‌های تازه با آفست نسبی به ابتدای ‏record‏ نام‌گذاری می‌شوند و هنگام نوشتن ‏record‏، این آدرس‌ها به ‏paddr‏ مطلق تبدیل می‌شوند. ‏DEVICE_ID_DELAYED‏ برای بلوک‌هایی است که جای آن‌ها تا لحظه‌ی ثبت با ‏ExtentPlacementManager‏ تعیین نشده است (نوشتن ‏out-of-line‏).

۳۰-۶-۲ ‏record‏ و دسته‌بندی در ‏journal‏#

pseudocode: دسته‌بندی journal (مدل مفهومی)
submit(record):
  if current_batch can fit record and batch.size < batch_capacity(16):
      current_batch.add(record)
  else: flush_current_batch(); current_batch.add(record)
  if outstanding_ios < iodepth_limit(5): flush_current_batch()      # دیسک بی‌کار است: صبر نکن
  else: wait (batch بزرگ‌تر می‌شود تا یکی از نوشتن‌ها تمام شود)
flush_current_batch():
  header = record_group_header_t{records=n, mdlength, dlength, segment_nonce,
                                 committed_to = آخرین نقطه‌ای که همه‌ی قبلی‌ها کامل‌اند,
                                 data_crc = crc(data)}
  write(header + metadata + data) as ONE aligned I/O

مثال عددی. فرض کنید ۴۰ تراکنش کوچک (هرکدام یک ‏delta‏ روی ‏onode‏ و ۴‏K‏ داده) هم‌زمان می‌رسند و دیسک هر نوشتن را در ۲۰ میکروثانیه کامل می‌کند. پنج ‏record‏ اول هرکدام به یک نوشتن جدا تبدیل می‌شوند، چون صف دیسک خالی است. پس از رسیدن به سقف ۵ نوشتن هم‌زمان، بقیه تا ۱۶ عدد در یک ‏batch‏ جمع می‌شوند. ۳۵ ‏record‏ باقی‌مانده در ۳ نوشتن (۱۶+۱۶+۳) ثبت می‌شوند. در مجموع ۸ نوشتن به‌جای ۴۰ انجام می‌شود و بیشترین تأخیر اضافه‌ی هر ‏record‏ کمتر از دو بار زمان یک نوشتن است. این همان مصالحه‌ی ‏group commit‏ در ‏kv_sync_thread‏ در ‏BlueStore‏ است، با این تفاوت که بدون ‏thread‏ جداگانه و فقط با ‏future‏ها پیاده شده است.

۳۰-۶-۳ حالت‌های یک ‏extent‏ در ‏cache‏#

نکته‌ی مهم این ماشین حالت کنترل هم‌روندی خوش‌بینانه است. هر تراکنش ‏extent‏هایی را که خوانده در ‏read_set‏ نگه می‌دارد. اگر تراکنش دیگری پیش از ‏commit‏ یکی از آن‌ها را تغییر دهد، ‏Cache::mark_transaction_conflicted‏ تراکنش اول را نامعتبر می‌کند و تراکنش باید از نو اجرا شود. مستند ‏SeaStore‏ یادآوری می‌کند که این سازوکار در بارهای نوشتن سنگین نرخ تکرار بالایی دارد و برای حذف آن برنامه‌ریزی شده است. این یکی از دلایل وضعیت «اولیه»ی ‏SeaStore‏ است.

۳۰-۷ ‏GC‏ سگمنت‌ها: انتخاب سگمنت قربانی#

در دستگاه ‏segmented‏، هر بایتی که نوشته می‌شود در نهایت باید با «تمیز کردن» یک سگمنت قدیمی جبران شود: داده‌ی زنده‌ی آن سگمنت به سگمنت تازه منتقل و سگمنت آزاد می‌شود. پرسش کلیدی این است که کدام سگمنت انتخاب شود.

pseudocode: get_next_reclaim_segment (خلاصه)
for each closed segment s:
   u = live_bytes(s) / segment_size                      # 0 ≤ u < 1
   score(s) = greedy:       1 - u
              cost_benefit: (1 - u) × age(s) / (2u)        # u=0 ⇒ +∞
              benefit:      ترکیب (1-u) با عامل سن نرمال‌شده
pick = argmax score;  greedy_pick = argmin u
if autotune and formula ≠ greedy and (1-u_greedy) ≥ ratio(2.0) × (1-u_pick):
   pick = greedy_pick                                     # فرمول سن‌محور اشتباه کرده است

فرمول ‏cost-benefit‏ همان فرمول کلاسیک سامانه‌های فایل ‏log-structured‏ (LFS) است. سود پاک کردن سگمنت متناسب با فضای آزادشده (۱-‏u‏) و «پایداری» آن (سن) است و هزینه‌اش خواندن ‏u‏ و نوشتن ‏u‏ (یعنی ۲‏u‏). سگمنت قدیمی با داده‌ی کم‌زنده بهترین گزینه است، چون داده‌ی باقی‌مانده‌اش احتمالاً «سرد» است و دوباره به این زودی نمی‌میرد.

مثال عددی. سه سگمنت بسته داریم:

فرمول ‏cost-benefit‏ سگمنت ‏C‏ را انتخاب می‌کند، چون بسیار قدیمی است. اما پاک کردن ‏C‏ فقط ۱۰٪ فضای آزاد به دست می‌دهد و باید ۹۰٪ آن را جابه‌جا کرد. ‏autotune‏ این را بررسی می‌کند: سهم آزاد ‏greedy‏ (۰.۸) دست‌کم ۲ برابر سهم آزاد انتخاب فرمول (۰.۱) است، پس انتخاب به ‏A‏ برمی‌گردد. اگر ‏C‏ در کار نبود، فرمول ‏B‏ را با امتیاز ۵۰۰ انتخاب می‌کرد. نسبت ۰.۸/۰.۵=۱.۶ کمتر از ۲ است، پس انتخاب فرمول حفظ می‌شد. این گزینه‌ها (‏seastore_segment_cleaner_gc_formula=cost_benefit‏، ‏seastore_segment_cleaner_gc_autotune=true‏ و ‏ratio=2.0‏) در ‏main‏ هستند و در ‏yaml‏ مربوط به ‏Squid‏ و ‏Tentacle‏ دیده نمی‌شوند.

استدلال ‏write amplification‏. اگر ‏cleaner‏ در حالت پایدار سگمنت‌هایی با میانگین ‏u=0.5‏ را پاک کند، برای هر ۱ بایت آزادشده ۱ بایت بازنویسی لازم است و ‏WA‏ حدود ۲ است. با ‏u=0.2‏، برای هر ۰.۸ بایت آزاد ۰.۲ بایت جابه‌جا می‌شود و ‏WA‏ حدود ۱.۲۵ است. پس رزرو فضای آزاد بیشتر روی دستگاه، ‏u‏ سگمنت‌های قربانی را پایین می‌آورد و هم عمر ‏NVMe‏ و هم تأخیر نوشتن را بهتر می‌کند.

۳۰-۸ سنجش و پایش ‏Crimson‏#

ceph tell osd.0 dump_metrics reactor_utilization     # بهره‌وری هر reactor (shard)
ceph tell osd.0 dump_store_shards                    # نگاشت PGها و store shardها به هسته‌ها
ceph config set osd crimson_prometheus_port_base 29180   # main: osd.N روی 29180+N
curl -s http://HOST:29180/metrics | grep osd_reactor_utilization
ceph osd dump | grep -E 'allow_crimson|crimson'          # پرچم‌های نقشه و pool

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

• در شاخه‌ی ‏main‏، مستند کاربری ‏Crimson‏ از ‏doc/dev/crimson/‏ به ‏doc/crimson/crimson.rst‏ منتقل شده و استقرار با ‏ceph orch apply osd --osd-type crimson‏ و برای ‏SeaStore‏ با ‏--objectstore seastore‏ شرح داده شده است. در ‏Squid‏ و ‏Tentacle‏ این فرمان‌ها در مستند نیستند.
• ‏crimson_cpu_num‏ پیش‌فرض ندارد و پس از استقرار تغییرپذیر نیست. مستند توصیه می‌کند آن را کمتر از ‏nproc‏ تقسیم بر تعداد ‏OSD‏های میزبان بگذارید.
• ‏io_uring backend‏ پیش‌فرض ‏reactor‏ است، اگر هسته اجازه دهد (‏kernel.io_uring_disabled‏). در برخی توزیع‌های محافظه‌کار باید آن را صریحاً فعال کرد.
• ‏SeaStore‏ برای ‏HDD‏ مناسب نیست (طبق مستند). ‏Crimson‏ برای ‏HDD‏ و ‏SSD‏های کند همچنان ‏BlueStore‏ را از راه ‏AlienStore‏ پشتیبانی می‌کند.

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

1. ۱. با ‏vstart‏ (‏MDS=0 MON=1 OSD=1 ../src/vstart.sh -n --crimson --crimson-smp 2‏) یک خوشه‌ی ‏Crimson‏ بسازید. ‏dump_metrics reactor_utilization‏ را پیش و پس از ‏rados bench‏ مقایسه کنید.
2. ۲. ‏CyanStore‏ را با ‏AlienStore+BlueStore‏ با یک بار ۴‏K‏ تصادفی مقایسه کنید. تفاوت تأخیر، هزینه‌ی ذخیره‌ساز است و تأخیر ‏CyanStore‏ سربار خود ‏OSD‏.
3. ۳. با چهار ‏PG‏ در ‏pool‏ و دو ‏reactor‏، با ‏dump_store_shards‏ نگاشت را ببینید و آن را با مثال این فصل مقایسه کنید.
4. ۴. سه سگمنت فرضی با ‏u‏ و سن دلخواه بسازید و امتیاز ‏greedy‏ و ‏cost-benefit‏ و نتیجه‌ی ‏autotune‏ را دستی حساب کنید.

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

1. ۱. چرا مدل ‏thread pool‏ در ‏OSD‏ کلاسیک روی ‏NVMe‏ هزینه‌بر است؟
2. ۲. ‏future‏ و ‏continuation‏ در ‏Seastar‏ چگونه جایگزین بلوکه شدن می‌شوند؟
3. ۳. ‏crimson_reactor_task_quota_ms‏ چه چیزی را محدود می‌کند و یک ‏continuation‏ طولانی چه اثری دارد؟
4. ۴. ‏PG‏ تازه چگونه به یک هسته نسبت داده می‌شود و این روش چه ضعفی دارد؟
5. ۵. تفاوت ‏phase‏های ‏exclusive‏ و ‏concurrent‏ را با مثال ‏WaitRepop‏ توضیح دهید.
6. ۶. ‏AlienStore‏ چرا لازم است و چه هزینه‌ای دارد؟
7. ۷. ‏laddr‏ و ‏paddr‏ در ‏SeaStore‏ چه تفاوتی دارند و چرا این جداسازی هزینه‌ی ‏GC‏ را کم می‌کند؟
8. ۸. ساختار ۶۴ بیتی ‏paddr_t‏ را برای ‏segment‏ و ‏RBM‏ شرح دهید.
9. ۹. فرمول ‏cost-benefit‏ را بنویسید و ‏autotune‏ را با مثال توضیح دهید.
10. ۱۰. سه پرچمی که برای فعال کردن ‏Crimson‏ لازم‌اند کدام‌اند؟

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

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

• ‏Crimson‏ در مستندات (‏main‏
  https://github.com/ceph/ceph/blob/main/doc/crimson/crimson.rst
• راهنمای توسعه‌دهنده‌ی ‏Crimson‏
  https://github.com/ceph/ceph/blob/main/doc/dev/crimson/index.rst
• طراحی ‏SeaStore‏
  https://github.com/ceph/ceph/blob/main/doc/dev/crimson/seastore.rst
• کد ‏Crimson‏
  https://github.com/ceph/ceph/tree/main/src/crimson
• گزینه‌های ‏Crimson‏
  https://github.com/ceph/ceph/blob/main/src/common/options/crimson.yaml.in
• ‏Seastar‏
  https://seastar.io/
• آموزش ‏Seastar‏
  https://github.com/scylladb/seastar/blob/master/doc/tutorial.md
• پروژه‌ی ‏Crimson‏ در وبلاگ ‏Ceph‏
  https://ceph.io/en/news/crimson/
• ‏Rosenblum‏ و ‏Ousterhout‏، ‏The Design and Implementation of a Log-Structured File System‏ (۱۹۹۲
  https://people.eecs.berkeley.edu/~brewer/cs262/LFS.pdf