We are interested in balancing load in distributed data-structures that support range-queries: The keys are stored in the network nodes so that a natural order is preserved and range-queries are efficiently handled. The interest in such structures is increasing, as they can be very useful in a variety of situations: On-line games, web servers, data-warehousing, etc. In such cases, adaptive and on-line load-balancing schemes must be employed in order to avoid resource unavailability and performance in a variety of workloads.

In our system, peers iteratively redistribute their load according to their capacities as well as with respect to the current load conditions. Our scheme manages to adapt as load changes both over time and items requested. Moreover, it preserves both the locality of the indexed items as well as the consistency of the system, without requiring any global knowledge.

As a case study, we offer an implementation on top of a skip graph, a distributed indexing structure based in skip lists that supports range queries. We present a modification that allows a faster and smoother load redistribution among the skip graph nodes. Our extensive simulations show that our method effectively balances load, minimizing the overloaded peer instances over the network. Moreover, we show that it quickly adapts to changes in the workload without excessive burden over the network.

-- IoannisKonstantinou - 15 Jul 2008