[Talks][DB Talk] Shimin Chen: Persistent B+Trees in NonVolatile Main Memory (02/10/2015, 11:00am-12:00pm, Eli Lilly Room)

Presenter: Shimin Chen
Date: Tuesday, Febuary 10, 2015
Time: 11:00am - 12:00pm
Location: Eli Lilly Room, Sennott Square, University of Pittsburgh

Computer systems in the near future are expected to have Non-Volatile Main Memory (NVMM), enabled by a new generation of Non-Volatile Memory (NVM) technologies, such as Phase Change Memory (PCM), STT-MRAM, and Memristor. The non-volatility property has the promise to persist in-memory data structures for instantaneous failure recovery. However, realizing such promise requires a careful design to ensure that in-memory data structures are in known consistent states after failures.

I will talk about our recent study on persistent in-memory B+-Trees. While traditional techniques, such as undo-redo logging and shadowing, support persistent B+-Trees, we find that they incur drastic performance overhead because of extensive NVM writes and CPU cache flush operations. PCM-friendly B+-Trees with unsorted leaf nodes help mediate this issue, but the remaining overhead is still large. We propose write atomic B+-Trees (wB+-Trees), a new type of main-memory B+-Trees, that aim to reduce such overhead as much as possible. Experimental results show that compared with previous persistent B+-Tree solutions, wB+-Trees achieve up to 8.8x speedups on DRAM-like fast NVM and up to 27.1x speedups on PCM for insertions and deletions while maintaining good search performance. Moreover, we replaced Memcached’s internal hash index with tree indices. Our real machine Memcached experiments show that wB+-Trees achieve up to 3.8X improvements over previous persistent tree structures with undo-redo logging or shadowing.

Shimin Chen is a professor at Institute of Computing Technology, Chinese Academy of Sciences. His research interests are in data management systems, big data processing, and computer architecture. He received his Ph.D. in Computer Science from Carnegie Mellon University in 2005, and his B.E. and M.E. from Tsinghua University in 1997 and 1999, respectively. He worked as a researcher, senior researcher, and research manager at Intel Labs, Carnegie Mellon University, and HP Labs before joining ICT CAS in 2013. He has won a ICDE'04 best paper, a SIGMOD’01 runner-up best paper, and a 2008 Computer Architecture Top Picks award. He has served as PC area chair on DB Track - Cloud Computing and Big Data Analytics in CIKM'14, Co-Chair for DAMON'12, Industry Co-Chair for WAIM'14, and PC member for various conferences including SIGMOD, VLDB, ASPLOS, ICDE, and CIDR.