Pebble Gamesから、ライブのリーダーボードを求められています。架空の規模は、ランキング対象のプレイヤーが5,000,000人、ピーク時のスコア更新が毎秒20,000件です。スコープ、メモリの見積もり、順位のAPI、スコアと順位の経路、同点のルール、精度のトレードオフを提出してください。
面接官はこの設計でレベルをどう判断するか
- ジュニア:順位には順序付きのインメモリ構造を、スコアには永続的なストアを使います。
- ミドルレベル:構造の規模を見積もり、同点の扱いを決定的にし、キャッシュが失われた後に順位を再構築する方法を説明します。
- シニア:下位層では正確さと引き換えに規模を確保し、ゲームや階層ごとにシャーディングし、不正行為とスコアの訂正に対処します。
Pebble Gamesはライブのリーダーボードを求めています:全体の上位100件と各プレイヤー自身の順位を、スコアが届くたびに更新します。リクエストのたびに500万行を並べ替えるリレーショナルのクエリでは追いつかないので、ランキングには、スコアが変わっても順序を保つ構造が必要です。
それを実現するのがインメモリのソート済みセットです:スコアの挿入も順位の読み取りも、対数時間で済みます。ソート済みセットは高速ですが正式な記録の保管場所ではないので、スコアは永続的なストレージにも保存します。ソート済みセットに必要なメモリを見積もり、順位のAPIを定義し、更新と読み取りの経路を描き、同点を公平に扱い、上位から遠いプレイヤーの順位をどこまで正確にするかを決めます。