关于数据库:LBTree

VLDB 论文浏览笔记

可间接看 LB+-Tree 局部。

论文题目

《LB+-Trees Optimizing Persistent Index Performance on 3DXpoint memory》

http://www.vldb.org/pvldb/vol13/p1078-liu.pdf

Minimizes the number of NVM Line writes and performs Logless insertions.

简介

3DXpoint 个性：

• 应用 clwb，sfence 等指令，将数据从 cache 拷到 3DXpoint，会大大降低写性能。
• 3DXPoint 内存外部数据存取粒度是 256B。等等

论文核心思想

在一个 cache line 中，批改的字数对 3DXpoint 的写性能没有影响。提出持久性索引 LB+-tree 来进步一次写入的字数，缩小写 NVM line 的次数。晋升 LB+-tree 插入性能的办法：

1. Entry moving。在叶子节点的第一行创立更多空槽。

   • 思考插入新索引项，更新叶子节点的头。
   • best case：头部所在的行（即第一行）有空槽，则插入和更新需一次 NVM 行写入。
   • 另一状况：第一行已满，叶子节点的另一行找到空槽，更新头、写新项，需两次行写入。
   • 策略：将尽可能多的项从第一行挪动到要写入的行，以产生更多空槽。
2. Logless node split。应用原子写（NAW）来缩小日志开销（先前的基于 NVM 优化的 B + 树应用日志来反对节点宰割）。

3. Distributed headers。使得 (1)(2) 对 multi-256B 节点十分无效。

   • 对于 multi-256B 节点，先前的做法是将元数据信息放在在节点的头部。（元数据信息包含：标记空 / 满项的 bitmap、减速码搜寻的指纹）。然而当节点大小增大时，第一行的槽项数会缩小。该论文：在节点中，每 256 个 block 调配一个头。
4. 前面证实

• 在断电和过程解体的状况下，算法能保证数据一致性。
• 微基准测试。插入操作，比照传统均衡树，NVM 行写入次数的缩小。
• 零碎试验：X-engine，Memcached。

背景

3DXpoint 两种模式

• 内存模式。DRAM 作为 3DXpoint 的 cache，主存容量和 3DXPoint 雷同，对不写内存的利用敌对。毛病：不反对持久性数据结构；更长的加载数据工夫，需先访 DRAM，缺失再访 3DXpoint。
• app-direct 模式。DRAM、3DXPoint 与 CPU 直连，应用 PMDK（持久性内存开发工具）来装置文件系统。本文关注该模式。

论文三发现

• 在一个 cache 行中，批改的字数对 3DXpoint 的写性能没有影响。先前数据比拟写：读硬件原始数据，比拟新的，仅写入批改的 bit，则写提早会比写整行要小。作者认为，目前的 3DXPoint 没有对数据比拟写进行优化。如其中一款 Intel 的，数据有加密，批改一个 bit 会扭转多个 bit。
• 3DXPoint 内存外部数据存取粒度是 256B。cache line 是 64 个字节。读操作：3DXPoint 读 256 个字节，给 cache 64 个字节；写操作：3DXpoint 读 256 个字节，批改 64 个字节，再写 256 个字节。
• 使用量低于 1 / 8 时，应用程序工作集变大，3DXPoint 性能升高。应用程序拜访的数据大于或等于 3DXPoint 容量的 1 /8，内存性能稳固。（因而试验需至多填满 1 /8）

数据一致性策略

一致性操作：缓存行 flush 指令（如 clwb）和内存栅栏指令（如 sfence），保障脏数据写回 NVM。开销大。

NVM 保证数据一致性的策略：logging , shadowing , PMwCAS , NVM atomic writes (NAW)。

• logging：write-ahead logging。故障复原，依据日志。
• shadowing：NVM 中新调配空间，拷贝要批改的数据结构，批改拷贝，再应用 NAW 切换。留神点：须仅有一个指针指向要批改的数据（B+ 树满足）。故障复原，指向新或旧的？
• PMwCAS：兼顾数据一致性和无锁操作。

前三种办法，兴许比间接批改持久性数据结构开销大得多。

NAW

8B 写，后接 clwb（persist），sfence。8B 写是原子的。

证实一致性。……

对于某些数据结构，如 B + 树叶子节点，能够采纳多个两头可复原状态、多个 NAW 来保障一致性。

优化的 NVM B+ 树

• 基于缓存优化，缓存行对齐。
• 尽可能减少 NVM 写次数。如应用 bitmap，叶子节点不排序，能够缩小挪动的次数。
• 应用 NAW 来保证数据一致性。如 WB+ 树，叶子结点蕴含间接数组，以辅助在无序叶子结点的排序。这和 bitmap 同，在插入时都须要 NAW 两次，是可复原的。
• 非叶结点放入 DRAM 中。如，Oukid 的抉择一致性策略：将 FP-tree 的非叶结点放入 DRAM，叶子结点放 NVM（若出故障，可从叶子结点中复原非叶局部）；搜寻码 1 字节指纹，SIMD 减速叶子搜寻。
• 并发的 B + 树。
• Bztree，应用 PMwCAS，实现无锁数据一致性。

对 3DXPoint 设计准则

• 缩小 NVM 行写入的次数，而非字写入次数。
• 叶子结点大小 256B 的倍数.
• 齐全不应用日志，用 NAW 实现结点宰割。

LB+-Tree

构造

仿照 FP-tree。

• 非叶结点放 DRAM，叶子结点放 3DXPoint。
• lock 位：并发管制。alt：指明可选的兄弟结点。
• 指纹：减速搜寻。hash(key)：计算出 1 字节的指纹，应用 128bit 的 SIMD。
• alt：抉择以后正在应用的指针
• sibling ptr, 各 8B。无效的 sibling ptr 指向以后叶子结点的右兄弟指针。如果以后叶子结点为 NULL，则为 NULL。为什么要这样设计？

并发管制

仿照 FP-tree，联合 HTM(硬件事务存储)和 lock 位来实现并发管制。本试验用原语实现 HTM。

留神，缓存行 flush 指令不能兼容 HTM，因为 HTM 在事务提交前，须要在 cache 中放弃批改的 cache line。然而，在 3DXPoint 中，缓存行 flush 指令是必须的。用 lock bit 来解决。

index 操作达到叶子，查看 lock。若 lock=1，阐明已有 index 写操作锁住结点了，废止事务。若 lock=0，持续，读则读，写则先 lock=1，提交事务，再真正写（事务外写，应用 clwb）。

搜寻

• 3，5，11 并发管制
• xbegin(), xabort(), and xend() 别离为开始、废止、提交事务。胜利开始，返沪_XBEGIN_STARTED，若因 xbort()或硬件抵触，则继续执行 xbegin()
• 搜非叶结点，查叶子结点
• 应用 SIMD 匹配指纹，失去候选集
• 查看 slot 是否非法，key 是否等

插入：缩小 line writes

与 header 同 line，需写一次 line；否则，需写两次。

将数据从 line0 移到其余 line 时，批改 header 的 bitmap 和指纹：16B dword。

证：256 结点 LB+-tree，若叶子结点有空槽，插入操作能保障叶子结点的数据一致性。

（只在 lineid 行找空槽）。

结点宰割

• 调配新结点，将 14 个索引项中最大的 7 个拷到新结点的最初两个 line。
• 替换兄弟结点，以在不扭转以后无效 指针的状况下，插入新叶子结点？（新的兄弟 1 指向旧的无效的兄弟结点的指向，旧的 alt 扭转，无效的指向新叶子结点）
• 状况 1：插入到新叶子结点（17-18：leaf 的 bitmap 变了）
• 状况 2：插入到旧叶子结点。20-23：先 persist 新叶和兄弟指针，插入项

（结点宰割之后旧结点没有马上将 line0 的挪动到 line2, line3）

一致性证实。

删除

查找，用 NAW 置空 bitmap 对应位。

一致性证实。

故障复原

一致性已证实。

出故障，扫描叶子，重建非叶。

multi-256B 结点

起因剖析

应用大结点的起因：非叶局部占更少 DRAM；内存带宽、内存控制器队列大小可能大于 256B。前面 4.2 局部，发现，512B 的叶子结点性能更好。

应用分布式头部的起因：

若应用集中式 (centralized) 头，一个头（蕴含 ​-bit map, ​ x1B 指纹, lock,alt 位），两个兄弟节点，​ x 16 B 的数据项。

​

则当结点大小为 512B，768B，1024B 时，头部大小别离为 32B, 49B, 66B，则 Line0 残余的数据项数目别离为 2，0，0。因为咱们的目标是缩小 NVM 写的次数，这种办法效率低。

应用分布式头部。

应用 H1 的起因：若无，则结点宰割时，需更新分布式头部，一个 NAW 无奈解决多个头部写，且可能要求日志记录。

因而在 2~m 块的开端引入可选头部。复用 alt，用来示意前后哪个头是无效的。？？

写有效的头，再用一个 NAW 来批改第一个头部，切换兄弟结点和 2~m 块的头。该过程不需写日志。？

操作

• 搜寻：指纹比拟，bitmap 查看，key 比拟。
• 删除：间接更新第一个头部
• 插入操作：寻找第一个非满 block，进行插入。若所有 block 均满，进行节点宰割。
• 节点宰割：调配新节点；把一半的项拷到新节点；批改代替兄弟节点和代替头部；应用一个 NAW 去更新第一个 block 的头部；切换 alt

一致性证实。

代价剖析

试验

比照 B +tree，WB+tree，FP-tree。LB+Tree 基于后两者提出，但这两者没有 entry moving，须要写日志，且采纳集中式头部。LB+-Tree 则通过应用代替兄弟指针和代替头部实现无日志写。FP-Tree 和 LB+Tree 应用指纹数组反对 SIMD 查找，WB+tree 则应用间接数组来反对二分查找。

micro-benchmark

X-Engine 和 Memcached

其余

可能能够进挖的点？

• 依据 3DXPoint 的 endurance，进行 wear-leveling。（本文 2.2 开端）
• 第三发现的起因。作者解释：可能为 3DXPoint 内存模块的缓存机制。

没看懂的：

• 论文提到的 PMwCAS。
• 论文的并发管制？？怪怪的。
• 看看插入的代码吧
• 为什么要设计两个兄弟指针？怎么实现无日志写的？
• 插入、宰割的代码为什么要用 dword
• 插入的代码为什么不须要 clwb leaf[to]所在的 line
• muti-256B，节点宰割没看懂，具体的代码？（是将每个 block 的一半分给另一个节点吗？将整个 block 复制给新节点更高效吧？然而这如同和代价剖析局部矛盾了？）
• 代价剖析。LB+ 的状况 leaf n 的计算，worst case，为什么有 3 个插入须要写 2 次，其余都是 1 次？
• 插入 worst case 不思考数据迁徙的开销吗 — 思考的哦
• 代价剖析。传统的 leafn 为什么要规定新的节点是填充在后面而不是前面的？
• multi-256B 的状况，代价剖析？对照的是集中式头部 迁徙写 还是 分布式头部不迁徙写？看阐明，如同是前者？然而计算 又像是后者。
• skip-list 跳表是什么？