FB

NEWS

TOPICS

「MOBILITY:dev 2019」レポート ~「MOV」の効率的な配車を実現する、サーバーAPI実装の「超最適化」

10月31日に開催された、移動と交通を技術で変えたい、エンジニアのためのカンファレンス「MOBILITY:dev 2019」にて、DeNAオートモーティブ事業本部のメンバーが講演を行いました。レポート第2弾は、スマートタクシー事業部システム開発部部長の惠良が、次世代タクシー配車アプリ「MOV」におけるサーバー API 実装をどのように最適化したかについて話した講演をご紹介します。

「Point-In-Polygon」判定で、効率的な配車を

「MOV」は、ユーザーから配車をリクエストされた際に、迎車地に最も早く到着する車輌に配車依頼を送信するよう設計されています。その際に「MOV」では、交通圏に存在する複数のタクシーから「呼べる状態にあるかどうか」を判定し、その中から到着までの時間が最も短いタクシーを自動で選択しています。

「呼べる状態」というのは、「空車であること」「休憩中ではないこと」などの他に、「駅などのタクシー乗り場で、お客様を待つ列に並んで(駅待ちして)いない」という条件もあります。さらに迎車地についても、「歩行者天国や交通規制区域などのタクシーを呼べない場所」でないかどうかを「MOV」が判定する必要があります。

つまり、サービス圏内にいる乗客やタクシーが「配車禁止エリア※」にいないかどうかを判定することは、タクシー配車における必須処理といえます。これを実現するのが「Point-In-Polygon」という判定処理。あらかじめ定義されたポリゴン(配車禁止エリア)に、任意の点(乗客やタクシー)が含まれているかどうかを判定するものです。

※配車禁止エリア:タクシー乗り場や決まったタクシーのみが停まることのできる場所など配車依頼ができないエリア

紆余曲折した「Point-In-Polygon」判定手法

「Point-In-Polygon」判定の手法には様々なものがありますが、「MOV」では2018年4月のリリース当初、AWS の Elasticsearch Service を利用していました。

Elasticsearch では GIS 向けの機能が提供されており、データタイプとしても geo-point、geo-shape などの、ジオメトリとしての点やポリゴンが使えます。これらが交差しているかどうかの判定をクエリで利用できるため、車輌が配車禁止エリアに重なっているか、サービス圏に入っているかの判定をすることができます。

しかしその後、Elasticsearch Service の利用をやめることになります。MOVではタクシーの状態を AWS IoT で管理し、そのデータを Elasticsearch Service で検索可能にしています。かたや、乗客側のアプリは Google Cloud Platform のサービス API を経由して、Elasticsearch Service に車輌の情報を参照する構造でした。当時は、車輌の情報取得のために Elasticsearch Service を利用していることもあり、Point-In-Polygon にも利用することにしました。

ところが、Elasticsearch Service に AWS 外からアクセスする場合は、必ず AWS Sigv4 という認証処理が入るため、期待するスループットが出ないという問題がありました。さらに Elasticsearch Service にはオートスケール機能がないため、急に利用者が増えた際に、自動で台数を増やしてくれません。そのため、常に最大キャパシティでインスタンスを作る必要がありました。これではコストもかかってしまうため、別の方法を考えることにしました。

次の代替手段として採用されたのが、データベース管理システム「PostgreSQL」の拡張機能「PostGIS」でした。多種多様な GIS オペレーションを SQL で実現できることと、単純な QPS 性能は Elasticsearch よりも高いことから、実装が決定しました。フロントエンドとして GAE/python を採用し、API として利用できるよう実装されました。

しかし、PostGIS にはまた別の問題がありました。まず、PostgreSQL を動かしている CloudSQL はインスタンスのメモリ容量が多いほど、最大同時接続数が増える仕様になっています。そのため、負荷が上がったときに GAE 側でインスタンスがオートスケールしても、その後ろにある CloudSQL の最大接続数が少ない(=メモリ容量が少ない)と接続ができなくなります。そのため予め大量のメモリを積んだインスタンスを複数用意する必要があり、その結果コストが上がることに。さらに PostGIS 自体も、交通圏のポリゴンデータが多頂点となっているため、Point-In-Polygon 判定だけで数ms かかってしまう状況でした。元ゲーム開発者としては、1ms でも十分に遅いと感じるため、もう少し早くしたいという思いがありました。

そして、「超最適化」により実現できたこと

タクシーは、たとえば雨や暑さなど、天候によって需要が数倍から数十倍にも増えます。そのため、キャパシティには余裕が必要ですが、そのためのインフラ費用をどこまで削減できるかが重要になります。さらにユーザビリティを考慮すると、サーバー間の Point-In-Polygon 判定はできるだけ高速に処理したい。そこで「MOV」で行われたのが「超最適化」です。

それは「事前処理」をしっかり行った上で、PostGIS が内部で使っている GDAL を利用した Point-In-Polygon 判定を行うこと。

まずは交通圏をメッシュで切り、「絶対に(ポリゴンと)交差する」「絶対に(ポリゴンと)交差しない」「(ポリゴンと)交差するかもしれない」という3領域に分けます。そのうえで、「交差するかもしれない」領域から、メッシュ範囲内の部分を切り出し「ポリゴンの細分化」を行います。

そうして各メッシュに「絶対に交差する」「切り出したポリゴンと交差する」といった情報をもたせ、メッシュのIDとポリゴンデータをマッピングする。それによって、従来よりも複雑な計算がいらなくなり、サービスの速度を保つことができます。

もうひとつの事前処理が「ポリゴンのクラスタリング」。無数にある配車禁止エリアをあらかじめクラスタリングし、どのポリゴンがどのメッシュに含まれるかを事前に判断できるようにします。そして、そのマッピングデータを各メッシュの ID にひもづけます。

最終的には、事前計算を行ったデータを protocol buffers 形式のバイナリファイルとして事前に作成し、 Google Cloud Storage に配置しておきます。そのデータをサーバー側でメモリにロードしておき、オンメモリですべての処理を行うという形にしました。実装言語は、メンテナンス性と実行速度を考慮して Go を選択し、GKE 上に Go 実装された Web サーバーの構築を行いました。

こうしたデータの適切な事前処理を含む「超最適化」によって、交通圏判定 API 、配車禁止エリア判定 API ともに、従来よりも圧倒的に高速化されました。処理された交通圏や配車禁止エリアデータはサイズがそれほど大きくないため、すべてメモリに載せることで GDAL の計算がすぐにできる状態となったのも、大きなポイントです。

高速化したことで実行性能が数百倍となり、インスタンスあたりの性能キャパシティが大幅に拡大しました。結果としてユーザーが急に増えても、慌てて台数を増やさなくても大丈夫な形となりました。キャパシティが拡大したため、通常時のユーザー数だと1~2%程度の状態で稼働できるようになり、GKE のスケーリング速度でも十分耐えられるシステムを作ることができました。

これらをもって講演は終了。「MOV」のサーバー API 実装の事例を通して、交通系サービスにおける開発視点を学ぶ時間となりました。

【登壇資料はこちらをチェックください!→https://www.slideshare.net/dena_tech/movapi-mobilitydev

 

DeNAオートモーティブでは、さまざまなイベントを通して、開発した技術や経験を発表していきます。ぜひこれからもチェックしてください。