Variable-size data item placement for load and storage balancing

Yung Cheng Ma*, Jih Chiu Chiu, Tien-Fu Chen, Chung-Ping Chung

*Corresponding author for this work

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

The rapid growth of Internet brings the need for a low cost high performance file system. Two objectives are to be pursued in building such a large scale storage system on multiple disks: load balancing and storage minimization. We investigate the optimization problem of placing variable-size data items onto multiple disks with replication to achieve the two objectives. An approximate algorithm, called LSB_Placement, is proposed for the optimization problem. The algorithm performs bin packing along with MMPacking to obtain a load balanced placement with near-optimal storage balancing. The key issue in deriving the algorithm is to find the optimal bin capacity for the bin packing to reduce storage cost. We derive the optimal bin capacity and prove that LSB_Placement algorithm is asymptotically 1-optimal on storage balancing. That is, when the problem size exceeds certain threshold, the algorithm generates a load balanced placement in which the data sizes allocated on disks are almost balanced. We demonstrate that, for various Web applications, a load balanced placement can be generated with disk capacity not exceeding 10% more than the balanced storage space. This shows that the LSB_Placement algorithm is useful in constructing a low cost and high performance storage system.

Original languageEnglish
Pages (from-to)157-166
Number of pages10
JournalJournal of Systems and Software
Volume66
Issue number2
DOIs
StatePublished - 15 May 2003

Fingerprint Dive into the research topics of 'Variable-size data item placement for load and storage balancing'. Together they form a unique fingerprint.

  • Cite this