万字长文带你详解九大数据存储引擎结构（下）

五．倒排索引存储

对Mysql来说，采用B+树索引，对Elasticsearch/Lucene来说，是倒排索引。倒排索引(Inverted Index)也叫反向索引，有反向索引必有正向索引。通俗地讲，正向索引是通过key找value，反向索引则是通过value找key。

Elasticsearch是建立在全文搜索引擎库Lucene基础上的搜索引擎，它隐藏了Lucene的复杂性，提供一套简单一致的RESTful API。Elasticsearch的倒排索引其实就是Lucene的倒排索引。

1.  Lucene 的倒排索引

倒排索引，通过Term搜索到文档ID。首先想想看，世界上那么多单词，中文、英文、日文、韩文 … 如每次搜索一个单词都要全局遍历一遍，明显不行。于是有了对单词进行排序，像B+树一样可在页里实现二分查找。光排序还不行，单词都放在磁盘，磁盘IO慢的不得了，大量存放内存会导致内存爆了。

下图：通过字典把所有单词都贴在目录里。

Lucene的倒排索引，增加了最左边的一层「字典树」term index，它不存储所有的单词，只存储单词前缀，通过字典树找到单词所在的块，也就是单词的大概位置，再在块里二分查找，找到对应的单词，再找到单词对应的文档列表。

假设有多个term，如：Carla,Sara,Elin,Ada,Patty,Kate,Selena。找出某个特定term,可通过排序后以二分查找方式，logN次磁盘查找得到目标，但磁盘随机读操作较昂贵(单次Random access约10ms)。所以尽量少的读磁盘，可把一些数据缓存到内存。但term dictionary太大，于是就有了term index.通过trie树来构建index;

通过term index可快速定位term dictionary的某个offset，从这个位置再往后顺序查找。再加上一些压缩技术(FST)，term index 的尺寸可以只有所有term尺寸的几十分之一，使得用内存缓存整个term index变成可能。

FST Tree

一种有限状态转移机，优点：1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；2）查询速度快。O(len(str))的查询时间复杂度。

示例：对“cat”、 “deep”、 “do”、 “dog” 、“dogs”这5个单词进行插入构建FST（必须已排序），得到如下一个有向无环图。

FST压缩率一般在3倍~20倍之间，相对于TreeMap/HashMap的膨胀3倍，内存节省就有9倍到60倍！

2.  与MySQL检索对比

MySQL只有term dictionary，以B-树排序的方式存储在磁盘上。检索一个term需若干次random access磁盘操作。而Lucene在term dictionary的基础上添加了term index来加速检索，以树的形式缓存在内存中。从term index查到对应term dictionary的block位置后，再去磁盘上找term，大大减少磁盘的random access次数。

Term index在内存中是以FST(finite state transducers)的压缩形式保存，其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可比B-树更节约空间。

3.  联合索引结构及检索

给定多个查询过滤条件，如”age=18 AND gender=女”就是把两个posting list做一个“与”的合并。对于MySql来说，如果给age和gender两个字段都建立了索引，查询时只会选择其中最selective的来用，然后另一个条件是在遍历行的过程中在内存中计算之后过滤掉。那如何联合使用两个索引呢？两种办法：

l  使用skip list数据结构，同时遍历gender和age的posting list，互相skip；

l  使用bitset数据结构，对gender和age两个filter分别求出 bitset，对两个bitset做AND操作。

PostgreSQL从8.4版本开始支持通过bitmap联合使用两个索引，就是利用bitset数据结构来做的。一些商业的关系型数据库也支持类似联合索引的功能。

ES支持以上两种的联合索引方式，如果查询的filter缓存到了内存中(以bitset形式），那么合并就是两个bitset的AND。如果查询的filter没有缓存，那么就用skip list的方式去遍历两个on disk的posting list。

1)  利用Skip List合并

即使对于排过序的链表，查找还是需要进行通过链表的指针进行遍历，时间复杂度很高依然是O(n)，这个显然不能接受。是否可以像数组那样，通过二分法查找，但由于在内存中的存储的不确定性，不能这么做。但可结合二分法思想，跳表就是链表与二分法的结合。跳表是有序链表。

l  链表从头节点到尾节点都是有序的

l  可以进行跳跃查找(形如二分法），降低时间复杂度

说明：在上图中如要找node6节点

1)   第一次比较headerNode->next[2]的值，即node5的值。显然node5小于node6，所以，下一次应从第2级的node5开始查询，令targetNode=targetNode->next[2];

2)   第二次应该比较node5->next[2]的值，即tailNode的值。tailNode的值是最大的，所以结果是大于，下一次应从第1级的node5开始查询。这里从第2级跳到第1级。但没有改变targetNode。

3)   第三次应该比较node5->next[1]的值，即node7的值。因node7大于node6，所以，下一次应该从第0级的node5开始查询。这里从第1级跳到第0级。也没有改变targetNode。

4)   第四次应该比较node5->next[0]的值，即node6的值。这时相等，结束。如果小于，targetNode往后移，改变targetNode=targetNode->next[0]，如果大于，则没找到，结束。因为这已经是第0级，没法再降了。

考虑到频繁出现的term，如gender里的男或女。如有1百万个文档，那性别为男的posting list里就会有50万个int值。用FOR编码进行压缩可极大减少磁盘占用,对于减少索引尺寸有非常重要的意义。当然MySql B-树里也有类似的posting list，是未经这样压缩的。因为FOR的编码有解压缩成本,利用skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的block的过程，从而节省了CPU。

Frame Of Reference

以下三个步骤组成了Frame Of Reference(FOR)压缩编码技术

Step 1：增量编码

Step 2：分割成块

Lucene每个块是256个文档ID，每个块增量编码后每个元素都不会超过256(1 byte).为方便演示，图中假设每个块是3个文档ID。

Step 3：按需分配空间

对于第一个块 [73, 227, 2]，最大元素是227，需要 8 bits，那给这个块的每个元素，都分配8 bits的空间。但对于第二个块[30,11,29]，最大才30，只需5bits，那给每个元素只分配5bits空间。这一步可说是精打细算，按需分配。

2)  利用bitset合并

Bitset是一种很直观的数据结构，posting list如:[1,3,4,7,10]对应的bitset就是:[1,0,1,1,0,0,1,0,0,1], 每个文档按照文档id排序对应其中的一个bit。Bitset自身就有压缩的特点，其用一个byte就可以代表8个文档。所以100万个文档只需要12.5万个byte。但考虑到文档可能有数十亿之多，在内存里保存bitset仍然是很奢侈的事情。且对于每一个filter都要消耗一个bitset，比如age=18缓存起来的话是一个bitset，18<=age<25是另外一个filter,缓存起来也要一个bitset。所以需要一个数据结构：

l  可以压缩地保存上亿个bit代表对应的文档是否匹配filter；

l  压缩的bitset仍然可以很快地进行AND和OR的逻辑操作。

Roaring Bitmap

Lucene使用这个数据结构，其压缩思路其实很简单,与其保存100个0，占用100个bit，还不如保存0一次，然后声明这个0重复了100遍。

bitmap不管有多少文档，占用的空间都一样。譬如一个数组里面只有两个文档ID：[0, 65535]，表示[1,0,0,0,….(很多个0),…,0,0,1]，需要65536个bit，也就是65536/8=8192 bytes。而用Integer数组只需2*2bytes=4 bytes。可见在文档数量不多时使用Integer数组更节省内存。算一下临界值，无论文档数量多少，bitmap都需要8192bytes，而Integer数组则和文档数量成线性相关，每个文档ID占2bytes，所以8192/2=4096，当文档数量少于4096时用Integer数组，否则用bitmap.

4.  存储文档的减少方式

一种常见的压缩存储时间序列的方式是把多个数据点合并成一行。Opentsdb支持海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫compaction。类似的vivdcortext使用MySql存储的时候，也把一分钟的很多数据点合并存储到MySql的一行以减少行数。

ES可实现类似优化，那就是Nested Document。可把一段时间的很多个数据点打包存储到一个父文档里，变成其嵌套的子文档。这样可把数据点公共的维度字段上移到父文档里，而不用在每个子文档里重复存储，从而减少索引的尺寸。

存储时，无论父文档还是子文档，对于Lucene来说都是文档，都会有文档Id。但对于嵌套文档来说，可以保存起子文档和父文档的文档id是连续的，且父文档总是最后一个。有这样一个排序性作为保障，那么有一个所有父文档的posting list就可跟踪所有的父子关系。也可以很容易地在父子文档id之间做转换。把父子关系也理解为一个filter，那么查询检索的时候不过是又AND了另外一个filter而已。

使用了嵌套文档之后，对于term的posting list只需要保存父文档的docid就可，可以比保存所有的数据点的doc id要少很多。如可在一个父文档里塞入50个嵌套文档，那posting list可变成之前的1/50。

… … …

六．对象与块存储

本章节描述，以Ceph 分布式存储系统为参考。

1.  对象存储结构

在文件系统一级提供服务，只是优化了目前的文件系统，采用扁平化方式，弃用了目录树结构，便于共享，高速访问。

对象存储体系结构定义了一个新的、更加智能化的磁盘接口OSD。OSD是与网络连接的设备，包含存储介质，如磁盘或磁带，并具有足够智能可管理本地存储的数据。计算结点直接与OSD通信，访问它存储的数据，不需要文件服务器的介入。对象存储结构提供的性能是目前其它存储结构难以达到的，如ActiveScale对象存储文件系统的带宽可以达到10GB/s。

对象存储的结构包括元数据服务器（控制节点MDS）和数据存储服务器（OSD），两者进行数据的存储，还需客服端进行存储的服务访问和使用。

2.  块设备存储

块存储技术的构成基础是最下层的硬件存储设备，可能是机械硬盘也可能是固态硬盘。一个操作系统下可以独立控制多个硬件存储设备，但这些硬件存储设备的工作相对独立，通过操作系统命令看到的也是几个独立的设备文件。通过阵列控制层的设备可以在同一个操作系统下协同控制多个存储设备，让后者在操作系统层被视为同一个存储设备。

典型设备：磁盘阵列，硬盘，虚拟硬盘，这种接口通常以QEMU Driver或者Kernel Module的方式存在，接口需要实现Linux的Block Device的接口或者QEMU提供的Block Driver接口，如Sheepdog，AWS的EBS，阿里云的盘古系统，还有Ceph的RBD（RBD是Ceph面向块存储的接口）。

·       可通过Raid与LVM等手段对数据提供了保护;

·       多块廉价的硬盘组合起来，提高容量;

·       多块磁盘组合出来的逻辑盘，提升读写效率。

Ceph的RBD(RADOS Block Device)使用方式：先创建一个块设备，然后映射块设备到服务器，挂载后即可使用。

七．矩阵的存储结构

说明：本章节以矩阵存储为重心，而非矩阵的运算。

矩阵具有元素数目固定以及元素按下标关系有序排列等特点，所以在使用高级语言编程时，一般是用二维数组来存储矩阵。数据库表数据是行列存储，可视为矩阵的应用形式。矩阵的存储包括完全存储和稀疏存储方式。

1.  常规&特殊矩阵形态

常规矩阵形态

采用二维数组来存储，可按行优先或列优先的形式记录。

特殊矩阵形态

特殊矩阵指的是具有许多相同元素或零元素，并且这些元素的分布有一定规律性的矩阵。这种矩阵如果还使用常规方式来存储，就会产生大量的空间浪费，为了节省存储空间，可以对这类矩阵采用压缩存储，压缩存储的方式是把那些呈现规律性分布的相同元素只分配一个存储空间，对零元素不分配存储空间。 

1)  对称矩阵

对于矩阵中的任何一个元素都有aij=aji  1≤i,j≤n这样的矩阵就叫对称矩阵。也就是上三角等于下三角。对于对称矩阵的存储方式是存储上三角或者下三角加对角线，假设一个n阶对称方阵，如果全部存储使用的存储空间是n*n，压缩存储则是n(n+1)/2，对角线元素为n个，除了对角线之外为n*n-n，需要存储的元素(n*n-n)/2，加上对角线上的元素后结果就是n(n+1)/2。假设存储一个n阶对称矩阵，使用sa[n(n+1)/2]来存储，那么sa[k]与ai,j的关系是：

当i>=j时，k= i(i-1)/2+j-1

当i<j 时，k =j(j-1)/2+i-1

2)  三角矩阵

上三角或下三角全为相同元素的矩阵。可用类似于对称矩阵的方式存储，再加上一个位置用来存储上三角或者下三角元素就好。

a[i][j]=a[0][0] + (i* (i+1) /2+j) *size;

size为每个数据所占用的存储单元大小。

3)  带状对角矩阵

矩阵中所有非0元素集中在主对角线为中心的区域中。下图为3条对角线区域，其他区域的元素都为0。除了第一行和最后一行仅2个非零元素，其余行都是3个非零元素，所以所需的一维空间大小为：3n - 2；

a[i][j]的内存地址=a00首地址+ ((3 * i -1) + (j-i+1)) * size；(size为每个数据所占用的存储单元大小)。比如首地址为1000，每个数据占用2个存储单元，那么a45在内存中的地址=1000+13 * 2=1026；

2.  稀疏矩阵及压缩

由于特殊矩阵中非零元素的分布是有规律的，所以总是可以找到矩阵元素与一维数组下标的对应关系，但还有一种矩阵，矩阵中大多数元素都为0，一般情况下非零元素个数只占矩阵元素总数的5%以下，且元素的分布无规律，这样的矩阵称为稀疏矩阵。

三元组顺序法

如果采用常规方法存储稀疏矩阵，会相当浪费存储空间，因此只存储非零元素。除了存储非零元素的值之外，还需要同时存储非零元素的行、列位置，也就是三元组(i,j,aij)。矩阵元素的存储顺序并没有改变，也是按列的顺序进行存储。

è  

三元组也就是一个矩阵，一个二维数组，每一行三个列，分别为行号、列号、元素值。由于三元组在稀疏矩阵与内存地址间扮演了一个中间人的角色，所以稀疏矩阵进行压缩存储后，便失去了随机存取的特性。

行逻辑链接的顺序表

为了随机访问任意一行的非零元，这种方式需要一个数组指向每一行开始元素(非零元素)的位置。这种方式适合矩阵相乘。

十字链表法

当矩阵中元素非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。如在进行加减操作时，会出现非零元变成零元的情况，因此，就适合用十字链表来存储。

十字链表的结构有五个域，一个数据域存放矩阵元，i、j 域分别存放该非零元所在的行、列。还有right、down域，right指向右边第一个矩阵元的位置，down用来指向下面第一个矩阵元的位置。然后建立两个数组，分别指向每行/列的第一个元素。十字链表在图中也有应用，用来存储图。

八．图结构存储

图通常用来表示和存储具有“多对多”关系的数据，是数据结构中非常重要的一种结构。

1.  邻接矩阵结构

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

无向图

1）基于邻接矩阵容易判断任意两顶点是否有边无边；

2）某个顶点的度就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素和；

3）vi的所有邻接点就是矩阵中第i行元素，如arc[i][j]为1就是邻接点；

n个顶点和e条边的无向网图的创建，时间复杂度为O(n + n2 + e)，其中对邻接矩阵的初始化耗费了O(n2)的时间。

有向图

有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。

若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。

下面左图是一个有向网图，右图是其邻接矩阵。

2.  邻接表结构

邻接矩阵是不错的一种图存储结构，但对边数相对顶点较少的图存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。邻接表的处理方法：

1）图中顶点用一个一维数组存储，当然，顶点也可用单链表来存储，不过数组较容易的读取顶点的信息。

2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

例如，下图就是一个无向图的邻接表的结构。

从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如下图所示。

对于无向图，一条边对应都是两个顶点，所以在循环中，一次就针对i和j分布进行插入。本算法的时间复杂度，对于n个顶点e条边来说，容易得出是O(n+e)。

3.  十字链表存储

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。而十字链表存储方法可把邻接表和逆邻接表结合。

重新定义顶点表结点结构，如下所示

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

重新定义边表结构，如下所示

其中tailvex是指弧起点在顶点表的下表，headvex是指弧终点在顶点表的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。还可增加一个weight域来存储权值。

比如下图，顶点依然是存入一个一维数组，实线箭头指针的图示完全与邻接表相同。就以顶点v0来说，firstout指向的是出边表中的第一个结点v3。所以v0边表结点hearvex=3，而tailvex其实就是当前顶点v0的下标0，由于v0只有一个出边顶点，所有headlink和taillink都是空的。

虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此它的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。

十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而较易求得顶点的出度和入度。除了结构复杂一点外，其实创建图算法的时间复杂度和邻接表相同，因此在有向图应用中，十字链表是非常好的数据结构模型。

九．分布式图存储

分布式图(巨型图)的存储总体上有边分割和点分割两种方式，目前业界广泛接受并使用的存储方式为点分割，点分割在处理性能上要高于边分割。

l  边分割（Edge-Cut）：每个顶点都存储一次，但有的边会被打断分到两台机器上。这样做的好处是节省存储空间；坏处是对图进行基于边的计算时，对于一条两个顶点被分到不同机器上的边来说，要跨机器通信传输数据，内网通信流量大。

l  点分割（Vertex-Cut）：每条边只存储一次，都只会出现在一台机器上。邻居多的点会被复制到多台机器上，增加了存储开销，同时会引发数据同步问题。好处是可以大幅减少内网通信量。

虽然两种方法互有利弊，但现在是点分割占上风，各种分布式图计算框架都将自己底层的存储形式变成了点分割。主要原因有以下两个。

1)   磁盘价格下降，存储空间不再是问题，而内网通信资源无突破性进展，集群计算时内网带宽是宝贵的，时间比磁盘更珍贵。这点类似于常见的空间换时间的策略。

2)   在当前应用场景中，绝大多数网络都是“无尺度网络”，遵循幂律分布，不同点的邻居数量相差非常悬殊。而边分割会使那些多邻居的点所相连的边大多数被分到不同的机器上，这样的数据分布会使得内网带宽更加捉襟见肘，于是边分割存储方式被渐渐抛弃。

1.  GraphX存储模式

借鉴PowerGraph,使用点分割方式存储图,用三个RDD(Resilient Distributed Dataset,弹性分布式数据集)存储图数据信息：

VertexTable(id, data): id为Vertex id，data为Edge data

EdgeTable(pid, src, dst, data):pid为PartionId，src为原顶点id，dst为目的顶点id

RoutingTable(id, pid)：id为Vertex id，pid为Partion id

点分割存储实现如下图所示：

2.  超大规模图存储

超大规模图（数十亿点，数百亿边）存储，需要分布式的存储架构。在图加载时，整张图在图处理引擎内部被切分为多个子图，每个计算节点被分配1个或几个子图进行加载。

一张有向图的基本元素是顶点和边,一般都具有类型和权重，边是有向的，一条边由：起点、终点、类型三者标识，即相同的两点之间可以同时具有多条不同类型的边。下面是一个简单的带权异构属性图示例：

顶点以uint64标识，顶点类型、边类型，以及点边上的三种属性均采用字符串描述。对于例子中的图，需要将点边归类编号，得到一张可以识别的图。

图数据JSON格式

JSON文件由两大部分组成，点和边，分别存储在JSON对象的“nodes”、“edges”中。每个节点对象包含了节点的id，type，weight以及name，type和value属性信息字段。每个边对象则包含这个边相关联的起点和终点id：src和dst，和边相关的属性信息。

点和边属性索引

·     全局hash索引：全局采样过滤精确匹配某种属性的点和边。适用于全局采样负例的时候，加上过滤条件，只采样满足条件的负例。支持的查询有：eq，not_eq，in，not_in。

·     全局range索引：全局采样过滤某种属性在某个范围内的点和边。适用于全局采样负例时，加上过滤条件采样满足条件的负例。支持：eq，not_eq，ge，le，gt，lt，in，not_in

·     邻居索引： 采样某个点的满足某种属性的邻居节点。适用于邻居采样的时候，加上过滤条件，只采样满足条件的邻居节点。支持的查询与全局range索引相同。

图数据二进制生成

将JSON文件转化为分布式图引擎加载所需要的二进制格式，包括分片个数等。

… 广告搜索场景：图嵌入，向量化最近邻检索网络结构

… …

最 后

当今的计算机以运算器为中心，I/O设备与存储器间的数据传送都要经过运算器。相对处理器的速度来说，IO设备就慢多了。就SSD来说，IO也是远低于RAM的读写速率。IO读写的耗时常常成为性能的瓶颈点，所以要减少IO次数，且随着数据量增加，IO次数稳定是数据存储引擎的核心要务。当然了，CPU等指标也是很重要的。

文中倒排索引存储章节介绍了Lucene如何实现倒排索引的关键技术，如何精打细算每一块内存、磁盘空间、如何用诡谲的位运算加快处理速度，但往高处思考，再类比一下MySql就会发现，虽然都是索引，但实现机制却截然不同。

很多业务、技术上要解决的问题，大都可以抽象为一道算法题，复杂问题简单化。每种数据存储引擎都有自己要解决的问题（或者说擅长的领域），对应的就有自己的数据结构，而不同的使用场景和数据结构，需要引入不同的索引，才能起到最大化加快查询、检索的目的。

… ……