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

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

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.