作者 | 西湖数据智能研究院高级研发工程师 无极
大千世界纷繁复杂，万物之间总会有千头万绪的关系。随着古代商业社会的倒退，事物的关联关系越发盘根错节，传统的关系存储曾经不能满足咱们的业务需要。“图”作为关系摸索将来倒退的风向标，能够更为直观地帮忙人们认知事物，开掘数据之间的神秘，为数据价值的体现开拓了新天地。
作为业余的数据智能上市公司，个推在图利用剖析方面也进行了丰盛的实际。本文将讲述图的常见业务场景、Neo4j 在个推的落地利用案例和优化动作，并在此基础上创新性地提出了个推独有的 Neo4j 社区版 HA（High Availability）计划。
01 图
驰名的柯尼斯堡七桥问题拉开了图的新篇章。1736 年，莱昂哈德·欧拉针对该问题，进行了数学形象，用二维矩阵予以示意，奠定了图论的根底。
图片来源于 neo4j.com
什么是图？
图的定义指出，图 G 由两个汇合形成，记作 G =<V,E>。其中 V 是顶点的非空无限汇合，E 是边的无限汇合，边是顶点的无序对或有序对汇合。为了更好地了解图，咱们能够看看上面的例子。
图片来源于 neo4j.com
图中展现了 3200 个机场与 60000 条航线。对应图的定义，每个机场就是 V 汇合，航线则是 E 汇合。
图有哪些存储形式？
• 图的邻接矩阵
• 图的邻接表
• 有向图的十字链表存储示意
• 无向图的邻接多重表存储示意
图有哪些遍历形式？
• 深度优先遍历(DFS)
• 广度优先遍历(BFS)
图数据库
图数据库(GraphDatabase) 并非指存储图片的数据库，而是指反对以图数据结构存储和查问数据的数据库。图数据库是一种在线数据库管理系统，具备解决图数据模型的创立、读取、更新和删除（CRUD）操作。
图片来源于 amazon.com
图存储
一些图数据库应用原生图存储，这类存储是通过优化的，并且是专门为了存储和治理图而设计的。并不是所有图数据库都应用原生图存储，也有一些图数据库将图数据序列化，而后保留到关系型数据库、面向对象数据库，或其余通用数据存储中。
图解决引擎
原生图解决（也称为无索引邻接）因为其连贯的节点在数据库中能够物理地指向彼此，因而被认为是解决图数据的最无效的办法。非原生图解决应用其余办法来解决 CRUD 操作。
图常见业务场景
图片来源于 amazon.com
上图中展现了图在 社交网络、举荐零碎、常识图谱、欺诈检测、生命科学、网络运维等业务场景中的利用。举荐零碎是图的一个典型利用，比方当咱们想要查问难看的影片之时，售票软件会依据咱们常常看的类型和格调帮咱们举荐相似的电影。
图数据库排名
依据 DB-Engines 统计，2020 年图数据库受欢迎水平排行榜清晰地表明 Neo4j 曾经抢占了图数据库的半壁江山。
02 Neo4j 图数据库
Neo4j 是一个高性能的 NOSQL 图形数据库，它将结构化数据存储在网络上而不是表中。它是一个嵌入式的、基于磁盘的、具备齐全的事务个性的 Java 长久化引擎，也能够被看作是一个高性能的图引擎，该引擎具备成熟数据库的所有个性。
Neo4j 让程序员工作在一个面向对象的、灵便的网络结构下而不是严格、动态的表中——但他们能够还能享受到具备齐全的事务个性、企业级的数据库的所有益处。
图片来源于 neo4j.com
图中展现了 Neo4j 图数据库从存储到剖析的平台生态。
Neo4j 社区版 (4.0.6) 存储剖析
图片来源于 neo4j.com
Node 存储(15 bytes)
节点存储文件为 neostore.nodestore.db，定长记录文件，每个记录代表一个节点。
• inUse(1 byte)
– [x x x x,_ _ ] 1-4 示意 nextPropId 的高 4 位
– [ _ , x x x ] 5-7 示意 nextRelId 的高 3 位
– [ _ , _ _ x ] 8 示意节点是否可用
• nextRelId (4 bytes) : 节点关联的第一条边的 id 的低位，加上 inUse 中的 3 个 bit，relId 一共 35 个 bit
• nextPropId (4 bytes)：节点关联的第一个属性的 id 的低位，加上 inUse 中的 4 个 bit，propId 一共 36 个 bit
• labels (5 bytes) : 存储 label 信息，前 4 个 byte 为低位，最初一个 1 个 byte 为高位
– [1 x x x ,_ _ ] : 第一个 bit (1)示意 内联，2-4 示意 label 数量, 剩下的 36 个 bit 应用除法均分给每个 label，代表 label 的 id
– [0 _ ,_ _ ] : 第一个 bit (0)示意 非内联，则低位的 36 个 bit 示意第一个动静 label 记录的 id
• extra (1 byte) : [ _ , _ _ x ] 只用到最初一个 bit，用来标记是否为超级节点
边的 id 长度为 35bit，即边下限 320 亿左右，属性的 id 长度为 36bit，则属性下限约 640 亿。
Relationship 存储 (34 bytes)
边存储文件为 neostore.relationshipstore.db，定长记录文件，每个记录代表一条边
• inUse(1 byte)
– [x x x x,_ _ ] 1-4 示意 nextPropId 的高 4 位
– [ _ , x x x ] 5-7 示意 firstNodeId 的高 3 位
– [ _ , _ _ x ] 8 示意节点是否可用
• firstNode（4 bytes）：边关联的第一个节点 id 的低位，加上 inUse 中的 3 个 bit，nodeId 一共 35 个 bit
• secondNode（4 bytes）：边关联的第二个节点 id 的低位，加上 relationshipType mid 中的 3 个 bit，nodeId 一共 35 个 bit
• relationshipType (4 bytes) :
– mid（2 bytes）：
• [ x x x , _ , _ , _ ]：2- 4 示意 secondNodeId 的高 3 位
• [ _ , x x x , _ , _ ]：5- 7 示意 first prevRelId 的高 3 位
• [ _ , _ x , x x _ , _ _ ]：8-10 示意 firstNextRelId 的高 3 位
• [ _ , _ , x x , x _ ]：11-13 示意 secondPrevRelId 的高 3 位
• [ _ , _ , _ , x x x ]：14-16 示意 secondNextRelId 的高 3 位
– type（2 bytes）：边类型 id
• firstPrevRelId（4 bytes）：第一个节点相干的前一条边 id 的低位，加上 relationshipType mid 中的 3 个 bit，relId 一共 35 个 bit
• firstNextRelId（4 bytes）：第一个节点相干的后一条边 id 的低位，加上 relationshipType mid 中的 3 个 bit，relId 一共 35 个 bit
• secondPrevRelId（4 bytes）：第二个节点相干的前一条边 id 的低位，加上 relationshipType mid 中的 3 个 bit，relId 一共 35 个 bit
• secondNextRelId（4 bytes）：第二个节点相干的后一条边 id 的低位，加上 relationshipType mid 中的 3 个 bit，relId 一共 35 个 bit
•nextPropId (4 bytes)：边关联的第一个属性的 id 的低位，加上 inUse 中的 4 个 bit，propId 一共 36 个 bit
• firstInChainMarkers（1 byte）：
– [ _ , _ x _ ]：第 7 个 bit 标识是否为第一个节点的第一条边
– [ _ , _ _ x ]：第 8 个 bit 标识是否为第二个节点的第一条边
通过存储构造咱们能够看出，边存储了两端节点的 id 以及两条双向链表，参考如图：
图片来源于 neo4j.com
Neo4j 大数据量读写优化
读优化
当咱们遇到一个工作有很多关系的时候，如果要查问这个工作下所有数据，则须要 match(n)扫描所有的 Node，而这样查问效率会非常低。为了解决这个问题，咱们依然采纳空间换工夫的形式，引入了辅助 label，这样能够高效地抽出指定工作下的所有数据，将原来 8 秒 查问的效率优化到了 100 毫秒 以内。
写优化
Neo4j 传统的数据导入形式是要先创立 Node，而后再创立 Relation，接着通过 cypher（SQL）执行打算剖析。在此过程中，创立 Node 和 Relation 步骤耗时少，但 match 操作却非常耗时。
为了解决创立 Relation 的过程中须要 match 操作而导致的耗时问题，咱们先创立 Node 与 Relation（Relation 的终点和起点与创立的 Node 有独特属性），而后通过 Node 某个特定属性合并 Node，并采纳空间换工夫的计划来实时写入数据，最终将原来 Node、Relation 写入效率从 40 分钟 缩减到了 3 分钟。
Tips
空间换工夫与 工夫换空间 是解决性能平衡问题的两种形式，抉择工夫与空间正当的平衡点能极大地提高咱们软件的服务质量。
Neo4j 社区版 HA（high availability）计划摸索
通过比照剖析，咱们最终抉择采纳 Neo4j 图数据库。Neo4j 企业版性能尽管较全然而价格十分低廉，为此咱们将指标瞄向 Neo4j 社区版。而 Neo4j 社区版存在不反对高可用、数据无奈备份的毛病，不利于其在业务环境下的应用，因而设计一种 HA 计划，来解决单点故障是十分有必要的。以下是 Neo4j 社区版高可用的一种摸索计划。
**1. Neo4j 部署 master 节点与 slave 节点，master 可读可写，slave 仅可读。
- 通过 lsyncd 将 Neo4j 主节点的 data 目录实时同步到 slave 的 data 目录。
- slave data 目录挂载到 master 节点的特定目录下。
- 定时重启 slave 节点（Neo4j 社区版须要重启加载同步的数据文件），容许 slave 节点与主节点之间存在肯定的数据提早。
- 当 master 呈现故障后，驱动会连贯一个可用的 slave，“只读 slave”提供查问，此时无奈写入数据，并告知用户 master 节点产生故障，须要及时处理。**
03 总结
图数据库具备高度关联的个性，能疾速进行简单关系数据处理，从而能够无效帮忙企业取得更粗浅的洞察力和更多的竞争劣势。业内越来越多的公司开始布局图数据库畛域钻研，研发本人的图数据库系统。作为领有海量数据积淀的数据智能上市公司，个推在图数据库实际畛域不断创新，继续打磨本身图开掘与剖析技术的同时，也期待与业界一起碰撞更多的图数据库实际。
参考资料:
https://db-engines.com/en/ran…
https://neo4j.com/docs/
https://www.tutorialspoint.co…
https://www.6aiq.com/article/…
https://aws.amazon.com/
https://www.tony-bro.com/post…