Scalable, efficient range queries for grid information services

Abstract

Recent peer-to-peer (P2P) systems such as Tapestry, Chord or CAN act primarily as a distributed hash table (DHT). A DHT is a data structure for distributed storing of pairs (key, data) which allows fast locating of data when a key is given. To facilitate efficient queries on a range of keys, we propose a CAN-based extension of this DHT-functionality. The design of our extension suggests several range query strategies; their efficiency is investigated in the paper. A further goal is to enhance the routing aspects of current DHT-systems so that frequently changing data can also be handled efficiently. We show that relatively simple approaches are able to reduce the communication overhead in this case. The design of the system is driven by its application as a part of the information infrastructure for computational grids. Such grids provide an infrastructure for sharing computing resources; an information infrastructure is their inherent part which collects resource data and provides search functionality. Our approach complements current solutions such as MDS-2 by adding self-organization, fault-tolerance and an ability to efficiently handle dynamic attributes, such as server processing capacity. We evaluate our system in this context via a simulation and show that its design along with particular query and update strategies meet the goals of scalability, communication-efficiency and availability.