跳到主要內容

臺灣博碩士論文加值系統

(44.221.73.157) 您好!臺灣時間:2024/06/15 12:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳俐瑩
研究生(外文):Li-Ying Wu
論文名稱:於Cassandra系統評估應用導向之一致性與延遲取捨
論文名稱(外文):Application-specific Tradeoffs between Consistency and Latency in Cassandra Storage Systems
指導教授:郭斯彥郭斯彥引用關係
指導教授(外文):Sy-Yen Kuo
口試委員:雷欽隆陳英一顏嗣鈞陳俊良
口試委員(外文):Chin-Laung LeiIng-Yi ChenHsu-chun YenJiann-Liang Chen
口試日期:2014-07-15
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:45
中文關鍵詞:分散式資料儲存系統資料複製一致性延遲
外文關鍵詞:Distributed storage systemData replicationConsistencyLatency
相關次數:
  • 被引用被引用:0
  • 點閱點閱:223
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在資料庫系統層面難以分析理解對於資料一致性的需求,因此在決定讀取/寫入資料時所保證的資料一致性必須由應用程式開發者根據一致性與延遲時間之間的取捨去做設定。不同類型的應用對於資料一致性的需求不同,開發者可以選擇犧牲部份的一致性來達到較快的回應時間。本篇針對應用導向分析不同服務所需的一致性需求,提供應用程式開發者根據其服務類型的特性選擇合適一致性設定的依據:根據所需滿足的一致性需求,提供一個擁有較低延遲時間的一致性設定。在實驗部分,首先觀察不同一致性強度所造成的延遲程度以及讀取和寫入之間造成的延遲時間之差別;再者模擬不同應用的workload比例以及資料傳輸特性所需的一致性以及其造成的延遲時間,並證明根據需求分析所得到之一致性設定能達到較低的延遲。

As long as data replicated, the tradeoff between consistency and latency occurs. Since understanding the consistency requirements at storage system level is not possible, choosing specific consistency policy for reading and writing data requires developers to make decisions. According to application-specific consistency requirements, application developers can choose between stronger consistency with lower performance and relaxed consistency with higher performance. In this work, we propose an approach that helps application administrators to decide which consistency policy is abided by its high-level consistency semantics with lower operation response latency. In Cassandra distributed storage system, it provides flexible and tunable consistency configuration that application administrators have different choice between strong consistency and eventual consistency for both reads and writes. The decision of consistency policy can provide a guideline for developers with varying application-specific consistency requirements. Experiments show that storage system has different ability to perform read and write operation; and the selected consistency policy achieves lower latency with satisfying quorum-based consistency requirement.

口試委員會審定書 #
誌謝 i
中文摘要 ii
ABSTRACT iii
CONTENTS iv
LIST OF FIGURES vi
LIST OF TABLES vii
Chapter 1 Introduction 1
Chapter 2 Background 4
2.1 Tradeoff between Consistency and latency 4
2.1.1 The CAP theorem 4
2.1.2 Misleading on the CAP theorem 6
2.1.3 PACELEC instead of CAP 7
2.2 Replication in distributed storage systems 8
2.2.1 Typical Replication Mechanisms: Active and Passive Replication Techniques 8
2.2.2 Consistency Models 9
2.3 Replication in Cassandra 11
2.3.1 Cassandra Architecture 12
2.3.2 Replica, replication factor and consistency level 13
2.3.3 Replication strategy 15
Chapter 3 Related works 16
Chapter 4 Methodology 18
4.1 Application Scenarios 18
4.2 Data-Centric and Client-Centric Consistency 20
4.3 Decision Features 21
4.4 Consistency Policies 22
4.4.1 Quorum-based Protocols 23
4.5 Decision of Consistency Policy 25
4.5.1 Data-Centric Based Decision Process Flow 25
4.5.2 Client-Centric Based Decision Process Flow 26
4.6 Latency Formulation 28
Chapter 5 Experiment and Results 32
5.1 Workload Benchmark 32
5.2 Experimental setup 34
5.3 Results 35
5.3.1 Comparison of different consistency policies 35
5.3.2 Under update-heavy workload 35
5.3.3 Under read-intensive workload 36
Chapter 6 Conclusions 38
Reference 39


Reference
[1]D. J. Abadi, “Consistency tradeoffs in modern distributed database system design: Cap is only part of the story,” Computer, vol. 45, pp. 37–42, 2012.
[2]S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility of consistent available partition-tolerant web services,” in ACM SIGACT News, 2002.
[3]Y. Zhu, P. S. Yu, and J. Wang. "RECODS: Replica consistency-on-demand store." Data Engineering (ICDE), 2013 IEEE 29th International Conference on. IEEE, 2013.
[4]H.E. Chihoub, S. Ibrahim, G. Antoniu and M. Perez “Consistency in the Cloud: When Money Does Matter!,” CCGRID 2013–13th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, Aug. 2008, [medium: online] Available: http://hal.inria.fr/hal-00789013, Delft, Pays-Bas
[5]H.E. Chihoub, S. Ibrahim, G. Antoniu, and M. S. P’erez-Hern’andez, “Harmony: Towards automated self-adaptive consistency in cloud storage.” Cluster Computing (CLUSTER), 2012 IEEE International Conference on. IEEE, 2012.
[6]E. Brewer, “Cap twelve years later: How the “rules” have changed,” Computer, vol. 45, no. 2, pp. 23 –29, Feb. 2012.
[7]A. Malik and P. Lakshman, “Cassandra: a decentralized structured storage system,”SIGOPS Operating System Review, vol. 44, no. 2, 2010.
[8]Y. Liu, and V. Vlassov, “Replication in Distributed Storage Systems: State of the Art, Possible Directions, and Open Issues.” Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2013 International Conference on, pp.225 – 232, Oct. 2013.
[9]Cozzi, Martin (2011-08-31). "Cassandra at Formspring"
[10]G. Linden. Make data useful. 29 November 2006. [Online]. Available: https://sites.google.com/site/glinden/Home/StanfordDataMining.2006-11-29.ppt.
[11]A. Fox,E. A.Brewer, “Harvest, yield, and scalable tolerant systems,” Proc. of the 7th Workshop on Hot Topics in Operating Systems, Rio Rico, AZ, USA, 29-30 March 1999. p.174-178.
[12]E. A. Brewer, “Towards robust distributed systems (abstract),” in Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, ser. PODC ’00. New York, NY, USA: ACM, 2000, pp. 7–.
[13]W. Vogels, “Eventually consistent,” Commun. ACM, pp. 40–44, 2009.
[14]D. Pritchett, “Base: An acid alternative,” ACM Queue, vol. 6, pp. 48–55, May 2008.
[15]Roe C. 2012 “ACID vs. BASE: The Shifting pH of Database Transaction Processing”- http://www.dataversity.net/acid-vs-base-the-shifting-ph-of-database-transaction-processing/.
[16]C. Hale, “You Can’t Sacrifice Partition Tolerance”, (2010) October 7, http://codahale.com/you-cant-sacrifice-partition-tolerance.
[17]D. Abadi, “IEEE Computer issue on the CAP Theorem”, DBMS Musings blog, (2012) October 29, http://dbmsmusings.blogspot.com/2012_10_01_archive.html.
[18]B. F. Cooper, “PNUTS: Yahoo!’s Hosted Data Serving Plat form”, Proc. VLDB Endowment (VLDB 08), ACM, 2008, pp. 1277-1288.
[19]E. Cecchet, G. Candea, and A. Ailamaki, “Middleware-based database replication: the gaps between theory and practice,”in SIGMOD 2008: Proceedings of the 28th ACM International Conference on Management of Data, Vancouver, Canada, June 2008, pp. 739–752.
[20]R. Jhawar, V. Piuri, “Fault Tolerance and Resilience in Cloud Computing Environments,”in Computer and Information Security Handbook, 2nd Edition, J. Vacca (ed.), Morgan Kaufmann, 2013. ISBN: 978-0-1239-4397-2
[21]F.B. Schneider, “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial,”ACM Computing Surveys, vol. 22, no. 4, pp. 299-319, 1990.
[22]F. Pedone, R. Guerraoui and A. Schiper, “The Database State Machine Approach,”Distributed and Parallel Databases, vol. 14, no. 1, pp. 71-98, July 2003.
[23]M. Wiesmann, F. Pedone, A. Schiper, B. Kemme and G. Alonso, “"Understanding replication in databases and distributed systems,” Proc. 20th Int''l Conf. Distributed Computing Systems (ICDCS ''00), 2000.
[24]J.N. Gray, P. Helland, P. O''Neil and D. Shasha, “The dangers of replication and a solution,” Proc. 1996 Int''l Conf. Management of Data, pp. 173-182, 1996.
[25]M. Wiesmann and A. Schiper, “Comparison of database replication techniques based on total order broadcast,”IEEE TKDE, vol. 17, no. 4, pp. 551–566, 2005.
[26]S. Savinov and K. Daudjee, “Dynamic database replica provisioning through virtualization,” in CloudDB ’10, 2010, pp. 41–46.
[27]W. Zhao, P. M. Melliar-Smith, and L. E. Moser, “Fault tolerance middleware for cloud computing,” in Proc. 3rd Int. Conf. Cloud Comput., Jul. 2010, pp. 67–74.
[28]M. P. Herlihy and J. M. Wing, “Linearizability: A correctness condition for concurrent objects,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 12, no. 3, pp. 463–492, 1990.
[29]Leslie Lamport, “How to make a multiprocessor computer that correctly executes multiprocess programs,”IEEE Trans. Comput. C-28,9 (Sept. 1979), 690-691.
[30]M. Ahamad, J.E. Burns, P.W. Hutto, and G. Neiger. “Causal Memory.” In Proc. 5th Intl. Workshop on Distributed Algorithms (WDAG-5), pages 9–30. Springer Verlag, LNCS 579, 1991.
[31]Solid IT.DB-Engines Ranking - Trend Popularity. 2014 [Online]. Available: http://db-engines.com/en/ranking_trend
[32]G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, W. Vogels,“Dynamo: Amazon''s Highly Available Key-value Store,”Proc. 21st SOSP, October 2007, pp. 205–220. (Pubitemid 351429377)
[33]E. Hewitt. “Cassandra: the definitive guide.” O''Reilly Media, 2010.
[34]V. Abramova and J. Bernardino. “NoSQL databases: MongoDB vs cassandra.” Proceedings of the International C* Conference on Computer Science and Software Engineering. ACM, pp. 14-22, 2013.
[35]David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web.”In ACM Symposium on Theory of Computing, pages 654–663, 1997.
[36]DataStax. “Apache Cassandra&;#8482; 2.0 Documentation,” April, 2014.
[37]Velocity and the Bottom Line.http://radar.oreilly.com/2009/07/velocity-making-your-site-fast.html
[38]W. Vogels, “Data access patterns in the Amazon.com technology platform,”in Proc. 2007 VLDB.
[39]L. ZHAO, S. SAKR, AND A. LIU, “A Framework for Consumer-Centric SLA Management of Cloud-Hosted Databases.” In IEEE Transactions on Service Computing (TSC), 2013.
[40]A. Tanenbaum and M. Van Steen, “Distributed Systems: Principles and Paradigms.”Prentice Hall PTR, 2002.
[41]D. Bermbach, S. Sakr, and L. Zhao, “Towards comprehensive measurement of consistency guarantees for cloud-hosted data storage services,”in Proceedings of the Fifth TPC Technology Conference on Performance Evaluation &; Benchmarking (TPCTC 2013). Springer, 2013.
[42]B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears, “Benchmarking cloud serving systems with ycsb,” in SoCC ’10, pp. 143–154.
[43]H. E. Chihoub, M.Perez, G. Antoniu, andL. Bouge. “Chameleon: Customized Application-Specific Consistency by means of Behavior Modeling.”2013.
[44]“Yahoo Cloud Serving Benchmark,” 2012. [Online]. Available: https://github.com/brianfrankcooper/YCSB/wiki
[45]B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H. arno Jacobsen, N. Puz, D. Weaver, and R. Yerneni, “Pnuts: Yahoo!s hosted data serving platform,” In Proc. 34th VLDB, Tech. Rep., 2008.
[46]“mongoDB,” 2012. [Online]. Available: http://www.mongodb.org/
[47]D. Bermbach, M. Klems, S. Tai, M. Menzel, “MetaStorage:A Federated Cloud Storage System to Manage Consistency-Latency Tradeoffs.” IEEE 4th International Conference on Cloud Computing, 2011.
[48]P. Goyal et al., “CacheCOW: QoS for Storage System Caches,” in Proceedings of 11th International Workshop on Quality of Service (IWQoS 03), Monterey, CA, Jun. 2003.
[49]K. Magoutis, P. Sarkar, and G. Shah, “OASIS: Self-Tuning Storage for Applications,” in Proc. of 23rd IEEE Conference on Mass Storage Systems and Technologies (MSST), College Park, MD, 2006.
[50]T. Kraska, M. Hentschel, G. Alonso, and D. Kossmann, “Consistency rationing in the cloud: pay only when it matters,” in Proc. 2009 VLDB.
[51]S. Esteves, J. Silva, and L. Veiga, “Quality-of-service for consistency of data geo-replication in cloud computing,” Euro-Par 2012 Parallel Processing, vol. 7484, 2012.
[52]Q. Liu, G. Wang, and J. Wu, “Consistency as a Service: Auditing Cloud Consistency.” Network and Service Management, IEEE Transactions on, Vol. 11, no. 1, March 2014.
[53]Douglas Terry, Vijayan Prabhakaran, Rama Kotla, Mahesh Balakrishnan, Marcos K. Aguilera, and Hussam Abu-Libdeh. “Consistency-based service level agreements for cloud storage.” To appear in Proceedings of the 24th ACM Symposium on Op-erating Systems Principles (SOSP), November 2013.
[54]M. Chalkiadaki, and K. Magoutis. “Managing Service Performance in the Cassandra Distributed Storage System.”Cloud Computing Technology and Science (CloudCom), 2013 IEEE 5th International Conference on. Vol. 1. IEEE, 2013.
[55]X. Wang, H. Sun, T. Deng, and J. Huai, “Consistency or latency? A quantitative analysis of replication systems based on replicated state machines.” Dependable Systems and Networks (DSN), 2013 43rd Annual IEEE/IFIP International Conference on. June 2013.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top