CIDR匹配 域名匹配

所有完整实现代码:match

CIDR

我们知道cidr对ip匹配时,只要cidr的mask长度的前几位与要匹配的ip相同,则可以说匹配成功.

1
2
3
4
5
假设有一个cidr为128.0.0.1/24
转换为二进制 1000 0000.0000 0000.0000 0000.0000 0001/24
可以知道要匹配ip的前24为与cidr的前24(1000 0000.0000 0000.0000 0000)位相同则匹配成功
假设有一个ip 128.0.0.128 二进制为 1000 0000.0000 0000.0000 0000.1000 0000
可以看到前24位与cidr相同 则匹配成功

域名

域名就比较简单了,直接按点分割就行了

前缀树

通过上述规则 我们可以使用前缀树实现CIDR对ip的匹配

1
2
3
4
5
6
7
8
        root
/ \
0 1
/ \ / \
0 1 0 1
/
当ip匹配到此处,此处已无任何子树,且是某一cidr的末尾时则匹配成功
若此处节点为null(golang为nil)且不是某一cidr的末尾时则匹配失败

域名的前缀树相同,只不过域名不再是只有0和1,而且在匹配的时候还需要跳过前面的那些前缀.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
        +---------+
| root |
+---------+
/ / \
facebook google twitter ...
/ / \ \
com com mail com ...
\
com

在对域名匹配时
如对 www.play.google.com匹配:
没有www 跳过
没有play 跳过
有google 继续
有com 且 域名已为最后一个节点 -> 判断trie中是否为最后的一个子树 -> 是 -> 匹配成功

这里有一个明显的问题
true比如我们同时插入了music.126.com和163.com
true然后我们需要查询music.163.com是否被匹配
true是不是发现了问题,无法被匹配,因为包含music,我们会匹配到music.126.com这条线,而不是163.com

这里有个很简单的解决方法,就是把域名倒过来插入,倒过来匹配,就跟JAVA包名那样
+---------+
| root |
+---------+
/
com ...
/ \
163 126 ...
\
music

这样就能被正确匹配了,而且会缩短时间,不会去完整匹配整个域名,只匹配后面有的就行了

trie树类似上述结构

trie树节点 我们可以这样写
+node
|- bool(判断是否匹配成功,是否是某一cidr的末尾)
|- left(左树代表0)
|- right(右树代表1)

域名的这样写
+node
|- bool
|- domainNode
|- next

使用golang实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type node struct {
isLast bool
left *node
right *node
}

type TrieTree struct {
root *node
}

func NewTrieTree() *TrieTree {
truereturn &TrieTree{
truetrueroot: &node{},
true}
}

对每一个CIDR的插入
注意: 此处传入的CIDR为CIDR前mask位的二进制形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (trie *TrieTree) Insert(str string) {
truenodeTemp := trie.root
truefor i := 0; i < len(str); i++ {
truetrue// 1 byte is 49
truetrueif str[i] == 49 {
truetruetrueif nodeTemp.right == nil {
truetruetruetruenodeTemp.right = new(node)
truetruetrue}
truetruetruenodeTemp = nodeTemp.right
truetrue}
truetrue// 0 byte is 48
truetrueif str[i] == 48 {
truetruetrueif nodeTemp.left == nil {
truetruetruetruenodeTemp.left = new(node)
truetruetrue}
truetruetruenodeTemp = nodeTemp.left
truetrue}
truetrueif i == len(str)-1 {
truetruetruenodeTemp.isLast = true
truetrue}
true}
}

对ip的匹配
注意: 此处传入的ip为ip的二进制形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (trie *TrieTree) Search(str string) bool {
truenodeTemp := trie.root
truefor i := 0; i < len(str); i++ {
truetrueif str[i] == 49 {
truetruetruenodeTemp = nodeTemp.right
truetrue}
truetrueif str[i] == 48 {
truetruetruenodeTemp = nodeTemp.left
truetrue}
truetrueif nodeTemp == nil {
truetruetruereturn false
truetrue}
truetrueif nodeTemp.isLast == true {
truetruetruereturn true
truetrue}
true}
truereturn false
}