Papers We Love Too

This event is also on Luma.

Mini: Almog Gavra on "Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging"

Abstract: We show that all mainstream LSM-tree based key-value stores in the literature and in industry suboptimally trade between the I/O cost of updates on one hand and the I/O cost of lookups and storage space on the other. The reason is that they perform equally expensive merge operations across all levels of LSM-tree to bound the number of runs that a lookup has to probe and to remove obsolete entries to reclaim storage space. With state-of-the-art designs, however, merge operations from all levels of LSM-tree but the largest (i.e., most merge operations) reduce point lookup cost, long range lookup cost, and storage space by a negligible amount while significantly adding to the amortized cost of updates. To address this problem…We put everything together to design Dostoevsky, a key-value store that adaptively removes superfluous merging by navigating the Fluid LSM-tree design space based on the application workload and hardware. We implemented Dostoevsky on top of RocksDB, and we show that it strictly dominates state-of-the-art designs in terms of performance and storage space.

Bio: Almog is a co-founder at responsive.dev and a SlateDB committer, working on the most ambitious database project in history. He writes about how storage systems work on bitsxpages.com and occasionally draws an XKCD inspired comic with a snarky take on databases.

Main: Will Wilson on "Swarm Testing"

Abstract: Swarm testing is a novel and inexpensive way to improve the diversity of test cases generated during random testing. Increased diversity leads to improved coverage and fault detection. In swarm testing, the usual practice of potentially including all features in every test case is abandoned. Rather, a large “swarm” of randomly generated configurations, each of which omits some features, is used, with configurations receiving equal resources. We have identified two mechanisms by which feature omission leads to better exploration of a system’s state space. First, some features actively prevent the system from executing interesting behaviors; e.g., “pop” calls may prevent a stack data structure from executing a bug in its overflow detection logic. Second, even when there is no active suppression of behaviors, test features compete for space in each test, limiting the depth to which logic driven by features can be explored. Experimental results show that swarm testing increases coverage and can improve fault detection dramatically; for example, in a week of testing it found 42% more distinct ways to crash a collection of C compilers than did the heavily hand-tuned default configuration of a random tester.

Bio: Will Wilson is the CEO and co-founder of Antithesis, purveyors of the finest testing platform in the land. Before Antithesis, Will was an early engineer at FoundationDB and worked on Google Cloud Spanner.

RSVP to join us in person! If you can't make it live, join on Zoom - no RSVP needed. The agenda is also available online.

This event is also on Luma.

Main: Peter Corless on "In Search of an Understandable Consensus Algorithm"

Abstract: Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos; this makes Raft more understandable than Paxos and also provides a better foundation for building practical systems. In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforces a stronger degree of coherency to reduce the number of states that must be considered. Results from a user study demonstrate that Raft is easier for students to learn than Paxos. Raft also includes a new mechanism for changing the cluster membership, which uses overlapping majorities to guarantee safety.

Bio: Peter Corless is a Principal Product Marketing Manager at Redpanda Data, where he focuses on bringing AI, data streaming, and analytical services to market. Before Redpanda, Peter has worked across a broad spectrum of the data industry over the past decade - including distributed OLTP and OLAP databases, both SQL and NoSQL. In 2025, he wrote an O’Reilly book on Open Source Observability.

Mini: Rohan Puri on "Paxos vs Raft: Have we reached consensus on distributed consensus?"

Abstract: Distributed consensus is a fundamental primitive for constructing fault-tolerant, strongly-consistent distributed systems. Though many distributed consensus algorithms have been proposed, just two dominate production systems: Paxos, the traditional, famously subtle, algorithm; and Raft, a more recent algorithm positioned as a more understandable alternative to Paxos. In this paper, we consider the question of which algorithm, Paxos or Raft, is the better solution to distributed consensus…We find that both Paxos and Raft take a very similar approach to distributed consensus, differing only in their approach to leader election…We surmise that much of the understandability of Raft comes from the paper's clear presentation rather than being fundamental to the underlying algorithm being presented.

Bio: Rohan Puri is a Senior Staff Engineer at DDN working on DDN Infinia. He has 15+ years of experience building and optimizing file systems and distributed storage systems, and has contributed to storage systems at Samsung, Veritas, Oracle, and several startups. He also serves as Industry Co-Chair at MSST and on the Advisory Board of the Future Memory Storage conference.

RSVP to join us in person! If you can't make it live, join on Zoom - no RSVP needed. The agenda is also available online.