فیلترهای بلوم و ارتباط آن با جدول وب گوگل، آپاچی کاساندرا

به گزارش reportaj.me و به نقل از linkedin فیلترهای بلوم به یک استاندارد در سیستم های تولیدی تبدیل شده اند که مجموعه داده های بزرگ تری را پردازش می کنند. استفاده گسترده از آنها، به ویژه در پایگاه های داده توزیع شده، ناشی از اثربخشی آنها در موارد استفاده است که در آن ما به یک عملکرد جدول هش برای جستجو و درج سریع نیاز داریم، اما لوکس فضا را ندارند. آنها در دهه ۱۹۷۰ توسط برتون بلوم اختراع شدند. اما در دهه گذشته زمانی که نیاز به سیستم‌های کارآمد فضایی افزایش یافت، به لطف رونق مجموعه داده‌های بزرگ، در واقع شکوفا شد.

یک راه ساده برای فکر کردن در مورد فیلترهای بلوم این است که آنها از درج و جستجو به همان روشی که جداول هش انجام می‌دهند، پشتیبانی می‌کنند، اما با استفاده از فضای بسیار کم، یعنی ۱ بایت در هر مورد یا کمتر. زمانی که کلیدها ۴ تا ۸ بایت اشغال می کنند، این صرفه جویی قابل توجهی است. Bloom Filers خود مورد را ذخیره نمی کند و بنابراین می تواند کارایی را در RAM بارگذاری کند، اما در نتیجه نرخ خطای کوچکی نیز نشان می دهد که مجموعه ای از موارد مثبت کاذب است.

توجه داشته باشید که فیلترهای بلوم دارای مثبت کاذب هستند اما منفی کاذب ندارند.

بنابراین، به زبان ساده، وقتی فیلتر بلوم گزارش می‌دهد که یک آیتم “در حال حاضر” است، احتمال کمی وجود دارد که آیتم ممکن است در شی ساختار داده وجود نداشته باشد، اما وقتی آن مورد را به عنوان “موجود نیست/ یافت نشد” گزارش می‌کند، قطعا وجود ندارد بنابراین، در موقعیت‌هایی که انتظار می‌رود پاسخ پرس و جو در اکثر مواقع وجود نداشته باشد، فیلترهای Bloom دقت بسیار خوبی به همراه مزایای صرفه‌جویی در فضا ارائه می‌دهند.

چگونه از فیلترهای بلوم در WebTable Google و Apache Cassandra استفاده می شود

WebTable گوگل و آپاچی کاساندرا از جمله پرکاربردترین سیستم های ذخیره سازی توزیع شده برای انتقال داده های عظیم هستند. بنابراین، بسیار جالب خواهد بود که به نحوه استفاده از فیلترهای شکوفه توسط این سیستم ها نگاهی بیاندازیم.

یعنی، این سیستم ها داده های خود را در تعدادی جداول به نام جداول رشته ای مرتب شده (SST) سازماندهی می کنند که روی دیسک قرار دارند و به صورت نقشه های کلید-مقدار ساختار یافته اند (یک کلید ممکن است URL باشد و یک مقدار ممکن است ویژگی ها یا محتویات وب سایت باشد. مثال.). Cassandra و WebTable به طور همزمان اضافه کردن محتوای جدید به جداول و پاسخ دادن به پرس و جوها را انجام می دهند، و هنگامی که یک پرس و جو وارد می شود، مهم است که SST حاوی محتوای درخواست شده را بدون پرس و جوی صریح در هر جدول تعیین کنید. بنابراین، برای انجام این کار، فیلترهای Bloom اختصاصی در RAM نگهداری می شوند، یکی در هر SST، تا پرس و جو را به جدول صحیح هدایت کنند.

بنابراین، فرض کنید اگر به ما ۵۰ SST ذخیره شده در دیسکی داده شود که دارای ۵۰ فیلتر شکوفه نقشه برداری شده در RAM بارگذاری شده است، برای یک SST به محض اینکه فیلتر bloom مورد را به عنوان “Not Found” در جستجو گزارش کند، پرس و جو مسیریابی می شود. به فیلتر شکوفایی بعدی مرتبط با SST بعدی.

و اولین بار که فیلتر Bloom مورد را به عنوان “Present” در یک SST گزارش می دهد، به دیسک می رویم تا بررسی کنیم که آیا آیتم در جدول وجود دارد یا خیر. در صورت جست‌وجوی مثبت نادرست، به مسیریابی پرس و جو ادامه می‌دهیم تا زمانی که فیلتر Bloom دوباره Present را گزارش کند و این بار داده‌ها نیز روی دیسک پیدا شوند. اگر این مورد اتفاق بیفتد، داده ها به کاربر برگردانده می شود، در غیر این صورت مسیریابی تا پایان SST ادامه می یابد.

به طور مشابه، فیلترهای بلوم زمانی که به صورت استراتژیک در سیستم‌های پر مصرف قرار می‌گیرند بسیار مفید هستند. برای مثال، داشتن یک برنامه SSD/دیسک خواندن/نوشتن می‌تواند به راحتی توان عملیاتی یک برنامه را از صدها هزار عملیات در ثانیه به چند هزار یا حتی چند صد عملیات در ثانیه کاهش دهد. در عوض، اگر فیلتر Bloom را در RAM قرار دهیم تا به جستجوها سرویس دهد، می‌توانیم از این افت عملکرد جلوگیری کنیم و به طور مداوم توان عملیاتی بالایی را در اجزای مختلف یک برنامه حفظ کنیم.