"Addressing the parallelism gap in replicated server systems" by Jose Faleiro

### Overview In this talk, Jose Faleiro addresses the tension between two critical requirements in modern server systems: exploiting multi-core parallelism and maintaining high availability through replication. While multi-core systems (ranging from cloud instances with 128 vCPUs to machines with 50+ cores) allow primary servers to handle high concurrency, typical primary-backup replication relies on shipping an update log to backups. Because parallel execution on multi-core systems is inherently non-deterministic (e.g., lock acquisition order variations, Heisenbugs), replaying logs naively in parallel can cause backups to diverge from the primary's state. To guarantee consistency, conventional databases like MySQL, PostgreSQL, and MongoDB often fall back to serial (single-threaded) log replay on backups. This disparity creates a severe "parallelism gap" where backups cannot keep up with primaries, leading to unbounded replication lag, stale read replicas, and slow failover times that threaten availability.

### Key Topics - **The Parallelism Gap:** The divergence in throughput when primaries process transactions across multiple cores while replicas process log streams sequentially. - **Non-Determinism in Multi-Core Replay:** How parallel programming primitives (locks, futures) introduce non-deterministic execution orders that cause replica states to diverge if conflicting updates are executed out of order. - **Conflict Analysis and Pre-Scheduling:** Parsing the log to identify conflicting writes and building a directed dependency graph so non-conflicting records can run fully in parallel. - **Consistent Read Serving:** Resolving implicit application-level dependencies (such as foreign-key-like relationships between albums and pictures) by exposing read states strictly along complete prefix low-water marks without stalling write parallelism.

### Technical Details Faleiro proposes a solution that requires no invasive changes or throughput penalties on the primary, relying entirely on existing log data: - **Conflict Graph Execution:** Since log records specify write targets, a conflict analysis identifies write-write conflicts on shared data objects. For conflicting records, log order is strictly enforced; for non-conflicting records, execution order is arbitrary. The output is a directed acyclic graph where any log record is safe to execute as soon as its parent dependencies finish. - **Parallelizing Conflict Analysis:** To prevent single-threaded conflict analysis from becoming a CPU bottleneck on many-core systems, objects are partitioned across threads. Each thread tracks only the objects within its partition and maintains a map of each object to its last writer to generate execution dependencies concurrently. - **Handling Implicit Dependencies for Reads:** Even if records write different objects (avoiding explicit write conflicts), applications often harbor implicit read-after-write invariants (e.g., verifying an album exists before inserting a photo). Executing records out of order could expose inconsistent states to read queries. Because implicit dependencies are application-specific and impractical to detect directly, the system satisfies them by exposing state at complete prefix low-water marks. Using an incremental, asynchronous checkpointing mechanism, the backup materializes states corresponding to the low-water mark of completed prefixes without requiring full update quiescence.

### Takeaways Combining multi-core parallelism and log-shipping replication seems straightforward but readily leads to correctness and performance issues due to concurrency non-determinism. By extracting conflict constraints directly from log records, systems can parallelize log replay on backups without primary-side overhead. Combining parallel partitioned conflict analysis with low-water mark incremental checkpoints allows backups to match primary throughput and reliably serve consistent read traffic.