更多互联网新鲜资讯、工作奇淫技巧关注原创【飞鱼在浪屿】（日更新）

本文来自Varnish的开源HTTP加速器的作者于2010年发表。

该加速器是一个放置在慢速Web服务器前面的HTTP缓存。如今，各种各样的网站（从Facebook，Wikia和Slashdot）使用Varnish来掩盖您肯定从未听说过的网站。

作为FreeBSD内核的首席开发人员已经有15年的时间了，我进入了用户领域，对系统调用下会发生的事情有了详细的了解。我接受Varnish公司的主要原因之一就是展示如何编写高性能的服务器程序。

你们中的大多数人都做错了。不只是错在不完美的，但错在浪费一半以上的性能。

Varnish的第一个用户是大型的挪威报纸VG，用三台运行Varnish的机器代替了运行Squid的12台机器。Squid机器忙得不可开交100％，而Varnish机器有90％的CPU可用来做事情。

这个故事的简短版本是Varnish知道它不是在裸机上运行，​而是在提供基于虚拟内存的抽象机的操作系统下运行。例如，Varnish并不忽略内存是虚拟的这一事实。它积极地利用它。一个300 GB的后备存储区（通常是在不超过16 GB RAM的计算机上映射的内存）非常典型。用户支付了64位地址空间，我不怕使用它。

Varnish内部的一项特殊任务是，当虚拟生命周期耗尽时，将对象从缓存中过期淘汰。这就需要一种数据结构，该结构可以有效地传递总集合中最老的键控对象。

快速浏览目录就可以找到二进制堆，它不仅具有O（log2（n））处理性能的复杂度，而且元数据开销还包括指向每个对象的指针，这在以下情况下有1000万个以上的对象。

在最近的一次夜间火车到阿姆斯特丹的旅行中，我的想法徘徊了，令我震惊的是，努斯可能对二进制堆的性能产生极大的误导，甚至可能是一个数量级。在回家的路上，也在火车上，我写了一个模拟证明了我的直觉。

在任何原教旨主义CS理论家嗤之以鼻之前，我还没有发现Knuth等人的推理质量存在系统性缺陷。我们知道，CS的发现仍然是正确的。它们的相关性和实用性远不如您想象的那么好-至少在性能方面。

在计算机环境中，我找到的最早的二进制堆引用是JWJ Williams在1964年6月发行的ACM通讯上发表的文章，标题为“算法编号232-Heapsort”。麻烦的是，威廉姆斯已经失去联系了，他的算法分析甚至在出版之前就已经过时了。

在的1961年4月的一篇文章CACM， J. Fotheringham记录了计算机阿特拉斯曼彻斯特大学如何区分address和memroy location（VM， virtual memory），但是如今，，大多数嵌入式和许多专业操作系统都使用VM来向其管理的进程提供标准化的虚拟机模型（即POSIX）。

怪罪威廉姆斯没有意识到阿特拉斯已经使他的算法的一个默认假设无效是不公正和不合理的：只有后见之明才能使这种观察成为可能。然而，事实是，46年后，大多数受过CS培训的专业人员仍然无视VM。这对于CS作为一门学科和专业来说是一个尴尬，更不用说浪费大量的硬件和电力了。

性能模拟

聊够了。让我在桌子上放一些模拟的事实。图1中的图显示了64位计算机上100万个项目的二进制堆和我的新B堆版本的运行时间。c（我尊敬的FreeBSD同事Colin Percival很有帮助地指出，我对二进制堆所做的更改与从二进制树到B树的更改非常相似，因此我采纳了他的建议，并将我的新变种命名为B-堆）

x轴是VM压力，以不驻留在主内存中的地址空间量来衡量，因为内核将其分页到了辅助存储中。左y轴是运行时间，以秒为单位（对数刻度），右y轴显示两个运行时间的比率：（二进制堆/ B堆）。

让我们摆脱我的“数量级”要求。当我们放大到左侧时（图2），我们发现在几乎总VM压力下运行时，两种算法的时间确实存在10倍的差异：分配的1,954页中只有8至10页位于主内存在同一时间。

您是否只是确定我的数量级要求是虚假的，因为它仅基于极端情况？如果是这样，则您做错了，因为这几乎是现实世界中看到的行为。

在Varnish中创建和过期对象是相对少见的动作。创建对象后，对象通常会被缓存数周甚至数月，因此二进制堆甚至每分钟可能不会更新一次。在某些网站上甚至每小时都不发送一次。

同时，我们向客户的浏览器交付了千兆字节的对象，并且由于所有这些对象都在争夺主内存中的空间，因此包含未访问的binheap的VM页面将被调出。在仅驻留九个页面的最坏情况下，二进制堆平均每个操作11.5页传输，而B堆仅需要1.14页传输。如果您的服务器具有SSD（固态驱动器）磁盘，则每个操作之间的时间差为11或1.1毫秒。如果您仍然有旋转的机械盘片，它是110毫秒与11毫秒之间的差值。

在这一点上，想到“如果它每分钟只运行一次，即使花费一整秒，谁在乎呢？”是否是错误的呢？

实际上，我们确实很在意，因为每分钟需要在RAM中闲逛一分钟的10个额外的页面会停留一阵子，它们什么也不做，直到内核再次将它们分页出去，这时它们才能堆积在已经存在的顶部频繁的磁盘活动，通常在这种沉重的VM压力下在系统上看到。

接下来，让我们放大图的另一端（图3）。如果没有VM压力，则B堆算法比二进制排序需要更多的比较，并且简单的父子/子对父索引计算要花些时间：因此，而不是4.55的运行时秒，则需要5.92秒，这要慢30％，每项操作要慢近350纳秒。

因此，是的，Knuth和所有其他CS帅哥的数学运算正确。

但是，如果我们在曲线上向左移动，那么我们发现，在VM缺少四个页面（等于0.2％）的VM压力下，B堆由于VM页面故障较少而赶上了。并逐渐变得越来越好，直到如我们先前所见，它的峰值速度提高了10倍。

那是假设您使用的SSD磁盘可以在1毫秒内完成页面操作-相当乐观，尤其是对于写入操作。如果我们通过将I / O时间设置为仍然最佳的10毫秒来模拟机械磁盘（图4），则当内核从我们1,954页的工作中仅窃取一页时，B堆的速度将提高10％。如果缺少四页，则设置速度会提高37％。

那么，什么是B堆？

二进制堆和B堆之间的唯一区别是从子级中查找父级的函数，反之亦然。

传统的n-> {2n，2n + 1}公式给我们留下了一个由虚拟页面构成的堆，该虚拟页面在下一个页面上堆叠，这导致（几乎）所有垂直遍历在页面的上，下每一步都到达不同的VM页面树，如图5所示，每页八个项目。（数字显示对象分配的顺序，而不是键值。）

B堆通过垂直填充页面来构建树，以匹配我们遍历堆的方向（图6）。这种重新排列增加了保持树不变性所需的比较/交换操作的平均数量，但是确保了这些操作中的大多数都发生在单个VM页面内，从而减少了VM占用空间，从而减少了VM页面故障。

有两个细节值得注意：

一旦我们从底部离开一个VM页面，两个子节点都位于同一个VM页面中对于性能很重要，因为我们将把它们与它们的父节点进行比较。因此，该树在每次进入新的VM页面时都无法扩展一代，从而无法有效地使用页面中的前两个元素。

在我们的模拟示例中，如果不这样做，将需要五页以上的时间。

如果这对您来说不重要，那么您做错了：尝试将B堆线向图2和3中的右侧移动20 KB，然后思考其中的含义。

选择我的模拟参数来代表Varnish现实生活中发生的情况，而我并未尝试针对所有可能的参数全面表征或分析B堆的性能。同样，我也不排除存在将VM-线索添加到二进制堆中的更聪明的方法，但是我不倾向于在跨西伯利亚铁路上购买车票以寻找时间解决该问题。

差异的数量级显然源自每个VM页面内的堆级别数，因此最终的提速将在指针大小较小且页面大小较大的计算机上进行。这是一个相关的观察，因为操作系统内核开始使用超级页来跟上增加的I / O吞吐量。

那么，为什么您和我仍然做错了？

曾经有一个（著名的）辩论，即“ Quicksort vs. Heapsort”，它集中在以下事实上：前者的最坏情况表现很糟糕，而后者的平均表现却较差，但没有这种“坏点”。根据您的应用程序，这可能是非常重要的区别。

面对由虚拟内存，CPU缓存，写缓冲区和现代硬件的其他事实引起的各向异性内存访问延迟，我们对算法选择缺乏类似的查询。

无论您从中学习编程的那本书，它的前五页中都有一个图，它像图7所示那样描绘了一台计算机。

令人惊讶的是，它实际上是计算机教育中使用的唯一概念模型，尽管它几乎与现代计算机上的执行环境无关。仅作记录：现代，我的意思是VAX 11/780或更高版本。

过去30或40年的硬件和操作系统开发似乎只对CS部门的算法分析部分的议程产生了很小的影响，就我的轶事证据而言，它完全没有注册到他们提供的教育中。

Atlas计算机上的主存储和辅助存储之间的速度差异约为1：1,000。Atlas鼓花了2毫秒来传送一个扇区。指令执行大约需要2微秒的时间。对于每个VM页面错误，您丢失了大约1,000条指令。

在运行于几GHz时钟频率的现代多问题CPU上，最坏情况下的损失是每个VM页面错误将近1000万条指令。如果使用旋转磁盘运行，则该数字更像是1亿条指令。

如果O（log2（n））操作导致页面错误和磁盘操作缓慢，那么O（log2（n））算法有什么用？对于最相关的数据集，避免页面错误的O（n）或至O（n ^ 2）算法将在其周围运行圆圈。

算法的性能分析将永远是计算机科学的基础成就，并且像你们所有人一样，我非常珍惜《计算机编程艺术》第3卷中的磁带分类折叠表。但是，如果将CS部门的结果应用于真实计算机，而不仅仅是ZX81，C64和TRS-80之类的玩具，它的结果将变得更加有趣和有用。

问

代码实现：

有关的：

努尔Mubeen -负荷频率标度律-推导和验证

本文给出了一个相关的工作负载利用率缩放在每个DVFS子系统级别的方程式。在频率，利用率和比例因子（其本身随频率变化）之间建立了关系。验证这些方程式非常棘手，因为工作负载固有的利用率似乎在治理样本的粒度上以未指定的方式变化。因此，应用了一种称为直方图脊迹的新颖方法。将DVFS视为构建模块时，量化缩放影响至关重要。典型应用包括DVFS调速器和/或影响系统利用率，功率和性能的其他层。

西奥Schlossnagle -在DevOps的世界监控

监测似乎相当铺天盖地。要记住的最重要的事情是，完美绝不应该成为更好的敌人。DevOps可以在组织内部进行高度迭代的改进。如果您没有监控，那就得到一些东西。得到任何东西。事情总比没有好，并且，如果您已经接受了DevOps，那么您已经注册了，希望随着时间的推移变得更好。

乌兰Degenbaev，约亨·艾辛格，曼弗雷德·恩斯特，罗斯麦克罗伊，汉纳斯付款人-空闲时间的垃圾收集调度

谷歌的Chrome网络浏览器致力于提供流畅的用户体验。动画将以60 FPS（每秒帧）的速度更新屏幕，使Chrome大约有16.6毫秒执行更新。在这16.6毫秒内，必须处理所有输入事件，必须执行所有动画，最后必须渲染帧。错过最后期限将导致丢帧。这些对于用户是可见的，并且会降低用户体验。这种零星的动画伪像在这里称为“垃圾”。本文介绍了一种在Chrome浏览器使用的JavaScript引擎V8中实现的方法，该方法可以在Chrome浏览器处于空闲状态时安排垃圾回收暂停。

尼尔·冈瑟（Neil Gunther），保罗·普利亚（Paul Puglia），克里斯托弗·托马塞特（Kristofer Tomasette）-Hadoop超线性可扩展性

我们经常看到超过100％的加速效率！再次提醒您，您不能拥有超过100％的任何物品。但这只是软件工程师在有关如何根据加速指标量化计算机系统可伸缩性的演示中的第一个抽空。在不同的场合，随后的反驳似乎逐渐形成了一个名副其实的合唱团，不仅普遍观察到超线性加速，而且在过去20年中用于量化可伸缩性的模型在应用于超线性加速数据时也失败了。