MT-10.06

A Case Study of DHT Functionality: Range Query on DHT


Author(s): 

Yoshihiro Tanaka

Oral Defence Date: 

Wednesday, December 15, 2010 - 16:10

Location: 

SCI 241

Time: 

4:10 PM

Committee: 

Professors Wong, Murphy & Puder


Abstract: 

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.


Copyright: 
Yoshihiro Tanaka

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