怎么深入分析ip2region實現(xiàn)

怎么深入分析ip2region實現(xiàn)，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

在移動互聯(lián)網(wǎng)的應(yīng)用中，經(jīng)常需要根據(jù)用戶的位置信息等做一些用戶側(cè)信息的統(tǒng)計分析。而要拿到用戶的位置信息，一般有兩個方法： GPS 定位的信息和用戶 IP 地址。由于每個手機都不一定會打開 GPS，而且有時并不太需要太精確的位置（到城市這個級別即可），所以根據(jù) IP 地址入手來分析用戶位置是個不錯的選擇。 要做到這個功能得需要一個 IP 和地理位置的映射關(guān)系庫，并依賴這個庫啟動一個 IP 轉(zhuǎn)地理位置的服務(wù)。下面結(jié)合的 ip2region 來分析映射關(guān)系庫的設(shè)計以及 IP 如何快速轉(zhuǎn)換成地理位置。

介紹

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

在日常工作通常需要將大量用戶請求日志中 IP 轉(zhuǎn)換成用戶位置信息，用作后續(xù)的分析。這其中的關(guān)鍵是數(shù)據(jù)量大，處理要快。顯然每次都通過請求 API 公共服務(wù)的方式無法滿足我們的日常需求。

暴力生成 IP 庫

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

TIPS: IPv4
目前所說的 IP 地址是指 IPv4，它是使用 32 位（4 字節(jié)）地址，因此地址空間約有 42.9 億$2^32=4294967296$個, 不過一些地址是作為特殊用途所保留的，如專用網(wǎng)絡(luò)（約 1800 萬個）和多播地址（約 2.7 億個），這些減少了可在互聯(lián)網(wǎng)上路由的地址數(shù)量。 據(jù) wiki 上統(tǒng)計，中國的 IPv4 數(shù)量達到 3.3 億，而美國有 15.4 億個。

這里我們約定一下位置信息的數(shù)據(jù)格式： 國家|區(qū)域|省份|城市|ISP，如果接口中返回的字段沒有對應(yīng)的信息，則對應(yīng)的字段填充0。那么我們通過順序請求 API 服務(wù)可以獲取到如下文件數(shù)據(jù)（地址依次遞增）：

0.0.0.0|0|0|0|內(nèi)網(wǎng)IP|內(nèi)網(wǎng)IP
0.0.0.1|0|0|0|內(nèi)網(wǎng)IP|內(nèi)網(wǎng)IP
...
1.0.15.255|中國|0|廣東省|廣州市|電信
...
255.255.255.255|0|0|0|內(nèi)網(wǎng)IP|內(nèi)網(wǎng)IP

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

空間優(yōu)化

IP 庫文件優(yōu)化

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

0.0.0.0|0.255.255.255|0|0|0|內(nèi)網(wǎng)IP|內(nèi)網(wǎng)IP
...
1.0.8.0|1.0.15.255|中國|0|廣東省|廣州市|電信
...
224.0.0.0|255.255.255.255|0|0|0|內(nèi)網(wǎng)IP|內(nèi)網(wǎng)IP

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

IP地址優(yōu)化

從上面的文件數(shù)據(jù)發(fā)現(xiàn)大量的IP地址以字符串形式存儲，而 IPv4 是使用 32 位地址。所以將其轉(zhuǎn)換成整型進行存儲可以大大節(jié)省空間，比如像最短的字符串 0.0.0.0 占據(jù) 7 字節(jié)，最長的字符串 111.111.111.111 占據(jù) 15 字節(jié)，如果將其轉(zhuǎn)換成整型，他們都占據(jù) 4 字節(jié)。0.0.0.0 是 int(0), 111.111.111.111 是 int(1869573999)。

位置信息優(yōu)化

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

優(yōu)化后的IP庫

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

IP庫的結(jié)構(gòu)

IP 庫文件ip2region.db的結(jié)構(gòu)分為四個部分：super 塊， header索引區(qū)，數(shù)據(jù)區(qū)，索引區(qū)。具體如下圖所示：

• super 塊
  用來保存索引塊的起始地址和結(jié)束地址，第一個索引指針指向索引塊的開始位置，也就是第一個索引分區(qū)的第一個索引塊， 最后一個索引指針 指向索引塊的結(jié)束位置-12，也就是最后一個索引分區(qū)的最后一個索引塊的頭地址。這樣查詢的時候直接讀取super塊 8 個字節(jié)，就能快速獲取索引塊的地址范圍。

• header 索引區(qū)
  header索引是對索引塊的二級索引，專門為b+tree搜索服務(wù)的。索引區(qū)總長度除以索引分區(qū)長度12*(1024*8/12-1)就是 header 索引的實際索引數(shù)。該區(qū)域大小為 2048*8 bytes, 由 2048 個 8 bytes 的 header 索引塊組成。header索引塊前四個字節(jié)存儲每個索引分區(qū)第一個索引塊的起始ip值，后四個字節(jié)指向該索引塊的地址。
  header索引區(qū)之所以定義為接近16k，是因為可以通過四次磁盤讀取讀取整個header索引區(qū)，然后在內(nèi)存中進行查詢，查詢的結(jié)果可以確定該ip在索引區(qū)的某個索引分區(qū)內(nèi)，然后再根據(jù)地址兩次讀取8k 索引分區(qū)到內(nèi)存，再在內(nèi)存中查詢，從而減少磁盤讀取的次數(shù)。

• 數(shù)據(jù)區(qū)
  保存的數(shù)據(jù)，數(shù)據(jù)格式如下：中國|華南|廣東省|深圳市|鵬博士， 分別表示國家，區(qū)域，省份，城市，運營商

• 索引區(qū)
  索引區(qū)是由索引塊構(gòu)成， 每個索引塊占 12 字節(jié)，包括起始IP, 結(jié)束IP, 數(shù)據(jù)信息。數(shù)據(jù)信息中前三個字節(jié)保存數(shù)據(jù)地址，后一個字節(jié)保存數(shù)據(jù)長度。 每一條索引塊對應(yīng) ip.merge.txt 中的一條記錄，表示一個 IP 段的索引。
  在檢索中當(dāng)指定 IP 在某個索引塊的起始IP和結(jié)束IP中間，即表示命中索引。再通過索引塊中的數(shù)據(jù)地址和數(shù)據(jù)長度，就能從 ip2region.db 讀取對應(yīng)的位置信息數(shù)據(jù)。

IP庫的生成

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

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

1. 通過 RandomAccessFile 在文件中預(yù)留 8 bytes 的 super 塊和 2048*8 bytes 的 header 索引區(qū)

2. 掃描 ip.merge.txt 文件，對每一條記錄作如下處理：
   依據(jù)每一條記錄的起始IP, 結(jié)束IP 和數(shù)據(jù)，生成一個索引塊， 前四個字節(jié)存儲起始IP, 中間四個字節(jié)存儲結(jié)束IP, 后四個字節(jié)存儲已經(jīng)計算出的數(shù)據(jù)地址（通過 RandomAccessFile 寫入，這里維護一個位置信息到文件位置的字典，保證同一個位置信息只寫入一次。），并將索引塊暫存在 indexPool 鏈表中。這一步會將數(shù)據(jù)區(qū)的所有位置信息確定。

3. 掃描完 ip.merge.txt 中所有的記錄， 將 indexPool 中所有的索引塊寫到數(shù)據(jù)區(qū)后面。在此過程中將 int(1024*8/12-1)= 681 個索引塊組成一個索引分區(qū)，并記錄下每個索引分區(qū)第一個索引塊的起始IP和地址信息（header塊），并暫存在 headerPool 鏈表中。此外還會將索引區(qū)的起始位置和結(jié)束位置記錄下來。

4. 調(diào)整 RandomAccessFile 指向文件開頭，寫入索引區(qū)的起始位置存儲到 super 塊的前四個字節(jié)，結(jié)束位置存儲到 super 塊的后四個字節(jié)。

5. 繼續(xù)將 headerPool 中的 header 塊寫入到 header 區(qū)。

6. 調(diào)整 RandomAccessFile 指向文件結(jié)尾，寫入時間戳和版權(quán)信息。

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

快速搜索

ip2region 提供三種查詢算法，最差的查詢耗時都是ms級別的。分別是內(nèi)存二分搜索，b+tree搜索，二分查找。耗時依次增加。其搜索結(jié)構(gòu)圖如下：

二分搜索

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

1. 把 IP 值通過 ip2long 方法轉(zhuǎn)為整型

2. 讀取 super 塊獲取索引區(qū)的起始位置和結(jié)束位置，二者相減 +1 可得索引塊的總個數(shù)

3. 采用二分法直接求解，比較索引塊中起始IP，結(jié)尾IP 和當(dāng)前 IP 的大小，即可找到該 IP 對應(yīng)的索引塊，根據(jù)索引塊后面四個字節(jié)得到數(shù)據(jù)地址和數(shù)據(jù)長度，從而拿到位置信息。

b+tree搜索

b+tree 搜索用到了 header 索引區(qū)，第一步先在 header 索引區(qū)中使用二分搜索，定位到某個索引分區(qū)后，再在對應(yīng)的索引分區(qū)中使用二分搜索。相比較二分搜索而言，它的速度更快，原因是讀磁盤的次數(shù)遠低于二分搜索。其步驟如下：

1. 把 IP 值通過 ip2long 轉(zhuǎn)為整型

2. 使用二分法在 header 索引區(qū)中搜索，比較得到對應(yīng)的 header 索引塊以及其對應(yīng)的索引分區(qū)。

3. 讀取對應(yīng)索引分區(qū)，再通過二分法定位到對應(yīng)的索引塊，從而獲得位置信息。

基于內(nèi)存的二分搜索

該方法和二分搜索方法類似，區(qū)別就是前者將 ip2region.db 全部讀進內(nèi)存中，后者則是通過不斷讀取 ip2region.db 文件。

ip2region 庫只解決了一個非常常見的 IP 定位問題，但將這個服務(wù)做到了又小又快（當(dāng)然還提供了多語言的客戶端），從而在 Github 上獲得了 8.4k 的 star。

占用內(nèi)存小

1. 相鄰 IP 的位置信息相同，通過 IP 段來解決相鄰 IP 對應(yīng)相同位置信息，避免位置信息被重復(fù)存儲

2. IP 轉(zhuǎn)換成 INT，像字符串 111.111.111.111 被轉(zhuǎn)換成int（1869573999），從 15Byte 縮小到 4Byte

3. 不同的 IP 段也有相同的位置信息，通過指針來指向特定的位置信息，保證位置信息只保存一次（全量掃描存儲進字典中）

搜索速度快

1. IP 有序，使用二分搜索將時間復(fù)雜度降到 O(logN)

2. 二級索引 header 索引區(qū)的使用，降低磁盤讀寫頻率，先確定索引分區(qū)，再從索引分區(qū)確定索引位置，再確定位置信息數(shù)據(jù)。

多語言客戶端支持

支持 java、C#、php、c、python、nodejs、php擴展(php5和php7)、golang、rust、lua、lua_c, nginx。

關(guān)于怎么深入分析ip2region實現(xiàn)問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。