طراحی قابلیت K ویدیوی برتر YouTube

درک مسئله

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

کلمه «دقیقاً» اینجا پیامدهای چشمگیری برای این مسئله دارد. برای بیشتر اپلیکیشن‌ها کمی غیرواقعی است، اما راه‌حل تقریبی به‌شدت به رویکردهای احتمالاتی و تقریبی تکیه می‌کند که برای بسیاری از نقش‌ها نیاز به دانش تخصصی دارد، از جمله Count-Min Sketch. به‌جز موقعیت‌های تخصصی، بیشتر مصاحبه‌کننده‌های معقول دانش عمومی را می‌سنجند، نه چیزی که در حین کار بعد از خواندن چند مقاله یاد می‌گیرید.

ممکن است مصاحبه‌کننده برای کمک به درک مقیاس سیستم اعدادی بدهد. مثلاً YouTube Shorts روزانه 70 میلیارد بازدید داشت و تقریباً 1 ساعت محتوا در هر ثانیه روی YouTube آپلود می‌شود. بزرگ است!

نیازمندی‌های عملکردی

نیازمندی‌های اصلی:

• کلاینت‌ها بتوانند K ویدیوی برتر (حداکثر 1000) را برای یک بازه زمانی مشخص کوئری کنند.
• بازه‌های زمانی به 1 ساعت، 1 روز، 1 ماه و همه زمان‌ها محدود باشد.

موارد خارج از محدوده:

• بازه‌های زمانی دلخواه
• نقطه شروع و پایان دلخواه (فرض می‌کنیم همه کوئری‌ها از لحظه فعلی به عقب نگاه می‌کنند).

نیازمندی‌های غیرعملکردی

نیازمندی‌های اصلی:

• حداکثر 1 دقیقه تأخیر بین رخ دادن یک بازدید و محاسبه آن را تحمل می‌کنیم.
• نتایج باید دقیق باشند، پس نباید تقریبی باشند (توجه: این برای بیشتر سیستم‌های تولیدی غیرعادی است).
• سیستم باید بتواند تعداد بسیار زیادی بازدید در ثانیه را مدیریت کند (TBD، بعداً پوشش می‌دهیم).
• باید از تعداد بسیار زیادی ویدیو پشتیبانی کنیم (TBD، بعداً پوشش می‌دهیم).
• باید نتایج را در حد ده‌ها میلی‌ثانیه برگردانیم.
• سیستم باید اقتصادی باشد. برای حل این مسئله نباید به ناوگان 10 هزار میزبانی نیاز داشته باشیم.

داشتن عدد برای نیازمندی‌های غیرعملکردی به تصمیم‌گیری در طراحی کمک می‌کند. در اینجا توجه کنید که سیستمی که در ده‌ها میلی‌ثانیه جواب می‌دهد، بسیاری از رویکردها را از فضای راه‌حل حذف می‌کند و ما باید از پیش‌محاسبه (Precomputation) استفاده کنیم.

برای مقادیری که برای طراحی ما مهم‌اند اما نمی‌توانیم آن‌ها را الان برآورد کنیم، زمانی را برای بعد کنار می‌گذاریم.

برآورد مقیاس

دو مقدار را برای طراحی در نظر گرفته‌ایم: (الف) تعداد بازدید در ثانیه و (ب) تعداد کل ویدیوها. اولی به درک عملکرد کلی سیستم کمک می‌کند، دومی برای محدود کردن فضای ذخیره‌سازی لازم مهم است.

اول Throughput (نرخ گذردهی داده):

70B views/day / (100k seconds/day) = 700k tps

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

حالا ذخیره‌سازی. اول به تعداد ویدیوها نیاز داریم:

Videos/Day = 1 hour content/second / (6 minutes content/video) * (100k seconds/day) = 1M videos/day
Total Videos = 1M videos/day * 365 days/year * 10 years = 3.6B videos

با این عدد، تخمین می‌زنیم جدول ساده شناسه‌ها و شمارنده‌ها چقدر بزرگ می‌شود:

Naive Storage = 4B videos * (8 bytes/ID + 8 bytes/count) = 64 GB

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

هدف برآوردها در واقع این نیست که ببینند حساب ذهنی بلدید یا نه (پس از اعداد نترسید). تأمل شما درباره پیامدهای این مقدارها در طراحی، مثل معماری‌هایی که در نتیجه روی میز می‌مانند یا کنار می‌روند، اغلب مهم‌ترین عامل است.

آماده‌سازی

برنامه‌ریزی رویکرد

بر اساس نیازمندی‌ها می‌دانیم که چند مشاهده برای مصاحبه‌کننده داریم:

• به اشتراک گذاشتن روند فکری‌تان راه عالی برای نشان دادن ارشدیت است، چون نشان می‌دهد یک قدم جلوتر فکر می‌کنید.
• اول باید داده را از یک جریان با حجم بسیار بالا ایندکس کنیم. برای برآورده کردن نیازمندی Latency، بیشتر مقدارها باید از پیش محاسبه شوند.
• بعد، مسائلی مثل این معمولاً گلوگاه‌هایی دارند که پشت گلوگاه‌های دیگر پنهان‌اند: حل یک مسئله (دست‌کم) مسئله دیگری می‌سازد. پس هدف ما این است که اول ساده‌ترین مسئله را حل کنیم و بعد پیچیدگی اضافه کنیم.
• در نهایت، متذکر می‌شویم که پنجره زمانی کشویی چالش بیشتری اضافه می‌کند. پس با «همه زمان‌ها» شروع می‌کنیم و بعد بقیه را حل می‌کنیم.

طرح کلی ما این است:

1. یک راه‌حل پایه (غیرمقیاس‌پذیر) برای Top K همه زمان‌ها بسازیم.
2. مشکلات اولیه راه‌حل پایه را حل کنیم.
3. راه‌حلی برای ورودی‌های بازه زمانی اضافه کنیم.
4. تا وقتی وقتمان تمام شود، گلوگاه‌های باقی‌مانده را عمیق بررسی کنیم.

تعریف موجودیت‌های اصلی

در مسئله ما چند موجودیت اساسی داریم که قرار است برای ساخت API با آن‌ها کار کنیم:

• Video (ویدیو)
• View (بازدید)
• Time Window (پنجره زمانی)

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

API یا رابط سیستم

API ما بقیه مصاحبه را هدایت می‌کند، اما در این مورد هم واقعاً پایه‌ای است! فقط به یک API برای بازیابی K ویدیوی برتر نیاز داریم:

GET /views/top?window={WINDOW}&k={K}
Response:
{
    "videos": [
        {
            "videoId": // ...
            "views": // ...
        }
    ]
}

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

طراحی سطح بالا

1) راه‌حل پایه برای همه زمان‌ها

با یک راه‌حل ساده برای K ویدیوی برتر همه زمان‌ها روی یک میزبان غول‌پیکر شروع می‌کنیم و بعد می‌توانیم بهینه‌اش کنیم.

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

می‌توانیم این کار را با نگه داشتن جدولی از شناسه ویدیوها و شمارنده‌هایشان انجام دهیم. با این کار شمارش هر ویدیو به‌روز می‌شود، اما پیمایش 4 میلیارد کلید برای پیدا کردن بزرگ‌ترین مقدارها قابل دفاع نیست. پس مجموعه‌ای از K ویدیوی برتر را در یک Heap نگه می‌داریم که با هر افزایش می‌توانیم آن را به‌روز کنیم. اکثریت قریب‌به‌اتفاق بازدیدها هرگز این Heap را لمس نمی‌کنند، چون زیر آستانه 1000 مورد برتر خواهند بود (حداکثر K ما طبق نیازمندی‌های عملکردی).

عملکرد اصلی این است: وقتی درخواست بازدیدی می‌رسد، شمارنده را در Hash Table با شناسه ورودی به‌صورت اتمی افزایش می‌دهیم. شمارش به‌روز را می‌گیریم و آن را با کف Heap مقایسه می‌کنیم. اگر شمارش از کف بیشتر باشد (یعنی ویدیو در 1000 مورد برتر است)، Heap را به‌روز می‌کنیم یا در آن درج می‌کنیم و Heapify می‌کنیم. کلاینت‌ها مستقیم از همین Heap کوئری می‌کنند تا K ویدیوی برتر را بگیرند.

این واقعاً ساده و سریع است، چون روی یک میزبان اجرا می‌شود. با اینکه از نظر مفهومی در حافظه و روی یک میزبان ممکن است، نمی‌خواهیم این کار را بکنیم. اول به این دلیل که Throughput ای که یک میزبان تکی می‌تواند پشتیبانی کند، احتمالاً بیش از یک مرتبه بزرگی کمتر از 700 هزار TPS مورد نیاز ماست، و دوم به این دلیل که آن میزبان تبدیل به نقطه شکست واحد (Single Point of Failure) می‌شود. اینجا چه کنیم؟

2) مسائل اولیه راه‌حل پایه

دو مسئله داریم که باید به آن‌ها بپردازیم: چطور در برابر خرابی قابل اعتماد بمانیم و چطور Throughput نوشتن سیستم را مقیاس بدهیم. به ترتیب درباره‌شان صحبت می‌کنیم.

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

رویکرد بد: شمارنده‌های مبتنی بر پایگاه داده

یکی از گزینه‌های ما این است که شمارنده‌ها را در یک پایگاه داده بنویسیم و جمع کنیم. چون پایگاه داده تمام وضعیت را نگه می‌دارد، سرویس ما بدون حالت (Stateless) است و می‌توانیم به‌سادگی روی میزبان جدید بالا بیاوریم و از همان‌جا ادامه بدهیم.

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

رویکرد خوب: شمارنده‌های Replica شده

گزینه دیگر نگه داشتن چند Replica از نمونه‌های Counter است. این نه‌تنها اجازه می‌دهد بار خواندن کلاینت‌ها را کم کنیم، بلکه در صورت خرابی می‌توانیم به‌سادگی آن گره‌ها را از Load Balancer حذف کنیم. جریان (Stream) را Retain می‌کنیم تا در صورت خرابی بتوانیم از ابتدا بازسازی کنیم.

چالش‌ها: اگرچه Replica ها دسترس‌پذیری را بهتر می‌کنند، بار روی جریان View را افزایش می‌دهند و سخت‌افزار لازم برای استقرار را چند برابر می‌کنند. علاوه بر این، شکست‌ها را زیبا مدیریت نمی‌کنند. هنوز باید در صورت خرابی نمونه جدید بالا بیاوریم و «رسیدن به بقیه» (Catch up) بسته به تعداد بازدید قابل پردازش در ثانیه ممکن است زمان زیادی ببرد. در نهایت باید از ابتدای جریان شروع کنیم!

رویکرد عالی: Replica همراه Snapshot

گزینه عالی برای ما این است که چند Replica از نمونه‌های Counter نگه داریم و دوره‌ای از حافظه‌شان Snapshot بگیریم. این نه‌تنها بار خواندن کلاینت‌ها را کم می‌کند، بلکه می‌توانیم در صورت خرابی سریع بازیابی کنیم: جدیدترین Snapshot را بارگذاری می‌کنیم و تا وقتی به جریان زنده برسیم، از جریان دوباره می‌خوانیم. اگرچه هنوز به Retention در جریان نیاز داریم، حالا می‌توانیم مدت نگه داشتن جریان را محدود کنیم. وقتی از همه پارتیشن‌هایمان Snapshot داشتیم، می‌توانیم بعد از آن Retention را حذف کنیم.

چالش‌ها: اگرچه Snapshot ها زمان بازیابی را به‌طور قابل توجهی بهتر می‌کنند، هنوز باید نگران Throughput پردازش باشیم. اگر لازم باشد 700 هزار بازدید در ثانیه پردازش کنیم و سیستم ما فقط بتواند حدود 1.4 میلیون بازدید در ثانیه پردازش کند، یعنی ظرفیت اضافه فقط 700 هزار در ثانیه است، پس به ازای هر ثانیه که از آخرین Snapshot گذشته، 1 ثانیه برای جبران لازم داریم. علاوه بر این، این Snapshot ها چند گیگابایتی خواهند بود. سربار Snapshot ممکن است بار اضافه بسازد (که Throughput ما را پایین می‌کشد) و به مکانیزمی نیاز داریم تا مطمئن شویم Snapshot ها از درون سازگارند.

خوب، با چند Replica و Snapshot در وضعیت بسیار مقاوم‌تری در برابر خطا هستیم. در مرحله بعد باید Throughput نوشتن سیستم را مقیاس بدهیم، چون Replica ها مشکل داشتن یک «شلنگ آتش‌نشانی» (Firehose) عظیم از داده ورودی را حل نمی‌کنند. ذهنتان باید فوراً به Sharding و پارتیشن‌بندی برود.

الگو: مقیاس‌دهی نوشتن (Scaling Writes). Sharding و پارتیشن‌بندی اولین خط دفاع شما در مقیاس‌دهی نوشتن‌هاست. الگوی Scaling Writes استراتژی‌های تکرارپذیری را توصیف می‌کند که می‌توانید در مسائلی که حجم نوشتن بالاست استفاده کنید.

رویکرد خوب: Shard های ثابت

ابتدایی‌ترین ایده این است که P تا Shard بسازیم که هر کدام زیرمجموعه‌ای از فضای شناسه‌ها را «مالک» هستند. می‌توانیم مدول P را روی شناسه‌های ورودی اعمال کنیم تا بازدیدهای ویدیو را به میزبانی هدایت کنیم که id % P را مالک است. یعنی هر میزبان همراه Replica هایش زیرمجموعه‌ای متقابلاً ناهم‌پوشان و روی هم‌رفته کامل از همه ویدیوها دارد.

این (هنوز) کامل نیست، چون حالا P تا Top K متمایز داریم، پس کلاینت ما باید هر Heap را کوئری کند و آن‌ها را ادغام کند تا Top K سراسری را برگرداند. سرویسی اضافه می‌کنیم که مسئول کوئری هر Shard Counter (یا Replica اش) و ادغام نتیجه است. می‌توانیم از رکوردهای DNS ایستا برای ارجاع به هر Shard و Replica هایش به‌صورت Round Robin استفاده کنیم: topk-shard-1، topk-shard-2 و غیره.

چالش‌ها: این رویکرد مبادلاتی دارد. چون پارتیشن‌های ما ثابت‌اند، Snapshot هایمان تمیز به هر Shard نگاشت می‌شوند. اما اگر لازم باشد P را زیاد کنیم، مثلاً چون روزانه ویدیوهای جدید به YouTube اضافه می‌شود، این وضعیت به هم می‌خورد. دوم، اگر P بزرگ شود، سرویس Top-K باید تعداد زیادی تماس بگیرد.

رویکرد عالی: Sharding الاستیک

می‌توانیم رویکرد پارتیشن‌بندی را طوری به‌روز کنیم که مقیاس‌دهی را ممکن کند. مثل راه‌حل «خوب»، می‌توانیم P تا Shard از Worker های Counter (به‌علاوه Replica) بسازیم که هرکدام زیرمجموعه‌ای از فضای شناسه را با Consistent Hashing (هشینگ پایدار) در اختیار دارند. به‌جای ثابت کردن پارامترهای پارتیشن‌بندی، می‌توانیم آن‌ها را متغیر کنیم تا بتوانیم مقیاسشان را بالا و پایین ببریم. وقتی لازم است ظرفیت بیشتری اضافه کنیم، Shard های جدید بالا می‌آیند که از دو Snapshot مختلف (چپ و راست در حلقه Consistent Hashing ما) می‌خوانند و به فضای شناسه متعلق به این Shard جدید فیلتر می‌شوند.

چالش‌ها: چون پارتیشن‌ها دیگر ثابت نیستند، باید رجیستری مثل ZooKeeper داشته باشیم تا هر Shard تکلیف خود را بداند و سرویس Top-K بداند برای هر پیکربندی کدام Shard ها را کوئری کند. برای زمانی که تعداد Shard ها را زیاد یا کم می‌کنیم، به ارکستراسیون نیاز داریم. و هنوز مشکل بزرگ شدن P را داریم که عملیات Scatter-gather بزرگی می‌خواهد.

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

بررسی‌های عمیق

1) مدیریت پنجره‌های زمانی

در حالی که راه‌حل «همه زمان‌ها» به‌راحتی بازدیدها را برای همیشه جمع می‌کند، برای مدیریت پنجره‌های زمانی باید بازدیدهایی را که بیرون از آن پنجره رخ داده‌اند «منقضی» کنیم. مثلاً اگر ویدیویی در زمان T=0 یک بازدید داشته باشد و پنجره زمانی ما 1 باشد، در T=2 باید مطمئن شویم شمارش آن ویدیو 0 است.

یکی از مزیت‌های ما این است که پنجره‌های زمانی که با آن‌ها کار می‌کنیم ثابت و کم‌اند: فقط 3 تا داریم. یکی از معایبشان این است که دانه‌بندی‌های بسیار متفاوتی دارند: از 1 دقیقه تا 1 ماه.

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

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

این کار از دو حالت شکست رایج جلوگیری می‌کند: (1) گیر افتادن در تلاش برای پریدن از دو مرحله، و (2) مجبور کردن مصاحبه‌کننده به اصلاح زودهنگام شما، چون فکر می‌کند ایده بد اولیه شما … خوب … بد است.

مصاحبه‌کننده دنبال این است که شما چطور درباره مسئله فکر می‌کنید، نه اینکه (لزوماً) پاسخ بهینه را بگیرید. شناسایی نقطه‌های ضعف، حل آن‌ها و گیر نکردن بسیار مهم است. اما اگر می‌توانید به بهترین راه‌حل فکر کنید، دنبالش بروید!

رویکرد بد: شمارش هر دقیقه با تجمیع در زمان کوئری

به‌جای نگه داشتن شمارش همه زمان‌ها، می‌توانیم شمارش هر ویدیو را برای هر دقیقه نگه داریم. وقتی درخواستی می‌رسد، اجزای غیر دقیقه مهر زمانی را حذف می‌کنیم و آن را به نگاشت شمارش به کلید [videoId, minute] اضافه می‌کنیم. سپس برای هر بازه زمانی (1 دقیقه، 1 ساعت، 1 روز)، همه [videoId, minute] ها در آن بازه را جمع می‌کنیم و به یک Heap Top-K جداگانه برای آن بازه اضافه می‌کنیم.

چالش‌ها: این روشن است که کار نمی‌کند. چه ایرادی دارد؟

• ورودی‌هایی در Heap داریم که ممکن است کهنه باشند (این ویدیو در ساعت گذشته با 100 بازدید رتبه اول بود، ولی در این ساعت هیچ بازدیدی نداشته).
• جمع کردن همه [videoId, minute] ها برای یک ماه گران است.
• حافظه باد می‌کند.

رویکرد خوب: اصلاح رویکرد بد (Heap های بازخوانی‌شونده و دانه‌بندی چندگانه)

می‌توانیم رویکرد «بد» را بگیریم و سعی کنیم کاستی‌هایش را اصلاح کنیم.

اول، برای حل مشکل کهنگی Heap، می‌توانیم به Heap یک فیلد «قدیمی‌ترین افزایش» (Oldest Increment) اضافه کنیم. در آن قدیمی‌ترین مهر زمانی در مجموعه‌ای را که شمارش کل پنجره را ساخته ذخیره می‌کنیم. قبل از کوئری، باید روی Heap ها پیمایش کنیم و ورودی‌های «کهنه» را بررسی کنیم و با جمع کردن دوباره پنجره‌های زمانی سازنده‌شان آن‌ها را بازخوانی کنیم. بعد از «تازه» شدن Heap می‌توانیم K برتر را برگردانیم. (توجه: گاهی این فرایند به‌روزرسانی ممکن است ورودی‌ای را از Top-K که قبلاً در آن بود بیرون بیندازد، پس باید Heap را بزرگ‌تر از K نگه داریم، مثلاً 2000 به‌جای 1000.)

بعد، برای مقابله با هزینه تجمیع‌ها می‌توانیم چند دانه‌بندی (Granularity) نگه داریم. علاوه بر دانه‌بندی 1 دقیقه‌ای، ممکن است نصف هر بازه (30 دقیقه، 12 ساعت، 15 روز) را هم نگه داریم. برای این کار ذخیره‌سازی را (به‌دلیل پراکندگی دانه‌بندی‌های پایین‌تر کمی بیشتر از) 3 برابر می‌کنیم، اما تعداد خواندن‌هایی را که برای هر درخواست مشخص لازم داریم به‌طور چشمگیری کم می‌کنیم. حالا به‌جای تلاش برای جمع کردن 1 ماه دقیقه (حدود 43 هزار)، می‌توانیم (1×15 روز + 29×12 ساعت + 23×30 دقیقه + 29×1 دقیقه) یعنی 82 ورودی را جمع کنیم. بد نیست.

در نهایت، به راهی برای مقابله با باد کردن حافظه نیاز داریم. مطمئناً می‌توانیم داده قدیمی‌تر از 1 ماه را منقضی کنیم، چون دیگر به آن نیاز نداریم. اما ممکن است برای تکمیل پنجره‌مان به داده 1 دقیقه‌ای 30 روز پیش نیاز داشته باشیم. آخ! مشکلات Retention. توجه کنید که برای تکمیل کل پنجره به چند ثانیه نیاز داریم.

چالش‌ها: این راه‌حل پیچیده است. تا حدی مشکل کهنگی Heap را حل کردیم، اما در زمان خواندن ممکن است بسیاری از محتویات آن را بازسازی کنیم. عملکرد تجمیع را خیلی بهتر کردیم، اما هنوز باید دانه‌بندی 1 دقیقه‌ای را برای یک ماه کامل نگه داریم. در این فرایند، سیستمی ساخته‌ایم که می‌تواند به سؤال‌های مربوط به شمارش بازه‌های زمانی دلخواه پاسخ بدهد، اما به آن نیازی نداریم!

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

رویکرد عالی: دو نشانگر روی جریان (لبه بالارونده و پایین‌رونده)

چون از جریان بادوامی مثل Kafka می‌خوانیم، می‌توانیم اشاره‌گرهایی داشته باشیم که پیام‌ها را با Offset های مختلف می‌کشند. یک «لبه بالارونده» (Rising Edge) خواهیم داشت، یعنی زمانی که شمارش را افزایش می‌دهیم، و 3 «لبه پایین‌رونده» (Falling Edge)، یعنی زمانی که شمارش را کاهش می‌دهیم. برای لبه‌های پایین‌رونده، خواندن از جریان را از Offset مناسب (مثلاً 1 ساعت، 1 روز، 1 ماه قبل) شروع می‌کنیم و وقتی به ورودی جدیدتر از «زمان فعلی منهای آن بازه» رسیدیم، مکث می‌کنیم. این یعنی راهی داریم که در زمان مناسب شمارش را بالا و پایین ببریم.

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

باید شمارش‌های جداگانه برای هر پنجره زمانی نگه داریم (پس ذخیره‌سازی را 4 برابر می‌کنیم) و همچنین Heap های Top-K جداگانه. اما شمارش‌ها هرگز کهنه نخواهند بود. با نگه داشتن نشانگرهایی در جریان که به اندازه پنجره زمانی عقب‌اند، می‌توانیم وقتی آن بازدیدها از پنجره زمانی بیرون می‌افتند شمارش را کاهش بدهیم.

بیایید یک مثال را حل کنیم. فرض کنید دنباله اقدام‌های زیر رخ بدهد:

• در ساعت 0:05، بازدیدی از ویدیو A
• در ساعت 0:20، بازدیدی از ویدیو B
• در ساعت 0:40، بازدیدی از ویدیو B

حالا می‌توانیم وضعیت سیستم را در زمان‌های مختلف مرور کنیم.

در ساعت 0:00، همه Heap های ما خالی‌اند و شمارش‌ها 0 هستند.

• شمارنده 1 ساعت: شمارش: { }، لبه پایین‌رونده در -1:00
• شمارنده 1 روز: شمارش: { }، لبه پایین‌رونده در -24:00
• شمارنده همه زمان‌ها: شمارش: { }، بدون لبه پایین‌رونده

در ساعت 0:05، بازدید جدیدی به بالای جریان می‌رسد. این برای همه بازه‌های زمانی یک رویداد لبه بالارونده است. در این مرحله شمارش هر پنجره زمانی (1 ساعت، 1 روز، 1 ماه، همه زمان‌ها) را افزایش می‌دهیم.

• شمارنده 1 ساعت: شمارش: { A: 1 }، لبه پایین‌رونده در -0:55
• شمارنده 1 روز: شمارش: { A: 1 }، لبه پایین‌رونده در -23:55
• شمارنده همه زمان‌ها: شمارش: { A: 1 }، بدون لبه پایین‌رونده

در ساعت 0:20، بازدید جدید دیگری داریم. باز هم یک رویداد لبه بالارونده برای همه بازه‌هاست و شمارش هر پنجره زمانی را افزایش می‌دهیم.

• شمارنده 1 ساعت: شمارش: { A: 1, B: 1 }، لبه پایین‌رونده در -0:40
• شمارنده 1 روز: شمارش: { A: 1, B: 1 }، لبه پایین‌رونده در -23:40
• شمارنده همه زمان‌ها: شمارش: { A: 1, B: 1 }، بدون لبه پایین‌رونده

در ساعت 0:40، دوباره بازدیدی از B.

• شمارنده 1 ساعت: شمارش: { A: 1, B: 2 }، لبه پایین‌رونده در -0:20
• شمارنده 1 روز: شمارش: { A: 1, B: 2 }، لبه پایین‌رونده در -23:20
• شمارنده همه زمان‌ها: شمارش: { A: 1, B: 2 }، بدون لبه پایین‌رونده

در ساعت 1:05 جالب می‌شود. نشانگر لبه پایین‌رونده 1 ساعته ما حالا رویدادی را می‌خواند که در 0:05 رخ داده بود (بازدید از A). یعنی این شمارش را برای شمارنده ساعت کم می‌کنیم، که همان چیزی است که انتظار داریم، چون آن بازدید بیرون از پنجره منقضی شده. شمارش‌های روزانه دست‌نخورده می‌مانند.

• شمارنده 1 ساعت: شمارش: { B: 2 }، لبه پایین‌رونده در 0:05
• شمارنده 1 روز: شمارش: { A: 1, B: 2 }، لبه پایین‌رونده در -22:55
• شمارنده همه زمان‌ها: شمارش: { A: 1, B: 2 }، بدون لبه پایین‌رونده

در ساعت 1:20، همین اتفاق برای یکی از بازدیدهای B رخ می‌دهد. لبه پایین‌رونده به 0:20 رسیده، رویدادی را می‌خواند که بازدیدی رخ داده و کم می‌کند، چون این وظیفه نشانگر لبه پایین‌رونده ماست.

• شمارنده 1 ساعت: شمارش: { B: 1 }، لبه پایین‌رونده در 0:20
• شمارنده 1 روز: شمارش: { A: 1, B: 2 }، لبه پایین‌رونده در -22:40
• شمارنده همه زمان‌ها: شمارش: { A: 1, B: 2 }، بدون لبه پایین‌رونده

و در ساعت 1:40، آخرین بازدید B برای پنجره ساعتی منقضی می‌شود.

• شمارنده 1 ساعت: شمارش: { }، لبه پایین‌رونده در 0:40
• شمارنده 1 روز: شمارش: { A: 1, B: 2 }، لبه پایین‌رونده در -22:20
• شمارنده همه زمان‌ها: شمارش: { A: 1, B: 2 }، بدون لبه پایین‌رونده

در نهایت، برای نمایش، در ساعت 24:05 بازدیدی را که در 0:05 رخ داده بود از پنجره 1 روزه منقضی می‌کنیم.

• شمارنده 1 ساعت: شمارش: { }، لبه پایین‌رونده در 23:05
• شمارنده 1 روز: شمارش: { B: 2 }، لبه پایین‌رونده در 0:05
• شمارنده همه زمان‌ها: شمارش: { A: 1, B: 2 }، بدون لبه پایین‌رونده

چالش‌ها: این یک نیازمندی سخت برای پردازش جریان ما می‌سازد: دست‌کم یک ماه Retention (به‌علاوه زمان از آخرین Snapshot) لازم داریم. اگرچه احتمالاً دست‌کم چند روز را برای بازیابی از بحران نگه می‌داریم، این هزینه استقرار Kafka را به‌طور چشمگیری بالا می‌برد. همچنین بار خواندن را 4 برابر کرده‌ایم.

چون ممکن است ویدیوها از 1000 مورد برتر بیرون بیفتند، باید مطمئن شویم Heap های ما به‌طور قابل توجهی بیش از 1000 مورد (مثلاً 2000) نگه می‌دارند تا با «منقضی شدن بازدیدهای قدیمی»، برای ورودی‌های جدید در بالای فهرست جا باز شود.

2) تعداد زیاد درخواست‌های ورودی

تا حالا درباره مدیریت تعداد زیاد بازدید (نوشتن) صحبت کرده‌ایم، اما خواندن چه؟ چون بین زمان رخ دادن بازدید و زمان لازم برای جدول‌بندی آن 1 دقیقه زمان داریم، طبیعی‌ترین راه‌حل اضافه کردن کش است. می‌توانیم یک TTL یک‌دقیقه‌ای روی کش بگذاریم تا نتایج هرگز بیش از آنچه لازم داریم کهنه نشوند. وقتی درخواستی می‌رسد، می‌توانیم آن را از کش سرو کنیم یا از همه Counter ها برای Heap شان کوئری بگیریم و بعد مقدارهای ادغام‌شده را دوباره در کش ذخیره کنیم.

طراحی کامل ما شامل این اجزاست: جریان بازدید (Kafka)، Worker های Counter Shard شده با Consistent Hashing و Replica ها، Snapshot ها، نشانگرهای لبه بالارونده و پایین‌رونده برای هر پنجره زمانی، سرویس Top-K که Heap ها را ادغام می‌کند، رجیستری (ZooKeeper) و کش با TTL یک‌دقیقه‌ای جلوی سرویس.

انتظارات در هر سطح

شاید فکر کنید «واقعاً چقدر از این‌ها در مصاحبه لازم است؟» بیایید تفکیک کنیم.

سطح Mid-level

• عرض در برابر عمق: تمرکز بیشتر روی عرض است (حدود 80 درصد عرض و 20 درصد عمق). باید بتوانید طراحی سطح بالایی بسازید که نیازمندی‌های عملکردی تعریف‌شده را پوشش بدهد، هرچند با بسیاری از اجزا فقط آشنایی سطحی داشته باشید.
• مرور مبانی: مصاحبه‌کننده مدتی را صرف بررسی مبانی می‌کند تا مطمئن شود می‌دانید هر جزء چه کاری می‌کند. مثلاً اگر API Gateway اضافه کنید، انتظار داشته باشید بپرسد چه کاری می‌کند و در سطح بالا چطور کار می‌کند. او هیچ چیز را بدیهی فرض نمی‌کند.
• ترکیب هدایت و همراهی: در مراحل اولیه مصاحبه باید خودتان جلو بروید، اما مصاحبه‌کننده انتظار ندارد مشکلات طراحی را با دقت بالا پیش‌دستانه تشخیص بدهید. طبیعی است که در مراحل بعد، با بررسی طراحی شما، خودش هدایت را به دست بگیرد.
• معیار برای Top K: داوطلب Mid-level می‌تواند راه‌حلی ارائه کند که احتمالاً بهینه نیست. او درباره نقاط ضعف سیستم بینش‌هایی خواهد داشت و می‌تواند بعضی از آن‌ها را حل کند. با فناوری‌های مربوط آشنا خواهد بود.

سطح Senior

• عمق تخصص: انتظار به سمت دانش عمیق‌تر می‌رود، حدود 60 درصد عرض و 40 درصد عمق. باید در حوزه‌هایی که تجربه عملی دارید وارد جزئیات فنی شوید و درک عمیقی از مفاهیم و فناوری‌های کلیدی مسئله نشان بدهید.
• طراحی سیستم پیشرفته: باید با اصول پیشرفته طراحی سیستم آشنا باشید. مثلاً دانستن نحوه استفاده از Consistent Hashing برای مقیاس‌دهی الاستیک داده پارتیشن‌بندی‌شده. همچنین انتظار می‌رود بفهمید جریان رویداد مبتنی بر Log (مثلاً Kafka یا Redis Streams) چطور کار می‌کند. توانایی شما در حرکت با اطمینان و وضوح در این موضوع‌های پیشرفته کلیدی است.
• تشریح تصمیم‌های معماری: باید مزایا و معایب انتخاب‌های معماری را روشن بیان کنید، به‌ویژه اثر آن‌ها روی مقیاس‌پذیری، عملکرد و قابلیت نگهداری، و تصمیم‌هایتان را توجیه کنید.
• حل مسئله و پیش‌قدمی: باید مهارت حل مسئله قوی و رویکرد فعالانه نشان بدهید. یعنی چالش‌های احتمالی طراحی را پیش‌بینی کنید، بهبود پیشنهاد بدهید، گلوگاه‌ها را پیدا و رفع کنید، عملکرد را بهینه کنید و از قابلیت اطمینان سیستم مطمئن شوید.
• معیار برای Top K: داوطلب Senior باید بتواند راه‌حلی ارائه کند که تقریباً بهینه است. او بیشتر گلوگاه‌ها را شناسایی می‌کند و فعالانه برای حل آن‌ها تلاش می‌کند. با فناوری‌های مربوط آشناست و حتی ممکن است مزایا و معایب هرکدام را بسنجد.

سطح Staff به بالا

• تأکید بر عمق: انتظار می‌رود وارد ظرافت‌های طراحی سیستم شوید، با حدود 40 درصد عرض و 60 درصد عمق. حتی اگر این مسئله خاص را قبلاً حل نکرده باشید، باید در دنیای واقعی آن‌قدر مسئله حل کرده باشید که با پشتوانه تجربه‌تان با اطمینان راه‌حل طراحی کنید.
• دانش عملی فناوری‌ها: باید بدانید از چه فناوری‌هایی استفاده کنید، نه فقط در تئوری بلکه در عمل، و با تجربه‌های قبلی توضیح بدهید چطور برای حل مسائل خاص به کار می‌روند. مصاحبه‌کننده می‌داند مباحث ساده‌تر (کش، ذخیره‌ساز کلید-مقدار و غیره) را می‌دانید، پس سریع از آن‌ها عبور می‌کنید تا برای بخش‌های جذاب‌تر وقت بماند.
• پیش‌قدمی بالا: انتظار می‌رود مسائل را مستقل شناسایی و حل کنید و چالش‌های اصلی طراحی را بشناسید. این فقط پاسخ به مشکلات پس از بروز نیست، بلکه پیش‌بینی آن‌ها و اجرای راه‌حل‌های پیشگیرانه هم هست. مصاحبه‌کننده فقط باید برای تمرکز دخالت کند، نه برای هدایت.
• کاربرد عملی فناوری: باید در به‌کارگیری عملی فناوری‌های مختلف مسلط باشید. تجربه شما باید گفت‌وگو را هدایت کند و درک روشنی از پیکربندی ابزارها و سیستم‌ها در سناریوهای واقعی نشان بدهد.
• حل مسئله پیچیده و تصمیم‌گیری: نه‌تنها باید چالش‌های فنی پیچیده را حل کنید، بلکه تصمیم‌های آگاهانه‌ای بگیرید که مقیاس‌پذیری، عملکرد، قابلیت اطمینان و نگهداری را در نظر می‌گیرد.
• طراحی پیشرفته و مقیاس‌پذیری: رویکرد شما باید بر مقیاس‌پذیری و قابلیت اطمینان در بار بالا متمرکز باشد. این شامل درک کامل سیستم‌های توزیع‌شده، Load Balancing، استراتژی‌های ذخیره‌سازی و دیگر مفاهیم پیشرفته است.
• معیار برای Top K: برای داوطلب Staff به بالا، انتظار از عمق و کیفیت راه‌حل‌ها بالاست، به‌ویژه برای سناریوهای پیچیده‌ای که بحث شد. او همه بررسی‌های عمیقی را که فهرست کردیم پوشش می‌دهد.