CSR: Medium: Collaborative Research: The Commutativity Rule for Scalable Systems Software

经过几十年的可靠改进，处理器速度已经趋于平缓；在可预见的未来，计算机将通过增加更多处理器而不是更快的处理器来增加处理能力。这对软件设计者来说是一项艰巨的挑战。对于使用多个处理器的软件来说，将越来越多的可用处理能力消耗在像锁定这样的协调开销上太容易了，而不是实际的工作。也就是说，对于没有规模的软件来说太容易了：随着处理器的增加而变慢。而这一点的一个重要叛逆就是人们对可伸缩性的理解很少。有些程序之所以不能伸缩，是因为它们编写得很糟糕，而另一些程序之所以不能伸缩，是因为它们的目标根本不可能以可伸缩的方式实现。程序员缺乏有效的工具来对软件可伸缩性限制进行高级推理，因此在不可能和无趣的任务上都浪费了精力。我们将产生第一个具有良好基础和形式化的可伸缩性推理过程，该过程足够灵活，可以应用于整个操作系统。我们的可伸缩性规则将交换性和可伸缩性联系在一起。我们将软件接口描述为或多或少固有的可伸缩性，这取决于这些接口交换的上下文：接口的交换性越强(也就是说，其函数调用的顺序越不重要)，实现的可伸缩性就越强。我们证明了对任何可交换的上下文都存在可伸缩的实现。这个想法已经可以指导软件设计人员开发可轻松扩展的接口，但我们还将提供一套自动化工具来衡量接口的交换性和寻找实现的可伸缩性瓶颈，并在高度可伸缩的操作系统中评估我们的想法。由此产生的工具和想法可以使可伸缩软件更容易设计和编程，从而帮助软件设计者提供如此多的经济所依赖的软件性能。

After decades of reliable improvement, processor speeds haveflattened; for the foreseeable future, computers will add processingpower by adding more processors, rather than faster ones. This is atremendous challenge for software designers. It's far too easy forsoftware using multiple processors to burn up a growing fraction ofavailable processing power on coordination overheads like locking,rather than actual work. That is, it's far too easy for software tonot scale: to get slower as processors are added. And an importantreason for this is simply that scalability is poorly understood. Someprograms don't scale because they're badly written, but others don'tscale because their goals are fundamentally impossible to accomplishin a scalable way. Programmers lack effective tools for high-levelreasoning about software scalability limitations, and thus wasteeffort on both impossible and uninteresting tasks.We will produce the first well-grounded and formal reasoning procedurefor scalability that is flexible enough to apply to an entireoperating system. Our scalability rule links commutativity andscalability. We characterize software interfaces as more or lessinherently scalable depending on the contexts in which thoseinterfaces commute: the more commutative an interface (that is, themore often the order of its function calls doesn't matter), the morescalable an implementation can be. We prove that a scalableimplementation exists for any commutative context. This idea canalready guide software designers in developing easily-scalableinterfaces, but we will also provide a set of automated tools formeasuring interface commutativity and for finding implementationscalability bottlenecks, and evaluate our ideas in a highly-scalableoperating system. The resulting tools and ideas could make scalablesoftware far easier to design and program, and thus help softwaredesigners provide the software performance on which so much of oureconomy depends.