ACM通信

研究突出了

可扩展交换性规则:为多核处理器设计可扩展软件

奥斯汀·t·克莱门茨，m·弗兰斯·卡舒克，艾迪·科勒，罗伯特·t·莫里斯，尼克莱·泽尔多维奇
ACM通信，2017年8月，第60卷第8期，83-90页
10.1145 / 3068914
评论

开发在多核处理器上伸缩的软件是一门不精确的科学，主要依靠猜测、测量和昂贵的重新设计和重新实现周期。目前的方法是工作负载驱动的，因此只能揭示已知工作负载和可用软件和硬件的可伸缩性瓶颈。本文介绍了一种界面驱动构建可伸缩软件的方法。这种方法是基于可伸缩的交换性规则它非正式地表示，无论何时接口操作交换，它们都可以以可伸缩的方式实现。我们将此规则形式化，并证明它适用于任何具有无冲突操作规模的机器，例如当前的缓存相干多核机器。该规则还为可伸缩软件提供了更好的设计过程:程序员现在可以从接口定义的最初阶段，到软件设计、实现和评估，推断可伸缩性。

回到顶部

1.简介

直到2000年代中期，不断提高的CPU时钟速度使顺序软件在每一代新硬件中执行得更快。但更高的时钟速度需要更多的电力，产生更多的热量，在2005年左右，时钟速度达到了几平方厘米硅的散热极限。自那以后，CPU架构师并没有显著提高时钟速度，但可放置在芯片上的晶体管数量却持续上升。架构师现在通过在每个芯片上放置更多的CPU内核来提高并行性。总计每秒循环次数继续呈指数级增长，但软件必须规模必须利用并行CPU资源从这种增长中受益。

不幸的是，规模化仍然是一个无法解决的问题。即使经过仔细的工程设计，软件也很少能达到线性可伸缩性的圣杯，即硬件并行度翻倍会使软件性能翻倍。

工程可伸缩系统软件尤其具有挑战性。系统软件，如操作系统内核和数据库，通过定义良好的接口向应用程序提供服务。设计人员很少提前知道应用程序将如何使用这些接口，因此通常无法预测多核可伸缩性会出现什么瓶颈。此外，扩展瓶颈可能是接口本身定义的结果;一旦许多应用程序依赖于接口，这类问题就特别难以解决。

缺乏对可伸缩性进行推理的原则性方法阻碍了系统软件开发的所有阶段:定义接口、实现接口和测试其可伸缩性。

在定义接口时，开发人员缺乏一种系统的方法来决定给定的定义是否允许可伸缩的实现。演示可伸缩性瓶颈需要完整的实现和工作负载。当这些可用时，接口更改可能不再实际:许多应用程序可能依赖于现有的接口，触发瓶颈的应用程序可能不够重要，不需要进行接口更改。

在设计和实现过程中，开发人员缺乏一种系统的方法来发现可以实现完美可伸缩性的情况。这使得从一开始就很难设计一个可伸缩的实现。相反，随着时间的推移，当特定的工作负载发现瓶颈时，开发人员必须迭代地改进软件的并行性能，通常需要多次重新实现软件。

在测试时，开发人员缺乏评估可伸缩性的系统方法。测试多核软件的可伸缩性的技术现状是选择一个工作负载，绘制不同核数量下的性能图，并使用诸如差异分析之类的工具¹³确定该工作负载所显示的可伸缩性瓶颈。然而，每个新的硬件模型或工作负载都可能暴露新的可伸缩性瓶颈。

本文提出了一种设计可扩展软件的新方法，从设计可扩展软件接口开始。这种方法使得在实现存在之前，甚至在必要的硬件可用之前，就可以对多核可伸缩性进行推理。它可以突出固有的可伸缩性问题，导致更好的界面设计。它为可伸缩接口的实现设置了明确的伸缩目标。最后，它支持对实现的可伸缩性进行系统测试。

我们方法的核心是我们所说的可伸缩的交换性规则:在多次操作的任何情况下上下班(这意味着没有办法使用接口来区分它们的执行顺序)，存在这样一种实现无冲突在这些操作期间(意味着没有一个内核写被另一个内核读或写的缓存线)。由于无冲突操作按经验进行扩展(正如我们在第2节中讨论的那样)，因此此实现可扩展。因此,更简洁,无论何时接口操作交换，都可以以可伸缩的方式实现它们。

这个规则很直观:当操作交换时，它们的结果(返回值和对系统状态的影响)与顺序无关。因此，交换操作之间的通信是不必要的，避免它产生无冲突的实现。无冲突操作可以通过核间缓存一致性失效请求在不同核上执行，而不会相互干扰，允许总吞吐量随核数线性扩展。

该规则的直观版本在实践中是有用的，但不够精确，无法正式地推理接口或构建评估可伸缩性的自动化工具。本文形式化了可扩展交换性规则，并在几个例子中说明了它的用途，以及对于支持POSIX(一种广泛使用的复杂接口)的整个操作系统。

回到顶部

2.可伸缩性和Conflict-Freedom

可伸缩交换性规则假设具有无冲突内存访问的代码，即一个核所写的缓存线不能被其他核读或写的代码是可伸缩的。本节认为，在合理的假设下，无冲突操作在共享内存多核计算机上是线性扩展的。

多核使用类似于mesi的一致性协议来维护统一的、全局一致的内存视图。¹⁵MESI协议在缓存线级别协调缓存内存的所有权。它们的关键不变是，在一个核心缓存中具有可变副本的行不能出现在任何其他缓存中:获取一个可变副本将使其他缓存的不可变副本失效。这需要协调，这会影响可伸缩性。

图1显示每个缓存为每个缓存行实现的基本状态机。这通过确保缓存行在所有缓存中都是“无效的”，在一个缓存中是“修改的”，在所有其他缓存中是“无效的”，或者在任意数量的缓存中是“共享的”来维护不变式。实际的实现进一步增加了mesi的“独占”状态、Intel的“前进”状态和AMD的“拥有”状态，但这些都不会改变维持缓存一致性所需的基本通信。

图1。一个基本的缓存一致性状态机。“R”和“W”表示本地读写操作，“rR”和“rW”表示远程读写操作的响应。粗粗的红线表示引起通信的操作。细绿线表示在没有通信的情况下发生的操作。

粗略地说，当维持一致性时，一组操作的规模并不需要持续的沟通。有两种适合的内存访问模式:

• 多核读取和/或写入不同的缓存线。这是因为一旦每个缓存线都位于相关核心的缓存中，就不需要进一步的通信，因此进一步的访问可以独立于并发操作进行。
• 多个核读取相同的缓存线。线路的副本可以在共享模式下保存在每个核心的缓存中;来自这些核心的进一步读取可以在不通信的情况下访问线路。

也就是说，当内存访问无冲突时，它们不需要通信。此外，由无冲突读和写组成的高级操作本身是无冲突的，并且也将独立和并行地执行。在所有这些情况下，无冲突操作与它们并发执行的时间相同，因此的总吞吐量N这样的并发操作与N。因此，在MESI的完美实现下，无冲突操作线性扩展。

无冲突性并不是可伸缩性的完美预测指标。有限的缓存容量和结合性会导致缓存驱逐缓存线(后来导致缓存丢失)，即使在没有相干流量的情况下，一个核心第一次访问缓存线总是会丢失。这样的丢失会直接影响顺序的性能，但它们也可能影响无冲突操作的可伸缩性。满足缓存缺失(由于冲突或容量)需要缓存从另一个缓存或内存中获取缓存线;由此产生的通信可能与互连资源或内存控制器带宽的并发操作相竞争。但是具有良好缓存行为的应用程序不太可能有这样的问题，而缓存行为较差的应用程序通常有顺序的性能问题，这些问题超过了可伸缩性问题。我们已经在真实的硬件上验证了无冲突操作实际上在合理的工作负载假设下是线性扩展的。⁶

回到顶部

3.可扩展交换性规则

交换性和可伸缩性之间的联系以前已经被探讨过，特别是在抽象数据类型的操作上下文中。^{2，16，17，19，21，22}例如，交换复制数据类型¹⁹是分布式对象，其操作总是交换的，允许可伸缩的、无同步的实现。如果抽象数据类型操作总是产生相同的结果，无论顺序如何，那么它们就会交换。例如，set成员插入与自身交换，但不与删除:set.insert(i)和set.insert(j)以任何顺序产生相同的结果，如果i = j, set.insert(i)和set.remove(j)的结果是顺序相关的。但我们所关心的系统接口比典型的数据类型操作更丰富、更细粒度、更依赖状态和上下文。考虑POSIX创建系统调用，它创建一个文件。调用creat("/d1/x")和creat("/d2/y")似乎可以交换:无论应用的顺序如何，它们的结果都是相同的。但是，如果磁盘几乎已满，而只剩下一个inode，则调用不会进行交换——第二个create调用将失败。(除非，一个或多个文件已经存在，在这种情况下，调用终究是交换的!)像这样的特殊情况可以主导使用交换性强概念的分析。如果交换运算必须换入所有上下文，那么只有琐碎的系统操作可以交换，交换性不会帮助我们探索接口可伸缩性。

我们的工作依赖于交换性的一个新定义，叫做SIM交换性(依赖于状态、基于接口和单调)，它捕获依赖于状态和上下文的条件交换性，独立于任何实现。SIM交换性让我们可以证明可伸缩交换性规则，该规则表示只要操作交换，就存在可伸缩实现。即使接口仅在受限的上下文中是可交换的，也存在在该上下文中可扩展的实现。

本节的其余部分解释了这种形式主义，给出了精确的规则，并为系统设计人员列出了它的一些结果。

3.1.规范

我们使用行动，其中动作要么是调用(表示带有参数的操作调用)或响应(表示返回值)。将每个操作拆分为一个调用和一个响应，使我们能够建模阻塞接口和并发操作。¹¹每个调用都由特定的线程执行，相应的响应返回给相同的线程。我们将把调用写成create ("/x")₁和反应，其中横线标记响应，下标编号为线程id。

一个系统的特定执行是历史或跟踪，这只是一个动作的序列。例如,

由跨越三个不同线程的七个调用和七个相应的响应组成。在一个格式良好的历史中，每个线程的操作交替调用和响应，因此每个线程在任何点上最多有一个未完成的调用。H以上是格式良好的。例如，在线程受限的子历史中H| 1 = (₁，₁D₁，G₁，]，它选择1的动作H，调用和响应按预期交替进行。

一个规范将接口的行为建模为一组系统历史记录，具体地说，是一组前缀封闭的格式良好的历史记录。根据规范，如果系统执行的跟踪包含在规范中，则系统执行是“正确的”。例如,如果对应于POSIX规范(一个进程可以有PID 92)但是(getpid()系统调用可能不会返回该错误)。规范同时约束调用和响应₁没有在POSIX规范中，因为NtAddAtom不是POSIX系统调用。

一个实现是一个接受调用并计算响应的抽象机器。我们对可伸缩交换性规则的建设性证明使用了一类定义了冲突自由的机器⁶；一个很好的类比是具有随机访问磁带的图灵型机器，如果机器代表不同线程访问磁带的不连接部分，则冲突自由随之而来。实现可能会“断断续续”，需要多轮才能完成响应的计算，并且它不必按照接收调用的顺序生成响应。

一个实现M展品一段历史H如果,当美联储H在适当的时候，米可以生产H的响应(使其外部行为等于H整体)。一个实现米是正确的为规范如果米的反应总是遵守规范。这意味着每一段历史都由米要么是在，或者包含一些无效的调用。

3.2.交换性

我们在这里定义的SIM交换性，旨在捕获接口级别的状态依赖性。状态依赖性意味着当操作在某些状态下交换时必须捕获SIM交换性，即使这些相同的操作在其他状态下不交换;但是，我们希望在上下文环境中捕获它，而不参考任何特定的实现的状态。要原因可能的实现时，我们必须捕获接口本身固有的可伸缩性。这反过来又使得在软件开发早期，在界面设计和初始实现期间使用可伸缩交换性规则成为可能。

交换性表示动作可以重新排序而不影响最终结果。我们说历史H”是一个重新排序的H当H|t＝H”|t为每一个线程t。这允许跨线程重新排序动作，但不能在线程内部重新排序。例如,如果H= (₁B₁，₁C₁，，),然后(B₂，,一个₁，₁C₁，的重新排序H,但B₂C₁，，,一个₁，₁不是的，因为它不尊重行动的顺序H| 1。

现在，我们来看看历史H＝XY(其中连接动作序列)。我们说Y SI-commutes在H当给出任何重新排序Y '的Y，以及任何动作序列Z，

该定义捕获接口级别的状态依赖性。动作序列X将系统置于特定的状态，而不指定该状态的表示(这将依赖于实现)。切换区域Y而且Y '要求精确的响应Y根据规范保持有效，即使Y重新排序。区域的存在Z在这两种历史中，都要求对区域内的行动进行重新排序Y不能通过未来的操作来区分，这是一种基于接口的说法Y而且Y '保持系统处于相同的状态。

不幸的是，SI交换性不足以证明可伸缩交换性规则。为了避免某些退化的情况，我们必须进一步强化交换性的定义单调(SIM中的M)。一个操作序列Y SIM-commutes在一个历史H＝XY当任何前缀P任何重新排序的Y(包括P＝Y)，PSI-commutes在XP。等价地，Y sim通勤H当，给定任何前缀P任何重新排序的Y,任何重新排序P '的P，以及任何动作序列Z，

SI交换性和SIM交换性都捕获了状态依赖性和接口基础。与SI交换性不同，SIM交换性排除了区域交换性取决于未来操作的情况。SIM交换性是我们需要陈述和证明的可扩展交换性规则。

3.3.规则

我们现在可以正式地陈述可扩展交换性规则。

假设有一个接口规范它有正确的实现和历史H＝XY通过这个实现来展示。每当YSIM-commutes在H，存在一个正确的实现的步骤Y无冲突。由于给定合理的工作负载假设，无冲突操作可以在现代多核硬件上进行经验扩展，因此该实现在Y．

我们的规则证明从正确的参考实现构建了可伸缩的实现，并依赖于抽象的机器定义和冲突自由的定义。⁶

3.4.例子

考虑一个包含四个操作的引用计数器接口。reset(v)将计数器设置为特定值v, inc和dec对计数器递增或递减并返回其新值，isz如果计数器值为0则返回Z，否则返回NZ。调用者被期望永远不会递减到0以下，一旦计数器达到0，调用者就不应该调用inc。

考虑计数器的历史

该地区H₁SIM-commutes在H，因此该规则告诉我们存在一个正确的实现，它是无冲突的H₁．事实上，一个简单的共享计数器实现已经是这样:它的isz读取共享计数器，但不写入它。

但H₂不是sim通勤吗H因此，没有可扩展的实现，事实上，没有一个是可能的。问题是调用者可以通过dec返回值来推断顺序。只有一个退化的实现，例如拒绝响应某些请求的实现，才能避免以无冲突的方式跟踪此顺序。

我们可以通过消除dec的返回值来使其通勤。如果我们修改规范，使inc和dec不返回任何东西，那么任何专门由这些操作组成的区域将在任何历史记录中交换。的一个版本H修改后的规格是

H＇₂,不像H₂， sim通勤，所以必须有一个无冲突的实现。每线程计数器为我们提供了这样的实现:每个dec可以修改其本地计数器，而isz对每线程值求和。像这样的数据结构的每线程和每核分片是可伸缩实现中常见且长期存在的模式。

这条规则至少强调了这段历史上的另一个机会。H＇_3.也SIM-commutesH．但是，每线程计数器实现并不是无冲突的H＇_3.: 12月_3.是否写入状态的一个被isz读取和求和的组件₁和isz₂．但是，同样，有一个基于添加布尔“零”快照和每个线程计数器的无冲突实现。Isz只是返回这个快照。当dec将每个线程的值减少到零或以下时，它将读取并求和所有每个线程的值，并在必要时更新快照。

3.5.讨论

该规则将状态和历史依赖性推到了极致:它对一个单历史。在广泛交换的接口中，一组操作交换的参数和系统状态通常分解为定义良好的类(例如，只要包含的目录不同，文件创建就可能交换)。在实践中，实现可扩展到整个状态和参数类，而不仅仅是特定的历史。

另一方面，实现的扩展范围也有限制。有时，一组操作在多个类的情况下交换，但没有一个实现可以伸缩到所有类。例如，在我们修改过的引用计数器中，H＇₁，H＇₂,H＇_3.所有SIM-commuteH，我们描述了针对每种情况的可伸缩实现。然而,H＇₄不进行sim交换，即使它是一个sim交换块的联合:如果两个dec操作被重新排序到区域的开始，那么isz操作将必须返回不同的值。任何合理的反执行都必须无法向内扩展H＇₄，因为isz必须根据它是在dec调用之前还是之后运行而返回不同的值，这需要在运行dec和isz的内核之间进行通信。这可以用规则的反方向来证明:当历史记录中包含一个非sim交换区域时，在该区域中没有非简并实现可以伸缩。⁶(非简并条件消除了一些实现，例如从不响应任何调用，或总是响应一个错误返回值。)

在我们的经验中，真实的接口操作很少演示这种互斥的实现选择。例如，第5节中的POSIX实现扩展非常广泛，只有少数情况需要不兼容的实现。

回到顶部

4.定义交换接口

本节将使用POSIX(类unix操作系统的标准接口)演示该规则启用的接口级推理的更多情况。

下面的部分将探讨使POSIX操作在更多的情况下可交换的四种一般类型的更改，从而支持更多可伸缩的实现。

4.1.分解复合操作

许多POSIX api将多个操作合并为一个，限制了组合操作的交换性。例如，fork既创建一个新进程，又快照当前进程的整个内存状态、文件描述符状态、信号掩码和其他一些属性。因此，fork无法与同一进程中的大多数其他操作进行交换，包括内存写、地址空间操作和许多文件描述符操作。然而，应用程序经常在fork之后使用exec，它撤消fork的大多数子操作。只有fork和exec，应用程序被迫接受这些限制交换性的不必要的子操作。POSIX有一个posix_spawn调用，它通过创建一个进程并直接加载图像来解决这个问题(Windows中的CreateProcess类似)。这相当于fork后面跟着exec，消除了对fork的许多子操作的需要。因此，posix_spawn可以与大多数其他操作交换，并允许广泛的可伸缩实现。

另一个例子是stat，它同时检索和返回文件的许多不同属性，这使得它与在同一文件上更改stat返回的任何属性的操作(如link、chmod、chown、write甚至read)不可交换。在实践中，应用程序仅为一个或两个返回字段调用stat。另一种让应用程序控制返回哪个或哪个字段的API将与更多操作进行交换，并支持stat的更可伸缩的实现。⁶

POSIX还有许多其他复合返回值的例子。Sigpending返回所有挂起的信号，即使调用者只关心一个子集;select返回所有就绪的文件描述符，即使调用者只需要其中一个。

4.2.接受规范非确定性

POSIX要求打开的系统调用为新打开的文件返回编号最低的未使用文件描述符(FD)。这条规则是导致可伸缩性差的过度确定性设计的典型例子。由于这一规则，同一进程中的开放操作(以及任何其他FD分配操作)不会交换，因为它们执行的顺序决定了返回的FD。应用程序很少需要此约束，可以返回任何未使用FD的替代接口可以使用众所周知的可伸缩分配方法。许多其他POSIX接口都能做到这一点:mmap可以返回任何未使用的虚拟地址，而create可以将任何未使用的inode号分配给新文件。

4.3.允许弱排序

交换性受限的另一个常见原因是操作之间严格的排序要求。对于许多操作，排序是自然的，并保持接口易于使用;例如，当一个线程向一个文件写入数据时，其他线程可以立即读取该数据。这样的同步操作自然是非交换的。另一方面，通信接口通常强制执行严格的排序，但可能不需要这样做。例如，大多数系统命令所有消息通过本地Unix域套接字发送，即使在使用SOCK_DGRAM，因此在同一个套接字上的任何send和recv系统调用都不会交换(除非在错误条件下)。这通常是不必要的，特别是在多读取器或多写入器的情况下，只要套接字上有足够的空闲空间和足够的挂起消息，不强制排序的替代接口将允许send和recv交换。反过来，这将允许Unix域套接字的实现支持可伸缩通信。

4.4.异步释放资源

一个密切相关的问题是，许多POSIX操作具有全局效应，在操作返回之前必须可见。对于可用的接口来说，这通常是很好的设计，但是对于释放资源的操作来说，这通常比应用程序需要的更严格，而且确保成本也很高。例如，写入管道必须交付SIGPIPE如果该管道没有读FD，则立即执行，因此管道写操作不会与读FD的最后一个关闭进行交换。这需要积极地跟踪读取fd的数量;一个承诺最终交付SIGPIPE的宽松规范将允许实现使用更可伸缩的读FD跟踪。类似地，munt -map不与其他线程对未映射区域的内存读写进行交换，因为在munt -map返回后，其他线程不应该能够对未映射区域进行写操作(尽管依赖这种行为通常表明存在错误)。实际上，执行这一点需要远程TLB停机，这在今天的硬件上是无法扩展的。异步释放虚拟内存的munmap(或madvise)将允许内核懒懒地回收物理内存并批量处理或消除远程TLB停机。

另一个例子是，要构建一个可伸缩的引用计数器，我们从3.4节中描述的接口开始:inc和dec都不返回任何东西，因此总是交换。在isz操作的地方，我们引入了一个新的检查操作，它查找引用计数最近为零的所有对象;这使开发人员不必自己定期调用isz。审查不以任何顺序通勤任何对象的引用计数已达到零，即使它进行了交换，它的实现也会在少量缓存行上发生冲突。然而，与dec不同的是，用户可以选择调用复查的频率。更频繁的调用会更快地清理释放的内存，但会导致更多的冲突。在我们实现这个称为Refcache的方案时，⁷复查每隔10毫秒调用一次，这比当前多核上最昂贵的冲突所需的时间要长好几个数量级。

回到顶部

5.设计Conflict-Freedom

为了评估上一节交换接口的实现难度，我们构建了sv6，这是一个研究性操作系统，旨在提供具有尽可能多可伸缩性的类posix接口。sv6包含一个类似ramfs的内存文件系统，称为ScaleFS⁸以及一个名为RadixVM的虚拟内存系统。⁷在设计和实现sv6时，该规则告诉我们，在许多情况下无冲突实现是可能的，这迫使我们提出实现无冲突的设计。如果没有这条规则，我们就会过早放弃，认为一些极端情况根本无法按比例进行。

实现无冲突的问题可分为两大类。一方面，我们发现从多个核访问单个逻辑对象(如引用计数器、内存池或调度器队列)的情况。在这里，我们通常为API的可交换部分使用单核数据结构，并试图确保极少调用API的非交换部分(例如协调每核引用计数，或在一个核心耗尽时从其他核心窃取空闲内存页或可运行线程)，并在调用它们时尽量减少缓存线移动。在某些情况下，这需要设计新的算法，如Refcache。

另一方面，我们也遇到了访问逻辑上不同的对象(例如，目录中的文件，或虚拟地址空间中的页面)的情况，但通常用于访问这些对象的数据结构导致了不必要的冲突。特别是，我们发现许多复杂的数据结构，如红黑树、扩展树、AVL树、并发无锁跳过表等，都不太适合可伸缩交换性规则。例如，二叉树上的平衡操作具有非本地影响:在一个分支上的操作可能导致树的大部分发生冲突。无锁跳过表和其他无锁平衡查找数据结构避免了锁定，但仍然会在应该交换的操作上引发冲突:插入和删除进行非本地内存写操作以保持平衡(或等效的操作)，而这些写操作与交换查找冲突。这些冲突对绩效的影响可能是戏剧性的。一个常见的解决方案涉及到切换到基于数组的数据结构，这往往自然地有助于避免交换操作的冲突。例如，使用数组表示进程打开的文件描述符，自然为不同文件描述符上的操作提供了无冲突性，因为这些操作访问数组中的不同地址。

朴素数组不适用于键空间很大的情况。对于中等大小的键，一个解决方案是使用基树。例如，我们在sv6虚拟内存系统RadixVM中使用基树，⁷实现从虚拟地址到相应映射对象的映射。由于基树没有平衡操作，对不同地址的访问往往不会冲突。与此同时，基树中的简单压缩技术允许更紧凑的表示，这比单一的平面数组更有效。

对于大型或可变大小的键，哈希表是一个自然的选择。例如，在sv6文件系统中，我们使用哈希表来表示每个目录。这意味着对单个目录中不同文件名的并发操作不太可能发生冲突(除非它们映射到同一个哈希表桶)。这与传统的文件系统设计形成对比，传统的文件系统设计采用单一锁，以确保操作不会同时修改相同的目录条目。

回到顶部

6.测试Conflict-Freedom

完全理解一个复杂接口的交换性是很棘手的，检查一个实现是否在操作交换时实现了冲突自由，这为本已困难的任务增加了另一个维度。为了帮助开发人员在测试期间应用规则，我们开发了一个名为“通勤者”的工具，它可以自动完成这个过程。⁶首先，通勤者采用一个接口的符号模型，并计算该接口的操作何时交换的精确条件。其次，通勤者使用这些条件生成根据接口模型交换的操作集的具体测试，因此根据交换性规则应该具有无冲突的实现。第三，通勤检查每个测试用例的特定实现是否无冲突。开发人员可以使用这些测试用例来理解他们应该考虑的交换用例，迭代地发现并修复代码中的可伸缩性瓶颈，并执行回归测试以确保可伸缩性错误不会随着时间的推移而渗透到实现中。

为了说明通勤如何帮助测试可伸缩性，我们编写了一个POSIX接口的符号模型，包括文件系统和虚拟内存操作，并针对Linux和sv6操作系统检查结果测试用例。结果显示在图2而且3.,分别。每个方格表示一对系统调用。每个方格的颜色表示尽管是可交换的，但仍不能无冲突的测试用例的比例。

图2。在Linux 3.8中交换系统调用对的无冲突性，显示了由通勤产生的测试用例的比例和绝对数量不每个系统调用对无冲突。

图3。sv6交换系统调用对的无冲突性。

在Linux的情况下，我们可以看到内核已经具有相当大的可伸缩性:对于由通勤者生成的所有测试，许多对系统调用是无冲突的。然而，也有许多成对的通勤，但并不是没有冲突。这表明，即使是一个成熟的、可合理伸缩的操作系统实现也会错过许多根据交换性规则可伸缩的情况。其中一些与Linux中众所周知的可伸缩性问题相对应，例如对同一目录中不同文件名的并发操作(在每个目录锁上发生冲突)或对虚拟内存子系统的并发操作(在每个地址空间锁上发生冲突)⁷)．其他的则是以前可能没有发现的新瓶颈:通勤者系统地发现了潜在的可伸缩性问题。

与Linux相比，sv6对于几乎每一个交换测试用例都是无冲突的。部分原因是我们选择了自然无冲突的数据结构，如上一节所述。在测试sv6时，通勤者还发现了许多我们自己没有想到的交换角情况。例如，考虑重命名系统调用和访问系统调用，它们可用于检查文件是否存在。假设有两个现有的文件，a和b。通勤者发现重命名(a, b)与访问(b)交换，因为在任何一个顺序中，重命名都成功，访问指示b存在。然而，我们的初始实现并不是无冲突的，因为访问使用了一个内部函数，该函数不仅检查文件是否存在，还查找文件的inode。为了避免冲突，我们引入了一个单独的函数来检查目录哈希表中是否存在文件名，而不实际读取文件名对应的值。在测试期间，我们发现了许多其他常见的设计模式，例如尽可能延迟工作，在悲观(即写入内存位置)之前使用乐观只读检查，以及除非绝对必要，否则避免读取。

对于少数交换运算，sv6不是无冲突的。这些情况中的大多数都涉及到对内部状态的幂等更新，例如两个lseek操作都寻找一个具有相同偏移量的文件描述符，或者两个具有相同固定基址和权限的匿名mmap操作。虽然可伸缩性地实现这些功能是可能的，但是我们考虑的每一个实现都会显著地降低更常见操作的性能，因此我们明确地选择在总体可伸缩性之上优先考虑通用情况的性能。其他情况则代表有意的工程决策，目的是对内存消耗和顺序性能的实际约束。复杂的软件系统不可避免地涉及相互冲突的需求，可伸缩性也不例外。然而，规则的存在迫使我们明确地认识、评估和证明我们在哪里做了这样的权衡。

回到顶部

7.讨论

该规则的一个令人惊讶的方面是，它允许我们推理可伸缩性，而不必测量系统的吞吐量作为核心数量的函数。事实上，这篇论文没有包含这样的图表。为了确保我们的规则在实践中有效，我们使用交换系统调用来测量在sv6上运行的邮件服务器的可伸缩性。结果是完美的可伸缩性。一方面，这证明了该规则的力量:即使对于以前没有测试过的硬件系统和工作负载，我们也能够自信地预测可伸缩性。另一方面，可伸缩性并不等同于性能，一个完全可伸缩的实现可能比在少量核上调优效率的实现具有更低的总体性能。

扩大该规则的影响范围并为可伸缩的实现创造更多机会的一个潜在方法是找到这样的方法nonconflict-free操作可以扩展。例如，由于互连和内存争用，流计算通常不是线性可扩展的，但我们已经成功地实现了可扩展互连感知流计算。这些计算将线程放在内核上，以便线程之间的共享结构与硬件互连的结构相匹配，并且不会出现链接过度订阅的情况。在一个80核的x86系统上，在映射到硬件互连的环上重复移动令牌，无论环上有多少核，都能实现相同的吞吐量，即使每个操作都会导致冲突和通信。将计算映射到这个模型可能是困难的，并且考虑到多核互连的变化结构，模型本身可能无法推广。然而，这个问题与数据中心的就业安置密切相关，可能也适用于类似的方法。同样，不断发展的数据中心网络结构可以为多核互连的设计提供信息，从而支持更可伸缩的计算。

回到顶部

8.相关工作

本节简要说明可伸缩交换性规则与先前探讨可伸缩性和交换性的工作之间的关系。关于相关工作的更深入的讨论，也包括可扩展的操作系统和测试方法，我们建议读者参考Clements的论文。⁶

8.1.可伸缩性

以色列和导演奖。¹²引入分离存取并行存储器系统的概念。粗略地说，如果一个共享内存系统是互不连接的并行访问，并且一组进程访问互不连接的内存位置，那么这些进程就会线性扩展。与交换性规则一样，这是一种有条件的可伸缩性保证:如果应用程序以特定的方式使用共享内存，那么共享内存实现将伸缩。然而，当分离访问并行性专门用于内存系统接口时，我们的工作包含了任何软件接口。提亚等。^3.扩展israel和Rappoport的定义，额外要求不间断读数按比例。我们的工作建立在这样的假设上，即内存系统的行为是这样的，我们已经证实，真正的硬件非常接近这种行为。⁶

最初的分离访问并行论文和后续的工作¹⁸探索具有一定数量的非分离共享的进程的可伸缩性，例如共享缓存线或共享锁上的比较-交换指令。我们的工作是非黑即白的，因为我们发现，在真正的硬件上，单个经过修改的共享缓存线会破坏可伸缩性。

秩序的法则²探讨接口的“强非交换性”与该接口的任何实现是否必须包含原子和/或栅栏指令以实现正确的并发执行之间的关系。这些指令通过干扰无序执行来降低执行速度，即使没有内存访问冲突。秩序定律类似于交换性规则，但得出的结论是关于顺序性能，而不是可伸缩性。

众所周知，缓存线争用会导致糟糕的可伸缩性。一个明显的例子是MCS锁的设计，¹⁴它避免了特定缓存线的争用，从而消除了可伸缩性崩溃。其他好的例子包括可伸缩参考计数器。^1，5，9交换性规则建立在这种理解的基础上，并确定何时任意接口可以避免冲突的内存访问。

8.2.交换性

使用交换性来增加并发性已经得到了广泛的探索。Steele描述了一种并行编程规程，其中所有的操作要么是因果相关的，要么是交换的。²¹他的工作将交换性近似为冲突自由。我们证明交换运算总是有一个无冲突的实现，这意味着Steele的模型是广泛适用的。想一想Rinard和迪尼斯那样不知满足、¹⁷描述如何利用交换性来自动并行化代码。它们允许内存冲突，但生成同步代码以确保交换操作的原子性。类似地，Prabhu等人。¹⁶描述如何使用手动注释而不是自动交换性分析自动并行化代码。里纳德和普拉布的研究重点是安全同时执行交换操作。这为业务提供了扩大规模的机会，但并不能确保它们一定会扩大规模。我们的工作直接聚焦于可伸缩性:我们展示了任何并发的交换操作都具有可伸缩的实现。

数据库社区长期以来一直使用逻辑读集和写集、冲突和执行历史来推断如何在保持可序列化性的情况下交叉事务。⁴Weihl将这项工作扩展到抽象数据类型，从操作的可交换性推导出锁冲突关系。²²事务提升在软件事务内存上下文中应用了类似的技术。¹⁰夏皮罗等。^19，20.将此扩展到分布式设置，在复制数据类型的设计中利用交换操作，在故障和网络分区期间支持更新。与Rinard和Prabhu的工作一样，数据库及其扩展的工作主要关注并发执行交换操作的安全性，而不是直接关注可伸缩性。

回到顶部

9.结论

可伸缩交换性规则帮助开发人员在软件设计的所有三个阶段中推理可伸缩性:定义接口、设计和实现软件，以及测试其可伸缩性属性。该规则不要求开发人员有一个目标工作负载或一台物理机器来推断可伸缩性。我们希望程序员们会发现交换性规则在生产可根据设计伸缩的软件时是有帮助的。

回到顶部

致谢

本研究得到了NSF奖项SHF-964106和CNS-1301934、广达和谷歌的支持。艾迪·科勒获得了微软研究新教员奖学金和斯隆研究奖学金的部分支持。

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2017 ACM, Inc.

---

没有发现记录