在这篇文章中，我描述了一个实验的结果，它展示了HTTPS Everywhere规则匹配的内存效率如何提高4到10倍，匹配引擎的初始化减少到不到25毫秒，HTTPS升级的执行时间为0.0029到0.0073毫秒，使用受现代广告拦截器启发的不同设计，而不依赖于Rust/WebAssembly组合(即纯JavaScript)。
免责声明：这项工作不是作为HTTPS Everywhere项目的一部分进行的。在试验规则集匹配时，我的目的是探索实现高效引擎并记录我的发现的新方法。如果这些想法中的一些被上游使用，我当然会很高兴。
过去几年，HTTPS的采用率不断提升，2017年首次达到50%的Web流量，2019年更是高达80%。然而，根据EFF的说法：“许多网站(仍然)对HTTPS上的加密提供了一些有限的支持，但这使得它很难使用。例如，它们可能默认使用未加密的HTTP，或者使用返回到未加密站点的链接填充加密的页面。“。
为此，EFF在2014年启动了HTTPS Everywhere项目，为用户提供了一个浏览器扩展，可以在任何可能的情况下自动升级到HTTPS的连接。
为了确定何时升级是可行的，扩展依赖于规则集数据库，该数据库允许它知道给定URL是否支持HTTPS。这些规则会不断更新，以限制破坏并最大限度地扩大覆盖范围。
在过去的几年里，我花了相当多的时间在内容阻止程序上-特别是在性能方面-我一直很好奇规则匹配逻辑是如何在任何地方的HTTPS中实现的，因为这项任务与广告阻止有许多相似之处。最近，我无意中发现了两张罚单，上面提到了内存使用率高和扩展初始化慢的问题，于是我决定仔细看看。
高内存和高CPU使用率是有问题的，原因有很多。由于HTTPS Everywhere运行在各种环境中--包括潜在的低端手机--即使在IO性能有限、CPU速度慢和内存容量低的情况下，它也必须表现良好。此外，HTTPS包含在ToR中(在台式机和移动设备上)，当安全设置达到最大值时，可以禁用JIT，从而进一步降低性能。还要考虑到，在加载页面的同时，浏览器的许多组件都在争夺资源：解析HTML、评估JavaScript、呈现页面，但也会保护隐私，例如广告拦截器，当然还有无处不在的HTTPS。最后但并非最不重要的一点是，能耗(尤其是在移动设备上)不容忽视：CPU使用率越高，意味着电池寿命越短。
在进行实验时，我想知道作为现代内容拦截器的一部分实现的一些优化在任何地方的HTTPS中是否都有意义，以及它们是否会提高整体效率。这篇博客文章介绍了这次调查的一些结果。提出了以下贡献和改进：
一种新的设计灵感来自于在最快的内容拦截器中实现的一些相同的优化，从而提高了效率：大约4.7MB的内存使用(比当前HTTPS Everywhere Rust/WebAssembly实现减少了4倍)，在使用实验性的统计数据结构时进一步减少到大约2.1MB(有想法可以进一步减少)。
查询具有要升级到HTTPS的URL的规则集时的决策时间介于0.0029到0.0073毫秒之间。
序列化到紧凑的二进制表示形式和从紧凑的二进制表示形式反序列化只需不到25毫秒，并且没有内存副本。
设计和实现紧凑的索引数据结构，允许高效地检索可能应用于给定输入URL的一小部分规则。
受SMAZ启发的内置小字符串压缩实现，可减少高达60%的内存使用量。
一种实验性的统计数据结构，允许在不太可能发生冲突的风险下使用更低的内存。
在深入研究匹配引擎的设计之前，我们先简要描述一下HTTPS Everwhere规则集。
规则数据库由数千个规则集(目前约为25k)组成。每个规则集都是一个XML文件，其中包含有关将一个域或一组域升级到HTTPS的请求的信息(例如，对于像Bitly这样的组织)。该文件可以包含以下实体：
目标-定义此规则集的目标域(例如example.com)。它们还可以使用通配符，既可以针对所有子域，也可以针对多个顶级域。
排除-是允许阻止某些特定域或URL升级到HTTPS的正则表达式(例如，为了防止破坏)。
规则-定义如何将不安全请求从不安全升级到安全(即，它们对URL重写逻辑进行编码)。它们定义了输入URL应该匹配的From正则表达式，该表达式与描述升级后的URL应该是什么样子的to属性相关联。最常见的情况是简单地将^http：转换为https：。
安全Cookie-可选地定义是否也应使用强化标志保护来自某个目标域的Cookie。
在给定一组规则集的情况下，将不安全请求升级为安全请求取决于以下步骤：
如果按照前面的步骤找到匹配规则，则使用此规则定义的重写逻辑将URL重写为安全版本。有关匹配规则集的确切语义的更多信息，请查看官方文档的此页。
编写匹配算法的简单方法是迭代检查每个输入URL的所有规则集，检查它们的目标、排除和规则，直到找到匹配为止。这不会非常有效，我们可以做得更好(需要明确的是，这不是HTTPS无处不在的方法，我描述它只是为了获得最幼稚的解决方案的感觉)。
在接下来的几节中，我们将探索对新匹配引擎的速度和内存效率做出贡献的一些最重要的想法。首先，我将介绍中央索引数据结构，它允许大幅减少查找相关规则集所需的工作量。其次，我将带您了解如何以非常紧凑的方式将此索引表示为单类型数组。第三，我们将了解如何通过实现此紧凑索引的内置字符串压缩功能来进一步减少内存使用。最后，我将简要描述使用TRIE数据结构和基于散列的实验性概率数据结构来减小索引大小的另外两种尝试。
我们不是迭代每个输入URL的所有规则集，而是希望快速识别将根据输入URL进行评估的一小部分候选者。为了实现这一目标，我们依赖反向索引，该索引将目标、排除和规则分组到由它们包含的公共子字符串(或令牌)索引的桶中。这允许我们通过使用在URL中找到的令牌查询索引来收集给定URL的候选者。因此，保证检索到的每个候选与该URL至少共享一个公共子字符串。在实践中，这极大地减少了做出决定所需的工作量。此技术用作内容拦截器的一部分，用于标识指示应该取消网络请求的过滤器列表。
我们为目标、排除、规则和安全cookie创建单独的索引。为了最大限度地减少为每个URL检索的候选者的数量，我们确保每个目标和安全Cookie都使用其最稀有的令牌进行索引，而排除项和规则仅使用它们所属的规则集的ID进行索引。实际上，每个索引都是使用以下算法创建的：
每个元素都使用\w+(字母数字字符)进行标记，或者将规则集ID用作标记。例如，目标example.com将被标记为['；example&39；，'；com'；]。
我们使用全局计数器跟踪每个令牌的出现次数。
然后，我们为每个元素选择最好的(即最少看到的)令牌，并将其用作反向索引中的关键字。
因此，索引的大多数存储桶将包含单个元素(这意味着我们找到了一个全局唯一的令牌来索引该元素)。为了更好地了解此技术带来的调度功能，请考虑通过将包含来自最流行的域的24万个URL的数据集与HTTPS Everywhere规则集进行匹配而收集的以下统计数据：
对于给定的网址，候选目标评估的中位数是：7个--总共163k；这意味着我们平均只需要查看所有目标的0.004%。在这些目标中，大多数只需要在一个集合中查找一次，因为我们经常从同一个规则集中获得多个候选者。通过跟踪我们已经在考虑的规则集，我们只需要评估给定规则集中的第一个目标。需要进行字符串比较的候选目标的中位数是：5。
考虑的规则集的中位数为：1，在给定域被多个规则集作为目标的极少数情况下，最大值为：2(总共25k)。
然后，对于每个规则集，我们检索一个组合排除(所有正则表达式聚合为一个，并使用|字符连接)，从而产生一个或两个RegExp计算(来自所考虑的一个或两个规则集)。
最后，我们检查尚未排除的每个规则集中的规则，直到找到匹配项。考虑的规则的中位数是2。
此图描述了根据规则集的最新快照将请求重写到HTTPS所需的平均时间，该快照是根据上述24万个URL的数据集进行评估的。请注意，这些测量禁用了HTTPS Everywhere的内部缓存，以便仅考虑引擎的原始速度。
令人惊讶的是，Rust/WebAssembly版本比JavaScript实现慢。虽然两者都很快，因为即使是“最慢”的结果平均也只有0.028毫秒。很可能是将数据从JavaScript传输到WebAssembly的开销导致了这个结果。另一方面，我们看到我们的反向索引实现比两者都快，平均时间在0.0046到0.0073毫秒之间。注意，在Node.js中运行相同的基准测试会导致更快的决策时间，为0.0029毫秒-这可能是因为浏览器对基准测试不太友好，因为许多组件可能会竞争cpu资源，但这只是我的猜测。
虽然上一节中描述的索引技术大大加快了匹配速度，但它在内存使用和初始化时间方面并不是最优的。如果索引表示为Map，这意味着在每次初始化时(当扩展启动时)，我们需要从头开始重新创建索引(使用原始XML规则集或其JSON版本)，或者从Map的文本表示(即从缓存)加载它，就像键、值对数组一样。
相反，上面描述的反向索引被实现为存储在单个Uint8Array(类型化数组)中的紧凑二进制数据结构，其中数据以允许高效查找的方式组织。内存中的目标、排除、规则和安全cookie实例，以及匹配输入URL和域所需的RegExp实例，只有在它们有机会匹配时才会延迟加载，并从存储在类型化数组中的二进制表示进行编译，这要归功于反向索引。这些实例还可以(可选地)缓存到Map中，以便后续查找不需要命中二进制索引(比Map.get稍微慢一点)。
由于实际考虑的规则集的数量或多或少与用户在浏览会话期间访问的唯一域的数量成正比，因此缓存机制所需的额外存储器使用量相当小。
在这篇文章的“使用类型化数组进行低级操作”一节中给出了更多实现细节。要总结此数据结构的优势，请执行以下操作：
它允许将所有规则集编码成非常紧凑的二进制格式，存储在单个Uint8Array中。因此，使用这种引擎的扩展的总内存使用量是相当可预测的，并且接近此类型化数组的大小。
序列化和反序列化非常高效，因为可以在此Uint8Array实例上直接执行查找，而无需首先将数据复制到更方便的数据结构(如Map)中。因此，序列化在于本地存储相同类型的数组(例如，在IndexedDB中)，而反序列化在于读回它。
这个二进制数据结构可以在服务器端创建一次，然后托管在CDN上，这样客户端就可以直接获取它，进一步加快初始化速度(以下二进制文件使用cron触发的GitHub工作流自动更新)。
由于反向索引，目标、排除、规则和安全cookie的内存中实例以及与输入URL和域匹配所需的RegExp实例仅在有机会匹配时才从二进制表示中延迟加载和编译。
然而，这种方法的缺点是，更新(添加或删除索引中的元素)目前需要完全重新创建索引，这相对昂贵(大约需要500毫秒)。但是，由于更新可以在后端执行，而且相对较少，所以这不是一个拦路虎。
这些测量提供了一些相当令人惊讶的结果。一方面，我们看到与Firefox相比，Chrome似乎在WebAssembly版本上举步维艰。不过，JavaScript实现的性能再一次超过了Rust/WebAssembly组合。同样，我最好的猜测是，传输到WebAssembly上下文的数据量可能是造成这种情况的部分原因，但我希望从核心开发人员那里获得更多关于这方面的见解。我们还看到，我们的二进制索引初始化非常快，在12到45毫秒之间。我们可以通过禁用内置的CRC-32校验和机制来进一步减少它，该机制可确保缓冲区在反序列化之前不会损坏，但这似乎不是必要的。
至此，我们已经展示了如何高效地查询规则集，以及如何以紧凑的方式表示索引数据结构，便于序列化和反序列化以实现更快的初始化。最终的类型化数组的大小大约为7Mb。仔细观察会发现，这些数据中有很大一部分由来自目标的原始字符串(主机)、排除项(模式)、规则(从和到)以及安全cookie(主机和名称)组成：大约3MB，占总大小的40%多一点。
查看这些字符串，很快就会注意到一些值非常频繁，比如安全Cookie中的.+，或者规则中的^http：和https：。利用这些模式的一种方式是对一些公共字符串的检测进行硬编码，并用操作码替换它们，或者执行某种类型的字符串插入，以避免在内存中(或在紧凑的反向索引中)具有多次相同的数据。
看待这个问题的另一种方式(也可以被视为字符串插入机制)是依赖基于码本的压缩算法来减小字符串的大小。碰巧我在过去已经尝试过这样的技术(例如使用SMAZ或SHECHO)。最后，我用纯JavaScript实现了SMAZ的一个自定义变体，以集成到我正在工作的广告拦截器中。该库提供了自动生成码本的功能，该功能试图根据输入字符串列表查找最佳码本。
将这种码本压缩思想应用于规则集，我们能够将字符串压缩40%到60%，从而将序列化引擎的总大小进一步减少到5MB(即减少2MB或30%)。应用此优化可以在自定义的类似DataView的抽象中透明地完成，该抽象用于将数据序列化为二进制表示形式并返回。
依赖代码簿的一个缺点是，在更新规则集时需要重新生成代码簿，以便它们保持相关性。托管在GitHub上的原型依靠GitHub工作流基于规则的最新快照更新代码簿，并使用更新后的资产打开PR。码本也作为匹配引擎的二进制表示的一部分提供，这意味着从CDN(即GitHub)下载新版本的客户端始终获得最佳压缩，而无需更新源代码。
此图显示了Chrome Memory Dev工具使用快照报告的规则集占用的大小。我们看到，与HTTPS Everywhere的初始JavaScript实现相比，WebAssembly降低了内存使用量。另一方面，我们的二进制索引使用的内存更少，当使用字符串压缩时，差别甚至更大。
虽然基于码本的压缩在减少匹配规则集所需的原始字符串的内存使用量方面非常有效，但根据数据的性质，可能会有更有效的方法。具体地说，目标是域名，其中大多数根本不使用通配符；它们还代表大部分字符串。Trie通常用于表示这类数据。我们希望域的后缀在多个目标之间重复(一些顶级域非常常见)。
我已经知道可以用非常紧凑的方式对trie进行编码-在存储ASCII字符串时，只使用一个32位数字来表示每个节点。在实现这个新的数据结构之前，我首先估计了预期的最终大小，以确保它是值得的。
我在内存中使用了基于JavaScript对象的更朴素的表示形式，并在每个节点中使用Map实例将父节点链接到其子节点，从而构建了内存中的trie。存储所有目标会产生1,654,430个节点的trie，在我们的紧凑表示中，这将产生大约6.6MB的内存。不太令人振奋的…。
然后我意识到，为了从顶级域的压缩中获益，反向存储域可能更有意义。在颠倒插入目标的顺序后，节点数量降至878,251，这将产生3.5MB的内存。这看起来已经更合理了。但我们还需要考虑有关每个目标属于哪个规则集的额外信息(匹配时需要的信息)。假设我们有163,486个目标，并且假设我们找到了一种方法来为每个目标使用额外的32位数字来编码规则集成员资格，粗略的计算告诉我们需要额外的650KB，从而导致总共4.1MB的内存使用。即使假设每个目标有非常乐观的16位开销，我们仍然需要比上面描述的码本压缩方法更多的内存来存储目标。
这就以尝试结束了实验。不幸的是，与已经实现的字符串压缩方法相比，使用trie似乎不会产生任何显著的节省。如果根本不实现字符串压缩，这可能是一个可行的选择。而且，使用诸如Patricia或自适应(ART)Trie之类的更高级的Trie结构可以获得更好的结果，这将允许将多个字符存储到单个节点中。
在这个位置。
..