ABSTRACT
With the advent of cloud computing model, distributed caches have become the cornerstone for building scalable applications. Popular systems like Facebook [1] or Twitter use Memcached [5], a highly scalable distributed object cache, to speed up applications by avoiding database accesses. Distributed object caches assign objects to cache instances based on a hashing function, and objects are not moved from a cache instance to another unless more instances are added to the cache and objects are redistributed. This may lead to situations where some cache instances are overloaded when some of the objects they store are frequently accessed, while other cache instances are less frequently used.
In this paper we propose a multi-resource load balancing algorithm for distributed cache systems. The algorithm aims at balancing both CPU and Memory resources among cache instances by redistributing stored data. Considering the possible conflict of balancing multiple resources at the same time, we give CPU and Memory resources weighted priorities based on the runtime load distributions. A scarcer resource is given a higher weight than a less scarce resource when load balancing. The system imbalance degree is evaluated based on monitoring information, and the utility load of a node, a unit for resource consumption. Besides, since continuous rebalance of the system may affect the QoS of applications utilizing the cache system, our data selection policy ensures that each data migration minimizes the system imbalance degree and hence, the total reconfiguration cost can be minimized. An extensive simulation is conducted to compare our policy with other policies. Our policy shows a significant improvement in time efficiency and decrease in reconfiguration cost.
- Lucas Nealan. Caching & Performance: Lessons from Facebook. Retrieved May 10,2012, from http://www.scribd.com/doc/4069180/Caching-Performance-Lessonsfrom-FacebookGoogle Scholar
- Roebuck, K. Platform as a Service(PaaS):High-Impact Emerging Technology - What You Need to Know: Definitions, Adoptions, Impact, Benefits, Maturity, Vendors. Tebbo Publishers, 2011.Google Scholar
- Gualtieri, M. Rymer, J. R. The Forrester Wave#8482;: Elastic Caching Platforms, Q2 2010. Retrieved May 14, 2012,from Forrester Companies: http://www.forrester.com/The+Forrester+Wave+Elastic+Caching+Platforms+Q2+2010/fulltext/-/E-RES55505?docid=55505Google Scholar
- Perez-Sorrosal, F., Patiño-Martínez, M. Jiménez-Peris, R. and Kemme, B. Elastic SI-Cache: consistent and scalable caching in multi-tier architectures. The VLDB Journal --- The International Journal on Very Large Data Bases, 20 (6).841--865 Google ScholarDigital Library
- Memcached. Retrieved March 15, 2012, from Dormando Companies: http://memcached.org/Google Scholar
- Scudder, J. Effective Memcache. Retrieved June, 2012, from https://developers.google.com/appengine/articles/scaling/memcacheGoogle Scholar
- You, G. W., Hwang, S. W. and Jain, N. Scalable Load Balancing in Cluster Storage Systems. In Proceedings of the 12th ACM/IFIP/USENIX international conference on Middleware, (Lisboa, Portugal, 2011), Springer Publishers, 101--122. Google ScholarDigital Library
- Sung Goo Yoo, Kil To Chong. Hot Spot Prediction Algorithm for Shared Web Caching System using NN. In 2007 International Symposium on Information Technology Convergence, (Jeonju, Korea, 2007), Springer Publishers, 125--129. Google ScholarDigital Library
- Chandra Chekuri. On multidimensional packing problems. SIAM Journal on Computing.33 (4).837--851. Google ScholarDigital Library
- Csirik, J., Frenk, J. B. G., Labbé, M and Zhang, Shu. On the multidimensional vector bin packing. Acta Cybern Publishers, 1990.Google Scholar
- Chekuri C., Khanna S. On multi-dimensional packing problems. In Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. (Baltimore, Maryland, 1999), Society for Industrial and Applied Mathematics Philadelphia Publishers, 185--194 Google ScholarDigital Library
- Patt-Shamir, B., Rawitz, D. Vector bin packing with multiple-choice. In Proceedings of the 12th Scandinavian conference on Algorithm Theory. (Bergen, Norway, 2010), Springer Publishers, 248--259. Google ScholarDigital Library
- Godfrey, B., Lakshminarayanan, K., Surana, S., Karp, R., Stoica, I. Load balancing in dynamic structured peer-to-peer systems. Performance Evaluation - P2P computing systems, 63(3). 217--240. Google ScholarDigital Library
- Kunkle D., Schindler J. A load balancing framework for clustered storage systems. In Proceedings of the 15th International Conference on High Performance Computing, (Bangalore, India, 2008). Springer Publishers, 57--72. Google ScholarDigital Library
- Gulisano, V., Jiménez-Peris, R., Patiño-Martínez, M., Soriente, C., Valduriez, P. StreamCloud: An Elastic and Scalable Data Streaming System. In Proceedings of the 2012 Parallel and Distributed Systems. Page(s): 1 Google ScholarDigital Library
- Milan-Franco, J. M., Jiménez-Peris, R., Patiño-Martínez, M. and Kemme, B. Adaptive Middleware for Data Replication. In Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, (Toronto, Canada, 2004). ACM Publishers, 175--194. Google ScholarDigital Library
- Leinberger, W., Karypis, G., Kumar, V. Job scheduling in the presence of multiple resource requirements. In Proceedings of the 1999 ACM/IEEE conference on Supercomputing, (Portland, Oregon, USA, 1999) ACM Publishers. Google ScholarDigital Library
- Chih-Chiang, Y., Kun-Ting, C., Jing-Ying, C. Market-Based Load Balancing for Distributed Heterogeneous Multi-Resource Servers. In Proceedings of the 2009 15th International Conference on Parallel and Distributed Systems (Shenzhen, China, 2009) IEEE Computer Society Publishers, 158--165. Google ScholarDigital Library
- Jiménez-Peris, R., Patiño-Martínez, M., Magoutis, K. Bilas, A. and Brondino, I. CumuloNimbo: A highly-scalable transaction processing platform as a service. ERCIM NEWS n° 89, Special theme Big Data, 34--35. April 2012.Google Scholar
- Friedman, J. H., Baskett, F. and Shustek, L. J. An algorithm for finding nearest neighbors. IEEE Transactions on Computers, C-24(10). 1000--1006. Google ScholarDigital Library
Index Terms
- A multi-resource load balancing algorithm for cloud cache systems
Recommendations
Load balancing in cloud computing: A big picture
AbstractScheduling or the allocation of user requests (tasks) in the cloud environment is an NP-hard optimization problem. According to the cloud infrastructure and the user requests, the cloud system is assigned with some load (that may be ...
Resource scheduling algorithm with load balancing for cloud service provisioning
AbstractCloud computing uses scheduling and load balancing for virtualized file sharing in cloud infrastructure. These two have to be performed in an optimized manner in cloud computing environment to achieve optimal file sharing. Recently, ...
Graphical abstractDisplay Omitted
Highlights- FMRS algorithm for minimizing response time on handling complex query.
- ...
A Predictive Workload Balancing Algorithm in Cloud Services
AbstractPerformance of dynamic clouds depends on the efficiency of its load balancing and resource allocation. This paper is an exploratory study on the predictive approach for dynamic resource distribution of cloud services. Efficient cloud resource ...
Comments