UberのチーフシステムアーキテクトであるMatt Ranney氏は、Uberのディスパッチシステムを紹介した。このシステムはUberのパートナー、つまり、運転手や乗客をマッチングする役割を担う。氏は、このシステムを完全に書き直すことになった理由を説明している。また、このシステム支える設計原則、可用性や性能、アルゴリズム、そして、独自のRPCプロトコルを設計実装した理由について説明している。
古いディスパッチシステムは個人輸送(1人の運転手、1台の自動車、1人の乗客)のために設計され、人を輸送するという概念の周辺に構築されていた。しかし、Uberは新しい市場に参入したいと思っている。例えば、物の輸送だ。また、同社は取得したデータを市ごとに分けている。Uberが成長し多くの市に広がり、その中には巨大都市もあり、データの管理が難しくなった。最終的にディスパッチシステムは複数の障害ポイントを持ってしまった。同社の強烈な成長に追いつこうとした結果だ。
新しいディスパッチシステムはふたつのサービスを持っている。供給側のサービス、つまり、運転手のためのサービスと、需要側のサービス、つまり、乗客のためのサービスだ。このふたつのサービスは供給側と需要側の能力と状態マシンを追跡する。例えば、供給側のサービスはひとつの自動車が持っている座席の数や車いすで乗車できるかどうかの情報を持っている。ディスパッチシステムの第3のシステムはDisco (Dispatch Optimization)と呼ばれており、供給と需要をマッチングする。UberはDiscoを使って"未来を覗き込み"、情報を使う。例えば、古いディスパッチシステムは現在利用可能な供給しか見えなかった。ほとんどのパートナーはいつも忙しいので、このシステムの場合、Uberはグローバルインデックスをメンテナンスすることができた。新しいディスパッチシステムはもっと効率的だが、より多くのデータを必要とする。Uberはこの新しいシステムで秒間100万の書き込みとより高速な読み込みを扱いたいと考えている。なので、データを分割する必要があった。
このスケールを達成するため、UberはGoogleのS2 Geometry Libraryを使っている。S2は球体をセルに分割する。それぞれのセルはidを持っている。地球はほとんど球体なので、S2は64ビットの数値で平方センチメートルを表現できる。UberにとってS2にはふたつの重要な属性がある。各セルの解像度を定義できるということ、ある特定の領域を与えるとセルを特定できるという属性だ。Uberは3,31平方キロメータのセルでデータを分割している。新しいデータによってUberは待ち時間を少なくし、パートナーによる不要な運転を削減し、到着予定時刻(ETA)を短くする。では、乗客がUberを使うとき何が起きるだろうか。Uberは乗客の位置とS2のエリアカバレッジ機能を使って乗客にマッチする運転手を見つける。そして、最も短いETAを選択する。このとき、稼働できる運転手だけでなく、時間内に乗客を乗せることができる運転手も考慮する。
ディスパッチシステムの大部分はNodeJSで構築されている。つまり、シングルスレッドであるということだ。Uberはひとつのマシンのすべてのコアを活用したいと考えているが、新しいノードをシステムに簡単に追加できるようにしておくことも必要だ。Ranney氏によれば、サーバはステートフルでなければならない。そうでなければ、データストアがロードに耐えられないからだ。Uberはすべてのディスパッチプロセスを同じように扱っている。同じマシンで実行中かどうかにかかわらずだ。この問題に対処するために同社はringpopを開発した。これは、AmazonのDynamoやmemcached、Riakでノード間で状態の分散を実現しているコンシステントハッシュリングという技術を使っている。クラスタのメンバシップと失敗検知を管理するため、RingpopはSWIMを使っている。SWIMはScalable Weakly-consistent, Infection-style Process Group Membershipプロトコルをいう意味だ。これは、HashicorpのSerfでも利用されている。RingpopはRPCプロトコルとしてTChannelを使っている。これもUberが作ったものだ。
TChannelはFinagleの多重送信RPCプロトコルであるMuxに着想を得ている。これは、Twitterで開発された。Uberが独自プロトコル開発の必要を感じたのは、複数の言語(javascriptとpython)、トレーシング、カプセル化をサポートする必要があったからだ。Ranney氏に言うには、UberはHTTP+JSONからTChannelとThriftの世界へ移行している。TChannelはNodeJSで使った場合、HTTPよりも21倍速いという。
Uberの設計上の選択のほとんどは可用性と性能に基づいている。そうすることで運転手と乗客を簡単に競争状態にできるからだ。Uberでは、データベースを含むすべてが再試行可能で、冪等で、停止可能でなければならない。システムのどの部分もプロセスがシャットダウンするのはクラッシュのときのみと考えられている。これらの制約は小さなサービスに向いている。クラッシュしたとしても、影響範囲が限られているからだ。
小さなサービスのが増え、極端に分散すると性能に影響が出る。リクエスト全体の遅延が、最も遅いコンポーネントの遅延よりも大きくなるか等しくなる。Ranney氏はこの点についてGoogleのJeffrey Dean氏の手法を好む。例えば、TChannelは"リクエストをバックアップし、サーバに股がった取り消し"ができる。つまり、同じリクエストが同じサービスのふたつのインスタンスに送られ、そのふたつの間にわずかな遅延がある場合、最初に応答するインスタンスがふたつ目のインスタンスへのリクエストのキャンセルを行い、無駄な処理は排除する。
Uberはデータセンター障害対策はかなり工夫されている。データセンター間で複製されているデータはない。複製すると可用性と一貫性にたくさんの制約が生まれるからだ。Uberは運転手の電話を使ってデータを分散している。4秒に1回、運転手が位置情報の更新をポストするのであれば、サーバは暗号化した状態のダイジェストを応答すればいい。データセンターが霜害を起こしたら、運転手は新しいデータセンターに更新された位置情報をポストすればいいのだ。新しいデータセンターは特定の運転手については何もしらないので、状態のダイジェストを問い合わせ、そこから情報を取り出す。
ディスパッチシステムはNodeJSで作られているが、Uberはio.jsに切り替えようと考えている。io.jsはNodeJSのフォークだ。Ranney氏はUberの設計上のコンポーネントにも簡単に言及した。地図とETAは複数の言語で書かれている。C++やJavaだ。というのは、他の種類のサービスと統合する必要があるからだ。すべてのビジネスロジックはPythonで書かれている。独自の列指向分散データストアを構築しているが、PostgresやMySQL、Redis、Riakも使っている。