判断 ip 是否在一个超大 ip 集中（识别国内 ip）

原文地址： https://www.ikaze.cn/article/65

前几天发帖/t/785801讨论匹配大量 ip 的方法，经过几天的思考，把最终使用的方法分享给大家。

1. 通过 ip 位置数据库

比较有名的服务商有：ipip（付费）， maxmind （付费），纯真（免费）。

但在这个应用场景下，我们并不需要具体的位置信息，类似的方案会浪费不必要的内存因此放弃。

2. 利用 ip 的连续性

后面两个方法有个前提：ip 地址列表中大部分是连续的。

这里我们已有了国内 ip 地址列表（已有开源的库，很好找，另外我用的这个库已经把 ip 合并为了 CIDR 格式的地址）。

我们先通过二进制把 ip 转为可直接比较的数字，再把连续的 ip 变为 (start_ip, end_ip) 这样的集合，就可以利用二分法快速查找了。

import ipcalc

class ChinaIp:
    def __init__(self):
        self.data = []

    def load(self, cidr_file='data/china_ip_list.txt'):
        with open(cidr_file, 'r')as f:
            for s in f.readlines():
                self.add(s.strip())

    def add(self, cidr):
        n = ipcalc.Network(cidr)
        self.data.append((n.host_first().ip, n.host_last().ip))

    def search(self, ip):

        l = 0
        r = len(self.data) - 1
        while l <= r:
            mid = (l + r) // 2
            if self.data[mid][0] <= ip <= self.data[mid][1]:
                return True
            elif self.data[mid][0] > ip:
                r = mid - 1
            elif self.data[mid][1] < ip:
                l = mid + 1
            else:
                return False
        return False

    def __contains__(self, item):
        ip = ipcalc.IP(item).ip
        return self.search(ip)
        
china_ip = ChinaIp()
china_ip.load()
print('223.70.163.83' in china_ip)

3. 利用 CIDR 的特性

CIDR 是形如 x.x.x.x/n 这样的地址，它表示一组网络地址相同的 ip，其中 n 表示前 n 位作为网络地址。

根据 CIDR 的特性，我们可以得到这样的结论：同一 CIDR 下的 ip，其网络地址是相同的。

因此我们可以把所有国内 cidr 地址的网络地址取出，放字典；对于一个 ip，尝试可能的网络地址（即 n ），看其是否在字典中。

import ipcalc

class ChinaIp(object):
    def __init__(self):
        self.data = {}


    def load(self, cidr_files='data/china_ip_list.txt'):
        with open(cidr_files, 'r')as f:
            cidr_list = f.readlines()

        for cidr in cidr_list:
            self.insert(cidr.strip())

    def insert(self, cidr):
        network = ipcalc.Network(cidr)
        self.data[str(network.netmask())]=True

    def search(self, netmask: str) -> bool:

        for i in netmask.split('.'):
            node = node.children.get(i, None)
            if node is None:
                return False
            if node.is_end:
                return True
        return False

    def __contains__(self, ip):
        for i in range(1,33):
            if self.search(str(ipcalc.Network(f'{ip}/{i}').netmask())):
                return True
        return False
        
china_ip = ChinaIp()
china_ip.load()
print('223.70.163.83' in china_ip)

这个算法看起来没啥毛病，但实际测试中速度比第二种慢了很多，耗时的地方在比较时必须循环所有 n，而二分法可以快速的排除不可能的部分。

对于这种情况，有两种优化方法：

1. 随机 n 的列表

class ChinaIp(object):

    ...
    
    def __contains__(self, ip):
        l = list(range(1, 33))
        random.shuffle(l)
        for i in l:
            if self.search(str(ipcalc.Network(f'{ip}/{i}').netmask())):
                return True
        return False

这种方法在测试中，时间减少了一半多。

2. 排除不会出现的 n

class ChinaIp(object):
    def __init__(self):
        ...
        self.mask_list = []
    ...

    def insert(self, cidr):
        network = ipcalc.Network(cidr)
        self.data[str(network.netmask())] = True
        self.mask_set.add(network.mask)

    def __contains__(self, ip):

        for i in self.mask_set:
            netmask = str(ipcalc.Network(f'{ip}/{i}').netmask())
            if netmask in self.data:
                return True
        return False

这样优化后速度和第二种持平，不过实际应用中还需要根据 ip 列表的情况来判断需要用哪种。