MOVで実践したサーバーAPI実装の超最適化について [MOBILITY:dev]
?Download as PPTX, PDF?
4 likes?9,558 views
DeNAのオートモーティブ事業本部スマートタクシー事業部システム開発部 部長 惠良 和隆 が 2019/10/31 に MOBILITY:dev で 登壇した内容をご紹介します。
![MOVでのPoint-In-Polygon実装（２）
? 性能評価結果
? クエリ実行元は、Google Compute Engine上のインスタンスとする
? クエリ内容はどちらも同様の結果が得られるものとする
? 試験対象インスタンスのCPU負荷が65％程度になるようにクエリを実行する
28
Product Instance Type vCPU Memory
[GB]
QPS Response
Time [ms]
Elasticsearch c4.2xlarge
.elasticsearch
8 15 1615.85 6.189
PostGIS N/A 16 15 46303.36 0.66
1インスタンスあたりの性能](https://image.slidesharecdn.com/20191031mobilitydevera-191031084650/85/MOV-API-MOBILITY-dev-28-320.jpg)
![MOVでのPoint-In-Polygon実装（２）
? 性能評価結果
? クエリ実行元は、Google Compute Engine上のインスタンスとする
? クエリ内容はどちらも同様の結果が得られるものとする
? 試験対象インスタンスのCPU負荷が65％程度になるようにクエリを実行する
29
1インスタンスあたりの性能
PostGISのvCPUを考慮しても、QPSとResponse Timeが圧倒的
Product Instance Type vCPU Memory
[GB]
QPS Response
Time [ms]
Elasticsearch c4.2xlarge
.elasticsearch
8 15 1615.85 6.189
PostGIS N/A 16 15 46303.36 0.66](https://image.slidesharecdn.com/20191031mobilitydevera-191031084650/85/MOV-API-MOBILITY-dev-29-320.jpg)
MOVで実践したサーバーAPI実装の超最適化について [MOBILITY:dev]
- 4. MOVとは？ ? DeNAが提供するタクシー配車アプリ ? ITのチカラでタクシー利用を進化させるサービス ? 神奈川、東京、大阪、京都にサービス展開 ? 近くのタクシーがすぐに来る ? 車輌ステータスのモニタリングすることにより、 呼べるタクシー車輌を選んで配車している 4 ※MOVのシステムの詳細は、DeNA TechCon2019 の 『次世代タクシー配車サービス「MOV」を支える車載ハードウェアとソフトウェアの話」 を参照ください
- 10. 呼べる状態の車輌とは？ ? 空車であること ? タクシーの所属する交通圏に迎車地が含まれていること ? 休憩中など、MOV配車受付停止中でないこと ? 駅などのタクシー乗り場で、お客様を待つ列に並んでいな いこと（駅待ちしていないこと） 10
- 11. 呼べる状態の車輌とは？ ? 空車であること ? タクシーの所属する交通圏に迎車地が含まれていること ? 休憩中など、MOV配車受付停止中でないこと ? 駅などのタクシー乗り場で、お客様を待つ列に並んでいな いこと（駅待ちしていないこと） 11
- 12. 呼べる状態の車輌とは？ ? 空車であること ? タクシーの所属する交通圏に迎車地が含まれていること ? 休憩中など、MOV配車受付停止中でないこと ? 駅などのタクシー乗り場で、お客様を待つ列に並んでいな いこと（駅待ちしていないこと） 12 駅待ちしていないことをどうやって判断するか？
- 15. タクシーを呼べない場所 ? そもそも車が進入できない場所 ? 車輌侵入禁止区域 ? 歩行者天国となっている道路 ? お祭りや花火などのイベントによる交通規制区域 ? 駅や空港、病院などの施設のタクシー乗り場 ? すべてのタクシーが乗り入れることが出来ない場所もある ? 交通渋滞緩和のための自主規制 ? お客様を乗せる順番は、タクシーの並び順に従うのが通常であり、 呼ばれたからと言って列に並ばずにお客様を乗せるとトラブルの 原因になりかねない 15
- 18. 本日お話する内容 ? タクシー配車における必須処理 ? Point-In-Polygon判定のための方法 ? 超最適化の手法 ? まとめ 18
- 19. Point-In-Polygon判定の手法 ? アルゴリズムには様々なものがあるが、いずれかを自前実 装する or 実装されたライブラリを利用する ? ElasticsearchのGeolocation機能を利用する ? PostGIS（PostgreSQLのExtension）の機能を利用する ? 様々なサービスが提供しているWeb APIを利用する 19
- 20. MOVでのPoint-In-Polygon実装（１） ? リリース最初期は、AWSのElasticsearch Serviceを利用 ? Elasticsearchには、GIS向けの機能が提供されている ? データタイプ：geo-point、geo-shape ? geo-shapeとgeo-pointが交差しているかの判定や、両者の距離 などをクエリで利用できる ? タクシー車輌位置を示すgeo-pointと交差するgeo-shape をもつドキュメントがインデックス内に存在するかどうか ? ユーザー位置を示すgeo-pointから半径Xm以内の距離にあ るドキュメント（geo-shape）を取得する 20
- 21. 21 その後???
- 23. MOVでのPoint-In-Polygon実装（１） ? MOVの構成（当時） 23 AWS IoT Core Amazon Elasticsearch Service Service API App Engine MySQL Cloud SQL AWS Cloud Android AndroidiOS 乗務員アプリ ユーザーアプリ
- 24. MOVでのPoint-In-Polygon実装（１） ? MOVのサービスAPIは、GCP環境（GAE/go）で動作して おり、AWSのマネージドサービスであるElasticsearch Serviceにアクセスする際に、必ずAWS Sigv4の認証が入 り、GCP-AWS間のレイテンシも存在する （インスタンス規模の割にスループットが出なかった） ? Elasticsearch Serviceはマネージドサービスではあるが、 オートスケールしてくれないので、急激な負荷の上昇など に対応できない 24
- 26. 26
- 27. MOVでのPoint-In-Polygon実装（２） 27 ? PostgreSQLの拡張機能であるPostGISを利用する ? PostgreSQL＠CloudSQLはPostGISをサポート ? Point-In-Polygon以外にも多種多様なGISオペレーション をSQLで実現できる ? 単純なQPS性能はElasticsearchよりもかなり高い ? フロントエンドとしてGAE/pythonを採用し、APIとして 利用できるように実装
- 28. MOVでのPoint-In-Polygon実装（２） ? 性能評価結果 ? クエリ実行元は、Google Compute Engine上のインスタンスとする ? クエリ内容はどちらも同様の結果が得られるものとする ? 試験対象インスタンスのCPU負荷が65％程度になるようにクエリを実行する 28 Product Instance Type vCPU Memory [GB] QPS Response Time [ms] Elasticsearch c4.2xlarge .elasticsearch 8 15 1615.85 6.189 PostGIS N/A 16 15 46303.36 0.66 1インスタンスあたりの性能
- 29. MOVでのPoint-In-Polygon実装（２） ? 性能評価結果 ? クエリ実行元は、Google Compute Engine上のインスタンスとする ? クエリ内容はどちらも同様の結果が得られるものとする ? 試験対象インスタンスのCPU負荷が65％程度になるようにクエリを実行する 29 1インスタンスあたりの性能 PostGISのvCPUを考慮しても、QPSとResponse Timeが圧倒的 Product Instance Type vCPU Memory [GB] QPS Response Time [ms] Elasticsearch c4.2xlarge .elasticsearch 8 15 1615.85 6.189 PostGIS N/A 16 15 46303.36 0.66
- 30. 30 その後???
- 33. MOVでのPoint-In-Polygon実装（２） ? CloudSQLのPostgreSQLは、インスタンスのメモリ容量 が多いほど最大同時接続数が増加する ? CloudSQLインスタンスのメモリが少ないと、 GAE側でイ ンスタンスがスケールしてもCloudSQLの最大同時接続数 に到達してしまい接続できなくなる ? 結果として、大量のメモリを積んだインスタンスを複数台 使用しなければならなくなり、コスト高に??? 33
- 34. MOVでのPoint-In-Polygon実装（２） ? CloudSQLのPostgreSQLは、インスタンスのメモリ容量 が多いほど最大同時接続数が増加する ? CloudSQLインスタンスのメモリが少ないと、 GAE側でイ ンスタンスがスケールしてもCloudSQLの最大同時接続数 に到達してしまい接続できなくなる ? 結果として、大量のメモリを積んだインスタンスを複数台 使用しなければならなくなり、コスト高に??? 34 PostGISのせいじゃないじゃん???
- 38. MOVでのPoint-In-Polygon実装（２） ? PostGISを使った判定にも性能的な課題はあった ? 交通圏のポリゴンデータが多頂点ポリゴンとなっており、 PostGISでもPoint-In-Polygon判定だけで数msかかって いた ? PostGISが内部で利用しているGDALを直接利用して判定 しても1ms以上かかることが判明した 38
- 39. MOVでのPoint-In-Polygon実装（２） ? Point-In-Polygon判定は、ユーザーアクセス数が増加する とそれに比例して増加するため、一定以上のキャパシティ が必要だが、インフラ費用を無駄に消費するのは避けたい ? 数ms程度なら十分高速な部類ではあるが、様々なAPIで利 用されるものであり、より高速にするとサービスAPIのレ イテンシを削減できる ? 何より??? 元ゲーム開発者としては、1msでも十分遅い！！！！ 39
- 40. 40 そして、超最適化へ???
- 44. 事前処理①：Polygonの細分化 44 絶対に交差する 交差する かもしれない 絶対に交差しない 出典：政府統計の総合窓口(e-Stat)（https://www.e-stat.go.jp/）
- 47. 事前処理①：Polygonの細分化 ? ポリゴンを一定サイズのメッシュで分割し、各メッシュに 以下の情報をもたせる ? 絶対に交差するかどうかのBOOL値 ? 交差するかもしれないメッシュは、切り出したポリゴンデータ ? 絶対に交差しないメッシュに関してはデータを持たない ? メッシュのIDと上記の情報のマッピングデータを事前計算 ? 分割に使うメッシュの大きさはポリゴンのサイズに合わせ てアダプティブに設定 ? MOVでは地域メッシュを使って分割 47
- 49. 事前処理②：ポリゴンのクラスタリング ? どのポリゴンがどのメッシュに含まれるかを事前計算 49 出典：政府統計の総合窓口(e-Stat)（https://www.e-stat.go.jp/）
- 51. MOVでのPoint-In-Polygon超最適化 ? GDALを直接利用して判定する ? ただし、最適化のための事前処理を行う ? 事前処理を行ったデータをすべてメモリにロードすることで全 計算をオンメモリで処理する （protocol buffers形式のバイナリファイルをGCSに配置） ? 実装言語はgolang ? GDALをgolangで使用するためには、cgoが必須 ?GAE/goは諦める ? GKE上にgolang実装されたWebサーバーを構築 51
- 52. MOVでのPoint-In-Polygon超最適化 ? インフラ構成 52 Kubernetes Cluster Container Engine Ingress Cloud Load Balancing Preprocessed Data Cloud Storage Polygon Meta Data Cloud SQL Service API App Engine
- 57. まとめ ? データに適切な事前処理を施すことにより、超効率的な Point-In-Polygon判定処理を実装した ? 全データをオンメモリとすることで、交通圏判定や配車禁 止エリア判定を超高速化できた ? 実行性能が数百倍になったことでインスタンスあたりの性 能キャパシティが大幅に拡大した ? 結果として、GAE/goほどのスピンアップ速度がなくても 負荷上昇に十分耐えられるシステムになった 57