在移動網際網路的應用中，經常需要根據使用者的位置資訊等做一些使用者側資訊的統計分析。而要拿到使用者的位置資訊，一般有兩個方法： 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|內網IP0.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|內網IPip2region 庫中最新的 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 對應的索引塊，根據索引塊後面四個位元組得到資料地址和資料長度，從而拿到位置資訊。b+tree搜尋b+tree 搜尋用到了 header 索引區，第一步先在 header 索引區中使用二分搜尋，定位到某個索引分割槽後，再在對應的索引分割槽中使用二分搜尋。相比較二分搜尋而言，它的速度更快，原因是讀磁碟的次數遠低於二分搜尋。其步驟如下：
把 IP 值透過 ip2long 轉為整型使用二分法在 header 索引區中搜索，比較得到對應的 header 索引塊以及其對應的索引分割槽。讀取對應索引分割槽，再透過二分法定位到對應的索引塊，從而獲得位置資訊。基於記憶體的二分搜尋該方法和二分搜尋方法類似，區別就是前者將 ip2region.db 全部讀進記憶體中，後者則是透過不斷讀取 ip2region.db 檔案。
總結ip2region 庫只解決了一個非常常見的 IP 定位問題，但將這個服務做到了又小又快（當然還提供了多語言的客戶端），從而在 Github 上獲得了 8.4k 的 star。
佔用記憶體小相鄰 IP 的位置資訊相同，透過 IP 段來解決相鄰 IP 對應相同位置資訊，避免位置資訊被重複儲存IP 轉換成 INT，像字串 111.111.111.111 被轉換成int（1869573999），從 15Byte 縮小到 4Byte不同的 IP 段也有相同的位置資訊，透過指標來指向特定的位置資訊，保證位置資訊只儲存一次（全量掃描儲存進字典中）搜尋速度快IP 有序，使用二分搜尋將時間複雜度降到 O(logN)二級索引 header 索引區的使用，降低磁碟讀寫頻率，先確定索引分割槽，再從索引分割槽確定索引位置，在確定位置資訊資料。多語言客戶端支援支援 java、C#、php、c、python、nodejs、php擴充套件(php5和php7)、golang、rust、lua、lua_c, nginx。