《图数据库(第2版)》——2.2 NoSQL数据库也缺少联系

简介:

本节书摘来自异步社区出版社《图数据库(第2版)》一书中的第2章,第2.2节,作者:【美】Ian Robinson(伊恩•罗宾逊) , Jim Webber(吉姆•韦伯) , Emil Eifrem(埃米尔•艾弗雷姆),更多章节内容可以访问云栖社区“异步社区”公众号查看。

2.2 NoSQL数据库也缺少联系

大多数NoSQL数据库—无论是键值数据库、文档数据库,还是基于列的数据库—存储的都是无关联的文档/值/列,因此很难将它们用于关联数据和图。

对这些数据库来说,一种广为认知的添加联系的策略是在某个聚合数据(aggregate)中嵌入另一个聚合数据标识符,即添加外键。然而这需要在应用层连接聚合数据,其代价极速增加。

当我们着眼于聚合存储模型(aggregate store model)时,如图2-3所示,想象我们可以看到联系。看到开头为user: Alice的记录中有对订单的引用order: 1234时,我们推断user: Aliceorder: 1234之间存在关联。而这给了我们错误的希望:我们可以使用键值对来管理图。

在图2-3中,我们看到一些属性值确实引用了数据库中其他的聚合数据。然而将这些引用转化为可导航的结构并非是没有代价的,因为聚合数据之间的联系并非数据模型中的一等公民—多数聚合存储只是以内嵌映射结构的方式装饰在聚合数据之内。相反,应用程序使用数据库时必须从这种扁平的、无关联的数据结构中建立起联系。我们还必须确保应用程序能够随着剩余数据的变化更新或删除外部聚合引用。假如不这样做,存储将积累无用的引用,从而破坏数据的质量和查询性能。
image

Riak中的指针(Link)和查找(Walking)

Riak键值存储引擎允许使用指针(Link)元数据去扩展每个存储的值。指针都是单向的,从一个存储的值指向另一个。Riak允许查找(Walk)(Riak术语)任何数量的指针,从而一定程度上将数据模型关联起来。然而,Riak的指针查找是通过map-reduce驱动的,这一定程度上会有延迟。与图数据库不同,这种指针的连接仅适用于简单的图结构编程,对于通用的图算法就不适用了。
这种方案还有另一个弱点。由于没有反向指针(外部聚合引用的指针当然不是自反的),数据库丧失了运行其他有趣的查询的能力。比如图2-3中,想要知道是谁买了某种商品(也许问这个问题的目的是想要基于客户资料进行推荐)就是一个代价高昂的操作。想要回答这类问题,我们可能得通过导出数据集并在外部计算框架(如Hadoop)上运行它们来暴力地获得结果。或者只能回过头将外部聚合引用反向插入,随后才能查询结果。无论哪种方法,结果都不是直接的,而是隐含的。

人们很容易认为聚合存储和图数据在关联数据这方面的功能是等同的。但其实不是这样。聚合存储并不维护关联数据的一致性,也不提供免索引邻接(index-free adjacency),即元素直接与其邻居相连。因此为了解决数据关联问题,聚合存储必须使用其提供的隐含方法在数据模型之外创建和查询联系。

让我们看看它们的局限性是如何表现的。图2-4展示了一个用文档实现的使用聚合存储的小型社交网络。
image

通过这种结构,可以很容易地找到用户的直接朋友—假设应用程序一直在努力确保存储在friends属性中的标识符与数据库中的其他记录的ID保持一致。在这种情况下,我们可以简单地通过它们的ID检索直接朋友,这需要对每个朋友进行大量索引查找,但不需要对整个数据集进行暴力扫描。这样做我们会发现,Bob认为AliceZach是他的朋友。

但朋友关系不总是对称的。如果我们想问问“谁的朋友是Bob?”而不是“谁是Bob的朋友?”问题就相对难以回答了。在这种情况下,我们唯一的选择是暴力扫描整个数据集,从而在所有friends条目中寻找到包含Bob的条目。

O符号和暴力计算

我们用O符号作为描述一个算法的性能随数据集的大小而变化的简写方式。O(1)算法表示性能的时间复杂度为常数时间,也就是说,该算法与数据集大小无关,无论数据集大小如何,执行算法所花时间都是相同的。O(n)算法表示性能的时间复杂度为线性时间,当数据集增加一倍,执行算法所花时间也会增加一倍。O(log n)算法表示性能的时间复杂度为对数时间,当数据集增加一倍,执行算法所花时间增加一个固定的量。在起步阶段,随着数据集的增大,其所花时间的增加相对很多,但数据集变得非常大的时候,时间的增加会渐渐消失趋于稳定。O(m log n)算法表示的时间复杂度是本书所考虑的最差情况。在O(m log n)的算法中,当数据集增加一倍时,执行时间会在加倍的同时有额外的增加,其增加量与数据集中元素数目成正比。

暴力计算整个数据集的时间复杂度是O(n),因为在数据存储中所有的即n个聚合数据都需要加以考虑。这对于大多数合理规模的数据集来说代价过高,因此我们倾向于选择一个时间复杂度为O(log n)的算法(这在很大程度上是高效的,因为它在每次迭代时能够丢弃掉一半的潜在工作量)或者复杂度更低的算法。

相反,图数据库对于同一个查询提供恒定的查找顺序。在这种情况下,我们只需在图中找到表示Bob的节点,然后寻找任何friend的入度联系,这些联系连接的节点表示那些认为Bob是他们的朋友的人。这比暴力扫描的代价小得多,因为它只和网络中很少的节点相关,即,那些和Bob关联的节点。当然,如果所有人都认为Bob是他们的朋友,我们还是会遍历到整个数据集。
为了避免处理整个数据集,我们可以增加反向指针,但这会反规范化存储模型。通过为每个用户添加第二个属性,也许可以称为friended`_`by,我们可以列出与该用户相关联的入度朋友关系。但这不是没有代价的。对于起点数据,我们要因写入延迟增加初始成本和后续成本,还要为存储额外的元数据增加磁盘使用开销。最重要的是,因为每一跳(hop)都需要通过一次索引查找,所以遍历指针的代价仍然很高。这是因为聚合数据没有局部性这个概念,它不像图数据库那样通过真实的(而不是具体化的)联系自然地提供免索引邻接。如此,通过实现图结构之上的非原生存储,我们获得了局部连通性的好处,但却引入了巨大的开销。

当遍历涉及两跳或更深的时候,这种巨大的开销被放大了。朋友关系是足够简单的,然而想象一下,当试图实时地计算朋友的朋友,或是朋友的朋友的朋友时,这类数据库就不合时宜了,因为遍历一个虚假的联系的代价并不小。这不仅限制了你扩大社交网络的机会,也减少了有益的推荐,遗漏了数据中心的故障设备,并让欺诈采购活动成为漏网之鱼。许多系统试图去维护类图的计算处理,但仍不可避免地使用批处理,并非按照用户需求提供实时的交互。

相关实践学习
阿里云图数据库GDB入门与应用
图数据库(Graph Database,简称GDB)是一种支持Property Graph图模型、用于处理高度连接数据查询与存储的实时、可靠的在线数据库服务。它支持Apache TinkerPop Gremlin查询语言,可以帮您快速构建基于高度连接的数据集的应用程序。GDB非常适合社交网络、欺诈检测、推荐引擎、实时图谱、网络/IT运营这类高度互连数据集的场景。 GDB由阿里云自主研发,具备如下优势: 标准图查询语言:支持属性图,高度兼容Gremlin图查询语言。 高度优化的自研引擎:高度优化的自研图计算层和存储层,云盘多副本保障数据超高可靠,支持ACID事务。 服务高可用:支持高可用实例,节点故障迅速转移,保障业务连续性。 易运维:提供备份恢复、自动升级、监控告警、故障切换等丰富的运维功能,大幅降低运维成本。 产品主页:https://www.aliyun.com/product/gdb
相关文章
|
23天前
|
存储 NoSQL 关系型数据库
面试题18: NOSQL数据库
面试题18: NOSQL数据库
|
28天前
|
存储 NoSQL API
一个小巧、快速、轻量级的 .NET NoSQL 嵌入式数据库
一个小巧、快速、轻量级的 .NET NoSQL 嵌入式数据库
|
27天前
|
多模数据库 Cloud Native NoSQL
Nosql学习之路:云原生多模数据库Lindorm训练营第一弹来啦
Lindorm训练营系列将通过一系列由浅入深的高质量课程和丰富的动手实验,将理论与实践结合,带你从入门到成为高阶开发者。参营学习还有机会获得惊喜彩蛋~
|
1月前
|
缓存 NoSQL MongoDB
在使用NoSQL数据库时,你遇到过哪些挑战?如何解决这些挑战?
在使用NoSQL数据库时,你遇到过哪些挑战?如何解决这些挑战?
20 0
|
1月前
|
存储 JSON NoSQL
请列举一些常见的NoSQL数据库类型和其特点。
请列举一些常见的NoSQL数据库类型和其特点。
25 0
|
1月前
|
存储 SQL NoSQL
NoSQL数据库的优点和缺点是什么?
NoSQL数据库的优点和缺点是什么?
32 0
|
1月前
|
存储 NoSQL 关系型数据库
什么是NoSQL数据库?它与传统关系型数据库有什么区别?
什么是NoSQL数据库?它与传统关系型数据库有什么区别?
22 0
|
1月前
|
存储 NoSQL 关系型数据库
【MySQL】为什么需要NOSQL数据库
`RDBMS`和`NOSQL`数据库的优缺点
|
2月前
|
NoSQL 安全 Java
基于内存的分布式NoSQL数据库Redis(六)AOF设计
基于内存的分布式NoSQL数据库Redis(六)AOF设计
156 0
|
2月前
|
存储 分布式计算 NoSQL
基于内存的分布式NoSQL数据库Redis(五)数据存储与RDB设计
基于内存的分布式NoSQL数据库Redis(五)数据存储与RDB设计
142 0

热门文章

最新文章