A Case Study of DHT Functionality: Range Query on DHT


Yoshihiro Tanaka

Oral Defence Date: 

Wednesday, December 15, 2010 - 16:10


SCI 241


4:10 PM


Professors Wong, Murphy & Puder


Distributed Hash Table (DHT) is a method to store and lookup data across distributed nodes. It provides a lookup service to locate a corresponding node for a given key using a hash function. DHT is scalable, fault-tolerant and widely used in P2P systems. However, it does not inherently support range queries, since DHT is based on a hash function. In this project, a method to perform range queries on DHT is introduced. To verify and evaluate this method, a simple Chord based DHT system was implemented using Erlang/OTP. Experiments were performed using several machines. These experiments include measuring the performance under different conditions, comparison with a simple get method, memory usage of the range query method, and load balancing considerations. The experimental results show that the range query method outperforms exhaustive search using a simple get method; and the data load distribution was more balanced as the number of virtual nodes increases.

Yoshihiro Tanaka

DHT, Range Query, Key/Value store, Erlang, Distributed systems