PDF可能有效
概率算法在我们周围无处不在。它们不仅是可以接受的，而且一些程序员实际上在寻找使用它们的机会。
Tyler McMullen，Fastly
概率算法的存在是为了解决那些不可能或不现实（太昂贵、太耗时等）精确解决的问题。在理想的世界中，您永远不需要使用概率算法。对于不熟悉它们的程序员来说，这个想法可能会让人非常紧张：“我怎么知道它真的会有效？如果它莫名其妙地错了怎么办？我该如何调试它？也许我们应该放弃这个问题，或者购买更多服务器……”
然而，对于那些深入理解概率论或者至少在大型生产环境中使用和观察过概率算法行为的人来说，这些算法不仅是可以接受的，而且也值得寻找机会使用它们。这是因为它们可以帮助解决问题并创建更便宜、更可预测的系统，并可以做其他方法无法完成的事情。
世界是概率性的——或者至少对于我们来说，要 100% 精确地建模实在太复杂了。网络，尤其是互联网，也是概率性的。一个特定的数据包是否会到达它需要去的地方，我们无法完全知晓。知道它在从世界的这一端到另一端的过程中将通过哪些网络路径，就更不确定了。运行在异步/有损网络上的系统必然是概率性的。不管你喜不喜欢，概率就在我们周围。
不确定性是缺乏经验的开发人员对概率算法产生问题的核心，导致他们认为这些算法可能效果不佳或无法调试。然而，这种想法是不正确的。概率算法融入了随机性元素（它们也被称为随机化算法），这是可以量化的。它可以被分析，从而可以对算法的行为做出强有力的预测。事实上，关于算法将如何表现，几乎没有什么不确定性。
本文讨论两种类型的概率算法：一种是通过 rand() 调用显式引入随机性的算法，另一种是将输入数据转换为均匀分布以达到类似效果的算法。我将讨论属于这些类别的特定算法，包括 LogLog（及其更著名的后继者 HyperLogLog）和双峰组播，以及它们试图解决的问题。
在第三种类型的概率算法中，随机性是数据固有的。这适用于诸如 GPS 跟踪、自动驾驶汽车、传感器网络和导弹制导系统等问题。例如，传感器网络通常试图在只有部分数据的情况下对整个网络做出声明。在自动驾驶汽车和导弹制导系统的情况下，数据处于持续变化中。当程序处理完数据时，当前状态已经改变。因此，它已经不准确了，必须考虑到这一点。本文不讨论这种类型的算法，但要了解有关此类别中的问题集以及解决这些问题的算法的更多信息，阅读卡尔曼滤波器11和一般的估计算法会很有帮助。
去重计数
去重计数问题涉及计算可能包含重复项的流中唯一项的数量。更正式地说：找到多重集的基数。许多问题都属于这一类。例如：过去一小时内有多少个唯一 IP 连接到服务器？一个巨大的文本语料库中有多少个不同的单词？一天内有多少不同的用户访问了一个流行的网站？或者甚至，通过 HTTP 代理请求了多少个唯一的 URL？
这个问题的朴素解决方案很简单。在看完上一句话之前，你可能已经在脑海中写出了代码。以下是一些 Python 代码，说明了该解决方案
...
def count_distinct(stream)
seen = set()
for item in stream
seen.add(item)
return len(seen)
...
与许多问题一样，去重计数的难度在于规模。计算一千甚至一百万个唯一用户、IP、URL 或单词可能很容易且廉价，但一亿个呢？还不太糟。那么在数千台服务器上每台服务器一亿个呢？现在开始变得有趣了。
现在的问题是：在 1,000 台服务器上执行去重计数，每台服务器可能有多达 1 亿个唯一项，并找到其结果并集的基数。换句话说：分布式去重计数。让我们考虑一个朴素的解决方案。
每台服务器都可以像前面的代码示例中那样，保留一组“已见”项。当每台服务器完成其单独的去重计数运行时，它会将该“已见”集的全部内容发送到中央服务器，然后中央服务器可以取所有集合的并集，并返回合并集的基数。
...
def combined_cardinality(seen_sets)
combined = set()
for seen in seen_sets
combined |= seen
return len(combined)
...
同样，朴素的解决方案非常简单明了，但代价也很高昂。如果每台服务器看到多达 1 亿个唯一项，那么“已见”列表的大小将非常大。在 URL 的情况下，平均长度约为 76 个字符。这将使每个服务器的列表大小约为 7.6 GB 数据。即使每个 URL 都可以哈希为 64 位整数，大小也将为 800 MB。这要容易管理得多，但是如果有数千台服务器呢？每台服务器都将其“已见”列表发送到中央服务器。仅在 1,000 台服务器的情况下，就有 800 GB 的数据要转储到 combined_cardinality 函数中。
如果您需要经常执行这种分布式去重计数，那么您要么需要安装那些“大数据”系统之一（并聘请一个团队来运行它），要么找到不同的解决方案。
引入 HyperLogLog。此算法采用概率方法来解决去重计数问题。它的核心基于两个观察结果：首先，在随机数的二进制表示中，任何特定位被设置的概率为 50%；其次，两个独立事件 A 和 B 同时发生的概率是 P(A)*P(B)。因此，如果该随机数中任何一个特定位被设置的概率为 50%，那么任何两个特定位被设置的概率为 25%，而任何三个特定位被设置的概率为 12.5%。您明白了吧。
要记住的概率论 101 的另一个知识点是，直到事件发生为止的预期试验次数是 1 / P(event)。因此，如果 P(一个特定位被设置) 为 50%，那么其预期试验次数为两次。对于两个特定位，期望值为四；对于三个，为八；依此类推。
输入值通常不是均匀分布的随机数，因此您需要一种将输入值转换为类似于均匀分布的值的方法——换句话说，哈希函数。一个警告：在哈希函数的某些应用中，分布对于系统的正确性并不重要。然而，HyperLogLog 对此非常敏感。如果哈希函数输出的某些位比其他位更有可能被设置或取消设置，它会完全扰乱算法背后的数学原理。（我在 MurmurHash313 上取得了良好的成功。要了解您首选的哈希函数的性能如何，请查看 SMHasher15，它在查找哈希函数中的缺陷方面做得非常出色。）
那么，第一步是获取输入项并将其哈希为一组位。然后计算设置的前导位的数量，并记录到目前为止已设置的前导位的最大数量。这将提供对已处理的唯一项数量的粗略估计。看到一个前导位被设置的概率是 50%，因此您会“期望”唯一项的数量是两个。如果设置了三个前导位，那么平均而言，您将看到八个唯一项。
改进估计的方法——以及 HyperLogLog 背后的独特想法——是将传入的项根据其尾部位划分为一系列“桶”。记住每个桶的最大前导设置位数：通过像这样将传入的项划分为桶，您可以对总基数进行更准确的估计。如果您有 m 个桶和 n 个唯一项，那么平均而言，每个桶将看到 n/m 个唯一项。因此，取这些桶的平均值可以合理地估计 log2(n/m)，您可以从中轻松生成估计值。
此外，HyperLogLog 具有出色的特性，允许您获取相同数量桶的单独 HyperLogLog 实例，以及每个对应桶的最大值，并最终得到一个 HyperLogLog，它是前两个 HyperLogLog 的并集。
这是 HyperLogLog 算法工作原理的粗略草图。HyperLogLog 引入的主要更改是使用调和平均数而不是算术平均数。（有关更多信息，请阅读原始 LogLog6 和 HyperLogLog8 论文。）
考虑分布式去重计数问题的朴素实现。假设您有 1,000 台服务器，每台服务器有 1 亿个唯一项。在算法的每次运行中，中央服务器都需要处理 800 GB 的数据。这也意味着 800 GB 的数据需要遍历网络。HyperLogLog 如何改变这一点？
根据原始论文作者所做的分析，您可以使用大约 1.5 KB 的空间用于桶，从而获得大约 2% 的准确率。每台服务器保留其自己的 1.5 KB HyperLogLog，然后将其发送到中央服务器。对于 1,000 台服务器，中央服务器在每次分布式去重计数运行时处理大约 1.5 MB 的数据。换句话说，您处理的数据量仅为朴素解决方案处理的数据量的 0.0002% 左右。
这完全改变了问题的经济性。突然之间，您可以运行许多这样的操作，并且更频繁地运行它们。您不需要大数据系统；您甚至不需要多台服务器——所有这些都只需付出估计值 2% 的偏差的代价。
最近邻搜索
最近邻搜索问题涉及在集合中查找相似的项目——例如，书籍、音乐、产品、照片和视频。这实际上是一个双重问题：相似是什么意思，以及如何找到彼此相似的项目？
问题的前半部分称为特征提取。它定义了项目中要比较的内容。例如，如果要逐字符比较两本书，那么字符及其位置将是您的特征。在实践中，这并不是非常有用。相反，您可以选择提取每个唯一单词的相对计数，并将其用作本书的特征集。想象一下以下引言是一本“书”
一个人仍然是即将不再成为的人，并且已经是即将成为的人。一个人活着自己的死亡，一个人死着自己的生命。
— 让-保罗·萨特
从这本“书”中提取每个单词的计数将产生一个“词袋”，可视化如下
{ already: 1, and: 1, be: 1, become: 1, cease: 1, death: 1, die: 1, going: 2, is: 3, life: 1, lives: 1, one: 7, still: 1, to: 3, what: 2 }
这只是进行特征提取的一种方法。您可以选择改为提取单词对
{ already_what: 1, and_already: 1, be_and: 1, become_one: 1, cease_to: 1, death_one: 1, ... }
然而，在所有情况下，特征提取的输出都可以表示为向量。一本有 10,000 个唯一单词的书可以表示为 10,000 维空间中的一个向量。
这可能看起来很奇怪，但是以这种方式表示特征可以进行一些巧妙的操作。例如，如果您将每本书都视为 n 维空间中的一个点，则可以通过计算它们之间的欧几里得距离7 来衡量相似性。您也可以测量向量之间的角度。余弦相似度3 在这种技术中效果很好。
有很多测量相似性的技术，但它们都容易受到一个潜在问题的困扰：维度灾难4。简而言之，维度灾难是一组现象，当尝试处理非常高维度空间中的数据时，由于空间体积随着每个维度呈指数级增长而发生。问题是，计算两个向量的欧几里得距离或余弦相似度所需的工作量与维度的数量成正比。对具有许多维度的向量执行这些计算非常耗时。
引入另一种概率算法：LSH（局部敏感哈希）。LSH 背后的思想基本上与传统哈希相反。在传统哈希中，两个相似但不相同的输入值需要具有非常不同的输出。在 LSH 中，两个相似的输入应该具有相似的输出，但数据量要小得多得多。在实践中，我使用 LSH 将百万维向量转换为 512 位哈希，效果很好。
显然，如果高维向量被缩小为小的“签名”，那么数据将会丢失。这就是概率部分发挥作用的地方。
有很多不同的方法可以生成 LSH。以下示例是其中一种更简单的方法。
假设我们有一个图书文本语料库。我们已经提取了一个包含 100,000 个条目的词汇表。因此，这些书中每一本的特征向量将具有 100,000 个维度。我们还假设我们已决定创建一个 256 位 LSH 函数。现在我们生成 256 个完全随机的 100,000 维向量。这些随机向量是我们 LSH 函数的基础。
LSH 函数计算输入向量与预先生成的每个随机向量的点积。对于每个随机向量，如果点积为正，我们记录为 1 位。如果为负，我们记录为 0 位。我们最终得到一个 256 位输出哈希。
考虑这个问题的最佳方式是随机向量有效地“划分”了向量空间。通过回答输入向量是大于还是小于它们中的每一个，我们可以近似其在该空间中的“角度”。因此，此 LSH 函数实际执行的操作是生成一个哈希，该哈希可用于近似任意两个哈希之间的余弦相似度。两本书的余弦相似度将与它们哈希之间的汉明距离成正比。
可靠广播
在跨高延迟有损网络（即互联网）的大量对等方之间可靠地广播消息是一个难题。事实上，这正是我们在 Fastly 必须解决的问题，以便创建我们的即时清除系统。通常，当面对这个问题时，工程师会尝试使用集中的单一事实来源来解决它。然后，该系统要么将更新推送到所有服务器，要么由所有服务器从中拉取更新。然而，依赖于单一事实来源也使其成为单一故障点。如果该中央系统消失，或者所有或部分服务器无法访问，那么系统的可靠性就彻底完蛋了。
是否有替代解决方案？乍一看，这个问题似乎可以用原子广播5来解决。然而，原子广播的原则之一是全序属性。换句话说，如果您有两条消息 A 和 B，则每台服务器始终以相同的顺序看到它们。虽然该属性对于某些应用程序可能很有用，但它引入了队头阻塞问题10。如果消息 A 在消息 B 之前到达，但消息 A 延迟到达服务器，则每台服务器都必须等待接收 B，直到该服务器接收到 A。在我们的特定应用中，顺序无关紧要，并且队头阻塞可能导致的额外延迟是不可接受的。
我们一直在寻找替代方案，最终决定采用一种名为双峰组播的算法，这是一种多阶段协议，可在服务器网络上可靠且概率性地分发消息。第一阶段包括从一个对等方到所有其他对等方不可靠地广播消息。该广播的机制不是很重要——例如，如果可用，您可以使用 IP 组播。重要的是消息尽可能快地发送到所有服务器，即使它们有可能在途中丢失。
该算法的第二阶段是用于反熵的流言协议9。每个服务器不时独立地在网络中随机选择另一台服务器。它将当前状态的摘要发送给选定的服务器，本质上是该服务器到目前为止所看到的一切的摘要版本。该摘要的具体格式不是协议的规定部分，但其思想是以这样一种方式发送摘要，以便当服务器收到摘要时，它可以确定它错过了哪些消息。然后，它将响应它尚未收到的消息列表，并且发起流言的服务器将重新发送这些消息。
该系统是概率性的，因为服务器随机选择与其他哪些服务器进行流言。他们选择在某些轮次中与之进行流言的服务器可能也错过了他们错过的相同消息。在这种情况下，他们不会立即恢复丢失的消息。即使丢失的消息在系统中传播的方式是随机的，但它是众所周知的，并且遵循经典的“流行病”模式。丢失的消息通过网络传播的速度和概率可以通过更改流言的频率以及服务器记住旧消息的时间长度来调整。
我们清除系统核心的这个系统版本经过调整，使得永久丢失消息的概率极低——可能性约为 10-312%。按照当前的清除速度，我们预计由于算法中的随机性，每 3x10300 年会丢失一条消息。换句话说，只要您知道该概率是多少，“高概率”就完全足够了。
许多难以精确解决的问题通过概率算法变得非常可行。一致性哈希2 常用于负载均衡和分布式数据库。最小割算法12 可以应用于网络路由中的问题。布隆过滤器1 存在于许多数据库和网络应用程序中。快速排序14 实际上是当今使用的标准排序算法。即使是基本的普通哈希表实际上也是概率性的。程序员的日常工作充满了概率算法和数据结构。它们往往不会被注意到，因为它们工作正常。
的确，概率算法在我们周围无处不在。它们可以帮助解决难题，而无需求助于成排的机器。它们可以帮助解决其他方法实际上无法解决的问题。概率算法应该成为那些设计和构建大型系统的人们脑海中的首要考虑因素。
参考文献
1. 布隆过滤器. 维基百科; https://en.wikipedia.org/wiki/Bloom_filter.
2. 一致性哈希. 维基百科; https://en.wikipedia.org/wiki/Consistent_hashing.
3. 余弦相似度. 维基百科; https://en.wikipedia.org/wiki/Cosine_similarity.
4. 维度灾难. 维基百科; https://en.wikipedia.org/wiki/Curse_of_dimensionality.
5. Defago, X., Schiper, A., Urban, P. 2004. 全序广播和组播算法：分类学和调查. 计算调查 36(4): 372-421; http://dl.acm.org/citation.cfm?doid=1041680.1041682.
6. Durand, M., Flajolet, P. 2003. 大型基数的 LogLog 计数. 欧洲算法研讨会; http://www.ic.unicamp.br/~celio/peer2peer/math/bitmap-algorithms/durand03loglog.pdf.
7. 欧几里得距离. 维基百科; https://en.wikipedia.org/wiki/Euclidean_distance.
8. Flajolet, P., Fusy, E., Gandouet, O., Meunier, F. 2007. HyperLogLog：近乎最优的基数估计算法分析. 算法分析会议; http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf.
9. 流言协议. 维基百科; https://en.wikipedia.org/wiki/Gossip_protocol.
10. 队头阻塞问题. 维基百科; https://en.wikipedia.org/wiki/Head-of-line_blocking.
11. Kalman, R. E. 1960. 线性滤波和预测问题的新方法. ASME 交易 - 基础工程杂志 82 (D 系列): 35-45; http://www.cs.unc.edu/~welch/kalman/kalmanPaper.html.
12. 最小割算法. 维基百科; https://en.wikipedia.org/wiki/Karger%27s_algorithm.
13. MurmurHash3; https://code.google.com/p/smhasher/wiki/MurmurHash3.
14. 快速排序. 维基百科; https://en.wikipedia.org/wiki/Quicksort.
15. SMHasher; https://code.google.com/p/smhasher/.
更多信息
有关生成局部敏感哈希的技术的更详尽解释内容太多，无法包含在本文中。请参阅以下推荐的相关文章列表
Andoni, A., Indyk, P. 2008. 近似最优哈希算法近似高维最近邻. 通讯 51(1):117-122; http://people.csail.mit.edu/indyk/p117-andoni.pdf.
Andoni, A., Indyk, P. Patrascu, M. 2006. 维度缩减方法的最优性. 计算机科学基础:449-458; http://people.csail.mit.edu/mip/papers/eps2n/eps2n.pdf
Andoni, A., Indyk, P. Nguyen, H. L., Razenshteyn, I. 2013. 超越局部敏感哈希; http://arxiv.org/pdf/1306.1547.pdf.
Datar, M., Indyk, P., Immorlica, N., Mirrokni, V. S. 2004. 基于 p 稳定分布的局部敏感哈希方案; http://www.cs.princeton.edu/courses/archive/ spring05/cos598E/bib/p253-datar.pdf.
Gionis, A., Indyk, O., Motwani, R. 1999. 通过哈希实现高维度相似性搜索. 第 25 届国际超大型数据库会议论文集; 518-529; http://www.cs.princeton.edu/courses/archive/spring13/cos598C/Gionis. pdf.
Indyk, P., Motwani, R. 1998. 近似最近邻：消除维度灾难. 第 30 届 理论计算年会论文集：604-613; http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.249&rep=rep1&type=pdf.
Tyler McMullen (https://twitter.com/tbmcmullen) 是 Fastly (fastly.com) 的 CTO，在那里他负责系统架构并领导公司的技术愿景。作为创始团队的一员，McMullen 构建了 Fastly 的即时清除系统、API 和实时分析的第一个版本。在加入 Fastly 之前，他在 Scribd 从事文本分析和推荐工作。他自称是技术守旧派，在从 Web 设计到内核开发等各个领域都有经验，并且讨厌所有这些——尤其是分布式系统。
最初发表于 Queue 第 13 卷，第 8 期 —
在 数字图书馆中评论本文
更多相关文章
Catherine Hayes, David Malone - 质疑评估非加密哈希函数的标准
尽管加密和非加密哈希函数无处不在，但在它们的设计方式上似乎存在差距。出于各种安全要求，存在许多针对加密哈希的标准，但在非加密方面，存在一定程度的民间传说，尽管哈希函数历史悠久，但尚未得到充分探索。虽然针对现实世界数据集的均匀分布很有意义，但当面对具有特定模式的数据集时，这可能是一个挑战。
Nicole Forsgren, Eirini Kalliamvakou, Abi Noda, Michaela Greiler, Brian Houck, Margaret-Anne Storey - DevEx in Action
随着领导者寻求在财政紧缩和人工智能等变革性技术的背景下优化软件交付，DevEx（开发者体验）在许多软件组织中越来越受到关注。技术领导者们凭直觉接受，良好的开发者体验能够实现更有效的软件交付和开发者幸福感。然而，在许多组织中，为改进 DevEx 而提出的倡议和投资难以获得支持，因为业务利益相关者质疑改进的价值主张。
João Varajão, António Trigo, Miguel Almeida - 低代码开发生产力
本文旨在通过介绍使用基于代码、低代码和极端低代码技术进行的实验室实验结果，研究生产力差异，从而为该主题提供新的见解。低代码技术已清楚地显示出更高的生产力水平，为低代码在短期/中期内主导软件开发主流提供了强有力的论据。本文报告了程序和协议、结果、局限性和未来研究的机会。
Ivar Jacobson, Alistair Cockburn - 用例至关重要
虽然软件行业是一个快节奏且令人兴奋的世界，其中不断开发新的工具、技术和技巧来服务于商业和社会，但它也很健忘。在其快速前进的过程中，它容易受到时尚的支配，并且可能会忘记或忽略某些它面临的永恒问题的行之有效的解决方案。用例于 1986 年首次引入，后来普及，是这些行之有效的解决方案之一。
© 保留所有权利。