شمارش با بوکشیدن - ساختمان‌داده‌ی HyperLogLog

نیاز بود تعداد کانتکت‌هایی که به یک اکانت مشخص پیام‌ میدن در یک بازه‌ی ۲۴ ساعته شمرده بشن.

اولین راه حل و بدیهی‌ترینش این بود که واقعا ارسال کننده‌ی پیام‌ها رو توی یک ست ذخیره کنیم. یعنی توی یک بازه‌ی ۲۴ ساعته هرچی پیام بعد از یک ایونت شروع کننده‌ی اون ۲۴ ساعت میومد رو دونه دونه برای هر اکانت بررسی کنیم. پیجیده نبود ولی خیلی جالب به نظر نمیومد به خصوص این که نیازی به شمارش دقیق نداشتیم و این یعنی کلی هدررفت حافظه.

برای این که توی فضای بهینه این مسئله رو حل می‌کردم خیلی زود به یک حدس اولیه رسیدیم: Bloom filter.

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

بلوم فیلتر خیلی جالبه ولی راه حل ما نبود. ما نیاز به شمردن داشتیم ولی بلوم فیلتر یک فیلتره(!) نه یک شمارنده. انگار هش‌تیبلیه که بدون این که همه‌ی داده‌ها رو ذخیره کنه بهت میتونه بگه کلیدت احتمالا هست یا قطعا نیست. پس باید یک شمارنده کنار بلوم فیلتر استفاده می‌کردیم که هروقت نبود یکی بهش اضافه بشه. عملا پیچیدگی پیاده‌سازی بدو ‌دلیل کافی بالا می‌رفت و برای همین باید می‌رفتیم سراغ یک روش دیگه.

تو این فکرا بودم و داشتم واسه یه مصاحبه سوال آماده می‌کردم که یهو یادم افتاد که من قبلا توی داکیومنت ردیس چشمم خورد به یک ساختمان داده‌ای که همون موقع برام خیلی جالب به‌نظر اومد: HyperLogLog. بعد بررسی مجدد به نظر میر‌سید که جوابمون همینه!

هایپرلاگ‌لاگ یا HLL یک ساختمان داده با پیچیدگی فضایی ثابت مبتنی بر احتمالاته که میتونه تعداد عناصر یکتا در یک مجموعه‌ رو (که بهش می‌گن Cardinality) بدون این که واقعا تعداد تکرار‌ها رو بشمره و یا داده‌ها رو ذخیره کنه با ضریب خطای زیر یک درصد (حدود ۰.۸٪) محاسبه کنه. (برای تعداد ۲ به توان ۱۴ رجیستر. به صورت کلی، نرخ خطا برای m رجیستر برابر است با ۱.۰۴ بر رادیکال m)

نحوه‌ی کارش هم به این شکله که به جای ذخیره یا شمردن مستقیم عنصر‌ها، هر ورودی رو ابتدا با یک تابع هش یکنواخت به یک مقدار باینری با طول ثابت تبدیل می‌کنه. بعد چند بیت ابتدایی این هش رو برای تعیین رجیستری (باکت) که داده بهش تعلق می‌گیره استفاده می‌کنه و روی بقیه‌ی بیت‌ها، تعداد صفرهای متوالی ابتدای رشته شمرده می‌شه.

از اونجایی که ظاهر شدن تعداد زیاد صفرهای متوالی در ابتدای یک عدد باینری در صورت استفاده از همچین تابع هشی یک رخداد کم احتمالیه، این مقدار می‌تونه به‌صورت آماری نماینده‌ای از بزرگی مجموعه‌ی عناصر یکتا باشه. یعنی چی؟

احتمال این که یک عدد باینری:

با ۱ صفر شروع بشه: P(0) = ۱/۲
با ۲ صفر متوالی شروع بشه (00): P(00) = ۱/۴
با ۳ صفر متوالی شروع بشه (000): P(000) = ۱/۸
با k صفر متوالی شروع بشه: P(00…0)= ۱/۲^k

یعنی به ازای هر صفر اضافه، احتمال نصف می‌شه.

در نتیجه دیدن عددی که مثلاً با ۱۰ صفر شروع بشه، احتمالی به برابر با ۱ به ۱۰۲۴ داره. اتفاقی که فقط وقتی حجم داده‌ها بزرگ باشه رخ می‌ده.

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

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

در همین راستا، و برای این که این روایت برای علاقه‌مندان ابتر نمونه، این بلاگ پست رو که آقای Salvatore Sanfilippo که از ایتالیایی‌های اهل دل و البته از توسعه‌دهندگان اصلی ردیس هستن رو به هیج‌وجه از دست ندین. بلاگ راجع‌به HLL و پیاده‌سازیش در ردیسه:

Redis new data structure: the HyperLogLog

HyperLogLog is remarkable as it provides a very good approximation of the cardinality of a set even using a very small amount of memory. In the Redis implementation it only uses 12kbytes per key to count with a standard error of 0.81%, and there is no limit to the number of items you can count, unless you approach 2^64 items (which seems quite unlikely).