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 跳表是什么？