算法是很多IT公司面试中很重要的一环，但是很多人抱怨在实际工作中遇到的很少，实用性不高。这篇文章描述了我们公司面试中常用的一个话题。虽然在底层使用了一个很简单的算法，但是在具体工作中是比较容易看到的场景：大规模的黑名单ip匹配。同时用我们在安全网关中开发的例子做一些验证。1、问题与场景：IP网段列表数量众多，需要快速验证某个IP是否属于其中的某个网段。这其实是一个比较普遍的问题。以我们的安全网关为例，至少在以下场景下是需要的：场景一：简单的黑白名单匹配对于网关来说，黑白名单匹配是一个基本功能：内网ip需要白名单绕过。根据公司的规模和地理位置，这里可能会有大量的白名单。攻击ip需要黑名单拦截。现在的互联网，各种扫描和攻击还是比较猖獗，很容易获取到大量的黑名单ip，需要实时封禁。同样可以参考nginx的黑名单功能。通过deny语句“deny192.168.1.0/24;”可以定义一批ip网段进行访问控制。场景二：获取真实ip获取真实ip对于一些网站来说其实是一个比较麻烦的问题，因为流量可能有不同的来源路径：浏览器-->网关。这里直接取remote_address，即tcp的远程地址；浏览器-->lb-->网关。中间可能还有其他的负载均衡，一般通过XFF头标识；浏览器-->cdn-->lb-->网关。部分流量经过cdn或云waf，需要对XFF头进行特殊处理，识别cdn的ip；浏览器-->cdn-->lb-->...-->lb-->网关。在实际场景中，受重定向和内部多层网关的影响，可能会有更复杂的场景。同样可以参考nginx的realip功能，原理比较简单。可以通过类似于“set_real_ip_from192.168.1.0/24;”的语句来设置内部ip列表，这样在处理XFF头的时候，可以从后往前查找，递归方式下，寻找第一个值不是内部ip，也就是真实ip。这就回到了本文的问题。场景三：流量标签功能往往由后端业务模块实现。我们希望在产品开发过程中有请求进来的时候做一些自动标注，减轻后端的负担。比较有用的比如：ip归属判断。ip归属地一般是由几十万个网段组成的指标，需要快速判断；基站有标记。目前普遍使用4G上网，所以基站的IP一定要慎重对待，基站的数据也是大量的IP网段；由云服务器标记。目前更多的攻击来自于云服务器，这些注解对于后台的安全和风控业务是有帮助的。云服务器列表也是通过海量ip网段列表来展示的。以上场景描述了匹配大量IP网段列表的一些应用场景，比较容易遇到。2.算法说明算法一：hashmap大部分人的第一反应是用hashmap做匹配，理论上可以实现（将网段拆分成独立的ip），但基本无法实现：网段的掩码不一定是24位，可以是32以内的任意数字，所以如果要保证通用性，需要彻底拆成一个独立的ip；即使是真实ip获取这样的常见场景，我们在客户端也遇到过，因为使用了很多cdn厂商，有1300+的cdn网段。假设都是24位掩码的C类地址，那么也会有332800+个ip。制作哈希图会产生大量内存开销；因为网关一般是通过多进程或者多个实例横向扩展的话，这种内存浪费也会成倍增加。所以hashmap的方式对于查询是高效的，但是在实现层面是不可行的。算法二：顺序匹配网段列表目前我们看到一些开源实现大多采用这种方式。比如场景段落中描述的nginx的两个功能模块，可以在accss模块和realip模块中找到，将配置存储为cidrList，然后一一匹配；另一个实现是openresty的lua-resty-iputils模块，这段代码看起来更直观：[2]thenreturntrueendreturnfalseend开源的实现对于大多数简单的场景来说已经足够了，但是后来的测试表明当IP网段数量增加的时候，性能还是有所欠缺。算法三：二分查找实际算法其实很简单，就是二分查找，假设这些ip网段不相邻，就用类似java的二分查找即可，如图：假设有A，B,C,D四个不相邻的ip网段，每个网段可以转化为两个数：起始ip的整数表示和结束ip的整数表示；例如，0.0.0.0/24可以转换为[0,255]。这样4个网段就转换成8个数，可以排序了。由于网段不相邻，所以肯定是如图所示一个ip段后面跟着另一个ip段的情况。这个匹配算法会比较简单：将查询到的ip转化为数字，在数组中进行二分查找；参考java的二进制实现，当查询命中时，直接返回命中数的索引；当查询未命中时，返回一个负数，其绝对值表示其插入位置（具体实现需要稍做改动，此处忽略）；如果第二步返回值为正，恭喜你，找到了，直接命中；如果第二步的返回值为负数，插入坐标为奇数（1,3,5,7），说明插入点正好在一个网段内，表示命中；如果第二步返回负数，则插入坐标为偶数（0,2,4,6,8），说明插入点正好在两个网段之间，说明这个ip不匹配所有网段；证书结束了。所以整个算法很简单，但是这里假设网段不相邻，这个容易被忽略，下面做一些简单的解释。任意两个网段A和B可能存在三种关系：完全不相邻。A和B没有任何重复的部分。包含，即A包含B或B包含A。这种情况可以在数据预处理时发现并消除（只保留大网段）。A和B相交，但不包含。即存在两个网段相互交错的情况。下图表明这种情况并非如此。上图描述了任意两个网段：“*”表示屏蔽两个网段，共32位，其中子网部分，前X个连续位相同，第一个网段剩余Y位，第二个网段还剩Z位，所以：假设Y==Z==0，表示两个网段完全相等，否则Y==0&&Z!=0，表示第一个网段包含第二网段；Y!=0&&Z==0，则第二个网段更大Y!=0&&Z!=0，这是图上的直观表示，因为网段中的ip只能是*部分，因此，两个网段不可能有相同的ip，因为至少中间有几位是不一样的。因此，如果对原始数据进行一些预处理，二分查找是一种安全有效的方式。三、测试数据最近手机比较多，所以我们跟风跑分：测试使用RaspberryPi3ModelB，4核1.2GHzCPU，1G内存。通过wrk进行50个连接30秒的性能测试。测试1：BenchmarkRunning30Stest@http：//10.0.0.5/12threadsand50connectionsthreadstatsavgstdevmax+/stdevlatency6.54ms4.80mms194.75MS99.299.299.2999.29;MBreadRequests/sec:7373.42Transfer/sec:1.35MB测试二：10000个黑名单+hashmapRunning30stest@http://10.0.0.5/block_ip_1w12threadsand50connectionsThreadStatsAvgStdevMax+/-StdevLatency7.75ms2.34ms94.11ms85.57%Req/Sec512.7268.86780.0074.28%LatencyDistribution50%7.21ms75%8.36ms90%10.63ms99%14.07ms184298requestsin30.09s,32.16MBreadRequests/sec:6125.35Transfer/sec:1.07MBTestThree:10000ModuleSearch-Blacklist-testluuts@http://10.0.0.5/block_iputils_1w12threadsand50connectionsThreadStatsAvgStdevMax+/-StdevLatency162.93ms100.27ms1.96s95.22%Req/Sec27.4712.28150.0066.46%LatencyDistribution50%155.88ms75%159.40ms90%161.54ms99%670.13ms9164requestsin30.09s,1.60MBreadSocketsecrors:connect0,time4.Refe1:connect0,timeRequest1:trans1,writeR/SEC：54.41KB测试：10000个+二分+二分查找查找查找查找查找查找查找%8.45ms75%10.94ms90%12.55ms99%18.58ms153892requestsin30.10s,26.85MBreadRequests/sec:5112.69Transfer/sec:0.89MB?通过测试数据可以看出二分查找可以达到接近基于hash的性能，但是内存消耗等会少很多；而简单的顺序遍历会带来一个数量级的性能下降【本文为专栏组织《奇安科技》原创文章，转载请微信联系原作者♂(bigsec)】点此查看看作者更多好文章
