ip2region xdb 二進制資料生成過程詳解

一、xdb 結構簡述

為了便于了解接下來要介紹的 xdb 的生成過程，我們有必要再了解下 xdb 檔案的結構分層，整個檔案的資料分為如下四層：

四層結構的作用分别如下：

Header 資料段：存儲例如版本号，索引指針等頭資訊，固定空間。

Vector 索引資料段：二級加速索引，固定空間。

地域資訊資料段：IP 歸屬地地域資訊資料，不固定空間。

二分索引資料段：二分查找依賴的一級索引資料，不固定空間。

二、幾個重要約定

描述過程中我會給每個核心過程配上必要的僞代碼，為了僞代碼的簡明我們先統一如下幾個約定：

1、全部的語言層面的 API 調用都忽略錯誤檢測和處理：僞代碼重點用于描述核心過程邏輯，錯誤處理細節可以閱讀相關的 maker 代碼。

2、多位元組的編解碼全部采用小端位元組序：除非特殊注明的地方。

3、字面資料類型統一：uint16，uint32，int64 等等，u表示無符号，後面的數字就表示占據的位數，例如：uint32 表示 32 位的無符号整數。

三、初始化工作

初始化工作主要包括如下三個部分：

1、打開原始的 ip.merge.txt 檔案和目标 xdb 二進制檔案：

// 以隻讀模式打開 ip.merge.txt 原始輸入檔案
srcHandle = fopen("ip.merge.txt file path", "r")


// 以讀寫模式打開 xdb 二進制檔案目的位址，不存在自動建立 xdb 檔案
dstHandle = fopen("ip2region.xdb dst path", "rw")           

2、配置設定 header 資料段的空間，并寫入已經确定的資訊，整個 header 資料段的空間結構如下：

header 資料的初始化邏輯如下：

// 将 dstHandle seek 到檔案開頭
dstHandle.seek(0, SEEK_SET)


  // header 資訊 buffer 數組，并且全部初始化為 0
var header[256] = {0}


// 從0索引處寫入2個位元組的版本号，此處固定為 2
writeShort(header, 0, VersionNo)
// 從2索引處寫入2個位元組的的緩存政策，此處固定為 1，表示采用 vector 索引
writeShort(header, 2, indexPolicy)
// 從4索引處寫入4個位元組的生成時間，擷取目前系統時間戳
writeInt(header, 4, time.Unix())
// 從8索引處寫入4個位元組的二分索引開始指針位址，一開始不确定，固定寫入 0
writeInt(header, 8, 0)
// 從12索引處寫入4個位元組的二分索引結束指針位址，一開始不确定，固定寫入 0
writeInt(header, 12, 0)


// 寫入整個 header 到 dstHandle 檔案中
dstHandle.Write(header)           

3、加載 ip.merge.txt 中的 IP 資料段并且對資料段進行必要的驗證：

// 全部的 ip 資料段對象動态數組
var Segment[] segments


// 上一個 ip 段的引用   
var Segment last 


// 逐行讀取 srcHandle 中的 ip 資料段
for s := srcHandle.lines() {
  // 去掉兩邊可能存在的空白
  var l = trim(s)
  
  // 對讀取的資料進行拆分
  // ps[0] -> 開始 IP
  // ps[1] -> 結束 IP
  // ps[2] -> 地域資訊，不做任何處理
  var ps = l.SplitN("|", 3)


  // 檢查開始和結束 IP，確定都是合法的 IP 位址
  var sip = CheckIP(ps[0])
  var eip = CheckIP(ps[1])


  // 開始 IP 應該 <= 結束 IP
  if sip > eip {
    return errorf("start ip(%s) should not be greater than end ip(%s)", ps[0], ps[1])
  }


  // 地域資訊應該有點什麼，空的算啥？
  if len(ps[2]) < 1 {
    return errorf("empty region info in segment line `%s`", l)
  }


  // 建立一個 Segment 結構體或者對象
  // 這裡 seg 為指針或者引用
  var seg = &Segment{
    StartIP: sip,
    EndIP:   eip,
    Region:  ps[2],
  }


  // 檢查 IP 資料段的連續性
  // 也就是上一行的結束 IP + 1 需要等于這行的開始 IP
  if last != nil {
    if last.EndIP+1 != seg.StartIP {
      return errorf("discontinuous data segment: last.eip+1(%d) != seg.sip(%d, %s)", sip, eip, ps[0])
    }
  }


  // 将得到的 IP 段對象加入到全局的 segments 動态數組中
  segments.add(seg)
  
  // 重置上一個 IP 段 last 為目前這個 Segment對象
  last = seg
}           

四、寫入地域資料資訊

完成了上面的初始化就可以開始寫入地域資料了，為什麼地域資料的寫入是在這一步呢？vector 索引在第二層，但是他需要等到二分索引寫入完成後才能确定，因為 vector 索引本身就是二分索引的索引，而二分索引在第四層，但是二分索引的結構本身需要對應 IP 段的地域資訊的指針，是以我們需要先寫入地域資訊資料并且得到每個地域資訊的指針，才能比較自然的完成不同層段的資料依賴映射。

地域資訊的去重和寫入邏輯如下：

// 地域資訊指針 map，同時用來去重
var regionPool[string]int64


// 将 dstHandle seek 到資料段的開始位置
// HeaderInfoLength 就是 header 段的長度 - 固定 256
// VectorIndexLength 就是 vector 索引段的長度 - 固定 512KiB 
dstHandle.seek(HeaderInfoLength+VectorIndexLength, SEEK_SET)


// 逐條寫入初始化過程中加載的 segments 集合
for _, seg := range segments {
  // 先檢測下對應的地域資訊是否已經寫入
  // 同時可以過濾已經寫入了的重複地域資訊
  ptr, has := regionPool[seg.Region]
  if has {
    // 地域資訊已經寫入了
    continue
  }


  // 使用 utf-8 編碼地域資訊字元串
  var region = getUtf8Bytes(seg.Region)
  
  // 確定 region 位元組數的整個長度不超過 65535
  // 也就是可以用兩個位元組存儲其長度
  if len(region) > 0xFFFF {
    return errorf("too long region info `%s`: should be less than %d bytes", seg.Region, 0xFFFF)
  }


  // 擷取目前 dstHandle 的目前的檔案指針
  pos = dstHandle.ftell()


  // 寫入 region 到 dstHandle
  dstHandle.write(region)


  // 記下目前地域資訊寫入時候的檔案指針
  // 這裡使用 uint32 轉換檔案指針，也就是之保留 32 位
  // 檔案最大可以 4G，對于 ipv4 完全足夠了
  regionPool[seg.Region] = uint32(pos)
}           

五、建構二分索引

上一步我們寫入了地域資料并且存儲對應的檔案指針資訊 - regionPool，有了這個資料我們就可以建構第四層的二分索引了，這一步是整個生成過程最複雜的一個過程，這個過程還需要同步建構 vector 二級索引資訊，需要對本身的 IP 資料段進行二次拆分，目的是為了使用一次固定的 IO 操作大幅度的減少二分索引的掃描範圍，加速查詢，詳細的解釋請閱讀上一篇的 ”xdb 的查詢過程“。

在生成二分索引的時候我們将利用 IP 的第一個和第二個位元組來生成 vector 索引，是以要確定每個 IP 段的開始和結束 IP 的第一個和第二個位元組一樣，如果不一樣就需要拆分成多個 IP 段，例如如下的一個 IP 資料段：

1.1.0.0|1.3.3.24|中國|廣東|深圳|電信           

第一個位元組相同都是 1，但是第二個位元組就不同了，是以這裡需要拆分成如下三個 IP 段：

1.1.0.0|1.1.255.255|中國|廣東|深圳|電信
1.2.0.0|1.2.255.255|中國|廣東|深圳|電信
1.3.0.0|1.3.3.24|中國|廣東|深圳|電信           

經過拆分後的三個 IP 段的開始和結束 IP 的第一個和第二個位元組都相等了，這樣我們在建構二分索引的時候可以非常友善的建構 vector 二級索引。IP 資料段的二次拆分代碼就不在此描述了，你可以用你自己的邏輯來實作，也可以參考預設的 maker 的實作。

二分索引項的空間結構如下：

二分索引整個寫入邏輯如下：

// 二分索引資料段的開始和結束檔案指針值
var startIndexPtr, endIndexPtr = int64(-1), int64(-1)


// 二分索引緩沖 buffer，并且初始化為 0
var indexBuff[SegmentIndexSize] = {0}


// 周遊每一個 segment 開始生成二分索引
for _, seg := range segments {
  // 擷取目前地域資訊的位置指針
  // 這個資料是在第四步的 “寫入地域資訊” 記錄的
  ptr, has := regionPool[seg.Region]
  if !has {
    return errorf("missing ptr cache for region `%s`", seg.Region)
  }


  // 擷取地域資訊 utf-8 編碼後的位元組數
  var rLen = utf8Bytes(seg.Region)


  // 檢測并且拆分目前資料段
  var segList = seg.Split()
  
  // 周遊拆分後的資料段進行處理
  for _, s := range segList {
    // 記錄目前 dstHandle 檔案指針位置
    pos = dstHandle.ftell()


    // 編碼二分索引資訊到 indexBuff
    // 從0索引處寫入4位元組的開始 IP
    writeInt(indexBuff, 0, s.StartIP)
    // 從4索引處寫入4位元組的結束 IP
    writeInt(indexBuff, 4, s.EndIP)
    // 從8索引處寫入2位元組的地域資訊長度
    writeInt(indexBuff, 8, uint16(rLen))
    // 從10索引處寫入4位元組的地域資訊位置指針
    writeInt(indexBuff[10:], ptr)
    
    // 寫入編碼後的 indexBuff 到 dstHandle 檔案
    dstHandle.write(indexBuff)


    // 更新目前 IP 段的 vector 索引資訊
    // @Note: 檢視下面的詳細介紹
    setVectorIndex(s.StartIP, uint32(pos))


    // 檢測并且更新二分索引的開始和結束指針
    endIndexPtr = pos
    if startIndexPtr == -1 {
      startIndexPtr = pos
    }
  }
}           

六、寫入 vector 索引資訊

二分索引寫入完成後，我們就可以緊接着處理 vector 二級索引了，上面的二分索引建構過程中有個 setVectorIndex 就是更新記憶體中的 vector 索引的位置，vectorIndex 的空間結構如下，等同于一個 256 x 256 的二位數組：

vector 索引更新函數的實作如下：

func setVectorIndex(ip uint32, ptr uint32) {
  // 擷取 ip 的第一個位元組
  var il0 = (ip >> 24) & 0xFF
  
  // 擷取 ip 的第二個位元組
  var il1 = (ip >> 16) & 0xFF
  
  // 計算目前 ip 的 vector 索引的偏移量
  // 等同于二位數組的 vectorIndex[il0][il1]
  var idx = il0*VectorIndexCols*VectorIndexSize + il1*VectorIndexSize
  
  // 從 idx 解碼4個位元組得到目前 ip 的 vector 索引資訊
  var sPtr = getInt(vectorIndex, idx)
  if sPtr == 0 {
    // 索引資訊尚不存在 - 第一次更新
    // 從 idx 處寫入4位元組的ptr資訊
    writeInt(vectorIndex, idx, ptr)
    // 從 idx+4 處寫入4位元組的ptr資訊
    writeInt(vectorIndex, idx + 4, ptr+SegmentIndexSize)
  } else {
    // vector 索引資訊已經存在 - 更新
    // 從 idx+4 處寫入4位元組的ptr資訊
    writeInt(vectorIndex, idx+4, ptr+SegmentIndexSize)
  }
}           

二分索引寫入完成後，就可以直接寫入 vector 索引到 dstHandle 檔案中，具體邏輯如下：

// 将 dstHandle seek 到 vector 索引段開始位置
dstHandle.seek(int64(HeaderInfoLength), SEEK_SET)


// 寫入 vectorIndex 緩沖到 dstHandle
dstHandle.write(vectorIndex)           

七、記錄二分索引位置資訊

最後再把二分索引寫入過程中記載的二分索引段的開始和結束的指針資訊寫入頭資訊中即可，具體實作如下：

// dstHandle seek 到 8 位置 - header 資訊中存儲索引首位址的位置
dstHandle.seek(8, SEEK_SET)


// 編碼二分索引開始和結束位址到 indexBuff
var indexBuff[8]
// 從 0 處寫入4個位元組的 startIndexPtr
writeInt(indexBuff, 0, uint32(startIndexPtr))
// 從 4 處寫入4個位元組的 endIndexPtr
writeInt(indexBuff, 4, uint32(endIndexPtr))


// 最後将 indexBuff 寫入到 dstHandle
dstHandle.write(indexBuff[:8])           

利用這裡寫入的二分索引的開始和結束位置資訊也可以做完全的二分查找，也就是不基于 vector 索引的查找，查找過程自然會慢很多。

到此整個 xdb 二進制檔案的生成過程就介紹完成了，詳細的實作代碼可以參考你熟悉的語言的 maker 實作，有問題歡迎到 ip2region 技術交流群讨論。

作者:獅子的魂

來源:微信公衆号:獅子的魂

出處:https://mp.weixin.qq.com/s/HEAc7WKzAjH5oTwgxojPUg