オートモーティブ領域における 位置情報関連アルゴリズムあれこれ
?Download as PPTX, PDF?
3 likes?876 views
株式会社ディー?エヌ?エー オートモーティブ事業本部スマートタクシー事業部システム開発部 部長 惠良 和隆が 2019年12月14日に開催されたイベントで登壇した内容を紹介します。
![Redis Pub/Sub
? Redisが持つPub/Sub機能
? レプリケーションやクラスタ構成があってもPublishされたメッセー
ジが適切にSubscriberに届く
? パターンマッチによるSubscribeをサポート
? Glob形式のパターンにマッチするすべてのチャンネルのメッセージを受信可能
? hoge1, hoge2, hoge3 -> hoge? or hoge[1-3] or hoge*
Publisher
Subscriber
Subscriber
(2) publish ch1 “hello” (1) subscribe ch1
(3) “hello”
(1) psubscribe ch*
(3) “hello”
Redis Server](https://image.slidesharecdn.com/camphorerakazu3-191217061735/85/-39-320.jpg)
オートモーティブ領域における 位置情報関連アルゴリズムあれこれ
- 4. 現在のトレンド ? 自動運転 ? Waymo, Uber, Tesla, 各OEM ? MaaS（Mobility as a Service） ? ICT を活用して交通をクラウド化し、公共交通か否か、またその 運営主体にかかわらず、マイカー以外のすべての交通手段による モビリティ（移動）を 1 つのサービスとしてとらえ、シームレス につなぐ 新たな「移動」の概念である (国土交通省PRI Reviewより) ? 先行事例：Whim（MaaS Global社＠フィンランド） ? 日本では決済まで統合されたサービスが普及していない 4
- 5. MaaSのポイント ? 各公共交通サービスのIT化 ? 様々な交通サービスを跨いで横断的に活用する ? マイカー以外の、より自由な移动を実现する
- 6. DeNAにおけるMaaS ? 次世代タクシー配車アプリ『MOV』 ? タクシーのIT化 ? 効率的な配车システム、础滨を活用した推奨経路案内など
- 7. 交通のIT化における重要ポイント ? 車輛の状態の把握 ? 現在位置 ? 利用状況 ? 運行状況 ? MOVでは ? 車輛の情報を数秒間隔で収集 ? 収集された情報を元に、配車可能な車輛の把握を行う
- 8. 車輛情報はサービスの根幹 ? リアルタイム情報 ? 配車や現在の状況把握に必須 ? エンドユーザーに状況を伝えるためにも、低遅延な情報伝達が求められる ? 履歴情報 ? 過去の状況を確認するために必須 ? カスタマーサポート ? 分析 ? システムの動作検証などにも活用可能
- 9. 車輌情報に関する処理 ? 位置情報 ? 特定エリアに位置しているか？ ? 特定位置から一定距離内にいるか？ ? 要するに、Geolocation関連処理 ? 利用状況 ? 乗客を乗せているかどうか ? 運行状況 ? 休憩中かどうか 9
- 10. 重要ポイント ? 大量のリアルタイムデータを低遅延で送受信する ? 大量のリアルタイムデータを短時間で処理する ? Geolocation処理を適用する ? プロパティ値に従ってフィルタする 10 大量のデータを効率的に処理する技術
- 11. 11 大量のデータを処理する
- 12. 大量のデータを処理する技術 ? ＝大量のデータを収集する ? オーバーヘッドの少ない通信プロトコル ? 認証処理のタイミングと回数 ? データサイズ ? スケーラビリティの担保 12
- 13. オーバーヘッドの少ない通信プロトコル ? 数秒に１回ペースで通信するような場合、通信プロトコルで生じる オーバーヘッドは無視出来ない ? サーバー側で最も効率よく処理出来るものを選択すべし ? 常時接続型が望ましい ? gRPC/WebSocket/MQTT/TCP ? 実装のしやすさやポータビリティなどを考慮 ? MOVではgRPCを採用 13
- 14. gRPC ? RPCフレームワーク ? 様々な言語をサポート ? 以下のRPCライフサイクルに対応 ? Unary RPC ? Server Streaming RPC ? Client Streaming RPC ? Bidirectional Streaming RPC ? gRPC-Webの利用を考える場合 ? Unary RPC ? Server Streaming RPC 14
- 15. gRPC IDL Sample 15 service HelloService { rpc SayHello (HelloRequest) returns (HelloResponse) {} rpc LotsOfReplies(HelloRequest) returns (stream HelloResponse) {} rpc LotsOfGreetings(stream HelloRequest) returns (HelloResponse) {} rpc BidiHello(stream HelloRequest) returns (stream HelloResponse) {} } message HelloRequest { string greeting = 1; } message HelloResponse { string reply = 1; }
- 16. 認証処理のタイミングと回数 ? 認証処理はそれなりに重たい処理という認識 ? 無駄に実行されるとそれだけでサーバーに負荷がかかる ? 認証された接続であるという情報を再利用する 16
- 17. 認証手段の一例 ? Google Cloud Endpoints for gRPC ? SSL/TLSによる認証 ? Google ID Tokenによる認証 ? 独自の認証処理 17 基本的にAPI呼び出しごとに実行される サーバー側で管理しているコネクションと認証処理が１対１対応 するのであれば、認証結果をキャッシュするなどの効率化も可能
- 18. 18 つまり、
- 20. データサイズ ? 大量のデータを収集する場合、メッセージのデータサイズが超重要 ? 最適なデータ?フォーマットは、サーバーの実装にも大きく依存す る（特に速度面） ? 例えば、ProtocolBuffersはバイナリフォーマットでデータサイズも 小さいが、Pythonだとデシリアライズの速度が非常に遅い（特に、 C++実装をリンクしない場合） ? サイズだけで考えるとJSON + zlibという組み合わせも有り得る(当 然、処理速度はきちんと把握すること） 20
- 21. スケーラビリティの担保 ? ステートレスなHTTPサーバーなら苦労はほぼない ? 常時接続型ならではの問題 ? 負荷がかかっているサーバー＝接続数の多いサーバー ? 負荷上昇を検知してスケールアウトしてもコネクションが維持され ていると、検知したサーバーの負荷は低下しない 21
- 22. 例：KubernetesのHPAの場合 ? CPU負荷のしきい値（50％）を超えたらスケールアウト 22 apiVersion: autoscaling/v2beta1 kind: HorizontalPodAutoscaler metadata: name: server-hpa spec: minReplicas: 1 maxReplicas: 5 metrics: - type: Resource resource: name: cpu targetAverageUtilization: 50
- 26. スケーラビリティの担保 ? ステートレスなHTTPサーバーなら苦労はしない ? 常時接続型ならではの問題 ? 負荷がかかっているサーバー＝接続数の多いサーバー ? 負荷上昇を検知してスケールアウトしてもコネクションが維持され ていると、検知したサーバーの負荷は低下しない 26 クライアント側が定期的に接続し直すか、 サーバー側がコネクションを一定周期で切断する （結果として、クライアントが再接続する）
- 27. スケーラビリティの担保 ? ステートレスなHTTPサーバーなら苦労はしない ? 常時接続型ならではの問題 ? 負荷がかかっているサーバー＝接続数の多いサーバー ? 負荷上昇を検知してスケールアウトしてもコネクションが維持され ていると、検知したサーバーの負荷は低下しない ? バックエンドのServer to Serverの接続で常時接続を使う場合も同 様の問題が発生する 27 解決策として一番カンタンなのは、Envoyの導入
- 28. Envoy ? Lyftが開発したProxy ? Load Balancing ? Retry ? Circuit Breaking ? Rate Limiting ? …etc ? gRPC-Webのための変換プロキシとしても動作 ? JWTトークン検証によるリクエストの認証 ? 負荷分散 ? サービスディスカバリ 28
- 29. スケーラビリティの担保（Cont.） ? 大抵の場合は、Envoyで対処可能 ? ただし、特殊なサーバー実装を行う場合は別問題 ? 例えば、車輌からの接続は１コネクションに限定且つ１つのサー バープロセスだけで処理したい場合など、ステートフルな処理を実 装しようとすると、単純なロードバランシングでは対処できなくな る 29
- 30. スケーラビリティの担保（Cont.） ? 大抵の場合は、Envoyで対処可能 ? ただし、特殊なサーバー実装を行う場合は別問題 ? 例えば、車輌からの接続は１コネクションに限定且つ１つのサー バープロセスだけで処理したい場合など、ステートフルな処理を実 装しようとすると、単純なロードバランシングでは対処できなくな る 30 実装するサービスの仕様に適合する手段を検討する
- 32. 大量のデータを効率的に処理する技術 ? ＝大量のデータを収集する ? オーバーヘッドの少ない通信プロトコル ? 認証処理のタイミングと回数 ? データサイズ ? スケーラビリティの担保 ? 小さな処理を少しずつ実行 ? 十二分に最適化されたアルゴリズム 32
- 33. 小さな処理を少しずつ実行 ? まとめて処理するよりも、少しずつ処理した方が効率が良いことが 多い ? 負荷が集中しないことが重要 ? キャパシティプランニングの観点でも重要 33
- 34. MOVの事例 ? ユーザーからのリクエストに応じて、乗車地点の周囲にある車輌情 報を収集し、その車輌が特定エリアに含まれているか／いないかを 判定する 34 出典：政府統計の総合窓口(e-Stat)（https://www.e-stat.go.jp/） ?OpenStreetMap contributors
- 35. MOVの事例 ? ユーザーからのリクエストに応じて、乗車地点の周囲にある車輌情 報を収集し、その車輌が特定エリアに含まれているか／いないかを 判定する ? 周囲の車輌の数に応じて、Point-In-Polygonの判定回数が増減する ? ユーザーのリクエスト数に応じて、Point-In-Polygonの判定回数が 増減する 35
- 36. MOVの事例 ? 流入する全ての車輌データに対して、予め特定エリアに含まれてい るか／いないかを判定する ? Point-In-Polygonの判定回数は、車輌台数とデータ送信頻度に比例 するため、負荷の増減が予想可能 ? ユーザーアクセス数とは切り離される ? 天候による需要増加やマーケティング施策による需要増加に怯えず に済む 36
- 37. 十二分に最適化されたアルゴリズム ? 処理を小さくするには、無駄な計算を無くすことが重要 ? 世の中にある各種アルゴリズムは、十分に枯れたものであれば安定 した性能が期待出来る ? 一方で、汎用的なアルゴリズムは、特殊化されたアルゴリズムに比 べると数十?数百倍も低速という事も多々ある ? 車輪の再開発は避けつつ、適切なアルゴリズムを適切に利用するこ とが重要 37
- 38. 例）Message Dispatch ? 特定の情報を欲しているサーバープロセスが複数ある場合に、その 情報をどうやってサーバープロセスに届けるか？ ? サーバー間をgRPCで接続？ ? Redis Pub/Subやnatsを利用した方が、十分に最適化された実装の 恩恵を受けることが出来る 38
- 39. Redis Pub/Sub ? Redisが持つPub/Sub機能 ? レプリケーションやクラスタ構成があってもPublishされたメッセー ジが適切にSubscriberに届く ? パターンマッチによるSubscribeをサポート ? Glob形式のパターンにマッチするすべてのチャンネルのメッセージを受信可能 ? hoge1, hoge2, hoge3 -> hoge? or hoge[1-3] or hoge* Publisher Subscriber Subscriber (2) publish ch1 “hello” (1) subscribe ch1 (3) “hello” (1) psubscribe ch* (3) “hello” Redis Server
- 40. Pub/Subの使い方にも要注意 ? Redis Pub/Subそのものは単体でも高い性能を発揮するし、クラス タ化することでスケールアウトも可能 ? Subscriberでの処理が詰まることがよくある ? 大量のデータをPub/Subでディスパッチする場合、必要な情報を選 別するのはチャンネル名を使って行うべき ? とりあえず全部受け取り、その後で選別する場合、データ流量に対 応出来るだけの受信性能が必要になる 40 使い方を誤ってしまうとSubscriber側の処理が 大きくなる（≠小さな処理を少しずつ実行）
- 41. MOVでのRedis Pub/Subの利用例 ? チャンネル名は特定範囲を示す地域メッシュコードにする ? 全ての車輌情報は、その車輌の所属する地域メッシュのコードを チャンネル名としてPublishする ? 例）緯度経度から基準地域メッシュコードを算出 (35.659008, 139.703499) → 53393596 41
- 42. 地域メッシュコードとは？ ? 地域メッシュ ? 統計に利用するために、緯度?経度に基づいて地域を隙間なく網 の目（メッシュ）の区域に分けたもの ? 標準地域メッシュでは、第１次?第３次まで定められている ? さらに細分化した分割地域メッシュもある ? 地域メッシュコード ? 地域メッシュを識別するためのコード
- 43. ①第１次地域区画 およそ 80km 四方 東 京 度 40 分 経度１度 ５３３９ 総務省統計局 地域メッシュの区分図より抜粋
- 44. 1 ②第２次地域区画 足立区 江戸川区 葛飾区 江東区 北区 区 墨田区 文京区 千代田区 台東区 荒川区 中央区 およそ 10km 四方 第 1 次地域区画を 64 分割 (縦横それぞれ８等分) した区画 ５３３９-４６ 総務省統計局 地域メッシュの区分図より抜粋
- 45. 千代田 皇居外苑 隼町 丸の内 永田町１丁目 丸の 霞が関２丁目 霞が関１丁目 日比谷公園 有楽町１丁目 有楽町２ 霞が関３丁目 内幸町１丁目内幸町２丁目 銀 銀座目 虎ノ門１丁目 西新橋１丁目 虎ノ門２丁目 銀座 新橋１丁目 新橋２丁目 ③第３次地域区画＝基準地域メッシュ 第 2 次地域区画を 100 分割 (縦横それぞれ 10 等分) した区画 ５３３９-４６-００ およそ１ｋｍ四方（東京都の場合:縦 0.925km,横 1.132km） 足立区 江戸川区 葛飾区 江東区 北区 区 墨田区 文京区 千代田区 台東区 荒川区 中央区 総務省統計局 地域メッシュの区分図より抜粋
- 46. MOVでのRedis Pub/Subの利用例 ? チャンネル名は特定範囲を示す地域メッシュコードにする ? 全ての車輌情報は、その車輌の所属する地域メッシュのコードを チャンネル名としてPublishする ? 例）緯度経度から基準地域メッシュコードを算出 (35.659008, 139.703499) → 53393596 ? 大抵の場合、Subscriberは限られた範囲内の情報だけを必要とする ため、適切なチャンネル名だけをSubscribeすれば、不要なデータ を処理しなくても済む 46
- 48. MOVでのRedis Pub/Subの利用例 48 Redis Server Publisher Publisher Publisher Publisher Publisher Publisher Subscriber Subscriber Subscriber Subscriber 必要なデータだけを取得することで、データ流入量が増えて も各Subscriberで処理するデータ量は抑制できる subscribe 53393596 subscribe 53393595 subscribe 53393574 subscribe 53393496
- 49. 例）Point-In-Polygon ? Elasticsearch ? PostGIS ? GDAL/GEOS ? ソリューションはいくつも考えられるが、基本となるアルゴリズム は十分に枯れたものが採用されている ? ただし、Point-In-Polygonはデータ依存で計算量が変化 ? 重いデータを使うと計算時間がかかるので、小さな処理にするため の事前処理を行う 49
- 52. 事前処理：Polygonの細分化 52 絶対に交差する 交差する かもしれない 絶対に交差しない 出典：政府統計の総合窓口(e-Stat)（https://www.e-stat.go.jp/）
- 53. 事前処理：Polygonの細分化 53 切り出した小さなポリ ゴンとの判定を行う 交差する かもしれない 出典：政府統計の総合窓口(e-Stat)（https://www.e-stat.go.jp/）
- 55. 事前処理：Polygonの細分化 ? ポリゴンを一定サイズのメッシュで分割し、各メッシュに以下の情 報をもたせる ? 絶対に交差するかどうかのBOOL値 ? 交差するかもしれないメッシュは、切り出したポリゴンデータ ? 絶対に交差しないメッシュに関してはデータを持たない ? メッシュのIDと上記の情報のマッピングデータを事前計算 ? 分割に使うメッシュの大きさはポリゴンのサイズに合わせてアダプ ティブに設定 ? MOVでは地域メッシュを使って分割 55
- 56. 十二分に最適化されたアルゴリズム ? 処理を小さくするには、無駄な計算を無くすことが重要 ? 世の中にある各種アルゴリズムは、十分に枯れたものであれば安定 した性能が期待出来る ? 一方で、汎用的なアルゴリズムは、特殊化されたアルゴリズムに比 べると数十?数百倍も低速という事も多々ある ? 車輪の再開発は避けつつ、適切なアルゴリズムを適切に利用するこ とが重要 ? 利用シーンに合わせて、データや利用方法を特殊化することで最適 化を推し進める 56
- 57. 大量のデータを効率的に処理する技術 ? ＝大量のデータを収集する ? オーバーヘッドの少ない通信プロトコル ? 認証処理のタイミングと回数 ? データサイズ ? スケーラビリティの担保 ? 小さな処理を少しずつ実行 ? 十二分に最適化されたアルゴリズム 57
- 58. Kubernetes cluster #FCE4EC pod TechCon2019の後に作ったもの ? ユーザーアプリが周囲の車輌情報を取得するために使って いたPull型のAPIをPush型のAPIに置き換えるもの 58 AWS Cloud MOVの車輛情報収集システム Redis Cluster Container Engine SubscribeServer Container Engine PublishServer Container Engine DensityServer Container Engine gRPC gRPC pod pod pod
- 59. Kubernetes cluster #FCE4EC pod TechCon2019の後に作ったもの ? ユーザーアプリが周囲の車輌情報を取得するために使って いたPull型のAPIをPush型のAPIに置き換えるもの 59 AWS Cloud MOVの車輛情報収集システム Redis Cluster Container Engine SubscribeServer Container Engine PublishServer Container Engine DensityServer Container Engine gRPC gRPC pod pod pod AWSから送信される車輌データに対し て、ユーザーに見せて良い状態の車輌 かどうかを判定。パスした場合は、そ の車輌の座標に対応する3次メッシュ コードを算出し、それをチャンネル名 としてRedisにPublishする
- 60. Kubernetes cluster #FCE4EC pod TechCon2019の後に作ったもの ? ユーザーアプリが周囲の車輌情報を取得するために使って いたPull型のAPIをPush型のAPIに置き換えるもの 60 AWS Cloud MOVの車輛情報収集システム Redis Cluster Container Engine SubscribeServer Container Engine PublishServer Container Engine DensityServer Container Engine gRPC gRPC pod pod pod RedisにPublishされる全ての車輌 データを取得し、各３次メッシュ ごとの車輌密度を計算、その結果 をRedisにPublishする
- 61. Kubernetes cluster #FCE4EC pod TechCon2019の後に作ったもの ? ユーザーアプリが周囲の車輌情報を取得するために使って いたPull型のAPIをPush型のAPIに置き換えるもの 61 AWS Cloud MOVの車輛情報収集システム Redis Cluster Container Engine SubscribeServer Container Engine PublishServer Container Engine DensityServer Container Engine gRPC gRPC pod pod pod ユーザーの位置と周辺の車輌 密度から取得範囲を確定し、 その取得範囲の車輌情報を Subscribeする
- 62. まとめ ? オートモーティブ領域で求められる、大量のリアルタイム データを低遅延で処理するための技術について紹介した ? どのようなシステムも、はじめから最終的な利用シーンや サービス規模の拡大を想定してアーキテクチャを検討する 必要がある ? まず動くものを作るのも大切だが、それしか考えずにサー ビスを開発してしまうと、後々パフォーマンスで泣くこと になる（絶対に） 62