臺灣博碩士論文加值系統

在雲端平台上每個資料庫主機往往必須同時服務多個資料庫應用系統，但在主機的資源有限下，就必須對所儲存的資料量，以及所需負擔的資料庫數目給予必須的考量，希望能夠達到負載平衡，以免各主機工作分配不均的情況下，造成服務品質不佳。然而，如何考量資料量與資料庫數目的均衡分配到各雲端主機，目前則尚未受到關注。本研究首先設計了五個將資料庫分配到主機的方法，嘗試將資料庫平衡的分配到各雲端主機，我們也設計了與理想分配差異的偏離公式，透過偏離值判斷分配方法的優劣。然而，資料庫的實際大小並不一致，也就是有所謂的資料歪斜(skew)，如果有部份資料庫的資料量特別的多，特別的大型，則我們所設計的五個資料庫分配方法，仍然無法有效的讓雲端主機達到較佳的負載平衡。因此，我們在此研究報告中，進一步的提出了資料庫切割的技術，利用分散式資料庫的概念，將大型資料庫降為較小的資料庫，以方便更進階的平衡分配。但資料庫切割也伴隨著資料的複製，不能無限度的將資料庫切小，如此，我們則可透過了偏離值的判斷，以做為資料庫適當切割的依據。最後經實驗的驗證，我們提出的資料庫分配與切割技術，可以有效的改善資料庫於雲端主機之分配，以達平衡負載。

Each database host in the cloud platform often has to service more than one database application system. However, under the resource limitations of the hosts, evenly distributed databases into each host is an important issue needed to be addressed. The database sizes and the number of databases must be taken into account for workload balancing among database hosts. If too many data or databases are gathered in only few database hosts, the data skew may occur and result in poor quality of service. Currently, how to evenly allocating databases into hosts has not been concerned yet. In this research, we first propose five database allocation algorithms for distributing databases to hosts in the cloud platform. The equations used to evaluate the deviation of database allocation results are also provided. However, if severe database skew problems occur, some database sizes may be too large to well distributed by our proposed schemes. The database fragmentation and replication are taken into account in our advanced approach of database distributions. In our experimental study, the advanced approach can well balance the severe skew problems of databases.

目錄
摘要 I
Abstract II
誌謝 III
目錄 V
圖目錄 VII
表目錄 VIII
第一章 緒論 1
第二章 文獻探討 4
2.1 Metadata Management for Small Files 5
2.2 Best Fit Decreasing Strategy 6
2.3 Round-Robin Scheduling 8
第三章 資料分配方法設計 9
3.1 Round-Robin Allocation 9
3.2 Z-Distributed 10
3.3 Best Fit Decreasing Strategy with Size First 11
3.4 Best Fit Decreasing Strategy with Limited Number of Databases 11
3.5 Quantity Ratio Allocation 11
第四章分配實驗分析 14
4.1 實驗模型 14
4.2資料量偏離分析 17
4.3資料庫數目偏離分析 19
4.4總偏離率分析 20
4.5資料庫數目的影響 21
4.6最佳解的探討 23
第五章大型資料庫之切割分配設計 25
第六章切割分配實驗分析 28
6.1固定複製比率的資料庫切割 28
6.2變動複製比率的資料庫切割 30
6.3複製比率的分析 31
第七章結論與未來研究方向 33
參考文獻 35
圖目錄
圖1. 雲端儲存(cloud storage) 1
圖2. 詮釋資料伺服器連結多個I/O節點 6
圖3. 檔案系統中每位使用者的檔案數與空間的限制 6
圖4. Best Fit Decreasing Strategy 7
圖5. Round-Robin Scheduling 8
圖6. Round-Robin Allocation 10
圖7. Z-Distributed 10
圖8 QR示意圖 12
圖9. Zipf-like distribution分佈情形 15
圖10. 資料量偏離分析 18
圖11. 資料庫數目偏離分析 20
圖12. 總偏離率分析 21
圖13. 資料庫數目的影響分析 22
圖14. QR與最佳解的比較 24
圖15. 資料庫切割與複製示意圖 25
圖16. 固定複製5%的資料庫切割 30
圖17. 變動複製比率的資料庫切割 31
圖18. 複製比率分析 32
表目錄
表1. 實驗參數 17
表2. Zipf-like distribution 最大與最小資料庫 19
表3. 各資料庫數量實驗參考 22

[1] S.A. Cook, “The Complexity of Theorem Proving Procedures,” In proceedings of 3rd Annual ACM Symposium on the Theory of Computing, New York: ACM, 151-158, 1971.
[2] J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” In Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI 04), Usenix Assoc., pages 137–150, 2004.
[3] D.J. DeWitt, J. Gray, “Parallel Database Systems: The Future of High Performance Database Systems,” Comm. ACM 35 (6), 85 - 98, 1992.
[4] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman, San Francisco, 1979.
[5] D.S. Johnson, “Near-optimal bin packing algorithms,” Ph.D. Thesis, MIT, Cambridge, MA, 1973.
[6] J.L. Johnson, “SQL in the Clouds,” Computing in Science and Engineering, pp. 12-28, July/August, 2009.
[7] Y. Kakuda, H. Yukitomo, S. Kusumoto, and T. Kikuno, "Scientific Computing in the Cloud, " IEEE Design &; Test, Vol. 12, Issue 3, IEEE Computer Society Press, pp. 34-43, May 2010.
[8] M. Kitsuregawa and Y. Ogawa. “Bucket spreading parallel hash: A new, robust, parallel hash join method for data skew in the super database computer (SDC),” In Proc. of 16th Int ’ l Conf. on VLDB, pages 210-221, Brisbane, Australia, August 1990.
[9] Y- L. Lo and M-S. Lai, “The Load Balancing of Database Allocation in the Cloud,” In Proc. of the International MultiConference of Engineers and Computer Scientists IMECS, Hong Kong , pp.223-228 , March 13 – 15, 2013.
[10] G. Mackey, S. Sehrish and J. Wang, "Improving metadata management for small files in HDFS," CLUSTER ‘09. IEEE International Conference on Cluster Computing and Workshops, September, 2009.
[11] V. Mateljan, D. Cisic, and D. Ogrizovic, “Cloud Database-as-a-Service (DaaS) – ROI,” proceedings of the 33rd International Convention MIPRO, pp. 1185-1188, May 2010.
[12] Z. Mian and Z. Nong, “The Study of Multimedia Data Model Technology Based on Cloud Computing,” The 2nd International Conference on Signal Processing Systems (ICSPS), pp. V3-743-V3-746, July 2010.
[13] A. Michael, F. Armando, G. Rean, A. D. Joseph, K. Randy, K. Andy, L. Gunho, P. David, R. Ariel, S. Ion, and Z. Matei, “A View of Cloud Computing,” Communications of the ACM, Vol.53, No. 4, pp. 50-58, 2010.
[14] J. Rogers,O. Papaemmanouil, and U. Cetintemel, "A Generic Auto-Provisioning Framework for Cloud Databases," IEEE 26th International Conference on Data Engineering Workshops (ICDEW), pp. 63-68, 2010.
[15] A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts, John Wiley &; Sons, Inc., seventh edition. pp. 164-166, 2005.
[16] T. Stohr, H. Martens, E. Rahm, “Multi-Dimensional Database Allocation for Parallel Data Warehouses,” Proc. 26th VLDB Conference, Cairo, Egypt, Sep. 2000.
[17] N.E. Taylor and Z.G. Ives, “Reliable Storage and Querying for Collaborative Data Sharing Systems,” IEEE 26th International Conference on Data Engineering (ICDE), pp. 40-51, 2010.
[18] C. Turbyfill. ”Comparative Benchmark of Relational Database System,”. PhD thesis, Cornell University, September 1987.
[19] M.A. Vouk, “Cloud Computing- Issues, Research and Implementations,” the 30th International Conference on Information Technology Interfaces, pp. 31-40, June 23-26, 2008.
[20] E. Walker, W. Brisken, and J. Romney, “To Lease or Not to Lease from Storage Clouds,” Computer, Vol. 43, Issue 4, IEEE Computer Society Press, pp. 6-9, April 2010.
[21] J.L. Wolf, D.M. Dias, P.S. Yu, and J. Turek, “Comparative performance of parallel join algorithms,” In Proc. of Int’l Conf. on Parallel and Distributed Information Systems, pages 78-88, Miami, Florida, December 1991.
[22] S. Zhang, S. Zhang, X. Chen, and X. Huo, “Cloud Computing Research and Development Trend,” the 2nd International Conference on Future Networks, pp. 93-97, Jan. 2010.
[23] G.K. Zipf, “Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology,” Addison-Welsey, Reading, MA. 1949.
[24] Y.F. Zheng and C. Shao, “An efficient round-robin algorithm for combined input-crosspoint-queued switches,” In: Dini P, ed. Proc. of the IEEE ICAS/ICNS, Papeete: IEEE Computer Society, pp. 23−28. 2005.
[25] J. Wu, L. Ping, X. Ge. Y. Wang, and J. Fu, Cloud storage as the infrastructure of cloud computing,” In Proceedings of the International Conference on Intelligent Computing and Cognitive Informatics, Kuala Lumpur, Malaysia, pp.380–383, 22–23 June, 2010.
[26] Gartner Says Cloud Computing Will Be as Influential as E-business, June 2008, (http://www.gartner.com/it/page.jsp?id=707508)
[27] The Apache Software What Is Apache Hadoop, 2012, (http://hadoop.apache.org/)