GraphSSD: Graph Semantics Aware SSD

作者：Kiran Kumar Matam, Gunjae Koo, Haipeng Zha, Hung-Wei Tseng and Murali Annavaram

@ University of Southern California

现有的Out-of-core图处理系统试图通过分块的方式减缓的I/O访存瓶颈，然而这种方法产生了很多冗余的数据访问开销。本文提出的GraphSSD是一个在SSD上进行图存储、图访问和图分析的一体化方案。其主要创新点有：

• GraphSSD在用新颖的vertex-to-page框架替换掉传统的物理页映射机制，将冗余数据访问降到了最小
• 最小化了不必要的页面替换开销来支持图更新
• 提供了有效的编程接口，支持应用开发人员像访问内存内的数据一样访问图。

Introduction

在图分析领域中，由于许多图的大小已经远远超过了现有的单机主存的大小，需要来考虑以存储为中心的图处理方案。在这类问题中，访问图数据的I/O时间相比于CPU计算和内存的访问时间成为了新的系统性能瓶颈。

存储层面上来看，SSD的价格下降明显(大约100$每TB)。并且伴随着NVMe接口的普及，SSD在带宽上有了明显的提升。除此之外，SSD内部还提供一些计算功能来管理闪存。这种SSD的出现使得构建感知图语义的存储系统成为了可能。

所谓的“感知图语义的存储系统”，具体来说就是将图结构直接看成一种本地数据，而实际上它在存储一端。相比于以往都是将图看成成页的数据，这种方式可以再编程友好的前提下融合更多底层的访存优化。

背景和挑战

现代可编程的SSD平台

SSD内部通过多个闪存信道(Flash Channels)来提供高数据带宽。物理页面是一条闪存命令能够读写的最小单元。

SSD的写操作比较特殊：闪存页面在被写入操作之前要被完全擦除，但因为擦除闪存单元往往需要更高的能耗，也会污染邻近的页面，所以擦除过程以块单位上进行。故擦除过程很明显的比读写操作要慢，这叫做写放大现象。SSD都不会在每次写入操作时都执行擦除-写入的过程，而是会将更新的页内容写到空的物理页。每当页数据被更新的时候，FTL会将闪存页的逻辑块(LBA)地址映射到新的物理页地址(PPA)上，并老的页设定为失效。SSD控制器将这个映射机制放置在FTL中(闪存翻译层)的映射表里。

此外，SSD控制器内部对于失效的页建立了一个垃圾回收机制，来创造更多空的物理页面。这个机制擦除整个block，将该block中所有有效的物理页面写入到不同的block中的另一个空的物理页中。

图更新

虽然许多图处理系统都假设图是静态的，但是在实际应用场景中，节点或边信息有可能会被更新。基于此，GraphSSD支持基于Delta Graph机制的图更新。

Delta Graph机制将图更新作为一系列的快照。一开始，所有的节点使用一个连续的向量来保存他的邻居信息。当图更新产生的时候，多个更新会合并形成一个snapshot。在常规的运行间隙，一个snapshot会被写入到存储中去，而新的snapshot会建立，以容纳新的更新。graphSSD在常规的间隙也会合并snapshot，来为每个节点创建单一的连续邻接矩阵。

当使用基于CSR的图表示来合并更新时，有可能需要遍历整个图以归并更新，将其写到新的位置。而出于一致性考虑，只有在全部的归并操作完成之后，才能从新位置读取节点的邻接矩阵。因此，支持归并会对节点的遍历过程带来很大的性能损失。

架构设计

组成部分：

• SSD端：图翻译层(GTL)，图命令解码器
• HOST端：图缓存和图更新日志管理

图命令解码器

GraphSSD向上层提供一系列图访问的API。每一个API函数会进而激活SSD控制器来完成访存工作。这些函数会通过host端向SSD端发送的NVMe命令来实现。

所有的NVMe命令首先被GraphSSD图命令解码器解码，图命令解码器将GraphSSD和常规的NVMe命令执行不同的处理路线。因此GraphSSD和其他传统的存储可以共存。

一般来说，所有GraphSSD函数处理的第一步都是在闪存中访问节点及邻边。为了与原始的物理页面访问机制(FTL)进行区别，GraphSSD建立了GTL层(graph translation layer)。

GTL层和图存储格式

GTL(graph translation layer)将传统的LBA-to-PPN机制更改了，其直接将节点id映射到保存其邻接节点信息的物理NAND页序号。

GTL结构

GTL中的每一项都将节点id映射到物理页数，并且还保存有一系列的状态信息。(dirty / extension / valid)。因为很多点其邻接边非常少，可以将多个节点的信息全部定位到同一个物理页中。这样能够减少GTL的项数。GTL上只保存给定物理页中最小的节点作表项。在GTL中保存的节点信息是按照节点序号的大小从小到大进行编号的。如果是有向图，GraphSSD建立两个GTL，分别表示入边信息和出边信息。

物理页面存储

在一个物理页中，

1. 最后一部分是本页中包含的节点个数；
2. 第二部分中保存有很多二元组<节点，偏移量>，二元组记录节点的id和本节点在全页的邻接向量中的开始偏移量的比特数，最后一个二元组保存有整个页的有效数据的结束位置。
3. 一页的开始部分保存有节点邻接信息。
   这样保存的好处：能够减少GTT的大小，使得dram中可以保持一个非常大的GTT；使得访问一个节点id的全部信息不需要额外nand页的访问；

GTT的不同情况：

1. 节点Vi的所有信息都能保存在页中，平凡不讨论；
2. 节点Vi的信息太大，一个页保存不下。多页保存同一个Vi。建立物理页映射，多个项和物理页对应一个节点。在满的一页上面写一个节点的信息；
3. 节点Vi的信息恰好在拐角处，不允许这样的情况发生，采取规避措施

用GTL进行访存的例子

GTL使用二分查找的方式对节点进行查找。对于节点Vi，我们要找到下标使得j<=i<=k。当定位到Vj时，在上面的二元组进行二分查找，是否能够找到Vi。如果找得到则获取其邻接矩阵；如果Vi的邻结点很多那么将找到很多的页，来构建其邻接矩阵。

如何在上图中找到V3的邻接矩阵？
在GTT的节点id上进行二分查找，因为V3=V3 < V6,所以V3应该在P2中，之后P2会被取到，P2中的最后一个位置中写着3，也就是本页中会有三个节点。之后GTL会搜索后半部分来查找V3的偏移位置，也就是1。通过其下一项V4的位置3，我们可以知道V3的邻结点有两个，即为V1,V2。

支持图更新的设计

GTT支持的操作AddEdge(在两个点之间加一条边)和AddVertex(添加一个节点及其邻接边和权值)

1. AddEdge(Vid1,Vid2)：将Vid2添加在Vid1的邻接矩阵中，并且也要添加值到value中。因为Vid1有可能存在一个物理页或两个中，所以有两种情况，如下。

2. 当Vid1在单一页中时：Vid被添加到Vid1邻结点的最后。在Vid1之后的其他节点都向更高的页偏移进行移动。这些节点的指针也在本页的最后被更新。
   特殊情况：有可能发生溢出，溢出时重新添加一页，并且将这部分节点信息大概分成两页每页里面的空白空间相近。这是为了在之后的更新中尽可能减少溢出。

对于一个加入的页，我们应该将本GTT中的所有内容都向后移动一些，在最差的情况下，有可能移动所有的GTT项。为了防止这种现象发生，我们采用了GTT项中的扩展位，设置一个指针指向两页的位置。如下图。

3. 当Vid1在多页时，添加在最后一页的最后，和上述操作基本相似。

AddEdge的例子：

一致性考虑

将更新写在DRAM中就会有断电失去状态的风险。重要的是在重启之后要保持和重启前相同的一致性。因此每个更新都需要在重启后自动进行。我们在开始更新过程之前先创建redo-log，保存了正在更新的GTL项、deltaPointer和deltaUpdate数据。更新过程会先写新的页，之后清空GTL dirty位，将GTLentry的指针指向新的一页，最终将原来的老的物理页面设置为无效。

如果在写新的页或者在写完页，没有更新dirty位的时候断电，重启时，redo-log会从选择另一个页进行写入开始整个更新过程；之前写入的页会被垃圾回收机制回收。

如果在dirty位更新之后断电，并且GTLentry没有改动，GTL会把dirty为设置回来，重新开始更新过程；

如果在GTLentry更新之后改动，但老的页面并没有设置为无效，redo-log会简单的把老的页面设置为无效，把deltaPointer也设置为无效。

Garbage Collection机制：如果该页正在被用于保存图数据，在移动这一页的时候，GC会通知GraphSSD的运行时更新GTT。正在移动的页面已经包含有其包含的最小节点信息的内容。将该GTT项的节点信息改为这个节点信息并且更新page地址为移动到的位置。

保证更新效率

前面提起的图更新过程会导致非常多没有必要的物理页写入。每次写入都会引起read-modify-write的过程，导致非常明显的写放大现象。为了减少写放大，直到更新数量足够多或者到达一定的时间要求，所有的更新都被记录在DRAM端的log文件中。主机端的GraphSSD log manager为了处理日志功能而创建。

1. HOST端的logger

更新需要先检查被更新的节点或者边信息还在不在图里。因此主机端的logger向SSD发送一个请求，确认节点或者边的存在性。Logger也同时启动另一进程来检查边或点信息在日志文件中是否存在，这是因为要被更新的节点或边信息可能仍然存在在DRAM的log文件中，但是这个更新还没有被映射到SSD中。如果不存在则返回FALSE。注意到这只需要一个简单的读操作，不会触发物理页面的更新。

2. Delta graph

当DRAMlog文件满了或者计时器到达了设定时间时，HOST端的logger会初始化一个更新队列。GraphSSD采用Delta graph来进一步减少写放大现象。我们在graphSSD中用两个数组来实现delta graph，包括deltapointer和deltaUpdates。一个邻接表的所有更新会被放在deltaUpdate vector里。对于一个节点，新添加的更新会被链接在之前的更新之后。一个节点的DeltaPointer指向指向deltaUpdate中的最近的更新位置。

3. 有DRAM日志和Delta graph的图访问

   图访问机制在运行时，为了正确地重构图，需要知道delta graph的存在性。为了标志delta graph的存在，GraphSSD在GTT中设置了dirty bit。如果dirty bit被设置了，先找到当前的图，再利用DeltaPointer找到所有的对该节点的更新。

4. 将原始图和delta graph合并

   因为会导致比较大的写放大，因此最好周期性地将delta graph和原图进行合并。在更新过程中，我们循环过整个GTT，并且找到所有GTT项中dirty的项。对于这些节点，我们找到更新并把他们和原图的信息进行合并。在所有的节点更新做完之后，所有GTT中的dirty bit都应该被抹除

GraphSSD的缓存管理

graph的数据会被缓存再host端一部分。要求连续的节点id，因为会有很多对于连续的节点进行更新的操作，所以这样的缓存机制还是非常有用的。为了减少开销，建立了graphSSD cache，缓存了GTT，并且缓存系统可以处理graph command。在cache有miss的时候进行nand的获取，单独的nand页获取可能会导致很多host端的访问，这样也减少了对于SSD的访问。HOST端的GTT是只读的，所有的更新操作会使cache在Host上的GTT无效，并且更新会被做在SSD上。

在SSD上的GC机制中，在一个NAND页上面的数据可能会被写到另一个NAND上。如果NAND页上保存的图数据被移动了，新的NAND页码应该在HOST上的GTT上被更新。为了更新主机端的内容，SSD控制器会向host端的cache管理器发送一个请求来自动使得主机端的缓存无效，再进行更新。

实验

平台

GraphSSD在OpenSSD上被评估。

• 平台：Xilinx Zynq-7000 可编程 SoC
• 核心：双核ARM酷腾A9处理器
• PCIe 和 NAND flash信道设计为在可编程阵列的硬件逻辑；可嵌入的ARM核心运行SSD固件。此固件可以完成命令的处理，页缓存管理和FTL的功能。在GraphSSD中我们修改其固件的FTL部分，命令处理部分和主机端调用库，使得可以管理主机端的缓存情况。
• 内存：搭载1GB DDR DRAM和2TB Hynix NAND Flash DIMM,与可编程SoC相连接。
• 传输协议：与主机端使用PCIe Gen2 x 8接口相连，其支持4GB/s的带宽。
• OpenSSD上的NAND页大小为16KB；主机端系统使用4KB。
• 主机系统：Intel i7-4790CPU，16GB DDR3 DRAM。为了扩展NVMe命令，主机端安装NVMe ver.3.19 linux驱动器

数据

测试图数据：com-friendster(CF) / YahooWebScope(YWS)

结果

本文章的实验首先从基础的GraphSSD提供的图访问API进行评估，主要是GetAdjacentVerteces和GetEdgeWeight这两个函数。之后GraphSSD在应用级别的表现。对于基础API，每条命令执行1M次，并且使用随机的点或者边作为此查询过程的起点。

基础API

GraphSSD是baseline系统的1.85倍。性能提升原因的两个点：

1. baseline使用block接口来访问rowPtr和colIdx；GraphSSD使用GTL直接找到节点的邻接信息。Baseline 必须访问两个不同的页面来找到rowPtr和colIdx，但是GraphSSD用图语义可知的系统通过GTL来减少NAND页的访问。即使有百万请求，host端的缓存系统能够帮助减少NAND页的访问。没有成倍的原因是rowPtr向量比较紧凑，可以被缓存系统缓存在HOST端上来减少rowPtr有关的NAND页接触。
2. 序列化瓶颈：首先访问rowPtr，再访问colIdx，因此两个访问是有先后顺序的。着花样有可能减少SSD请求率，会导致SSD与HOST之间通信的低带宽。但是实际上因为多个请求并行发送，所以rowPtr和colIdx的请求是混杂在一起的，这种多线程的方式保证了很高的带宽利用。如下图所示。

应用

使用Random-walk应用来呈现细节的结果，根据全部应用的实验结果进行详细的分析。
A.Random-walk

a图：Y轴为相对于baseline的加速比。X轴为迭代伦次。整体提升性能大概为1.6倍。性能的提升来自于两点：NAND page访问的数量和SSD带宽的利用。

b图：因为在randomwalk中，下一个节点是随机访问的，baseline系统缓存rowPtr的作用不大。而使用一个紧凑的GTL的表示，GraphSSD能够减少NAND物理页面的访问数量。

c图：在baseline里面，访问rowPtr到访问colIdx的顺序会导致对SSD带宽的利用不充分。GraphSSD可以更好的缓存GTL，并行地去访问邻接点，所以提高了带宽。

B.所有应用

对于BFS，将能够到达的位置占全图最长路径的长度作为横坐标。对于BFS / CC / MIS / PR来说，性能分别提升1.40 / 1.42 / 1.56 / 1.29倍。原因是更少的NAND页访问和更高效的带宽利用。

C. 与GraphChi对比

因为GraphChi是为Vertex-centric为主的模型设计的，例如BFS / CC等这些不适合用这个模型的方案不能够使用。GraphChi会在每次迭代的时候会把所有的点都加入到内存中，但是其中只有一小部分的活跃点会被使用。和GraphChi来说跟它比较BFS不公平。与GraphSSD相比较的结果就是证明了其多样性。
在一次更新过程中，将所有的节点都放入到内存中，对于BFS来说不适用。随着距离变长，GraphChi的性能逐渐变差，在每次迭代过程中，所有的块都会被读取。
另一方面，PR这种更加适合vertex-centric的编程模型，许多点会被重复遍历，与GraphSSD相比，性能性能有了2.62倍的提升。
shard在每次都要被放入内存中计算，即时在shard中的计算非常少。

D. GraphSSD的开销
GTT的大小对于两个数据集来说分别是8MB和34MB，相对于整个DRAM来说非常小。原因是因为多个节点放在同一个页中，这就只需要一个项来实现映射。只有很少的节点需要多个GTT项(0% in CF and 0.01% in YWS)。如果每个节点一页，大概需要1GB到11.2GB。
空间开销：当将节点的邻接点放进NAND页中，为了简化设计，如果邻接点放不进空闲空间中，我们使用新的一个NAND页。此设计的空间开销大概4.8%或者4.9%。如果使用更加负责的设计，例如追踪一个节点在不同页之间的邻结点划分，能够轻松的省下。

E. 图更新

a图：横坐标是一共有多少个delta图。可以看出查询操作GetAdjacentVertices的性能稳定地下降，因为在更新过程中访问图很有可能涉及到UpdatePointer的追踪操作。

b图：横坐标是在一个页中有多少空的位置，纵坐标是merge过程的时间。空位置越少，merge时间越长。

c图：因为merge过程中，如果要查询节点，如果她已经被更新过直接查找page即可，但是没更新的需要找pointers。横坐标表示了merge的比例，纵坐标是性能体现。

在SSD的merge过程中，有更新直接merge。在更新NAND过程中溢出会用额外的空页来补足。对于更新在很少的NAND页中的图，这也帮助了更快的merge。对于普通的CSR来说，更新需要将所有的图信息重写写到另一个地方。

结论

GraphSSD是一个图语义感知的SSD架构，使得SSD控制器可以直接接触flash存储。GTL层负责节点信息向flash存储上物理页的转换，为了GTL的实现，提出了一个行之有效的编码方案，使得GTT的要求空间非常小。我们也提出了几个优化来处理图更新。我们完成了GraphSSD的设计在SSD的开发平台上，来展示其性能。实验证明对于简单的基本操作来说其性能提升1.85倍，对于BFS / CC / RW / MIS / PR应用其加速了1.40 / 1.42 / 1.60 / 1.56 / 1.29倍。