图数据库 | 11、图数据库架构设计——高性能图存储架构(下)

在上篇内容中，老夫着重讲了高性能图存储系统的特点，咱们继续往下讲重点——高性能存储架构的设计思路！！

2.高性能存储架构设计思路

首先呢，存储架构以及核心数据结构的设计思路通常围绕如下4个维度来进行：

一是：外存与内存使用占比（角色分配及分配比例）​；

·是否利用缓存，如何优化缓存；

·是否进行数据或记录的排序，如何排序；

·是否允许数据或记录的更改（可变性）​，以及如何更改。

（1）内外存占比

100%使用外存的数据库是极为罕见的，甚至可以说和高性能数据库关系不大。同样地，100%使用内存的数据库也非常罕见，即便存在“内存数据库”这一门类，通常作为关系型数据库的一个子类或键值库，数据也会持久化在外存之上，原因不外乎是内存的“易失性”​。

在绝大多数现代数据库的架构设计中，都会利用外存与内存中的数据结构特性来实现某种存储加速。除了缓存设计、排序与否和数据可变性之外，对于图数据库而言，因为其存在特殊的数据空间网络拓扑结构，所以内存用来存放一些关键数据（如元数据、映射数据、临时算法数据、索引、需要实时计算的元数据之属性类数据等）​，外存用来存放不需要实时计算的海量剩余数据。这种内、外存按照一定比例来搭配的方式，通常会实现性能较大幅度的提升。

内外存占比并没有固定的方式。在很多传统的IT架构中，服务器的内存资源都占比较低，并且这种情况在云化的过程中愈演愈烈，不得不说是一种倒退——在数据库的应用场景中，内存的占比不应当低于外存的1/8（12.5%）​，也就是说如果有1TB的外存，至少应该有128GB的内存。而在高性能计算场景中，内外存占比可以达到1/4（25%）以上，如果有2TB的外存持久化层数据，内存至少可以是512GB。在这一点上，很多私有云部署的场景由于无法分配大内存，也无法管理大内存的虚拟机，因此不得不说这种云虚拟化本身是与高性能计算背道而驰的。

需要注意的是，为了磁盘访问而优化的数据库数据结构和代码逻辑，虽然可以直接在固态硬盘上运行，但是存在大量的优化和调整空间，这些细节也是数据库架构设计最为繁杂之处。如果我们再把持久化内存的硬件方案引入，就会让问题更复杂。很显然，一套代码逻辑、一套数据结构要泛化并适配到全部的硬件架构之上，并且都能获得最佳的性能，是不太现实的。在实际的数据库架构设计中，我们总在不断地取舍（平衡）​，包括面向底层硬件而做出相应的适配。我们认为那种忽略底层硬件而一味相信硬件透明的数据库设计方案是不可行的——尽管作为数据库下层的文件系统与操作系统已经做了很多抽象、适配的工作，然而高性能数据库依然需要面向具体的硬件环境进行精准的数据结构、架构及性能调优。

（2）缓存

存的目的本质上是为了降低I/O数量，提高系统吞吐率。几乎所有的落盘数据结构都会利用缓存来加速（帮助更快速地定位、读取或回写）​。另外，缓存的设计与数据可变性以及排序与否经常需要通盘考虑，因为是否允许数据被更改，以及数据是否需要排序后存储直接影响了缓存的设计逻辑与实现，反之亦然。

图数据库的存储引擎对于缓存的利用似乎较其他类型的数据库更多，这里不妨罗列一下可能用到缓存的情况：数据写入、数据读出、元数据索引、全文搜索索引、近邻数据、中间操作结果，以及高并发、多版本维护场景等。

需要注意的是，无论是机械硬盘还是固态硬盘，读取与写入的最小单位是块（block）​。机械硬盘通常在硬件层面用扇区（sector）表示，如下图所示，但是在操作系统层面，和固态硬盘一样统一用块表示，一个块通常可设定为固定大小，例如4KB，可能包含多个扇区。在Linux操作系统中，下面两个命令可以方便地判断block与sector的大小：

fdisk - 1 | grep "Sector size"
blockdev - getbsz/dev/sda

​

图3： 机械硬盘的存储部件示意图

在机械硬盘上，活动部件的寻址与磁盘转动时间占到了每次操作的90%以上，而在固态硬盘（及持久化内存、动态内存）中，由于不存在这个物理部件移动而消耗时间的环节，也因此指数级地缩短了每次操作的时耗（如图4所示）​，时间消耗从每次数毫秒降低到了几十到几百微秒（约40倍以上的性能提升）​。 

​

图4：机械硬盘与固态硬盘访问时延分解对比示意图

在固态硬盘中，最小颗粒度的存储单位是Cell，其次是String、Array、Page、Block、Plane、Die、Solid State Drive（SSD）​，最后的SSD就是我们熟知的固态硬盘（图5）​。而可编程（写）​、可读取的最小单位是Page（页）​，最小可擦除（erase）的存储单位是Block（块）​，每个Block通常由64～512个Pages构成。 

​

图5：固态硬盘的存储单元间的层层嵌套关系示意图

无论是机械硬盘还是固态硬盘，读写的单位不是操作系统、文件系统与数据库存储逻辑层面所需要存储的最细颗粒度的数据记录——比特，甚至都不是字节或者多个字节所构成的字符、整数、浮点数或字符串。在硬件层面这么设计是为了提高存储效率。举个例子，一个人从家里到公司的距离是20km，打车需要1小时，他需要从家里带10本书到公司，可以一次性运送10本书去公司，也可以多次运送，从运输成本、时间成本上综合考量，显然是一次性运送最划算。同样地，在面对存储媒介的时候，缓存设计就是这种“一次性”批量运送（存取）技术手段。类似地，在分布式架构设计中，如果每个操作都涉及网络请求与传输过程，合理地合并多个操作后再统一传输不失为一种优化方案。 

下图示意的是缓存与物理I/O之间的“反比”关系，理论上缓存越多，I/O越低，但实际上，缓存量到达C点后，对于I/O降低（性能提升）的效果就不明显了。这个C点就是我们在设计存储缓存时的一个“高规格”目标，而B或A则是低成本投入时的“中低规格”目标。

​

图6：缓存与I/O之间的“反比”关系

总之，缓存是一个贯穿整个计算机硬件和软件发展历程的核心技术。即便是在最极端的情况下，比如在数据库或应用软件设计中没有主动使用任何缓存技术，底层的文件系统、操作系统、像硬盘、CPU等硬件依然会通过缓存来实现存取与计算加速。缓存的出现让系统架构设计变得更为复杂，因为系统有更多的组件需要管理，例如保持更新、提升命中率、清空重置等。

（3）排序（与否）

数据排序是一个随着数据记录数量增长而越来越常见的存储优化技术。是否排序取决于具体的业务场景。如果是对插入数据进行排序，那么在连续存储类型的数据结构中，可以直接使用地址下标来以最低延迟访问一条记录，或者快速读取一段地址空间内存放的数据记录。再结合缓存的加速策略，连续存放的数据记录可以更充分、有效地利用缓存技术，但如果中间需要插入或删除一条记录，操作成本会比较昂贵。 

在之前的内容中，老夫就介绍过“近邻无索引”存储数据结构，可以以O(1)的时间复杂度来从任意一个顶点去定位它的近邻（即一度以内的邻居）顶点。这种数据结构设计本身的存取效率已经高于索引。在不考虑并发锁等复杂的情况下，增量写入、读取、更新效率都可以做到O(1)，但是删除的复杂度会更大。因为像数组这类连续存储的数据结构，从中间位置删除记录会导致整个后序数据记录移位。这个时候，如果数据记录可以不按照Key或ID排序，则可以考虑在定位要被删除的数据记录后，与末尾的记录置换，完成置换后再删除尾部记录。这个操作称为接入-删除（swtich-on-delete）操作，其复杂度依然可以等同于O(1)（实际复杂度是最低延迟的O(1)的7～10倍）​，操作示意图如图7所示。

​

图7：接入— 删除操作

非连续存放的特点是可以把数据结构设计为删除单个记录，效率可能较高，如O(log N)（通常这一数值不大于5）​，但是连续读取的多条记录的范围查询成本则很高，例如，读取K条记录的时耗为KO(log N)。

范围查询在很多应用场景中被大量使用，但它似乎与非排序存储方式相冲突。在之前的内容中我们介绍过LSMT，这里介绍一种基于LSMT优化的WiscKey（Wisc是University ofWisconsin-Madison的缩写，Key指的是一种Key-Value Store的存储优化方案）​，数据结构可以兼顾写的效率与非排序存储的空间利用优势。

首先针对磁盘而言，LSMT的特点如下：
·批量、顺序写入；
·顺序访问高通量（顺序访问的效率是随机访问的数以百倍计）​；
·读写放大效应（并没有面向SSD优化，记录读写都会被放大很多倍）​。
其次，固态硬盘的特点如下：
·随机读性能高；
·并行操作能力。
WiskKey的设计核心理念是键值分离（仅键需要排序）​，它包含如下几个面向固态硬盘的优化策略（图8、图9）：

图8： LSMT与WiscKey

图9：WiscKey中LSMT与vLog分离

 ·拆分排序与GC（垃圾回收）​；

·利用固态硬盘在范围查询时并发的能力；

·在线、轻量级GC；·最小化I/O放大；

·崩溃一致性。

经过WiskKey优化的固态硬盘上的顺序、随机访问性能如下图所示。可以看到，当访问的数据大小在64K～256KB范围内的时候，32线程并发访问的吞吐率已经和串行访问不相上下了。

图10： ”WiscKey串行、单线程随机、32线程随机范围查询性能比较

WiscKey是基于LevelDB的核心代码优化的，经过优化后，WiscKey在随机访问和顺序访问上都有一定程度的性能提升，特别是在键所对应值的占用空间大于4KB之后（下图11）​。

当然，有多少实际业务中的键值需要4KB以上的存储空间，是个需要具体探讨的问题。以老夫的经验，实际键值普遍在1KB以内。这个时候，WiscKey与常规的LSMT的性能相差无几。

图11：基于对LevelDB代码优化的WiscKey与LevelDB查询性能比较

（4）数据可变（与否）

数据是否可变（mutability）指的是数据记录的更新采用追加模式（append-only）还是允许本地更改。不同的模式适用于不同的场景，也因此而衍化出了不同的“加速”模式。

例如最早在Linux内核设计中实现的Copy-on-Write模式（COW）​，即不更改原数据，采用先拷贝再更改的方式。LSMT与B-Tree之间的区别也通常被归纳为不可变与就地更改两种缓存加速模式的区别。

COW所采用的一个技巧被称为无锁式记录更新，如图3-12所示。具体操作步骤如下：

图12：无锁式更新变量（记录）

1）定位变量（记录）A（内容为X）​；
2）拷贝A至A′（非深度拷贝，指针级拷贝）​，创建内容为Y；
3）在一个原子级操作（compare-and-swap）中，A指向Y，切断A′与该变量关联关系，之前的X记录被GC（垃圾回收）​。

把上面的操作放在一颗二叉树中，也是一样的逻辑，COW的核心在于尽可能地避免深度拷贝（deep-copy）​，使用指针来通过轻量级的操作实现浅层拷贝（copy-by-reference）​，并只在必要的时候再进行深度拷贝以及精准的记录更新操作。

在Linux操作系统的内核中，当父进程需要衍生子进程时就使用了这种COW的技术，节省了内存与CPU时钟的消耗。 

B-Tree类型的数据结构虽然实现了就地更新记录（in-place update）的功能，但是带来了写放大（write-amplification）的问题，以及处理锁和并发时的设计复杂度较高。Bw-Tree由此应运而生，它的全称是Buzzword-Tree，是一种内存级、可变页大小、高并发、无锁数据结构。

 Bw-Tree有4个核心设计（图13）​：

·基点（base nodes）和变化链（delta chains）​。

·映射关系表。

·合并与垃圾回收。

·结构化更改（SMO）​：为了实现无锁化。

确切地说，这4个设计都是为了实现无锁式高并发，当然，代价就是使用了更多的内存空间。其示范意义在于，高性能系统的设计思路无外乎以下几点：
1）使用和适配更快的存储设备（包括内存、包括分级存储）​；
2）尽可能实现更高的并发（配合数据结构支持）​；

图13：Bw-Tree的内部逻辑关系

3）避免使用过多的、颗粒度太粗的锁；
4）避免频繁地拷贝数据等操作（数据利用率太低）​；
5）贴近底层硬件，避免过多的虚拟化和过多的中间环节。

老夫在上一篇文章中就说过高性能存储架构设计思路要聊的东西非常多、非常细。今儿还没聊完，下一篇咱们接着叙——高性能图计算架构！

今天先这样，已经洋洋洒洒快五千字了，大家先吸收一下，明天或后天继续码字。

 

· END ·

（文/Ricky - HPC高性能计算与存储专家、大数据专家、数据库专家及学者）