شمارش با بو کشیدن: 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

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).

این پنل، تابمش عوض شده و به پنجشنبه ۱۸ دی تغییر کرد. اگه با روز و ساعتش مشکل داشتین، الان میتوانید ثبت نام کنید ✌️

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

https://interviewguide.dev/

پسرم برنامه‌نویس سیستمی لینوکسه، پسرش:

کامند معروف sudo یه فیچر بامزه داره. قضیه از این قراره که وقتی که شما پسورد رو اشتباه می‌زنید در حالت عادی میگه try again و اینا، ولی یه فیچر داره به اسم insults که می‌تونید فعالش کنید و به این صورت می‌تونه به هر کسی که پسورد sudo رو اشتباه زد متن توهین‌آمیز نشون بده.

هدفم از این، این نیست که بگم برید روشنش کنید چون که کاربرد خاصی نداره، ولی به نظرم یه تنظیم نسبتا بی‌خطره برای بازی کردن با تنظیمات sudo.

تو این آموزش هم در مورد اهمیت کاربر root و دستور sudo و هم این فیچر بخونید و هم آموزش تغییر دادن تنظیمات sudo رو با visudo ببینید.

https://www.techtarget.com/searchsecurity/tutorial/Use-sudo-insults-to-add-spice-to-incorrect-password-attempts


شاید بپرسید متن‌های اینا از کجا میاد؟ حتما یه جا توی سیستم منه؟ ولی خب خیر به شکل متنی در اختیارتون نیست. توی یه فایل .so قرار داره. با کامند strings می‌تونید رشته‌های داخلش رو از فایل باینری استخراح کنید (که خروجی به درد بخوری نمیده البته)
https://askubuntu.com/questions/837558/where-are-sudos-insults-stored

برای کار با io توی لینوکس از سیستم کال استفاده می‌کنیم. یه دسته از این سیستم‌کال ها io_uring نام دارن که به ما امکان پروسس async رو می‌دن. خلاصه‌ش به این شکله که دو تا صف حلقوی مشترک بین user space و kernel space داریم که توی یکی درخواست های io رو می‌نویسیم و نتیجه توی یک صف دیگه قرار می‌گیره.
نکته جالب اول اینه که میتونیم چند تا درخواست رو بنویسیم و بعد به kernel بگیم همه رو پردازش کن و یه حالت batching پیش میاد.
نکته جالب دوم اینه که میتونیم به کرنل بگیم که خودت به شکل polling صف درخواست‌ها رو بررسی کن و خودت کار رو شروع کن، بدون این که حتی نیاز باشه سیستم‌کال بزنیم. البته که برای همه‌ی برنامه‌ها می‌تونه مناسب نباشه چون پردازنده رو درگیر می‌کنه.

https://unixism.net/loti/what_is_io_uring.html

توسعه فیچر، سرعت رشد رو برای فیچر های آینده میگیره. این طبیعیه؟ بله. مطلوبه؟ قاعدتا نه.

پس چیکار کنیم؟ گاهی باید برگردیم عقب و ساختار کد رو درست کنیم.

https://tidyfirst.substack.com/p/why-does-development-slow

چرا در git، عملیات squash کردن بد است
و کمی در مورد نحوه کار git

https://dev.to/wesen/squash-commits-considered-harmful-ob1

چرا فیچرفلگ ها بد هستند و باید باهاشون چیکار کنیم؟

https://newsletter.manager.dev/p/feature-flags-are-ruining-your-codebase

این قسمت درس شبکه معمولا تو امتحان نمیاد، ولی شما اگه دوست داشتید بخونید
https://digiato.com/internet-network/from-ixp-to-bgp-internet-cuts

مستند "پریدن از روی دیوار آتش"

https://www.aparat.com/v/8s6Yy/

یکی از بهترین مطالبی که خوندم:
چطور کد جدید رو ببریم روی پروداکشن؟ چقدر تست کنیم؟ محیط تست داشته باشیم؟ برای همه کاربرها فعال کنیم یا برای تعداد کمی؟
اگه تجربه پروداکشن نداشتید یا فقط تو شرکت های سایز مشخص کار کردید (یا فقط کوچک یا فقط بزرگ) بهتون توصیه میکنم بخونید.

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

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

https://charity.wtf/2025/12/24/on-friday-deploys-sometimes-that-puppy-needs-murdering-xpost/


و در ادامه این مطلب:
https://www.linkedin.com/posts/michael-davis-7033548_friday-deploy-freezes-are-exactly-like-murdering-activity-7408181339444707328-8GjS

چه زمانی ریفکتور کنیم و چه زمانی بازنویسی کامل؟با یکسری مثال و ایده این مطلب بهتون کمک می‌کنه.

https://herbcaudill.com/words/20190219-rewrite-refactor-reinvent