iyashar/bloom-filter-descr

Bloom-filter-Descr

فیلترهای Bloom به عنوان مثال بلوم فیلتر در سال ۱۹۷۰ به وسیله آقای بولوم ارائه شد. فیلتر بولوم یک ساختار داده است که طراحی شده تا با سرعت و بدون فشار بر حافظه به ما بگوید که آیا عنصری در یک مجموعه وجود دارد یا خیر. آنچه به ازای این کارایی از دست می دهیم این است فیلتر بولوم یک ساختار داده احتمالی است: یعنی به ما می گوید که این عنصر یا قطعاً در مجموعه نیست یا ممکن است در مجموعه باشد. ساختار داده پایه Bloom فیلتر یک وکتور بیت است. تصویر زیر را در نظر بگیرید: هر سلول خالی در این جدول معادل یک بیت است و هر شماره ایندکس آن بیت.

کاساندرا برای خواندن اطلاعات، داده های روی دیسک و حافظه را ترکیب می نماید. برای جلوگیری از کنترل تک تک فایل های داده روی هارد که زمان زیادی را می طلبد، کاساندارا از ساختاری تحت عنوان بلوم فیلتر استفاده می کند. بلوم فیلتر یک ساختار داده احتمالی است که به کاساندرا اجازه می دهد یکی از وضعیت های ممکن را بیابد: دیتا قطعا در فایل نیست یا دیتا احتمالا در فایل هست. با استفاده از فیلتر Bloom سرعت نوشتن دیسک ها تقریباً به نصف کاهش یافته و باعث کاهش بار دیسک ها و افزایش عملکرد بالقوه دیسک می شود.