由于多种原因，我们将使用Neo4j图形数据库说明本章中的讨论。 Neo4j是一个具有本机处理功能以及本机图存储的图数据库（有关本机图处理和存储的讨论，请参见第1章）。除了在撰写本文时成为最常用的图形数据库外，它还具有开源的透明性优势，这使冒险的读者可以更轻松地更深入地研究代码。最后，这是一个作者很了解的数据库。

1.本机图处理

在本书中，我们多次讨论了属性图模型。至此，您应该熟悉其通过命名和定向关系连接的节点的概念，其中节点和关系都充当属性的容器。尽管模型本身在图形数据库实现之间合理地一致，但是有许多方法可以在数据库引擎的主内存中编码和表示图形。在许多不同的引擎体系结构中，我们说图数据库如果具有称为无索引邻接的属性，则具有本机处理功能。

利用无索引邻接的数据库引擎是其中每个节点都维护对其相邻节点的直接引用的引擎。因此，每个节点都充当附近其他节点的微索引，这比使用全局索引便宜得多。这意味着查询时间与图形的总大小无关，而是与搜索的图形量成正比。

相反，非本机图数据库引擎使用（全局）索引将节点链接在一起，如图6-1所示。这些索引为每个遍历增加了一个间接层，从而导致更大的计算成本。支持本机图处理的人认为，无索引的邻接对于快速，有效地遍历图至关重要。

要了解为什么本机图处理比基于重索引的图更高效，请考虑以下内容：根据实现的不同，索引查找的算法复杂度可能为O(log n)，而查找直接关系的开销可能为O(1)。为了遍历m个步长的网络，索引方法的成本为O(m log n)，与使用无索引邻接的实现的O(m)成本相比显得微不足道。

图6-1显示了图处理的非本机方法如何工作。要查找爱丽丝的朋友，我们首先要执行索引查找，费用为O(log n)。对于偶尔或浅浅的查找，这可能是可以接受的，但是当我们反转遍历的方向时，它很快变得昂贵。如果我们不是要找到爱丽丝的朋友，而是要找出谁是爱丽丝的朋友，而必须执行多个索引查找，则对可能与爱丽丝成为朋友的每个节点执行一次索引查找。这使成本更加繁重。找出谁是爱丽丝的朋友是O(log n)成本，而找出谁是爱丽丝的朋友是O(m log n)。

无索引的邻接导致低成本的“加入”

使用无索引邻接，可以有效地预先计算双向联接并将其作为关系存储在数据库中。相反，当使用索引来模拟记录之间的连接时，数据库中没有实际存储的关系。由此产生两个问题：

首先，在算法上使用全局索引查找通常比遍历物理关系要昂贵得多。索引通常在时间上花费O(log(n))，而至少在Neo4j中,遍历关系在时间上是O(1) 。从理论上讲，即使n的值适中，对数成本也可能比恒定时间贵很多倍。在实践中，由于图形及其全局索引竞争诸如缓存和 I/O 之类的资源（例如，当索引和图形数据之间发生页面争用时），其性能甚至会更差。

其次，当我们尝试从构造索引的方向“相反(opposite)”的方向进行遍历时，使用索引来模拟连接变得很成问题。现在，我们面临着为每个遍历方案创建反向查找索引的选择，或者我们必须通过原始索引（这是O(n)操作）执行蛮力搜索。鉴于这种情况下的算法性能不佳，像这样的联接太昂贵了，以至于无法用于在线系统。

索引查找可用于小型网络（例如图6-1中的网络），但对于大型图的查询而言代价太高。具有本机图处理功能的图数据库不使用索引查找来履行查询时的关系角色，而是使用无索引的邻接关系来确保高性能遍历。图6-2显示了关系如何消除了对索引查找的需求。

回想一下，在通用图形数据库中，可以非常便宜地在任一方向（从头到尾，或从头到尾）遍历关系。如图6-2所示，要使用图表查找爱丽丝的朋友，我们只需遵循她的外向朋友关系，每个关系的成本为O(1) 。要查找谁是爱丽丝的朋友，我们只需跟踪所有爱丽丝传入的FRIEND关系到他们的来源，同样，每次花费O(1) 。

考虑到这些成本，很明显，至少在理论上，图遍历可能非常有效。但是，只有在为此目的设计的架构支持它们的情况下，此类高性能遍历才成为现实。

2.本机图存储

如果无索引的邻接关系是高性能遍历，查询和写入的关键，那么图形数据库设计的一个关键方面就是图形的存储方式。高效的本机图形存储格式支持任意图形算法的快速遍历，这是使用图形的重要原因。为了说明起见，我们将使用Neo4j数据库作为图形数据库的结构示例。

首先，让我们通过图6-3所示的Neo4j的高级体系结构将我们的讨论背景化。接下来，我们将自下而上地进行研究，从磁盘上的文件，编程API到Cypher查询语言。在此过程中，我们将讨论Neo4j的性能和可靠性特征，以及使Neo4j成为高性能，可靠的图形数据库的设计决策。

Neo4j将图形数据存储在许多不同的存储文件中。每个存储文件都包含图形特定部分的数据（例如，有单独的存储用于节点，关系，标签和属性）。存储职责的划分（尤其是图形结构与属性数据的分离）有助于进行高效的图形遍历，即使这意味着用户对其图形的看法与磁盘上的实际记录在结构上也不相同。让我们开始研究物理存储，方法是查看节点的结构和磁盘上的关系，如图6-4所示。

节点存储文件存储节点记录。用户级图中创建的每个节点最终都位于节点存储中，该节点存储的物理文件为neostore.nodestore.db。像大多数Neo4j存储文件一样，节点存储是固定大小的记录存储，其中每个记录的长度为9个字节。固定大小的记录可对存储文件中的节点进行快速查找。如果我们有一个ID为100的节点，那么我们知道它的记录从文件开始900个字节。根据这种格式，数据库可以直接计算记录的位置，而费用为O（1），而不是执行搜索，而费用为O（log n）。

节点记录的第一个字节是使用中(in-use)标志。这可以告诉数据库该记录当前是用于存储节点，还是可以代表新节点进行回收（Neo4j的.id文件跟踪未使用的记录）。接下来的四个字节表示连接到该节点的第一个关系的ID，接下来的四个字节表示该节点的第一个属性的ID。标签的五个字节指向该节点的标签存储（可以在标签相对较少的地方内联标签）。最后一个字节多余的部分用于标志。一个这样的标志用于标识密集连接的节点，其余空间保留供将来使用。节点记录非常轻巧：实际上只是指向关系，标签和属性列表的少数指针。

相应地，关系存储在关系存储文件neo store.relationshipstore.db中。与节点存储一样，关系存储也由固定大小的记录组成。每个关系记录都包含关系开始和结束时节点的ID，指向关系类型的指针（存储在关系类型存储中），指向每个开始和结束的下一个和上一个关系记录的指针节点和一个标志，指示当前记录是否是通常称为关系链的第一条记录。

节点和关系存储仅与图的结构有关，而与图的属性数据无关。这两个存储都使用固定大小的记录，因此只要指定了文件ID，就可以快速计算出商店文件中任何单个记录的位置。这些关键的设计决策突显了Neo4j对高性能遍历的承诺。

在图6-5中，我们看到了各种存储文件如何在磁盘上进行交互。两个节点记录中的每个记录都包含一个指向该节点的第一个属性和关系链中的第一个关系的指针。要读取节点的属性，我们遵循从第一个属性的指针开始的单链列表结构。为了找到节点的关系，我们遵循该节点的关系指针指向其第一个关系（在此示例中为LIKES关系）。然后，从此处开始，跟踪该特定节点的关系的双向链接列表（即开始节点双向链接列表或结束节点双向链接列表），直到找到我们感兴趣的关系为止。记录我们想要的关系，我们可以使用与节点属性相同的单链列表结构来读取该关系的属性（如果有），或者我们可以使用关系的开始检查关系所连接的两个节点的节点记录节点和终端节点ID。这些ID乘以节点记录大小，即可得出节点存储文件中每个节点的立即偏移量。

关系存储中的双链接列表

最初，如果关系存储结构看起来有些复杂，请不要担心。它不像节点存储或属性存储那么简单。

将关系记录视为“属于”两个节点（关系的开始节点和结束节点）会很有帮助。显然，我们不想存储两个关系记录，因为那样会很浪费。但是，同样清楚的是，关系记录应该以某种方式既属于起始节点又属于终止节点。

这就是为什么有两个双向链接列表的指针（又称记录ID）的原因。一个是从起始节点可见的关系列表。另一个是从终端节点可见的关系列表。每个列表都被双重链接，简单地使我们能够在任一方向上快速迭代该列表，并有效地插入和删除关系。

选择遵循不同的关系涉及对关系的链接列表进行迭代，直到找到合适的候选对象（例如，匹配正确的类型或具有一些匹配的属性值）。建立起适当的关系后，我们便重新开始业务，将ID乘以记录大小，然后追逐指针。

使用固定大小的记录和类似指针的记录ID，可以通过在数据结构周围跟踪指针来简单地实现遍历，这可以以很高的速度执行。为了遍历从一个节点到另一个节点的特定关系，数据库执行了几次廉价的ID计算（这些计算比搜索全局索引便宜得多，因为如果要伪造非图本机数据库中的图，则必须这样做）：

从给定的节点记录中，通过计算其在关系存储中的偏移量，即通过将其ID乘以固定的关系记录大小，来在关系链中找到第一条记录。这使我们直接到达关系存储中的正确记录。
从关系记录中，在第二个节点字段中查找以找到第二个节点的ID。将该ID乘以节点记录大小即可在存储中找到正确的节点记录。

如果我们希望将遍历限制为与特定类型的关系，则可以在关系类型存储区中添加查找。同样，这是ID与记录大小的简单乘积，以在关系存储中找到适当的关系类型记录的偏移量。同样，如果我们选择按标签进行约束，则会引用标签存储。

除了包含图结构的节点和关系存储外，我们还有属性存储文件，这些文件将用户的数据保存在键值对中。回想一下，Neo4j是一个属性图数据库，它允许将属性（name-value对）附加到节点和关系。因此，属性存储是从节点和关系记录中引用的。

属性存储中的记录，实际上，存储在neostore.propertys tore.db文件中。与节点和关系存储一样，属性记录的大小是固定的。每个属性记录都包含四个属性块和属性链中下一个属性的ID（请记住，与关系链中使用的双链表相比，属性在磁盘上作为单链表保存）。每个属性占用一个到四个属性块-一个属性记录最多可以容纳四个属性。属性记录保存属性类型（Neo4j允许任何原始JVM类型，字符串以及JVM基本类型的数组）以及指向属性索引文件的指针（neostore.propertystore.db.index）名称已存储。对于每个属性的值，记录都包含指向动态存储记录的指针或内联值。动态存储允许存储较大的属性值。动态存储有两个：动态字符串存储（neostore.propertystore.db.strings）和动态数组存储（neostore.propertystore.db.arrays）。动态记录包括固定大小记录的链接列表；因此，一个非常大的字符串或一个大数组可能会占用多个动态记录。

内联和优属性存储的利用

Neo4j支持存储优化，从而将某些属性直接内联到属性存储文件（neostore.propertystore.db）。当可以对属性数据进行编码以使其适合记录的四个属性块中的一个或多个时，就会发生这种情况。实际上，这意味着可以将诸如电话号码和邮政编码之类的数据直接内联到属性存储文件中，而不是将其推送到动态存储中。由于只需要单个文件访问，因此减少了I / O操作并提高了吞吐量。

除了内联某些兼容的属性值外，Neo4j还维护属性名称上的空间规则。例如，在社交图中，可能会有许多具有诸如first_name和last_name之类的属性的节点。如果将每个属性名称逐字写到磁盘上，那将很浪费，因此通过属性索引文件从属性存储中间接引用属性名称。属性索引允许具有相同名称的所有属性共享一条记录，因此对于重复图形（这是一种非常常见的用例），Neo4j节省了大量空间和I/O。

有效的存储布局只是图片的一半。尽管已针对快速遍历对存储文件进行了优化，但是硬件方面的考虑仍然会对性能产生重大影响。近年来，内存容量显着增加。尽管如此，非常大的图形仍将超出我们将其完全保存在主内存中的能力。硬盘的毫秒级搜索时间约为个位数，尽管按照人类的标准，这是快速的，但是在计算方面却非常缓慢。固态磁盘（SSD）更好（因为没有大的寻星等待磁盘旋转），但是CPU和磁盘之间的路径仍然比通向L2高速缓存或主内存的路径更潜伏，理想情况下，我们希望在图表上进行操作。

为了减轻机械/电子大容量存储设备的性能特征，许多图形数据库使用内存中缓存来提供对图形的概率低延迟访问。从Neo4j的2.2，一个off-heap缓存用于提供这种性能提升。

从Neo4j 2.2开始，Neo4j使用LRU-K页面缓存。页面高速缓存是一种LRU-K页面化高速缓存，这意味着该高速缓存将每个存储区划分为多个离散区域，然后每个存储文件保留固定数量的区域。页面是根据最不常用的（LFU）缓存策略从缓存中逐出的，这受页面受欢迎程度的影响。也就是说，优先页面会从缓存中撤出，而不是流行页面，即使最近没有访问过流行页面也是如此。此策略可确保在统计上优化使用缓存资源。

3.程序化API

尽管文件系统和缓存基础结构本身很吸引人，但是开发人员很少直接与它们进行交互。相反，开发人员通过查询语言来操纵图形数据库，查询语言可以是命令性的也可以是声明性的。本书中的示例使用Cypher查询语言，这是Neo4j固有的声明性查询语言，因为它是一种易于学习和使用的语言。但是，还存在其他API，根据我们在做什么，我们可能需要对不同的问题进行优先级排序。着手新项目时，务必要了解API的选择及其功能。如果本章没有其他内容，则可以将这些API视为堆栈，如图6-6所示：在顶部，我们重视表达性和声明性编程；在底部，我们奖励精度，命令式样式以及（最低层）“裸机（bare metal）”性能。

我们在第3章中详细讨论了Cypher。在以下各节中，我们将从底部到顶部逐步介绍其余的API。此API导览旨在进行说明。并非所有的图形数据库都具有相同数量的层，也不一定具有行为和交互方式完全相同的层。每个API都有其优点和缺点，您应该对其进行调查，以便做出明智的决定。

3.1.内核API（Kernel API）

API堆栈的最低层是内核的事务事件处理程序。这些允许用户代码在事务流过内核时侦听事务，此后基于事务的数据内容和生命周期阶段做出反应（或不做出反应）。

内核事务事件处理程序

事务事件处理程序的典型用例是防止记录的物理删除。可以将处理程序设置为拦截节点的删除，然后简单地将该节点标记为逻辑删除（或者以更复杂的方式，通过创建带有时间戳的归档关系将节点“回滚（back in time）”）。

3.2.核心API（Core API）

Neo4j的Core API是命令性Java API，它向用户提供节点，关系，属性和标签的图基元。当用于读取时，会延迟评估API，这意味着仅当调用代码要求下一个节点时才遍历关系。只要API调用者可以使用它，就可以从图形中检索数据，并且调用者可以选择随时终止遍历。对于写操作，Core API提供了事务管理功能，以确保原子，一致，隔离和持久的持久性。

在以下代码中，我们看到从Neo4j教程借来的代码片段，在其中我们尝试从Doctor Who宇宙中找到人类伴侣：


// Index lookup for the node representing the Doctor is omitted for brevity
Iterable<Relationship> relationships =
        doctor.getRelationships( Direction.INCOMING, COMPANION_OF );
for ( Relationship rel : relationships )
{
    Node companionNode = rel.getStartNode();
    if ( companionNode.hasRelationship( Direction.OUTGOING, IS_A ) )
    {
        Relationship singleRelationship = companionNode
            .getSingleRelationship( IS_A, Direction.OUTGOING );
        Node endNode = singleRelationship.getEndNode();
        if ( endNode.equals( human ) )
        {
            // Found one!
        }
    }
}

这段代码非常重要：我们只需要在Doctor的同伴之间循环，并检查是否有任何同伴节点与代表人类物种的节点之间具有IS_A关系。如果同伴节点连接到人类物种节点，我们将对其进行处理。

因为它是命令性API，所以Core API要求我们对其进行微调以使其成为基础图结构。这可以非常快。但是，与此同时，这意味着我们最终将特定领域结构的知识应用到我们的代码中。与更高级别的API（尤其是Cypher）相比，需要更多的代码才能实现相同的目标。尽管如此，Core API和底层记录存储之间的亲和力显而易见，Core API相对忠实地向用户代码公开了存储和缓存级别使用的结构。

3.3.遍历框架（Traversal Framework）

遍历框架是声明性Java API。它使用户可以指定一组约束，这些约束限制了允许遍历的图形的各个部分。我们可以指定要遵循的关系类型和方向（有效地指定关系过滤器）；我们可以指出我们要遍历是广度优先还是深度优先；并且我们可以指定一个用户定义的路径评估器，该评估器由遇到的每个节点触发。在遍历的每个步骤中，该评估器确定下一步如何进行遍历。以下代码段显示了运行中的遍历API：


Traversal.description()
    .relationships( DoctorWhoRelationships.PLAYED, Direction.INCOMING )
    .breadthFirst()
    .evaluator( new Evaluator()
{
    public Evaluation evaluate( Path path )
    {
        if ( path.endNode().hasRelationship(
                            DoctorWhoRelationships.REGENERATED_TO ) )
        {
            return Evaluation.INCLUDE_AND_CONTINUE;
        }
        else
        {
            return Evaluation.EXCLUDE_AND_CONTINUE;
        }
    }
} );

通过此摘要，可以清楚地看到遍历框架的主要声明性。 Relationships()方法声明只能在INCOMING方向上遍历PLAYED关系。此后，我们声明遍历应该以breadthFirst()方式执行，这意味着它将遍历所有最近的邻居，然后再进行进一步的遍历。

遍历框架在导航图结构方面是声明性的。但是，对于我们的Evaluator实施，我们将使用命令式Core API。也就是说，在给定当前节点的路径的情况下，我们使用Core API来确定是否有必要进一步遍历该图（我们也可以使用Core API从评估程序内部修改该图）。同样，数据库内部的本地图结构在此处靠近表面气泡，而节点，关系和属性的图基元在API中占据中心位置。

核心API，遍历框架还是Cypher？（Core API, Traversal Framework, or Cypher?）

给定这几种查询图形的不同方法，我们应该选择哪一种？

核心API（Core API）允许开发人员微调其查询，以使其与基础图形具有高度的亲和力。编写良好的Core API查询通常比任何其他方法都快。缺点是此类查询可能很冗长，需要开发人员付出大量努力。此外，它们与基础图的高度亲和性使它们紧密耦合到其结构。当图结构改变时，它们经常会断裂。 Cypher对结构变化的容忍度更高-诸如可变长度路径之类的东西有助于减轻变化和变化。

遍历框架（Traversal Framework）的耦合性比Core API宽松（因为它允许开发人员声明信息目标），而且冗长得多，因此，使用遍历框架（Traversal Framework）编写的查询通常比使用核心API（Core API）编写的查询所需的开发工作更少。但是，由于它是通用框架，因此遍历框架的性能往往不如编写良好的Core API查询好。

如果我们发现自己处于使用Core API或Traversal Framework进行编码的异常情况下（从而避免使用Cypher及其提供的功能），那是因为我们正在研究一种边缘情况，我们需要精心设计无法使用高效表达的算法，密码的模式匹配。在Core API和Traversal Framework之间进行选择是要确定Traversal Framework的较高抽象/较低耦合是否足够，或者实际上是否需要Core API的接近金属（metal）/较高耦合才是必要的。根据我们的性能要求正确实施算法。

到此，我们以本机Neo4j API为例对图形编程API进行了简要调查。我们已经了解了这些API如何反映Neo4j堆栈较低层中使用的结构，以及这种对齐方式如何允许惯用且快速的图形遍历。

但是，数据库的快速运行还不够。它也必须是可靠的。这使我们对图数据库的非功能特性进行了讨论。

4.非功能特性（Nonfunctional Characteristics）

至此，我们已经了解了构建本地图形数据库的含义，并了解了如何使用Neo4j作为示例来实现其中某些图形本地功能。但是要被认为是可靠的，任何数据存储技术都必须在某种程度上保证所存储数据的持久性和可访问性。

传统上评估关系数据库的一种常用方法是每秒可处理的事务数。在关系世界中，假定这些事务维护ACID属性（即使存在故障），以使数据一致且可恢复。对于大批量的不间断处理和管理，关系数据库有望扩展，以便许多实例可用于处理查询和更新，而单个实例的丢失不会过度影响整个群集的运行。

至少在高层次上，图数据库也是如此。他们需要保证一致性，从崩溃中正常恢复，并防止数据损坏。此外，他们需要扩展以提供高可用性并扩展性能。在以下部分中，我们将探讨这些要求中的每一个对于图形数据库体系结构的意义。再一次，我们将通过研究Neo4j的体系结构来扩展某些方面，以提供具体示例。应该指出的是，并非所有图形数据库都是完全ACID的。因此，重要的是要了解所选数据库的事务模型的细节。 Neo4j的ACID事务性显示了可以从图形数据库获得的相当高的可靠性水平，这是我们习惯从企业级关系数据库管理系统获得的水平。

4.1.事务处理（Transactions）

数十年来，事务一直是可靠的计算系统的基础。尽管许多NOSQL存储区都不进行事务处理，部分原因是未经验证的假设认为事务处理系统的伸缩性较差，但是事务仍然是当代图形数据库（包括Neo4j）中可靠性的基本抽象。（关于事务限制可伸缩性的说法是有道理的，因为在病理情况下，分布式的两阶段提交可能会显示不可用性问题，但总的来说，其效果远不如通常所设想的那样。）

Neo4j中的事务在语义上与传统的数据库事务相同。写入发生在事务上下文中，为了保持一致性，对事务中涉及的任何节点和关系都采用了写锁。事务成功完成后，更改将刷新到磁盘以提高持久性，并释放写锁定。这些动作保持了事务的原子性保证。如果事务由于某种原因失败，则将丢弃写入并释放写入锁，从而将图形保持在其先前的一致状态。

如果两个或多个事务试图同时更改相同的图形元素，Neo4j将检测到潜在的死锁情况，并对事务进行序列化。单个事务上下文中的写入将对其他事务不可见，从而保持隔离。

Neo4j中如何实现事务

Neo4j中的事务实现在概念上很简单。每个事务都表示为一个内存中对象，其状态表示对数据库的写入。锁定管理器支持该对象，该管理器在创建，更新和删除节点和关系时将写锁定应用于节点和关系。在事务回滚时，将丢弃事务对象并释放写锁，而在成功完成时，将事务提交到磁盘。

在Neo4j中将数据提交到磁盘使用预先写入日志，从而将更改作为可操作条目附加到活动事务日志中。在事务提交时（假定对准备阶段的响应是肯定的），提交条目将被写入日志。这将导致日志刷新到磁盘，从而使更改具有持久性。一旦发生磁盘刷新，更改将应用于图本身。将所有更改应用于图之后，将释放与事务关联的所有写锁。

提交事务后，即使故障导致非病理性故障，系统也处于保证更改在数据库中的状态。正如我们现在所看到的，这在可恢复性和持续提供服务方面具有实质性优势。

4.2.可恢复性（Recoverability）

数据库与任何其他软件系统都没有什么不同，因为它们易于在实现，运行的硬件以及硬件的电源，散热和连通性方面受到错误的影响。尽管勤奋的工程师试图将所有这些故障的可能性降到最低，但在某些时候数据库不可避免地会崩溃—尽管两次故障之间的平均时间确实应该很长。

在设计良好的系统中，数据库服务器崩溃虽然很烦人，但不影响可用性，尽管它可能会影响吞吐量。并且，当发生故障的服务器恢复运行时，无论崩溃的性质或时机如何，它都不得向其用户提供损坏的数据。

当从不正常的关机中恢复时，Neo4j可能是由故障甚至是过度的操作员引起的，都会检入最近活动的事务日志，并根据存储，重放，找到的所有事务。这些事务中的某些事务可能已经应用于存储，但是由于重播是幂等操作，因此最终结果是相同的：恢复后，存储将与失败之前成功提交的所有事务保持一致。

在单个数据库实例的情况下，仅需进行本地恢复。但是，通常，我们在群集中运行数据库（稍后将讨论），以确保代表客户端应用程序的高可用性。幸运的是，群集为恢复实例提供了更多好处。如前所述，实例不仅会与失败之前成功提交的所有事务保持一致，而且还可以迅速赶上群集中的其他实例，从而与失败之后成功提交的所有事务保持一致。也就是说，本地恢复完成后，副本服务器可以向群集的其他成员（通常是主服务器）询问任何新的事务。然后，它可以通过事务重播将这些较新的事务应用于其自己的数据集。

可恢复性处理数据库在发生故障后立即进行设置的能力。除了可恢复性之外，一个良好的数据库还需要高度可用才能满足数据密集型应用程序日益复杂的需求。

4.3.可用性（Availability）

Neo4j的事务和恢复功能除了本身有价值之外，还具有其高可用性特征。数据库能够在崩溃后识别并在必要时修复实例，这意味着无需人工干预即可快速恢复数据。当然，更多的活动实例可以提高数据库处理查询的整体可用性。

在典型的生产场景中，通常需要单独的断开连接的数据库实例。通常，我们对数据库实例进行集群以实现高可用性。 Neo4j使用主从集群配置来确保图形的完整副本存储在每台计算机上。写入会定期从主机复制到从机。在任何时候，主服务器和一些从服务器都将拥有该图的最新副本，而其他从服务器将迎头赶上（通常，它们仅落后毫秒）。

对于写操作，具有读取从属关系的经典写主是一种流行的拓扑。通过这种设置，所有数据库写操作都针对主服务器，而读操作则针对从属服务器。这为写入提供了渐进的可伸缩性（最大达到单个主轴的容量），但为读取提供了近乎线性的可伸缩性（考虑到管理集群的适度开销）。

尽管带有读取从机的写主机是经典的部署拓扑，但Neo4j还支持通过从机进行写。在这种情况下，客户端首先将写操作定向到的从属服务器确保其与主服务器保持一致（“追赶”）；此后，将在两个实例之间同步处理写操作。当我们要在两个数据库实例中具有持久性时，这很有用。此外，由于它允许将写入定向到任何实例，因此它提供了额外的部署灵活性。然而，由于强制追赶阶段，这以更高的写入等待时间为代价。这并不意味着写操作会在系统中分布：所有写操作仍必须在某个时刻通过主服务器。

Neo4j中的其他复制选项

从Neo4j 1.8版开始，可以指定在认为事务完成之前，以尽力而为的方式将对主服务器的写入复制到任意数量的副本中。这提供了通过从站写入实现的“至少两个”持久性级别的替代方法。有关更多详细信息，请参见“复制”。

可用性的另一个方面是争用资源。争夺对图的特定部分的排他访问（例如，用于写入）的操作可能遭受足够高的等待时间，以致显得不可用。我们已经在RDBMS中看到了粗粒度表级锁定的类似争用，即使逻辑上没有争用，写操作也是潜在的。

惯用查询的好处

一级方程式赛车手杰基·斯图尔特（Jackie Stewart）曾说过，要驾驶好汽车，您不需要成为一名工程师，但是您需要机械上的配合。也就是说，最佳性能来自于驾驶员和汽车和谐地协作。

以几乎相同的方式，当图数据库查询被构造为从一个或多个起点开始遍历的惯用图本地查询时，它们被视为机械同情数据库。对基础结构（包括缓存和存储访问）进行了优化，以支持此类工作负载。

惯用查询具有有益的副作用。例如，由于缓存与惯用搜索保持一致，因此，本身是惯用的查询往往比非惯用的查询更好地利用缓存并运行得更快。反过来，快速运行的查询可以释放数据库以运行更多数据库，这意味着从客户端的角度来看，吞吐量更高，可用性更高，因为等待的时间更少。

单项查询（例如，选择随机节点/关系而不是遍历的查询）表现出相反的特征：它们不尊重底层的缓存层，因此运行速度较慢，因为需要更多的磁盘I / O。由于查询运行缓慢，因此数据库每秒可以处理更少的查询，这意味着从客户端的角度来看，数据库执行有用工作的可用性降低了。

无论使用哪种数据库，了解底层存储和缓存基础结构都将帮助我们构建惯用的（因此机械上能相互配合）查询，以最大限度地提高性能。

我们对可用性的最终观察是，针对群集范围的复制进行扩展具有积极的影响，不仅在容错方面，而且在响应能力方面。因为有许多计算机可用于给定的工作负载，所以查询延迟很短，并且可以保持可用性。但是，正如我们现在将要讨论的，扩展本身比我们部署的服务器数量更加细微。

4.4.规模（Scale）

随着数据量的增长，规模主题变得越来越重要。实际上，事实证明，关系数据库难以解决的大规模数据问题一直是NOSQL运动的主要动力。从某种意义上说，图形数据库没有什么不同。毕竟，它们还需要扩展以满足现代应用程序的工作量需求。但是规模并不是一个简单的值，例如每秒的事务数。而是我们跨多个轴衡量的汇总值。

对于图数据库，我们将把对比例的广泛讨论分解为三个关键主题：

容量 Capacity (graph size)
潜在因素 Latency (response time)
读写吞吐量 Read and write throughput

4.4.1.Capacity

一些图形数据库供应商选择避开图形大小的任何上限，以换取性能和存储成本。 Neo4j历史上采用了某种独特的方法，通过优化图大小等于或低于用例第95个百分位数的情况，维护了一个“最佳点”，该点可实现更快的性能和更低的存储量（并因此减少了内存占用和IO-ops）进行权衡的原因在于使用了固定的记录大小和指针（如“本机图形存储”中所述），它在存储内部大量使用。在撰写本文时，Neo4j的当前版本可以支持具有数百亿个节点，关系和属性的单个图。这样就可以将社交网络数据集的大小与Facebook的大小相提并论。

Neo4j团队已公开表示打算在单个图中支持100B + 节点/关系/属性（nodes/relationships/properties）作为其路线图的一部分。

数据集必须利用多少大小才能利用图形数据库必须提供的所有优势？答案是，比您想像的要小。对于二级或三级查询，在具有几个个位数的千个节点的数据集上，性能优势会显现出来。查询的程度越高，变化量就越极端。易于开发的好处当然与数据量无关，并且无论数据库大小如何都可以使用。作者已经看到有意义的生产应用程序，范围从小到几万个节点，数十万个关系到数十亿个节点和关系。

4.4.2.Latency

图形数据库不会像传统的关系数据库一样遭受延迟问题的困扰，在传统的关系数据库中，表和索引中的数据越多，联接操作的时间就越长（这种简单的事实是性能调优几乎是关键的原因之一）始终是关系型DBA的首要问题）。对于图形数据库，大多数查询都遵循一种模式，在该模式下，仅使用索引来查找一个或多个起始节点。然后，遍历的其余部分使用指针追踪和模式匹配的组合来搜索数据存储。这意味着，与关系数据库不同，性能不取决于数据集的总大小，而仅取决于要查询的数据。这导致性能时间几乎是恒定的（即与结果集的大小有关），即使数据集的大小不断增长（尽管正如我们在第3章中所讨论的那样，仍然需要调整性能）。图形以适合查询，即使我们处理的数据量较小也是如此。

4.4.3.Throughput

我们可能认为图形数据库需要以与其他数据库相同的方式进行缩放。但这不是事实。当我们查看IO密集型应用程序行为时，我们看到单个复杂的业务操作通常会读写一组相关数据。换句话说，应用程序对整个数据集中的逻辑子图执行多项操作。使用图形数据库，可以将多个操作汇总为更大，更紧密的操作。此外，对于图形本机存储，执行每个操作比等效的关系操作需要更少的计算量。对于相同的结果，图形可以通过减少工作量来进行缩放。

例如，假设有一个发布场景，我们想要阅读作者的最新文章。在RDBMS中，我们通常通过以下方式来选择作者的作品：根据匹配的作者ID将authors表与出版物表相连，然后按出版日期对出版物进行排序，并限制为最新的出版物。根据订购操作的特性，可能是O(log(n))操作，这并不是很糟糕。

但是，如图6-7所示，等效图形操作为O（1），这意味着性能稳定，与数据集大小无关。使用图表，我们只需遵循从作者到已发表文章列表（或树）顶部的工作的称为WROTE的出站关系。如果我们希望找到较旧的出版物，我们只需遵循PREV关系并通过链表进行迭代（或者通过树进行递归）。写操作更合适，因为我们总是在列表的开头（或树的根）插入新的出版物，这是另一个固定时间的操作。与RDBMS替代方案相比，这是有利的，特别是因为它自然地保持了读取的恒定时间性能。

当然，最苛刻的部署将使一台计算机运行查询的能力不堪重负，更具体地说，其I / O吞吐量将不堪重负。发生这种情况时，使用Neo4j构建可水平扩展以实现高可用性和高读取吞吐量的集群非常简单。对于典型的图形工作负载（读取远超过写入），此解决方案体系结构可能是理想的选择。

如果我们超出了集群的容量，则可以通过在应用程序中建立分片逻辑来在整个数据库实例中分布图。分片涉及在应用程序级别使用综合标识符来跨数据库实例连接记录。执行效果如何很大程度上取决于图形的形状。一些图形非常适合这一点。例如，Mozilla将Neo4j图形数据库用作其下一代云浏览器Pancake的一部分。它存储了大量独立于终端用户的小独立图，而不是拥有一个大图。这使得扩展非常容易。

当然，并不是所有的图都有这样方便的边界。如果我们的图足够大以至于需要分解，但是不存在自然界限，则我们使用的方法与使用MongoDB等NOSQL存储的方法几乎相同：我们创建综合（synthetic）键，并通过应用层使用这些键以及一些应用程序级别的解析算法。与MongoDB方法的主要区别在于，本机图数据库将在您在数据库实例内进行遍历时随时为您提供性能提升，而在实例之间运行的遍历部分将以与MongoDB大致相同的速度运行加入。但是，总体性能应该明显更快。

图可扩展性的圣杯

大多数图形数据库的未来目标是能够在多台计算机之间划分图形，而无需应用程序级别的干预，以便可以水平缩放对图形的读写访问。通常情况下，这是一个NP Hard问题，因此不切实际。

对于幼稚的问题，由于遍历（慢速）网络的计算机之间的图形遍历会导致意外的查询时间，从而导致查询时间无法预测。相比之下，明智的实现可以理解特定域范围内的最小切点，从而最大程度地减少了跨机器的遍历。尽管在撰写本文时该地区正在进行令人兴奋的研究工作，但尚无数据库可证明地支持这种行为。

5.摘要

在本章中，我们展示了属性图如何成为实用数据建模的理想选择。我们已经探究了图形数据库的体系结构，特别参考了Neo4j的体系结构，并讨论了图形数据库实现的非功能性特征及其对可靠性的意义。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/1013524