Computer Science ›› 2019, Vol. 46 ›› Issue (9): 66-72.doi: 10.11896/j.issn.1002-137X.2019.09.008

• NDBC 2018 • Previous Articles     Next Articles

Logless Hash Table Based on NVM

WANG Tao1, LIANG Xiao1, WU Qian-qian1, WANG Peng2, CAO Wei2, SUN Jian-ling1   

  1. (College of Computer Science and Technology,Zhejiang University,Hangzhou 310012,China)1;
    (Alibaba-Zhejiang University Joint Research Institute of Frontier Technologies,Hangzhou 310012,China)2
  • Received:2018-07-05 Online:2019-09-15 Published:2019-09-02

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: Non-volatile memory, Indexing structure, Persistence, Instantly recoverable

CLC Number: 

  • TP391
[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].
[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.
[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.
[1] WANG Xin-xin, ZHUGE Qing-feng, WU Lin. Method for Simulating and Verifying NVM-based In-memory File Systems [J]. Computer Science, 2020, 47(9): 74-80.
[2] LI Yue,WANG Fang. Survey on Storage Security of Emerging Non-volatile Memory [J]. Computer Science, 2018, 45(7): 53-60.
[3] HOU Ze-yi, WAN Hu, XU Yuan-chao. NMST:A Persistent Memory Management Optimization Approach Based on Segment Tree [J]. Computer Science, 2018, 45(7): 78-83.
[4] SUN Qiang, ZHUGE Qing-feng, CHEN Xian-zhang, Edwin H.-M.SHA, WU Lin. In-page Wear-leveling Memory Management Based on Non-volatile Memory [J]. Computer Science, 2018, 45(11A): 505-510.
[5] LI Jie. Research and Application of Lightweight Data Persistence Technology Based on ORM [J]. Computer Science, 2010, 37(9): 190-193.
[6] GU Si-shan,ZHAO Li-yang,LI Shi-xian. Practical Framework of Object Persistence [J]. Computer Science, 2010, 37(8): 146-151.
[7] . [J]. Computer Science, 2008, 35(5): 229-230.
[8] GU Yi ,WU Zhong-Fu, WEI Li ,ZHONG Jiang, MA Jin-Liang (College of Computer Science, Chongqing University, Chongqing 400044). [J]. Computer Science, 2006, 33(5): 142-145.
[9] ZENG Yi, XU Ke ,LI Ying (College of Computer Science, Chongqing University, Chongqing 400044). [J]. Computer Science, 2005, 32(12): 120-124.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .