RHT: Supporting range queries in DHT-based P2P systems

Abstract

An efficient range query processing support is required for Distributed Hash Table (DHT)-based P2P networks as consistent hashing destroys the inherent order of numeric keys. In this paper, we present a lightweight and efficient mechanism, called Range Hash Tree (RHT), to support range queries on DHTs. In RHT, key space is partitioned into small ranges such that data items within one range can be stored on one node. To quickly resolve a range query, we introduce a scalable encoding algorithm that can represent the key space partitioning status with a small RHT Signature. Compared to other approaches, RHT provides a bounded query delay, which is independent of the size of range query and the number of matching data items. Our experiments show that RHT works efficiently on both uniform and much skewed data distributions.