在移動互聯網的應用中，經常需要根據用戶的位置信息等做一些用戶側信息的統計分析。而要拿到用戶的位置信息，一般有兩個方法： GPS 定位的信息和用戶 IP 地址。由於每個手機都不一定會打開 GPS，而且有時並不太需要太精確的位置（到城市這個級別即可），所以根據 IP 地址入手來分析用戶位置是個不錯的選擇。要做到這個功能得需要一個 IP 和地理位置的映射關係庫，並依賴這個庫啟動一個 IP 轉地理位置的服務。本文從需求入手，結合 Github 上擁有 8.4k 星的 ip2region 來分析映射關係庫的設計以及 IP 如何快速轉換成地理位置。

介紹

IP 定位服務很常見，而且很多公司都提供了類似的付費服務，比如阿里，高德，百度等，當然也有公開的免費服務，像 GeoIP，純真IP等。這些服務要麼通過 HTML 頁面解析，要麼通過介面請求，但不管怎樣都離不開一次 http 請求，更不用說大部分服務都對 QPS 作了限制。下表枚舉了一些常見的通過 IP 獲取地址的方式。

在日常工作通常需要將大量用戶請求日誌中 IP 轉換成用戶位置信息，用作後續的分析。這其中的關鍵是數據量大，處理要快。顯然每次都通過請求 API 公共服務的方式無法滿足我們的日常需求。

暴力生成 IP 庫

對於日常的需求，一種簡單粗暴的做法就是提前通過 API 獲取所有公網 IP 對應的位置信息，按照下面的 TIPS 中我們可以估算出如果通過訪問淘寶IP地址庫來遍歷 3.3 億的國內 IP 地址要 10 年。如果是高德的企業用戶遍歷國內 IP 地址大概要 11 天。感覺這個 11 天還是能夠接受的。

TIPS: IPv4
目前所說的 IP 地址是指 IPv4，它是使用 32 位（4 位元組）地址，因此地址空間約有 42.9 億$2^32=4294967296$個, 不過一些地址是作為特殊用途所保留的，如專用網路（約 1800 萬個）和多播地址（約 2.7 億個），這些減少了可在互聯網上路由的地址數量。據 wiki 上統計，中國的 IPv4 數量達到 3.3 億，而美國有 15.4 億個。

這裡我們約定一下位置信息的數據格式：國家|區域|省份|城市|ISP，如果介面中返回的欄位沒有對應的信息，則對應的欄位填充0。那麼我們通過順序請求 API 服務可以獲取到如下文件數據（地址依次遞增）：

0.0.0.0|0|0|0|內網IP|內網IP
0.0.0.1|0|0|0|內網IP|內網IP
...
1.0.15.255|中國|0|廣東省|廣州市|電信
...
255.255.255.255|0|0|0|內網IP|內網IP

只要有了這個文件，可以將其讀到內存中，使用字典保存，鍵為 IP 地址，值為位置信息。程序可以在 O(1) 時間複雜度內返回位置信息，不過該程序或文件佔用的大小我們可以粗略的計算一下。假定我們使用 utf-8 進行存儲，一條記錄最短的情況是 0.0.0.0|0|0|0|0|0，佔用17個位元組，IP 庫文件的大小為 17*4294967296 = 73014444032 B = 71303MB = 71GB。這個大小是任意一個程序不能接受的。

空間優化

IP 庫文件優化

從上面的文件數據發現大量的相鄰 IP 擁有相同的位置信息（客戶在申請一段 IP 地址都會盡量連在一起），所以我們可以將這樣的記錄合成一條記錄。如下文件數據（地址段依次遞增）：

0.0.0.0|0.255.255.255|0|0|0|內網IP|內網IP
...
1.0.8.0|1.0.15.255|中國|0|廣東省|廣州市|電信
...
224.0.0.0|255.255.255.255|0|0|0|內網IP|內網IP

ip2region 庫中最新的 ip.merge.txt 共有 658207 記錄，文件大小 39 M。

IP地址優化

從上面的文件數據發現大量的IP地址以字元串形式存儲，而 IPv4 是使用 32 位地址。所以將其轉換成整型進行存儲可以大大節省空間，比如像最短的字元串 0.0.0.0 佔據 7 位元組，最長的字元串 111.111.111.111 佔據 15 位元組，如果將其轉換成整型，他們都佔據 4 位元組。0.0.0.0 是 int(0), 111.111.111.111 是 int(1869573999)。

位置信息優化

從上面的文件數據發現相同的位置信息會對應不同的 IP 段（客戶可能在不同的時間段去申請 IP 段），所以還是有大量的位置信息在 IP 庫文件中，在內存中我們可以只保留一份位置信息，並使用指針或者文件偏移量+數據長度來獲取對應的位置信息。

優化後的IP庫

根據上面的優化，我們可以生成最終的IP庫：ip2region.db，該文件只有8.1M。

IP庫的結構

IP 庫文件ip2region.db的結構分為四個部分：super 塊， header索引區，數據區，索引區。具體如下圖所示：

super 塊
用來保存索引塊的起始地址和結束地址，第一個索引指針指向索引塊的開始位置，也就是第一個索引分區的第一個索引塊，最後一個索引指針指向索引塊的結束位置-12，也就是最後一個索引分區的最後一個索引塊的頭地址。這樣查詢的時候直接讀取super塊 8 個位元組，就能快速獲取索引塊的地址範圍。
header 索引區
header索引是對索引塊的二級索引，專門為b+tree搜索服務的。索引區總長度除以索引分區長度12*(1024*8/12-1)就是 header 索引的實際索引數。該區域大小為 2048*8 bytes, 由 2048 個 8 bytes 的 header 索引塊組成。header索引塊前四個位元組存儲每個索引分區第一個索引塊的起始ip值，後四個位元組指向該索引塊的地址。
header索引區之所以定義為接近16k，是因為可以通過四次磁碟讀取讀取整個header索引區，然後在內存中進行查詢，查詢的結果可以確定該ip在索引區的某個索引分區內，然後再根據地址兩次讀取8k 索引分區到內存，再在內存中查詢，從而減少磁碟讀取的次數。
數據區
保存的數據，數據格式如下：中國|華南|廣東省|深圳市|鵬博士，分別表示國家，區域，省份，城市，運營商
索引區
索引區是由索引塊構成，每個索引塊占 12 位元組，包括起始IP, 結束IP, 數據信息。數據信息中前三個位元組保存數據地址，後一個位元組保存數據長度。每一條索引塊對應 ip.merge.txt 中的一條記錄，表示一個 IP 段的索引。在檢索中當指定 IP 在某個索引塊的起始IP和結束IP中間，即表示命中索引。再通過索引塊中的數據地址和數據長度，就能從 ip2region.db 讀取對應的位置信息數據。

IP庫的生成

ip2region 的 Github 倉庫中提供了 ip2region.db 的生成過程，是用 JAVA 寫的，其類圖如下所示：

通過熟悉生成 ip2region.db 的源碼，簡述一下其生成過程如下：

通過 RandomAccessFile 在文件中預留 8 bytes 的 super 塊和 2048*8 bytes 的 header 索引區
掃描 ip.merge.txt 文件，對每一條記錄作如下處理：
依據每一條記錄的起始IP, 結束IP 和數據，生成一個索引塊，前四個位元組存儲起始IP, 中間四個位元組存儲結束IP, 後四個位元組存儲已經計算出的數據地址（通過 RandomAccessFile 寫入，這裡維護一個位置信息到文件位置的字典，保證同一個位置信息只寫入一次。），並將索引塊暫存在 indexPool 鏈表中。這一步會將數據區的所有位置信息確定。
掃描完 ip.merge.txt 中所有的記錄，將 indexPool 中所有的索引塊寫到數據區後面。在此過程中將 int(1024*8/12-1)= 681 個索引塊組成一個索引分區，並記錄下每個索引分區第一個索引塊的起始IP和地址信息（header塊），並暫存在 headerPool 鏈表中。此外還會將索引區的起始位置和結束位置記錄下來。
調整 RandomAccessFile 指向文件開頭，寫入索引區的起始位置存儲到 super 塊的前四個位元組，結束位置存儲到 super 塊的後四個位元組。
繼續將 headerPool 中的 header 塊寫入到 header 區。
調整 RandomAccessFile 指向文件結尾，寫入時間戳和版權信息。

TIPS: ip2region 倉庫中還使用了 global_region.csv 數據，該文件有5列（行號，，區域，，郵政編碼），對應著區域的具體信息，可以往數據區每個位置信息中填充。

快速搜索

ip2region 提供三種查詢演算法，最差的查詢耗時都是ms級別的。分別是內存二分搜索，b+tree搜索，二分查找。耗時依次增加。其搜索結構圖如下：

二分搜索

通過 super 塊可以拿到索引區的起始位置和結束位置，而且每個索引塊都是 12 bytes，其中的 IP 地址都是遞增的，所以可以使用二分搜索來快速獲取位置信息。其步驟如下：

把 IP 值通過 ip2long 方法轉為整型
讀取 super 塊獲取索引區的起始位置和結束位置，二者相減 +1 可得索引塊的總個數
採用二分法直接求解，比較索引塊中起始IP，結尾IP 和當前 IP 的大小，即可找到該 IP 對應的索引塊，根據索引塊後面四個位元組得到數據地址和數據長度，從而拿到位置信息。