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

دیروز نسخه جدید گولنگ بعد از ۶ ماه معرفی شد. نسخه 1.26.0 هم امکانات جدیدی داره هم بهبودهای پرفورمنسی خوبی داشته.

اول از همه، زباله‌روب (Garbage Collector) جدیدی که قبل‌تر معرفی شده بود، الان به طور پیش‌فرض فعاله و انتظار می‌ره که باعث بهبود پرفورمنس در اکثر workloadها بشه، البته که اگر دوستش نداشتید میتونید با یه متغیر محیطی غیرفعالش کنید.
نکته‌ی جالب برای من اینه که بعد از گذشت ۱۰ سال هنوز هم یکی از ویژگی‌های اساسی زبون بهبود پیدا می‌کنه و روی بازدهیش کار می‌شه.

بهبود های پرفورمنسی البته به همین خلاصه نمیشه و روی صدا زدن توابعی که با C نوشته شده (cgo) هم بهبود ۳۰ درصدی سربار رو داشتیم. اگه از کتابخونه‌هایی که با c نوشته شدن استفاده می‌کنید سعی کنید آپدیت رو در اولویت قرار بدید، مثلا confluent یا gmf یا h3.

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

یکسری بهبود tooling هم داشتیم که profiling و تشخیص go routine leak و بهبود ساب‌کامند go fix جزوشه.

اطلاعات بیشتر در بلاگ رسمی گولنگ:
https://go.dev/doc/go1.26

من اعتقاد دارم برنامه نویسی یاد گرفتن پیش‌نیاز کار به عنوان برنامه‌نویس یا مهندس نرم‌افزار یا شغل های مشابه هست، ولی اصلا کافی نیست، بلکه نیاز به دانش تئوری هم داریم که هم تو دانشگاه یاد میدن، هم جاهای دیگه میشه یاد گرفت.

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

فرض کنید که یک redis داریم که موقع ذخیره RDB در دیسک، با خطا مواجه می‌شه. در مرحله اول خطا رو می‌خونیم و سرچ میکنیم. خب خطای OOM داریم یعنی مموری پر شده، پس بیایم حافظه بیشتری بهش تخصیص بدیم، ولی این حافظه فقط برای ذخیره RDB استفاده میشه، پس آیا ارزش داره؟ احتمالا نه.
پس می‌تونیم چیکار کنیم؟ اگر با CoW یا همون copy on write و memory overcommit آشنا باشیم می‌دونیم که پروسسی از ردیس که قراره اطلاعات رو توی دیسک بنویسه، اگرچه فورکی از پروسس اصلیه ولی نیاز نیست همون مموری رو کپی کنه چون نیاز نیست write انجام بده و فقط میخواد اطلاعات رو بخونه. البته این رو سیستم‌عامل از قبل نمی‌دونه و مجبوره حافظه برای حالتی که پروسس بخواد در مموری خودش بنویسه در نظر بگیره. برای این که سیستم عامل بدونه بهش میگیم اجازه داری overcommit کنی! مسئولیتش با من.

https://redis.io/docs/latest/develop/get-started/faq/#background-saving-fails-with-a-fork-error-on-linux

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

اینجا دو تا مفهوم داریم که خوبه با اسم اصلیشون هم آشنا باشیم. Cohesion به وابستگی و شباهت داخل ماژول برمی‌گرده که انتظار داریم بالا باشه و سعی می‌کنیم بیشینه‌اش کنیم. اما Coupling به وابستگی بین یک ماژول و ماژول‌های دیگه برمی‌گرده و سعی می‌کنیم کمش کنیم.

این که انواع Coupling چیا می‌تونه باشه بسته به نرم‌افزار و سطحی که توش صحبت می‌کنیم می‌تونه خیلی متفاوت باشه ولی اگه بخوام ساده مثال بزنم ممکنه ماژول ما انتظار داشته باشه دیتای تولیدشده توسط یه ماژول دیگه یه جایی باشه. یا این که متدهای یک کلاس متدهای کلاس دیگری رو صدا بزنن.

در این زمینه تلاش‌های متفاوتی شده که به شکل عددی بیایم دو تا معیار رو اندازه‌گیری کنیم ولی من چیز به درد بخور عملی‌ای ندیدم!

https://en.wikipedia.org/wiki/Coupling_(computer_programming)

چطور یک سیستم online dating رو طراحی کنیم؟
به چشم سوال system design به تیندر نگاه کنید نکات جالبی می‌تونه داشته باشه.

https://www.systemdesignhandbook.com/guides/design-tinder/

دوست دارید برای خودتون گیت رو بنویسید؟
https://wyag.thb.lt/

یکسری مسائل دنیای واقعی هستن که توی کامپیوترها هم پیش میان، مخصوصا توی شبکه و سیستم‌های توزیع‌شده، این جور چیزها زیاد وجود داره.

یکی از ساده‌ترین مشکلات که اینه که بفهمیم یک کامپیوتر دیگه توی شبکه زنده هست یا نه. یکی از کاربردهاش توی باز نگه داشتن سوکت tcpئه. سیستم ما لازم داره بدونه این کانکشن tcpای که باز کرده و الان دیتایی توش نمیاد آیا به خاطر اینه که دیتای خاصی نداریم به هم بفرستیم یا اصلا سمت مقابل سرور در دسترس نیست و الکی منابع سیستم رو مشغول نگه نداریم و کاربر رو امیدوار نکنیم.

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

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

https://en.wikipedia.org/wiki/Heartbeat_(computing)