我們將 MMDB 檔案縮減 33%

在八月，我們告訴資料庫客戶他們的檔案已縮小多達 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 檔案分為兩部分。搜尋樹是以 IP 位址的位元為基礎的二元 trie。從根節點開始，逐位讀取位址，遇到 0 時往左，遇到 1 時往右，直到到達葉節點。葉節點包含一個指向第二部分 資料區 的指標，資料區存放記錄：國家、城市、ASN、隱私旗標，資料庫所載的任何資訊。

格式設計者對資料區進行了精心設計。它擁有指標型別，因而重複的記錄可只寫一次，並由多個葉節點引用，常見的寫入工具也採用此做法。

這也是為什麼在下方示範的 ipinfo_lite 執行中，資料區的大小完全不變。

搜尋樹則較少受到關注。每個節點會被寫成兩筆記錄，分別對應兩個子節點，標準寫入器會輸出它訪問到的每個節點。它不會詢問自己是否已經寫過相同的節點。

為什麼這很重要：網際網路是重複的

想像在位址空間不同區域有兩個 /24 網路，且它們的 256 個位址都回傳相同答案。在 /24 邊界以下，這兩個字首下的子樹逐位相同：相同結構、相同葉節點、相同指向資料區的指標。標準寫入器會將兩者都儲存。

現在將規模放大。隱私資料庫只包含少量判斷，適用於數百萬個範圍。位置資料庫則有數十萬個不同城市記錄，分佈於數百萬個字首。只要兩個字首解析到相同記錄，且其下方所有內容也相同，它們的子樹就是重複的。在我們的檔案中，樹的大部分都是重複子樹。

解決方案：使用 Hash-Consing 來處理樹

Hash-consing is a long-established technique from compiler and symbolic-computation work, described by Filliâtre and Conchon (2006), Type-Safe Modular Hash-Consing, and closely related to the subgraph sharing in Bryant’s binary decision diagrams (1986). The idea is simple: keep a hash table of nodes already created, and reuse an existing node whenever its contents are structurally identical to the one you are about to create. Applied bottom-up to a trie, this means processing the children first, then sharing nodes with the same pair of children. The result is a directed acyclic graph: multiple parents can point to the same subtree, which is stored only once.

應用於 MMDB 搜尋樹，程式如下：

從葉節點向上遍歷現有樹，先處理子節點再處理父節點。
對於每個節點，將對子節點的引用替換為其標準身份。對資料記錄和空結果的引用保持其含義。
使用子節點引用的有序對作為雜湊表的鍵。若該精確對已存在，則重複使用標準節點；否則新增一個新的標準節點。表格會完整檢查整對是否相等，因而雜湊衝突永不導致合併。
輸出標準節點，保持根節點為節點零，重新編號節點引用，並更新 node_count 及編碼資料引用。

This requires no change to the MMDB format. Each node contains two records, which can identify another node, a data record, or an empty result. Multiple parents can refer to the same node; the MMDB format specification already describes this kind of sharing for IPv4 aliases.

共享相同子樹可保留每個 IP 位址的分支決策順序，並得到相同的資料記錄或空結果。檔案佈局與大小會變更；查詢結果保持不變。

我們是第一個發現並發布此節省方案的人。起初，參考寫入器在每個位置輸出一個新節點，其他我們檢視的寫入器也是如此。去年在一篇 WhatsApp 漏洞論文中出現了概念相似的技術，研究人員需要儲存大量電話號碼，並自行構建自訂結構。與此不同的是，我們的輸出仍然是有效的 MMDB。

數字

在我們的生產目錄中：

查詢速度保持不變或略有提升。在下列 ipinfo_lite 基準中，一百萬次查詢在原始檔案上每次 797 ns，在最佳化檔案上 757 ns，常駐記憶體從 36.02 MiB 降至 23.92 MiB。樹節點位元組數減少意味著頁面錯誤更少。

實作範例

這是對我們免費 Lite 資料庫執行的工具，與 README 中的說明完全相同。

$ 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

一起閱讀最後三行。資料區段未被改動。每節省的位元組均來自搜尋樹，41% 的節點被發現是已寫入節點的重複。

證明輸出為相同資料庫

若單一查詢結果改變，縮小檔案毫無價值。在任何最佳化檔案送達客戶前，我們以四種方式檢查它。

雙向完整列舉。原始檔案中的每個字首都在最佳化檔案中查詢，反之亦然。對於 ipinfo_lite，這是 3,783,922 個字首，7,567,844 次查詢，全部匹配。
隨機探測。一百萬個隨機 IPv4 和一百萬個隨機 IPv6 位址，零不匹配。
現有工具。 mmdbctl verify 報告檔案有效，mmdbctl diff 報告 0 個子網路與 0 個記錄被修改，MaxMind 自己的 mmdbverify 也通過。我們將檔案對照 12 個 MMDB 讀取 SDK 進行測試。
基準相容性 在延遲與記憶體上，與上文相同。

第一批最佳化檔案於七月投入正式環境，最先應用於一位客戶自訂資料集，該資料集已超過 2GB 平臺限制，接著再進入我們自己的 API，較小的檔案降低了每個例項所需的記憶體。如今它們已成為預設：100% 的 API 流量與 100% 的 IPinfo 資料庫下載均以相同檔名提供已最佳化的檔案。

我們為何免費提供

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 檔案已經套用了這些節省。