Adaptive Partitioning Algorithms for Optimized State Replication of Highly Available Services

In order to provide highly available, stateful services it is often necessary to setup several servers that actively provide the service, while performing dynamic state-replication between them. As the number of servers increases, scalability issues arise because of the large amount of state sharing messages. In this paper, methods are provided to reduce the amount of state sharing messages, while reserving high availability, scalability, and consistency. To reduce the amount of state update messages, the servers are divided into subsets of servers. The stateful services could be running in an ad-hoc setting where the application will have to adapt to highly fluctuating network parameters. By knowing the characteristics of the network, the servers can be partitioned in an efficient manner, thereby increasing consistency. Subset division algorithms that take the characteristics of the network into account are developed in this paper. The algorithms are evaluated with respect to quality and runtime. Furthermore, full network-level simulations are utilized to investigate the impact of the partitioning algorithms on different performance metrics in a dynamically changing scenario. The results show that inconsistency is reduced while preserving high availability and scalability.