Scalable Fine-Grained Reconfigurable Replica Coordination

Many large distributed systems today use sophisticated combinations of replication and partitioning of data and compute, but traditional distributed system designs steer developers towards a monolithic design, wherein the distributed principal–a slice of the state or the state machine–is heavyweight and replication and partitioning decisions are infrequently reconfigured if at all. We present GigaPaxos, a novel system for scalable, fine-grained, reconfigurable replica coordination. A key capability in GigaPaxos is maximal object-group configurability, i.e., the ability to easily manage and quickly reconfigure a very large number of replica groups, one for each lightweight fault-tolerant principal as small as a single record in a key-value store or an ephemeral service replica created on the fly for each user. GigaPaxos achieves this goal by driving down the marginal memory overhead of a replicated state machine to a few hundred bytes while keeping the messaging overhead, throughput, and latency of each group independent of the total number of groups and comparable to or vastly better than state-of-the-art consensus systems. We study the benefits of object-group configurability using several case studies including myCloud, a hypothetical application that creates a custom, reconfigurable replica group for each user’s personal cloud data, and show that agile reconfigurability can significantly enhance user-perceived performance.