PAC 自动代理配置的性能问题

GFW Sep 12, 2015

用 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 是可以的。

Tags

Jie Li

🚘 On-road / 📉 US Stock / 💻 Full Stack Developer / 🎓 Grad Student / ®️ ENTJ

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.