Table of Content

用 PAC 也有一段时间了,Mac 上是 Shadowsocks 配置的 PAC,iPhone 上是 wifi 下配置的 PAC,服务器端使用 squid,每个 PAC 文件都将近 200kb,从一开始就担心他的性能,最近找到点资料,看来我的担心是多余的。

PAC 文件即 (Proxy auto-con­fig file),实质上是一个 javascript 脚本。浏览器在连接互联网时会调用其中的 Find­Proxy­For­URL(url, host) 函数,并根据其返回值决定访问特定 url 时的代理设置。

高效匹配的算法

  • 得益于 V8 引擎,手机、平板电脑、电脑处理 javascript 脚本的效率非常高。

  • 处理 ip 段的时候,javascript 脚本可以使用二分搜索等方式降低时间复杂度到 O(logn)

  • 处理域名的时候,javascript 可以使用 has­Own­Prop­erty 的方式将时间复杂度降低到 O(1)。

域名匹配的高效算法

进行高效域名匹配的关键在于使用 has­Own­Prop­erty 方法,这个方法以 O(1)的时间复杂度进行查找。

比较好的算法是从完整的域名开始匹配,随后逐级向上查找,即先尝试匹配”trans­late.google.com”,随后尝试匹配”google.com”,最后匹配”com”。

另外一种思路是从根域开始逐级向下查找,顺序与上面的算法相反。

虽然后者的性能比前者好(在处理白名单,让”cn”域名全部直连时,后者只需查找一次,前者需要循环多次),但是灵活性不如前者(后者无法处理只需要让子域名走代理的情况,北大的网络常常有这种奇异现象,比如 B 站处理登录验证的域名 ac­count.bili­bili.com 需要走代理,但是其他 B 站的域名都不需要走代理,在这种情况下,只能用前者处理)。

IP 段匹配的高效算法

AP­NIC 提供了各国的 IP 地址段信息,这些信息由 IP 地址段起始点和地址段长度组成,比如下面这一条记录:

apnic|CN|ipv4|101.0.0.0|1024|20110414|allocated

CN 代表中国,101.0.0.0 是地址段起始点,1024 是地址段长度。

最高效的算法是这样的:先用二分查找,找出比目标 IP 小的最大的地址段起始点,再求出目标 IP 与这个起始点的距离,最后比较这个距离与地址段长度即可。

IP 地址应当被转换为 10 进制保存,另外地址段长度均为 2 的幂次方,所以可以被转换为幂来保存,并且用右移代替简单的比较大小,最终的公式变为:

if (((目标 IP - 起始 IP) >> 幂次) === 0) {retrun True} else {return False}

所以 PAC 的性能没问题,大胆用吧,不过 PAC 只能代理 http/https 协议,邮件的 IMAP/SMTP 是不行的。不过实际使用中,squid 代理的 SMTP 确实不行,但是 Shadowsocks 代理的 SMTP 是可以的。