ライドシェアのシステム設計：位置情報の更新、マッチング、配車

乗客が「リクエスト」をタップすると、数秒以内に車が来ることを期待します。そのタップの裏で、システムは移動中の何十万人ものドライバーがいまどこにいるかを把握し、よいドライバーを選び、ほかの乗客に同じドライバーが割り当てられないようにし、さらに支払いで終わる乗車を追跡しなければなりません。大量のリアルタイムストリームと、小さく厳格なトランザクションの中核を組み合わせるため、システム設計の面接でよく出題される問題です。

この記事では、バックエンドを段階的に設計します。要件と容量の数値、位置情報の取り込み、geohash・S2・H3 による地理空間インデックス、マッチングと配車、乗車の状態機械、想定しておくべき障害を、そのまま使えるアーキテクチャ図とともに扱います。

要件

機能要件：

• ドライバーはオンラインになり、位置情報を継続的に送信します。
• 乗客は乗車をリクエストし、近くの車と到着予定時刻を確認します。
• システムは乗客とドライバーをマッチングし、ドライバーは承諾または拒否できます。
• 両方のアプリが乗車をリアルタイムで追跡し、乗車は運賃と支払いで終わります。

非機能要件：

• 数秒以内にマッチングすること。
• ドライバーの位置情報の古さは数秒以内であること。
• 1 人のドライバーを 2 人の乗客に割り当てないこと。
• ある都市の問題がほかの都市を巻き込まないこと。

容量：設計を形づくる数値

大規模な運用を想定し、ピーク時にオンラインのドライバーが 100 万人、それぞれが 4 秒ごとに位置を送信し、乗車リクエストが毎分 20,000 件あるとします。

性質のまったく異なる 2 つのワークロードが見えてきます。位置情報の更新は量が膨大ですが、1 件 1 件は小さく、使い捨てで、4 秒後には次の更新に置き換わります。乗車リクエストは 3 桁少ないものの、1 件ずつ正確に 1 回だけ処理し、お金に結び付けなければなりません。アーキテクチャはこの 2 つを分離します。

位置情報の取り込み：最新のものだけを保持する

ドライバーアプリは、WebSocket のような永続的な接続、または小さな定期的 HTTPS リクエストで位置を送信します。位置情報ゲートウェイはドライバーを認証し、あり得ない地点（4 秒で 50 km の移動など）を捨て、各更新を Kafka のような、都市ごとにパーティション分割したストリームに書き込みます。

ストリームを読むコンシューマーは 3 つです。

1. ライブの地理空間インデックスは、空車の各ドライバーの最新位置だけを短い有効期限付きで保持します。スマートフォンが応答しなくなったドライバーは、たとえば 30 秒後に消えます。
2. 乗車トラッキングは、割り当てられたドライバーの位置を乗客のアプリに転送します。
3. コールドストレージは、分析、ETA モデル、紛争解決のために、全履歴をオブジェクトストレージに保存します。

重要な判断は、ホットなインデックスが更新ごとではなくドライバーごとに 1 行を持つことです。100 万人のドライバーがそれぞれ約 100 バイトなら合計約 100 MB で、都市ごとにメモリに収まる小ささです。

地理空間インデックス

マッチングでの問いは「この地点の近くにいる空車のドライバーは誰か」です。緯度と経度に対する普通のデータベースインデックスではうまく答えられないため、システムは座標をセルに対応付けます。

2018 年に Uber がオープンソース化した H3 では、半径検索が均一になります。乗客のセルとその周りのセルのリングを取り、その中のドライバーを集めるだけです。解像度は重要です。H3 の解像度表によると次のとおりです。

人口密度の高い都市には解像度 8 か 9 が適しており、郊外では広めのリングか粗いセルが必要です。

シンプルに始めたいなら、Redis には地理空間コマンドが組み込まれています。

GEOADD drivers:sf -122.4194 37.7749 driver:8812
GEOSEARCH drivers:sf FROMLONLAT -122.4100 37.7800 BYRADIUS 2 km ASC COUNT 20 WITHDIST

Redis 6.2 から使える GEOSEARCH は、半径 2 km 以内で最も近い 20 人のドライバーを距離順に返します。まずは自然な境界である都市でシャーディングし、空港やスタジアムのような非常に混雑する場所は、より細かいセルに分割します。

マッチングと配車

直線距離は迎車時間の目安としては不十分です。川の向こう岸で 500 m 先にいるドライバーが、15 分かかることもあります。そこでマッチングは 2 段階で行います。

1. 候補の生成。 地理インデックスに、乗車地点の近くにいる空車のドライバーを、車種などの条件で絞り込んで問い合わせます。
2. ランキング。 上位の候補について、道路網に基づく迎車時間を ETA サービスに問い合わせ、ETA にドライバーの進行方向などの要素を加えて順位を付けます。

各リクエストを即座に最寄りのドライバーとマッチングするのは貪欲法です。リクエストを 1〜2 秒ためて割り当て問題としてまとめて解くと、乗客全体の待ち時間の合計を最小化できます。混雑時により良いマッチングを得る代わりに、わずかな遅延が生じるというトレードオフです。

その後、配車は一度に 1 人のドライバーにだけ、約 15 秒のタイムアウト付きでオファーを送ります。拒否またはタイムアウトの場合は、次の候補にオファーが移ります。

ドライバーを二重に割り当てない

2 つのマッチングワーカーが、同じ 1 秒の間に同じドライバーを 2 人の乗客に選ぶことがあります。これはマッチングのロジックではなく、ドライバーの状態で防ぎます。

• 各ドライバーの状態（available、offered、on_trip）をバージョン番号とともに保存します。
• オファーは条件付き更新です。読み取ったバージョンで状態がまだ available の場合に限り、offered に設定します。
• 勝つワーカーはちょうど 1 つで、もう一方は次の候補に移ります。
• 期限切れのオファーは、やはり条件付きで、ドライバーを available に戻します。

同じコンペアアンドセットの考え方は乗客側も守ります。乗客ごとに有効なリクエストは 1 件だけです。

乗車の状態機械

乗車は requested、matching、driver_assigned、driver_arrived、in_progress、completed、paid と進み、いくつかの状態からはキャンセルも可能です。乗車サービスは各乗車を Postgres のようなリレーショナルデータベースに保存し、現在の状態が許す場合にだけ遷移を適用し、すべての変更を請求、通知、領収書、分析のためのイベントとして発行します。

すべての遷移を、乗車 ID と状態のバージョンをキーにして冪等にします。モバイルネットワークは再試行するため、2 回届いた「ドライバー到着」が何かを 2 回実行してはいけません。このライフサイクルだけを描く方法は状態遷移図の例で紹介しています。

ライブ更新、ETA、料金

乗車中、乗客のアプリはプッシュ接続を通じてドライバーの位置を受け取ります。更新は数秒ごとに間引かれ、クライアント側で滑らかに補間されます。同じ位置情報のストリームは、リアルタイムの交通情報を必要とする ETA サービスと、スライディングウィンドウでセルごとにリクエスト数と空車のドライバー数を比べるダイナミックプライシングにも供給されます。支払いは乗車後に決済プロバイダーを通じて行われます。この部分は決済ゲートウェイ連携の図で扱っています。

想定しておくべき障害

• ドライバーの接続が切れる。 アプリは再接続時に最新の地点だけを送り、インデックスは応答のないドライバーを期限切れにします。
• マッチングワーカーがオファーの途中でクラッシュする。 オファーには有効期限があり、オファーが失効するとドライバーは available に戻ります。
• ある都市のクラスターが落ちる。 すべてが都市ごとに分割されているので、障害はその都市内にとどまります。進行中の乗車は、永続的な乗車ストアに状態を保持しています。
• GPS の偽装。 ゲートウェイで速度とルートの妥当性をチェックすれば、粗雑なケースは捕まえられます。

ライドシェアの図

図の読み方は次のとおりです。

• フレームは 1 つの都市で、その中のすべてのパーティション境界です。
• 位置情報の経路は上段を通ります。 ドライバーアプリ、位置情報ゲートウェイ、Kafka と進み、そこから Redis の地理インデックスと、履歴用のオブジェクトストアに分かれます。
• リクエストの経路は下段を通ります。 乗客アプリがマッチングを呼び出し、マッチングは地理インデックスから候補を読み、ETA サービスに迎車時間を問い合わせ、ドライバーにオファーを送ります。
• 乗車サービスは状態機械を所有し、それを Postgres に保存します。
• Markdown ブロックは容量の数値を示しています。

リアルタイムシステムのシステム設計図を描く

• ホットパスとトランザクションのパスを分けます。 ここでは位置情報のストリームと乗車のライフサイクルとで、量も保証も障害の起き方も異なります。別々のレーンとして描きましょう。
• パーティションキーを図に書きます。 「都市ごとにパーティション分割」という一言が、スケーリングと障害の分離を説明します。
• 何が最新で何が履歴かを示します。 最新位置のインデックスと履歴のストアは、別々の問いに答えます。
• エッジにレートを書きます。 1 本の矢印に書かれた毎秒 250,000 件の更新が、負荷がどこにあるかをレビュー担当者に伝えます。

この種の図の一般的な進め方はシステム設計図の例を参照してください。プッシュ接続はチャットアプリのアーキテクチャ図で、ストリームそのものは Kafka のアーキテクチャ図で扱っています。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. 都市名を付けた基本パックの フレーム を追加します。
3. ドライバーアプリと乗客アプリ用に、ネットワークパックの デバイス ノードを 2 つ追加します。
4. 位置情報ゲートウェイ用にクラウドパックの APIゲートウェイ、ストリーム用にデータパックの Kafka ノード、地理インデックス用に Redis ノード、履歴用に オブジェクトストア を追加します。
5. マッチング、ETA、乗車の各サービス用にクラウドパックの コンピューティング ノードを 3 つ、乗車データ用にデータパックの Postgres ノードを追加します。
6. 位置情報の経路を上段に、リクエストの経路をその下に接続し、エッジには運ぶ内容と頻度をラベルとして付けます。
7. 容量の数値を書いた基本パックの Markdown ブロックを追加します。

この例で使うダイアグラムノードは 12 個で、Free プランの範囲に収まります。

よくある質問

ドライバーはどのくらいの頻度で位置を送信すべきですか？ 数秒ごとがよくある範囲です。更新を増やすと位置は新しくなりますが、取り込み量は何倍にもなります。間隔を 4 秒から 2 秒に半分にすれば、トラフィックは 2 倍になります。

geohash、S2、H3 のどれを使うべきですか？ どれでも機能します。geohash は最も単純で Redis に組み込まれています。H3 は隣接セルまでの距離が均一なので、半径検索やセルごとの料金設定がすっきりします。1 つを選んで一貫して使いましょう。

1 人のドライバーを 2 人の乗客に割り当てるのはどう防ぐのですか？ オファーをドライバーの状態に対する条件付き更新にします。そうすれば、マッチャーが読み取ったバージョンでドライバーがまだ空車の場合にだけ成功します。勝てるマッチャーは 1 つだけです。

なぜ各乗客をすぐに最寄りのドライバーとマッチングしないのですか？ 貪欲なマッチングでは、後から来た乗客が長く待たされることがあります。リクエストを 1〜2 秒まとめて一緒に解けば、わずかな遅延と引き換えに待ち時間の合計を減らせます。

乗車はどのデータベースに保存しますか？ リレーショナルデータベースがよく合います。乗車はトランザクション的で、厳格な状態遷移が必要で、請求処理にもつながるからです。大量の位置データは別の場所、つまりメモリとオブジェクトストレージに置きます。

無料で始める — 1 シート、クレジットカード不要。