XDB generation process

Before reading this chapter I assume you have already read the description in XDB data structure and have a basic understanding of the XDB data structure. To make the xdb generation process described below easier to follow, here is once more the layered structure of the xdb file, in these four layers:

Header segment	Vector index segment	Region data segment	Binary search index segment
256 Bytes	512 KiB	Dynamic space	Dynamic space

The roles of the four layers are as follows:

Header segment: stores header information such as the version number and index pointers; fixed space.
Vector index segment: the second-level acceleration index; fixed space.
Region data segment: the IP region info data; the space is not fixed.
Binary search index segment: the first-level index data that the binary search depends on; the space is not fixed.

1. A few important conventions

In this description I will accompany each core step with the necessary pseudocode. To keep the pseudocode concise, let us first agree on the following conventions:

Error handling: all language-level API calls ignore error detection and handling. The pseudocode focuses on describing the core process logic; for the error-handling details, read the corresponding maker code.
Byte order: except for the byte arrays obtained from IP parsing, which use big-endian byte order, all multi-byte encoding and decoding uses little-endian byte order unless explicitly noted otherwise.
Data types: literal data types are written uniformly as uint16, uint32, int64 and so on; u means unsigned and the number after it gives the width in bits. For example, uint32 denotes a 32-bit unsigned integer.

2. Initialization work

The initialization work mainly includes the following three parts:

Open the source IP file and the destination xdb binary file:

// IP version of the source IP file: set to IPv4 for v4 and IPv6 for v6.
// For the class description of Version, see the relevant description in the XDB search process chapter.
var version = IPv4; // or IPv6;

// Open the ipvx_source.txt source input file in read-only mode
var srcHandle = fopen("ipvx_source.txt file path", "r")

// Open the xdb binary destination in read-write mode; the xdb file is created automatically if it does not exist
var dstHandle = fopen("ip2region_vx.xdb dst path", "rw")

// Note: the demo code below will use the three global variables above directly

Allocate the space of the header data segment and write in the information that is already determined. The space structure of the entire header data segment is as follows:

Version	Cache policy	File creation time	Index start pointer	Index end pointer	IP version	Pointer bytes	Reserved space
2 Bytes	2 Bytes	4 Bytes	4 Bytes	4 Bytes	2 Bytes	2 Bytes	`236`Bytes

The initialization logic of the header data is as follows:

// Seek dstHandle to the beginning of the file
dstHandle.seek(0, SEEK_SET)

// Header info buffer array, all initialized to 0
var header[256] = {0}

// Write 2 bytes of version number at index 0; fixed at 2 here
writeShort(header, 0, VersionNo)
// Write 2 bytes of cache policy at index 2; fixed at 1 here, meaning the vector index is used
writeShort(header, 2, indexPolicy)
// Write 4 bytes of creation time at index 4, taking the current system timestamp
writeInt(header, 4, time.Unix())
// Write 4 bytes of the binary search index start pointer address at index 8; not yet known, write a fixed 0
writeInt(header, 8, 0)
// Write 4 bytes of the binary search index end pointer address at index 12; not yet known, write a fixed 0
writeInt(header, 12, 0)

// The fields below exist only from xdb structure 3.0 onward, i.e. versions with IPv6 support
// Write 2 bytes of IP version number at index 16
writeShort(header, 16, version.id)
// Write 2 bytes of runtime pointer bytes at index 18; RuntimePtrSize is currently fixed at 4
writeShort(header, 16, uint16(RuntimePtrSize))

// Write the entire header into the dstHandle file
dstHandle.Write(header)

Load the IP segments from ipvx_source.txt and perform the necessary validation on the segments:

// Dynamic array of all ip segment objects
var Segment[] segments

// Reference to the previous ip segment
var Segment last

// Read the ip segments in srcHandle line by line
for s := srcHandle.lines() {
  // Strip whitespace on both ends, if any
  var l = trim(s)

  // Split the line read
  // ps[0] -> start IP
  // ps[1] -> end IP
  // ps[2] -> region info, left untouched
  var ps = l.SplitN("|", 3)

  // Parse the start and end IP, ensuring both are valid IP addresses
  var sip_bytes = parseIP(ps[0])
  var eip_bytes = parseIP(ps[1])

  // The start IP should be <= the end IP
  if ipCompare(sip_bytes, eip_bytes) > 0 {
    return errorf("start ip(%s) should not be greater than end ip(%s)", ps[0], ps[1])
  }

  // Since xdb 3.0 the region info may be empty, making it easy for developers to generate custom fields

  // Create a Segment struct or object
  // here seg is a pointer or reference
  var seg = &Segment{
    StartIP: sip_bytes,
    EndIP:   eip_bytes,
    Region:  ps[2],
  }

  // Check the continuity of the IP segments
  // that is, the previous line's end IP + 1 must equal this line's start IP
  if last != nil {
      if ipCompare(ipAddOne(last.EndIP), seg.StartIP) != 0 {
          return errorf("discontinuous data segment: last.eip+1(%d) != seg.sip(%d, %s)", sip, eip, ps[0])
      }
  }

  // Add the resulting IP segment object to the global segments dynamic array
  segments.add(seg)

  // Reset the previous IP segment last to this Segment object
  last = seg
}

3. Write the region data

With the initialization above done, we can start writing the region data. Why is the region data written at this step? The vector index sits in the second layer, but it cannot be determined until the binary search index has been written, because the vector index is itself an index of the binary search index; and the binary search index sits in the fourth layer, yet its structure needs the pointer to the region info of the corresponding IP segment. So we must write the region info data first and obtain each region info's pointer before the data dependencies between the different layers can be mapped out naturally.

The dedup and write logic for the region info is as follows:

// Region info pointer map, also used for dedup
var regionPool[string]int64

// Seek dstHandle to the start position of the data segment
// HeaderInfoLength is the length of the header segment - fixed 256
// VectorIndexLength is the length of the vector index segment - fixed 512KiB
dstHandle.seek(HeaderInfoLength+VectorIndexLength, SEEK_SET)

// Write the segments collection loaded during initialization one by one
for _, seg := range segments {
  // First check whether the corresponding region info has already been written
  // this also filters out duplicate region info that was already written
  ptr, has := regionPool[seg.Region]
  if has {
    // The region info has already been written
    continue
  }

  // Encode the region info string as utf-8
  var region = getUtf8Bytes(seg.Region)

  // Ensure the total length of the region bytes does not exceed 65535
  // so that its length can be stored in two bytes
  if len(region) > 0xFFFF {
    return errorf("too long region info `%s`: should be less than %d bytes", seg.Region, 0xFFFF)
  }

  // Get the current file pointer of dstHandle
  pos = dstHandle.ftell()

  // Write the region into dstHandle
  dstHandle.write(region)

  // Record the file pointer at the moment this region info was written
  // the file pointer is converted with uint32, i.e. only the lower 32 bits are kept
  // the file can be at most 4G, which is fully sufficient for ipv4
  regionPool[seg.Region] = uint32(pos)
}

4. Build the binary search index

In the previous step we wrote the region data and stored the corresponding file pointer information in regionPool. With this data we can build the fourth-layer binary search index. This is the most complex part of the whole generation process. It also builds the vector second-level index information at the same time, which requires re-splitting the IP segments themselves — the goal is to use one fixed IO operation to greatly reduce the scan range of the binary search index and speed up queries. For a detailed explanation, read XDB search process.

When generating the binary search index we will use the first and second bytes of the IP to build the vector index, so we must ensure that the first and second bytes of a segment's start and end IP are the same; if not, the segment needs to be split into multiple IP segments. For example, the following IP segment:

1.1.0.0|1.3.3.24|中国|广东|深圳|电信

has the same first byte (1), but the second byte differs, so it needs to be split into the following three IP segments:

1.1.0.0|1.1.255.255|中国|广东|深圳|电信
1.2.0.0|1.2.255.255|中国|广东|深圳|电信
1.3.0.0|1.3.3.24|中国|广东|深圳|电信

After the split, the first and second bytes of the start and end IP of all three IP segments are equal, which makes building the vector second-level index very convenient while building the binary search index. The code for this re-splitting of IP segments is not described here; you can implement it with your own logic or refer to the default maker implementation.

The space structure of a binary search index entry is as follows:

Start IP	End IP	Data length	Data pointer
4 / 16 Bytes	4 / 16 Bytes	2 Bytes	4 Bytes

The complete write logic of the binary search index is as follows:

// Start and end file pointer values of the binary search index segment
var startIndexPtr, endIndexPtr = int64(-1), int64(-1)

// Binary search index buffer, of length version.indexSize (different for IPv4 / IPv6), initialized to 0
var indexBuff[version.indexSize] = {0}

// Iterate over every segment to generate the binary search index
for _, seg := range segments {
  // Get the position pointer of the current region info
  // this data was recorded in step 4, "Write the region info"
  ptr, has := regionPool[seg.Region]
  if !has {
    return errorf("missing ptr cache for region `%s`", seg.Region)
  }

  // Get the byte length of the region info after utf-8 encoding
  var rLen = utf8Bytes(seg.Region)

  // Detect and split the current segment
  var segList = seg.Split()

  // Iterate over the split segments and process them
  for _, s := range segList {
    // Record the current file pointer position of dstHandle
    pos = dstHandle.ftell()

    // Encode the binary search index info into indexBuff
    // write the start IP bytes at index 0
    writeInt(indexBuff, 0, s.StartIP)
    // write the end IP bytes at index len(s.StartIP)
    writeInt(indexBuff, len(s.StartIP), s.EndIP)

    // The offset value in the buffer after the IP addresses
    var offset = len(s.StartIP.length) + len(s.EndIP);
    // Write 2 bytes of region info length
    writeInt(indexBuff, offset, uint16(rLen))
    // Write 4 bytes of the region info position pointer
    writeInt(indexBuff, offset + 2, ptr)

    // Write the encoded indexBuff into the dstHandle file
    dstHandle.write(indexBuff)

    // Update the vector index info of the current IP segment
    // @Note: see the detailed introduction below
    setVectorIndex(s.StartIP, uint32(pos))

    // Detect and update the start and end pointers of the binary search index
    endIndexPtr = pos
    if startIndexPtr == -1 {
      startIndexPtr = pos
    }
  }
}

5. Write the vector index information

Once the binary search index has been written, we can immediately proceed to the vector second-level index. In the binary search index building process above, the setVectorIndex call updates the positions in the in-memory vector index. The space structure of vectorIndex is as follows — equivalent to a 256 x 256 two-dimensional array:

0	1	...	254	255
1
2
...
254
255

The implementation of the vector index update function is as follows:

func setVectorIndex(ip_bytes byte[], ptr uint32) {
  // Get the first byte of the ip
  var il0 = ip_bytes[0] & 0xFF

  // Get the second byte of the ip
  var il1 = ip_bytes[1] & 0xFF

  // Compute the vector index offset of the current ip
  // equivalent to the two-dimensional array's vectorIndex[il0][il1]
  var idx = il0*VectorIndexCols*VectorIndexSize + il1*VectorIndexSize

  // Decode 4 bytes at idx to get the vector index info of the current ip
  var sPtr = le_getUint32(vectorIndex, idx)
  if sPtr == 0 {
    // The index info does not exist yet - first update
    // write 4 bytes of ptr info at idx
    writeInt(vectorIndex, idx, ptr)
    // write 4 bytes of ptr info at idx + 4
    writeInt(vectorIndex, idx + 4, ptr + version.indexSize)
  } else {
    // The vector index info already exists - update
    // write 4 bytes of ptr info at idx + 4
    writeInt(vectorIndex, idx + 4, ptr + version.indexSize)
  }
}

After the binary search index has been written, the vector index can be written straight into the dstHandle file. The concrete logic is as follows:

// Seek dstHandle to the start position of the vector index segment
dstHandle.seek(int64(HeaderInfoLength), SEEK_SET)

// Write the vectorIndex buffer into dstHandle
dstHandle.write(vectorIndex)

6. Record the binary search index position information

Finally, write the start and end pointer information of the binary search index segment, recorded during the binary search index writing, into the header information. The concrete implementation is as follows:

// Seek dstHandle to position 8 - where the header info stores the index start address
dstHandle.seek(8, SEEK_SET)

// Encode the binary search index start and end addresses into indexBuff
var indexBuff[8]
// write 4 bytes of startIndexPtr at 0
writeInt(indexBuff, 0, uint32(startIndexPtr))
// write 4 bytes of endIndexPtr at 4
writeInt(indexBuff, 4, uint32(endIndexPtr))

// Finally write indexBuff into dstHandle
dstHandle.write(indexBuff[:8])

The binary search index start and end position information written here can also be used to perform a complete binary search, i.e. a search that does not rely on the vector index; that search process is naturally much slower.

That completes the introduction to the generation process of the entire xdb binary file. For the detailed implementation code, refer to the maker implementation in the language you are familiar with.