算法题实战 — 大规模黑名单IP匹配

算法是许多IT公司面试时很重要的一个环节，但也有很多人抱怨实际工作中很少碰到，实用性不高。本文描述了我们公司在面试时常用的一道题目，虽然底层用了非常简单的算法，但却是具体工作中比较容易见到的场景：大规模黑名单 ip 匹配。同时用我们在安全网关中开发的例子来做些验证。

一、问题和场景

问题：有海量的 ip 网段名单，需要快速的验证某一个 ip 是否属于其中任意一个网段。

这其实是一个比较普遍的问题，以我们的安全网关为例，至少在以下场景中有需要:

场景一：单纯的黑白名单匹配

对于网关来说，黑白名单匹配是基本功能：

内部 ip 需要白名单 bypass。按照公司的规模和地域所在，这里可能会有大量的白名单。

攻击 ip 需要黑名单 block。目前的互联网，各种扫描和攻击还是比较猖獗的，可以很容易的获得大量黑名单 ip，需要进行实时封禁。

类似的可以参考 nginx 的黑名单功能,通过 deny 语句 "deny 192.168.1.0/24;" 可以定义一批 ip 网段，用来做访问控制。

场景二：真实ip获取

真实 ip 获取对有些网站来说其实是一个比较麻烦的问题，因为流量可能有不同的来源路径：

浏览器-->网关。这种直接取 remote_address, 即 tcp 的远端地址;

浏览器-->lb-->网关。中间可能有别的负载均衡，一般靠 XFF 头来识别;

浏览器-->cdn-->lb-->网关。有些流量走了 cdn 或者云 waf，需要对 XFF 头特别处理，识别出 cdn 的 ip;

浏览器-->cdn-->lb-->...-->lb-->网关。实际场景中，受到重定向，内部多层网关的影响，可能会有比较复杂的场景。

类似的可以参考 nginx 的真实 ip 功能, 原理也比较简单，通过类似 "set_real_ip_from 192.168.1.0/24;" 的语句可以设置内部 ip 名单，这样在处理 XFF 头的时候，从后往前找，递归模式下寻找第一个不是内部 ip 的值，即真实 ip。这就回归到本文的问题上来。

场景三：流量标注

这部分功能常由后端的业务模块自行实现，我们在开发产品中希望能在请求进来的时候做一些自动标注，减轻后端的负担，比较有用的如：

ip 归属地判断。ip 归属地一般是由数十万网段组成的索引，需要进行快速判断;

基站标注。目前大量使用 4g 上网，所以基站 ip 必须小心对待，而基站数据也是大量的 ip 网段;

云服务器标注。目前较多的攻击来自于云服务器，这些标注对后台的安全和风控业务有协助。云服务器列表也通过海量 ip 网段列表来展现。

以上场景描述了海量 ip 网段列表匹配的一些应用场景，还是比较容易碰到的。

二、算法描述

算法一: hashmap

绝大部分人第一反应是通过 hashmap 来做匹配，理论上可以实现(将网段拆分为独立的 ip)，但基本不可用：

网段的掩码不一定是24位，可以是32内的任一数字，所以如果要保证普遍性的话，需要完全拆成独立的 ip;

哪怕是真实 ip 获取这样常见的场景，我们在客户这边碰到，由于使用了多家 cdn 厂家，cdn 网段有1300+，假设都为24位掩码的 c 类地址，也会有332800+的 ip，做成 hashmap 将是大量的内存开销;

由于网关一般是通过多进程或者多实例做水平扩展的，这个内存浪费也会成倍增加。

所以 hashmap 的方式所以查询高效，但在实现层来说不太可行。

算法二：对网段列表进行顺序匹配

目前可以看到一些开源的实现大都采用这种方式，比如场景段落描述的 nginx 两个功能模块，可以再 accss 模块和 realip 模块发现都是将配置存储为 cidr 列表，然后逐个匹配;另外一个实现是 openresty 的 lua-resty-iputils 模块，这个代码看起来比较直观些：

local function ip_in_cidrs(ip, cidrs) 

 local bin_ip, bin_octets = ip2bin(ip) 

 if not bin_ip then 

 return nil, bin_octets 

 end 

 for _,cidr in ipairs(cidrs) do 

 if bin_ip >= cidr[1] and bin_ip <= cidr[2] then 

 return true 

 end 

 end 

 return false 

end 

开源的实现在应付绝大多数简单场景足够可用，但后面的测试可以看到，当ip网段数量上升的时候，性能还是欠缺。

算法三：二分查找

实际的算法其实很简单，二分查找即可，假设这些 ip 网段都是互不相邻的，采用类似 java 的二分查找即可，如图：