وقتی شمارش دقیق خیلی گرون میشه: HyperLogLog 🔢
وقتی با داده‌های بزرگ سروکار داریم، خیلی وقت‌ها لازم داریم بدانیم:
✅چند کاربر یکتا در سایت بوده‌اند؟
✅چند IP مختلف به API ما وصل شده‌اند؟
✅چند محصول متفاوت در یک بازه دیده شده؟
💡 راه ساده این است که همه شناسه‌ها را نگه داریم و آخرش بشماریم.
اما در دیتابیس‌های توزیع‌شده، این یعنی انفجار حافظه و فشار شدید روی شبکه.
برای همین سراغ ساختارهای داده‌ی «تقریبی» می‌رویم که با مصرف کم حافظه، جواب نزدیک به درست بدهند. یکی از معروف‌ترین‌ها: #HyperLogLog.
🎲 مثال با تاس: رخدادهای نادر
فرض کن کسی مدام تاس می‌ریزد. تو نمی‌دانی چند بار تاس انداخته، فقط نتایج را می‌بینی.
🔹 اگه فقط یک بار ۶ آمد → عادی است.
🔹 اگه دو بار پشت سر هم ۶ آمد → کمی نادرتر.
🔹 اگه چهار بار پشت سر هم ۶ آمد → خیلی خیلی نادر.
این رخدادهای نادر سرنخ خوبی هستند. وقتی چیزی خیلی نادر دیدی، می‌توانی حدس بزنی که احتمالا تعداد دفعات تاس انداختن خیلی زیاد بوده است.
🔑 ارتباط با #HyperLogLog
حالا این ایده را می‌بریم به دنیای هش:
📌هر آیتم (مثل IP یا UserID) را هش می‌کنیم → یک رشته‌ی طولانی صفر و یک.
📌به ابتدای این رشته نگاه می‌کنیم: چند صفر پشت سر هم آمده؟
📌هرچه صفرهای بیشتری پشت سر هم باشد، اتفاق نادرتر است → پس احتمالاً داده‌های یکتای زیادی وارد شده‌اند.
📌در نسخه‌ی ساده‌ی الگوریتم، همیشه بیشترین تعداد صفر دیده‌شده را نگه می‌داریم.
مثلاً اگر حداکثر ۶ صفر دیده‌ایم، می‌گوییم:
تقریباً 6^2 = 64 آیتم یکتا داشته‌ایم. (بر اساس فرمول‌های آماری)
🚨 ایراد نسخه‌ی ساده
این روش یک اشکال بزرگ دارد:
اگر همان اوّل کار شانسی هشی بیاید با ۲۰ صفر پشت سر هم، الگوریتم می‌گوید: «اینجا باید حدود یک میلیون آیتم یکتا دیده شده باشد!»
در حالی که شاید فقط ۱۰ آیتم وارد شده‌اند.
مثل این است که دفعه‌ی اوّل ۴ تا شش پشت سر هم بیاید و ما فکر کنیم هزار بار تاس ریخته‌ایم!
🪣 راه‌حل: باکتینگ
برای حل این مشکل، #HyperLogLog واقعی از باکت‌ها استفاده می‌کند:
🎯چند بیت اول هش → تعیین می‌کند آیتم در کدام باکت قرار بگیرد.
🎯بقیه بیت‌ها → برای شمردن تعداد صفرهای ابتدای رشته استفاده می‌شود.
🎯در هر باکت، فقط «بیشترین تعداد صفر» ذخیره می‌شود.
🎯در پایان، الگوریتم همه باکت‌ها را با هم ترکیب می‌کند (با میانگین هارمونیک + اصلاح خطا).
به این ترتیب، یک رخداد نادر شانسی نمی‌تواند کل تخمین را خراب کند.
🏗 کجاها استفاده می‌شود؟
الگوریتم شمارش #HyperLogLog امروز در خیلی از دیتابیس‌ها و ابزارهای بزرگ به‌کار می‌رود:
🧩ردیس → دستورات PFADD و PFCOUNT برای شمارش یکتاها
🧩بیگ‌کوئری→ پشت APPROX_COUNT_DISTINCT
🧩ترینو/Presto و #ClickHouse → توابع شمارش تقریبی
🧩اسپارک و #Snowflake → در approx_count_distinct
🧩و حتی سیستم‌هایی مثل Cassandra / ScyllaDB که برای کم کردن بار IO از ساختارهای مشابه استفاده می‌کنند
✨ خلاصه اینکه:
الگوریتم HyperLogLog به‌جای شمردن دقیق، «حدس تقریبی اما پایدار» می‌زند؛ و همین باعث شده در مقیاس وب و دیتای عظیم، تبدیل به یک ابزار استاندارد شود.
کانال مدرسه مهندسی داده سپهرام: @sepahram_school
وقتی با داده‌های بزرگ سروکار داریم، خیلی وقت‌ها لازم داریم بدانیم:
✅چند کاربر یکتا در سایت بوده‌اند؟
✅چند IP مختلف به API ما وصل شده‌اند؟
✅چند محصول متفاوت در یک بازه دیده شده؟
💡 راه ساده این است که همه شناسه‌ها را نگه داریم و آخرش بشماریم.
اما در دیتابیس‌های توزیع‌شده، این یعنی انفجار حافظه و فشار شدید روی شبکه.
برای همین سراغ ساختارهای داده‌ی «تقریبی» می‌رویم که با مصرف کم حافظه، جواب نزدیک به درست بدهند. یکی از معروف‌ترین‌ها: #HyperLogLog.
🎲 مثال با تاس: رخدادهای نادر
فرض کن کسی مدام تاس می‌ریزد. تو نمی‌دانی چند بار تاس انداخته، فقط نتایج را می‌بینی.
🔹 اگه فقط یک بار ۶ آمد → عادی است.
🔹 اگه دو بار پشت سر هم ۶ آمد → کمی نادرتر.
🔹 اگه چهار بار پشت سر هم ۶ آمد → خیلی خیلی نادر.
این رخدادهای نادر سرنخ خوبی هستند. وقتی چیزی خیلی نادر دیدی، می‌توانی حدس بزنی که احتمالا تعداد دفعات تاس انداختن خیلی زیاد بوده است.
🔑 ارتباط با #HyperLogLog
حالا این ایده را می‌بریم به دنیای هش:
📌هر آیتم (مثل IP یا UserID) را هش می‌کنیم → یک رشته‌ی طولانی صفر و یک.
📌به ابتدای این رشته نگاه می‌کنیم: چند صفر پشت سر هم آمده؟
📌هرچه صفرهای بیشتری پشت سر هم باشد، اتفاق نادرتر است → پس احتمالاً داده‌های یکتای زیادی وارد شده‌اند.
📌در نسخه‌ی ساده‌ی الگوریتم، همیشه بیشترین تعداد صفر دیده‌شده را نگه می‌داریم.
مثلاً اگر حداکثر ۶ صفر دیده‌ایم، می‌گوییم:
تقریباً 6^2 = 64 آیتم یکتا داشته‌ایم. (بر اساس فرمول‌های آماری)
🚨 ایراد نسخه‌ی ساده
این روش یک اشکال بزرگ دارد:
اگر همان اوّل کار شانسی هشی بیاید با ۲۰ صفر پشت سر هم، الگوریتم می‌گوید: «اینجا باید حدود یک میلیون آیتم یکتا دیده شده باشد!»
در حالی که شاید فقط ۱۰ آیتم وارد شده‌اند.
مثل این است که دفعه‌ی اوّل ۴ تا شش پشت سر هم بیاید و ما فکر کنیم هزار بار تاس ریخته‌ایم!
🪣 راه‌حل: باکتینگ
برای حل این مشکل، #HyperLogLog واقعی از باکت‌ها استفاده می‌کند:
🎯چند بیت اول هش → تعیین می‌کند آیتم در کدام باکت قرار بگیرد.
🎯بقیه بیت‌ها → برای شمردن تعداد صفرهای ابتدای رشته استفاده می‌شود.
🎯در هر باکت، فقط «بیشترین تعداد صفر» ذخیره می‌شود.
🎯در پایان، الگوریتم همه باکت‌ها را با هم ترکیب می‌کند (با میانگین هارمونیک + اصلاح خطا).
به این ترتیب، یک رخداد نادر شانسی نمی‌تواند کل تخمین را خراب کند.
🏗 کجاها استفاده می‌شود؟
الگوریتم شمارش #HyperLogLog امروز در خیلی از دیتابیس‌ها و ابزارهای بزرگ به‌کار می‌رود:
🧩ردیس → دستورات PFADD و PFCOUNT برای شمارش یکتاها
🧩بیگ‌کوئری→ پشت APPROX_COUNT_DISTINCT
🧩ترینو/Presto و #ClickHouse → توابع شمارش تقریبی
🧩اسپارک و #Snowflake → در approx_count_distinct
🧩و حتی سیستم‌هایی مثل Cassandra / ScyllaDB که برای کم کردن بار IO از ساختارهای مشابه استفاده می‌کنند
✨ خلاصه اینکه:
الگوریتم HyperLogLog به‌جای شمردن دقیق، «حدس تقریبی اما پایدار» می‌زند؛ و همین باعث شده در مقیاس وب و دیتای عظیم، تبدیل به یک ابزار استاندارد شود.
کانال مدرسه مهندسی داده سپهرام: @sepahram_school
👌4❤1🔥1