IPアドレスデータのプロバイダーであるIPinfoは、位置情報やASN情報などのIPメタデータの高速なルックアップに広く使用されているMMDBファイルを縮小する手法を開発しました。MMDBフォーマットは、IPアドレスのビットに対するバイナリトライである「検索ツリー」と、実際のレコードが格納されている「データセクション」という2つの主要なコンポーネントで構成されています。データセクションはすでにレコードの共有をサポートしていますが、検索ツリーは通常それをサポートしていません。標準的なライターはツリーの各位置に対して新しいノードを出力するため、複数のIPプレフィックスが同じデータレコードに解決する場合、大幅な肥大化を招ります。
この画像は、第1段落で言及されているMMDBフォーマットの主要なコンポーネントを説明しています。
この課題に対処するため、IPinfoはhash-consingとして知られる技術を実装しました。この手法では、既存のツリーを葉から上に向かって走査し、ハッシュテーブルを使用して構造的に同一なノードを特定します。子ノードのペアがすでに処理されている場合、ツールは重複を作成するのではなく、既存の標準的なノードを再利用します。これにより、検索ツリーは複数の親が単一の共有サブツリーを指すことができる有向非巡回グラフ（DAG）へと変換されます。MMDBフォーマットはすでにこの種の共有をサポートしているため、この最適化にはファイルフォーマットやリーダーライブラリの変更は必要ありません。生成されたファイルは既存のツールと完全に互換性を維持します。
この視覚資料は、第2段落で説明されているhash-consingのメカニズムと、その結果生じるDAG構造を解説しています。
本番環境でのテストでは、この最適化によりIPinfoの89データベースカタログの総サイズが31%削減され、特定のデータベースでは最大80%の削減が見られました。MMDBファイルはメモリマップされるため、これらの節約は直接的にメモリフットプリントの縮小と、ルックアップ時のページフォルトの減少につながります。主な節約は検索ツリーから得られるものであり、データセクションは変更されません。IPinfoはこの最適化を`mmdbshrink`としてオープンソース化しており、他の開発者もルックアップ結果とパフォーマンスを同一に保ったまま、独自のMMDBファイルのサイズを削減できるようになります。
残された技術的な検討事項の一つは、MMDBヘッダー内の`record_size`フィールドです。hash-consingによって検索ツリーのノード数が大幅に減少するため、レコードサイズに割り当てられるビット数を減らす機会があり、さらに12〜25%のスペース節約が得られる可能性があります。しかし、そのような変更にはファイルの内部メタデータ構造の修正が必要となります。一方で、現在の`mmdbshrink`ツールは、基礎となるデータフォーマットを1バイトも変更することなくその成果を達成しています。