HN 日本語サマリー

← 一覧へ戻る
Web開発

MMDBファイルを33%小さくする方法：データは一切変更せず

How we made our MMDB files a 33% smaller (ipinfo.io)

13 pointsby mmaia1 コメント

要約

IPinfoは、MMDBファイルフォーマットの最適化により、データの内容を変更することなくファイルサイズを平均31%、最大80%削減する手法を開発しました。この手法は、重複するツリー構造をハッシュコンシング（hash-consing）という技術で共有することで実現されており、ファイルサイズだけでなくメモリフットプリントも削減します。このツールはオープンソース化され、公開されています。

全文翻訳

データは一切変更せず、MMDBファイルを3分の1小さくする方法

8月にデータベース顧客にファイルが最大80%縮小したとお伝えし、その方法を説明すると約束しました。これがその説明です。これを行うツールは現在オープンソース化されています。

私たちが行ったこと

MMDBファイルフォーマットで大幅なサイズ削減を見つけました。以下に説明します。これをmmdbctlのアップデートとして、またスタンドアロンツールであるmmdbshrinkとしてリリースしました。このツールは既存のMMDBファイルを受け取り、より小さなファイルを書き出します。新しいファイルは標準的なMMDBです。古いファイルを開くすべてのリーダーライブラリが新しいファイルも開くことができ、各IPアドレスに対して同じ結果を返します。毎日ビルドされる89のデータベース全体で、カタログは91.2 GBから62.8 GBへと31%削減されました。単一の最良の結果はipinfo_privacyで、789 MBから155 MBへと80%削減されました。

圧縮はされていません。解凍ステップも、新しいリーダーも、新しいフォーマットもありません。削減は、静止時、転送時、メモリ内でも実質的です。なぜなら、MMDBファイルはメモリマップされており、ファイルサイズがメモリフットプリントだからです。

このツールはhttps://github.com/ipinfo/mmdbctl/releases/latestで入手可能です。

MMDBファイルのレイアウト

MMDBファイルには2つの部分があります。検索ツリーは、IPアドレスのビットに対するバイナリトライです。ルートから開始し、ビットを1つずつアドレスを読み取り、0なら左、1なら右に進み、リーフに到達したら停止します。リーフは、2番目の部分であるデータセクションへのポインタを保持します。そこにはレコード（国、都市、ASN、プライバシーフラグなど、データベースが持つもの）が存在します。

フォーマットの設計者はデータセクションに配慮しました。ポインタ型があるため、繰り返し現れるレコードは一度だけ書き込まれ、多くのリーフから参照できます。一般的なライターはこれを行います。

［画像］

そのため、下の例のipinfo_liteの実行では、データセクションのサイズは全く変化しません。

検索ツリーはあまり注目されていませんでした。各ノードは2つのレコードとして書き出され、子ごとに1つずつです。標準的なライターは、訪れたすべてのノードを出力します。既に同一のノードを書き出したかどうかは問いません。

なぜそれが重要か：インターネットは繰り返しが多い

アドレス空間の異なる部分にある2つの/24ネットワークを考えてみてください。これらは、それぞれの256アドレスすべてに対して同じ結果を持つとします。/24境界の下では、これらの2つのプレフィックスの下のサブツリーはビットごとに同一です。同じ形状、同じリーフ、同じデータセクションへのポインタです。標準的なライターは両方を保存します。

これをスケールアップします。プライバシーデータベースは、数百万の範囲に適用される少数の判定のセットです。位置データベースには、数百万のプレフィックスに分散された数十万の異なる都市レコードがあります。2つのプレフィックスが同じレコードに解決され、それらの下のすべてが同じである場合、それらのサブツリーは重複しています。私たちのファイルでは、ツリーの大部分が重複するサブツリーでした。

修正：ツリーのハッシュコンシング

ハッシュコンシングは、コンパイラや記号計算の分野で確立された技術であり、FilliâtreとConchon (2006) による『Type-Safe Modular Hash-Consing』で説明されており、Bryantのバイナリ決定図（1986年）のサブグラフ共有と密接に関連しています。アイデアはシンプルです。既に作成されたノードのハッシュテーブルを保持し、作成しようとしているノードの内容が構造的に同一である場合は、既存のノードを再利用します。これをトライにボトムアップで適用すると、子ノードを先に処理し、同じ子ノードのペアを持つノードを共有することになります。結果として有向非巡回グラフ（DAG）が得られます。複数の親が同じサブツリーを指すことができ、サブツリーは一度だけ格納されます。

MMDB検索ツリーに適用する手順は次のとおりです。

  1. 既存のツリーをリーフから上にトラバースし、親ノードの前に子ノードを処理します。
  2. 各ノードについて、子ノードへの参照をそれらの正規化されたIDに置き換えます。データレコードや空の結果への参照はその意味を保持します。
  3. 子参照の順序付けられたペアをハッシュテーブルのキーとして使用します。その正確なペアが既に存在する場合は、正規化されたノードを再利用します。そうでない場合は、新しい正規化されたノードを追加します。テーブルはペア全体を比較して等価性をチェックするため、ハッシュ衝突がマージを引き起こすことはありません。
  4. 正規化されたノードを書き出し、ルートをノードゼロとして保持し、ノード参照を再ナンバリングし、node_countとエンコードされたデータ参照を更新します。

これにはMMDBフォーマットの変更は必要ありません。各ノードには2つのレコードが含まれており、別のノード、データレコード、または空の結果を指定できます。複数の親が同じノードを参照できます。MMDBフォーマット仕様は、IPv4エイリアスに対してこの種の共有を既に説明しています。

同一のサブツリーを共有することで、各IPアドレスの分岐決定シーケンスが維持され、同じデータレコードまたは空の結果が得られます。ファイルのレイアウトとサイズは変更されますが、ルックアップ結果は同じままです。

［画像］

私たちはこの削減を発見し、リリースした最初の組織です。私たちが始めたとき、リファレンスライターは各位置に新しいノードを出力し、私たちが調べた他のライターも同様でした。概念的に類似した技術が昨年WhatsAppの脆弱性に関する論文に登場し、研究者たちは非常に大きな電話番号のセットを保存する必要があり、独自のカスタム構造を構築しました。私たちのものとは1つの点で異なります。出力は依然として有効なMMDBです。

数値

私たちのプロダクションカタログ全体で：

ルックアップ速度は変更されないか、わずかに向上しました。以下のipinfo_liteベンチマークでは、100万回のルックアップが元のファイルで操作あたり797 ns、最適化されたファイルで757 nsで実行され、常駐メモリは36.02 MiBから23.92 MiBに減少しました。ツリーバイトが少ないほど、ページフォールトが少なくなります。

実例

これは、READMEに記載されているとおり、無料のLiteデータベースに対して実行されたツールの実行結果です。

$ mmdbshrink --full-report ipinfo_lite.mmdb

input:   ipinfo_lite.mmdb
output:  ipinfo_lite.shrunk.mmdb

  size:   37.76 MB   ->  25.08 MB   (saved 12.68 MB, -33.58%)
  nodes:  3,790,310  ->  2,205,358  (-41.82%)
  tree:   30.32 MB   ->  17.64 MB
  data:   7.44 MB    ->  7.44 MB    (unchanged)

elapsed: 452ms

validation (seed 1):
  [OK] metadata        ip_version=6  record_size=32  binary_format=2.0
                       database_type: ipinfo bundle_location_lite.mmdb  build_epoch=1790582633
                       node_count: 3,790,310 -> 2,205,358 (-41.82%)
  [OK] fixed probes    n=39  hits=7  (0s)
  [OK] random IPv4     n=1,000,000  hits=861,887 (86.19%)  mismatches=0  (1.73s)
  [OK] random IPv6     n=1,000,000  hits=1,985 (0.20%)  mismatches=0  (39ms)

bench (1,000,000 lookups each):
  input:    size=37.76 MB    per_op= 797ns  qps=1,320,636
  output:   size=25.08 MB    per_op= 757ns  qps=1,319,347

memory (200,000 lookups each, separate processes):
  input:    mmap_cached=36.02 MiB   proc_rss=29.34 MiB   per_op= 707ns  minflt=155  majflt=0
  output:   mmap_cached=23.92 MiB   proc_rss=27.58 MiB   per_op= 695ns  minflt=168  majflt=0

最後の3行を一緒に読んでください。データセクションは変更されていません。節約されたバイトはすべて検索ツリーから来ており、ノードの41%が既に書き込まれたノードの重複であることが判明しました。

出力が同じデータベースであることを証明する

小さなファイルは、単一のルックアップが変更された場合は価値がありません。最適化されたファイルが顧客に届く前に、4つの方法でチェックしました。

  1. 双方向での完全な列挙。 元のファイル内のすべてのプレフィックスを最適化されたファイルでルックアップし、その逆も行います。ipinfo_liteの場合、これは3,783,922プレフィックス、7,567,844ルックアップで、すべて一致しました。
  2. ランダムプローブ。 100万個のランダムなIPv4アドレスと100万個のランダムなIPv6アドレスで、不一致はゼロでした。
  3. 既存のツール。 mmdbctl verifyはファイルを有効と報告し、mmdbctl diffはサブネット0件、レコード変更0件を報告し、MaxMind自身のmmdbverifyもパスします。12のMMDBリーダーSDKでファイルをテストしました。
  4. ベンチマークの同等性レイテンシとメモリについて、上記のとおりです。

最初期の最適化されたファイルは7月に本番環境に投入されました。まず顧客のカスタムデータセットで、これは2 GBのプラットフォーム制限を超えて成長しており、次に自社のAPIで、より小さなファイルが各インスタンスが必要とするメモリを削減しました。今日、これらはデフォルトとなっています。APIトラフィックの100%、およびIPinfoデータベースダウンロードの100%が、以前と同じファイル名で最適化されたファイルを提供しています。

なぜ無料で提供するのか

MMDBは、IPメタデータの高速ルックアップを提供するオープンフォーマットであり、エコシステムはそれを広くサポートしています。以前にもオープンソースツールを公開しており、このコミットメントを継続します。私たちが発見した重複はフォーマットのライターの特性であり、MMDBファイルを配布している誰もが同じツリーブロートを抱えています。私たちが競争するのは、ファイルに何が含まれるかです。ファイルがどのようにパックされるかは、私たちの優位性が存在する場所ではないため、オプティマイザーはApache 2.0ライセンスの下でオープンソース化されています。

MMDBファイルをビルドする場合は、ご自身のファイルで実行してください。MMDBファイルを読み取る場合は、何もする必要はありません。

プロジェクトは次のGitHubリポジトリで見つけることができます：https://github.com/ipinfo/mmdbctl/tree/master/mmdbshrink

go install github.com/ipinfo/mmdbctl/mmdbzip@latestで直接簡単にインストールできます。その他のオプションについては、README.mdのインストールセクションを参照してください。

インストール後、次のように使用できます：mmdbshrink ipinfo_lite.mmdb

IPinfoのデータベース顧客の場合、何もする必要はありません。ダウンロードするMMDBには、既にこれらの削減が適用されています。