بررسی ساختار داده One Hash Bloom Filters و بهینه‌سازی‌های آن در معماری Bluesky

مقدمه و زمینه

بلوم فیلتر (Bloom Filter) یک ساختمان داده احتمالی است که به کمک آن می‌توانید به این پرسش که «آیا کلید X در این مجموعه وجود دارد یا خیر؟» با دو پاسخ «قطعاً خیر» یا «احتمالاً بله» پاسخ دهید. این ساختار از حافظه بسیار کمی استفاده می‌کند و از نظر پردازشی بسیار ارزان است. به همین دلیل، پایگاه‌های داده و سیستم‌های مقیاس‌پذیر بزرگ مانند بک‌اند شبکه اجتماعی Bluesky برای بررسی مواردی مثل مسدودسازی‌ها (Blocks) و سکوت‌ها (Mutes) پیش از مراجعه به دیسک یا دیتابیس از آن استفاده گسترده‌ای می‌کنند.

نحوه کارکرد سنتی و چالش‌های آن

در یک بلوم فیلتر استاندارد، ما یک آرایه بیتی و k تابع هش داریم. برای افزودن یا بررسی یک کلید، باید آن را k بار هش کنیم که این محاسبه می‌تواند برای سیستم‌های بسیار پربازده هزینه بر باشد. برای حل این مشکل، در سال ۲۰۰۸ مقاله‌ای منتشر شد که نشان می‌داد می‌توان با استفاده از دو هش (hash_1 + i*hash_2) به همان خروجی رسید. کتابخانه محبوب bits-and-blooms/bloom در زبان Go از همین روش استفاده می‌کند.

با این حال، در مقیاس Bluesky، مشکل اصلی تعداد توابع هش نبود؛ بلکه سربار ناشی از قفل‌ها (Mutex) بود. کتابخانه یادشده به صورت پیش‌فرض ایمن در برابر همزمانی (Thread-Safe) نبود و استفاده از Mutex باعث ایجاد گلوگاه و طول کشیدن فرآیند دیپلوی تا ۹۰ دقیقه شد. تیم مهندسی با جایگزینی دستورات اتمی پردازنده (Atomic Instructions)، این زمان را به ۱۵ دقیقه کاهش دادند.

بلوم فیلتر تک‌هش (One Hash Bloom Filters)

با الهام از پژوهش‌های جدید (از جمله مقاله‌ای از Lu و همکاران)، امکان ساخت بلوم فیلترها تنها با یک هش فراهم شده است. مکانیسم کلی این روش به شرح زیر است:

• آرایه بیتی بزرگ به k بخش با اندازه‌های متفاوت تقسیم می‌شود.
• تمامی این اندازه‌ها نسبت به هم اول (Coprime) هستند (هیچ عامل مشترک بزرگی غیر از ۱ ندارند).
• کلید داده‌شده تنها یک بار هش می‌شود.
• موقعیت بیت در هر بخش با استفاده از باقی‌مانده تقسیم مقدار هش بر اندازه آن بخش (hash % size_p) به دست می‌آید.

بر اساس این الگو، کتابخانه gloom در زبان Go توسعه داده شد که اکنون ماه‌هاست در سرویس‌های پربار Bluesky عملیاتی است.

بهینه‌سازی‌های سطح پایین (Low-Level)

در این پیاده‌سازی نکات مهندسی جالبی برای گرفتن حداکثر کارایی از سخت‌افزار به کار رفته است:

• تراز کردن کش خطی (Cache Line Alignment): فیلتر به بلوک‌های ۶۴ بایتی متناسب با اندازه خط کش پردازنده تقسیم می‌شود و با استفاده از پکیج unsafe در Go، تراز بودن حافظه تضمین می‌گردد تا در بدترین حالت، جستجو تنها یک Cache Miss داشته باشد.
• بهینه‌سازی ریاضی: استفاده از دستورالعمل ضرب (MUL) به جای عملگر سنگین تقسیم (Modulo) برای انتخاب بلوک‌ها.
• استفاده از ShardedAtomicFilter: برای جلوگیری از رقابت هسته‌های مختلف پردازنده روی داده‌های مشترک در سرورهای Bare-Metal.

دیدگاه جامعه توسعه‌دهندگان (Hacker News)

بحث‌های شکل‌گرفته در هکرنیوز نکات تکمیلی خوبی داشتند:

• برخی متخصصان اشاره کردند که می‌توان با توان‌های ۲ و مخلوط کردن ملایم مقادیر هش نیز به نتایج مشابهی رسید.
• منتقدان یادآور شدند که پارتیشن‌بندی در بلوم فیلترهای تک‌هش ممکن است کارایی فضا را کمی کاهش دهد، زیرا نرخ اشغال در بخش‌های مختلف نامتوازن می‌شود.
• در مجموع، این بهینه‌سازی به عنوان یک الگوی جذاب برای مهندسی سطح پایین و کاهش هزینه‌های زیرساختی تحسین شد.