Enforcing Crash Consistency of E

NVM图阅读笔记

摘要

许多复杂的网络系统上都使用了图这种数据结构，然而现在的这种图结构并不能很好的适配NVMM这种介质：（1）这种结构并不能做到错误恢复的能力（2）NVMM写和读相比DRAM均会带来严重的延迟

本文提出了一种evolving graph的方法，设计了多版本的数据结构：其中旧版本数据存储在 NVMM中。而其他版本被拆分成两部分一部分存在NVMM中另一部分在DRAM中以减少NVMM的延迟。

结果表明NVGraph减少使用了70%的内存单效果与内存相当。

INTRODUCTION

文中介绍内存图的数据一般包括三个部分：拓扑结构、运行时状态、应用定义的基础数据（这个感觉不是很抽象）。

由于内存容量有限，所以很多方法使用了scale-out or scale-up方法。

碰撞一致性保证系统错误后能够恢复，而图的数据并不是可恢复的，由于（1）首先需要更新参数（2）需要更新状态

在两次写中间如果出现错误那么无法恢复。

现在多使用保存checkpoint的方法，并且会造成非常严重的性能瓶颈。

仅仅单纯使用NVM有如下两个问题：1 DRAM与NVM中均需要保存 2 无法使用NVMM的字节寻址的优势。

本文提出了一种数据结构：NVGRAPH。它按照时间的连续顺序存储图的结构。为了保证碰撞可恢复，NVGRAPH设计使用多版本的数据结构来存储应用定义的数据以及运行状态数据。

NVGraph的设计思想

文中提到若想要保证数据具有一致性，那么需要至少两次的写操作。一次写为应用数据A，另一次为保存运行状态。

image.png

上图为NVGRAPH中Dram与Nvm的结构图。

在执行的过程中，这些拓扑结构数据并不是可恢复的（index table 与 edge table）。并且NVGRAPH在DRAM中管理快照减少数据在NVMM中的操作。

图中A表示应用定义的数据，R表示运行状态。

具体的细节见文章。

在运行过程中需要注意如下的内容：n-1版本不能动、n-1与n状态的共享版本不能动。

image.png

根据图中所述，Sbase中的所有变量都存入NVMM中；

• index table包括两个参数：Snapshot ID与Offset/P。

Snapshot ID指向具体的Edge table而Offset为该edge table中的第几个块。

• edge table also包括两个参数：Node ID和Flag。

Node ID表示节点的编号，而字母N，D分别代表存储在NVM或者DRAM中。

而我们现在需要具体关注其标号的具体含义：

首先我们需要看index table中标号的含义。

例如Sbase中的(0,1)指向第一个edge table中的第二块（0，D）。

而对于S1中的（1，P），表示当前操作添加或者删除节点。而这里的1代表指向编号为1的edge table（C0:0,2）。这里的2表示新增节点2-->0(这个0代表0，N中的0)。而（C0:0,2）中的0代表其余节点沿用Sbase。

NVGRAPH在DRAM中管理了一个cache快照，如果cache满了则删掉最旧版本。

下面文章讲解了一些关于对节点的操作过程。

删除节点需要我们在index table中标记“node”为“delete”，而真正的删除会在下面的垃圾回收中进行。

NVGraph在edge-list中加载图数据，在加载table表之前会对其进行排序。当上一个版本的数据不需要的时候，会调用flattening操作将其合并为新的snapshot。

GC垃圾回收会检测NVMM的空间可利用率，当到达一定值后自动进行。

数据合并：第n步完成后，进行合并。

image.png

之后标记n-1版本的数据为“delete”。

系统会自动更换base快照，如果Si的访问频率更快，那么将会用Si来替换当前快照。而这个操作是在后台运行的）。

数据恢复过程：如果在第n步遇到错误，那么会将N的版本标记为“delete”，最终使用NVMM中的n-1版本来恢复DRAM、NVMM以及Common数据。（？？这里怎么恢复的？）

下面需要我们解决如何分配资源的问题。

规定Dram的大小要比SizeDRAM设定的门限值要小。那么如何选择热数据呢？

• 1 选择节点：我们选择更为“重要”的节点。记录节点访问频率，并计算他们的特征中心度，之后根据内存访问频率进行分组。我们发现，访问最多的前10％节点的特征值中心性值也始终比其他百分位组中的节点（例如20％和30％）更大。所以我们可以使用eigenvalue来相应的找出重要的节点。

image.png

• 2 对边如何选择。

• 3 增量更新。当新的快照创建的时候，上述节点和边便会产生。

而如何选择cache快照的大小呢？

在DRAM中NVGRAPH会存一个快照在cache中，所以我们需要决定这个大小，以便我们有更高效的访问频率。

image.png

测试部分

测试部分看原文讲解，这部分并不是很难。主要关注它的流程部分，这个部分比较绕，花费了我很多时间。