2.1.1　图计算的基础概念

了解图计算的基础概念之前，需要先了解图论的基础概念，第1章介绍过欧拉于18世纪上半叶（1736年）开创了图论。图论研究的对象就是图——若干顶点及连接顶点的边所构成的空间拓扑结构（图形），这种图形用来描述事物（顶点）之间的某种关系（边）。显然，我们所说的图形就是网络，而图计算的本质就是面向复杂网络的计算，或者是面向关联数据与关联关系的计算。

很多我们日常生活中接触的数据类型在本质上都是图论的研究对象，如集合、树、列表、堆栈、队列、数组或向量。

细心的读者一定会问：数组是离散的数据，为什么也会是图论的研究对象？因为虽然图论研究的是复杂网络，但是在极端的情况下，网络中只存在一组顶点而没有边，这些离散的点就是一组数组。同样的逻辑，基于表结构的关系型数据库可以看作一种二维数据库，而图数据库本质上是一种高维的数据库，高维可以向下兼容低维，反之则非常困难。

图计算中最关注的有如下几点：

·基础的计算与查询模式；

·常见的数据结构；

·关于计算效率的讨论。

1.查询模式

我们先来看看图计算中有哪些基础的查询模式，从不同角度看有不同的分类方式。

1）从关联还是离散的角度看，可以分为离散查询（discreted query）和关联查询（connected query）。

最典型的离散查询是面向元数据的查询，在图计算、图数据库的语境下，元数据（meta-data）指顶点或边，这两者是最小颗粒度的数据，通常用唯一的ID来标识，不需要再作细分。所有仅面向顶点或边的操作，都是典型的离散类型操作。

有的读者对边是否算作元数据表示困惑，认为边并非独立存在，它因为关联顶点而看起来像是一个复合数据结构。需要指出的是，元数据的定义一方面是最小颗粒度、不可再分，另一方面是有唯一匹配的ID来定位它。而在图数据库中，只有顶点和边符合这两点。但是，边的表达的确更为复杂，因为边上面除了ID外，还会关联起点与终点、方向以及其他属性。有一些图计算系统中会对边进行切割，也就是说关联一条边的两个顶点可能会被切分存储在不同的分片中，但是这种切边设计的系统比较少见，且计算效率很低（相比于切点而言的分片逻辑）。

关联查询是图数据库相比于其他数据库而言最有特色的图计算操作。例如，路径查询、K邻查询、子图查询、组网查询、各类图算法等都属于典型的关联查询。关联查询通常是从某个顶点（或多个顶点）出发，通过对边、点以及它们各自的属性进行过滤，来返回相关联的数据集。从关系型数据库的视角看，这种关联查询类似于表连接的操作，然而，图计算所能带来的灵活性与高性能是关系型数据库无法比拟的。

2）从图上的查询（遍历操作）方式来看，可以分为广度优先（BFS）和深度优先（DFS）。

广度优先的遍历最为典型的是K邻（K-Hop）和最短路径查询。以K邻为例，它的原始定义是，从某个顶点出发，查找和该顶点最短路径距离为K跳（步、层）的所有不重复的顶点集合。K邻计算的逻辑是如果想知道某个顶点第K层的全部邻居，需要先知道它的全部K-1层邻居，依此类推。换个角度描述为：从该顶点出发，先要找到它的第一层的全部邻居，再到第二层，直到找到第K层所有的邻居为止。

K邻操作在数据量巨大且高度联通的数据集上的计算复杂度可能非常大，因为从任何一个节点出发，只要K值够大，就可以联通到所有的节点上去。在金融场景中，以信用卡交易数据的图计算为例，所有的信用卡和它们的交易对手POS机之间形成的交易网络几乎是完全联通的（这个假设的前提是，每一张卡只要消费，就会至少和某个POS机关联，而这个POS机还会与其他卡交易，其他卡还会与更多的POS机关联，这样的网络是高度联通的，甚至是不存在孤点的。在实际操作中，孤点可能会被直接剔除，因为它们对于关联查询是没有意义的），见图2-1。

图2-2演示了2种不同类型的K邻操作：

·仅返回第K跳邻居；

·返回从第1跳到第K跳的全部邻居。

其中第K跳邻居指的是距离原点最短路径为K的全部邻居数量。以上两种操作的区别仅仅在于到底第K跳邻居是只包含当前层的邻居，还是包含前面所有层的邻居。

例如K=3时，仅返回第3层邻居，但当K是一个范围值[1,3]时，该操作的返回值显然大于前者，因为它还额外包含了K=1和K=2情况下的最短路径邻居的数量。

如果把K=[1,2]和K=3的K邻返回数值相加，总和应等于K=[1,3]的K邻值。这也是通过K邻计算来验证一个图数据库或图计算系统准确性的一种典型手段。笔者注意到，由于图计算的复杂性而造成的系统性的图计算准确性问题是普遍存在的，例如第K-1层的顶点重复出现在第K层，或者第K层中出现同一个顶点多次，这都属于典型的图计算的广度优先遍历算法实现存在Bug的情况。

图2-3展示的是典型的BFS与DFS在遍历一张有向图时经过节点的顺序差异。

深度优先算法常见于按照某种特定的过滤规则从图中某个顶点出发寻找另一个或多个顶点之间的联通路径。例如，在银行的交易网络数据中，寻找两个账户之间全部单一方向的按时序降序或升序排列的转账路径。

理论上，广度优先和深度优先算法都可以完成同样的查询需求，区别在于算法的综合复杂度与效率，以及对计算资源的消耗。另外，图2-3中的遍历算法是典型的单线程遍历逻辑，在多线程并发遍历的情况下，每个顶点被遍历时的途径顺序会产生变化，这在后面的章节中再详细剖析。

2.数据结构与计算效率

可以用来进行图计算的数据结构有很多种，前面已经提到过一部分，这里将梳理得更为清晰。我们通常把数据结构分为原始数据结构和非原始数据结构，如图2-4所示。

原始数据结构是构造用户定义数据结构的基础，在不同的编程语言中对原始数据结构的定义各不相同，例如，短整型（short）、整数（int）、无符号整数（unsigned int）、浮点数（float、double）、指针（pointer）、字符（char）、字符串（string）、布尔类型（boolean）等，这里不再赘述，有兴趣的读者可以查询相关的工具书和资料，本书关注更多的是用户系统（图计算框架或图数据库）定义的线性（linear）或非线性（nonliniear）数据结构。

在不考虑效率的前提下，几乎任何原始数据结构都可以被用来组合和完成任何计算，然而它们之间的效率差距是指数级的。如图2-4所示，图数据结构被认为是一种复合型、非线性、高维的数据结构，用来构造图数据结构的原始或非原始数据结构有很多种，例如常见的数组（array）、栈（stack）、队列（queue）、链表（linked list）、向量（vector）、矩阵（matrix）、哈希表（hash table）、Map、HashMap、树（tree）、图（graph）等。

在具体的图计算场景中，到底使用哪些数据结构需要具体分析，主要考虑以下两个维度：

·效率及算法复杂度；

·读写需求差异。

以上两个维度经常是交织在一起的，例如只读的条件下意味着数据是静态的，那么显而易见连续的内存存储可以实现更高效的数据吞吐及处理效率；如果数据是动态的，数据结构就需要支持增删改查操作，那么就需要更复杂的存储逻辑，也意味着计算效率就会降低，我们通常说的用空间换时间就是这种情况。这里再次重申，在不同的上下文中，图计算的涵义可能大相径庭，图数据库的图计算引擎组件毫无疑问需要支持动态、不断变化的数据；学术界实现的图计算框架则大多只考虑静态数据。这两种图计算所适用的场景和各自能完成的工作差异巨大，本书所涉及的内容属于前者——图数据库，对于后者，有兴趣深入了解的读者可以参考GAP Benchmark及其他图计算实现。

很多现实世界中的应用场景都用图数据结构来表达，尤其是这些应用可以被表达为网络化的模式时，如交通道路网络、电话交换网络、电网、社交网络、金融交易网络。业界范围内很多赫赫有名的公司（例如谷歌、脸书、高盛、黑石）都是基于图技术而构建的。

图2-5展示了一个典型的社交图网络的局部。它实际上是在一张大图上进行的实时路径查询所生成的一张子图。A节点为初始顶点，B节点为终止顶点，两者有15层间隔，并有100条关联路径，每条路径上有不同类型的边连接着两两相邻的顶点，其中不同类型（属性）的边以不同的色彩来渲染，以表达不同类型的社交关系（帮助、喜欢、爱情、合作、竞争等）。

图的数据结构大体包含以下3种类型的数据：

1）顶点，也被称作点、节点。顶点可以有多个属性，下面的边也一样，有鉴于此，某个类型顶点的集合可以看作传统数据库中的一张表，而顶点间基于路径或属性的关联操作则可看作传统关系型数据库中的表连接操作，区别在于图上的连接操作效率指数级高于传统数据库。

2）边，也被称作关系。一般情况下，一条边会连接2个顶点，2个顶点的排列顺序可以表明边的方向，而无向边通常通过双向边来表达，所以A-B=A←→B=A→B+B→A。而那种特殊类型的关联多个（≥3）顶点的边，一般都被拆解为两两顶点相连的多条边来表达。

3）路径，表达的是一组相连的顶点与边的组合，多条路径可以构成一张网络，也称作子图，多张子图的全集合则构成了一张完整的图数据集，我们称之为“全图”。很显然，点和边两大基础数据类型的排列、组合就可以表达图上的全部数据模型。

在图中，数据类型的表达如下。

·顶点：u、v、w、a、b、c……

·边：(u,v)……

·路径：(u,v)、(v,w)、(w,a)、(a,b)……

注意，边的表达形式(u,v)通常代表有向边，也就是说边是存在方向的，即括号中的u和v指代不同的涵义，方向是从u指向v，我们也称u为out-node（出点），v为in-node（入点）。如果是无向图，则括号中的出点、入点顺序并不重要。在实际的数据结构设计中，也可以使用额外的字段来表明边的方向，例如(u,v，1)和(v,u，-1)表达了u→v这条边的正向与反向边，即从u出发到v是正向边，而从v到u存在一条反向边。之所以要表达反向边是因为如果不存在从v到u的边，那么在图上（路径）查询或遍历的时候，将不会找到从v出发可以直接到达u的任何边，也就意味着图的连通度受到了破坏，或者说数据结构的设计和表达没有100%反映出真实的顶点间的路网连接情况。

传统意义上，用来表达图的数据结构有3类：相邻链表（adjacency list）、相邻矩阵（adjacency matrix）、关联矩阵（incidence matrix）。

相邻链表以链表为基础数据结构来表达图数据的关联关系，如图2-6所示，左侧的有向图（注意带权重的边）用右侧的相邻链表表达，它包含了第一层的“数组或向量”，其中每个元素对应图中的一个顶点，第二层的数据结构则是每个顶点的出边所直接关联的顶点构成的链表。

注意，图2-6中右侧的相邻链表中只表达了有向图中的单向边，如果从顶点4出发，只能抵达顶点5，却无从知道顶点3可以抵达顶点4，除非用全图遍历的方式搜索，但那样的话效率会相当低下。当然，解决这一问题的另一种方式是在链表中也插入反向边和顶点，类似于上面提及的用额外的字段来表达边的方向，进而来表达反向边。

相邻矩阵是一个二维的矩阵，我们可以用一个二维数组的数据结构来表达，其中每个元素都代表了图中两个顶点之间存在一条边。有向图用相邻矩阵AM来表达，如表2-1所示，每条边需要用矩阵中的一个元素来对应行、列中的一个顶点，矩阵是6×6的，并且其中只有7个元素（7条边）是被赋值的。很显然，这是一个相当稀疏的矩阵，占满率只有(7/36)<20%，它所需要的最小存储空间则为36B（假设每个字节可以表达其所对应的一条边的权重）。如果是一张有100万顶点的图，其所需的存储空间至少为100GB（1M×1MB），而在工业界中动辄亿万量级的图中，这还只是属于占比仅1%的小图。

也许读者会质疑以上相邻矩阵的存储空间估算被夸大了，那么我们来探讨一下。如果每个矩阵中的元素可以用1个比特位来表达，那么100万顶点的全图存储空间可以降低到12.5GB。然而，我们是假设用1B来表达边的权重，如果这个权重的数值范围超过256，我们或许需要2B、4B甚至8B，如果边还有其他多个属性，那么对于存储空间就会有更大的甚至不可想象的需求。现代GPU是以善于处理矩阵运算而闻名的，不过通常二维矩阵的大小被限定在小于32K（32768）个顶点。这是可以理解的，因为32K顶点矩阵的内存存储空间已经达到1GB以上了，而这已经占到了GPU内存的25%～50%。换句话说，GPU并不适合用于大图上面的运算，除非使用极其复杂的图上的Map-Reduce方式来对大图进行切割、分片来实现分而治之、串行的或并发的处理方式。但是这种处理方式的效率会很高吗？

关联矩阵是一种典型的逻辑矩阵，它可以把两种不同的图中的元数据类型顶点和边关联在一起。例如每一行的行首对应顶点，每一列的列首对应边。仍以上面的有向图为例，我们可以设计一个6×7=42元素的二维带权重的关联矩阵，如表2-2所示。

表2-2的二维矩阵仅能表达无向图或有向图中的单向图，如果要表达反向边或者属性，这种数据结构显然是有缺陷的。

事实上，工业界的图数据库极少用以上三种数据结构，原因如下：

·无法表达点、边的属性；

·无法高效利用存储空间（降低存储量）；

·无法进行高性能（低延迟）的计算；

·无法支持动态的增删改查；

·无法支持复杂查询的高并发。

综合以上几点原因，我们可以对上面提及的相邻链表数据结构进行改造，或许就可以更好地支持真实世界的图计算场景。下面结合计算效率来评估与设计图计算所需的数据结构。

存储低效性或许是相邻矩阵或关联矩阵等数据结构的最大缺点，尽管它有着O(1)的访问时间复杂度。例如通过数组下标定位任何一条边或顶点所需的时间是恒定的O(1)，相比而言，相邻链表对于存储空间的需求要小得多，在工业界中的应用也更为广泛。例如Facebook的社交图谱（其底层的技术架构代码为Tao/Dragon）采用的就是相邻链表的方式，链表中每个顶点表示一个人，而每个顶点下的链表表示这个人的朋友或关注者。

这种设计方式很容易被理解，但是它可能会遇到热点问题，例如如果一个顶点有1万个邻居，那么链表的长度有10000步，遍历这个链表的时间复杂度为O(10000)。在链表上的增删改查操作都是一样的复杂度，更准确地说，平均复杂度为O(5000)。另一个角度来看，链表的并发能力很糟糕，你无法对一个链表进行并发（写）操作。事实上，Facebook的架构中限定了一个用户的朋友不能超过6000人，微信中也有类似的朋友人数限制。

现在，让我们思考一个方法，一种数据结构可以平衡以下两件事情。

·存储空间：相对可控的、占用更小的存储空间来存放更大量的数据。

·访问速度：低访问延迟，并且对并发访问友好。

在存储维度，当面对稀疏的图或网络时，我们要尽量避免使用利用率低下的数据结构，因为大量的空数据占用了大量的空闲空间。以相邻矩阵为例，它只适合用于拓扑结构非常密集的图，例如全连通图（所谓全连通指的是图中任意两个顶点都直接关联）。前面提到的有向图，如果全部连通，则至少存在30条有向边（2×6×5/2)，若还存在自己指向自己的边，则存在36条边，那么用相邻矩阵表达的数据结构是节省存储空间的。

然而，在实际应用场景中，绝大多数的图都是非常稀疏的［我们用公式“图的密度=（边数/全联通图的边数）×100%”来衡量，大多数图的密度远低于5%］，因此相邻矩阵就显得很低效了。另一方面，真实世界的图大多是多边图，即每对顶点间可能存在多条边。例如交易网络中的多笔转账关系，这种多边图不适合采用矩阵数据结构来表达（或者说矩阵只适合作为第一层数据结构，它还需要指向其他外部数据结构来表达多边的问题）。

相邻链表在存储空间上是大幅节省的，然而链表数据结构存在访问延迟大、并发访问不友好等问题，因此突破点应该在于如何设计可以支持高并发、低延迟访问的数据结构。在这里，我们尝试设计并采用一种新的数据结构，它具有如下特点：

·访问图中任一顶点的时耗为O(1)；

·访问图中任意边的延迟为O(2)或O(1)。

以上时耗的复杂度假设可以通过某种哈希函数来实现，最简单的例如通过点或边的ID对应的数组下标来访问具体的点、边元素来实现。顶点定位的时间复杂度为O(1)；边仅需定位out-node和in-node，时耗为O(2)。在C++中，面向以上特点的数据结构最简单的实现方式是采用向量数组（array of vectors）来表达点和边：

---

Vector <pair<int,int>> a_of_v[n];

---

动态向量数组可以实现极低的访问延迟，且存储空间浪费很小，但并不能解决以下几个问题：

·并发访问支持；

·数据删除时的额外代价（例如存储空白空间回填等）。

在工业界中，典型的高性能哈希表的实现有谷歌的SparseHash库，它实现了一种叫作dense_hash_map的哈希表。在C++标准11中实现了unordered_map，它是一种锁链式的哈希表，通过牺牲一定的存储空间来得到快速寻址能力。但以上两种实现的问题是，它们都没有和底层的硬件（CPU内核）并发算力同步的扩张能力，换句话说是一种单线程哈希表实现，任何时刻只有单读或单写进程占据全部的表资源，这或许可以算作对底层资源的一种浪费。

在高性能云计算环境下，通过并发计算可以获得更高的系统吞吐率，这也意味着底层的数据结构是支持并发的，并且能利用多核CPU、每核多线程，并能利用多机协同，针对一个逻辑上的大数据集进行并发处理。传统的哈希实现几乎都是单线程、单任务的，意味着它们采用的是阻塞式设计，第二个线程或任务如果试图访问同一个资源池，它会被阻塞而等待，以至于无法（实时）完成任务。

从上面的单写单读向前进化，很自然的一个小目标是单写多读，我们称之为single-writer-multiple-reader的并发哈希，它允许多个读线程去访问同一个资源池里的关键区域。当然，这种设计只允许任何时刻最多存在一个写的线程。

在单写多读的设计实现中通常会使用一些技术手段，具体如下。

·versioning：版本号记录。

·RCU（Read-Copy-Update）：读-拷贝-更新。

·open-addressing：开放式寻址。

在Linux操作系统的内核中首先使用了RCU技术来支持多读，在MemC3/Cuckoo哈希实现中则使用了开放式寻址技术，如图2-7、图2-8所示。

沿着上面的思路继续向前迭代，我们当然希望可以实现多读多写的真正意义上的高并发数据结构。但是，这个愿景似乎与ACID（数据强一致性）的要求相违背——在商用场景中，多个任务或线程在同一时间对同一个数据进行写、读等操作可能造成数据不一致而导致混乱的问题。下面把以上的挑战和问题细化后逐一解决。

实现可扩展的高并发哈希数据结构需要克服上面提到的几个主要问题：

·无阻塞或无锁式设计；

·精细颗粒度的访问控制。

要突破并实现上面提到的两条，两者都和并发访问控制高度相关，有如下要点需要考量。

1）核心区域（访问控制）。

·大小：保持足够小。

·执行时间（占用时间）：保持足够短。

2）通用数据访问。

·避免不必要的访问。

·避免无意识的访问。

3）并发控制。

·精细颗粒度的锁实现：例如lock-striping（条纹锁）。

·推测式上锁机制：例如交易过程中的合并锁机制（transactional lock elision）。

对于一个高并发系统而言，它通常至少包含如下三套机制协同工作才能实现充分并发，此三者在图数据库、图计算与存储引擎系统的设计中更是缺一不可。

·并发的基础架构；

·并发的数据结构；

·并发的算法实现。

并发的基础架构包含硬件和软件的基础架构，例如英特尔中央处理器的TSX（Transactional Synchronization Extensions，交易同步扩展）功能是硬件级别的在英特尔64位架构上的交易型内存支持。在软件层面，应用程序可以把一段代码声明为一笔交易，而在这段代码执行期间的操作为原子操作。像TSX这样的功能可以实现平均140%的性能加速。这也是英特尔推出的相对于其他X86架构处理器的一种竞争优势。当然这种硬件功能对于代码而言不完全是透明的，它在一定程度上也增加了编程的复杂度和程序的跨平台迁移复杂度。此外，软件层面更多考量的是操作系统本身对于高并发的支持，通常我们认为Linux操作系统在内核到库级别对于并发的支持要好于Windows操作系统，尽管这个并不绝对，但很多底层软件实现（例如虚拟化、容器等）降低了上层应用程序对底层硬件的依赖。

另一方面，有了并发的数据结构，在代码编程层面，依然需要设计代码逻辑、算法逻辑来充分利用和释放并发的数据处理能力。特别是对于图数据集和图数据结构而言，并发对程序员来说是一种思路的转变，充分利用并发能力，在同样的硬件资源基础、同样的数据结构基础、同样的编程语言实现上，可能会获得成百上千倍的性能提升，永远不要忽视并发图计算的意义和价值。

图2-9展示了在Ultipa Graph上一款高性能、高并发实时图数据库服务器，通过高并发架构、数据结构以及算法实现了高性能K邻操作。

在商用场景中，图的大小通常在百万、千万、亿、十亿以上数量级，而学术界中用于发论文的图数据集经常在千、万的数量级，两者之间存在着由量变到质变的区别，特别对于算法复杂度和数据结构的并发驾驭能力而言，读者需要注意区分和甄别。以Dijkstra最短路径算法为例，它的原生算法完全是串行的，在小图中或许还可以通过对全图进行全量计算来实现，在大图上则完全不具有可行性。类似地，鲁汶社区识别算法的原生实现是利用了C++代码的串行方法，但是对于一张百万以上量级的点、边规模的图数据集，如果用串行的方法迭代5次，使得模块度达到0.0001后才停止迭代，可能需要数个小时或者T+1，甚至更长的时间（如T+2、T+7）。

图2-10展示的是在700万“点+边”规模且高度联通的一个图数据集上，通过高密度并发实现的鲁汶社区识别算法的效果，毫秒级完成鲁汶社区识别算法的全量数据的迭代运算（engine time）且1～2s内完成数据库回写以及磁盘结果文件回写等一系列复杂操作（total time）。

表2-3很好地示意了不同版本系统性能所出现的指数级差异，是两位图灵奖获得者大卫·帕特森（David Patterson）与约翰·轩尼诗（John Hennessey）于2018年在图灵会议的演讲中所展示的。

·以基于Python实现的系统的数据处理速度为基准；

·C/C++系统的处理速度为其47倍；

·并发实现的C/C++系统的处理速度为其366倍；

·增加了内存访问优化的、并发实现的C/C++系统，处理速度为其6727倍；

·利用了X86 CPU的AVX（高级矢量扩展）指令集的系统，处理速度为其62806倍。

回顾前面的鲁汶社区识别算法，如果提升6万倍的性能，时间从T+1（约10万s）变为约1.7s，就可以实现完全实时。这种指数级的性能提升与时耗的相应减少所带来的商业价值是不言而喻的。

图2-11形象地解析了如何在图中实现BFS算法并发。以基于BFS的K邻算法为例，为读者解读如何实现高并发。

①在图中定位起始顶点（图中的中心顶点A），计算其直接关联的具有唯一性的邻居数量。如果K=1，直接返回邻居数量；否则，执行下一步。

②K≥2，确定参与并发计算的资源量，并根据第一步中返回的邻居数量决定每个并发线程（任务）所需处理的任务量大小，进入第三步。

③每个任务进一步以分而治之的方式，计算当前面对的（被分配）顶点的邻居数量，以递归的方式前进，直到满足深度为K或者无新的邻居顶点可以被返回而退出，算法结束。

基于以上的算法描述，我们再来回顾一下图2-11中的实现效果，当K邻计算深度为1～2层的时候，内存计算引擎在微秒级内完成计算。从第3层开始，返回的邻居数量呈现指数级快速上涨（2-Hop邻居数量约200,3-Hop邻居数量约8000,4-Hop邻居数量接近5万）的趋势，这就意味着计算复杂度也等比上涨。但是，通过饱满的并发操作，系统的时延保持在了相对低的水平，并呈现了线性甚至亚线性的增长趋势（而不是指数级增长趋势），特别是在搜索深度为第6～17层的区间内，系统时延稳定在约200ms。第17层返回的邻居数量为0，由于此时全图（联通子图）已经遍历完毕，没有找到任何深度达到17层的顶点邻居，因此返回结果集合大小为0。

我们做一个1:1的对标，同样的数据集在同样的硬件配置的公有云服务器上用经典的图数据库Neo4j来做同样的K邻操作，效果如下：

·1-Hop：约200ms，为Ultipa的1/1000；

·从5-Hop开始，几乎无法实时返回（系统内存资源耗尽前未能返回结果）；

·K邻的结果默认情况下没有去重，有大量重复邻居顶点在结果集中；

·随着搜索深度的增加，返回时间和系统消耗呈现指数级（超线性）增长趋势；

·最大并发为400%（4线程并发），远低于Ultipa的6400%并发规模。

基于Neo4j的实验（图2-12），我们只进行到7-Hop后就不得不终止了，因为7跳的时候系统耗时超过10s，从8跳开始Neo4j几乎不可能返回结果。而最大的问题是计算结果并不正确，这种不正确包含两个维度：重复顶点未被去重、顶点深度计算错误。

K邻操作中返回的应该是最短路径条件下的邻居，那么如果在第一层的直接邻居中已经被返回的顶点，不可能也不应该出现在第二层或第三层或其他层级的邻居列表中。目前市场上的一些图数据库产品在K邻的实现中并没有完全遵循BFS的原则（或者是实现算法的代码逻辑存在错误），也没有实现去重，甚至没有办法返回（任意深度）全部的邻居。

在更大的数据集中，例如Twitter的15亿条边、6000万顶点、26GB大小的社交数据集中，K邻操作的挑战更大，我们已知的很多开源甚至商业化的图数据库都无法在其上完成深度（≥3）的K邻查询。

到这里，我们来总结一下图数据结构的演化：更高的吞吐率可以通过更高的并发来实现，而这可以贯穿数据的全生命周期，如数据导入和加载、数据转换、数据计算（无论是K邻、路径还是……）以及基于批处理的操作、图算法等。

另外，内存消耗也是一个不可忽略的存储要素。尽管业内不少有识之士指出内存就是新的硬盘，它的性能指数级高于固态硬盘或磁盘，但是，它并不是没有成本的，因此谨慎使用内存是必要的。减少内存消耗的策略有：基于数据加速的数据建模；数据压缩与数据去重；算法实现与代码编程中避免过多的数据膨胀、数据拷贝等。 79HOuFt4wjobCekEPJCHSHTk8l6N6f3/kCiEFBELrxGaCO1vQnqH3VlJ00y2BpxJ