Data Structures for Routing Table of the Distributed Key-Value Store Based on Order Preserving Linear Hashing and Skip Graph with the Load Balancing Method
Ken Higuchi, Ami Miyazaki, Kenya Hasegawa, Tatsuo Tsuji · 2022
In this paper, data structures for reducing redundancy of routing information on the distributed key-value store based on order preserving linear hashing and Skip Graph with the load balancing method are proposed and evaluated. In this system, data are divided by order preserving linear hashing and Skip Graph is used for overlay network. For load balancing, by storing many Skip Graph nodes in one physical node, any highest-load Skip Graph can be divided. By this method, load balancing can be done. But the number of Skip Graph nodes becomes very many and redundant routing information exists. But this redundant routing information has regularity. In this paper, two types of data structure for reducing redundant routing elements are proposed. They are tree structure and array structure. By calculating space for them and searching time, the proposed data structures are experimentally evaluated.