CRS: Consistent Replica Selection Algorithm for Distributed Key-Value Storage

Abstract

The communication between data accessibility and consistency becomes a challenge of replica selection for a Key-Value Storage (KVS). Applying a fixed replica selection policy in numerous data centers may decrease the capacity of a data store. Dynamic scaling advances the KVS with dynamical addition or removing data nodes. To expand the effective addition of the data nodes, the consistent hashing method is applied in KVS because of the adjustability of node variants. The benefits of the hashing algorithms are that scalability, direct control, and adaptation to node transfers while it is not entirely restructuring data layout. The three algorithms are proposed in this paper for selecting the consistent replicas according to the order of the data nodes id’s hash values, total Round Trip Time (RTT), and Probability of Bounded Staleness (PBS) among the replicas in a datacenter. By selecting the appropriate node, it can reduce the write execution time for regenerating the data. Without applying the random of the existing consistent hashing technique, it is effective in reducing latency cost, memory cost, and replication cost. The experimental results state that the node selection procedure significantly improves the throughput and consistency rate.