Uberのリアルタイムマーケットプラットフォームのスケーリング

Scaling Uber's Real-time Market Platformという2015年のUserによるスケーリングに関する講演を見たので、簡単にまとめた。
他の海外の大きなサービスと比べても、技術的にはかなり複雑なように感じた。ユーザとドライバーをマッチングさせるところだけでも、リアルタイムで位置情報を更新するように大量のwriteリクエストを捌く必要がある。また、その位置情報からどのドライバーが最適なのかを選ぶのも、車種や乗車可能な人数、距離の計算なども遅延なく行わなければならない。また、支払いや

技術的に面白かったのは、スケーラブルと可用性を達成するために、スレッドがkillされたりノードがダウンするのも正常系の一部とする前提で設計が行われていたことだった。位置情報からの高速な検索も全く触れたことがなかったので興味深かった。

アーキテクチャ

f:id:hacking15dog:20200616113411p:plain

dispatch: 乗客とドライバーのマッチングとか。
maps/ETA: 交通マップや到着時間の計算など。
database: 色んな種類のものが使われている(Postgre, Redis, MySQL, Riak)
Post trip pipeline: 到着後の処理を扱う(ドライバー評価、メール送信、支払いなど)
money: 外部の支払いサービスとの連携

Problems

旧システムでは、以下のような前提で設計されていて、スケールさせるのが難しかった。アンチパターンではあるが、Dispatchを全部書き直した。

1ライダーに対して1台: Uber Poolとか他のビジネスに対応するのが難しい
人が動く: UserEatsのように食品とかが動くように適応するのが難しい
都市ごとにシャーディング: さらに都市を追加してスケールするためには、都市の大小差や負荷の差を考慮しなければならない
MPOF: Many Points Of Failures

Dispatch

supply（ドライバー）とdemand（乗客）をマッチングさせるサービス群。主にNode.jsで作られている。

位置情報は4秒に1回更新されるので、100万RPSに耐えられるぐらいかなりスケーラブルである必要がある。

主に以下のようなサービスから成る。

supply: ドライバーの情報(何人まで乗れるか、チャイルドシートはあるかなど)
demand: 注文の情報(何人乗る必要があるかなど)
DISCO: ビジネスロジックなど
geo by supply: ドライバーの位置情報
routing/ETA(Estimate Time of Arrival): 道路情報を加味して、距離を計算したりする
geo by demand: 乗客の位置情報(例えば、空港の何階にいるかなど)

S2

地球は球体なので、経緯度だけでは正確に計算を行うことが難しいため、S2を導入した。S2はGoogleのライブラリで、位置情報や計算を簡単に行える。

球体表面をcellで分割し、cellはidとlevelで表現され最小のcellは0.48cm²で、これは64bitで表現できる。

Level	最小面積	最大面積
0	85,011,012 km²	85,011,012 km²
1	21,252,753 km²	21,252,753 km²
12	3.31 km²	6.38 km²
30	0.48 cm²	0.93 cm²

このidをシャーディングとインデックスのキーとして使うことで、該当エリアにいるsupply一覧の取得等ができる。

Routing

目標

待ち時間を減らす
余分な運転を減らす
全ETAで最小にする

ベストな選択は、現在乗車可能なものとは限らない。例えば、今から1分後に近くで空きになるタクシーがベストな選択かもしれない。

スケーリング

Node.jsはそれぞれのモバイルのクライアントとのstateを保持しているため、単純なアプリケーションの水平スケーリングは適用できない。DBなどと同様にアプリケーションをstatefulにスケールさせないといけない。そこで、ringpopを開発した。CAP定理ではAP型で、可用性を重視している。ゴシップ型のメンバー管理で、アプリケーションレイヤーのシャーディングを行っている。クライアントからリクエストが来ると、適切なノードにリダイレクトする。

SWIM(Scalable Weakly-consistent Infection-style Process Group Membership)プロトコルがベースになっている。

TChannelというプロトコルでノード間の通信を行う。以下のような目標をもって設計されたプロトコル。

パフォーマンス: 特に複数の言語にまたがる箇所に関して。HTTPの20倍速い。
転送
言語サポート
正規パイプライン
チェックサム / トレーシング
カプセル化

eng.uber.com

可用性

ダウンしていると、他のサービスに流れてしまうので、遅延実行できるようにするなどしておかないとビジネス的に重要。

すべてリトライ可能に
すべてkillできるようにする: 失敗やダウンは例外ではなく、正常系の一つとして扱えるように。
クラッシュのみに対応: グレースフルシャットダウンに対応すると複雑性も増し、ちゃんと機能するかの確認も必要になってしまう
小さく分解する: 大きいインスタンスが少数だと、killするリスクが大きくなる

カルチャーチェンジ

すべて(DBでさえも)killする: Redisはリスタートのコストが高いので、この観点ではよくない

backup requests with cross server cancellation

分散システムで、レイテンシーを減らす方法。例えば、平均のレイテンシーは良いが、99パーセンタイルのレイテンシーが悪いときに、同じ種類のサービスに2リクエストを投げれば、どちらかのレスポンスは速く返ってくる可能性が高い。

詳細には、少し遅延してから2度目のリクエストを投げ、また1つ目のサービスは2つ目のサービスにキャンセルリクエストを投げる。遅延があることで、通常は1つ目のサービスのみが処理して、タイムアウトなどで失敗した場合は、2つ目のサービスがより低いレイテンシーで処理を返す。

更に詳細は、こちら。

f:id:hacking15dog:20200616113539p:plain

データセンターのダウン

DCが切り替わってもセッションや処理が継続しているかのように見せるために、定期的に状態のダイジェストをクライアントに保持させておき、データセンターがダウンすると、その情報をもとに再開させる。

lasciva blog

開発して得た知見やwebビジネスのストック