On the Scalability of the Erlang Term Storage
📜 Abstract
The Erlang Term Storage (ETS) is an important component of the Erlang runtime system, especially when parallelism enters the picture, as it provides an area where processes can share data. It is therefore important that ETS’s implementation is efficient, flexible, but also as scalable as possible. In this paper we document and describe the current implementation of ETS in detail, discuss the main data structures that support it, and present the main points of its evolution across Erlang/OTP releases. More importantly, we measure the scalability of its implementations, the effects of its tuning options, identify bottlenecks, and suggest changes and alternative designs that can improve both its performance and its scalability.
✨ Summary
Summary
The paper analyzes the implementation and multicore scalability of Erlang Term Storage (ETS), a shared in-memory key-value facility used by Erlang processes and by systems such as Mnesia. It explains how ETS manages copied Erlang terms, table metadata, ownership, fixation for safe traversal, and synchronization.
The study compares hash-based set tables and AVL-tree-based ordered_set tables across Erlang/OTP releases R11B-5, R13B02-1, R14B, and R16B. It shows that hash-based tables benefit substantially from fine-grained locking enabled by write_concurrency, while global locking makes ordered_set tables scale poorly under mixed lookup/update workloads. Reader groups introduced in R14B reduce contention caused by shared reader counters, but their optimal number depends on workload and hardware.
A major bottleneck is identified in the AVL-tree implementation: a shared statically allocated traversal stack causes cache-line migration between schedulers, harming lookup-only scalability. Replacing it with dynamic stacks substantially improves ordered_set performance. The experiments also show that increasing the number of hash-table bucket locks improves scalability until synchronization and memory overhead outweigh the benefit, motivating per-table runtime configurability.
The paper evaluates alternative designs, including a concurrent skip list, C++’s std::unordered_set, lock-free hash tables, split-ordered lists, concurrent B-trees, and more scalable metadata-locking schemes. The concurrent skip list provides better scalability than the AVL tree for mixed workloads but has poor sequential performance, partly because of memory-reclamation overhead. The authors conclude that ETS performance involves trade-offs among feature support, synchronization granularity, memory use, workload characteristics, and hardware topology.
Influence and subsequent development
The paper’s benchmark methodology and analysis of ETS synchronization are cited in later work on scalable Erlang runtime synchronization; subsequent research reused ets_bench and explicitly refers to this paper when evaluating ETS scalability. (researchgate.net) The paper’s concerns about contention in shared counters and lock granularity also align with later Erlang/OTP engineering work. In 2021, the Erlang/OTP team documented the decentralized_counters option, introduced in OTP 22 for ordered_set and OTP 23 for other table types, reporting substantially improved scalability for concurrent ETS updates while documenting the trade-off of slower table-size and memory queries. (erlang.org)