《图数据库(第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
相关文章
|
13天前
|
SQL 存储 NoSQL
Redis6入门到实战------ 一、NoSQL数据库简介
这篇文章是关于NoSQL数据库的简介,讨论了技术发展、NoSQL数据库的概念、适用场景、不适用场景,以及常见的非关系型数据库。文章还提到了Web1.0到Web2.0时代的技术演进,以及解决CPU、内存和IO压力的方法,并对比了行式存储和列式存储数据库的特点。
Redis6入门到实战------ 一、NoSQL数据库简介
|
2月前
|
SQL NoSQL 数据库
Flutter Hive NoSql 数据库使用指南
本文将会写一个 Hive CURD 的例子,详细介绍 Hive 这个轻量级的 Flutter 离线数据库的使用方法,包括 Hive 在 Flutter 开发中的重要性、Hive 与 SQLite 的比较等,帮助开发者快速上手 Hive 数据库。
Flutter Hive NoSql 数据库使用指南
|
2月前
|
存储 SQL NoSQL
NoSQL数据库与传统关系型数据库的比较
【7月更文挑战第29天】NoSQL数据库与传统关系型数据库各有其独特的优势和适用场景。关系型数据库在复杂查询、事务处理和一致性方面表现出色,但在扩展性和处理大规模数据集时可能受到限制。而NoSQL数据库则以高扩展性、高性能和高可用性为目标,适用于处理大规模数据集和高并发读写场景。在选择数据库时,开发者应根据具体的应用场景和需求进行权衡和选择。
|
2月前
|
存储 SQL NoSQL
现代数据库技术:从关系型到NoSQL的演进与比较
随着信息技术的飞速发展,数据库技术也在不断演进和创新。本文将探讨现代数据库技术的发展历程,重点比较了传统的关系型数据库和新兴的NoSQL数据库,分析它们在不同场景下的优缺点及应用推荐。
|
2月前
|
SQL NoSQL 关系型数据库
现代数据库技术:从关系型到NoSQL的进化与应用
本文探讨了现代数据库技术的发展历程,从传统的关系型数据库到新兴的NoSQL数据库的演进过程。通过比较不同类型数据库的特点和应用场景,分析它们在各自领域中的优缺点及适用性,旨在帮助读者理解并选择合适的数据库技术来支持他们的应用需求。
|
2月前
|
缓存 NoSQL Java
使用Spring Boot和Couchbase实现NoSQL数据库
使用Spring Boot和Couchbase实现NoSQL数据库
|
2月前
|
监控 NoSQL 数据管理
电脑监控软件中的NoSQL数据库管理
这篇文章介绍了在电脑监控软件中使用NoSQL数据库管理非结构化数据。通过Python示例展示了如何使用MongoDB客户端连接数据库、插入单条或多条数据、查询数据(包括所有、特定用户和时间范围)、更新数据以及删除数据。此外,还提供了一个简单的数据监控和自动提交到网站的脚本,以每分钟检查一次新活动并发送到指定URL。这些示例有助于理解和优化监控软件中的数据处理。
62 3
|
2月前
|
NoSQL Java MongoDB
如何在Java中使用NoSQL数据库
如何在Java中使用NoSQL数据库
|
2月前
|
存储 NoSQL Java
使用MongoDB实现NoSQL数据库的最佳实践
使用MongoDB实现NoSQL数据库的最佳实践
|
3月前
|
存储 NoSQL Java
Spring Boot中如何整合Couchbase NoSQL数据库
Spring Boot中如何整合Couchbase NoSQL数据库

热门文章

最新文章

下一篇
云函数