A Load Balancing Method for Distributed Key-Value Store Based on Order Preserving Linear Hashing and Skip Graph
Ken Higuchi, Jin Murayama, Tatsuo Tsuji · 2019
In this paper, a load balancing method for the distributed key-value store based on order preserving linear hashing and Skip Graph is proposed. In this system, data are divided by order preserving linear hashing and Skip Graph is used for overlay network. The routing table of this system is very uniform. Then, short detours can exist in the route of forwarding. By using these detours, the number of hops for the query forwarding is reduced. But since data is partitioned by linear hash, load balancing among nodes is difficult. In the proposed method, by dividing a physical node and a Skip Graph node, load balancing can be done. Furthermore, the maximum number of hops for message forwarding become smaller by this load balancing method.