|
›› 2017,Vol. 32 ›› Issue (1): 41-54.doi: 10.1007/s11390-017-1704-4
所属专题: Computer Architecture and Systems
• Special Section on Selected Paper from NPC 2011 • 上一篇 下一篇
Feng-Feng Pan1,2(潘锋烽), Student Member, CCF, ACM, IEEE, Yin-Liang Yue3(岳银亮), Member, CCF, ACM, IEEE, and Jin Xiong1,2(熊劲), Senior Member, CCF, Member, ACM, IEEE
Feng-Feng Pan1,2(潘锋烽), Student Member, CCF, ACM, IEEE, Yin-Liang Yue3(岳银亮), Member, CCF, ACM, IEEE, and Jin Xiong1,2(熊劲), Senior Member, CCF, Member, ACM, IEEE
键值存储系统在当今互联网应用中发挥着巨大的作用。写优化的数据结构,例如日志结构合并树以及它的变种,被广泛应用于各类键值存储系统中,如Bigtable,RocksDB等。传统的日志结构合并树通过两层有序数据集或者多层有序数据集对索引变更进行延迟及批量处理,并通过类似于归并排序的方式高效地将磁盘上的多个有序数据集进行合并,而在多层合并过程中会由于大量键值对重复读写引发写放大问题,导致性能下降。本文针对合并过程中的写放大问题,提出了一种新的合并方法—dCompaction,其核心思想是通过延迟调度部分合并操作方式,来减少合并过程中的键值对重复读写的问题,从而提升了系统的吞吐率。本文以RocksDB为原型在其上实现了dCompaction策略,并利用YCSB进行大量的测试,其结果表明与RocksDB相比,dCompaction在保持读性能不变的情况下,写性能提升40%左右。
[1] Sears R, Ramakrishnan R. bLSM:A general purpose log structured merge tree. In Proc. the ACM SIGMOD Inter national Conference on Management of Data, May 2012, pp.217-228.[2] Huang Q, Birman K, van Renesse R, Lloyd W, Kumar S, Li H C. An analysis of Facebook photo caching. In Proc. the 24th ACM Symposium on Operating Systems Princi ples (SOSP), Nov. 2013, pp.167-181.[3] Atikoglu B, Xu Y, Frachtenberg E et al. Workload analysis of a large-scale key-value store. In Proc. ACM SIGMET RICS, Jun. 2012, pp.53-64.[4] O'Neil P, Cheng E, Gawlick D et al. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996, 33(4):351-385.[5] Chang F, Dean J, Ghemawat S, Hsieh W, Wallach D, Bur rows M, Chandra T, Fikes A, Gruber R. Bigtable:A dis tributed storage system for structured data. In Proc. the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), Nov. 2006, pp.205-218.[6] Lakshman A, Malik P. Cassandra:A decentralized struc tured storage system. ACM SIGOPS Operating Systems Review, 2010, 44(2):35-40.[7] George L. HBase:The Definitive Guide. O'Reilly Media, 2011.[8] Escriva R, Wong B, Sirer E. HyperDex:A distributed, searchable key-value store. In Proc. ACM SIGCOMM Conf. Applications, Technologies, Architectures, and Protocols for Computer Communication, Aug. 2012, pp.25-36.[9] Cooper B, Ramakrishnan R, Srivastava U, Silberstein A, Bohannon P, Jacobsen H, Puz N, Weaver D, Yerneni R. PNUTS:Yahoo! hosted data serving platform. Proc. the VLDB Endowment, 2008, 1(2):1277-1288.[10] Shetty P, Spillane R, Malpani R et al. Building workloadindependent storage with VT-trees. In Proc. the 11th USENIX Conference on File and Storage Technologies (FAST), Feb. 2013, pp.17-30.[11] Jermaine C, Omiecinski E, Yee W G. The partitioned exponential file for database storage management. The VLDB Journal, 2007, 16(4):417-437.[12] Zhong Z, Yue Y, He B et al. Pipelined compaction for the LSM-tree. In Proc. the 28th International Parallel and Distributed Processing Symposium (IPDPS), May 2014, pp.777-786.[13] Wu X, Xu Y, Shao Z et al. LSM-trie:An LSM-tree-based ultra-large key-value store for small data. In Proc. the USENIX Annual Technical Conference (ATC), Jul. 2015, pp.71-82.[14] Amur H, Andersen D, Kaminsky M et al. Design of a writeoptimized data store. Technical Report GIT-CERCS-13-08, Georgia Tech CERCS, 2013.[15] Cooper B, Silberstein A, Tam E, Ramakrishnan R, Sears R. Benchmarking cloud serving systems with YCSB. In Proc. the 1st ACM Symposium on Cloud Computing (SoCC), Jun. 2010, pp.143-154.[16] Spillane R, Shetty P, Zadok E, Dixit S, Archak S. An efficient multi-tier tablet server storage architecture. In Proc. the 2nd ACM Symposium on Cloud Computing in Conjunction with SOSP (SoCC), Oct. 2011, pp.1-14.[17] Bloom H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13(7):422-426.[18] Chazelle B, Guibas L. Fractional cascading:A data structuring technique with geometric applications. In Proc. the 12th International Colloquium on Automata, Languages, and Programming (ICALP), Jul. 1985, pp.90-100.[19] Bender M, Farach-Colton M, Fineman J, Fogel Y, Kuszmaul B, Nelson J. Cache-oblivious streaming B-trees. In Proc. the 19th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Jun. 2007, pp.81-92.[20] Li Y, He B, Yang R J et al. Tree indexing on solid state drives. Proc. the VLDB Endowment, 2010, 3(1/2):1195-1206. |
No related articles found! |
版权所有 © 《计算机科学技术学报》编辑部 本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn 总访问量: |