图形数据库中的分布和划分

什么是分布式系统?

通常，一个分布式的计算机系统是一组计算机程序，它们在多个独立的服务器上协同工作，以实现一个共同的目标。那些服务器指的是那些商用服务器而不是大型机。这里用于跨服务器协作的硬件大多基于以太网设备或更高端的RMDA设备。

为什么我们需要一个分布式系统?

构建分布式系统的主要原因是用软件技术和廉价的硬件设备取代昂贵的硬件设备的成本。尤其是在大多数私有服务器机房，不公共云或者超算条件下，采购成本是商业决策的重要依据。

除了降低成本，分布式技术的另一个好处是它的可伸缩性。通过将几个服务器添加到原始数量的服务器上，然后结合分布式系统的调度和分发能力，新的服务器可以用于提供额外的服务。

与购买同等数量的更多服务器或购买更高配置的服务器相比，分布式技术允许您按需购买服务器，这降低了过度配置的风险，并提高了硬件资源的利用率。

分布式系统的基本问题

在分布式技术中，由于数据存储和计算需要在多个独立的服务器上实现，因此必须涉及一系列底层技术。在本文中，我们只讨论两个问题:一个是数据拷贝或副本问题，另一个是如何将大数据的存储和计算分布到独立的服务器上。

数据副本的问题

商用服务器的硬件可靠性和维护远低于大型机。因为大型机房几乎每小时都会发生网线松动、硬盘损坏、断电等情况。解决或避免这些硬件问题是分布式软件系统的一个基本问题。一种常见的解决方案是在多台服务器上复制数据。一旦一些数据副本丢失，系统仍然可以通过使用剩余的数据副本来提供服务。

更重要的是，当系统的访问负载过大时，系统还可以通过添加更多副本来提供更多服务。此外，还需要一些技术来保证数据副本之间的一致性;也就是说，不同服务器上的每个副本的数据是相同的。对于图形数据库数据复制问题也存在。解决这个问题的方法类似于解决关系数据库或大数据系统中数据副本问题的方法。

数据划分的问题

单个服务器的硬件、内存和CPU是有限的。如果数据太大，不可能将所有数据存储在一台服务器上。因此，TB级甚至PB级的数据必须分布到多个服务器上，我们称这个过程为数据分区。当请求访问多个数据分区时，分布式系统需要将请求分发到每个正确的数据分区，然后组合结果。

图数据库中的数据划分问题:图划分

在图形数据库，分布过程被形象地称为图划分。一个大图被分割成多个小图，每个小图的存储和计算都存储在不同的服务器上.

与关系数据库和大数据系统中的划分问题相比，图划分问题更值得特别关注。

我们来看一个静态的图结构，比如CiteSeer数据集，这是一个科学论文的引用网络，由3312篇论文以及它们之间的引用组成。它是一个小规模数据集，可以存储在一台服务器上。

Twitter 2010数据集是Twitter用户的社交网络，由1271万个顶点和2.3亿条边组成。在2022年生产的单个主流服务器上存储这个数据集相对容易。但是，要做到这一点，可能需要购买十年前生产的非常昂贵的高端服务器。

然而，WDC (Web Data Commons)数据集包含17亿个顶点和640亿条边。在当前的主流服务器上很难或者不可能存储如此大规模的数据集。

另一方面，由于人类的数据增长速度快于摩尔定律，并且数据之间的连接或关系的数量以指数形式高于数据产生的速度，因此数据划分问题似乎是图数据库系统不可避免的问题。但这听起来与主流分布式技术中数据的分区或散列方式没有什么不同。毕竟数据被分割成多个大数据系统。

等等，划分一个图有那么容易吗?

不，不是的。在图数据库领域，图划分问题是技术、产品和工程之间的权衡。

图划分面临的三个问题

第一个问题:应该分割什么?在大数据或关系数据库系统中，基于行的分区或基于列的分区是基于记录或字段执行的，或者是基于数据id执行的分区，这在语义和技术上是直观的。然而，图数据结构的强连通性使得对图数据进行划分变得困难。一个顶点可以通过多条边连接到许多其他顶点，并且其他顶点也可以通过它们的相邻边连接到许多其他顶点。这就像网页几乎是相互链接的一样。那么对于一个图数据库，应该划分什么才能使语义直观自然呢?(在RDBMS中，这相当于当表中有大量外键时，如何对数据进行分区。)当然，也存在一些自然的语义划分方法。例如，在新冠肺炎疫情下，各种毒株在中国和其他国家的传播链是两种不同的网络结构。

然后，引入第二个问题。

第二个问题:就是数据分区后如何保证每个分区的数据大致平衡。自然形成的图符合20%的少数顶点与其他80%的顶点相连的幂律，这些少数顶点称为超级节点或密集节点。这意味着少数顶点与大多数其他顶点相关联。因此，可以预期，包含超级节点的分区的负载和热点比包含其他顶点的其他分区的负载和热点高得多。

上图展示了互联网上网站超链接形成的联想网络的视觉效果，其中超级网站(节点)可见。

第三个问题:当原有的划分方法随着图网络的增长而逐渐过时，图的分布和连接模式发生变化时，如何评价和进行重新划分?下图显示了人脑中860亿个神经元之间连接的视觉效果。随着学习、锻炼、睡眠和衰老，神经元连接每周都在不断变化。原来的划分方式可能根本跟不上变化。

当然还有很多其他细节需要考虑。在本文中，我们尽量避免使用太多的技术术语。

不幸的是，从技术角度来看，没有解决图划分问题的灵丹妙药，每个产品都必须做出权衡。

这对于第三个问题，解决方案是使用细粒度的分区方法，以便可以执行某些分区的向外扩展。