حکایت شیخ و مریدان : Bloom Filter

مریدی «تگری زنان» نزد شیخ برفت و گفت یا شیخ حالم دریاب که بغایت رسید.
شیخ فرمود : مریدا تو را چه شده ؟

مرید گفت : یا شیخ چندی پیش استارتاپی زدیم در خصوص حمل و نقل درون قلعه با چهارپایان که نامش را خوش رکاب گذاشته ایم!

شیخ گفت : خب!؟؟نوش جان!چه شده که به ما رجوع کردی؟؟

مرید گفت : در این استارت آپ ما در بخش ثبت نام به کاربران اجازه میدهیم نام کاربری را برای خود انتخاب کنند!و یک Index و محدودیتUNIQUE هم زده ایم تنگش!

حال که میزان ثبت نام روزانه ما زیاد شده، از آن رو هم مردم ما به پاس چشم و هم چشمی به مانند تاریخ زایمان به دنبال نام های عجیب و خاص هستند و در بیکاری خود نشسته و یکی یکی نام ها را امتحان میکنند که لاکچری ترینشان را برای خودشان بردارند!
بگو خب!

شیخ گفت : خب!

مرید ادامه داد : حال این مرض مردم شهر برای ما دردسر شده!میزان IO دیتابیس بالا رفته و نرم افزار در حیاتی ترین جای خود کند عمل میکند!

شیخ گفت : خب حذفش کن!

مرید گفت : A/B تست کردیم 100 درصد نارضایتی خالص بدون حتی اندکی پالم!نمیشود!راه بده جان ما!

شیخ دستی به ریش خود کشید و گفت چیزی برتو گویم که خود نیز صبح شنبه فهمیدم!برای این مشکل الگوریتمی طراحی شده به نام BloomFilterحال بنشین تا از برایش روی منبر بروم!

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

اما به صورت ساده که مطلب را بیان کند ادامه میدهم فکر کن مثلا همین "کوپال" خودمان میخواهد در خوش رکاب ثبت نام کند!در مرحله اول نام شخص را هش کن!بعد باقیمانده آن را بر عددی بدست آور (مثلا 64) و تو عددی خواهی یافت بین 0 تا 63 و آن را در RAM یا Redis ذخیره کن!یا مثلا بیتی را یک کن!نمیدانم روشش با خودت!

سری بعد اگر شفتالو خانم آمد برای ثبت نام بعد از اجرای دستور بالا برو و در Redis نگاه کن و ببین آیا این عدد ثبت شده!یا یک شده است!اگر نبود که 100 درصد مطمئن باش که درست است و برو ثبت نام کن!
اگر بود حال دو راه می باشد!که یا ثبت نام شده و یا نشده، چرا چونکه شاید روزی نامی بعد از هش کردن و باقیمانده گرفتن عددش با یکی دیگر از نام های قبلی یکی شودو وقتی به Redis رجوع میکنی میبینی که هست! از این رو یا تو تصمیم میگیری که بروی و در دیتابیس هم چک کنی!و یا نه!برایتان صرفه ندارد و به شخص میگویی نامی دیگر انتخاب کن!خط القرآن که نیست!

این روش در بسیاری از سیستم های بزرگ استفاده میشود که در کل باعث کاهش IO به دیتابیس و کاهش هزینه میشود! برای مثال همین جیمیل مثلا اگر دقت کرده باشی بروی و نام "دست دراز 886" را بزنی میگوید این نام ثبت شده میخواهی "دراز دست 889" را امتحان کنی!؟خدا خیر داده اصلا حسش ندارد که به دیتابیس برود.

البته تصمیم استفاده از این روش با طراح سیستم است!

بعد از این سخن، مرید نعره‌ زد و خشتک درید
و لپ‌ تاپ‌ خود را به زمین کوبید
فغان کشان به کشتی مروارید سیاه پناه برد!!