课程大纲 第 47 课,共 156 课 · 构建一个拦截器
构建一个拦截器

把请求和规则进行匹配

为什么重要 一个拦截器要把一个页面发出的每一个请求(常常每页超过一百个),和成千上万条规则进行核对。如果这个核对很慢,每个页面都会感觉很慢,人们就会把拦截器关掉。又快又对,才是让保护变得可用的东西。

两项工作:答案要对,速度要快

想想一座有 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 -> False

text.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 次。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。