Proposal for amending domain matching logic

[Vigilans]

当前V2Ray版本

4.27.0

使用场景

域名匹配（路由、DNS）

看到的不正常的现象是什么？

这个Issue由 v2fly/domain-list-community#91 (comment) 中的现象引出：

我先尝试阅读 V2Ray DNS 部分的源码，看看能不能找出规则处理的优先级的 bug。找到的话，先修优先级 bug，这样通过 DNS 配置就可以避免用 V2Ray 做网关当透明代理时的解析问题。

这个是什么

"dns": {
  "servers": [
    {
      "address": "https+local://dns.alidns.com/dns-query",
      "domains": [
        "geosite:cn",
        "geosite:google@cn",
        "full:fonts.googleapis.com"
      ]
    },
    {
      "address": "https://1.1.1.1/dns-query",
      "domains": [
        "geosite:geolocation-!cn"
      ]
    },
    "223.5.5.5"
  ]
}

由于现在域名 font.googleapis.com 同时在 google@cn 和 geolocation-!cn 中。

当 V2Ray 做网关或者透明代理时，使用上面这样的 DNS 配置，解析 font.googleapis.com 会大概率使用 1.1.1.1，当这个解析失败，才会使用 dns.alidns.com

[Vigilans]

先阐述一下当前Domain Matcher的匹配过程：

1. 欲匹配域名的一方调用(g *MatcherGroup) Match(pattern string) uint32；
2. MatcherGroup 依照以下顺序调用所有保存的matchers：FullMatcher（完全匹配）、DomainMatcher（子域名匹配）、OtherMatchers（正则匹配等），只要某Matcher返回了一个有效结果，整个MatcherGroup立即返回该结果。
3. 调用方收到结果后，根据结果分发下一步流程。

其中：

1. FullMatcher与DomainMatcher是多个Matcher的集合，各自使用Key-Value Map与Trie树将所有Matcher组织起来。使用这两个聚合的Matcher匹配时，均只会返回一个结果。
2. OtherMatchers是简单的Matcher数组，通过遍历进行匹配，只返回第一个匹配到的结果。
3. DomainMatcher的各结点只存储一个整数值，因此最多保存一个记录，后插入的域名会将之前的同域名规则覆盖。

[Vigilans]

参考 v2fly/domain-list-community#91 (comment) 中的配置：

"dns": {
  "servers": [
    {
      "address": "https+local://dns.alidns.com/dns-query",
      "domains": [
        "geosite:cn",
        "geosite:google@cn",
        // "full:fonts.googleapis.com" // 这里注释掉了，因为full的优先级应该是高一些的
      ]
    },
    {
      "address": "https://1.1.1.1/dns-query",
      "domains": [
        "geosite:geolocation-!cn"
      ]
    },
    "223.5.5.5"
  ]
}

现在可以解释Issue中现象出现的原因了：

1. [1.1.1.1, geolocation-!cn]中的fonts.googleapis.com条目覆盖了[dns.alidns.com, google@cn]中的相同条目。
2. 匹配时，Matcher只返回了1.1.1.1服务器的索引2，由此优先使用该DNS服务器。
3. 1.1.1.1解析失败后，fallback到默认的由上至下顺序查询，由此使用dns.alidns.com查询。

以上十分需要注意的是，1.1.1.1匹配失败后并不是通过geosite:google@cn匹配成功才查询dns.alidns.com的，而是通过默认的数组遍历查询的，因为：

• MatcherGroup只会返回一条匹配记录，因此内置DNS对于domain的优先查询最多也只能做一次；
• [1.1.1.1, geolocation-!cn]的规则插入后，原来关于dns.alidns.com的规则在内存中已经不存在了。

因此若在dns.alidns.com前面再插入一个DNS服务器，则会更优先查询那个。

对于 #88 (comment) 中提到的路由模块匹配行为符合预期，是因为路由模块对于DomainMatcher（Trie树）的建立是per-rule的，因此后面的geosite规则不会影响到当前geosite规则的匹配。

[Vigilans]

修正方法提案

综合以上描述，可以总结出当前的域名匹配的两个重要特征：MatcherGroup只返回最先匹配到的记录、DomainMatcher只保留最后插入的记录。

因此修正方案有以下两个方向：

返回最先匹配的记录，保留最先插入的记录

这个方案直接解决了 v2fly/domain-list-community#91 (comment) 中的问题，同时改动极小（大约三行），也即当新记录插入时，若结点上已有记录，则抛弃新记录。

返回所有匹配的记录，保留所有插入的记录

这个方案改变MatcherGroup的实现，使其由返回一个记录变成返回一组纪录。同时，修改FullMatcher与DomainMatcher的实现，使其对应条目/节点变为保存一个数组，当有新纪录插入时，不覆盖而是扩充这个数组。

这个方案的优点：

• 优化了DNS的匹配能力。此前对于特殊规则的匹配最多只能执行一次，现在MatcherGroup返回一个数组后，则可以按序遍历数组，轮流查询多个优先匹配的DNS。同时也解决了上面的问题。
• 为优化未来Routing的域名匹配提供可能。目前路由规则里DomainMatcher（Trie树）的建立是per-rule的，每次经过路由规则都要将域名切割后再从根节点开始查询。该优化为将它们整合在一起提供可能，让域名在路由中也只用在Trie树上匹配一次。更进一步，或许还可以为路由规则设计一个计算图，优化每次路由过程的匹配路径

这个方案的缺点：

• 潜在的内存问题。将条目/节点存储的值从一个uint32改为uint32[]带来了内存消耗的提升，同时Slice作为动态数组似乎降低了局部性（不是很熟悉Go的实现）。
• 潜在的性能问题。此前只返回一个记录时，MatcherGroup可以找到记录后尽早退出。改成返回一个数组后则必须要尝试完所有的Matcher（Full, Domain, Others）。此前记录存储的整数赋值变成了切片append也可能引入潜在的overhead。

两种方案都会引入对DNS匹配规则的breaking change（虽然大概很少会有人利用后插入的优先匹配这个feature/bug）。

[Vigilans]

在本机上，原版实现与修改实现（返回所有记录）的Benchmark

原版实现

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           29968170                40.1 ns/op
BenchmarkFullMatcherGroup-6             100000000               11.5 ns/op
BenchmarkMarchGroup-6                   28197316                42.6 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.660s

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           29951710                40.1 ns/op
BenchmarkFullMatcherGroup-6             100000000               11.5 ns/op
BenchmarkMarchGroup-6                   28202142                42.6 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.659s

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           26360697                40.0 ns/op
BenchmarkFullMatcherGroup-6             100000000               11.5 ns/op
BenchmarkMarchGroup-6                   28160061                42.6 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.517s

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           29955906                40.2 ns/op
BenchmarkFullMatcherGroup-6             100000000               11.5 ns/op
BenchmarkMarchGroup-6                   28172674                43.9 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.701s

修改后实现

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           29703830                40.3 ns/op
BenchmarkFullMatcherGroup-6             91364202                13.1 ns/op
BenchmarkMarchGroup-6                   26097846                51.1 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.841s

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           29734064                40.3 ns/op
BenchmarkFullMatcherGroup-6             91500662                13.1 ns/op
BenchmarkMarchGroup-6                   26092104                45.9 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.708s

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           29723420                40.3 ns/op
BenchmarkFullMatcherGroup-6             91254849                13.1 ns/op
BenchmarkMarchGroup-6                   26092087                46.0 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.706s

$ go test -bench=.
goos: linux
goarch: amd64
pkg: v2ray.com/core/common/strmatcher
BenchmarkDomainMatcherGroup-6           29067766                41.4 ns/op
BenchmarkFullMatcherGroup-6             91259714                13.1 ns/op
BenchmarkMarchGroup-6                   25665771                47.3 ns/op
PASS
ok      v2ray.com/core/common/strmatcher        3.729s

[Vigilans]

@Loyalsoldier

[Loyalsoldier]

@Vigilans 哆啦 A 梦 😄 🎉

[kslr]

首先，路由应该设定是顺序匹配。
“返回所有匹配的记录，保留所有插入的记录” 下一步可以添加 Trie

[Loyalsoldier]

I think you should file a PR.

[Vigilans]

@Loyalsoldier I've created a PR adopting the second choice: preserving and returning array of all matches. Yesterday I purposely kept back my PR in order not to incline towards any of the two choices in this issue.

[Loyalsoldier]

@Vigilans Excellent job! 🎉

[Vigilans]

Domain Matcher还存在另外一个问题。在添加结点的代码中：

v2ray-core/common/strmatcher/domain_matcher.go

Lines 28 to 31 in 8b4ba03

	if len(current.values) > 0 {
	// if current node is already a match, it is not necessary to match further.
	return
	}

不太清最初的设计目的是什么，这段代码使得域名级数最少的优先匹配，而其他级数多的甚至不会加入进Trie树中。也即尝试往DomainMatcher中添加以下三条规则时：

domain:azure.com
domain:cloudapp.azure.com
domain:eastasia.cloudapp.azure.com

只有domain:azure.com会被记录，匹配时只会返回domain:azure.com对应的规则，后两者完全无效。

实际使用中，一般是对于一级域名使用一种通用规则，再对某些特定的二级及以上的域名设置更细致的规则。按这种模式一种修正方法是：

• 添加记录时，移除路径上某结点是否已有旧记录（一级域名，etc）的检查。
• 匹配域名时，保存路径上所有有值的结点的记录。
• 将保存的记录数组逆序拼接，从而使得级数更深的域名优先匹配，但子域名的规则失败后仍会使用更通用域名的规则。

[Loyalsoldier]

@Vigilans

"dns": {
  "servers": [
    {
      "address": "https+local://dns.alidns.com/dns-query",
      "domains": [
        "regex:apis\\.us$",
        "keyword:apis",
        "domain:googleapis.com",
        "domain:com",
        "full:www.baidu.com"
      ]
    },
    {
      "address": "https://1.1.1.1/dns-query",
      "domains": [
        "keyword:apis",
        "domain:googleapis.com",
        "full:fonts.googleapis.com",
        "full:www.baidu.com",
        "domain:example.com"
      ]
    }
  ]
}

做完以上修改后，DNS 匹配逻辑是不是下面这样？

总体优先级由上到下，且 full > domain > regex = keyword，且 domain 类型中，子域名更详细的，优先级更高。

使用上面的 DNS JSON 配置，

• www.baidu.com 会命中 dns.alidns.com，因为优先级由上到下，且 full:www.baidu.com 优先级比 domain:com 高
• fonts.googleapis.com 会命中 1.1.1.1，因为 full:fonts.googleapis.com 优先级比 domain 类型高；
• example.googleapis.com 会命中 dns.alidns.com，因为优先级由上到下；
• testapis.us 会命中 dns.alidns.com，因为 regex:apis\\.us$，且优先级由上到下，且 regex 类型和 keyword 类型相同优先级
• example.com 会命中 1.1.1.1，因为同是 domain 类型，domain:example.com 比 domain:com 更详细；
• 如果命中的 DNS 查询 IP 地址失败，则从最上面一个 DNS 重新开始查起

[Vigilans]

@Loyalsoldier 命中的 DNS 在所有命中结果全部查询失败后，则再从最上面的 DNS 重新开始查起。

我按你的配置写了测试代码，打印了一下匹配的中间过程，结果如下（Matcher 的标号与参考的 DNS JSON 配置一一对应，可以参照查阅标号对应的原 Matcher 的内容）：

DNS 0 manages matchers: [1 2 3 4 5]
DNS 1 manages matchers: [6 7 8 9 10]

www.baidu.com
Full Matcher  : [5 9]    -> ["full:www.baidu.com"(0), "full:www.baidu.com"(1)]
Domain Matcher: [4]      -> ["domain:com"(0)]
Matcher result: [5 9 4]
Matched DNS   : [0 1 0]

fonts.googleapis.com
Full Matcher  : [8]      -> ["full:fonts.googleapis.com"(1)]
Domain Matcher: [3 7 4]  -> ["domain:googleapis.com"(0), "domain:googleapis.com"(1), "domain:com"(0)]
Substr Matcher: 2        -> "keyword:apis"(0)
Substr Matcher: 6        -> "keyword:apis"(1)
Matcher result: [8 3 7 4 2 6]
Matched DNS   : [1 0 1 0 0 1]

example.googleapis.com
Full Matcher  : []       -> []
Domain Matcher: [3 7 4]  -> ["domain:googleapis.com"(0), "domain:googleapis.com"(1), "domain:com"(0)]
Substr Matcher: 2        -> "keyword:apis"(0)
Substr Matcher: 6        -> "keyword:apis"(1)
Matcher result: [3 7 4 2 6]
Matched DNS   : [0 1 0 0 1]

testapis.us
Full Matcher  : []       -> []
Domain Matcher: []       -> []
Regexp Matcher: 1        -> "regex:apis\\.us$"(0)
Substr Matcher: 2        -> "keyword:apis"(0)
Substr Matcher: 6        -> "keyword:apis"(1)
Matcher result: [1 2 6]
Matched DNS   : [0 0 1]

example.com
Full Matcher  : []       -> []
Domain Matcher: [10 4]   -> ["domain:example.com"(1), "domain:com"(0)]
Matcher result: [10 4]
Matched DNS   : [1 0]

可以看到 DNS 的优先级匹配行为与你的描述一致。

一个值得注意的现象是，由于两个 DNS 各自都设置了匹配范围相互覆盖的 Matcher，因此在 Matched DNS 中常常出现一个 DNS 被反复匹配的现象。这可能会导致该 DNS 在 Priority Matching 过程中被反复查询（如果前面的查询失败的话）。

个人认为这个行为可以保留，不需要修正，原因是：

• 修正的方法无非是数组去重，这会为 DNS 查询带来额外的 overhead，而大多数人的配置本是不会出现这种现象的。
• 这种现象增加了一次 DNS 查询可能的重试次数，一定程度上缓解了本来很稳定的 DNS 服务器偶然查询失败的问题。

[Loyalsoldier]

@Vigilans

想问一下，在 debug 级别的 log 中打印上面这个匹配流程，是否容易实现？这样的话，就不需要用户猜了。如果需要大改的话，就算了。

[Vigilans]

@Loyalsoldier 只打印标号的话，打印后两个总匹配结果很容易，前几个分Matcher的不太好打印，一方面是Match函数没有接收Context，另一方面是潜在的性能问题。

后两个在打印标号的基础上，要再打印名字等信息的话，打印最后一个DNS信息改动很小，打印Matcher信息稍微要加点东西。

[Loyalsoldier]

那只打印 Matcher result 和 Matched DNS 的话，应该可以同时打印具体匹配到的规则的文本吧？如果只打印标号的话，意义不是很大。

[Vigilans]

@Loyalsoldier 应该可以。在上面的测试结果里面发现了另一个小BUG（新PR里面少删了一行……），修正后把上面的测试结果更新了一下，并且手动添加了标号与原规则内容的映射，你可以看一下。

关于debug log里面的文本格式，你觉得该如何设置？我大概想了两种方案：

• 打印两行日志，第一行描述匹配到的Matcher，第二行描述匹配到的DNS（就是Matcher result与Matched DNS）。这样的话：
  • 每条Matcher记录里是否需要附上它属于哪个DNS？参考上面的测试，JSON配置里面两个DNS有一模一样的Matcher，因此需要记录源DNS消歧义。不过大多数正常的规则应该并不会重复写两个一样的Matcher？
  • 如果记录Matcher的附属DNS，则DNS是否用标号标识？若用详细信息标识，则变成↓
• 打印一行日志，第一行记录匹配到的Matcher，及附属上对应的DNS的详细信息。这样的话：
  • 一行日志可能很长。而且根据上面的重复匹配现象，可能DNS的详细信息要重复出现好几次，日志就更长了。

[Loyalsoldier]

line 1:
Debug level: fonts.googleapis.com matches rules [domain:googleapis.com(DNS idx:0), domain:googleapis.com(DNS idx:1), domain:com(DNS idx:0)]

line 2:
Debug level: fonts.googleapis.com will use following DNS in order: {idx0: DOHL//dns.alidns.com, idx1: DOH//1.1.1.1, idx0: DOHL//dns.alidns.com}

line 3:
原日志 Info level：DOHL//dns.alidns.com querying: fonts.googleapis.com.

[Vigilans]

@Loyalsoldier 我试着实现了一下，line 2没有什么问题，line 1有一些问题：

• 一般来说，希望给用户看到的规则应该是写在JSON文件里的原始的样子，但因为"ext"规则的存在，这个目标不容易达到。V2Ray会在解析配置阶段，将诸如geosite:cn的规则展开成domain:...的规则，再传给内置DNS。因此在获取到Matcher Result后，其对应的规则是domain:xxx.com而非geosite:xx。
• 解决方案是保存拆开后的规则(domain:xxx.com）到原规则(geosite:xx）的映射，把映射传给内置DNS。这需要: 1）修改数据结构的Protobuf文件；2）测试代码中用的是解析好的配置，而非原始JSON配置，因此需要为每个测试用例补上原始规则信息。这两者都是代码行数变动较多的操作了。

总体来看，目前有三个选择：

• 不打印line 1
• 只打印拆开后的规则。这个也有问题，因为内置DNS在把拆开规则生成Matcher后并没有继续保存规则。不管是保存拆开规则或是让Matcher计算一番重新生成，都是一笔不小的空间/时间开销。
• 打印JSON里的原始规则。这个对于内存消耗较小，会占用一点时间和代码生成日志（Go没有array.map()写数组生成真的不好看……），需要较大量trivial的代码改动。

---

Edit: 有个方案或许可以少一些Trivial改动，我试着写出来发个Draft PR看看

[Robot-DaneelOlivaw]

line 1已经存在(DNS idx:)的话，line 2的意义就在于解释每个标号为哪个DNS，作用似乎不大。如果在logger启动时就描述出标号和对应的DNS，随后在日志中仅用line 1，或许能节省一些笔墨。

[Debug] v2ray.com/core/app/log: Logger started
[Info] v2ray.com/core/app/dns: DNS: created Local DOH client for idx0: https://dns.alidns.com/dns-query
[Info] v2ray.com/core/app/dns: DNS: created Local DOH client for idx1: https://1.1.1.1/dns-query

如果日志中要打印DNS规则匹配流程，是否也应该打印路由规则匹配流程？

[Vigilans]

@Robot-DaneelOlivaw 在 #98 里实现了Log，line 2还是保留了下来，因为知道匹配了哪些规则和知道将用哪些DNS查询应该算是不同的需求，大多数人可能也比较关心后者。不过line 2的idx没有打印，因为line 1和line 2数组元素是一一对应的，确实没必要重复标识。

如果在logger启动时就描述出标号和对应的DNS，随后在日志中仅用line 1，或许能节省一些笔墨。

对于这个，我看了下原日志的打印代码，这种created ... client的代码并不是在某处统一打印的，而是被分发到具体的DNS Client后，由该Client打印的，而该Client拿不到自己的idx，因此不能直接实现你提出来的日志格式。

如果日志中要打印DNS规则匹配流程，是否也应该打印路由规则匹配流程？

路由和DNS虽然都有域名匹配，也都用了DomainMatcher，不过使用方式并不一样。支持打印DNS的匹配日志都花费了一些功夫，还有其他模块的路由可能会让事情更复杂一些。不过把DNS这边的Contribution清完后，个人再下一个计划看的就是路由了……