Bloom Filter: بررسی عضویت در مجموعه‌های بزرگ با حافظه‌ی کم

در نوشته‌ی طراحی کوتاه‌کننده‌ی لینک دو بار سراغ Bloom filter رفتم: یک‌بار برای سبک کردن بررسی برخورد کدها و یک‌بار برای جلوگیری از cache penetration. هر دو بار از کنارش رد شدم، چون جای توضیحش آن‌جا نبود. این نوشته همان توضیح است.

شاید Bloom filter را از کتاب‌های ساختار داده یا آمادگی مصاحبه بشناسید. ولی دلیل اصلی شناختنش این است که بی‌سروصدا داخل ابزارهای روزمره نشسته است. Cassandra، RocksDB و HBase با آن از خواندن دیسک فرار می‌کنند و Redis و PostgreSQL نسخه‌ی آماده‌اش را دارند. تصمیم‌های طراحی دورش هم آن‌قدر ظریف‌اند که اگر درست گرفته نشوند، سیستم بی‌آن‌که خطایی بدهد اشتباه جواب می‌دهد.

مسئله: «این را قبلاً دیده‌ام؟»

فرض کنید میلیاردها کد کوتاه دارید و می‌خواهید قبل از رفتن سراغ دیتابیس بدانید یک کد وجود دارد یا نه. راه بدیهی نگه داشتن همه‌ی کدها در یک hash set است. برای این‌که حسی از هزینه‌اش داشته باشیم، یک میلیون کد ۷ کاراکتری را در یک Set در Node.js ریختم و حافظه را اندازه گرفتم. همان یک میلیون کد را هم در یک Bloom filter با نرخ خطای ۱ درصد گذاشتم:

یعنی بیش از ۳۵ برابر کمتر. نکته‌ی جالب‌تر این است که حافظه‌ی Bloom filter به اندازه‌ی خود عضوها بستگی ندارد. چه کد ۷ کاراکتری ذخیره کنید، چه URL دوکیلوبایتی، هزینه برای هر عضو همان چند بیت است. بهایش هم یک چیز است: Bloom filter گاهی اشتباه می‌کند، ولی فقط در یک جهت.

سازوکار

یک Bloom filter فقط دو چیز دارد: یک آرایه‌ی m بیتی که همه‌ی بیت‌هایش صفر شروع می‌شوند، و k تابع هش که هرکدام یک مقدار را به یکی از خانه‌های آرایه نگاشت می‌کنند.

افزودن: مقدار را با هر k تابع هش می‌کنیم و بیت هر k خانه را یک می‌کنیم.

بررسی: مقدار را با همان k تابع هش می‌کنیم و بیت‌ها را نگاه می‌کنیم. اگر حتی یکی صفر باشد، مقدار قطعاً اضافه نشده، چون افزودنش آن بیت را یک می‌کرد. اگر همه یک باشند، مقدار شاید اضافه شده. ممکن است هم این بیت‌ها را مقدارهای دیگر روشن کرده باشند.

همین عدم تقارن کل ماجراست. منفی کاذب (false negative) هرگز رخ نمی‌دهد و مثبت کاذب (false positive) با احتمالی که خودمان انتخاب می‌کنیم رخ می‌دهد. پس Bloom filter جایی مفید است که جواب «نه» رایج باشد و فهمیدنش از راه عادی گران. هر «نه» یک سفر به دیسک، شبکه یا دیتابیس را حذف می‌کند و هر «شاید» ما را به همان راه عادی برمی‌گرداند.

چقدر حافظه و چند تابع هش؟

اگر n عضو را در آرایه‌ای با m بیت و k تابع هش بگذاریم، احتمال مثبت کاذب تقریباً این است:

با کمی حساب، تعداد بهینه‌ی تابع‌های هش و تعداد بیت لازم برای هر عضو به دست می‌آید:

عدد این فرمول‌ها برای چند نرخ خطای رایج:

قاعده‌ی سرانگشتی‌اش این است که هر بار نرخ خطا را ده برابر کم کنید، حدود ۴٫۸ بیت به هر عضو اضافه می‌شود. برای بازی با اعداد، ماشین‌حساب hur.st ابزار خوبی است.

پیاده‌سازی

نیازی به k تابع هش مستقل نیست. کیرش و میتزنماخر نشان داده‌اند که با دو هش h1 و h2 و ترکیب h1 + i·h2، کارایی عملاً همان می‌ماند. این پیاده‌سازی کوچک TypeScript از همین ترفند استفاده می‌کند:

export class BloomFilter {
  private bits: Uint8Array;
  readonly m: number; // تعداد بیت‌ها
  readonly k: number; // تعداد تابع‌های هش

  constructor(expectedItems: number, falsePositiveRate: number) {
    this.m = Math.ceil((-expectedItems * Math.log(falsePositiveRate)) / Math.LN2 ** 2);
    this.k = Math.max(1, Math.round((this.m / expectedItems) * Math.LN2));
    this.bits = new Uint8Array(Math.ceil(this.m / 8));
  }

  add(item: string) {
    for (const i of this.indexes(item)) this.bits[i >> 3] |= 1 << (i & 7);
  }

  mightContain(item: string): boolean {
    for (const i of this.indexes(item)) {
      if ((this.bits[i >> 3] & (1 << (i & 7))) === 0) return false; // قطعاً نیست
    }
    return true; // شاید هست
  }

  private *indexes(item: string) {
    const h1 = fnv1a(item, 0x811c9dc5);
    const h2 = (fnv1a(item, 0x9747b28c) | 1) >>> 0; // فرد و بدون علامت
    for (let i = 0; i < this.k; i++) yield (h1 + i * h2) % this.m;
  }
}

function fnv1a(str: string, seed: number): number {
  let h = seed;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

(این نسخه برای آموزش است. i >> 3 فقط تا ۲ به توان ۳۱ بیت درست کار می‌کند، یعنی حدود ۲۵۶ مگابایت. برای فیلترهای بزرگ‌تر باید از Math.floor(i / 8) استفاده کنید یا فیلتر را به چند بلوک بشکنید.)

باگی که تست پیدا کرد

نسخه‌ی اول این کد را که نوشتم، یک تست ساده رویش اجرا کردم: یک میلیون کد اضافه کن و بعد همه را دوباره بپرس. Bloom filter درست هیچ‌وقت منفی کاذب ندارد، پس جواب همه‌ی این پرسش‌ها باید «شاید هست» باشد. نتیجه این بود که حدود ۴۲ درصد کدهایی که همین الان اضافه کرده بودم، «قطعاً نیست» جواب گرفتند.

مقصر یک کاراکتر بود. در نسخه‌ی اول نوشته بودم fnv1a(...) | 1 تا h2 فرد شود. عملگرهای بیتی جاوااسکریپت خروجی را به عدد صحیح ۳۲ بیتی علامت‌دار تبدیل می‌کنند، پس برای نیمی از ورودی‌ها h2 منفی می‌شد. اندیس هم منفی می‌شد و Uint8Array نوشتن در اندیس منفی را بی‌صدا نادیده می‌گیرد. هیچ خطایی نبود؛ فقط بیت‌ها هیچ‌وقت روشن نمی‌شدند. >>> 0 در کد بالا همین را درست می‌کند.

درس این ماجرا برای هر ساختار داده‌ی احتمالاتی یک چیز است: ویژگی‌ای را تست کنید که باید همیشه برقرار باشد، نه فقط این‌که «چند جواب درست داد». نتیجه‌ی نسخه‌ی اصلاح‌شده روی یک میلیون کد عضو و یک میلیون کد غیرعضو:

محدودیت‌ها

حذف ممکن نیست. نمی‌شود بیت‌های یک عضو را صفر کرد، چون ممکن است همان بیت‌ها مال عضوهای دیگر هم باشند. اگر حذف لازم است، Counting Bloom filter به‌جای هر بیت یک شمارنده‌ی کوچک (معمولاً ۴ بیتی) نگه می‌دارد و حافظه را حدود ۴ برابر می‌کند. Cuckoo filter هم حذف را پشتیبانی می‌کند و در نرخ‌های خطای پایین معمولاً حافظه‌ی کمتری می‌خواهد.

اندازه را از قبل باید بدانید. فیلتر برای n عضو ساخته می‌شود. اگر بیشتر از آن در آن بریزید، خطا نمی‌دهد، ولی نرخ مثبت کاذب سریع بالا می‌رود:

هر دو عدد را هم با فرمول حساب کردم و هم با همان پیاده‌سازی اندازه گرفتم. نسخه‌ی مقیاس‌پذیر (Scalable Bloom filter) با پر شدن هر لایه یک لایه‌ی جدید و بزرگ‌تر اضافه می‌کند. BF.RESERVE در Redis هم به‌طور پیش‌فرض همین کار را می‌کند.

فهرست عضوها را نمی‌دهد. فقط به «هست یا نیست» جواب می‌دهد. برای بازسازی فیلتر، مثلاً بعد از تغییر اندازه، به منبع اصلی داده نیاز دارید.

ورودی‌های مهاجم. اگر تابع هش شناخته‌شده و بدون کلید باشد و ورودی را کاربر تعیین کند، مهاجم می‌تواند مقدارهایی بسازد که همه به بیت‌های روشن بخورند و نرخ مثبت کاذب را بالا ببرد. اگر ورودی از بیرون می‌آید، از هش کلیددار مثل SipHash¹ با کلید مخفی استفاده کنید.

دسترسی پراکنده به حافظه. هر پرسش k خانه‌ی تصادفی از آرایه را می‌خواند و برای فیلترهای بزرگ یعنی چند cache miss². به همین دلیل RocksDB در فرمت جدید فیلترش همه‌ی بیت‌های هر کلید را داخل یک cache line نگه می‌دارد.

کجا به کار رفته

• دیتابیس‌های مبتنی بر LSM-tree³ مثل Cassandra، HBase، RocksDB و LevelDB. داده در چند فایل مرتب و تغییرناپذیر (SSTable⁴) ذخیره می‌شود و خواندن یک کلید ممکن است نیاز به نگاه کردن به چند فایل داشته باشد. هر فایل یک Bloom filter دارد و فایل‌هایی که فیلترشان «نه» می‌گوید، اصلاً از دیسک خوانده نمی‌شوند. در Cassandra نرخ خطای این فیلترها با تنظیم bloom_filter_fp_chance برای هر جدول قابل تغییر است.
• CDN و کش‌کردن فقط بعد از درخواست دوم. مهندس‌های Akamai گزارش کرده‌اند که حدود سه‌چهارم اشیایی که درخواست می‌شوند، فقط یک‌بار درخواست می‌شوند. کش کردن این‌ها فقط فضای دیسک را هدر می‌دهد. راه‌حلشان این بود که هر شیء فقط وقتی کش شود که Bloom filter بگوید قبلاً یک‌بار دیده شده.
• Redis با ماژول Bloom (که در نسخه‌های جدید جزو خود Redis است) دستورهای آماده دارد:

BF.RESERVE short_codes 0.01 10000000   # نرخ خطا و ظرفیت
BF.ADD short_codes aZ3kP9x
BF.EXISTS short_codes aZ3kP9x          # 1 = شاید هست
BF.EXISTS short_codes k7Qp01x          # 0 = قطعاً نیست

• PostgreSQL افزونه‌ای به نام bloom دارد که یک نوع ایندکس Bloom برای جست‌وجوی برابری روی ترکیب‌های دلخواه از چند ستون می‌سازد، وقتی ساختن یک ایندکس B-tree برای هر ترکیب صرف نمی‌کند.

برگردیم به کوتاه‌کننده‌ی لینک

در آن طراحی دو جا برای Bloom filter بود. ظاهرشان شبیه است، ولی اهمیت منفی کاذب در آن‌ها کاملاً فرق می‌کند.

کاربرد اول: بررسی برخورد در رویکرد هش. قبل از درج یک کد، از فیلتر می‌پرسیم. اگر گفت «نه»، کد را مستقیم با INSERT ... ON CONFLICT درج می‌کنیم و SELECT اضافه را حذف می‌کنیم. اگر گفت «شاید»، همان مسیر عادی را می‌رویم. این‌جا فیلتر فقط یک بهینه‌سازی است و منبع حقیقت همچنان قید یکتایی دیتابیس است. اگر فیلتر اشتباه کند، فقط یک رفت‌وبرگشت اضافه داریم. لینک‌های منقضی‌شده هم بیت‌هایشان را روشن نگه می‌دارند، یعنی نرخ مثبت کاذب به‌مرور بالا می‌رود ولی منفی کاذب ایجاد نمی‌شود. کافی است فیلتر را هر از گاهی از روی دیتابیس از نو بسازید.

کاربرد دوم: جلوگیری از cache penetration. این‌جا فیلتر همه‌ی کدهای موجود را نگه می‌دارد و اگر گفت «نه»، بدون رفتن به دیتابیس 404 برمی‌گردانیم. حالا منفی کاذب یعنی یک لینک سالم 404 بدهد، و این سناریو از چیزی که فکر می‌کنید محتمل‌تر است:

• فیلتر محلی در هر سرور. اگر ده سرور اپلیکیشن دارید و هرکدام فیلتر خودش را در حافظه نگه دارد، لینکی که سرور A ساخته، در فیلتر سرور B نیست. کاربری که درخواستش به B برسد، 404 می‌گیرد. تضمین «منفی کاذب ندارد» فقط وقتی برقرار است که هر درج به همان فیلتری برسد که از آن می‌پرسید. راه‌حل یک فیلتر مشترک است، مثلاً در Redis، یا این‌که هر سرور درج‌ها را از یک صف مشترک بخواند.
• ترتیب نوشتن. کد باید قبل از این‌که لینک کوتاه به کاربر برگردانده شود در فیلتر نوشته شده باشد، نه در یک job ناهمگام که چند ثانیه بعد اجرا می‌شود.
• ری‌استارت. فیلتری که فقط در حافظه است، با ری‌استارت خالی می‌شود و تا بازسازی نشده، به همه‌چیز «نه» می‌گوید. سرور یا باید قبل از پذیرفتن ترافیک فیلتر را از snapshot یا دیتابیس بازسازی کند، یا تا آن موقع فیلتر را دور بزند.

به نظر من این بخش همان‌جایی است که شناختن Bloom filter در سطح ارشد با شناختنش در سطح کتاب فرق می‌کند. سازوکارش را در ده دقیقه می‌شود یاد گرفت. سخت این است که تشخیص دهید تضمین‌هایش در یک سیستم توزیع‌شده کجا بی‌صدا می‌شکند.

جایگزین‌ها

در مصاحبه

اگر در مصاحبه Bloom filter را پیشنهاد می‌کنید، به همین چند سؤال جواب بدهید، قبل از این‌که مصاحبه‌کننده بپرسد:

1. چه چیزی را صرفه‌جویی می‌کند؟ کدام سفر به دیسک یا شبکه با جواب «نه» حذف می‌شود و این «نه» چقدر رایج است؟
2. نرخ خطا و حافظه چقدر است؟ یک عدد بدهید، مثلاً «۱٪، یعنی حدود ۱۰ بیت برای هر عضو».
3. مثبت کاذب چه هزینه‌ای دارد؟ معمولاً فقط یک رفت‌وبرگشت اضافه به منبع اصلی.
4. فیلتر کجا زندگی می‌کند و چطور به‌روز می‌ماند؟ با چند سرور، ری‌استارت، حذف و رشد داده چه می‌شود؟

جواب چهارم معمولاً همان چیزی است که یک طراحی خوب را از یک جواب حفظی جدا می‌کند.

منابع

• Burton H. Bloom، Space/Time Trade-offs in Hash Coding with Allowable Errors، مقاله‌ی اصلی، ۱۹۷۰.
• Adam Kirsch و Michael Mitzenmacher، Less Hashing, Same Performance: Building a Better Bloom Filter.
• Bin Fan و همکاران، Cuckoo Filter: Practically Better Than Bloom.
• Thomas Mueller Graf و Daniel Lemire، Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters.
• Bruce Maggs و Ramesh Sitaraman، Algorithmic Nuggets in Content Delivery، تجربه‌ی Akamai.
• RocksDB Wiki: RocksDB Bloom Filter
• Apache Cassandra: Bloom Filters
• Redis: Bloom filter
• PostgreSQL: bloom
• ماشین‌حساب اندازه‌ی Bloom filter در hur.st