Elastic Load-Balancing in a Distributed Spatial Cache Overlay

Location-based services (LBS) have gained enormous popularity, which imposes increasing query loads at the data tier of an LBS. Yet, the data access patterns of LBS typically possess high temporal and spatial locality. Therefore, a dedicated spatial cache which provides efficient access to the data currently needed may considerably reduce this load. To ensure high throughput, multiple cache nodes can collaborate in a distributed spatial cache overlay, which balances load among the nodes. However, load-balancing is a non-trivial task in this context, as load spreads unevenly in space and varies notably over time. This requires constant readjustment to shifting hot spots. We present an elastic load-balancing mechanism between cache nodes that is based on the physical model of a particle-spring system. Using spring contraction, nodes instantly form processing clusters in regions with high load and thus can easily work off accumulating queries. Our evaluation shows that our approach quickly adapts to rapidly changing hot spots and thereby ensures high throughput throughout the entire execution.