Abstract
Enterprise and cloud data centers are comprised of tens of thousands of servers providing petabytes of storage to a large number of users and applications. At such a scale, these storage systems face two key challenges: (a) hot-spots due to the dynamic popularity of stored objects and (b) high reconfiguration costs of data migration due to bandwidth oversubscription in the data center network. Existing storage solutions, however, are unsuitable to address these challenges because of the large number of servers and data objects. This paper describes the design, implementation, and evaluation of Ursa, which scales to a large number of storage nodes and objects and aims to minimize latency and bandwidth costs during system reconfiguration. Toward this goal, Ursa formulates an optimization problem that selects a subset of objects from hot-spot servers and performs topology-aware migration to minimize reconfiguration costs. As exact optimization is computationally expensive, we devise scalable approximation techniques for node selection and efficient divide-and-conquer computation. Our evaluation shows Ursa achieves cost-effective load balancing while scaling to large systems and is time-responsive in computing placement decisions, e.g., about two minutes for 10K nodes and 10M objects.
Chapter PDF
Similar content being viewed by others
References
Amazon S3, http://aws.amazon.com/s3/
Windows azure, http://www.microsoft.com/windowsazure/
Abd-El-Malek, M., Courtright II, W.V., Cranor, C., Ganger, G.R., Hendricks, J., Klosterman, A.J., Mesnier, M., Prasad, M., Salmon, B., Sambasivan, R.R., Sinnamohideen, S., Strunk, J.D., Thereska, E., Wachs, M., Wylie, J.J.: Ursa Minor: Versatile Cluster-based Storage. In: Proc. of FAST (2005)
Chang, F., Dean, J., Ghemawat, S., Hsieh, W.C., Wallach, D.A., Burrows, M., Chandra, T., Fikes, A., Gruber, R.E.: Bigtable: A Distributed Storage System for Structured Data. In: Proc. of OSDI (2006)
Curino, C., Jones, E., Zhang, Y., Madden, S.: Schism: a Workload-Driven Approach to Database Replication and Partitioning. In: Proc. of VLDB (2010)
Curino, C., Jones, E., Zhang, Y., Wu, E., Madden, S.: Relational Cloud: The Case for a Database Service. Technical Report MIT-CSAIL-TR-2010-014, MIT (2010)
Das, S., Nishimura, S., Agrawal, D., Abbadi, A.E.: Live Database Migration for Elasticity in a Multitenant Database for Cloud Platforms. Technical report, UCSB (2010)
Dean, J., Ghemawat, S.: MapReduce: Simplified Data Processing on Large Clusters. In: Proc. of OSDI (2004)
Elmore, A., Das, S., Agrawal, D., Abbadi, A.E.: Who’s Driving this Cloud? Towards Efficient Migration for Elastic and Autonomic Multitenant Databases. Technical report, UCSB (2010)
Elmore, A., Das, S., Agrawal, D., Abbadi, A.E.: Zephyr: Live Migration in Shared Nothing Databases for Elastic Cloud Platforms. In: Proc. of SIGMOD (2011)
Eric, E.A., Spence, S., Swaminathan, R., Kallahalla, M., Wang, Q.: Quickly Finding Near-optimal Storage Designs. ACM Transactions on Computer Systems 23, 337–374 (2005)
Ghemawat, S., Gobioff, H., Leung, S.-T.: The Google File System. SIGOPS Operating System Review 37, 29–43 (2003)
Greenberg, A.G., Hamilton, J.R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D.A., Patel, P., Sengupta, S.: VL2: A Scalable and Flexible Data Center Network. In: Proc. of SIGCOMM (2009)
Gulati, A., Kumar, C., Ahmad, I., Kumar, K.: BASIL: Automated IO Load Balancing Across Storage Devices. In: Proc. of FAST (2010)
Hiller, F.S., Lieberman, G.J.: Introduction to Operations Research, 8th edn. McGraw-Hill (2005)
Kunkle, D., Schindler, J.: A Load Balancing Framework for Clustered Storage Systems. In: Sadayappan, P., Parashar, M., Badrinath, R., Prasanna, V.K. (eds.) HiPC 2008. LNCS, vol. 5374, pp. 57–72. Springer, Heidelberg (2008)
Lang, W., Patel, J.M., Naughton, J.F.: On Energy Management, Load Balancing and Replication. SIGMOD Record 38, 35–42 (2010)
Litwin, W.: Linear Hashing: A New Tool for File and Table Addressing. In: Proc. of VLDB (1980)
Narayanan, D., Donnelly, A., Thereska, E., Elnikety, S., Rowstron, A.: Everest: Scaling Down Peak Loads through I/O Off-loading. In: Proc. of OSDI (2008)
Savinov, S., Daudjee, K.: Dynamic Database Replica Provisioning through Virtualization. In: Proc. of CloudDB (2010)
Tam, H.V., Chen, C., Ooi, B.C.: Towards Elastic Transactional Cloud Storage with Range Query Support. In: Proc. of VLDB (2010)
Thereska, E., Donnelly, A., Narayanan, C.: Sierra: A Power-proportional, Distributed Storage System. In: Technical Report MSR-TR-2009-153 (2009)
Venkataramani, A., Kokku, R., Dahlin, M.: TCP Nice: A Mechanism for Background Transfers. In: Proc. of OSDI (2002)
Verma, A., Ahuja, P., Neogi, A.: pMapper: Power and Migration Cost Aware Application Placement in Virtualized Systems. In: Issarny, V., Schantz, R. (eds.) Middleware 2008. LNCS, vol. 5346, pp. 243–264. Springer, Heidelberg (2008)
Weil, S.A., Brand, S.A., Miller, E.L., Long, D.D.E., Maltzahn, C.: Ceph: A Scalable, High-performance Distributed File System. In: Proc. of OSDI (2006)
Yin, Q., Schüpbach, A., Cappos, J., Baumann, A., Roscoe, T.: Rhizoma: A Runtime for Self-deploying, Self-managing Overlays. In: Bacon, J.M., Cooper, B.F. (eds.) Middleware 2009. LNCS, vol. 5896, pp. 184–204. Springer, Heidelberg (2009)
Zeng, L., Feng, D., Wang, F., Zhou, K.: A Strategy of Load Balancing in Objects Storage System. In: Proc. of CIT (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 IFIP International Federation for Information Processing
About this paper
Cite this paper
You, Gw., Hwang, Sw., Jain, N. (2011). Scalable Load Balancing in Cluster Storage Systems. In: Kon, F., Kermarrec, AM. (eds) Middleware 2011. Middleware 2011. Lecture Notes in Computer Science, vol 7049. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25821-3_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-25821-3_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25820-6
Online ISBN: 978-3-642-25821-3
eBook Packages: Computer ScienceComputer Science (R0)