Golang

路由匹配方式比较

前言

做权限验证时，需要对传入的路由与配置的路由进行匹配，判断是否对API有权限。这里比较通过字典树和正则匹配这两种实现方式的性能差异

权限信息

里面主要包含roleId、url、method

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

{
    "role_id": 5,
    "role_name": "超级管理员",
    "apis": [
        {
            "name": "a",
            "url": "github.com/go-redis/:str/redis/v8",
            "method": "GET"
        }
    ]
}

字典树的实现方式

1
2
3
4
5
6

// 获取一个对象
roleTrieTest = NewRoleTrie()
// 根据权限信息生成树
roleTrieTest.Generate(*roleInfo)
// 查找，符合条件返回true
roleTrieTest.Search(roleId, url, urlMethod)

正则匹配的实现方式

1
2
3
4
5
6

// 获取一个对象
roleTrieTest = NewRoleTrie()
// 根据权限信息生成role拥有的URL正则表达式列表
roleTrieTest.Generate(*roleInfo)
// 查找，符合条件返回true
roleTrieTest.Search(roleId, url, urlMethod)

Bench 测试代码如下

测试只针对查找过程，不包含生成查找信息。

 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

func TestMain(m *testing.M) {
	roleInfo := new(RoleInfo)
	_ = json.Unmarshal([]byte(apiStr), roleInfo)

	roleTrieTest = NewRoleTrie()
	roleTrieTest.Generate(*roleInfo)

	roleRegTest = NewRegexp()
	roleRegTest.GenerateReg(*roleInfo)

	m.Run()
}

func Benchmark_TrieSearch(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if roleTrieTest.Search(5, url1, http.MethodGet) != true {
			b.Fatal("Benchmark_TrieSearch url1 has failed")
		}
		if roleTrieTest.Search(5, url2, http.MethodPost) != false {
			b.Fatal("Benchmark_TrieSearch url2 has failed")
		}
	}
}

func Benchmark_RegSearch(b *testing.B) {
	for i := 0; i < b.N; i++ {
		if roleRegTest.Search(5, url1, http.MethodGet) != true {
			b.Fatal("Benchmark_RegSearch url1 has failed")
		}
		if roleRegTest.Search(5, url2, http.MethodPost) != false {
			b.Fatal("Benchmark_RegSearch url2 has failed")
		}
	}
}

测试结果

性能上的差别大概在210倍左右。 其中RegSearch方法的性能主要在正则匹配上损耗，TrieSearch则主要在对入参的URL进行字符串分割

1
2
3
4
5
6
7
8
9

go test -bench . -benchmem
goos: windows
goarch: amd64
pkg: CodeCollection/search-path
cpu: AMD Ryzen 5 3600X 6-Core Processor
Benchmark_TrieSearch-12          3217045               371.9 ns/op           160 B/op          2 allocs/op
Benchmark_RegSearch-12             15277             78974 ns/op           85607 B/op        534 allocs/op
PASS
ok      CodeCollection/search-path      3.856s

完整代码

完整代码