把请求和规则进行匹配
为什么重要 一个拦截器要把一个页面发出的每一个请求(常常每页超过一百个),和成千上万条规则进行核对。如果这个核对很慢,每个页面都会感觉很慢,人们就会把拦截器关掉。又快又对,才是让保护变得可用的东西。
两项工作:答案要对,速度要快
想想一座有 5,000 本书的图书馆。要找一本书,你不会从第一个书架开始读每一本书的书脊。你会去对的分区,再去对的书架。拦截器也应该这样做:直接跳到那几条可能匹配的规则,并且只检查它们。
这个练习会同时就这两方面打分。测试会统计你的 decide 为一个请求调用 rule_matches 多少次,而在加载了 5,000 条规则的情况下,预算是 20 次检查。我们统计的是检查次数,而不是给你计时,所以一部慢的手机和一台快的笔记本电脑会以同样的方式评分。
第 1 步:通配符
通配符:一个代表“任何字符”的符号。在过滤列表里它是 *,所以 /beacon/*/hit 匹配 /beacon/42/hit 和 /beacon/abc/hit。
在每个 * 处切分模式,然后在文本里按顺序找到这些片段,每一个都要在上一个之后:
wildcard_in("*/collect?*cid=", "https://m.example/collect?x=1&cid=9")
# pieces: "/collect?" then "cid=" -> both found, in order -> True
wildcard_in("a*b", "b then a")
# "a" found at position 7, then no "b" after it -> Falsetext.find(piece, pos) 只从位置 pos 开始查找,返回 piece 开始的位置,如果没有就返回 -1。注意,在过滤列表里 ? 和 . 都是普通字符,所以不要使用正则表达式或 fnmatch,它们会把这些字符当作特殊字符。
第 2 步:一条规则对一个请求
rule_matches(rule, url, third_party) 为一条规则回答是或否:
- 一条设置了
third_party的规则永远不会匹配一个第一方请求。 - 一条域名规则
adco.example匹配主机adco.example,或者任何以.adco.example结尾的主机。那个点很重要:notadco.example是别人。 - 当
wildcard_in(value, url.lower())为真时,一条模式规则就匹配。
第 3 步:一个索引,让你只检查少数几条规则
索引:一个只构建一次、让你不用搜索一切就能找到东西的结构,就像一本书末尾的索引。在这里:一个从主机名到这个主机的规则的字典。
无论一个 Python 字典装了多少个键,它都能一步找到一个键。所以只构建一次:
index = {"domains": {"adco.example": [rule, ...], ...},
"patterns": [rule, rule, ...]}对于一个发往 img.adco.example 的请求,查找这个主机的每一个结尾:img.adco.example、adco.example、example。这是三次查找,而不是 5,000 次检查。再加上少数几条模式规则(真正的拦截器也会给它们建索引,依据的是它们必须包含的一小段文本;我们把它们放在一个普通的列表里)。
第 4 步:做出决定,例外优先
检查每一个候选规则。如果任何一条匹配的规则是例外,答案就是 "allow",就这样。否则,如果有任何拦截规则匹配,就是 "block";如果什么都没匹配,就是 "allow"。例外之所以存在,是因为列表有时会抓住一个网站确实需要的东西,比如提供一个无害库的 cdn.example。
一个常见的误解
“规则越多,拦截器就越慢。”有了一个好的索引,就不会:在一个字典里查找一个主机,无论有 50 条规则还是 50,000 条,代价都差不多。让拦截器变慢的,是一条一条地检查规则。
试一试 通过之后,把 decide 改成遍历列表中的每一条规则(不用索引),再运行一次测试。预算测试会失败,计数大约是 5,000。这个数字,就是你的索引在每个页面的每一个请求上省下的工作量。
用其他语言实现
JavaScript:
function wildcardIn(pattern, text) {
let pos = 0;
for (const piece of pattern.split("*")) {
if (!piece) continue;
const at = text.indexOf(piece, pos);
if (at === -1) return false;
pos = at + piece.length;
}
return true;
}
// Index: a Map from host to rules; look up each ending of the host.
function candidates(index, host) {
const parts = host.split(".");
const out = [];
for (let i = 0; i < parts.length; i++) {
out.push(...(index.domains.get(parts.slice(i).join(".")) || []));
}
return out.concat(index.patterns);
}Go:
func wildcardIn(pattern, text string) bool {
pos := 0
for _, piece := range strings.Split(pattern, "*") {
if piece == "" {
continue
}
at := strings.Index(text[pos:], piece)
if at < 0 {
return false
}
pos += at + len(piece)
}
return true
}回顾
- 通配符模式:在
*处切分,然后按顺序找到这些片段。 - 域名规则匹配主机或任何子域名,逐个标签地进行比较。
- 一个索引(一个按主机组织的字典)意味着少数几次查找,而不是成千上万次检查。
- 一条匹配的例外总是优先于一条拦截规则。
编写四个函数。wildcard_in(pattern, text):当 pattern 中 * 之间的各个片段都按顺序出现在 text 中时为 True。rule_matches(rule, url, third_party):当一个规则字典(来自上一课)匹配这个请求时为 True。build_index(rules):以你喜欢的任何方式组织这些规则,让 decide 能跳过其中的大部分。decide(index, url, third_party):返回 "block" 或 "allow",任何匹配的例外都优先,并且在加载了 5,000 条规则时,每个请求最多调用 rule_matches 20 次。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。