图数据库 | 15、可扩展的图数据库设计（上）

和所有其他类型的数据库一样，可扩展的图数据库（Scalable Graph Database）是图数据库发展的必然阶段。

单机（单实例）所能承载的最大数据量、吞吐率、系统可用性显然是有限的，也正是这种限制，几乎所有的新型数据库系统都会把扩展能力，特别是通过多实例形成的水平集群扩展能力，作为一个重要的能力衡量指标。这也是分布式数据库方兴未艾的核心原因。

在探讨可扩展的图数据库设计时须明确一点，只有在垂直扩展没有可能的时候，才开始追求水平可扩展系统的构建与迭代。

换句话说，很多业务问题，无论是从数据量、吞吐量、性能还是其他要素来考虑，通过垂直扩展方式解决一定是复杂度最低、代价最小的。

事实上，水平可扩展系统的设计、实现及运维复杂度，远远超出绝大多数开发者的预期，而且很多情况下，系统的稳定性、时效性因真实世界的业务复杂性而变得不可预知，反而会形成一种颇具讽刺意味的效果：很多所谓的大规模水平分布式系统的实际应用效果往往差于预期，更弱于它们所取代的那些Monolithic（所谓的单机版）系统——最典型的基于秒杀类短链条交易场景而构建的分布式关系型数据库的性能、稳定性、用户总拥有成本、效率真的全面超越了它们所“取代”的Oracle数据库吗？

或许，我们在关注分布式图数据库架构设计的时候，可以更多地从真实的业务需求出发，避免让架构设计变成一种为了追求分布式而分布式的死循环。本篇内容先着重探讨垂直扩展的可能性，再探讨水平扩展的意义和优劣。

一、垂直扩展

传统意义上的垂直可扩展指的是在单节点（单实例）上，通过对存储、算力及网络三要素进行升级来获得更高的系统性能、吞吐率，以实现服务更多客户请求的业务目标。

在水平可扩展的概念被开发者与客户广泛接受前，垂直可扩展几乎是我们升级系统的唯一途径。一般认为水平可扩展肇始于AWS开始对外提供大规模云计算服务的2006年，在技术栈上则是源自Yahoo！向开源社区贡献的Apache Hadoop系统中的核心组件MapReduce+HDFS，让低成本的廉价PC通过大规模组网实现对海量数据的批处理，而Hadoop的核心理念则受到了2003—2004年谷歌的基于其内部闭源系统的两篇关于MR与GFS论文的启发，这是后话。随着水平可扩展架构及理念的广泛传播，很多人认为垂直可扩展系统已经一无是处了。然而，在计算机体系架构的不断发展过程中，垂直可扩展的方式依然有其顽强的生命力，如下图1所示：

很多人把垂直可扩展系统简单等同于对计算机系统及其周边关联设备的“硬件升级”​，即对如下的云计算三要素进行扩容：

·存储：硬盘、网盘、内存等。
·计算：CPU、GPU等。
·网络：网卡、网关、路由器等。

通过对硬件层面的存储、计算、网络资源升级，以及对主板、总线结构等的升级，的确可以获得更高的“算力”​，但这种硬件层面算力的提升仅停留在理论层面，它并不能等比例的、不言自明的，不通过任何“软件升级”让业务系统及应用程序获得更高的吞吐率、更低的延迟等。这一点是垂直可扩展系统经常忽略的问题，常被人们诟病。

不可否认，把5400r/min的磁盘升级为10 000r/min的确会获得近50%的数据吞吐能力提升，把CPU的主频从2GHz升级为3.2GHz也可以获得接近60%的计算效率提升。同样地，从100Mbit/s的网卡升级为1Gbit/s也会有至少5倍的带宽升级效果。然而，还有很多硬件能力指标是需要软件的升级改造来释放的。我们举3个例子来说明这个问题:

例1：从传统的企业级磁盘（HDD）升级为企业级固态硬盘（SSD）​。
例2：从8核CPU升级为2个40核CPU。
例3：从1Gbit/s网卡升级为带有Zero-copy RDMA功能的10Gbit/s网卡。

在例1中，从HDD升级为SSD，对于数据库级别的服务器端软件而言，最大的差异在于是否能充分释放SSD的能力优势。在之前的文章中介绍过，SSD相比HDD的性能优势在随机读写时是2个数量级（约100倍）​，在顺序连续读写时却只有几倍（如3～5倍）​，也就是说在不同的读写模式下，SSD和HDD之间的性能会有1～1.5个数量级的差距（例如，100倍与5倍的落差）​。对于数据库而言，最直接的差异会体现在如下两个场景：
第一类场景是数据连续写入或读取；
第二类场景是数据的随机读取或更新（删除、插入）​。

第一类场景最典型的是数据库批量加载数据或连续更新日志文件操作；第二类场景则几乎涉及所有的其他操作，特别是对于索引文件或数据库主存储文件的访问，其中前者以读为主，而后者，至少对于OLTP类型的图数据库而言，需要兼顾读与写操作的效率。

现在回到我们最初的问题，简单地从HDD升级为SSD是否就拥有了SSD所宣称能提供的所有性能吗？答案是，不一定。软件在很多时候是个制约因素，优化的软件架构才能更充分地释放底层硬件的能力。

老夫在存储引擎部分就介绍过WiscKey，通过对LSMT进行算法架构改造，有针对性地面向SSD的硬件特点做到了当KV键值尺寸大于等于4KB时的性能大幅提升。

这种改造可以视作一种典型的面向业务数据的性能优化，确切地说，在数据字段（值）的大小超过4KB之后的系统吞吐率较改造前有大幅提升——软件层面的优化更充分地释放了底层硬件的能力。

数据库查询优化器通常会对查询语句的内在逻辑进行优化，并通过执行它认为最优的路径来完成查询。基于HDD的硬件特性而设计的查询优化器可以不经过任何修改就在SSD上运行，但是，对于落盘在SSD上的数据文件、索引文件、缓存数据，以及数据库日志，通过有针对性地优化面向这些文件的访问路径，例如，降低I/O请求、合并多个操作、把随机读写优化为顺序读写等，可以让系统获得更高的数据吞吐率、更低的查询时耗。类似地，通过多级存储及缓存逻辑，可以用低成本的硬件来实现与高成本系统相近的性能产出。

例2中，从8核CPU升级为80核CPU，表面上看是10倍的计算资源增长，但是，如果没有数据库软件对于这些算力的释放，这个升级将不会带来任何变化。这也是很多人选择性忽略了垂直可扩展的真正意义——通过编写高并发的软件来充分利用多核CPU、多线程并发来实现更高的系统吞吐率。而高并发的效果实际上往往好于那些所谓的水平扩展系统的性能，因为水平分布式系统通常会伴随大量的网络通信，在其上所消耗的时间带来的系统时延上升、吞吐率下降，往往会抵消水平分布式带来的潜在多实例吞吐率上升的收益。

然而，高并发软件编写或改造的难度并不亚于水平分布式系统的构造难度，虽然两者在架构层面上的关注点差异决定了在具体实现过程中的难点不同，但它们的终极目标都是通过“并发、并行执行”来实现更高的系统吞吐率（更高的投入产出比，以及更好地满足客户的面向未来增长的架构设计与实现）​。笔者建议从这一刻开始，摒弃水平扩展与垂直扩展之争，把关注点放在如何实现并发软件上。高并发软件的设计与开发有3大“陷阱”​：

·缺少并发思维；
·锁（locks）与共享可变状态（shared mutable state）​；
·算法（与数据结构）选择。

对于大多数程序员（以及业务人员，甚至用户）而言，缺少并发思维让我们低估垂直扩展的收益，高估水平扩展的回报，也可能会让我们在设计并发系统架构时因为短视而无法考虑更长远的目标，进而导致系统架构需要反复推翻，最终无法实现既定设计目标。

同样，选择什么数据结构才能更好地适配并满足客户的业务需求（例如读写的比重分配、访问行为模式、最大负载情况及常见负载模式等）​？选择什么算法来对一份原本串行的工作拆分并进行并发执行改造呢？我们需要承认高效的算法可以带来指数级的效率提升，如同老夫在图算法中介绍过的典型图查询、图算法（例如全图度计算、全图K-Hop、含超级节点的K-Hop查询、鲁汶社区识别、三角形计算等）​，通过多核CPU、多线程充分并发，可以带来大幅的效率提升。而有一些图查询或算法甚至是“歧视”水平分布式系统的，例如，从某个节点出发的K-Hop查询，假设K=5，如果在一个完全水平分布式的图数据库系统中，无论是从一台实例出发，还是从多台实例出发，只要初始节点的多层邻居分布在整个集群内多个节点上，每向下一层实例访问就会因为实例数量的指数级（约10倍）增加带来对应的实例间通信的指数级增加，直至集群内通信成本完全抵消分布式带来的优势，导致无法完成查询操作。

锁（以及共享可变状态）的存在是为了保证多个并发任务（线程或进程）不会由于访问失控而导致数据库的数据不一致或不可预期。锁的存在意味着它的访问（以及它所保护的数据资源）只能以某种串行的方式进行，这也隐式地说明并发系统并不是完全并行的。事实上，任何分布式系统都一定会有一些环节、组件、进程是以串行的方式进行的。这或许才是所有分布式系统的底层真相，只不过在铺天盖地的分布式浪潮中，我们会选择性地忽略这些真相而已。

下图展示了完全串行的程序在经过部分并行改造后可以获得从50s缩减到40s的效果，因为其中2/5的程序被以2倍速并发执行，对整体而言是1.25倍速。如果全部环节都可以改造，则可以获得全程序2倍速的效率提升。如果可以以10倍速执行全部环节，则整体程序也将获得10倍速的效率提升。

在计算体系架构中，阿姆达尔定律（Amdahl's Law）描述了把程序从串行改造为并行过程中可以获得效率提升的数学模型。具体公式如下： 

假设一个程序完全串行需要50s可以完成，其中大部分（40s）可以改造为充分利用底层硬件的并发处理能力，有10s无法改造，则无论如何充分并发，该程序的最短执行时间无法低于10s。那么上面阿姆达尔公式中的p=40/50=0.8，如果并发可以从串行的1倍速改造为80倍速，则s=80，则Slatency=1/(0.2+0.8/80)=1/0.21=4.76，即非常接近理论上的5倍加速。

从串行改造为并行的挑战在于，当数据可能会被改动的时候，并发访问如果不加以控制就会出现差错。表5-1展示了在多线程读写条件下的问题复杂度。 

在例3中，网络从1Gbit/s升级为10Gbit/s，表面上获得了10倍的带宽提升，并且这个理论网速让人很容易有一种“错觉”​，就是网络的速率已经超越HDD了，甚至超越了SSD（一般的企业级SSD的顺序读写效率为500MB/s，随机读写则更低）​。这种错觉会让我们觉得分布式系统的瓶颈已经不复存在了，因为即便是多个节点实例间进行通信，有如此之快的网络，则完全不需要再担心网络延迟的问题了。但实际的情况是，特别是对于数据库系统，网络从来都不是系统瓶颈之所在。

为了更好地说明这个问题，我们举个例子：假设用10Gbit/s传输100万个小文件，每个文件约4KB，以及传输一个4GB的文件（在文件大小层面，4GB=4KB×100万）​，请问两者的传输时间差异是多少？

差异可能至少在100倍以上，甚至多达300倍。为什么会这样呢？因为我们大多数人会习惯性地忽略I/O的代价，传输1个大文件，假设10Gbit/s带宽的最大、有效利用率是80%，即8Gbit/s，那么4s就可以传输完成，但是传输100万个文件，则会有数百万次I/O，假设读取1个文件（block）只需要400μs（0.4ms）​，100万次读取也需要400s，也就是说，10Gbit/s的最大可能传输带宽根本不是瓶颈，即便是1Gbit/s对于这些小文件也绰绰有余了。

而实际上，在数据库系统中，多个实例间的信息同步问题类似于上面的百万量级小文件，这些小文件、小数据包往往只有几个字节到几百个字节，多实例之间的同步会产生大量的、频繁的I/O操作。我们甚至可以说：在分布式系统的设计中，能最低限度地使用网络同步是系统性能提升（降低延迟）的法宝。但是，规避网络同步似乎等同于去追求垂直扩展而非水平扩展；而垂直扩展的系统中同样也追求通过并发来实现增效、提速。 

那么，到底是垂直扩展还是水平扩展，这两者似乎更像薛定谔的猫。追求极致的并发才是更底层、更极致的挑战，才是我们需要关注的硬核问题。

在例3中，还有另外一个有趣的技术点——zero-copy RDMA（Remote Direct Memory Access，远程直接内存访问）​。图5-3右侧示意了RDMA技术，它让请求发起方的应用程序可以直接跨过多级缓存而直接通过支持RDMA的网卡向接受方实例的应用程序写入数据，在这个过程中，相比于传统的网络间数据交换模式，有如下几个优点：

·零复制（zero-copy）​；

·低CPU介入；

·无须操作系统内核介入；

·几乎无网络性能损耗；

·存储与计算融合。

但RDMA能发挥最大效用的前提是应用程序需要大幅改造。传统应用程序通常对硬盘I/O存在依赖，而改造后的应用（例如内存数据库）可更充分地利用RDMA的硬件加速能力。事实上，任何数据库都可以通过对内存的扩大利用和充分利用来获得更好的增速。对于图数据库而言，通过内存来提速的渠道有很多，枚举如下：
·索引常驻内存；
·部分数据常驻内存，例如元数据；
·中间数据内存存储；
·缓存数据常驻内存；
·日志常驻内存；
·以上多种类型数据的混搭常驻内存，或基于可定制策略的内存常驻逻辑；
·全部数据常驻内存。

关于内存，笔者认为有以下几点重要认知：

·内存会成为新的硬盘，大内存技术毫无疑问是未来10年内计算机体系架构升级换代技术栈中最重要的一环；
·升级内存来获得更高的系统性能往往是最简易、最低成本的方案；
·内存与外存以及网络可以构造一整套多级存储加速的架构，绝大多数现有数据库系统的改造和加速都没有充分考虑内存加速这一环。
在计算机体系架构中，从HDD、SSD到内存再到CPU缓存组件，如果再包含网络存储，至少有5级存储，任意相邻的两级之间存在指数级的性能落差，如下图所示。这种性能落差，无论是垂直扩展还是水平扩展都是客观存在的。真正能让我们获得性能提升的是高并发与低延迟的实现，或许这也是任何高性能系统的本质。图数据库系统的性能提升，无外乎通过如下几个手段来实现：
·更好的硬件；
·与硬件匹配的，可以支持最大并发、低延迟的系统架构，包括体系架构、数据结构、编程语言等；
·对图数据库中所有可能的操作进行并发优化、算法逻辑优化，以实现最低的延迟和最大的吞吐率。 

在高并发（或高并行）领域一直存在一个有趣的、无心的认知误区，高并发（high-concurrency）与高并行（high-parallelism）经常被混用，但是实际上它们代表不同的含义，如下图5所示，高并发其实是存在明显的单节点资源障碍的，即共享可变状态区，而高并行则不存在。但是，大家都已经把高并发等同于高并行了，本书也依照惯例不再加以区分。

在前面的内容中，我们多次阐述过对图数据库中的一些操作进行高并发实现可以获得指数级的性能提升，图5右上展示的就是一个在CPU层面串行执行40ms才能完成的工作，如果能充分利用32倍速并发，可以在1.25ms内完成，但是如果在内存层面，则需要4s,SSD层面需要超过1h,HDD层面需要超过1天……永远不要低估并发加速的效果，但这种效果在垂直扩展的系统上相对更容易获得，这和图数据库中复杂查询的特征有关——深度查询，例如多级（多步）路径查询、K邻查询、多层子图查询、复杂的图算法，它们的一个共有特征是节点之间通过大量的边关联，如果这些点、边不能整体地存储在同一个数据结构中，势必会出现海量的网络请求或大量因文件系统访问而出现的I/O，这些额外的请求与I/O是任何分布式系统的最大敌人。

一个垂直扩展就洋洋洒洒快6500多字，料实在太多了…… 明天老夫接着聊聊水平扩展怎么，88。

· END ·

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