Taming hot-spots in DHT inverted indexes

Abstract

DHT systems are structured overlay networks capable of using P2P resources as a scalable platform for very large data storage applications. However, their efficiency expects a level of uni- formity in the association of data to index keys that is often not present in inverted indexes. Index data tends to follow non- uniform distributions, often power law distributions, creating in- tense local storage hotspots and network bottlenecks on specific hosts. Current techniques like caching cannot, alone, cope with this issue. We propose a new distributed data structure based on a decen- tralized balanced tree to balance storage data and network load more uniformly across all hosts. The approach is stackable with standard DHTs and ensures that the DHT storage subsystem re- ceives an uniform load by assigning fixed sized, or low variance, blocks.