ساختارهای داده برای کلان‌داده در مصاحبه‌های طراحی سیستم

ساختارهای داده برای کلان‌داده

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

معمولاً در مصاحبه لازم نیست این ساختارها را همان لحظه پیاده‌سازی کنید. پس چرا باید آن‌ها را بشناسید؟ چون انتخاب یک ساختار داده مناسب می‌تواند شکل راه‌حل و معماری اطراف آن را تغییر دهد. این شناخت به شما کمک می‌کند سیستم‌هایی کم‌هزینه‌تر و مقیاس‌پذیرتر طراحی کنید.

البته تخصصی بودن این ابزارها بی‌دلیل نیست. استفاده از Bloom Filter وقتی یک HashSet ساده کافی است، بیشتر نشانه پیچیده کردن مسئله است تا طراحی بهتر. هدف این فصل گسترش گزینه‌های شما، شناخت کاربردهای مناسب و دوری از دام‌های رایج است.

اگر تازه طراحی سیستم را شروع کرده‌اید، اول روی کش، توزیع بار و پارتیشن‌بندی مسلط شوید. شناخت جزئیات Count-Min Sketch بدون درک این مفاهیم، به‌تنهایی کمکی به ساخت یک معماری کاربردی نمی‌کند.

Bloom Filter

Bloom Filter یک ساختار داده احتمالاتی برای بررسی عضویت در مجموعه است. مجموعه معمولی اجازه می‌دهد عنصری را اضافه کنیم و بعد بپرسیم آیا در مجموعه وجود دارد یا نه.

پیاده‌سازی مبتنی بر جدول هش، درج و بررسی عضویت را به‌طور متوسط در زمان O(1) انجام می‌دهد، اما باید خود عناصر یا اطلاعات لازم برای شناسایی آن‌ها را نگه دارد. وقتی تعداد عناصر بسیار زیاد باشد، مصرف حافظه به مسئله اصلی تبدیل می‌شود.

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

• عنصر قطعاً در مجموعه نیست.
• عنصر ممکن است در مجموعه باشد.

پاسخ دوم ممکن است مثبت کاذب (False Positive) باشد؛ یعنی ساختار بگوید عنصر احتمالاً وجود دارد، در حالی که اضافه نشده است. در مدل استاندارد و با درج صحیح عناصر، پاسخ منفی کاذب نداریم.

شهود با مهرهای هم‌پوشان

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

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

مثلاً مهر آلبرت یک دایره و علامت جمع دارد و مهر برایان یک دایره و خط مورب. اگر این نقش‌ها روی کاغذ باشند، حضور آن‌ها محتمل است. اگر مهر کریستینا یک خط و مربع داشته باشد و مربع روی کاغذ نباشد، می‌دانیم او حاضر نبوده است.

این همان مصالحه اصلی Bloom Filter است. اطلاعات چند عنصر را در فضای مشترک نگه می‌داریم، اما در ازای آن، تشخیص قطعی حضور را از دست می‌دهیم.

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

نحوه کار

به‌جای کاغذ، یک آرایه با m بیت داریم که ابتدا همه بیت‌های آن صفرند. به‌جای مهر هم از k تابع هش استفاده می‌کنیم.

برای اضافه کردن یک عنصر:

1. عنصر را با k تابع هش پردازش می‌کنیم.
2. خروجی هر تابع، موقعیتی در آرایه بیت را مشخص می‌کند.
3. بیت‌های این موقعیت‌ها را یک می‌کنیم.

برای بررسی عضویت:

1. همان توابع هش را روی عنصر اجرا می‌کنیم.
2. بیت‌های موقعیت‌های حاصل را بررسی می‌کنیم.
3. اگر حتی یکی صفر باشد، عنصر قطعاً اضافه نشده است.
4. اگر همه یک باشند، عنصر ممکن است اضافه شده باشد.

برخورد هش باعث می‌شود عناصر مختلف بعضی بیت‌ها را مشترک کنند. همین هم‌پوشانی منشأ پاسخ مثبت کاذب است. با اضافه شدن عناصر بیشتر، بیت‌های بیشتری یک می‌شوند و احتمال مثبت کاذب افزایش می‌یابد.

اندازه آرایه و تعداد توابع هش باید بر اساس تعداد عناصر مورد انتظار و نرخ خطای قابل‌قبول انتخاب شوند. افزایش تعداد توابع هش همیشه بهتر نیست؛ چون بیت‌های بیشتری را پر می‌کند و هزینه پردازش هم دارد.

مصرف حافظه

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

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

کاربردها و محدودیت‌ها

Bloom Filter زمانی مناسب است که این سه شرط برقرار باشند:

• مسئله شما بررسی عضویت در یک مجموعه باشد.
• محدودیت حافظه واقعاً مهم باشد.
• بتوانید پاسخ مثبت کاذب را تحمل کنید یا آن را با بررسی دقیق‌تر جبران کنید.

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

خزنده وب

خزنده وب روی گراف عظیمی از صفحات حرکت می‌کند. نمی‌خواهیم یک صفحه را بارها بخزیم، اما نگه داشتن همه URLهای دیده‌شده در HashSet می‌تواند حافظه زیادی بخواهد.

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

اگر پوشش کامل صفحات ضروری باشد، نمی‌توانیم صرفاً بر این پاسخ احتمالاتی تکیه کنیم. در آن صورت باید پاسخ مثبت را با یک منبع دقیق‌تر بررسی کنیم.

بهینه‌سازی مراجعه به کش

در الگوی رایج کش، ابتدا Redis یا Memcached را بررسی می‌کنیم. اگر داده موجود باشد، همان را برمی‌گردانیم. در غیر این صورت، محاسبه پرهزینه را انجام می‌دهیم و نتیجه را کش می‌کنیم.

اگر زمان مراجعه به کش C و زمان محاسبه E باشد، مسیر Cache Miss تقریباً C + E زمان می‌برد. ایده استفاده از Bloom Filter این است که در بعضی درخواست‌ها بتوانیم این مراجعه اضافی را حذف کنیم.

• اگر فیلتر بگوید کلید قطعاً در کش نیست، مستقیماً محاسبه را انجام می‌دهیم.
• اگر بگوید ممکن است موجود باشد، ابتدا کش را بررسی می‌کنیم.

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

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

Count-Min Sketch

Bloom Filter درباره عضویت پاسخ می‌دهد، اما گاهی می‌خواهیم بدانیم یک عنصر چند بار در جریان داده دیده شده است. Count-Min Sketch برای تخمین این فراوانی با مصرف حافظه محدود کاربرد دارد.

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

شهود با تیله‌ها

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

فرض کنید آلبرت از حفره‌های ۲ و ۴، برایان از حفره‌های ۲ و ۳ و کریستینا از حفره‌های ۱ و ۳ استفاده می‌کنند. آلبرت دو بار و برایان یک بار حاضر شده‌اند. در پایان:

حفره	تعداد تیله
۱	۰
۲	۳
۳	۱
۴	۲

برای تخمین حضور هر فرد، کمترین مقدار حفره‌های مربوط به او را برمی‌داریم.

• آلبرت مقدارهای ۳ و ۲ را دارد؛ پس تعداد حضور او حداکثر ۲ است.
• برایان مقدارهای ۳ و ۱ را دارد؛ پس تعداد حضور او حداکثر ۱ است.
• کریستینا مقدارهای ۰ و ۱ را دارد؛ پس قطعاً در هیچ جلسه‌ای حاضر نبوده است.

چرا حداقل را می‌گیریم؟ چون حضور واقعی فرد باید همه شمارنده‌های مربوط به او را افزایش داده باشد. شمارنده‌های بزرگ‌تر ممکن است تحت تأثیر افراد دیگر هم باشند، اما کمترین مقدار، محدودترین کران بالا را می‌دهد.

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

Count-Min Sketch بین این دو حالت قرار می‌گیرد: شمارنده‌های کمتری از تعداد شناسه‌های ممکن نگه می‌داریم و در ازای صرفه‌جویی در حافظه، تقریب را می‌پذیریم.

نحوه کار

ساختار اصلی یک آرایه دوبعدی از شمارنده‌هاست. هر ردیف تابع هش خودش را دارد.

برای ثبت یک مشاهده:

1. کلید عنصر را با تابع هش هر ردیف پردازش می‌کنیم.
2. در هر ردیف، شمارنده ستون حاصل را افزایش می‌دهیم.

برای تخمین فراوانی:

1. موقعیت‌های مربوط به کلید را دوباره محاسبه می‌کنیم.
2. مقدار شمارنده‌ها را می‌خوانیم.
3. کمترین مقدار را به‌عنوان تخمین برمی‌گردانیم.

دو پارامتر اصلی، مصالحه حافظه و دقت را کنترل می‌کنند:

• عرض w تعداد ستون‌ها را تعیین می‌کند. عرض بیشتر معمولاً برخورد کمتر و خطای کمتری دارد.
• عمق d تعداد ردیف‌ها و توابع هش را تعیین می‌کند. عمق بیشتر، اطمینان به کران خطا را افزایش می‌دهد.

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

کاربردها و دام‌ها

برای استفاده مناسب، این شرایط را بررسی کنید:

• به تخمین تعداد رخدادهای یک عنصر نیاز دارید.
• کلید عنصر مورد پرس‌وجو را از قبل می‌دانید؛ خود Sketch فهرست کلیدها را نگه نمی‌دارد.
• نگه داشتن شمارنده دقیق برای همه عناصر پرهزینه است.
• خطای تخمین، به‌ویژه بیش‌برآورد تعداد، قابل‌قبول است.

پیدا کردن Top K

فرض کنید می‌خواهیم K ویدیوی پربازدید را نگه داریم، اما تعداد ویدیوها و بازدیدها بسیار زیاد است.

1. ساختاری محدود برای نگهداری نامزدهای Top K در نظر می‌گیریم.
2. با هر بازدید، شمارش شناسه ویدیو را در Count-Min Sketch افزایش می‌دهیم.
3. تخمین فراوانی همان ویدیو را می‌خوانیم.
4. اگر ویدیو در فهرست نامزدهاست، امتیازش را به‌روز می‌کنیم. اگر از کم‌امتیازترین نامزد بالاتر است، ورود آن به فهرست را بررسی می‌کنیم.

این روش می‌تواند تقریب مفیدی از Top K بدهد، بدون اینکه برای تمام ویدیوها شمارنده دقیق نگه داریم. البته فهرست نامزدها همچنان لازم است؛ Count-Min Sketch به‌تنهایی شناسه ویدیوهای برتر را استخراج نمی‌کند.

مدیریت کش

در سیاست LFU، آیتم‌هایی که کمتر استفاده می‌شوند نامزد حذف هستند. Count-Min Sketch می‌تواند تعداد مراجعه به کلیدها را تقریبی ثبت کند و در تصمیم‌گیری درباره محبوبیت آن‌ها کمک کند.

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

در مثال Redis متن، برای سیاست LFU به شمارنده‌های فشرده کنار هر کلید اشاره شده است، نه الزاماً استفاده از Count-Min Sketch. نکته طراحی این است که هر شمارنده تقریبی با Count-Min Sketch یکسان نیست و باید پیاده‌سازی انتخابی را جداگانه بشناسیم.

HyperLogLog

Count-Min Sketch فراوانی رخدادها را تخمین می‌زند، اما گاهی تعداد عناصر یکتا را می‌خواهیم. مثلاً یک صفحه چند بازدیدکننده متمایز داشته است؟ هزار بازدید از یک کاربر با هزار بازدید از هزار کاربر فرق دارد.

HyperLogLog یا HLL ساختار داده احتمالاتی برای تخمین تعداد عناصر یکتا، یا همان Cardinality، است. در روش دقیقی مثل HashSet، حافظه با تعداد عناصر یکتا رشد می‌کند. HLL در ازای خطای آماری کوچک، حافظه بسیار کمتری مصرف می‌کند.

شهود با پرتاب سکه

در یک رشته بیت تصادفی، دیدن پیشوندهای طولانی‌تر از صفر نادرتر است:

• پیشوند 1 تقریباً با احتمال ۵۰٪ دیده می‌شود.
• پیشوند 01 تقریباً با احتمال ۲۵٪ دیده می‌شود.
• پیشوند 001 تقریباً با احتمال ۱۲٫۵٪ دیده می‌شود.

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

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

نحوه کار

تکیه بر نادرترین هش به‌تنهایی می‌تواند تخمین ناپایداری بسازد. برای کاهش این نوسان، فضای هش را به چند bucket تقسیم می‌کنیم.

1. هر عنصر ورودی به یک مقدار باینری با توزیع مناسب هش می‌شود.
2. b بیت ابتدایی، bucket را انتخاب می‌کنند؛ در نتیجه 2^b bucket داریم.
3. در بیت‌های باقی‌مانده، تعداد صفرهای ابتدایی را تا اولین بیت یک می‌شماریم.
4. برای هر bucket، رجیستری نگه می‌داریم که بیشترین طول مشاهده‌شده، به‌علاوه یک، را ثبت می‌کند.
5. تخمین نهایی از ترکیب رجیسترها و اصلاحات آماری به دست می‌آید.

برای ترکیب رجیسترها از محاسبه‌ای مبتنی بر میانگین هارمونیک استفاده می‌شود؛ منظور صرفاً میانگین گرفتن مستقیم از عددهای داخل رجیسترها نیست. پیاده‌سازی‌ها برای تعداد عناصر کم یا بسیار زیاد هم اصلاحاتی دارند.

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

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

کاربردها و محدودیت‌ها

HLL زمانی مناسب است که:

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

اگر شمارش دقیق لازم دارید، HLL پاسخ مناسبی نیست. اگر هم تعداد عناصر کم است، یک HashSet ساده ممکن است روشن‌تر و مناسب‌تر باشد.

در انتخاب ابزار، بین قابلیت داخلی و قابلیت ارائه‌شده از طریق افزونه تفاوت بگذارید. در متن به Redis و PostgreSQL اشاره شده است؛ برای استفاده عملی باید پشتیبانی HLL در محصول یا افزونه انتخابی را بررسی کنید.

سیستم‌های تحلیل و متریک

کاربردهای رایج تخمین Cardinality عبارت‌اند از:

• تعداد کاربران فعال روزانه یا ماهانه (DAU و MAU).
• تعداد بازدیدکنندگان یکتای هر صفحه.
• تعداد عبارت‌های جستجوی متمایز.
• تعداد آدرس‌های IP یکتا.

می‌توان HLL را همراه ورود داده‌های جدید به‌صورت استریمی به‌روز کرد، یا هنگام پردازش مجموعه داده از آن برای تخمین تعداد عناصر متمایز استفاده کرد.

تشخیص رفتار مشکوک

فرض کنید می‌خواهیم IPهایی را پیدا کنیم که با Scraping اطلاعات کاربران را جمع می‌کنند. تعداد بالای درخواست به‌تنهایی نشانه کافی نیست؛ شاید آن IP متعلق به پراکسی یک سازمان با کاربران زیاد باشد.

یک سیگنال کمکی، تعداد URLهای متمایزی است که هر IP درخواست می‌کند. اگر کاربران واقعی بیشتر به صفحه‌های محبوب برگردند، اما Scraper پیوسته صفحه‌های جدید را باز کند، نسبت URLهای یکتا به کل درخواست‌ها می‌تواند برای بررسی رفتار مفید باشد.

HLL کمک می‌کند این تعداد را بدون نگه داشتن HashSet بزرگی از تمام URLهای بازدیدشده هر IP تخمین بزنیم. البته این فقط یک سیگنال است، نه دلیل قطعی برای مسدود کردن کاربر. همچنین شمارش عناصر یکتا با محاسبه کامل آنتروپی توزیع یکسان نیست.

تحلیل اندازه کش

برای طراحی کش باید بدانیم Working Set چه اندازه‌ای دارد:

• در یک بازه زمانی به چند کلید یکتا دسترسی داریم؟
• تعداد کلیدهای جدید با چه سرعتی رشد می‌کند؟
• آیا ظرفیت فعلی کافی است یا باید کش را پارتیشن‌بندی کنیم؟

HLL می‌تواند به تخمین این مقادیر کمک کند، بدون اینکه مجبور باشیم تمام کلیدهای دیده‌شده را نگه داریم.

انتخاب ساختار مناسب

ساختار	پرسشی که پاسخ می‌دهد	مصالحه اصلی
Bloom Filter	آیا این عنصر قبلاً اضافه شده است؟	پاسخ مثبت ممکن است اشتباه باشد.
Count-Min Sketch	این عنصر تقریباً چند بار دیده شده است؟	در مدل افزایشی ممکن است تعداد را بیشتر از واقعیت تخمین بزند.
HyperLogLog	تقریباً چند عنصر یکتا دیده‌ایم؟	تعداد متمایز را با خطای آماری تخمین می‌زند و اعضای مجموعه را برنمی‌گرداند.

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