Shipyard: A Multi-Leader Consensus Protocol with Auto-Balanced Leadership of the Sharded Keyspace

IPDPS '26

Abstract

Leader-based consistency protocols often struggle with scalability due to the centralization of client request ordering. The leader, responsible for ensuring consistency by ordering reads and writes, becomes a bottleneck under high load, limiting overall system performance. This limitation is exacerbated by the tight coupling of consistency protocols with fault tolerance mechanisms, which further strain the leader’s capacity. Keyspace sharding, a widely adopted technique in databases and blockchain systems, helps mitigate this bottleneck by dis- tributing the workload. However, it introduces two primary challenges: first, maintaining consistency across shards, and second, balancing the workload between them. While several multi-leader approaches have been proposed to address consistency issues, they often neglect the crucial aspect of leadership balancing. Furthermore, these existing solutions frequently fail to consider dynamic factors such as CPU utilization, request frequency, and other performance metrics that significantly impact overall system efficiency. To address these gaps, we propose Skiff, a variant of the Raft protocol that automatically balances leadership for a single shard. Furthermore, we introduce Shipyard, a higher-level protocol that manages all sharded keyspaces as a unified system, integrating failure recovery and offering linearizable reads and writes.