D. Deveci, M. Kortenjan, and G. Schomaker (Germany)
Load Balancing, Distributed Systems, Hash Tables
We present an architecture using a dynamical deterministic unit ring decomposition to improve the balancing quality of an heterogeneous dynamic hashing scheme. This new approach, denoted by DhHHT, is capable to distribute any subset D′ ⊆ D of uniform items balanced among a dynamical node set V . Further, the capacity of a node, labeled as c(v) min v ∈ V , is allowed to change during runtime and causes no overhead. The challenge in this area is to as sign to each v ∈ V approximately |D′ | · c(v)/ u ∈V c(u) items, even if nodes are added or removed from V , where |D| denotes the cardinality of D. We will show that DhHHT reaches this without global knowledge about V nor by capacity normalization. Further, DhHHT has an improved model complexity of O(|V |), which is reduced by O(log n) compared to previous approaches. Its special design purpose is to manage limited resources with persistent allocation requests, where even slightly constant balancing deviations are intolerable. We also present an uniform dynamical deterministic hash range decomposition, used to place nodes in the hash range, which provides a constant upper and lower deviation of 1.118 ≤ s ≤ 1.809. The decomposition is embedded within the DhHHT architecture.
Important Links:
Go Back
