پست

طراحی سیستم Online Chess

طراحی پلتفرم شطرنج آنلاین شامل Matchmaking مبتنی بر مهارت و بازی بلادرنگ با WebSocket و ساعت عادلانه و Leaderboard

طراحی سیستم Online Chess

درک مسئله

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

اگر زیاد شطرنج بازی نمی‌کنید، این مقدمه‌ی کوتاه را بخوانید. دو بازیکن به‌نوبت روی تخته‌ی مشترک حرکت می‌کنند و هر طرف ساعت شمارش معکوس خودش را دارد که با Time Control تعیین می‌شود. بازی‌ها از کلاسیک با ساعت‌ها برای هر طرف تا یک دقیقه برای هر طرف در Blitz و Bullet متغیر است، که در آن‌ها بازیکنان فقط ثانیه‌هایی برای هر حرکت دارند و هر تأخیری از ساعتشان کم می‌کند.

بازیکنان همچنین رتبه‌ی مهارتی دارند که تعیین می‌کند با چه کسی جفت شوند و کجای جدول رتبه‌بندی قرار بگیرند. اول یک بازی تنها را می‌سازیم، بعد Deep Dive ها را برای بخش‌هایی که در مقیاس دشوار می‌شوند استفاده می‌کنیم. یعنی Matchmaking، اجرای ناوگان بزرگ سرور بازی، و عادلانه نگه داشتن ساعت بین بازیکنان با Latency شبکه‌ی متفاوت.

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

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

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

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

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

  • تماشای زنده‌ی بازی‌ها و پخش تخته‌های محبوب.
  • چت داخل بازی، دوستان و قابلیت‌های اجتماعی.
  • معما، آموزش و تحلیل یا Replay بعد از بازی.
  • تورنمنت و بازی Arena.
  • ضد تقلب و تشخیص موتور (Fair Play)، به‌علاوه‌ی یکپارچگی تورنمنت. در پایان توضیح می‌دهیم چرا جالب است ولی خارج از محدوده.

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

پیش از نیازمندی‌ها، مقیاس را مشخص کنیم، چون بیشتر طراحی را هدایت می‌کند. برای ۵۰۰ هزار بازی هم‌زمان در اوج طراحی می‌کنیم. هر بازی دو بازیکن روی اتصال‌های جدا دارد، پس ( 500K \times 2 = 1M ) اتصال هم‌زمان، به‌علاوه‌ی محاسبات برای اعتبارسنجی هر حرکت و اجرای دو ساعت در هر بازی. این اعداد در Deep Dive ها ادامه پیدا می‌کنند.

با این در ذهن، نیازمندی‌های غیرعملکردی:

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

  • انتشار حرکت با Latency کم، زیر ۲۰۰ میلی‌ثانیه سرتاسری. در بازی‌های Bullet و Blitz بازیکنان ثانیه‌هایی برای هر حرکت دارند، پس حرکت باید تقریباً فوراً روی تخته‌ی حریف بنشیند وگرنه بازی خراب احساس می‌شود.
  • Consistency بر Availability برای State بازی. اگر سرور بازی در دسترس نباشد، بازی باید متوقف شود، نه اینکه دو کلاینت به موقعیت‌های متفاوت تخته انحراف پیدا کنند، چون بازی متوقف‌شده قابل بازیابی است و بازی خراب نه.
  • مقیاس برای ۵۰۰ هزار بازی هم‌زمان (۱ میلیون اتصال) در اوج.

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

  • امنیت حساب و جلوگیری از سوءاستفاده فراتر از Fair Play.
  • Compliance مربوط به GDPR و حریم خصوصی داده.
  • پایش، لاگ و هشداردهی.
  • CI/CD و Deploy بدون Downtime.

روی تخته‌سفید ممکن است این‌طور باشد:

  • عملکردی: پیدا کردن حریف با Matchmaking مبتنی بر مهارت، بازی بلادرنگ با حرکت‌های اعتبارسنجی‌شده‌ی سرور، دیدن Leaderboard سراسری.
  • غیرعملکردی: حرکت با Latency کم (زیر ۲۰۰ میلی‌ثانیه سرتاسری)، Consistency مهم‌تر از Availability (متوقف کن، منحرف نشو)، مقیاس ۵۰۰ هزار بازی هم‌زمان (حدود ۱ میلیون اتصال).

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

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

بازی بلادرنگ قلب سیستم است و جایی که سرور بازی وارد می‌شود، پس بیشترین توجه را می‌گیرد. وقتی سه نیازمندی سرتاسری کار کردند، نیازمندی‌های غیرعملکردی (مقیاس، Latency کم و ساعت عادلانه) چیزی است که در Deep Dive ها می‌کاویم.

تعریف Entityهای اصلی

با فهرست کوتاهی از اسم‌های لازم برای طراحی API و مدل ذخیره‌سازی شروع می‌کنیم. هنوز ستون لازم نداریم، فقط واژگان کافی برای صحبت درباره‌ی API و طراحی.

  • Player: کاربر ثبت‌نام‌شده، با هویت و رتبه‌ی مهارتش (ELO). رتبه است که هم Matchmaking و هم جایگاه روی Leaderboard را هدایت می‌کند.
  • Game: یک بازی شطرنج بین دو بازیکن. ردیابی می‌کند چه کسی چه رنگی بازی می‌کند، موقعیت فعلی تخته، نوبت چه کسی است، وضعیت ساعت و نتیجه پس از پایان.
  • Move: یک حرکت در بازی (مربع مبدأ، مربع مقصد، شماره‌ی حرکت، Timestamp). حرکت‌ها تاریخچه‌ی Append-only بازی را می‌سازند، که برای Replay و حل اختلاف لازم است.
  • MatchRequest: درخواست بازیکن برای جفت شدن، با رتبه و Time Control ترجیحی‌اش. Time Control یعنی هر طرف چقدر زمان در ساعت دارد، مثل ۳ دقیقه برای هر طرف به‌علاوه‌ی ۲ ثانیه اضافه برای هر حرکت، و بازیکنان فقط می‌خواهند با کسی جفت شوند که همان را انتخاب کرده. اسم بدیهی در طراحی است و جدا نگه داشتنش از Game به Matchmaking چیزی می‌دهد که روی آن بنا شود.

ELO فقط یک عدد است که وقتی می‌برید بالا می‌رود و وقتی می‌بازید پایین می‌آید، و وقتی بازیکن قوی‌تر را ببرید بیشتر. این و جزئیات Time Controlهای شطرنج دانش لازم برای مصاحبه نیستند. مصاحبه‌کننده یا برایتان توضیح می‌دهد یا کلاً رد می‌شود. برای دقت اینجا آورده‌ایم ولی روی جزئیات بازی گیر نکنید.

روی تخته‌سفید می‌توانید Entityها را فقط این‌طور یادداشت کنید: Player، Game، Move، MatchRequest.

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

دو نوع تعامل کاملاً متفاوت داریم. Matchmaking و Leaderboard درخواست/پاسخ معمولی‌اند، پس به‌صورت فراخوانی REST منطقی‌اند. بازی تبادل پیوسته‌ی رفت‌وبرگشتی بین دو بازیکن و سرور است، پس روی WebSocket سوار می‌شود. اول سطح REST را طراحی می‌کنیم و بعد پیام‌هایی را که روی Socket جریان دارند توضیح می‌دهیم.

برای درخواست بازی، بازیکن Time Control ترجیحی‌اش را به ما می‌گوید. از POST استفاده می‌کنیم چون MatchRequest جدیدی می‌سازیم که سیستم به‌صورت Asynchronous روی آن کار خواهد کرد:

1
2
3
4
5
6

POST /matchmaking -> MatchRequest
Body: {
  timeControl    // e.g. "blitz-3-2" = 3 min each, +2s per move
}

- the playerId comes from the auth token, never the body or query params

توجه کنید playerId در Body نیست. هویت بازیکن همیشه از Session یا JWT می‌آید، هرگز از داده‌ای که کلاینت می‌فرستد. همیشه می‌بینم نامزدها userId یا، بدتر، رتبه‌ی خودشان را در Body درخواست می‌فرستند و هشدار است. هر چیزی که کلاینت بتواند درباره‌اش دروغ بگوید تا حریف ساده‌تری بگیرد باید از سرور بیاید. رتبه از رکورد Player خوانده می‌شود، نه اینکه از درخواست قبول شود.

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

1
2
3
4
5
6
7
8
9

WS /games/:gameId

Client -> Server:
  sendMove   { from, to, moveNumber }

Server -> Client:
  moveAck       { accepted, reason?, whiteTimeMs, blackTimeMs }
  opponentMove  { from, to, whiteTimeMs, blackTimeMs }
  gameEnd       { result }

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

در نهایت، Leaderboard یک خواندن است. بازیکنان را مرتب‌شده بر اساس رتبه صفحه‌بندی می‌کنیم و بازیکن رتبه‌ی خودش را هم می‌خواهد، پس دو GET داریم:

1
2

GET /leaderboard?cursor={cursor}&limit={limit} -> Player[]
GET /players/:playerId/rank -> { rank, rating }

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

۱) بازیکنان بتوانند از طریق Matchmaking مبتنی بر مهارت حریف پیدا کنند و بازی را شروع کنند

از جایی که بازیکن شروع می‌کند شروع می‌کنیم. بازی می‌خواهد، پس اول او را با کسی نزدیک در مهارت جفت می‌کنیم و Game ای می‌سازیم که آن دو بازی کنند. یک سرویس و یک جدول اضافه می‌کنیم:

  • Matchmaking Service: درخواست‌های بازی را می‌گیرد، دو بازیکن سازگار پیدا می‌کند و رکورد Game را می‌سازد که مسیر بازی آن را برمی‌دارد.
  • جدول MatchRequest: درخواست‌های در انتظار را با رتبه و Time Control انتخابی هر بازیکن نگه می‌دارد.

جریان ساده:

  1. کلاینت بازیکن POST به Matchmaking Service با Time Control می‌فرستد.
  2. سرویس MatchRequest با رتبه‌ی بازیکن (سمت سرور جستجو می‌شود) و وضعیت pending می‌سازد.
  3. درخواست در انتظار دیگری با همان Time Control و رتبه‌ای در بازه‌ای مثلاً ±۲۰۰ را Query می‌کند.
  4. اگر یکی پیدا شد، Game ای با هر دو بازیکن می‌سازد، هر دو درخواست را matched علامت می‌زند و gameId را به هرکدام برمی‌گرداند تا WebSocket بازی را باز کنند.

نکته‌ی قابل‌توجه این است که POST مربوط به Matchmaking یک Long-poll است. لحظه‌ای که درخواست ساخته می‌شود برنمی‌گردد؛ باز نگه داشته می‌شود تا بازیکن واقعاً جفت شود (یا انتظار Timeout بخورد). پس بازیکنی که Match را فعال می‌کند و بازیکنی که از قبل در Pool نشسته بود، هر دو جوابشان را روی همان درخواست باز می‌گیرند.

اگر کسی برای جفت شدن نباشد، درخواست pending با Long-poll باز می‌ماند. وقتی بازیکن سازگاری بعداً می‌رسد و با آن جفت می‌شود، همان درخواست باز دقیقاً چیزی است که کامل می‌شود. بازیکن منتظر لحظه‌ای که برداشته شد می‌فهمد، بدون کانال اعلان جداگانه.

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

برای پلتفرم ساکت این به‌اندازه‌ی کافی ساده است. اما در اوج از Pool با صدها هزار بازیکن جفت می‌کنیم و گام ۳ برای هر درخواست Query روی جدول مشترک است. در همان گام یک Race هم کمین کرده است. دو Matcher می‌توانند در یک لحظه همان بازیکن در انتظار را بخوانند و هر دو جفتش کنند، که آن بازیکن را در دو بازی هم‌زمان رزرو دوگانه می‌کند. پس جدول تحمل نمی‌کند، ادعا باید در برابر آن Race ایمن شود و بازیکنان در حدود افراطی رتبه برای همیشه برای هم‌ردیف منتظر می‌مانند. همه‌ی این مشکلات را بعداً در Deep Dive مربوط به Matchmaking بررسی می‌کنیم.

۲) بازیکنان بتوانند بازی را بلادرنگ انجام دهند

Matchmaking تازه دو بازیکن را جفت و Game را ساخت. حالا به مسیری نیاز داریم که واقعاً بازی کنند، با سرور به‌عنوان تنها منبع حقیقت برای تخته و ساعت‌ها.

باید سرور جدیدی اضافه کنیم، یعنی Game Service، که آن State معتبر را داشته باشد. حرکت‌های ورودی را اعتبارسنجی می‌کند، دو ساعت را مدیریت می‌کند و حرکت‌های اعتبارسنجی‌شده را به حریف Push می‌کند.

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

جریان حرکت وقتی هر دو بازیکن وصل‌اند:

  1. وقتی بازی ساخته می‌شود، کلاینت هر بازیکن WebSocket به Game Service ای که بازی‌اش را در حافظه دارد باز می‌کند و سرویس آن اتصال را با جایگاه بازیکن در بازی مرتبط می‌کند.
  2. بازیکن مهره را می‌کشد و کلاینتش پیام sendMove را روی WebSocket با مربع‌های مبدأ و مقصد می‌فرستد.
  3. Game Service آن را می‌گیرد و در برابر تخته‌ی درون‌حافظه اعتبارسنجی می‌کند: حرکت شطرنج قانونی است و واقعاً نوبت این بازیکن است.
  4. اگر قانونی بود، سرویس تخته‌ی درون‌حافظه را به‌روز می‌کند، ساعت بازیکن حرکت‌کننده را متوقف و ساعت حریف را شروع می‌کند.
  5. سرویس حرکت را به لاگ حرکت ماندگار Append می‌کند تا بازی بعد از Crash قابل بازیابی باشد.
  6. opponentMove را به بازیکن دیگر و moveAck را به حرکت‌کننده Push می‌کند، هرکدام با زمان‌های معتبر ساعت تا هر دو طرف همگام بمانند. حرکت غیرقانونی moveAck رد‌کننده می‌گیرد و هیچ‌چیز تغییر نمی‌کند.
  7. وقتی بازی با مات، پات یا تساوی دیگر، یا Flag (تمام شدن زمان) تمام می‌شود، سرویس نتیجه را می‌نویسد و gameEnd را به هر دو بازیکن می‌فرستد. مات و تساوی‌های خودکار از همان اعتبارسنجی حرکتی که مالک قوانین است نتیجه می‌شوند.

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

توجه کنید گام ۵ پیش از گام ۶ است. حرکت را پیش از Broadcast ماندگار می‌کنیم. اگر ابتدا به حرکت‌کننده Ack بدهیم یا به حریف Push کنیم و بعد Crash کنیم، بازیابی با تخته‌ای برمی‌گردد که حرکتی را که هر دو بازیکن دیده‌اند ندارد. دقیقاً همان State خراب است که گفتیم متوقف کردن را به اجازه دادنش ترجیح می‌دهیم. می‌توانیم همگام ماندگار کنیم چون بودجه‌ی ۲۰۰ میلی‌ثانیه به‌راحتی نوشتن چند میلی‌ثانیه‌ای را جذب می‌کند، پس درستی عملاً رایگان است.

الگو، Real-time Updates: Push کردن هر حرکت اعتبارسنجی‌شده به حریف در لحظه‌ی پذیرفتن، مسئله‌ی کتاب‌درسی به‌روزرسانی بلادرنگ است. تحلیل الگوی ما توضیح می‌دهد چرا WebSocket پایدار وقتی هر دو طرف پیوسته می‌فرستند و می‌گیرند از Polling یا SSE بهتر است، که دقیقاً شکل یک بازی شطرنج است.

۳) بازیکنان بتوانند Leaderboard سراسری را ببینند و رتبه‌ی خودشان را ببینند

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

  • وقتی بازی تمام می‌شود، Game Service ELO جدید (رتبه‌بندی شطرنج) را برای هر دو بازیکن از نتیجه و رتبه‌ی هر بازیکن در شروع بازی محاسبه می‌کند. آن رتبه‌های شروع بازی روی Game Snapshot می‌شوند، چون Delta مربوط به ELO از آن‌ها محاسبه می‌شود. سرویس بعد رتبه‌ی هر بازیکن را در جدول Players به‌روز می‌کند.
  • Endpoint مربوط به Leaderboard جدول Players را مرتب‌شده بر اساس رتبه‌ی نزولی با Cursor Pagination و Index روی ستون رتبه می‌خواند. رتبه‌ی خود بازیکن شمارش تعداد بازیکنانی است که بالاتر از رتبه‌ی او هستند.

چون رتبه‌ها فقط وقتی بازی تمام می‌شود تغییر می‌کنند، Leaderboard به‌طور طبیعی تازه است، بدون چیز پیچیده‌ای. و صفحه‌ی بالا بسیار ارزان بارگذاری می‌شود. با Index از نوع B-tree روی رتبه، ORDER BY rating DESC LIMIT 50 فقط پنجاه ورودی اول Index را می‌پیماید و می‌ایستد، پس حتی ۱۰ میلیون بازیکن هم در Postgres سریع مرتب می‌شوند. از تعداد ردیف نترسید.

جایی که می‌شکند رتبه‌ی خود بازیکن است. SELECT COUNT(*) FROM players WHERE rating > :myRating باید هر ردیف بالای شما را بشمارد. B-tree ساده ترتیب مرتب می‌دهد ولی موقعیت نه، پس میان‌بر ( O(\log n) ) برای «شما بازیکن 4,201,930 هستید» نیست.

این شمارش ( O(\text{rank}) ) است، برای بازیکنان وسط جدول، که بیشتر درخواست‌ها را می‌سازند، کندترین است، و یکی از پربازدیدترین خواندن‌های سایت است. گزینه‌هایی برای سریع‌تر کردنش را در Deep Dive ها می‌گوییم.

این سیستم کارایی می‌دهد. بازیکنان جفت می‌شوند، بازی بلادرنگ اعتبارسنجی‌شده انجام می‌دهند و در Leaderboard بالا می‌روند. حالا گلوگاه‌ها. سراغشان برویم.

Deep Dive های احتمالی

اینکه چقدر باید این‌ها را هدایت کنید تابعی از ارشدیت است. نامزد Mid-level می‌تواند تکیه کند که مصاحبه‌کننده به سمت مسائل جالب هدایتش کند. از نامزد Senior یا Staff انتظار می‌رود دور گوشه‌ها را ببیند و این گلوگاه‌ها را پیش از پرسیده شدن نام ببرد.

۱) چطور بازیکنان را منصفانه در مقیاس Match کنیم؟

در اوج گفتیم ۵۰۰ هزار بازی هم‌زمان داریم که یعنی ۱ میلیون بازیکن در بازی‌های فعال در هر لحظه. بیشتر شطرنج با Time Controlهای سریع بازی می‌شود، جایی که بازی Bullet یا Blitz چند دقیقه طول می‌کشد و بازیکنان معمولاً به محض پایان بازی دوباره وارد صف می‌شوند. پس تقریباً ۱ میلیون بازیکن که هرکدام هر ~۱۲۰ ثانیه درخواست بازی تازه شروع می‌کنند، فقط از جمعیت بازیکنان فعال ( 1M / 120 \approx 8k ) درخواست بازی جدید در ثانیه است. بازیکنان تازه‌رسیده و اوج‌های شبانه و تورنمنت را اضافه کنید و به ده‌ها هزار در ثانیه می‌رسد.

با این نرخ، اسکن جدول در هر درخواست دیگر جواب نمی‌دهد، چون Match جستجوی نقطه‌ای نیست. جستجوی بازه‌ای برای نزدیک‌ترین رتبه‌ی سازگار در همان Time Control است، و بعد Read-modify-write برای ادعای آن حریف پیش از اینکه Matcher دیگری بگیردش.

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

بازیکنان در دم منحنی مشکل مخالف دارند، چون امتیاز ۲۷۰۰ (واقعاً خوب!) ممکن است در هر لحظه فقط سه یا چهار هم‌ردیف آنلاین داشته باشد. بازه‌ی جستجویشان باید خیلی گسترش یابد تا کسی را در بر بگیرد. تا وقتی بگیرد، بازی با کسی ۵۰۰ امتیاز ضعیف‌تر به آن‌ها می‌دهیم که واقعاً بازی نیست.

الگو، Dealing with Contention: دو Worker Matchmaking می‌توانند همان لحظه یک بازیکن در انتظار را ببینند و هر دو سعی کنند جفتش کنند، که آن بازیکن را در دو بازی رزرو دوگانه می‌کند. این مسئله‌ی Contention است و الگوی ما تکنیک‌های ادعای Atomic را پوشش می‌دهد که تضمین می‌کنند دقیقاً یک Worker برنده شود.

رویکرد اول، ساختار درون‌پروسسی: بازیکنان در انتظار را از پایگاه داده بیرون بکشید و در ساختار مرتب (بر اساس رتبه، یکی برای هر Time Control) در حافظه‌ی پروسس خود Matchmaker نگه دارید. درخواست جدید در پنجره‌ای اطراف رتبه‌اش Binary Search می‌کند و با نزدیک‌ترین بازیکن در انتظار جفت می‌شود. چون همه در یک پروسس زندگی می‌کند، Match یک Read-modify-write محلی بدون پرش شبکه و بدون Race است. فقط باید مطمئن شوید هم‌زمانی چندنخی را مدیریت کنید که به‌اندازه‌ی کافی ساده است.

چالش‌ها: فقط به‌صورت پروسس واحد کار می‌کند. به محض اینکه Matchmaker دوم را برای Throughput (که در این مقیاس لازم داریم) یا Failover اجرا کنیم، آن دو درباره‌ی اینکه چه کسی منتظر است ایده‌های متفاوت دارند. شروع می‌کنند به رزرو دوگانه‌ی بازیکنان یا از دست دادن Matchها. کل Pool در انتظار هم در Heap همان یک پروسس زندگی می‌کند، پس Crash یا Deploy روتین همه‌ی کسانی را که الان در صف هستند می‌اندازد. تصویر مفیدی از چیزی است که می‌خواهیم ساختار داده انجام دهد، ولی نمی‌توانیم چیز واقعی را روی یک جعبه اجرا کنیم.

رویکرد دوم، Postgres با SKIP LOCKED: جایگزین این است که درخواست‌های در انتظار را در پایگاه داده بگذاریم و بگذاریم Matchmakerها آن‌ها را آنجا با SKIP LOCKED ادعا کنند. Matcher درخواست‌های سازگار را در پنجره‌ی رتبه‌اش، مرتب‌شده بر اساس نزدیکی به رتبه‌ی خودش، Query می‌کند و اولین ردیفی را که برمی‌گردد می‌گیرد.

آن ردیف بالا جایی است که SELECT ... FOR UPDATE ساده می‌افتد. هر Workerی که دنبال حریف حدود ۱۵۰۰ می‌گردد همان نزدیک‌ترین Match را حساب می‌کند و همه پشت هر کسی که اول قفلش کرد صف می‌کشند. در همین حال گوشت منحنی زنگوله‌ای پر از بازیکنانی است که یکی دو امتیاز دورترند و بازی به همان خوبی می‌دهند.

SELECT ... FOR UPDATE SKIP LOCKED نزدیک‌ترین ردیفی را که کسی قفل نکرده به هر Worker می‌دهد، به‌جای مسدود شدن روی ردیفی که از قبل گرفته شده، پس Workerی که ۱۵۰۰ را از دست می‌دهد ۱۵۰۱ را برمی‌دارد و ادامه می‌دهد. از آنجا Matcher هر دو درخواست را matched علامت می‌زند و Game را درج می‌کند، همه داخل یک تراکنش.

جذابیت اصلی این رویکرد این است که ادعا و ساخت بازی با هم Commit می‌شوند. هرگز لحظه‌ای نیست که دو بازیکن را از Pool بیرون کشیده باشیم ولی هنوز بازی‌ای که به آن تعلق دارند ثبت نکرده باشیم.

چالش‌ها: هر Match دو ردیف درخواست را به‌روز می‌کند و Update در Postgres نسخه‌ی قدیمی ردیف را به‌صورت Dead Tuple جا می‌گذارد. با ده‌ها هزار درخواست در ثانیه، Dead Tuple را سریع‌تر از پاک‌سازی Autovacuum تولید می‌کنیم، روی جدولی که هر درخواست ورودی هم Range Scan می‌کند. جدول و Indexهایش باد می‌کنند، Scanها کندتر می‌شوند و Scanهای کندتر قفل‌هایشان را بیشتر نگه می‌دارند، که همان چیزی است که مردم وقتی می‌گویند روی پایگاه داده صف نسازید منظورشان است. همچنین نمی‌توانیم آن بار را روی Primary های بیشتر پخش کنیم، چون Pool تقسیم‌شده بین دو تا هرگز نمی‌تواند بازیکنی روی یکی را با بازیکنی روی دیگری جفت کند.

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

رویکرد سوم، Sorted Set در Redis با Lua Script: بردن Pool از پایگاه داده به Store مشترک ساختار همیشه‌مرتبی را که نسخه‌ی درون‌پروسس داشت نگه می‌دارد. به هر Matchmaker همان نسخه از Pool را می‌دهد و برای هر ادعا هیچ نوشتن WAL یا Dead Tuple ندارد. هر Storeی که همه‌ی Workerها بتوانند به آن برسند جواب می‌دهد، به شرط اینکه بتواند درخواست در انتظار را به دقیقاً یکی از آن‌ها بدهد.

از Redis استفاده می‌کنیم چون Sorted Setهایش جستجوی مرتب را رایگان می‌دهند. Sorted Set اعضایش را به ترتیب کامل بر اساس Score نگه می‌دارد (پشتش Skip List است، پس مثل Index همیشه‌مرتب رفتار می‌کند). این Insert، حذف و جستجوی بازه‌ای بر اساس Score را همه ( O(\log n) ) به‌علاوه‌ی هر تعداد عضوی که برمی‌گردد می‌کند. (Deep Dive رسمی Redis هم می‌گوید Sorted Setها ترتیب را در زمان لگاریتمی نگه می‌دارند و برای Leaderboard مناسب‌اند [web:8].)

برای هر Time Control یک Sorted Set نگه می‌داریم، پس یک نسخه از Pool در انتظار داریم و هر Matchmakerی می‌تواند روی آن جستجو و ادعا کند. عضو requestId و Score رتبه است و فیلدهای دیگر درخواست در Hash زندگی می‌کنند:

1
2
3
4
5
6

# the request's other fields live in a hash, written first so
# whoever claims it can read the player
HSET mmreq:req_8a3f \
  playerId 42 rating 1512 status pending enqueuedAt 1718900000
# now it's discoverable, scored by rating
ZADD mm:blitz 1512 req_8a3f

هر درخواست دو کار می‌کند: پیدا کردن حریف سازگار و بعد ادعای آن حریف پیش از اینکه Worker دیگری بگیردش.

پیدا کردن حریف. Worker با جستجوی بازه‌ای بر اساس Score در پنجره‌ای اطراف رتبه‌ی درخواست ورودی جستجو می‌کند، که عملیات Sorted Set است که به خاطرش سراغ Redis آمدیم. این وسط Pool را مدیریت می‌کند، ولی برای ۲۷۰۰ که تقریباً هم‌ردیف آنلاین ندارد، پنجره را هرچه درخواست بیشتر منتظر می‌ماند گسترش می‌دهیم. بازه‌ای که درخواست می‌پذیرد هرچه بیشتر نشسته باشد بیشتر می‌شود، از enqueuedAt ذخیره‌شده محاسبه می‌شود. بازیکن قوی اول دنبال هم‌ردیف‌های نزدیک می‌گردد و از آنجا باز می‌شود، با یک پاس سبک پس‌زمینه که منتظران را دوباره اسکن می‌کند تا پنجره‌ی گسترده را اعمال کند:

1
2
3
4

# base search, opponents within +/-50 rating
ZRANGEBYSCORE mm:blitz 1462 1562
# widen with wait time: 50 + 8*30 = 290 after 30s, so 1512 +/- 290
ZRANGEBYSCORE mm:blitz 1222 1802

ادعای حریف. پیدا کردن کاندیدا کافی نیست، چون هزاران Worker همان Pool داغ را اسکن می‌کنند و چند تا می‌توانند هم‌زمان روی همان بازیکن در انتظار فرود بیایند. ادعا باید Atomic باشد و ZREM این را رایگان می‌دهد چون تعداد اعضایی را که واقعاً حذف کرده برمی‌گرداند. Workerی که 1 می‌گیرد آن بازیکن را بیرون کشیده و Workerی که 0 می‌گیرد می‌داند کسی پیش از او رسیده:

1
2

# claim atomically: 1 -> won the player, 0 -> already taken
ZREM mm:blitz req_2c91

این دو Worker را که به همان بازیکن دست می‌زنند پوشش می‌دهد، ولی نه دو Workerی که هرکدام هم‌زمان بازیکن دیگری را ادعا می‌کنند. فرض کنید Ava با رتبه‌ی ۱۵۰۸ و Ben با رتبه‌ی ۱۵۱۵ هم‌زمان وارد صف می‌شوند و روی Workerهای متفاوت می‌افتند، پس Worker مربوط به Ava، Ben را پیدا می‌کند و حذفش می‌کند در حالی که Worker مربوط به Ben، Ava را پیدا می‌کند و حذفش می‌کند.

هر دو ZREM مقدار 1 برمی‌گردانند، هر دو Worker فکر می‌کنند برده‌اند و هر دو بازی می‌سازند. Ava و Ben هرکدام gameId متفاوتی دارند و تنها نشسته‌اند و منتظر حریفی هستند که در بازی دیگر است.

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

جستجو و ادعا دستورهای جدا هستند، پس Worker دیگری همیشه می‌تواند بین آن‌ها اجرا شود. چون Redis اسکریپت Lua را از ابتدا تا انتها روی تک‌Thread خود بدون هیچ چیز در هم‌تنیده اجرا می‌کند، می‌توانیم کل تصمیم را به آن بدهیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

-- KEYS[1] = mm:blitz   ARGV = requestId, rating, window
local rating, window = tonumber(ARGV[2]), tonumber(ARGV[3])

if redis.call('ZREM', KEYS[1], ARGV[1]) == 0 then
  return { 'claimed' }            -- another worker already took us
end

local found = redis.call('ZRANGEBYSCORE', KEYS[1],
                         rating - window, rating + window, 'LIMIT', 0, 1)

if found[1] then
  redis.call('ZREM', KEYS[1], found[1])
  return { 'matched', found[1] }
end

redis.call('ZADD', KEYS[1], rating, ARGV[1])
return { 'waiting' }

درخواست هنگام رسیدن وارد Pool می‌شود و هر تلاش برای Match کردنش، اولی و هر Retry گسترده‌شده، یک فراخوانی این اسکریپت است.

بیرون کشیدن فراخوان‌گر اول چیزی است که مانع Match شدنش با خودش می‌شود و بررسی آن حذف چیزی است که مانع می‌شود Retry گسترده‌شده برای بازیکنی که Worker دیگری ادعایش کرده حریف دوم پیدا کند. هر فراخوانی matched، waiting یا claimed برمی‌گرداند و هیچ چیز نمی‌تواند در هم‌تنیده شود تا جواب متفاوتی بسازد.

چالش‌ها: سیاست گسترش (پنجره‌ی شروع، سرعت رشد، جایی که سقف می‌گیرد) دستگیره‌ای است که روی داده‌ی انتظار واقعی تنظیم می‌کنید. و بازیکنان ۲۸۰۰ در ساعت ۳ صبح بدون توجه به کار ما اینجا باز هم بیشترین انتظار را دارند، چون کسی آنلاین نیست که با او بازی کنند.

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

با Sorted Set در Redis جلو می‌رویم. دو سؤال پیگیری قابل‌انتظار است.

آیا لازم است Pool را بین Nodeهای Redis Shard کنیم؟ احتمالاً نه، و ارزش دارد پیش از رفتن سراغش اعداد را حساب کنید. پاسخ معمول به «Matchmaking را مقیاس بده» صف‌های Shard‌شده است، تقسیم بازیکنان در انتظار بین کلیدهای زیاد باند رتبه تا هیچ کلید واحدی داغ نشود. با اوج حدود ۳۰ هزار درخواست در ثانیه و تقریباً ۴ عملیات Redis برای هر کدام، کل حدود ۱۲۰ هزار عملیات در ثانیه است. شلوغ‌ترین Time Control تنها شاید ۴۰٪ آن باشد، یعنی حدود ۵۰ هزار عملیات در ثانیه روی کلیدش.

Node تک‌Thread از Redis عملیات Sorted Set را در محدوده‌ی چند صد هزار در ثانیه سرویس می‌دهد، پس داغ‌ترین کلید ما زیر یک‌سوم یک Node است با ۴ تا ۵ برابر فضای سر. خود Pool کوچک است، چند ده هزار ورودی، به‌راحتی زیر ۱۰۰ مگابایت. (این با ادعای Deep Dive رسمی Redis که یک Node حدود ۱۰۰ هزار نوشتن در ثانیه را تحمل می‌کند هم‌خوان است [web:8].)

Shard کردن آن قطعات متحرک بیشتر و دسته‌ی جدیدی از باگ در لبه‌ی باندها می‌خرید. دو بازیکن ۱۰ امتیاز از هم می‌توانند در Bucketهای متفاوت بیفتند و هرگز همدیگر را نبینند. فقط وقتی می‌خواهیم که یک Time Control چند برابر اوج امروز رشد کند.

اگر آن Node از Redis بیفتد چه؟ برای Pool در انتظار Single Point of Failure است، پس Redis را با Replication و Failover خودکار اجرا می‌کنیم (Redis Sentinel یا Redis Cluster مدیریت‌شده) و اگر Primary بمیرد یک Replica را ارتقا می‌دهیم. اینجا راحت رد می‌شویم چون درخواست بازی در انتظار ارزش زیادی ندارد. اگر Failover Pool در جریان را بیندازد، کلاینت‌های منتظر دوباره درخواست می‌دهند و صف ظرف چند ثانیه پر می‌شود. از دست دادن بازی در جریان مشکل واقعی بود، که به همین دلیل برای سرورهای بازی زحمت خیلی بیشتری می‌کشیم.

۲) چطور سرورهای بازی را به ۵۰۰ هزار بازی هم‌زمان مقیاس بدهیم؟

هر بازی فعال دو اتصال WebSocket پایدار به‌علاوه‌ی State زنده‌ی پشت آن‌ها را نگه می‌دارد: تخته، نوبت و هر دو ساعت. در ۵۰۰ هزار بازی، این ۱ میلیون اتصال و ۵۰۰ هزار Session کوچک برای ردیابی است. یک سرور می‌تواند ده‌ها هزار اتصال WebSocket بیکار را نگه دارد (حتی بیشتر روی سخت‌افزار واقعاً بزرگ)، ولی در هر حال باید خوشه‌ی سرورها را به صدها مقیاس بدهیم.

دو راه برای اجرای این ناوگان هست و در اینکه Node مالک چه چیزی باشد فرق دارند. اگر بازی در حافظه‌ی یک سرور زندگی کند، همان‌طور که طراحی سطح بالا دارد، هر دو بازیکن باید روی همان سرور فرود بیایند. Crash هم بازی‌هایش را با خودش می‌برد، پس به جایگذاری و بازیابی نیاز داریم. اگر بازی به‌جای آن در Store مشترک زندگی کند، چیزی برای جایگذاری نیست و کار به درست نگه داشتن آن Store زیر حرکت‌های هم‌زمان و رساندن هر حرکت به Socket درست می‌رود.

رویکرد اول، Hash ساده‌ی gameId به سرور: ناوگان اجرا کنید و هر دو بازیکن یک بازی را قطعی به همان سرور مسیریابی کنید، مثلاً با Hash کردن شناسه‌ی بازی به سرور. هر دو با هم فرود می‌آیند، پس اعتبارسنجی حرکت و به‌روزرسانی ساعت محلی و سریع می‌ماند، که ما را زیر بودجه‌ی ۲۰۰ میلی‌ثانیه نگه می‌دارد.

چالش‌ها: Hash ساده یعنی وقتی سرور اضافه یا حذف می‌شود، کسر بزرگی از بازی‌ها به سرور دیگری نگاشت می‌شوند. و هنوز Durability را حل نکرده‌ایم. وقتی سروری می‌میرد، هر بازی روی آن گم می‌شود، چون State آن فقط در حافظه‌ی آن پروسس بود. بار هم می‌تواند اگر Hash اتفاقاً بازی‌های سنگین را روی یک Node جمع کند کج شود.

رویکرد دوم، Consistent Hashing با Fencing: دو قطعه اینجا هست، مسیریابی قابل‌اعتماد و زنده ماندن از Crash.

برای مسیریابی، یک Session Router نازک و Stateless جلوی ناوگان می‌نشیند. در بازی جدید gameId را با Consistent Hashing به سرور نگاشت می‌کند و هر دو بازیکن را آنجا می‌فرستد، پس اعتبارسنجی حرکت و به‌روزرسانی ساعت محلی می‌ماند. (Consistent Hashing جابه‌جایی داده را هنگام افزودن یا حذف سرور به کسری از کلیدها محدود می‌کند، برخلاف Modulo ساده که تقریباً همه‌ی کلیدها را جابه‌جا می‌کند [web:34].) عضویت از Registry مثل ZooKeeper، etcd یا Consul می‌آید، که در آن هر سرور بازی یک Ephemeral Node ثبت می‌کند (ورودی Registry که اگر سرور Heartbeat را متوقف کند خودکار حذف می‌شود). ZooKeeper دقیقاً برای Cluster Membership و Leader Election با Ephemeral Znode و Watch شناخته می‌شود [web:35]. Router Registry را تماشا می‌کند و هر وقت Nodeی ظاهر یا منقضی می‌شود حلقه‌اش را دوباره می‌سازد، پس جستجو تابع محض gameId و عضویت فعلی است. افزودن یا حذف سرور فقط تکه‌ی کوچکی از بازی‌ها را دوباره نگاشت می‌کند و Ephemeral Nodeها یعنی سرور مرده خودش از حلقه بیرون می‌افتد.

برای زنده ماندن، توجه کنید که از قبل همه‌ی چیزهای لازم را از طراحی سطح بالا داریم. هر حرکت پیش از Broadcast به لاگ ماندگار Moves اضافه می‌شود و ردیف Game ساعت‌ها، نوبت و نتیجه را دارد. پس بازیابی مکانیزم جدید نیست، فقط Replay است. سرور جایگزین ردیف بازی را برای ساعت‌ها و نوبت می‌خواند و بعد حرکت‌هایش را Replay می‌کند تا تخته را در حافظه بازسازی کند. بازی ۴۰ حرکتی کامل فقط چند صد بایت حرکت است، پس آن Replay میکروثانیه است و هرگز موقعیت تخته را جدا ذخیره نمی‌کنیم یا درباره‌ی تازگی Snapshot استدلال نمی‌کنیم.

تنها چیزی که Failover واقعاً نیاز دارد، و چیز ساده‌ای که راحت جا می‌افتد، یک Fence است. سروری که جایگزین شده ولی هنوز زنده است، مثلاً آن سمت Partition شبکه، نباید به نوشتن در بازی ادامه دهد که حلقه از آن رد شده. برای همین یک شمارنده‌ی Generation به ردیف Game اضافه می‌کنیم:

1
2
3
4
5
6
7
8

CREATE TABLE games (
  game_id     UUID PRIMARY KEY,
  white_ms    INTEGER,
  black_ms    INTEGER,
  turn        CHAR(1),      -- 'w' or 'b'
  generation  INTEGER,      -- bumped each time the ring reassigns the game
  updated_at  TIMESTAMPTZ
);

هر بار حلقه بازی را دوباره تخصیص می‌دهد، مالک جدیدش Generation را افزایش می‌دهد. هر نوشتن برای آن بازی، Append حرکت و به‌روزرسانی ساعت با هم، در یک تراکنش با محافظ روی آن اجرا می‌شود:

1
2
3
4

UPDATE games
SET white_ms = :white_ms, black_ms = :black_ms, turn = :turn,
    generation = :gen, updated_at = NOW()
WHERE game_id = :id AND generation <= :gen;

سرور Zombie که هنوز Generation قدیمی دارد این محافظ را رد نمی‌کند، پس نوشتن‌هایش، از جمله هر حرکتی که سعی می‌کند در همان تراکنش Append کند، بی‌صدا رها می‌شوند. نمی‌تواند بازی را که حلقه از آن جابه‌جا شده زنده کند.

مسیر کامل وقتی سرور نگه‌دارنده‌ی بازی G می‌میرد:

  1. سرور S مالک بازی G در Generation برابر N است و Crash می‌کند، پس Ephemeral Node آن در Registry دیگر Heartbeat نمی‌دهد و منقضی می‌شود.
  2. Router حلقه را بدون S دوباره می‌سازد و جانشین hash(G) حالا سرور S’ است.
  3. کلاینت‌ها Socket افتاده را تشخیص می‌دهند و دوباره وصل می‌شوند و Router آن‌ها را به S’ می‌فرستد.
  4. S’ ردیف G را بارگذاری و حرکت‌هایش را Replay می‌کند تا تخته را بازسازی کند، Generation برابر N را می‌خواند و به‌عنوان مالک جدید آن را به N+1 افزایش می‌دهد.
  5. نوشتن تأخیری از S که Partition شده ولی زنده است با Generation برابر N می‌رسد، در بررسی generation <= :gen در برابر N+1 شکست می‌خورد و رد می‌شود.

چالش‌ها: آن اتصال دوباره برای کاربر قابل‌مشاهده است، هرچند متوقف کردن ساعت در آن مدت (انتخاب Consistency بر Availability ما) آن را عادلانه نگه می‌دارد. Fencing در گام ۵ کار واقعی Consistency بر Availability است و چیز ساده‌ای که راحت جا می‌افتد. بدون آن، سرور Partition‌شده‌ی زنده به تغییر بازی که حلقه از آن رد شده ادامه می‌دهد.

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

یک زائده ذاتی Hash است. چون جایگذاری تابع محض حلقه است، مقیاس‌دهی ناوگان در اوج شبانه تکه‌ای از بازی‌های کاملاً سالم در جریان را روی Node جدید دوباره نگاشت می‌کند. تنها زمانی که واقعاً می‌خواهید بازی را جابه‌جا کنید وقتی است که سرور خودش بمیرد.

برای شطرنج این هزینه‌ی کوچکی است، اتصال دوباره‌ی کوتاه روی کسری از بازی‌ها هنگام Scale-up. نه دایرکتوری جایگذاری تحت مالکیت Coordinator و نه طراحی Store مشترک زیر این هزینه را نمی‌پردازند، چون هیچ‌کدام وقتی ناوگان اندازه‌اش را عوض می‌کند بازی سالم را جابه‌جا نمی‌کنند.

رویکرد سوم، State مشترک در Redis: گزینه‌ی دیگر این است که اصلاً سرورها مالک بازی نباشند. تخته‌ی زنده، نوبت و هر دو ساعت زیر gameId در Redis می‌نشینند و هر حرکت پذیرفته‌شده هنوز به همان لاگ ماندگار Moves که قبلاً می‌نوشتیم اضافه می‌شود. حرکت می‌تواند توسط هر Nodeی که Socket آن بازیکن را نگه می‌دارد مدیریت شود و دو بازیکن هرگز لازم نیست با هم فرود بیایند.

وقتی حرکت می‌رسد، Node موقعیت را می‌خواند، اعتبارسنجی می‌کند و با Compare-and-Set روی نسخه‌ای که با هر حرکت افزایش می‌یابد Commit می‌کند. دو حرکتی که ظرف یک میلی‌ثانیه می‌رسند نمی‌توانند هر دو ببرند. دومی می‌بیند نسخه‌ای که خوانده جلو رفته و در برابر موقعیت جدید دوباره اعتبارسنجی می‌کند، که همان ترتیبی است که پروسس مالک واحد رایگان به ما می‌داد.

Commit ساعت‌ها را با ساعت خود Redis مهر می‌زند، نه ساعت Node، چون حرکت بعدی ممکن است کاملاً جای دیگری مدیریت شود و خواندن Monotonic محلی آنجا معنایی ندارد.

وقتی حرکت Commit شد، Node آن را روی کانال کلیدگذاری‌شده با gameId منتشر می‌کند و Nodeی که Socket حریف را نگه می‌دارد مشترک آن است و آن را پایین می‌فرستد. Pub/Sub در Redis فراموش‌کن است و Replay ندارد (Deep Dive رسمی Redis هم تأیید می‌کند Pub/Sub در Redis تحویل At-most-once است و پیام ازدست‌رفته برای مشترک آفلاین برنمی‌گردد [web:8])، پس کلاینت دوباره وصل‌شده از کانال نمی‌پرسد چه چیزی از دست داده. دوباره مشترک می‌شود و حرکت‌های بعد از آخرین شماره‌ی ترتیبش را از لاگ ماندگار می‌خواند. حلقه‌ای برای بازسازی و Registry عضویتی نیست، چون Nodeی که می‌میرد فقط Socketها را نگه می‌داشت.

چالش‌ها: Redis حالا روی مسیر هر حرکت در هر بازی زنده است، پس Redis چیزی است که در دسترس و مقیاس‌پذیر نگه می‌دارید. Replication معمولی Redis Asynchronous است و Failover می‌تواند نوشتن‌های اخیراً تأییدشده را بیندازد، پس Append ماندگار حرکت در طراحی می‌ماند. شعاع آسیب به نحوه‌ی Deploy بستگی دارد. یک Primary یعنی Failover همه‌ی بازی‌ها را هم‌زمان متوقف می‌کند، در حالی که پارتیشن‌بندی State و Pub/Sub بر اساس gameId آن را به بازی‌های روی آن Shard محدود می‌کند.

Consistent Hashing و Registry عضویت را با لایه‌ی Pub/Sub معاوضه می‌کنید. هر Node هنوز باید بداند کدام یک از Socketهای خودش به کدام بازی تعلق دارد تا بتواند آنچه روی کانال می‌رسد را مسیریابی کند.

هر دو کار می‌کنند و ما با ناوگان Stateful می‌مانیم. تخته در حافظه‌ی سروری است که حرکت‌ها را اعتبارسنجی می‌کند، پس هر خواندنی که قوانین لازم دارند محلی است. لاگ حرکتی که از قبل برای Replay و اختلاف نگه می‌داریم بازیابی را بدون مکانیزم دوم پوشش می‌دهد. تنها چیزی که واقعاً اضافه می‌کنیم جایگذاری است.

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

Lichess بین این دو تعادل برقرار می‌کند. بازی‌های زنده در Backend به‌صورت Actor برای هر بازی اجرا می‌شوند، که شکل Stateful است. اما اتصال‌های WebSocket توسط سرویس کاملاً جدایی مدیریت می‌شود که از طریق Redis با آن Backend صحبت می‌کند، که شبیه مسیر Pub/Sub بالاست.

آیا Framework جایگذاری را برایتان انجام نمی‌دهد؟ اگر Stateful بروید، اغلب بله. Frameworkهای Sharding Stateful و Runtimeهای Virtual-actor جایگذاری را به دایرکتوری تحت مالکیت Coordinator تبدیل می‌کنند، به‌جای Hashی که هر Router دوباره محاسبه می‌کند. افزودن ظرفیت بعد فقط بازی‌های جدید را برمی‌دارد و هنگام تغییر عضویت هیچ بازی سالمی جابه‌جا نمی‌شود. Akka Cluster Sharding و Microsoft Orleans هر دو اینطور کار می‌کنند و برای هر gameId یک Actor آدرس‌دهی می‌کنند. برای بازی‌های سنگین‌تر با پروسس برای هر مسابقه مثل شوترها، تخصیص مدیریت‌شده (Agones، AWS GameLift) کل سرور را برای هر مسابقه به شما می‌دهد.

اما صادق باشید که این برای شطرنج چه چیزی را عوض می‌کند، که هیچ چیز درباره‌ی جواب نیست. هنوز با Replay لاگ حرکت بازیابی می‌کنید و هنوز Fencing می‌خواهید که Orleans با دایرکتوری Grain با Consistency قوی‌اش فراهم می‌کند و محافظ Generation ما دستی انجام می‌دهد. Router دستی Consistent Hash اینجا خوب است. فقط اگر از قبل روی Framework می‌سازید سراغش می‌روید.

۳) چطور ساعت را با وجود Latency نابرابر عادلانه نگه داریم؟

سرور صاحب ساعت است، پس فقط می‌تواند تایمر بازیکن را وقتی حرکتش واقعاً روی شبکه می‌رسد شروع و متوقف کند. یعنی Latency شبکه‌ی هر بازیکن از ساعت خودش کم می‌شود و بازیکنان Latency برابر ندارند.

بگوییم بازیکن A رفت‌وبرگشت ۳۰ میلی‌ثانیه‌ای به سرور دارد در حالی که بازیکن B، که خیلی دورتر است، ۲۰۰ میلی‌ثانیه. B تا حرکت A به او نرسد نمی‌تواند شروع به فکر کردن کند و پاسخ B همان سفر را برمی‌گردد. هر دو ضلع روی ساعت B می‌افتد، پس هر حرکت حدود ۱۷۰ میلی‌ثانیه برای او بیش از A هزینه دارد.

در ۴۰ حرکت از بازی Blitz ۳ دقیقه‌ای، نزدیک ۷ ثانیه از ساعت B فقط در انتقال خرج شده، که برای باختن بر اساس زمان کافی است. بازیکنان موبایل یا دور از سرور بی‌تقصیر در برابر بازی‌شان در موقعیت ضعف واقعی‌اند. چطور ساعت را عادلانه کنیم؟

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

چالش‌ها: کلاینت دستکاری‌شده دروغ می‌گوید که هرگز کم نمی‌آورد. حتی با کلاینت‌های صادق، دو تایمر از هم دور می‌شوند و درباره‌ی اینکه زمان چه کسی اول تمام شد توافق ندارند. ساعت دقیقاً از نوع مقدار معتبری است که هرگز نمی‌تواند روی کلاینت زندگی کند.

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

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

رویکرد سوم، ساعت سرور با جبران تأخیر (Latency Compensation): سرور را معتبر نگه دارید، بعد انتقال شبکه را برگردانید تا بازیکنان با Latency بالا برای فاصله‌شان جریمه نشوند. تایمر برای هر بازی اجرا نمی‌کنیم. سرور remaining_ms هر بازیکن و last_start_timestamp زمان شروع ساعت او را نگه می‌دارد، از ساعت Monotonic می‌خواند و زمان سپری‌شده را بر حسب نیاز کم می‌کند. تنها نوشتن‌ها هنگام حرکت است.

کار واقعی جبران Latency است. سرور رفت‌وبرگشت به هر کلاینت را پیوسته با فریم‌های Ping/Pong در WebSocket می‌سنجد، مستقل از حرکت‌ها، چون بازیکن ممکن است بین حرکت‌ها ۳۰ ثانیه فکر کند. میانه‌ی غلتان نگه می‌دارد، نه میانگین، تا یک جهش بد آن را منحرف نکند. چیزی که برمی‌گرداند کل median_rtt است، نه نصف آن، چون هر دو ضلع آن سفر برای بازیکن زمان مرده است. نمی‌توانست پیش از رسیدن موقعیت حرکت کند و حرکتش وقتی به سرور برگشت از قبل انجام شده بود. شارژ هر ضلع به ساعتش او را برای شبکه شارژ می‌کند.

بازیکن ۲۰۰ میلی‌ثانیه را از آن رد کنید. بدون جبران، در هر حرکت جریمه‌ی ۱۷۰ میلی‌ثانیه‌ای می‌دهد، نزدیک ۷ ثانیه در بازی Blitz ۴۰ حرکتی. برگرداندن رفت‌وبرگشت اندازه‌گیری‌شده‌ی او کل ۲۰۰ میلی‌ثانیه انتقال را پس می‌دهد و او را فقط با زمان فکر پرداخت‌کننده باقی می‌گذارد. با این حال سقف پایین هر حرکت را به حدود ۱۰۰ میلی‌ثانیه محدود می‌کند، پس در عمل شکاف به زیر ۳ ثانیه کم می‌شود، نه اینکه ناپدید شود.

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

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

زاویه‌ی سوءاستفاده هم هست و ارزش دارد درباره‌اش صادق باشیم. چون زمان را بر اساس RTT اندازه‌گیری‌شده برمی‌گردانیم، کلاینت می‌تواند RTT خودش را با عمداً کش دادن پاسخ‌های Pong باد کند. سرور نمی‌تواند Pong متوقف‌شده را از لینک کند تشخیص دهد. Timestamp سمت سرور اینجا نجاتمان نمی‌دهد، کلاینت چیزی جعل نمی‌کند و فقط کند جواب می‌دهد.

پس دفاع واقعی تشخیص کامل نیست، سقف است. محدود می‌کنیم هر حرکت چقدر می‌تواند پس بگیرد (سقفی حدود ۱۰۰ میلی‌ثانیه)، یعنی حتی کلاینتی که RTT خود را بازی می‌دهد نمی‌تواند اتصال کند را به زمان رایگان معنادار تبدیل کند.

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

۴) چطور Leaderboard را در ۱۰ میلیون بازیکن درست و سریع نگه داریم؟

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

خواندن‌ها به دو Query خیلی متفاوت تقسیم می‌شوند که اصلاً به یک اندازه سخت نیستند. N بالا را در طراحی سطح بالا حل کردیم، B-tree روی رتبه ORDER BY rating DESC LIMIT 50 را ارزان می‌کند و Cache روی صفحه‌ای که تقریباً جابه‌جا نمی‌شود آن را مهر می‌کند. چیزی که واقعاً دردسر می‌سازد گرفتن رتبه‌ی یک بازیکن مشخص است. «کجای ۱۰ میلیون نشسته‌ام» همان COUNT(*) WHERE rating > :myRating است و B-tree نمی‌تواند در بهتر از ( O(\text{rank}) ) جوابش را بدهد. باید هر ورودی بالای شما را بشمارد. برای بازیکن وسط جدول، میلیون‌ها ورودی Index در هر فراخوانی است و رایج‌ترین خواندن شخصی‌شده در صفحه است. پس چالش واقعی اینجا نحوه‌ی محاسبه‌ی رتبه است، نه مرتب‌سازی جدول.

رویکرد اول، شمارش بر اساس باند (Bucketed Counts): بیشتر محصولات واقعاً لازم ندارند رتبه‌ی شما تا حد یک نفر دقیق باشد. تعداد بازیکنان را در هر باند رتبه نگه دارید، مثلاً Bucketهای ۱۰ امتیازی، چند صد تا در کل بازه‌ی رتبه. با پایان هر بازی به‌روزش کنید و بازیکن را از باند قدیمی به باند جدیدش ببرید. رتبه‌ی بازیکن آن‌وقت مجموع شمارش همه‌ی باندهای بالاتر است، اختیاراً با درون‌یابی داخل باند خودش.

چالش‌ها: کل ساختار چند صد عدد صحیح است، پس جستجوی رتبه کار ثابت است و به‌روز نگه داشتنش ارزان. هزینه این است که جواب تقریبی است، «حدود ۴۲۰۰ام» به‌جای دقیق، و باید شمارش باندها را با رتبه‌های واقعی همگام نگه دارید. برای خیلی از Leaderboardها این معامله‌ی کاملاً خوبی است و ارزش دارد به‌عنوان گزینه‌ی میانی عملی نامش را ببرید، به‌جای اینکه مستقیم به Datastore جدید بپرید.

رویکرد دوم، Sorted Set در Redis: وقتی رتبه‌ی دقیق ارزان می‌خواهید، ترتیب را در Sorted Set در Redis نگه دارید، با عضو playerId و Score برابر رتبه. ZREVRANK player رتبه‌ی دقیق و ZREVRANGE 0 49 صفحه‌ی بالا را می‌دهد، هر دو ( O(\log n) ). Skip List پشت Sorted Set عملاً همان ساختار Order-statistics است که B-tree ساده نیست.

چون از قبل Redis را برای Matchmaking اجرا می‌کنیم، این افزودن طبیعی است، نه تکه‌ی زیرساختی جدید.

Set با پایان بازی‌ها به‌روز می‌شود و نمای مشتق است، هرگز منبع حقیقت نیست (اینکه نوشتن رتبه چطور آن را با Postgres همگام نگه می‌دارد آخرین چیزی است که می‌گوییم). Redis را با AOF ماندگار نگه می‌داریم، ولی (طبق همان Deep Dive رسمی Redis) AOF به‌صورت پیش‌فرض هر ثانیه fsync می‌کند و Crash تا یک ثانیه نوشتن تأییدشده را از دست می‌دهد [web:8]، پس Set گم‌شده یا منحرف‌شده فقط بازسازی می‌شود. مقیاس برای یک Instance راحت است. ۱۰ میلیون عضو در حدود یک گیگابایت اجرا می‌شود. نرخ نوشتن فقط نرخ پایان بازی است، تقریباً ۴ هزار بازی در ثانیه ضربدر دو بازیکن، یعنی حدود ۸ هزار ZADD در ثانیه، که Redis به‌راحتی مدیریت می‌کند. رتبه‌بندی سراسری به هر حال یک ساختار مرتب واحد می‌خواهد، پس چیزی برای Shard کردن نیست.

چالش‌ها: رتبه‌های مساوی به Tiebreak قطعی که در Score پخته شود نیاز دارند (رتبه به‌علاوه‌ی جزء کسری زمان آخرین به‌روزرسانی، مثلاً) وگرنه صفحه‌بندی ممکن است لرزان شود. و سؤال صادقانه‌ای که باید بلند بپرسید این است که آیا اصلاً رتبه‌ی دقیق می‌خواهید. اگر تقریبی خوب است، شمارش باند ساده‌تر و ارزان‌تر است و Sorted Set جواب مخصوص وقتی است که دقت اهمیت دارد.

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

برای خواندن‌های سریع آن رتبه را در دو جا Materialize نگه می‌داریم، روی ردیف Players و در Sorted Set، هر دو وقتی بازی تمام می‌شود به‌روز می‌شوند. چیزی که مانع انحرافشان می‌شود این است که هیچ‌کدام منبع حقیقت دوم نیستند. هر دو از نتیجه‌ی Game مشتق می‌شوند و انتشار Idempotent است.

نوشتن نتیجه‌ی پایان بازی روی ردیف Game یگانه نقطه‌ی Commit است. بعد گام Apply، Delta ELO را به ردیف Players و Sorted Set پخش می‌کند، کلیدگذاری‌شده با gameId تا Replay همان بازی بی‌اثر باشد. Retry بعد از به‌روزرسانی نیمه‌تمام اصلاح می‌کند، نه دوبار می‌شمارد.

اگر نوشتنی از قلم بیفتد یا Redis به هر حال منحرف شود، تطبیق دوره‌ای از بازی‌های کامل‌شده دوباره محاسبه می‌کند و هر دو را بازنویسی می‌کند و در بدترین حالت کل Set را از صفر بازسازی می‌کنیم. به همین دلیل Crash درست در پایان بازی ترسناک نیست. نتیجه ماندگار است و Leaderboard فقط نمایی روی آن است.

Leaderboard جایی است که نامزدها تمایل دارند بیش‌ازحد یا کم‌تر از حد بسازند. مهندسان Senior+ باید ببینند رتبه مجموع مشتق بر بازی‌های تمام‌شده است، نه مقدار درون‌حافظه‌ی گران‌بها. آن‌وقت هم نگرانی Durability در Crash و هم داستان بازسازی رایگان نتیجه می‌شوند. Sorted Set در Redis فقط Index خارجی روی آن رکورد است، ساختار درست برای رتبه‌ی ( O(\log n) ).

طراحی نهایی

با کنار هم گذاشتن همه‌چیز، طراحی نهایی ما چنین است: بازیکن از API Gateway به Matchmaking Service می‌رسد که درخواست را در Sorted Set مربوط به Time Control در Redis وارد می‌کند و Match Workerها با Lua Script اتمیک جفت‌سازی می‌کنند و Game را در Postgres می‌سازند. Session Router با Consistent Hashing و عضویت ZooKeeper (Ephemeral Node برای هر سرور) هر دو بازیکن را به همان Game Service می‌فرستد. Game Service تخته و ساعت‌ها را در حافظه نگه می‌دارد، هر حرکت را پیش از Broadcast به لاگ ماندگار Append می‌کند و با محافظ Generation از Zombie جلوگیری می‌کند. هنگام پایان بازی، نتیجه روی ردیف Game ثبت می‌شود و Delta ELO به Players و Sorted Set مربوط به Leaderboard در Redis Idempotent اعمال می‌شود.

Deep Dive های اضافی که می‌توانید در نظر بگیرید

نتوانستیم همه‌چیز را جا بدهیم. چند جهت دیگر که مصاحبه‌کننده ممکن است فشار بیاورد:

  • Fair Play و ضد تقلب: کمک موتور شطرنج تهدید وجودی شطرنج آنلاین است و بازیکنی که موقعیت زنده را به موتور می‌دهد از هیچ بازی منفردی تقریباً غیرقابل‌تشخیص است. گرفتنش مسئله‌ی ML آفلاین و تحلیل رفتاری است: مقایسه‌ی انتخاب حرکت‌ها با برترین انتخاب‌های موتور، تماشای الگوهای زمان حرکت و امتیازدهی دقت در برابر تاریخچه‌ی رتبه، و بعد علامت‌گذاری حساب‌ها برای بررسی. سیستم متفاوتی از مسیر بلادرنگی است که ساختیم، که به همین دلیل زیر خط است. اما نام بردنش (همراه یکپارچگی تورنمنت) نشان می‌دهد می‌فهمید چه چیزی این پلتفرم‌ها را می‌سازد یا می‌شکند.
  • تماشای بازی‌های محبوب: بازی برتر، مثل مسابقه‌ی Blitz ابرمیزبان، می‌تواند ده‌ها هزار تماشاگر جذب کند، که مسئله‌ی Fan-out خواندن است و هیچ وجه مشترکی با مسیر ۱ به ۱ بازی ندارد. تماشاگران را به سرور بازی معتبر وصل نمی‌کنید. حرکت‌های اعتبارسنجی‌شده را از طریق لایه‌ی Pub/Sub یا درخت شبیه CDN به مشترکان فقط‌خواندنی Fan-out می‌کنید، که چند صد میلی‌ثانیه تأخیر اشکالی ندارد چون تماشاگران هرگز نمی‌نویسند.
  • ذخیره و سرویس‌دهی آرشیو بازی: هر بازی تمام‌شده برای همیشه نگه داشته می‌شود (Lichess بیش از ۱۲ میلیارد دارد)، که مسئله‌ی داده در حالت سکون جدا از مسیر زنده است. تحلیل بعد از بازی و کاوشگر گشایش (قابلیت «بازیکنان معمولاً در این موقعیت چه بازی می‌کنند») را قدرت می‌دهد. این ساده‌تر از چیزی است که در ابتدا به نظر می‌رسد، چون بازی فقط دنباله‌ی حرکاتش است که به‌صورت رشته ذخیره می‌شود. پیدا کردن هر بازی که از خط داده‌شده پیروی کرده، پیمایش بازه‌ای پیشوندی روی آن دنباله‌هاست، نه چیز پیچیده. Queryهای غنی‌تر روی کل آرشیو، تجمیع بر اساس موقعیت از جمله Transposition، جایی است که سراغ Store ستونی یا جستجو می‌روید (Lichess بازی‌ها را در Elasticsearch ایندکس می‌کند). هیچ‌کدام به پایگاه داده‌ی OLTP که بازی زنده روی آن اجرا می‌شود تعلق ندارد.
  • Premove در Bullet: در Bullet و Ultrabullet بازیکنان حرکتی را در صف می‌گذارند تا لحظه‌ای که حریف حرکت می‌کند شلیک شود و بازیکنان قوی چند تا پشت هم روی هم می‌گذارند. جالبش منطق سرور است. سرور حرکتی را اعتبارسنجی و اعمال می‌کند که بازیکن پیش از دیدن پاسخ واقعی حریف متعهد شده و وقتی پاسخ آن را غیرقانونی کرد تمیز رهایش می‌کند. همه‌ی این‌ها لحظه‌ای رخ می‌دهد که حرکت حریف می‌رسد، پس حرکت صف‌شده عملاً هیچ ساعتی خرج نمی‌کند. پلتفرم‌های واقعی سال‌ها روی این Edge Caseها تکرار کرده‌اند.

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

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

Mid-level: برای این سؤال، طراحی سطح بالای کارایی انتظار دارم که هر سه نیازمندی اصلی را پوشش دهد: Matchmaking، بازی بلادرنگ اعتبارسنجی‌شده توسط سرور روی WebSocket و Leaderboard. باید به این برسید که سرور، نه کلاینت، صاحب اعتبارسنجی حرکت و ساعت است. می‌خواهم ببینم متوجه می‌شوید ۵۰۰ هزار بازی هم‌زمان روی یک جعبه جا نمی‌شود. اگر اولین چیزی که به آن می‌رسید Hash کردن مستقیم شناسه‌ی بازی به سرور باشد اصلاً مهم نیست. فقط بتوانید بگویید وقتی آن سرور بمیرد برای آن بازی‌ها چه می‌شود. رسیدن به ساعت معتبر سمت سرور با کمی راهنمایی چیز دیگری است که اینجا انتظار دارم.

Senior: برای Senior می‌خواهم طراحی سطح بالا را سریع رد کنید تا وقتمان را در Deep Dive ها بگذاریم: Matchmaking در مقیاس، مقیاس‌دهی ناوگان سرور بازی، انصاف ساعت و درست و سریع نگه داشتن Leaderboard. سه‌تای اول بیشترین سیگنال را می‌دهند، پس می‌خواهم دست‌کم دو تا از آن‌ها خوب پوشش داده شود.

باید بتوانید مقیاس را خودتان استخراج کنید (۱ میلیون اتصال از ۵۰۰ هزار بازی، ده‌ها هزار درخواست بازی در ثانیه) و از آن اعداد برای استدلال درباره‌ی چرایی شکست رویکردهای ساده استفاده کنید. دنبال این هستم که Trade-off مشخص در طراحی ساعت بین ساعت ساده‌ی معتبر سمت سرور و ساعتی که رفت‌وبرگشت را برمی‌گرداند بیان کنید.

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

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

Staff و بالاتر: برای نامزد Staff+ عمق و قضاوت فراتر از پاسخ‌های کتاب‌درسی می‌خواهم. درباره‌ی سرورهای بازی می‌خواهم ببینید لاگ حرکت ماندگاری که از قبل می‌نویسیم مکانیزم بازیابی است، هر طراحی‌ای که انتخاب کرده باشید. سرور جایگزین چند صد بایت حرکت را Replay می‌کند و برگشته است. نامزدهایی که روی آن طرح Checkpoint یا جدول Snapshot اضافه می‌کنند معمولاً نفهمیده‌اند چه چیزی برایشان می‌خرد، که در چند صد حرکت در هر بازی هیچ است.

از آنجا واقعیت‌های Production را که از آن‌ها عبور کردیم انتظار دارم. ناوگان هنگام Deploy بازی‌ها را چطور تخلیه (Drain) می‌کند؟ اتصال دوباره از دید کلاینت هنگام بازیابی بازی چه شکلی است؟ و سیاست گسترش Matchmaking چطور از داده‌ی انتظار واقعی تنظیم می‌شود؟

طراحی سیستم, مصاحبه
online chess matchmaking websocket redis sorted set leaderboard مصاحبه