›› 2018,Vol. 33 ›› Issue (1): 79-97.doi: 10.1007/s11390-018-1809-4

所属专题: Computer Architecture and Systems

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

多布隆过滤器热数据识别:区块级别决策vs I/O请求级别决策

Dongchul Park1,2, Weiping He3, David H. C. Du4, Fellow, IEEE   

  1. 1 Division of Computer and Electronic Systems Engineering, Hankuk University of Foreign Studies Gyeonggi-do 17035, Korea;
    2 Intel Corporation, Hillsboro, OR 97124, U.S.A;
    3 Dell Storage, Eden Prairie, MN 55344, U.S.A;
    4 Department of Computer Science and Engineering, University of Minnesota-Twin Cities, Minneapolis, MN 55455, U.S.A
  • 收稿日期:2016-10-06 修回日期:2017-11-12 出版日期:2018-01-05 发布日期:2018-01-05
  • 作者简介:Dongchul Park is currently an assistant professor in Division of Computer & Electronic Systems Engineering at Hankuk University of Foreign Studies (HUFS), Gyeonggi-do, South Korea. Before joining HUFS, he was a senior staff research engineer in Storage Technology Group (STG) at Intel, Hillsboro, Oregon, USA in 2017 and a senior research engineer in Memory Solutions Laboratory (MSL) at Samsung Semiconductor Inc. in San Jose, California, USA from 2012 to 2016. He received his Ph.D. degree in computer science and engineering at the University of Minnesota-Twin Cities, Minneapolis, in 2012, and was a member of Center for Research in Intelligent Storage (CRIS) group under the advice of professor David H. C. Du. His research interests focus on storage system design and applications including non-volatile memories, in-storage computing, big data processing, Hadoop MapReduce, data deduplication, key-value store, cloud computing, and shingled magnetic recording (SMR) technology.
  • 基金资助:

    This work was supported by Hankuk University of Foreign Studies Research Fund of Korea, and also partially supported by the National Science Foundation (NSF) Awards of USA under Grant Nos. 1053533, 1439622, 1217569, 1305237, and 1421913.

Hot Data Identification with Multiple Bloom Filters: Block-Level Decision vs I/O Request-Level Decision

Dongchul Park1,2, Weiping He3, David H. C. Du4, Fellow, IEEE   

  1. 1 Division of Computer and Electronic Systems Engineering, Hankuk University of Foreign Studies Gyeonggi-do 17035, Korea;
    2 Intel Corporation, Hillsboro, OR 97124, U.S.A;
    3 Dell Storage, Eden Prairie, MN 55344, U.S.A;
    4 Department of Computer Science and Engineering, University of Minnesota-Twin Cities, Minneapolis, MN 55455, U.S.A
  • Received:2016-10-06 Revised:2017-11-12 Online:2018-01-05 Published:2018-01-05
  • About author:Dongchul Park is currently an assistant professor in Division of Computer & Electronic Systems Engineering at Hankuk University of Foreign Studies (HUFS), Gyeonggi-do, South Korea. Before joining HUFS, he was a senior staff research engineer in Storage Technology Group (STG) at Intel, Hillsboro, Oregon, USA in 2017 and a senior research engineer in Memory Solutions Laboratory (MSL) at Samsung Semiconductor Inc. in San Jose, California, USA from 2012 to 2016. He received his Ph.D. degree in computer science and engineering at the University of Minnesota-Twin Cities, Minneapolis, in 2012, and was a member of Center for Research in Intelligent Storage (CRIS) group under the advice of professor David H. C. Du. His research interests focus on storage system design and applications including non-volatile memories, in-storage computing, big data processing, Hadoop MapReduce, data deduplication, key-value store, cloud computing, and shingled magnetic recording (SMR) technology.
  • Supported by:

    This work was supported by Hankuk University of Foreign Studies Research Fund of Korea, and also partially supported by the National Science Foundation (NSF) Awards of USA under Grant Nos. 1053533, 1439622, 1217569, 1305237, and 1421913.

热数据识别对于很多应来说至关重要,但目前这方面的研究并不多。几乎所有的现存研究都把重点放在了频率上,然而,有效地识别热数据需要同时考虑新近和频率。而且,以往的研究均在数据块层级上作热数据决策。因为闪存存储的随机访问的性能与其顺序访问的性能一样优秀,如此细粒度的决策特别适合闪存存储。但是,硬盘驱动器(HDD)在顺序访问和随机访问的性能有显著差异,因此,与闪存存储不同,HDD不对称的访问性能使得需要粗粒度的决策。本文提出了一个新的热数据识别方案,它利用多布隆过滤器有效地描述新近和频率。因此,它不仅少消耗了50%的内存和高达58%的计算花销,而且与现有代表性方案相比,它降低了高达65%的错误识别率。此外,我们将此方案应用到下一代HDD技术,叠瓦式磁破纪录(SMR),以验证它的效用,。为此,我们设计了一个全新的基于SMR驱动的粗粒度决策的热数据识别方法。实验揭示了准确的热数据识别的重要性和好处;它为本文提出的SMR驱动性能提升高达42%。

Abstract: Hot data identification is crucial for many applications though few investigations have examined the subject. All existing studies focus almost exclusively on frequency. However, effectively identifying hot data requires equally considering recency and frequency. Moreover, previous studies make hot data decisions at the data block level. Such a fine-grained decision fits particularly well for flash-based storage because its random access achieves performance comparable with its sequential access. However, hard disk drives (HDDs) have a significant performance disparity between sequential and random access. Therefore, unlike flash-based storage, exploiting asymmetric HDD access performance requires making a coarse-grained decision. This paper proposes a novel hot data identification scheme adopting multiple bloom filters to efficiently characterize recency as well as frequency. Consequently, it not only consumes 50% less memory and up to 58% less computational overhead, but also lowers false identification rates up to 65% compared with a state-of-the-art scheme. Moreover, we apply the scheme to a next generation HDD technology, i.e., Shingled Magnetic Recording (SMR), to verify its effectiveness. For this, we design a new hot data identification based SMR drive with a coarse-grained decision. The experiments demonstrate the importance and benefits of accurate hot data identification, thereby improving the proposed SMR drive performance by up to 42%.

[1] Wang J G, Lo E, Yiu M L, Tong J C, Wang G, Liu X G. The impact of solid state drive on search engine cache management. In Proc. the 36th Int. ACM SIGIR Conf. Research and Development in Information Retrieval, July28-August 1, 2013, pp.693-702.

[2] Wang J G, Park D, Kee Y S, Papakonstantinou Y, Swanson S. SSD in-storage computing for list intersection. In Proc. the 12th Int. Workshop on Data Management on New Hardware, June 26-July1, 2016, Article No. 4.

[3] Park D, Debnath B, Du D. CFTL:A convertible flash translation layer adaptive to data access patterns. In Proc. the ACM SIGMETRICS Int. Conf. Measurement and Modeling of Computer Systems, June 2010, pp.365-366.

[4] Park D, Wang J G, Kee Y S. In-storage computing for Hadoop MapReduce framework:Challenges and possibilities. IEEE Trans. Computers, 2016 PP(99). doi:10.1109/TC.2016.2595566

[5] Park D, Debnath B, Du D H C. A dynamic switching flash translation layer based on page-level mapping. IEICE Trans. Information and Systems, 2016, E99-D(6):1502-1511

[6] Gray J. Tape is dead disk is tape flash is disk RAM locality is king. December 2006. http://signallake.com/innovation/FlashisGood.pdf, Dec. 2017.

[7] Martin J. Is tiered storage obsolete? Yes and no! November 2013. https://www.computerworld.com/article/2474599/data-center/is-tiered-storage-obsolete-yes-andno-.html, January 2018.

[8] Tagawa I, Williams M. High density data-storage using shingled-write. In Proc. the IEEE Int. Magnetics Conf., March 2009.

[9] Kasiraj P, New R M H, De Souza J C, Williams M L. System and method for writing data to dedicated bands of a hard disk drive:US 7490212. http://www.freepatentsonline.com/7490212.html, Dec. 2017.

[10] Gibson G, Polte M. Directions for shingled-write and two dimensional magnetic recording system architectures:Synergies with solid-state disks. Carnegie Mellon University Parallel Data Lab Technical Report, CMU-PDL-09-104, 2009. http://www.doc88.com/p-1866949816678.html, Dec. 2017.

[11] HGST. HGST delivers world's first 10TB enterprise HDD for active archive applications. June 2015. http://www.hgst.com/company/media-room/press-releases/HGSTDelivers-Worlds-First-10TB-Enterprise-HDD-for-Active-Archive-Applications, Dec. 2017.

[12] SMR. Seagate, breaking capacity barriers with seagate shingled magnetic recording. Aug. 2013. http://www.seagate.com/tech-insights/breaking-areal-density-barriers-with-seagate-smr-master-ti/, Dec. 2017.

[13] Sanvido M, Bandic Z, Cassuto Y, De Souza J, Guyot C, Harayama T. Distributed field self-test for shingled magnetic recording drives:US 8599507, http://www.freepatentsonline.com/8599507.html, Dec. 2017.

[14] Chang L P, Kuo T W. Efficient management for large-scale FlashMemory storage systems with resource conservation. ACM Trans. Storage, 2005, 1(4):381-418.

[15] Debnath B, Subramanya S, Du D, Lilja D J. Large Block CLOCK (LB-CLOCK):A write caching algorithm for solid state disks. In Proc. IEEE Int. Symp. Modeling Analysis & Simulation of Computer and Telecommunication Systems, September 2009.

[16] Kim H, Ahn S. BPLRU:A buffer management scheme for improving random writes in flash storage. In Proc. the 6th USENIX Conf. File and Storage Technologies, February 2008, Article No. 16.

[17] Levandoski J J, Larson P Å, Stoica R. Identifying hot and cold data in main-memory databases. In Proc. the 29th IEEE Int. Conf. Data Engineering, April 2013, pp.26-37.

[18] Chang Y H, Hsieh J W, Kuo T W. Endurance enhancement of FlashMemory storage systems:An efficient static wear leveling design. In Proc. the 44th ACM/IEEE Design Automation Conf., June 2007, pp.212-217.

[19] Boboila S, Desnoyers P. Write endurance in flash drives:Measurements and analysis. In Proc. the 8th USENIX Conf. File and Storage Technologies, February 2010.

[20] Soundararajan G, Prabhakaran V, Balakrishnan M, Wobber T. Extending SSD lifetimes with disk-based write caches. In Proc. the 8th USENIX Conf. File and Storage Technologies, February 2010.

[21] Nath S, Kansal A. FlashDB:Dynamic self-tuning database for NAND flash. In Proc. the 6th Int. Symp. Information Processing in Sensor Networks, April 2007, pp.410-419.

[22] Sun G Y, Joo Y, Chen Y B, Niu D M, Xie Y, Chen Y R, Li H. A hybrid solid-state storage architecture for the performance, energy consumption and lifetime improvement. In Proc. the 16th Int. Symp. High Performance Computer Architecture, January 2010,

[23] Chang L P. Hybrid solid-state disks:Combining heterogeneous NAND flash in large SSDs. In Proc. the Asia and South Pacific Design Automation Conf., March 2008, pp.428-433.

[24] Lin C I, Park D, He W P, Du D H C. H-SWD:Incorporating hot data identification into shingled write disks. In Proc. the 20th Int. Symp. Modeling Analysis and Simulation of Computer and Telecommunication Systems, August 2012, pp.321-330.

[25] Jones S N, Amer A, Miller E L, Long D D E, Pitchumani R, Strong C R. Classifying data to reduce long term data movement in shingled write disks. In Proc. the 31st Symp. Mass Storage Systems and Technologies, May 2015.

[26] Chiang M L, Lee P C H, Chang R C. Managing flash memory in personal communication devices. In Proc. IEEE International Symp. Consumer Electronics, December 1997, pp.177-182.

[27] Chang L P, Kuo T W. An adaptive striping architecture for flash memory storage systems of embedded systems. In Proc. IEEE Real-Time and Embedded Technology and Applications Symp., September 2002, pp.187-196.

[28] Hsieh J W, Kuo T W, Chang L P. Efficient identification of hot data for flash memory storage systems. ACM Trans. Storage, 2006, 2(1):22-40.

[29] Park D, Du D H C. Hot data identification for flash-based storage systems using multiple bloom filters. In Proc. the 27th IEEE Symp. Mass Storage Systems and Technologies, May 2011.

[30] Bloom B H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13(7):422-426.

[31] Dharmapurikar S, Krishnamurthy P, Taylor D E. Longest prefix matching using bloom filters. IEEE/ACM Trans. Networking, 2006, 14(2):397-409.

[32] Kryder M H, Gage E C, McDaniel T W, Challener W A, Rottmayer R E, Ju G P, Hsia Y T, Erden M F. Heat assisted magnetic recording. Proceedings of the IEEE, 2008, 96(11):1810-1835.

[33] Challener W A, Peng C, Itagi A V, Karns D, Peng Y, Yang X, Zhu X, Gokemeijer N J, Hsia Y T, Ju G, Rottmayer R E, Seigler M A, Gage E C. The road to HAMR. In Proc. Asia-Pacific Magnetic Recording Conf., January 2009.

[34] Rottmayer R E, Batra S, Buechel D, Challener W A, Hohlfeld J, Kubota Y, Li L, Lu B, Mihalcea C, Mountfield K, Pelhos K, Peng C, Rausch T, Seigler M A, Weller D, Yang X M. Heat-assisted magnetic recording. IEEE Trans. Magnetics, 2006, 42(10):2417-2421.

[35] Dobisz E A, Bandic Z Z, Wu T W, Albrecht T. Patterned media:Nanofabrication challenges of future disk drives. Proceedings of the IEEE, 2008, 96(11):1836-1846.

[36] Kikitsu A, Kamata Y, Sakurai M, Naito K. Recent progress of patterned media. IEEE Trans. Magnetics, 2007, 43(9):3685-3688.

[37] Zhang S H, Chai K S, Cai K, Chen B J, Qin Z L, Foo S M. Write failure analysis for bit-patterned-media recording and its impact on read channel modeling. IEEE Trans. Magnetics, 2010, 46(6):1363-1365.

[38] Amer A, Holliday J, Long D D E, Miller E L, Paris J F, Schwarz T. Data management and layout for shingled magnetic recording. IEEE Trans. Magnetics, 2011, 47(10):3691-3697.

[39] Greaves S, Kanai Y, Muraoka H. Shingled recording for 2-3 Tbit/in2. IEEE Trans. Magnetics, 2009, 45(10):3823-3829.

[40] Amer A, Long D D E, Miller E L, Paris J F, Schwarz S J T. Design issues for a shingled write disk system. In Proc. the 26th Symp. Mass Storage Systems and Technologies, May 2010.

[41] Cassuto Y, Sanvido M A A, Guyot C, Hall D R, Bandic Z Z. Indirection systems for shingled-recording disk drives. In Proc. the 26th Symp. Mass Storage Systems and Technologies, May 2010.

[42] Feldman T. Host-aware SMR. Nov. 2014. http://openzfs.org/w/images/2/2a/Host-AwareSMR-TimFeldman.pdf, Dec. 2017.

[43] Feldman T, Gibson G. Shingled magnetic recording:Areal density increase requires new data management. The Magazine of USENIX & SAGE, 2013, 38(3):22-30.

[44] Aghayev A, Desnoyers P. Skylight:A window on shingled disk operation. In Proc. the 13th USENIX Conf. File and Storage Technologies, February 2015, pp.135-149.

[45] Wu F G, Yang M C, Fan Z Q, Zhang B Q, Ge X Z, Du D. Evaluating host aware SMR drives. In Proc. the 8th USENIX Workshop on Hot Topics in Storage and File Systems, June 2016, pp.31-35.

[46] Narayanan D, Donnelly A, Rowstron A. Write off-loading:Practical power management for enterprise storage. In Proc. the 6th USENIX Conf. File and Storage Technologies, February 2008, pp.253-267.

[47] Russinovich M. DiskMon for Windows v2.01, 2006. https://technet.microsoft.com/enus/sysinternals/diskmon.aspx, Jan. 2018.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 张钹; 张铃;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] 孟力明; 徐晓飞; 常会友; 陈光熙; 胡铭曾; 李生;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] 林琦; 夏培肃;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] 冯玉琳;. Hierarchical Protocol Analysis by Temporal Logic[J]. , 1988, 3(1): 56 -69 .
[5] 孙成政; 慈云桂;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[6] 张钹; 张恬; 张建伟; 张铃;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[7] 王鼎兴; 郑纬民; 杜晓黎; 郭毅可;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[8] 周权; 魏道政;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[9] 赵靓海; 刘慎权;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[10] 商陆军; 许立辉;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: