地理空間インデックス
翻訳の状態: 現行の英語版からの翻訳です。
TL;DR
空間インデックスは、「この近くに何があるか」「この点を含むものは何か」という問いに、すべてのオブジェクトと比較することなく答える。難しさは、通常のインデックスが1つの次元でソートするのに対し、位置は2次元であることだ。直線上にどう点を並べても、近くの点すべてを隣り合わせに保つことはできない。したがって実用的な設計はどれも、2次元を既存のストレージが扱える構造へ写す方法であり、どれも端で綻びる。
本番での利用のほぼすべては2つの系統で足りる。セルに基づく方式(ジオハッシュ、S2、H3)は、地表を、整数や文字列の識別子を持つセルの階層に切り分ける。位置はキーになり、領域はキー範囲の集合になり、順序付きストアやハッシュマップがそのまま扱える。木に基づく方式(R木、四分木)は外接矩形を直接索引し、ポリゴンや経路のような広がりを持つ形に向く。どちらも使い方は同じである。安く候補を返す粗いフィルタの段階のあとに、厳密な絞り込みの段階が続く。設計の中身は3つある。フィルタが緩すぎず、参照回数も多すぎないようにセルのレベルや木のファンアウトを選ぶこと。都心と砂漠のあいだの密度の偏りを扱うこと。そして高速に動くオブジェクトをどう書き込むかを決めることである。これらの構造が完全なシステムの中でどう使われるかは、UberとGoogle Mapsが示している。
一次資料と適用範囲
| 資料 | 示していること | 限界 |
|---|---|---|
| Finkel, Bentley (1974) | 四分木。複合キーのための再帰的な4分割 | 点を対象とした原型。その後多くの変種が続いた |
| Guttman (SIGMOD 1984) | R木。動的な挿入と削除ができる、最小外接矩形の平衡木 | 分割が悪いとノードの重なりが増える。のちの変種が詰め方を改善した |
| Samet (ACM Computing Surveys, 1984) | 四分木系の階層構造とその操作の分類 | サーベイであり、性能の主張ではない |
| S2 Geometry文書 | 立方体への射影とヒルベルト曲線を使った球面上のセル階層。64ビットのセル識別子と31のレベル | 1つのライブラリの設計 |
| H3文書 | 正二十面体を土台にした、16の解像度を持つ六角形の階層グリッド | 六角形は解像度をまたいで正確には入れ子にならない |
| Redis、PostGIS文書 | ソート済みセットにジオハッシュを入れる方式と、GiST上のR木インデックス。広く使われる2つのストアでの実装 | 文書化された版でのプロダクトの振る舞い |
計算例の節のサイズとレートは例示である。
クエリと契約
空間ワークロードは、インデックスへの要求が異なる少数のクエリ形に還元できる。
| クエリ | 例 | インデックスがすべきこと |
|---|---|---|
| 半径検索、k近傍 | 2 km以内のドライバー。最も近い5店舗 | 点の周囲のセルを列挙し、結果が足りるまで広げる |
| バウンディングボックス | 表示中の地図タイル内のすべて | ボックスと交差するセルや矩形を範囲で取る |
| 点のポリゴン包含 | この住所はどの配送区域や課税地域に入るか | 候補のポリゴンを見つけ、厳密な包含判定を行う |
| 空間結合 | 地区ごとの乗車件数 | 大規模に、各点を領域へ割り当てる |
明文化すべき契約は次のとおり。座標参照系と軸の順序。距離の定義(球面上の直線距離か、ネットワーク上の移動距離か)。動くオブジェクトの最大の古さ。結果の厳密さ(半径のわずかに外の結果が出てよいか)。そして1つのクエリが覆ってよい最大の領域。
直線距離がプロダクトの要件であることはまれだ。大圏距離で最も近いドライバーは、橋のない川の向こうにいるかもしれない。空間インデックスが出すのは候補であり、移動時間による順位付けは経路探索エンジンの仕事である。
フィルタと絞り込みのパターン
円や任意のポリゴンに一致するセルグリッドはない。そのためインデックスは答えを含む上位集合を返し、厳密な幾何計算が余分を取り除く。コストは 参照回数 + 候補数 x 厳密判定のコスト である。粗いセルでは参照が少なく偽の候補が多い。細かいセルではその逆になる。最良のレベルは、セルがクエリ領域とおおよそ同じ大きさになるレベルである。システムが同じオブジェクトを複数のレベルで索引したり、クエリごとにレベルを選んだりするのはこのためだ。
ジオハッシュ: ビットを交互に並べた文字列
ジオハッシュは経度の範囲を半分に分け、次に緯度の範囲を半分に分け、これを繰り返して、分割ごとに1ビットを出力する。2つのビット列を交互に並べるとZ階数曲線をたどることになり、5ビットずつを32進の1文字に符号化すると文字列になる。文字列を切り詰めると、それを含むセルが得られる。つまり前方一致が包含関係になる。
| 長さ | 赤道でのおおよそのセルサイズ |
|---|---|
| 5 | 4.9 km x 4.9 km |
| 6 | 1.2 km x 0.61 km |
| 7 | 153 m x 153 m |
| 8 | 38 m x 19 m |
魅力は、ストアに特別な機能を求めないことだ。通常のインデックスを張った文字列の列で、前方一致クエリに答えられる。文書化済み、Redis: 地理空間コマンドは、各メンバーをソート済みセットに保存し、ジオハッシュから導いた整数をスコアとする。半径クエリは、スコア範囲のスキャンと、それに続く距離でのフィルタになる。
その限界が、乗り換えどきを決める。
- 境界での不連続。 セルの境界をはさんで1メートルしか離れていない2点が、前方をまったく共有しないことがある。正しい近接クエリは、対象のセルとその周囲8セルを必ず検索する。
- 形と面積の歪み。 セルは緯度と経度の矩形なので、地表での幅は極に向かって縮む。
- Z階数の飛び。 この曲線は象限のあいだで大きく飛ぶので、小さな領域が多数の離れたキー範囲に対応することがある。
S2: 球面上のセルとヒルベルト曲線
文書化済み: S2は球面を立方体の6つの面へ射影し、各面を四分木として面の下30レベルまで細分し、セルにヒルベルト曲線に沿って番号を振る。セル識別子は64ビット整数で、親の識別子の範囲がすべての子孫を含む。葉のセルは1平方センチメートル程度である。
システム設計にとって重要な性質は3つある。
- 包含は範囲の検査である。 あるセルの子孫はすべて、1つの連続した整数区間に入る。「このセルの中のすべて」は、ソート済みキーへの1回の範囲スキャンになる。
- 局所性がよい。 ヒルベルト曲線には大きな飛びがない。領域は、Z階数曲線で必要になるより少なく長い範囲で覆える。
- 領域の被覆がライブラリ関数である。 カバラーは、指定したセル数の予算の範囲で、任意の領域を覆う少数のセルを、レベルを混ぜて返す。この予算は、フィルタの粗さと参照回数のあいだのつまみを明示的にしたものだ。
同じレベルのセルは、球面上で等しくはないが近い面積を持ち、緯度経度グリッドのような極での潰れは起きない。
H3: 移動と集約のための六角形
文書化済み: H3は地球を16の解像度の六角形で敷き詰める。土台の正二十面体の都合で、解像度ごとに12個の五角形が加わる。セル識別子は64ビット整数である。
六角形が選ばれる理由は幾何的なものが1つある。すべての隣接セルが辺を共有し、中心間の距離が等しい。正方形のセルは、辺で接する4つと角で接する4つの隣接セルを持ち、距離が異なる。これはセル間に広がるものすべてに偏りを与える。需要のヒートマップ、サージ区域、平滑化、隣接区域間の流れでは、隣接の種類が1つであることがその偏りを取り除く。
代償は階層にある。7つの子の六角形は親を近似するが、正確には敷き詰めない。そのため親と子の集計は端でわずかに異なる。セルが分析の単位で、前方範囲のストアがアクセス経路でない場合にH3を使う。正確な入れ子と範囲スキャンが要る場合はS2を使う。
R木: 広がりを索引する
セルは点に向く。川、配送区域、建物の輪郭には広がりがあり、セルへ割り当てるには、それが触れるすべてのセルに保存することになる。R木は広がりを直接索引する。
葉の各エントリはオブジェクトの最小外接矩形を持つ。内部ノードは子の外接矩形を持つ。検索は、矩形がクエリと交差するすべての子を下る。兄弟の矩形は重なりうるので、検索が複数の経路をたどることがある。木の品質は、挿入と分割のヒューリスティクスが残した重なりの量で決まる。ソート済みのデータを一括ロードすると、1行ずつ挿入するよりはるかによく詰まる。
文書化済み、PostGIS: 空間インデックスはPostgreSQLのGiSTフレームワーク上に実装されたR木である。索引を使うクエリは、まず外接ボックスを照合し、次に厳密な幾何述語を適用する。これは1つのエンジンの内部にあるフィルタと絞り込みのパターンである。
R木は、ポリゴンや混在した幾何を保持し、書き込み頻度が中程度のリレーショナルストアに合う。毎分数百万件の位置更新には合わない。更新のたびに共有の木を再平衡することになるからだ。
動くオブジェクトと書き込み中心の位置状態
数秒ごとに位置を報告する車両の群れは、住所の索引とは別の問題である。インデックスは絶えず書き換えられ、ほぼすべての書き込みが前の書き込みを置き換える。
参照設計:
- ライブのインデックスはメモリ上に置き、セルをキーとして、各オブジェクトの最後の位置とタイムスタンプを持つ。永続的な履歴は別の追記専用ストリームに置く。
- 更新は、オブジェクトを古いセルから除き、新しいセルへ加える形でその場で行う。妥当なレベルなら、ほとんどの更新はセルを変えない。よくある場合はハッシュマップへの1回の書き込みで済む。
- エントリはタイムスタンプで失効させる。報告をやめたオブジェクトはひとりでに消える。考え方は導出されたマルチセッション状態としてのプレゼンスと同じで、更新がないこと自体がシグナルである。
- シャードは、オブジェクトの識別子ではなく、粗い地理的単位(都市や低レベルのセル)で分ける。近接クエリが1つのシャードで済むようにするためだ。シャードの境界付近のクエリは隣のシャードも参照しなければならない。
常につきまとう危険は密度の偏りである。繁華街でセルあたり10オブジェクトになる固定のセルレベルは、地図の大半で0になり、イベントの夜のスタジアムでは1万になる。観測した密度から地域ごとにレベルを選ぶか、検索を適応的にする。対象のセルから始め、輪を1つずつ広げ、k 件が見つかるか最大半径に達したら止める。ホットパーティションの一般的な扱いはパーティショニング戦略を参照。
容量モデル
入力はすべて例示である。
ライブの車両状態。 100万台のアクティブな車両が4秒ごとに報告する。
writes/s = 1,000,000 / 4 = 250,000
live state = 1,000,000 x 64 bytes = 64 MBデータは小さく、書き込みレートは小さくない。このワークロードのサイジングを決めるのは、更新のスループットとシャードへのファンアウトであり、ストレージではない。
半径2 kmのクエリに対するセルレベル。 円は12.6平方キロメートルを覆う。
geohash length 5 4.9 km cells up to 4 cells candidate area up to 96 km^2 about 8x the circle
geohash length 6 1.2 x 0.61 km about 28 cells candidate area about 21 km^2 about 1.7x the circle
geohash length 7 153 m cells about 700 cells candidate area close to exact lookups dominate妥当な中間は長さ6である。参照は数十回で、候補は必要量の2倍未満に収まる。長さ5は、密な地域で必要なオブジェクトの8倍を読む。長さ7は、1つのクエリを数百回のキー参照に変える。正解は半径によって変わる。レベルを混ぜるカバラーを使うべき理由がこれである。
障害トレース
境界での取りこぼし
店舗検索が、利用者の位置を6文字のジオハッシュにし、同じ前方を持つ店舗を返す。セルの境界の向こう側、50メートル先に店舗がある利用者は、最寄りの店舗は3キロメートル先だと告げられる。前方一致の参照を、フィルタではなく答えとして扱ったのが原因である。必ず隣接セルを検索し、そのあと厳密な距離で順位を付ける。
経度と緯度の取り違え
あるサービスは (lat, lng) を出力し、別のサービスは、いくつかの幾何フォーマットが定めるとおり (lng, lat) を期待する。点は海の中や別の半球に落ち、インデックスはエラーなしで空の結果を返す。境界で値域を検証し(緯度は正負90まで)、フィールドに名前を付け、結合テストに既知のランドマークを含める。
スタジアムのセル
コンサートが終わり、4万人の利用者が1つのセルの中でアプリを開く。すべてのリクエストが同じセルのドライバー一覧をスキャンし、それを持つシャードが飽和する。隣のシャードは遊んでいる。セルあたりの候補数に上限を設け、密度の高い場所では細かいセルを使い、シャードが落ちる前にセル単位でリクエストを落とすかキューに入れる。アドミッションの仕組みはレート制限にある。
古い位置が一致する
車両がトンネルで接続を失う。最後の位置がインデックスに残り、10分間にわたって配車を提案される。最大の古さは、バックグラウンドの掃除処理だけでなくクエリ経路でも強制する。正しさが掃除のタイミングに依存しないようにするためだ。
日付変更線と極のクエリ
経度180度をまたぐバウンディングボックスは、最小経度が最大経度より大きい形で表される。素朴な範囲ロジックはその補集合を返す。そのようなボックスは2つに分ける。プロダクトがそこで運用されていなくても、極と日付変更線の領域は明示的にテストする。テストデータや不正な入力はそこに現れるからだ。
運用と検証
測る対象は次のとおり。採用した結果1件あたりの候補数(フィルタの精度)。クエリあたりに訪れたセルやノードの数。セルあたりのオブジェクト数の上位パーセンタイル。動くオブジェクトの更新遅延。そして一致した位置の古さの分布。
総当たりと突き合わせて検証する。無作為な点と領域を生成し、すべてをスキャンして正確な答えを計算し、比較する。セルの境界上の点、シャードの境界をまたぐ領域、日付変更線、高緯度の地域を含める。動くオブジェクトについては、記録したトレースを実時間の数倍の速さで再生し、古さの上限を超えたオブジェクトを返すクエリがないことを確かめる。
判断の枠組み
| 状況 | 選択 | 理由 |
|---|---|---|
| キーバリューストアやソート済みストアでの点の近接検索 | S2のセル識別子と領域カバラー | 包含が1回の範囲スキャンで済む。ヒルベルト順は少ない範囲で足りる |
| 依存を最小にした、中程度の精度の近接検索 | 隣接検索つきのジオハッシュ | どんな文字列インデックスでも動く。境界と緯度の歪みに注意する |
| 集約、ヒートマップ、サージ区域、隣接区域間の流れ | H3 | 隣接の種類が1つで、距離が一様 |
| リレーショナルデータベースのポリゴン、経路、混在した幾何 | データベースの空間インデックスを通じたR木 | セルごとにオブジェクトを複製せず、広がりを索引する |
| 毎分数百万件の位置更新 | 失効つきのメモリ上のセルマップを地域でシャード | 更新は1セルへの書き込み。再平衡する共有の木がない |
| 密度が何桁も変わる | 適応的なレベル、または輪の拡大 | 固定レベルはほとんどの場所で誤っている |
| 「最も近い」が移動時間を意味する | 候補に空間インデックス、順位付けに経路探索エンジン | 直線距離はネットワークを無視する |
そのうえで4つを確認する。インデックスがフィルタとしてのみ使われていること。隣接と境界の場合が覆われていること。古さが読み取り時に強制されていること。そして最大のクエリ領域に上限があることである。
参考文献
- Finkel and Bentley, Quad Trees: A Data Structure for Retrieval on Composite Keys (Acta Informatica, 1974): 四分木の原論文
- Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching (SIGMOD 1984)
- Samet, The Quadtree and Related Hierarchical Data Structures (ACM Computing Surveys, 1984)
- S2 Geometry, S2 Cell Hierarchy
- H3 documentation
- Uber Engineering, H3: Uber's Hexagonal Hierarchical Spatial Index
- Redis documentation, Geospatial
- PostGIS workshop, Spatial Indexing