Cloud Optimized なマップタイルアーカイブ PMTiles のファイル構造を眺めてみる

# はじめに

大量のマップタイルを1つのファイルにまとめるアーカイブ形式として Cloud Optimized の文脈で PMTiles が注目されています。タイルのアーカイブ形式は、例えばベクタタイルにおいては MBTiles（SQLiteベース）などが昔から存在しますが、今回触れる PMTiles v3 のように、昨今 **Cloud Optimized** と銘打たれている形式は、特別なサーバを立てることなしに容易に配信できる構造になっているのが特徴です。Webブラウザが直接 HTTP Range Requests で必要な箇所だけ読み取れるような（あるいはCDNエッジコンピューティング等で容易に元のタイルに分解して配信できるような）平易な構造になっています。

PMTiles はベクタタイル・ラスタタイルを問わずに扱うことができます。PMTiles の**全体像や利用方法**については以下の記事が詳しいです。

https://qiita.com/Kanahiro/items/577f7828c5a1e323721a

この記事では、PMTiles v3 ファイルの内部構造を覗くことで、どのような工夫が取り入れられているのかを見ていきます。

## 参考にしたもの

仕様書は以下にあります（が、内容はあっさりしています）。

- [PMTiles version 3](https://github.com/protomaps/PMTiles/blob/main/spec/v3/spec.md)

PMTilesの開発元である protomaps による実装は以下にあります。

- https://github.com/protomaps/go-pmtiles/
- https://github.com/protomaps/pmtiles/

開発元の protomaps による以下のブログ記事も参考にしました。

- [PMTiles version 3: Hilbert Tile IDs and Run-Length Encoding](https://protomaps.com/blog/pmtiles-v3-hilbert-tile-ids)
- [PMTiles version 3: Disk Layout and Compressed Directories](https://protomaps.com/blog/pmtiles-v3-layout-compression)

# 主要な工夫

まず結論から述べると、PMTiles v3 には主な工夫として以下のような手法が取り入れられています。

- 各タイルを (z, x, y) ではなく、ヒルベルト曲線にもとづく単一の整数 (`TileId`) で識別する。
    - これは、圧縮効率の向上や、クライアント側 (JS) での扱いの効率など、様々な面でメリットがあります。
    ![hirbert.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/95370/45978238-2e36-925e-21fe-1be2440a721d.png)
- 同じ内容のタイル（海など）が連続する場合に、1つ1つ記録せずに、N個連続しているという事実を記録する（いわゆるランレングス圧縮）。
- ディレクトリ（＝目的のタイルを見つけるための索引）のサイズを減らすための工夫：
    - 整数として可変長整数を用いる。
    - 行指向ではなく列指向で記録する（圧縮されやすくするため）。
        - `TileId` の列は単調増加となるため、差分をとって（デルタエンコードして）記録する。
    - タイルデータの格納場所を表す `Offset` 値についてもサイズ削減の工夫する。
- ヘッダおよびルートディレクトリは必ずファイル先頭16KiBに収められている（最も重要な部分のプリフェッチが容易）。
- タイルデータがヒルベルト曲線の順で記録されている場合は、そのことをヘッダ情報の `clustered=True` で提示する（クライアント側が頑張ればタイルの一括取得を効率化できるため）。

ここから先は、詳しいファイル構造を見ていきましょう。

# チャンク構造

ファイルは先頭から順に以下の5つのチャンクで構成されています。

| 項目 | オフセット (bytes) | サイズ (bytes) | 内容 |
| --- | --- | --- | --- |
| ヘッダ部 | 0 | 127 | このファイルに関する各種情報 |
| ルートディレクトリ部 | header.RootOffset | header.RootLength **（ヘッダと合わせて16KiB未満）** | タイルまたはリーフディレクトリを参照するエントリの列 |
| メタデータ部 | header.MetadataOffset | header.MetadataLength | JSON形式の任意のメタデータ |
| リーフディレクトリ群 | header.LeafDirectoryOffset | header.LeafDirectoryLength | ヘッダとルートディレクトリの合計サイズが16KiB以上になりそうな場合はリーフディレクトリが作られる |
| タイルデータ部 | header.TileDataOffset | header.TileDataLength | タイルデータ領域 |

# ヘッダの内容

ファイルの先頭127バイトがヘッダ領域となっており、以下の内容が順に記録されています。各値のバイトオーダはリトルエンディアンです。

|オフセット| 名称 | 型 | 備考 |
| --- | --- | --- | --- |
| 0 | magic number | 7 bytes | マジックナンバー `PMTiles` (固定値) |
| 7 | spec version | uint8 | 仕様バージョン `3` (固定値) |
| 8 | RootOffset | uint64 | ルートディレクトリ部のオフセット |
| 16 | RootLength | uint64 | ルートディレクトリ部の長さ |
| 24 | MetadataOffset | uint64 | メタデータ部のオフセット |
| 32 | MetadataLength | uint64 | メタデータ部の長さ |
| 40 | LeafDirectoryOffset | uint64 | リーフディレクトリ群のオフセット |
| 48 | LeafDirectoryLength | uint64 | リーフディレクトリ群の長さ |
| 56 | TileDataOffset | uint64 | タイルデータ部のオフセット |
| 64 | TileDataLength | uint64 | タイルデータ部の長さ |
| 72 | AddressedTilesCount | uint64 | 総タイル数 |
| 80 | TileEntriesCount | uint64 | ディレクトリ上のタイルエントリ数（ランレングスされた分だけ総タイル数より減る） |
| 88 | TileContentsCount | uint64 | タイルの実データ数（同一内容のタイルデータが使いまわされた分だけエントリ数より減る） |
| 96 | Clustered | bool | True の場合はタイルデータがヒルベルトTileIdの順に格納されている |
| 97 | InternalCompression | uint8 | メタデータ部の圧縮方式 (0: 不明, 1: なし, 2: gzip, 3: Brotli, 4: Zstd) |
| 98 | TileCompression | uint8 | タイルの圧縮方式 (0: 不明, 1: なし, 2: gzip, 3: Brotli, 4: Zstd) |
| 99 | TileType | uint8 | タイルの種類 (0: 不明, 1: MVT, 2: PNG, 3: JPEG, 4: WebP) |
| 100 | MinZoom | uint8 | 最小ズーム値 |
| 101 | MaxZoom | uint8 | 最大ズーム値 |
| 102 | MinLonE7 | int32 | 最小経度 x 1e7 |
| 106 | MinLatE7 | int32 | 最小緯度 x 1e7 |
| 110 | MaxLonE7 | int32 | 最大経度 x 1e7 |
| 114 | MaxLatE7 | int32 | 最大緯度 x 1e7 |
| 118 | CenterZoom | uint8 |  |
| 119 | CenterLonE7 | int32 |  |
| 123 | CenterLatE7 | int32 |  |

# ルートディレクトリ部

ルートディレクトリ部には `TileId` に対応するタイルデータの格納場所を得るための索引エントリが格納されています。

ディレクトリのデータは**全体が gzip で圧縮されています**（ブラウザ側のサポートが進めば Brotli や Zstdにも対応できるとのこと）。ルートディレクトリ部を gzip 展開すると、データは以下のように格納されています。なお Varint は可変長整数を意味します。

|  | 個数 | 型 | 備考 |
| --- | --- | --- | --- |
| NumEntries | 1 | Varint | エントリの個数 |
| TileId | NumEntries 個 | Varint | タイルID。1つ前のエントリの値との差分が記録されている。 |
| RunLength | NumEntries 個 | Varint | ランレングス |
| Length | NumEntries 個 | Varint | タイルデータの長さ |
| Offset | NumEntries 個 | Varint | タイルデータのオフセット値。前エントリのタイルデータと連続している場合は 0 。それ以外の場合は 実際のoffset+1。 |

- タイルデータまたはリーフディレクトリの場所を示すエントリが `NumEntries` 個記録されています。
- エントリのデータは行指向ではなく**列指向**で記録されています（圧縮効率を高めるため）。
- ディレクトリのデータはすべて可変長整数（後述）で表現されています（ファイルサイズを減らすため）。
- エントリは `TileId` の順に記録されます（0 → 4 → 6 → 7 → 8 → ...のように）。
- `TileId` には、前のエントリの TileId との差分が記録されています（圧縮効率を高めるため）。
- `Offset` には、タイルデータの格納場所が前エントリのタイルデータと連続している場合は特別に `0` が記録され、それ以外の場合は `実際のオフセット+1` が記録されます。

それぞれの項目についてもう少し説明します。

- `TileId`
    - タイルを識別する (z, x, y) をヒルベルト曲線上の番号として表現したものです。
        ![hirbert.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/95370/45978238-2e36-925e-21fe-1be2440a721d.png)
    - 例えば `(z=8, x=68, y=100)` の TileId は `33759` となります。
    - (z, x, y) ⇔ TileId の相互変換の方法は protomaps による実装などを参照してください。
- `RunLength`
    - 同一内容のタイル（海など）が連続することはよくあります。そこで例えば同じ内容のタイルが213個連続する場合は、エントリを213個記録するのではなく RunLength=213 のエントリを1つだけ記録します。
- `Offset` と`Length`
    - タイルデータの格納場所が前エントリのタイルデータと連続している場合は `Offset` の値として特別に 0 を記録して省略します。実際のオフセットは前エントリのオフセットと長さから求められるためです。
    - それ以外の場合は、 `実際のオフセット+1` が記録されています。つまりタイルデータの開始位置は `header.TileDataOffset + Offset - 1` であり、サイズは `Length` です
- **重要な例外として** `RunLength == 0` の場合は、このエントリが**タイルではなくリーフディレクトリを参照している**ことを意味します。
    - 参照先のリーフディレクトリの開始位置は `header.LeafDirectoryOffset + Offset` であり、サイズは `Length` です。

なお、ルートディレクトリ部のサイズは、ヘッダ部と合わせて 16KiB (16,384 bytes) 未満でなければならないことが仕様で定められています。

### Varint（可変長整数）について

ディレクトリ周りのデータには、可変長の符号なし整数が使われています。より具体的にいうと、続きのバイトがあるかどうかを最上位ビットで示す方式が使われています。例を挙げると：


- 127 → `0x7f` (1 byte)
- 128 → `0x80, 0x01` (2 bytes)
- 129 → `0x81, 0x01` (2 bytes)
- 16383 → `0xff, 0x7f` (2 bytes)
- 16384 → `0x80, 0x80, 0x01` (3 bytes)

# メタデータ部

- 権利者情報や生成プログラム由来の情報など、自由な内容のJSONを格納できる領域です。
- このJSONは `header.InternalCompression` で示される方式で圧縮されています。（リファレンス実装では常にgzip圧縮されているようです。）

# リーフディレクトリ群

**ヘッダとルートディレクトリの合計サイズが 16KiB 未満になるようにするため**、エントリが多い場合はルートディレクトリの下層構造としてリーフディレクトリが作られます。各リーフディレクトリのデータ構造はルートディレクトリ部と同様です。

ディレクトリは、ルートディレクトリを含めて最大4階層にすることが許されています。リーフディレクトリをどのように構成するかについては特に定めがなく、変換プログラムの実装者に最適化が委ねられているようです。

# タイルデータ部

- 全タイルのデータが単純に結合されて格納されています。
- 各タイルは `header.TileCompression` で示される方式で圧縮されています（あるいは無圧縮）。protomaps による実装ではMVT (pbf) の場合のみにgzip圧縮しているようです。
- `header.Clustered` が True の場合は、タイルデータが TileID の順（つまりヒルベルト曲線の順）でファイルに格納されていることを示します（クライアント側が頑張ればタイルの一括取得を効率化することができます）。

# 補足: Webブラウザで圧縮パートを読む

PMTilesファイルはあちこちの部分がgzipで圧縮されています。したがってブラウザが PMTilesファイルを直接読む場合は、ブラウザ側にgzipを展開する仕組みが必要です。（注： HTTP通信におけるgzip圧縮の話ではなく、PMTilesファイル自体がgzipのつぎはぎになっていることに注意してください）。


2023年1月現在、一部のブラウザでは各種圧縮データを展開するための [DecompressionStream](https://developer.mozilla.org/ja/docs/Web/API/DecompressionStream) というAPIが利用できるようになっていますが、SafariやFirefoxではまだサポートされていません。
![Screenshot 2023-01-30 at 12.43.37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/95370/21f30470-c3b3-8e8e-8bb8-7e927c828a4d.png)
そこで protomaps による [JavaScript用実装](https://github.com/protomaps/PMTiles/tree/main/js) では、ブラウザにおるネイティブ実装ではなく、[fflate](https://www.npmjs.com/package/fflate) というライブラリを使って展開を行っているようです。