算法是許多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 的二分查找即可，如圖：

假設有 A, B, C, D 四個互不相鄰的 ip 網段，每個網段可以轉化為兩個數字：起始ip的整型表示和終止 ip 的整型表示;比如 0.0.0.0/24 可以轉化為 [0, 255]。這樣四個網段轉化為 8 個數字，可以進行排序，由于網段是互不相鄰的，所以一定是圖上這種一個 ip 段接一個 ip 段的情形。這樣匹配的算法會比較簡單：

• 將被查詢 ip 轉化為數字，并在數組中進行二分查找;
• 參考 java 的二分實現，當查詢命中時，直接返回命中數字的index;當查詢未命中時，返回一個負數，其絕對值表示了其插入位置(具體實現需略作變化，這里略過不計);
• 第二步如果返回值為正數，恭喜你，找到了，直接命中;
• 第二步如果返回的為負數，同時插入坐標為奇數(1, 3, 5, 7)，說明插入點正好在一個網段之內，說明命中;
• 第二步如果返回的為負數，同時插入坐標為偶數(0, 2, 4, 6, 8)，說明插入點正好在兩個網段之間，說明此 ip 與所有網段都不命中;
• 證畢收工。

所以整個算法非常簡單，不過這里假設了網段之間是互不相鄰的，這個很容易被忽視掉，下面做一些簡單說明。

任意兩個網段 A 和 B，可能有三種關系：

• 完全不相鄰。A 和 B 沒有任何重復的部分。
• 相包含，即 A 包含 B 或 B 包含 A。這種情形在數據預處理的時候可以發現并排除掉(只保留大的網段)。
• A 和 B 相交，但并不包含。即兩個網段存在相互交錯的情形，下面通過圖形說明此種情況不成立。

上圖描述了任意兩個網段：

• "*"表示掩碼
• 兩個網段，共32位，其中子網部分，前面 X 個連續 bit 是相同的
• 第一個網段剩余 Y 個 bit，第二個網段剩余 Z 個 bit

所以：

• 假設 Y == Z == 0, 表示兩個網段完全相等，否則
• Y == 0 && Z != 0， 說明第一個網段包含第二個網段;Y != 0 && Z == 0, 則第二個網段更大
• Y != 0 && Z != 0，就是圖上的直觀表示，由于網段中的 ip 只能是*號部分的變化，所以兩個網段不可能有相同的 ip，因為中間至少有幾位是不同的

因此，如果對原始數據進行一定的預處理，二分查找是安全有效的方式。

三、測試數據

最近手機出的有點多，我們也跟風跑個分：

• 測試采用 Raspberry Pi 3 Model B, 4核 1.2GHz CPU, 1G 內存。
• 通過 wrk 進行持續30s，50個連接的性能測試。

測試一：基準測試

Running 30s test @ http://10.0.0.5/ 
12 threads and 50 connections 
Thread Stats Avg Stdev Max +/- Stdev 
Latency 6.54ms 4.80ms 194.75ms 99.29% 
Req/Sec 617.22 56.76 1.05k 80.42% 
Latency Distribution 
50% 6.22ms 
75% 6.99ms 
90% 7.78ms 
99% 10.74ms 
221915 requests in 30.10s, 40.62MB read 
Requests/sec: 7373.42 
Transfer/sec: 1.35MB 

測試二：10000個黑名單+hashmap

Running 30s test @ http://10.0.0.5/block_ip_1w 
12 threads and 50 connections 
Thread Stats Avg Stdev Max +/- Stdev 
Latency 7.75ms 2.34ms 94.11ms 85.57% 
Req/Sec 512.72 68.86 780.00 74.28% 
Latency Distribution 
50% 7.21ms 
75% 8.36ms 
90% 10.63ms 
99% 14.07ms 
184298 requests in 30.09s, 32.16MB read 
Requests/sec: 6125.35 
Transfer/sec: 1.07MB 

測試三：10000個黑名單+lua-resty-utils 模塊順序查找

Running 30s test @ http://10.0.0.5/block_iputils_1w 
12 threads and 50 connections 
Thread Stats Avg Stdev Max +/- Stdev 
Latency 162.93ms 100.27ms 1.96s 95.22% 
Req/Sec 27.47 12.28 150.00 66.46% 
Latency Distribution 
50% 155.88ms 
75% 159.40ms 
90% 161.54ms 
99% 670.13ms 
9164 requests in 30.09s, 1.60MB read 
Socket errors: connect 0, read 0, write 0, timeout 11 
Requests/sec: 304.52 
Transfer/sec: 54.41KB 

測試四：10000個黑名單+二分查找

Running 30s test @ http://10.0.0.5/block_ipcidr_bin_1w 
12 threads and 50 connections 
Thread Stats Avg Stdev Max +/- Stdev 
Latency 9.60ms 6.78ms 196.80ms 97.53% 
Req/Sec 427.92 82.80 0.89k 60.15% 
Latency Distribution 
50% 8.45ms 
75% 10.94ms 
90% 12.55ms 
99% 18.58ms 
153892 requests in 30.10s, 26.85MB read 
Requests/sec: 5112.69 
Transfer/sec: 0.89MB 

☞ 通過測試數據，可以看到二分搜索可以達到接近于基于 hash 的性能，但內存消耗等會少很多;而簡單的順序遍歷會帶來數量級的性能下降。

【本文是51CTO專欄機構“豈安科技”的原創文章，轉載請通過微信公眾號(bigsec)聯系原作者】

戳這里，看該作者更多好文