基于高性能的P​a​c,实现智能代理

相关说明

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

由于 Pac 文件实质上是一个 javascript 脚本，如果我们把它放在某个 web 服务器上，浏览器下载 Pac 文件时，服务器可以使用 gzip 压缩等方式减少传输的流量，对 Pac 文件本身的压缩就没有必要了。然而，如果 Pac 文件是储存在一个 Open­Wrt 路由器上，储存空间寸土寸金，我们就有必要提前对 Pac 文件进行压缩了。

在 Open­Wrt 路由器上使用一个 Pac 文件代替 ipt­a­bles 与 dns­masq 有几个优势：

1. 性能更好：
   • Pac 文件运行在手机、平板电脑、电脑等设备上，ipt­a­bles 与 dns­masq 运行在路由器上，前者的 CPU、内存均远远好于后者
   • 得益于 V8 引擎，手机、平板电脑、电脑处理 javascript 脚本的效率非常高
   • ipt­a­bles 处理 ip 段匹配时使用的是遍历链表的方式，时间复杂度是 O(n)级别，javascript 脚本可以使用二分搜索等方式降低时间复杂度到 O(logn)
   • dns­masq 处理域名时使用的也是遍历链表的方式，javascript 可以使用 has­Own­Prop­erty 的方式将时间复杂度降低到 O(1)
   注：使用 ipset 进行 ip 段匹配可以获得更高的匹配效率，有人为 dns­masq 提供了一个 patch，用哈希表处理域名匹配以获得更高的匹配效率，这两个优化可以显著提升性能。
2. 配置方便：
   • Open­Wrt 路由器大多自带了网页服务器以提供 luci 网页配置界面，将 Pac 文件配置在路由器上只需要将文件放在路由器的 /​www 目录下即可
   • ipt­a­bles 或是 dns­masq 的配置需要一定的 linux 基础，需要 ssh 登录到路由器上进行配置
3. 扩展性强：
   • Pac 文件本质上是一个 javascript 脚本，利用 javascript 可以实现负载均衡、根据本机 ip 地址决定是否进行代理等多种功能
4. 独立性好：
   • Pac 文件可以部署在本机，方便在多个网络环境下切换
   • 不依赖经过特定部署的路由器，在校园网环境下可以更加方便

尽管如此，Pac 文件也有一些劣势：

1. 使用范围受限：
   • Pac 只能处理 http 与 https 协议，邮件客户端是无法通过 Pac 文件实现代理访问
   • SPDY 协议对代理与 Pac 的处理存在问题，受此影响，twit­ter、face­book 客户端无法使用 Pac 文件进行处理
2. 不能零配置使用：
   • 尽管 Open­Wrt 可以配置 Pac 自动发现，但 OS X 中仍然需要勾选一个选项才能实现这个功能

域名匹配的高效算法

进行高效域名匹配的关键在于使用 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 体积为 160kb，利用种种黑科技可以将数据最终压缩至 16kb 而只产生 2.8% 的效率损失。

分别用浏览器测试这两个 Pac：

var unixtime_ms = new Date().getTime();
while(new Date().getTime() < unixtime_ms + 5000) {}
function FindProxyForURL(url, host) {return "DIRECT;";}

function FindProxyForURL(url, host) {var unixtime_ms = new Date().getTime();
while(new Date().getTime() < unixtime_ms + 5000) {}
return "DIRECT;";
}

浏览一个简单网页，前者会导致浏览器卡顿 5 秒，刷新没有卡顿，访问其他网站也不会，而后者会导致每次刷新都卡顿 5 秒。我们可以得出一个结论：每个 Pac 实例都会被持续使用。这意味着把代码压缩后在 Pac 文件的主函数外解压缩将只有单次性能损失。

AP­NIC 分配 IP 地址段的最小单位是 256，所有的 IP 起始点都是 xx.xx.xx.0 的形式，这意味着我们可以把所有的 IP 段数据除以 256，这样一来 IP 地址的数值范围就从 0​-​4294967295 降低到了 0​-​16777215，Pac 文件的体积可以缩小到 128kb。

接下来，将 IP 起始点的第一组数字作为分组的依据，xx.yy.yy.0 只需要保存为 yy.yy 的十进制形式，数据的范围也就从 0​-​16777215 降低到了 0​-​65535，Pac 文件的体积可以缩小到 64kb。

在上面提到的 IP 段匹配算法中，子网掩码是以幂值来保存的，这样长度达 10 位数的十进制子网掩码数据只需用 2 位数的幂值来保存，Pac 文件的体积可以缩小到 40kb。

由于 IP 地址数据范围在 0​-​65535，可以将其转化为 Uni­code 编码保存。原先用逗号分割的数值可以被保存为字符串保存，用 charCodeAt 读取，大约 5000 个逗号可以被省略，Pac 文件的体积可以缩小到 20kb。

在上述情况下幂值的可能范围是 0​-​16，当幂值为 16 时，意味着其掩码为 /8，无需计算即可得知该 IP 一定是国内 IP，于是我们可以将幂值转换为十六进制数并保存为字符串。如果整个字符串是"10" 则意味着其掩码为 /8，可以直接判断为国内 IP，其他情况下每个幂值都一定是 1 位数，用parseInt 读取字符串指定位即可。这一步可以将 Pac 文件的体积缩小到 18kb。

最后，域名匹配使用的对象也可以由字符串动态生成，正如之前所说，在主函数外动态生成这个对象并不会产生巨大的性能损失，这样可以进一步将 Pac 文件的体积缩小到 16kb.