The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors

PublishedProceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles

It appeared in a journal, conference or book, which normally review work before accepting it. Even so, one study is never the final word.

Abstract

What fundamental opportunities for scalability are latent in interfaces, such as system call APIs? Can scalability opportunities be identified even before any implementation exists, simply by considering interface specifications? To answer these questions this paper introduces the following rule: Whenever interface operations commute, they can be implemented in a way that scales. This rule aids developers in building more scalable software starting from interface design and carrying on through implementation, testing, and evaluation. To help developers apply the rule, a new tool named COMMUTER accepts high-level interface models and generates tests of operations that commute and hence could scale. Using these tests, COMMUTER can evaluate the scalability of an implementation. We apply COMMUTER to 18 POSIX calls and use the results to guide the implementation of a new research operating system kernel called sv6. Linux scales for 68% of the 13,664 tests generated by COMMUTER for these calls, and COMMUTER finds many problems that have been observed to limit application scalability. sv6 scales for 99% of the tests.

Research Analysis

Written by Kurz, not by the authors of the paper. The abstract above is the authors' own.

Last revised
Version
1.0

Overview

The usual way to find multicore bottlenecks is to pick a workload, plot throughput against core count and profile. The authors list the drawbacks: other workloads or more cores expose new bottlenecks, it is unclear which ones are fundamental (so developers may give up when a scalable solution exists), and it all happens late, when interface-level fixes may be impractical. Their earlier study An Analysis of Linux Scalability to Many Cores is an instance of that iterative design, implement, measure, repeat process (my reading), and this paper says that without a way to reason about interface-level scalability it is unclear which of Linux's remaining bottlenecks are inherent to its system call interface.

The paper moves the question up to the interface. It assumes a shared-memory multicore with MESI-like coherence: a core scales on data it holds exclusively or in shared mode, and writing a line last touched by another core does not scale. A set of operations therefore "scales" when their implementations are conflict-free, meaning no core writes a cache line that another core read or wrote. The formal model of actions and histories follows Linearizability (the paper cites Herlihy and Wing for it).

The paper calls itself complementary to work that uses commutativity for safety, such as commutative replicated data types (CRDTs): that work asks when concurrent execution is safe, this one asks when it scales. It also contrasts with multikernels such as The Multikernel, and sv6 itself uses RCU for lock-free readers.

Contribution

  • The scalable commutativity rule. In any situation where several operations commute, meaning there is no way to distinguish their execution order using the interface, they have an implementation whose memory accesses are conflict-free during those operations.
  • SIM commutativity. A state-dependent, interface-based and monotonic form of commutativity, so the rule applies to stateful interfaces like POSIX rather than only to unconditional commutativity.
  • A constructive proof, which the authors say is not practical to use as a real implementation.
  • Guidelines for commutative interfaces (Section 4). Decompose compound operations (posix_spawn instead of fork plus exec, an fstat that returns selected fields), embrace specification non-determinism (any unused file descriptor instead of the lowest), permit weak ordering (unordered sockets) and release resources asynchronously.
  • COMMUTER, made of ANALYZER, TESTGEN and MTRACE, and the sv6 kernel with its in-memory file system ScaleFS. sv6 also contains RadixVM, from earlier work by the same authors.

Methodology

Formalism. An execution is a history of invocations and responses by threads. A specification S is a prefix-closed set of well-formed histories. A region Y SI-commutes in H = X||Y when for any reordering Y' of Y and any continuation Z, X||Y||Z is in S if and only if X||Y'||Z is in S. SI commutativity is not monotonic: with a get/set interface, set(1), set(2), set(2) commutes while its prefix set(1), set(2) does not. Y SIM-commutes when every prefix of every reordering of Y SI-commutes. An implementation is a step function from a state and an invocation to a new state and a response, with CONTINUE actions for concurrency. A step writes a state component when it changes it and reads one when it can affect the step; two steps on different threads conflict when one writes what the other reads or writes.

Rule and proof. Given a specification with a correct reference implementation M and a history H = X||Y that M can generate with Y SIM-commutative, a correct implementation exists whose steps in Y are conflict-free. The construction first replays H from a shared history (which conflicts), then keeps a per-thread history and a per-thread commute flag, and on divergence rebuilds M's state by replaying invocations, possibly in a different order, which is safe because Y commutes.

COMMUTER. ANALYZER symbolically executes a Python model of the interface (with Z3), for every set of operations (typically pairs), in all orders, and outputs the conditions under which the return values and resulting states are equivalent. TESTGEN solves those conditions and emits C test cases, aiming at path coverage and at "conflict coverage" of different access patterns. MTRACE runs the OS in a modified qemu, logs each core's reads and writes, and reports conflicting accesses with the C type and stack traces. The model covers 18 file system and virtual memory calls and is 596 lines of Python plus 675 for test generation.

Findings

  • Linux 3.8 (ramfs and its VM). COMMUTER generated 13,664 tests, taking 8 minutes for generation plus runs on Linux and sv6. Linux is conflict-free for 9,389 (68%) and not for 4,275. Causes named: reference counts on struct dentry and struct file (even two fstat on one descriptor), a lock on the parent directory for any name-creating operation, and coarse locks in the virtual memory system. The per-call-pair counts are in Figure 6, a heat map that this summary does not transcribe.
  • sv6. Conflict-free for 13,528 tests (99%), leaving 136. ScaleFS uses per-core allocation, double-checked locking, RCU readers, Refcache and seqlocks, with patterns such as radix arrays, deferring work (inode numbers are never reused), checking optimistically before locking (lseek, rename) and not reading an inode when only existence matters (access).
  • The 136 cases. Mostly idempotent updates (two lseek to the same offset, two anonymous mmap with the same fixed address and permissions), pipe descriptor reference counts and reads of files full of identical bytes. The authors deliberately kept common-case speed instead.
  • Hardware (80 cores, eight 10-core Intel E7-8870, prefetcher off, mean of 3 runs, variance under 4%). With fstatx omitting the link count, statbench scales perfectly with zero L2 misses in fstatx, while fstat does not scale even with a shared counter (one L2 miss per call). At 80 cores fstat costs 3.9 times Linux's. openbench with O_ANYFD scales linearly and at one core open beats Linux by 27%. The mail server with commutative APIs reaches 7.5 times scalability from 10 to 80 cores, while the POSIX version collapses at a small core count. Absolute per-core throughputs are in Figure 7 only (graph reading, not transcribed).

Critical Analysis

What the paper claims is narrow. The rule says an implementation exists, not that it is easy, efficient or cheap to build: the proof's construction is "impractical", real systems use other techniques, and the paper says commutativity suffices but may not be necessary (a non-commutative interface can scale on some hardware). It also says that a set of commuting situations can have no single scalable implementation (its put/max example) and that conflict-free patterns can still fail to scale if they saturate the memory bus. It does not claim anything for distributed systems, only that generalizing should be possible.

The following points are my reading of the evidence, not claims of the paper.

  • sv6's 99% is partly by construction. The authors used COMMUTER to guide ScaleFS, so the score measures their own design loop. The Linux 68% is a more independent number, but for Linux 3.8 and ramfs only.
  • The model bounds the tests. Nested directories are disabled, sizes and offsets are page-granular, and the coverage of an implementation is only as good as its structural similarity to the Python model. Two systems (Linux and sv6) are the only cases.
  • The cost is not measured. sv6 is 51,732 lines of code, and the authors chose not to port ScaleFS to Linux because it touches code throughout the kernel. The paper gives no estimate of the effort for an existing kernel.

Later literature, not part of this paper: the extended version appeared in Communications of the ACM 60(8), 2017 (pages 83 to 90, doi, checked in Crossref metadata only, not read; the backlog item said 2015). By its catalog entry, CortenMM uses RadixVM as a baseline on 384 cores, but I only checked that catalog text, not CortenMM's paper.

Further Research

  • Generalizing the rule to distributed systems, where the paper hopes that a shared abstraction's interface can be related to the scalability of a message-passing implementation.
  • Which non-commutative interfaces still scale (the paper mentions strictly increasing time sources and interconnects that let some communication scale), and when conflict-free access does not scale.
  • Practical constructions for existing kernels, since sv6 is a new system and Linux is only evaluated.
  • Whether the Linux numbers hold on current kernels, which the paper does not evaluate.

Full text

Loading the paper…

Discussion · 0

No posts yet. Be the first to start the discussion.