この記事は「彩雲天気地理查询优化: 最近的 N 个点」からの転載です。
まず実際の業務シナリオから始めます：
北京市海淀区の 768 創意産業園から最も近い K 個の国家観測所をどうやって見つけるか？
一番単純な考え方は、候補となる全ての観測所を全件走査し、それぞれの観測所と 768 の距離を計算して、距離の小さい順に上位 K 件を選ぶ方法です。このコード自体は書くのは簡単です。しかし問題は遅いことです。
なぜパフォーマンスが問題になるのでしょうか。実システムでは距離を単純な 2 次元平面のユークリッド距離 $\sqrt{(x_{1} - x_{2})^2 + (y_{1} - y_{2})^2}$ で置き換えられないからです。地球は曲面なので、距離が十分に大きくなると地球の曲率が表面上の点同士の距離に影響を与えます。
最も正確な距離計算法はVincenty の公式です。計算は複雑で、多くの三角関数を含みます：
別の代替としてはハーファーサイン（haversine）式があります：
精度はやや劣りますが、気象データに対しては空間精度として十分です。ただしこの式も内部に複数の三角関数計算を含むため、CPU 上で三角関数の計算は加減乗除に比べて相対的に遅いです。候補データが数万件に達すると大きな CPU コストになります。
最初に行った最適化は緯度経度の範囲による粗いフィルタです。特定のバウンディングボックスに入る座標だけをハーバーサイン距離計算へ進め、その他はスキップします。この最適化後、一般的な観測所取得とソートは約 200,000ns、遅いクエリでは 400,000ns に達しました。
Go のような静的コンパイル言語にとってこれはまだ遅めです。ピーク時には 1 秒間に数万回のこの種の操作が発生するため、速度改善でコストを抑えたいと考えました。pprof でプロファイルを取ると、実際の CPU ホットスポットはメモリアロケーションであることがわかりました。長さが数万の slice を for ループで走査することでアロケーションが発生していました。したがって最適化の中心は全件走査を避けることで、地理的なインデックスが必要になりました。
コミュニティの RTree/QuadTree 実装を調査しましたが、いくつかのシナリオでまだ性能問題がありました。例えば一部のクエリが約 100,000ns かかり、KNN の実装でソートを行っていないため距離を自分で計算してソートする必要がありました。そこで、理解しやすく十分高速な独自の方法を実装することにしました。RTree が好きな方は心配しないでください。RTree は後の章で登場します。
着想は地図のタイル（slippy map tile）から得ました。各観測所が特定のズームレベルで地図上のどのタイル（x, y）に属するかを計算します。そして x, y に ±1/0 を加えることで周囲の 8 つのタイルを得られます：
| |
タイルインデックス構造のおかげで、最初のタイル計算（ここでは三角関数計算が必要）以外は、あとは加減算だけで済みます。
便宜上、内部ではマップにタイルインデックスを逆順の z,y,x で保存しています。これによりフィルタ時に全ての観測所を力任せに走査する必要がなく、9 つのキーだけを参照すればよくなります。
現在の観測所データセットでは、大陸アメリカ本土は比較的均等に分布していますが、その他の国や地域では分布が非常に不均一です。例えば中国の中東部は西部より密集しており、西ヨーロッパは東ヨーロッパより密度が高いです。そのため本番環境では二層の事前インデックス機構を採用し、高解像度タイルでデータが見つからない場合はより粗いスケールへフォールバックします。
この最適化により、観測所クエリは約 900ns〜3000ns まで短縮され、サービスの CPU 負荷はおよそ 10%低下しました。今後の計画として、空間分解能が不均一で希薄なデータに対しては RTree ベースのインデックスを用いて自動適応するオプションも設ける予定です。