ソフトウェア開発では、特に厳しいリソース制限の下で動作し、MVPがその価値を証明する前にコストを最小限にしようとしているときに、多くの場合、興味深い課題に直面します。
Reverse Geocodingについて
2019年末、私は友達と一緒に、小さなiOSアプリの開発に取り組んでいました。AWAYアプリは、ユーザーが訪れた国の一覧を維持し、他の人と共有することを可能にします。その背後にあるコアコンセプトは、ユーザーが訪れた国を手動で入力する必要はありません。
あなたの携帯電話に写真が含まれている場合は、メディアライブラリへのアクセスを要求して受信した場合、アプリは、EXIFメタデータから各写真が撮影された場所の緯度と長さを読み取ることができます。
地理座標から住所(この場合、国名)を取得するこのプロセスは、reverse geocoding参考として、このプロセスの逆 - テキストアドレスから地理座標を取得する - は、前向きの地理コードと呼ばれます。
第三者ソリューション
私たちのMVPを開発するとき、私たちは利用可能で最も単純なオプションから始めました。Appleのデフォルトソリューションアプリケーションは機能し、国が自動的にリストに追加され、私たちは最初のユーザーを引き付けるようになりました。
しかし、我々はすぐに重大な制限に直面した。Appleのソリューションは、そのAPIへのネットワークリクエストに対する厳格な料金制限により非常に遅かったため、座標のバッチ処理のために設計されていなかった。
このような長い待機時間は必然的に私たちのアプリのウィルリティを損なった。訪問した国の一覧をすぐに受け取ってインスタグラムやフェイスブックで共有する代わりに、ユーザーはプロセスが終わるのを待つことなく去ります。
より適切な第三者ソリューションが見つかりませんでした。Googleので、マップボックス, and other similar APIs either had the same problems as Apple — being poor-fit for batch processing and offering no time-saving advantage — or would have been prohibitively expensive given the volume of coordinates we needed to handle. 多くの場合、それは両方であった。候補適切なサーバーをレンタルする費用がかかるため、あまりにも高額になります。
安価なオフ・ザ・シェルフオプションがないので、バックエンドの責任者として、私自身のAPIを構築し始めた。
ジョジョン
このプロジェクトの前に、地理空間データで作業する経験はなかったので、アプリケーションを開発する際にすべてを学ぶ必要があった。
実装に必要な最初のものは、座標を一致させるために国境に関する情報でした。GeoJSON.
GeoJSON は、任意の複雑さのポイント、ライン、形状を記述することを可能にする特定の構造を持つ標準の JSON ファイルです。
たとえば、イタリアの領土に関する情報を保存したいとします。Feature国の境界は、Aの範囲内で記述される。MultiPolygon各ポリゴンは1つまたは複数の座標の組合で構成され、座標の最初と最後の組合は[lon, lat]最初のマレージで説明された形は、全体的な地理的ゾーンに追加されます、この場合、イタリア自体は、サルディニア島と一緒に(島は別々の多角形で記述されます) このマレージの座標は、時計方向にリストされなければなりません。
ポリゴン内のいかなる次なる配列もオプションであり、排除された領域を表します。これは、サンマリノやバチカンなどのイタリアに完全に囲まれた都市国家などの領土を除外するために必要となります。これらの配列の座標は時刻表に記載されなければなりません。私たちが指定するポイントは、国の国境がより正確になります。
国名などのメタデータは、組み込まれたデータに含めることができます。properties客体
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"geometry": {
"type": "MultiPolygon",
"coordinates": [
[ // Polygon
// Exterior ring, Italy
[ [20, 35],[10, 30],[10, 10], ... ,[45, 20],[20, 35]],
// Interior "excluding" ring, San-Marino
[ [30, 20],[20, 15],[20, 25], ... ,[30, 20]]
],
[ // Polygon
// Exterior ring, Sardinia
[ [40, 40],[20, 45], [45, 30], ... ,[40, 40]]
]
]
},
"properties": {
"country": "Italy",
}
}
]
}
Geodataの準備
世界地図を作成するには、すべての国境の座標を含む最も正確なGeoJSONファイルをソースする必要があり、驚くほど挑戦的でした。
私は、複数のオープンソースに依存し、合計データを含む海洋学研究所で、npmjs.org からのパッケージ, and open geographic data from候補私が得たすべてのデータの共通の問題は、その品質でした。時には、国境が重なり、特に地域間の政治的紛争の場合です。他のケースでは、領水を含むデータのみが利用可能で、それは私たちのニーズに適していませんでした。フランダース海事研究所必要なデータを提供するために) 時には、解像度(座標の数)が信頼性の高い地理コード化のために低すぎて、代替案を探す必要があった。
アプリケーションの要件は非常に厳しいものであり、それぞれの高解像度の地理領域(領水なし)の正確で重複しない境界線(アプリ内地図で表示する)と領水を含む低解像度の境界線(地理コードをより迅速かつ効率的に行うため、特に沿岸線付近の船舶で撮影された写真)が必要でした。
1週間半の精密な作業の後、私は2つの高解像度のGeoJSONファイルを作成することができました。countries_maritime.json領水を含むすべての国の国境を記述し、他国は、countries_coastline.jsonそれぞれのファイルは数百メガバイトの大きさで、結局、私は世界のあらゆる角を個人的に訪れたような気がした。
花火
リリースされたとき、アップデートされたバージョンのアプリは、ユーザーのメディアライブラリからこれまで処理されていなかったすべての写真の座標を1万バッチで収集し、複数のリクエストでバックエンドに送信しました。
Node.js に構築され、AWS でホストされたバックエンドは、countries_maritime.json初期化時にファイルをメモリに戻します. 座標のバッチが到着したときに、ポリゴン見どころ図書館は、250カ国を含むファイルから、それぞれの領土に座標を合わせる。
私たちはまた、飛行機の翼の典型的なインスタグラムスタイルの写真を数えるのを避けるために、8 850メートル(エベレストの頂点を少し上回る)を超える高さの座標も捨てました(飛行機は通常、9000メートル以上の高さで飛ぶ)。
試合が見つかったとき、その国の識別子は、propertyすべての座標を処理した後、記録された識別子のリストはデダプライクされ、ユーザーの訪問国リストに追加され、クライアントに返され、アプリをバックエンドデータベースと同期します。
私たちのカスタムソリューションに切り替えると、ピーク処理速度は1秒間に1万座標に達した。(合成テストでは)ユーザーのメディアライブラリを処理するためのメディア時間は20〜25秒に減少した(ユーザー登録から訪問国リストを返すまで)、そして、1ユーザーあたりの平均追加国数が225%増加より正確な地理コードを
地理管理
アプリが成長し続けるにつれて、ユーザーは機能リクエストを提出し始めました. 最も頻繁なリクエストの1つは、各国内の地域や主要都市の自動認識の追加でした。
250カ国の国境に関する質の高いデータを収集することはすでに困難だったが、何千もの地域や都市について同じようなデータを収集する見通しはさらに恐ろしかった。
この問題に対処するために、JSON ファイルから領域を Postgres テーブルに移行し、地理区域を管理するための管理インターフェイスを開発しました。
私が直面した最初の問題は、地理領域データの固有の複雑さでした 地域と都市の間に普遍的に明確な区別はありません、そして異なる国には異なるレベルの行政分割があります。トップページ > トップページ, 条件と再発呼び出しを使用して、行政センター、人口のサイズ、および内部関係によってフィルタリングします. This also involved studying how to split and organize geographic nodes, their relationships, and nested structures, and correcting some erroneous data.
二つ目の課題は、地域の境界の座標源と協力して発生しました。地域や都市のためのosmIdのリストを取得した後、私はその境界の地理を抽出する必要がありました。トップページ > openstreetmap.orgしかも、ほぼ未記録のトップページ > openstreetmap.frこれらのソースは不完全だったので、複数のリクエストを送信し、結果を比較し、返されたデータの品質に基づいて最適なマッチを選択しました。
文書の欠如、複雑なデータ関係、およびソースの不一致にもかかわらず、私は安定したソリューションを作成することができました. admin panel interface now allows for the automatic loading of city and region lists for any country with just a few clicks, including their metadata and the best available boundary geometries. The data is then stored in the database, where it can be further refined for user availability, caching, and inclusion in the geocoding index.管理パネルインターフェイスは、いくつかのクリックで、どの国の都市や地域のリストを自動的にロードすることを可能にします。
GeoJSON データの頻繁な問題に対処するために、私は分割、合併、抽出、そして欠けている境界地理を描くことを可能にする組み込みのエディターを開発しました。
これらのツールはすべて、たった2人のチームで、私たちは1カ月半以内にユーザーに紹介できる地域と都市のデータベースを作成することができます。
現在、App は 3,134 地域と 28,083 都市をサポートしています。それぞれに正確な境界線があり、それらを訪れたユーザーの数を追跡します。
地質の最小化
Node.js で 31,467 領域を処理することは、インデックスの初期化段階ですでにパフォーマンスとリソースの制限により管理できないようになりました。
先ほど述べたように、アプリの表示と地理コードに必要なデータには非常に異なる要件がありました:アプリでレンダリングするための地図タイルの準備は数分間かかることができましたが、地理コードはデータボリュームに非常に敏感で、その速度は領土境界内の座標数に直接関連しています。
私は複数のアルゴリズムを実験して、多角の座標連鎖を簡素化しました。
最初のアプローチは、ラマー・ダグラス・ピューカーそのアプローチは不安定で、さまざまな GeoJSON ファイル間の共有境界の不一致を引き起こし、島などの小さな詳細の損失も引き起こした。
結局、私自身の実装を開発しました。(npm パッケージとして公開) based on theワイワイワイこのアルゴリズムの既存の実装は、GeoJSON構造の特定の部分にのみ適用することができ、結果の安定性の問題を解決したが、それでも限界の著しい劣化と小さな詳細の喪失を引き起こした。ハープ(集合元素として3つの隣接する座標の角度を用いて)、共通点保存のための追加の論理を持つ1つの曲線として処理した後、最終オブジェクトに再構築した。
私自身の実装を開発しました。データの量を減らすことに加えて、この GeoJSON ファイルの再構造化は、データ内の多くのエラーや矛盾を発見するのに役立ちました。
- 未開封の座標
- 間違った座標の折りたたみによる対立する配列。
- 空の座標アーレイ
- 過剰な巣立つ
- 座標の正確性の欠如
私は、これらのエラーの検証と訂正を、既存のツールを用いて、部分的に自動化しました。ポリゴンカットで、マップボックス / Geojsonhintで、マップボックス/geojson-rewindで、マップボックス/geojson-extentこれらは、個々の多角体を複数の多角体と地理学集合に合併し、座標解像度を必要なレベルに減らし、座標方向を訂正し、空の配列を除去することを含んだ。
その結果、地理データ処理のパフォーマンスが大幅に向上しました。さらに、私のアルゴリズムの安定性は、地図上の隣接する地域間の単純な境界線の不一致の問題を解決しました。
マイクロサービス
地理データの簡素化によって計算負荷を減らすにもかかわらず、Node.js は間違いなく私たちのニーズに最適なソリューションではないことが明らかになりました。ポストパフォーマンスとリソース消費の測定を含む幅広い研究の後、私は後者を選びました - Go で構築されたシンプルなマイクロサービス。
マイクロサービスアーキテクチャは、座標ペア処理の速度を最大化し、不要な操作を最小化するように設計されています。
最初の実行時に、マイクロサービスは PostgreSQL に接続し、100 個のオブジェクトのバッチで関連する GeoJSON データをすべて取得します。このデータは、それぞれにポリゴンと関連する領域識別子を含む構造に分類されます。
構造が整った後、ARツリーこのタイプの木は、多くの場合、多面性データの検索インデックスを作成するために使用されます。この木は、標的多角を含む最小の境界直角のためのロガリズム時間の検索を可能にします。
ツリーが構築された後、マイクロサービスは入力要求を待って聴く状態に入ります。
要求が受信されるときは、座標カップルで構成される[lat, lon]multithreaded 処理が開始されます. 結果は、提供された座標を含むユニークな領域識別子の数列です。
各座標は最初にR-ツリーを介して検索を行う。この検索は、座標を含む可能性のある多角形を含む正方角を返す可能性があります。Ray-Castingアルゴリズムこのアルゴリズムは、リニアタイムで動作し、プロセスの最もリソース密集部分となっています。しかし、レイキャストチェックを実行する前に、私は、リクエスト内の他の座標の処理中に、多角の領土識別子が既に発見されたかどうかを確認します。
すべてのトレードが仕事を終えた後、識別子の数列が Node.js レイヤーに戻ります. Below, I have tried to represent the architecture in the following diagram:
検索プロセス全体は、繰り返しのレー・キャッシング・チェックを省略するための特定の最適化に加え、PostGISがどのように類似のタスクを処理するかを密接に反映しています。ギフトインデックス
Go マイクロサービスの周りに構築された API を使用すると、私たちは1秒間に約10万の座標カップルの処理能力を達成しました。比較すると、以前の Node.js ソリューションは、ネットワーク リクエストとバックエンド オペレーションを含む 250 ゾーンの約 10,000 つの座標 ペアを管理しました。
この処理速度の大幅な改善により、ユーザーが訪問した国のリストをより迅速に作成することが可能となりました。このアプリは、アクティブユーザー数が160%増加し、ユーザー共有率が107%増加した。その結果
このソリューションは現在も使用されており、ますます増大するリクエストと地理ゾーンを効率的に処理し続けています。注目すべきことに、バックエンド全体は1ギガバイト未満のRAMで動作し、最適化されたリソース利用を示しています。
