基于NVM的无日志哈希表

doi:10.11896/j.issn.1002-137X.2019.09.008

计算机科学 ›› 2019, Vol. 46 ›› Issue (9): 66-72.doi: 10.11896/j.issn.1002-137X.2019.09.008

所属专题：数据库技术

• 第35届中国数据库学术会议 • 上一篇下一篇

基于NVM的无日志哈希表

王涛¹, 梁潇¹, 吴倩倩¹, 王彭², 曹伟², 孙建伶¹

(浙江大学计算机科学与技术学院杭州310012)¹;
(阿里巴巴-浙江大学前沿技术研究中心杭州310012)²

收稿日期:2018-07-05 出版日期:2019-09-15 发布日期:2019-09-02
通讯作者: 孙建伶(1964－),男,博士,教授,主要研究方向为数据库系统、机器学习、金融科技、软件工程等,E-mail:sunjl@zju.edu.cn
作者简介:王涛(1992-),男,硕士,主要研究方向为数据库系统设计,E-mail:wangt0907@zju.edu.cn;梁潇(1995-),男,硕士,主要研究方向为数据库系统设计;吴倩倩(1996-),女,硕士,主要研究方向为数据库系统设计;王彭(1989－),男,硕士,主要研究方向为数据库系统、分布式存储系统、云计算;曹伟(1984－),男,硕士,主要研究方向为分布式数据库与存储系统、大规模实时计算、云计算等;

Logless Hash Table Based on NVM

WANG Tao¹, LIANG Xiao¹, WU Qian-qian¹, WANG Peng², CAO Wei², SUN Jian-ling¹

(College of Computer Science and Technology,Zhejiang University,Hangzhou 310012,China)¹;
(Alibaba-Zhejiang University Joint Research Institute of Frontier Technologies,Hangzhou 310012,China)²

Received:2018-07-05 Online:2019-09-15 Published:2019-09-02

摘要/Abstract

摘要： 新兴的非易失内存正逐步进入人们的视野。由于这类存储技术同时具备了低延迟、持久化、大容量和字节可寻址的特性,数据库系统可以运行在只有NVM的存储架构上。在这种环境下,一些新颖的无日志索引结构应运而生,并被期望在异常故障后能即时地恢复索引能力而无须重建索引。然而,在现有的计算机体系结构中,这些索引结构为了确保NVM上数据的一致性,需要进行大量的同步操作,从而严重影响了正常执行时的系统性能。基于NVM的无日志哈希表利用指针数据的原子修改确保数据结构的一致性。哈希表使用了一种优化的Rehash方法,既减少了正常工作时的同步操作,又确保了异常故障后的即时恢复能力。实验评估表明,相比于已有的持久化索引结构,无日志哈希表在大部分工作负荷下的吞吐率表现良好,而在恢复时间、NVM资源使用量和写磨损方面具备显著的优势。

关键词: 持久化, 非易失内存, 即时恢复, 索引结构

Abstract: Emerging non-volatile memory(NVM) is taking people’s attention.Due to the advantages of low latency,persistence,large capacity and byte-addressable,database system can run on the NVM-only storage architecture.In this configuration,some novel logless indexing structures come into being and are expected to recover indexing capability immediately after an system failure.However,under the current computer architecture,these structures need a large amount of synchronizations to ensure data consistency,which leads to a severe performance penalty.NVM-baesd logless hash table leverages the atomic update of the pointer data to ensure the consistency.An optimized rehash procedure was proposed to not only reduce the synchronizations during normal execution,but also ensure the instant recovery after system failures.Performance evaluation shows that,compared with existing persistent indexing structures,logless hash tables perform well under most workloads,and have significant advantages in terms of recovery time,NVM footprint,and write wear.

Key words: Indexing structure, Instantly recoverable, Non-volatile memory, Persistence

中图分类号:

TP391

王涛, 梁潇, 吴倩倩, 王彭, 曹伟, 孙建伶. 基于NVM的无日志哈希表[J]. 计算机科学, 2019, 46(9): 66-72. https://doi.org/10.11896/j.issn.1002-137X.2019.09.008

WANG Tao, LIANG Xiao, WU Qian-qian, WANG Peng, CAO Wei, SUN Jian-ling. Logless Hash Table Based on NVM[J]. Computer Science, 2019, 46(9): 66-72. https://doi.org/10.11896/j.issn.1002-137X.2019.09.008

参考文献

[1]MEENA J S,SZE S M,CHAND U,et al.Overview of emerging nonvolatile memory technologies[J].Nanoscale Research Letters,2014,9(1):526.
[2]VENKATARAMAN S,TOLIA N,RANGANATHAN P,et al.Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory[C]//Proceedings of 9th USENIX Confe-rence on File and Storage Technologies.San Jose,California:USENIX,2011:61-75.
[3]YANG J,WEI Q,CHEN C,et al.NV-Tree:Reducing Consis-tency Cost for NVM-based Single Level Systems[C]//Procee-dings of 13th USENIX Conference on File and Storage Technologies.San Jose,California:USENIX,2015:167-181.
[4]HUANG C C.Phase change random access memory:U.S.Patent 7,504,652[P].2009-3-17.
[5]DRISKILL-SMITH A.Latest advances and future prospects of STT-RAM[C]//Non-Volatile Memories Workshop.San Diego:University of California,2010:11-13.
[6]STRUKOV D B,SNIDER G S,STEWART D R,et al.Themissing memristor found[J].Nature,2008,453(7191):80-83.
[7]Intel and Micron produce breakthrough memory technology[EB/OL].http://newsroom.intel.com/community/intel_newsroom/blog/2015/07/28/intel-and-micron-produce-breakthrough-memory-technology.
[8]ARULRAJ J,PAVLO A,DULLOOR S R.Let’s talk about sto-rage & recovery methods for non-volatile memory database systems[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.New York:ACM,2015:707-722.
[9]ZAWODNY J.Redis:Lightweight key/value store that goes the extra mile[J/OL].Linux Magazine.http://www.linux-mag.com/id/7496/.
[10]RUDOFF A.Persistent Memory Programming[J].Login:The Usenix Magazine,2017,42(2):34-40.
[11]PAGH R,RODLER F F.Cuckoo hashing[J].Journal of Algorithms,2004,51(2):122-144.
[12]HERLIHY M,SHAVIT N,TZAFRIR M.Hopscotch hashing[C]//International Symposium on Distributed Computing.Berlin:Springer,2008:350-364.
[13]MOHAN C,HADERLE D,LINDSAY B,et al.ARIES:a tran-saction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging[J].ACM Transactions on Database Systems (TODS),1992,17(1):94-162.
[14]COOPER B F,SILBERSTEIN A,TAM E,et al.Benchmarkingcloud serving systems with YCSB[C]//Proceedings of the 1st ACM symposium on Cloud computing.New York:ACM,2010:143-154.
[15]REINDERS J.VTune performance analyzer essentials[M].Intel Press,2005:112-135.

相关文章 15

[1]	张晓, 张思蒙, 石佳, 董聪, 李战怀. Ceph分布式存储系统性能优化技术研究综述 Review on Performance Optimization of Ceph Distributed Storage System 计算机科学, 2021, 48(2): 1-12. https://doi.org/10.11896/jsjkx.201000149
[2]	陈圆圆, 严丽, 章哲庆, 马宗民. 基于邻域结构的时态RDF模型及索引方法 Temporal RDF Model and Index Method Based on Neighborhood Structure 计算机科学, 2021, 48(10): 167-176. https://doi.org/10.11896/jsjkx.200900114
[3]	王千阁, 何蒲, 聂铁铮, 申德荣, 于戈. 区块链系统的数据存储与查询技术综述 Survey of Data Storage and Query Techniques in Blockchain Systems 计算机科学, 2018, 45(12): 12-18. https://doi.org/10.11896／j.issn.1002-137X.2018.12.002
[4]	赵尔平,党红恩,刘炜. 虚拟旅游中海量3D点云数据的细节层次索引技术研究 Research on Detail Level Index Technology of Massive 3D Point Cloud Data in Virtual Tourism 计算机科学, 2017, 44(10): 171-176. https://doi.org/10.11896/j.issn.1002-137X.2017.10.032
[5]	李兆兴,马自堂. 面向批量处理的大数据检索过滤模型研究 Research on Big Data Retrieve Filter Model for Batch Processing 计算机科学, 2015, 42(9): 183-190. https://doi.org/10.11896/j.issn.1002-137X.2015.09.035
[6]	于美娟许力刘岩恺马希荣. 基于索引结构的手语词库的设计 Design of the Sign Language Template Library Based on Index Structure 计算机科学, 2012, 39(12): 195-197.
[7]	王锦何先波贺春林. 改进XISS索引技术的仿真研究 Simulation Study on Improved Index Technology for XML Data 计算机科学, 2012, 39(1): 148-151.
[8]	刘艳,郝忠孝. 高维主存kNN连接索引结构的核心算法 Core Algorithm of High-dimensional Main Memory kNN-Join Index Structure 计算机科学, 2011, 38(9): 146-149.
[9]	杨朝辉,王立松. pT-树:高速缓存优化的主存数据库索引结构 Prefetching T-Tree: A Cache-optimized Main Memory Database Index Structure 计算机科学, 2011, 38(10): 161-165.
[10]	李杰. 基于ORM的轻量级数据持久化技术研究及应用 Research and Application of Lightweight Data Persistence Technology Based on ORM 计算机科学, 2010, 37(9): 190-193.
[11]	古思山，赵黎阳，李师贤. 一种实用的对象持久化框架 Practical Framework of Object Persistence 计算机科学, 2010, 37(8): 146-151.
[12]	李博涵,郝忠孝. Rav-tree:一种有效支持反向近似近邻查询的索引结构 Rav-tree:An Efficient Index Structure for Reverse Approximate Nearest Neighbor Query 计算机科学, 2010, 37(1): 158-162.
[13]	. 基于Hibernate与Struts的鱼雷库数据持久化研究计算机科学, 2008, 35(5): 229-230.
[14]	古毅吴中福魏丽钟将马金亮. 高维空间数据索引结构分析研究计算机科学, 2006, 33(5): 142-145.
[15]	张文杰李建中张炜. E3D R-Tree：一种处理移动对象数据库历史查询的索引结构计算机科学, 2005, 32(9): 103-107.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于NVM的无日志哈希表

Logless Hash Table Based on NVM

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0