XDB search 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. Going deep into the search process will in turn give you a clearer picture of the structure of the whole xdb file. The search process consists of the following four core steps.
Step 1: Convert the IP into a byte array
Every query binding has a parseIP-like function that converts a string IP into a big-endian byte array: an IPv4 address parses into a 4-byte array, and an IPv6 address into a 16-byte array. For example:
// Convert IPv4 into ip_bytes
var ip_bytes = parseIP("58.251.27.201")
// [58,251,27,201]
// Convert IPv6 into ip_bytes
var ip_bytes = parseIP("240e:3b7:3272:d8d0:db09:c067:8d59:539e")
// [36,14,3.,83,50,114,216,208,219,9,192,103,141,89,83,158]
// Note: the code demos below will use the ip_bytes global variable directlyStep 2: Get the binary search index segment from the vector index
Step one ensures that the ip_bytes argument we receive is a byte array, 4 or 16 bytes. The lookup logic for fetching the binary search index segment is simple, as follows:
// Constant definitions
// Number of bytes per vector index entry
var VectorIndexSize = 8
// Number of columns of the vector index
var VectorIndexCols = 256
// Total number of bytes of the vector index segment
var VectorIndexLength = 512KiB
// Assume vectorIndex is the loaded vector index
// the data returned by the loadVectorIndex api, essentially a one-dimensional byte array.
var vectorIndex = byte[VectorIndexLength]
// Integer of the first byte (& 0xFF, ensuring a value in 0 ~ 255)
var il0 = ip_bytes[0] & 0xFF
// Integer of the second byte (& 0xFF, ensuring a value in 0 ~ 255)
var il1 = ip_bytes[1] & 0xFF
// Compute the start address of the vector index entry.
// You can compare this against the vector table structure above to understand it
var idx = il0 * VectorIndexCols * VectorIndexSize + il1 * VectorIndexSize
// Start address of the region's binary search index
// read 4 bytes starting at idx and decode them as little-endian into an unsigned integer
var sPtr = le_getUint32(vectorIndex, idx)
// End address of the region's binary search index
// read 4 bytes at idx + 4 and decode them as little-endian into an unsigned integer
var ePtr = le_getUint32(vectorIndex, idx + 4)Every searcher binding has an api for loading the vectorIndex, which is essentially a one-dimensional byte array. The first two bytes of the IP address are then used to quickly obtain, from the vectorIndex, the start and end addresses of this partition's binary search index. This is the core of the vector index: one lookup splits the binary search index into 256 × 256 partitions, drastically reducing the scan range of the subsequent binary search, thereby reducing the number of IO operations at runtime and speeding up the query process.
Step 3: Perform the binary search within the binary search index
After step two yields the start and end addresses of the region's binary search index, you can run a binary search between this region's index boundaries to obtain the concrete information that pinpoints the region data. This search must distinguish the IP version; the IP version class and its corresponding instance configuration are described as follows:
class Version {
var id; // version number
var name; // version name
var bytes; // number of IP bytes
var indexSize; // number of bytes of a binary search index entry
func ipSubCompare; // IP comparison function, different for IPv4 and IPv6
}
// IPv4 version instance
var IPv4 = new Version(4, "IPv4", 4, 14, func(ip1, buff, offset){
// For compatibility with the old 2.0 version: the ip1 being queried is big-endian, while the target ip at buff[offset:ip1.length] is little-endian.
// For the concrete search code, refer to the binding implementation in the language you are familiar with.
});
// IPv6 version instance
var IPv6 = new Version(6, "IPv6", 16, 38, func(ip1, buff, offset){
// Both ip1 and buffer[offset:ip1.length] are big-endian.
// For the concrete search code, refer to the binding implementation in the language you are familiar with.
});With the version defined as the version argument, the concrete binary search process is as follows:
// IP version description instance for the query, v4 = IPv4, v6 = IPv6
var version
// Low end of the binary search
var l = 0
// High end of the binary search
// Subtract the start index position from the end index position obtained in step one
// and divide by the byte size of each index entry to get the number of index entries this search will scan.
var h = (ePtr - sPtr) / version.indexSize
// Data length / data address
var dataLen = 0, dataPtr = 0
// Number of ip_bytes bytes / twice the number of ip_bytes bytes
var bytes = ip_bytes.length, dBytes = ip_bytes.length << 1;
// Start the binary search to obtain the length and position info of the region data
var buff[version.indexSize]
for l < h {
// Get the middle index entry
var m = (l + h) >> 1
// Compute the pointer address of the middle index entry
// just add m's relative address to the start address sPtr
var p = sPtr + m * version.indexSize
// Read buff.length bytes starting at position p into buff
// giving a complete binary search index entry as described above; to avoid unnecessary work we decode on demand
read(p, buff)
// Compare the ip_bytes being queried with the start IP of the current binary search index segment
if version.ipSubCompare(ip_bytes, buff, 0) < 0 {
// ip_bytes is smaller than sip, i.e. to the left of position p
h = m - 1
} else if version.ipSubCompare(ip_bytes, buff, bytes) > 0 {
// ip_bytes is larger than eip, i.e. to the right of position p
l = m + 1
} else {
// Search hit
// the target ip lies exactly between sip and eip
// meaning the target ip has been found
// Decode 2 bytes little-endian into an unsigned integer, which is the length of the region data
dataLen = le_getUint16(buff, dBytes)
// Decode 4 bytes little-endian into an unsigned integer, which is the address of the region data
dataPtr = le_getUint32(buff, dBytes + 2)
}
}After the search process above, we obtain the length dataLen and the address dataPtr of the region data.
Step 4: Fetch the region info and complete the search
With the dataLen and dataPtr obtained in step three, we can easily get the region data: reading dataLen bytes from position dataPtr gives the region data. The concrete code is as follows:
// Move the file pointer to dataPtr
handle.seek(dataPtr)
// Read dataLen bytes from the current position
var buff[dataLen]
handle.read(buff)
// Decode buff into a utf-8 string and return it
return string(buff, "utf-8")That completes the walkthrough of the entire xdb query process. You may not fully grasp everything on a first read of XDB data structure, but combined with the query logic above you should get a fairly clear picture of the whole xdb structure.