2022-05-27-NVM与数据库索引.md

2022.05.27 分享纪要

• 分享人：龚凯
• 记录人：龚凯
• 关键词：NVM、数据库索引
• 分享PPT: 2022-05-27-NVM与数据库索引.pptx

分享内容

问题描述

在以往的数据库中，索引要么构建在DRAM中，这类的索引在断电后可以根据磁盘上的数据进行重建，在NVM场景下，数据库索引如果要构建在NVM之上，如何利用NVM的特性去设计相关索引是一个值得研究的问题，NVM最大的特性是读写性能好，非易失性等，要利用非易失性的特性就意味着在NVM上的数据需要保证崩溃一致性，并且尽量的减少维护一致性开销。

解决思路

方向一：NVM+B tree

基本思路：部分持久化、减少对cacheline的写，叶子节点按照固定大小组织，和NVM的写大小对齐

1. LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory

   键值对无序存放，通过bitmap和fingerprint信息来加快查找

   尽量写第一个cacheline，严格按照对齐后，第一个cacheline写满后迁移到后面的cacheline

方向二：NVM+radix tree

基本思路:高度压缩，原子更新

1. WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems

   前面讲到的B+tree变体通过一些方法不对key进行比较来减少对nvm的读写，而radix tree是天生不需要进行key的比较的数据结构，并且它是一种确定性的数据结构，查找不需要比较key,这会提高cache命中率,不存储key,所以插入删除不需要调整树。文章认为这种结构更适合NVM

方向三：NVM+hash

基本思路:减少resize的开销，负载均衡

1. Level Hashing: A High-performance and Flexible-resizing Persistent Hashing Index Structure

   每个地址多个槽位，让一个桶可以存放多个键值对，类似布谷鸟哈希，设计两个hash函数，设计两层结构来进行resize的切换，最后的优化结果是每次插入最多附加一次移动的插入。

方向三：NVM+skiplist

基本思路:部分持久化

1. Design and implementation of skiplist-based key-value store on nonvolatile memory

   只有数据需要持久化再NVM上，上层可以基于数据进行重建，其对跳表结构也进行了相应优化，在内存中的跳表高度是随机的，这种是不确定性设计，这种不适合上下文搜索（搜索的数据和插入的顺序关联，例如查找最近插入的数据，某数据查询过多），因此设置相关阈值，如果查询次数过多则增加节点高度，同时在跳表中设置多个头指针，这样可以缩小查找范围