Strange Loop

Addressing the parallelism gap in replicated server systems

Over the past decade, server hardware has been characterized by an increasing number of CPU cores. Consequently, researchers and practitioners have developed a variety of sophisticated techniques, such as lock-free algorithms and futures, to scale server software on multicore hardware.

At the same time, applications need high availability via replication. A replicated system consists of a primary server and one or more backup servers, such that a backup is a faithful copy of its primary. The primary is responsible for processing update requests, which are periodically sent and applied to backups. Unfortunately, techniques to scale software on multicore systems are non-deterministic, and thus do not ensure that a primary and its backups will remain in-sync, even if they process precisely the same set of inputs in the same order. As a consequence, primaries can employ multicore scalability optimizations, while backups must sequentially execute a stream of updates from the primary. This "parallelism gap", manifesting as replication lag, has been a longstanding issue with several systems in widespread use, including MySQL and PostgreSQL.

To address this parallelism gap, I will describe how we can apply techniques from deterministic scheduling in databases systems to provably guarantee that backups process updates with at least as much parallelism as primaries, consequently increasing the utility of backups in serving fresh reads, and decreasing fail-over times.

Jose Faleiro

Yale University

Jose Faleiro is a fifth-year computer science PhD candidate at Yale University, where he works on building robust and performant large-scale concurrent systems. His PhD research focusses on using deterministic execution to simplify isolation and recovery in main-memory multi-core database systems. In addition to his research at Yale, Jose has worked on geo-distribution in the Orleans cloud programming framework (at Microsoft Research Redmond), and DebugAdvisor, a debugging tool that leverages a large software repository's history of changes (at Microsoft Research India). He has an undergraduate degree in computer science from the Birla Institute of Technology and Science (BITS), Pilani.