设计师网站模版,网站推广公司排行榜,做自动采集电影网站有什么处罚,西安企业黄页网站在传统类型的数据库架构设计中#xff0c;通常不会单独介绍计算架构#xff0c;一切都围绕存储引擎展开#xff0c;毕竟存储架构是基础#xff0c;尤其是在传统的基于磁盘存储的数据库架构设计中。
类似地#xff0c;在图数据库架构设计中#xff0c;项目就围绕存储的方…在传统类型的数据库架构设计中通常不会单独介绍计算架构一切都围绕存储引擎展开毕竟存储架构是基础尤其是在传统的基于磁盘存储的数据库架构设计中。
类似地在图数据库架构设计中项目就围绕存储的方式来展开例如开源的Titan项目已停滞及其后续延展形成的开源的JanusGraph项目都是基于第三方NoSQL数据库的存储引擎而构建的可以说这些图数据库项目本身是在调用底层存储提供的接口来完成图计算请求。
老夫认为图数据库所要解决的核心问题并非存储而是计算。换句话说传统数据库包含NoSQL类数据库不能完成业务与技术挑战的主要原因是在面向关联数据的深度穿透与分析时的计算效率问题。尽管这些挑战与存储也相关但更多的是计算效率问题参考下图所示的存储与计算的分层加速逻辑。 图1数据库存储引擎的7层分层示意图 1、实时图计算系统架构
关于数据库计算架构的设计没有所谓的唯一正确答案。
但是在众多可选方案中笔者认为最为重要的是常识有时候也包含一些逆向思维。
1常识
·内存比外存快得多。
·CPU的三级缓存比内存快得多。
·数据缓存在内存中要比在外存上快得多。
·Java的内存管理很糟糕。
·链表数据结构的搜索时间复杂度是O(N)树状数据结构索引的搜索时间复杂度是O(log N)哈希数据结构的复杂度是O(1)。
2逆向思维
·SQL和RDBMS是世界上最好的组合——在过去30年中大抵如此但是业务场景的不断推陈出新决定了需要有新的架构来满足业务需求。互联网业务中通过大量的多实例并发来满足海量用户请求例如秒杀场景这些高并发的场景中处理模式都属于短链条交易模式和以金融行业为首的长链交易模式非常不同——两者之间的主要区别在于长链条交易的计算复杂度成倍增加对于分布式系统的设计挑战更大而短链交易中分布式系统的各节点间的通信或同步量小且逻辑简单故称短链条。
·庞大有如BAT类的大企业一定是图技术最强大的提供商——如果按照这个思路BAT恐怕不会在过去20年中从小不点成长到今天的巨无霸。每一次新的巨大的IT升级换代机遇出现时都会有一些小公司跑赢大盘。图2是一种实时图数据库的总体架构设计思路。 图2一种图数据库的架构横向数据流与纵向架构堆栈 实时图数据库的核心部件纵向具体如下
·图存储引擎数据持久化层 ·图计算引擎实时图计算与分析层 ·内部工作流、算法流管理及优化组件 ·数据库、数据仓库对接组件数据导入、导出 ·图查询语言解析器及优化器组件 ·图谱管理、可视化及其他上层管理组件。 图数据库的内部结构示意图如下图3所示 图3图数据库的功能组件和内部数据流 上图中我们用了三种颜色来标识图数据库中三种工作流
数据工作流橙色、管理工作流蓝色和计算工作流绿色。
数据工作流与管理工作流对于设计实现过软件定义的存储系统的读者应该感到不陌生在逻辑上它们代表数据传输与系统管理指令的分离可以看作是在两个分离的通道上传输图数据与管理指令。
而计算工作流则可以看作是一种特殊的图数据工作流它是与图计算引擎之间流转的数据与指令流。我们用具体的例子来说明计算工作流与数据工作流之间的差异。
图4与图5分别是两条实时路径查询指令返回结果的可视化呈现。它们之间的差异在于是否有点实体、边关系的属性被返回。在图4中是无点、边属性返回在图5中是全部属性被返回。图3-16的查询指令如下 图4路径搜索中无属性返回 上图的查询指令如下
// 五环路路径查询返回结果无属性字段
ab().src(12).dest(21).depth(5).limit(5).no_circle图5路径搜索中带全部或部分属性返回 上图的查询指令如下
//返回结果包含全部点、边的五环路路径搜索
ab().src(12),dest(21).depth(5).limit(5).no_circle().select(*)
以上两个路径查询语句都是查询两个顶点间深度为5的无环路径且限定找到5条路径即可返回区别在于后者要求返回全部顶点及边上的属性。这一语义层面对于底层的图计算与存储引擎的区别在于如果无属性返回那么图计算引擎可以完全以序列化ID来进行查询与计算这样做显然最节省内存也是性能最优的一种方案如果需要返回属性这个工作可以分给存储引擎来完成在存储持久层找到每个点、边的属性并返回。
因此在需要返回属性的查询语句中计算与存储引擎都被调动了而无属性返回的场景中存储引擎无须介入计算过程中。
当然存储引擎通过优化特别是缓存等功能的实现也可以在毫秒级至秒级时间内返回大量的属性数据尤其是多次查询时的加速效果明显。
然而问题的关键在于像上面这种深度的路径查询基于内存加速的计算引擎的效率会是传统存储引擎的成百上千倍微秒级并且随着查询深度的递增而产生的性能落差指数级增大。
2、图数据库模型与数据模型
图数据库普遍被认为采用的是模式自由schema-free或无模式schemaless的方式来处理数据也因此具备了更高的灵活性和应对动态变化数据的能力。这也是图数据库区别于传统关系型数据库的一个重要之处。
关系型数据库的模式描述并定义了数据库对象及对象相互间的关系起到了一种提纲挈领的作用下图6显示了19张表及其数据类型表之间通过主外键所形成的关联关系。
不过不同厂家的数据库对于模式的具体定义存在很大差异在MySQL中schema可以等同于数据库本身Oracle则把schema作为数据库的一部分甚至从属于每个用户而在SQL Server中创建模式后用户与对象等信息可以依附在其下。 图6关系型数据库的模式 关于关系型数据库和图数据库语言之间的区别详细可以参见这篇嬴图 | 微距观察从“表数据”到“图数据”的建模过程CSDN博客
关系型数据库中的模式的创建是前置的一旦创建并且数据库已经运行做出动态、灵活的改变是非常困难的。然而在图数据库中如何能提纲挈领地定义图数据对象及对象间关系的骨架这一挑战有两种不用思路的解方案一是无模式方案二是动态模式方案。
事实上还有第三种方案就是延续传统数据库的静态模式方案但这个和构建较传统数据库更为灵活的图数据库的目标相悖不过超出不在本篇文章中讨论了。
无模式顾名思义无须明确定义数据库对象间关系的模式或者说对象间的模式是不言而喻的或隐含但明确的。例如社交网络图谱中顶点间的关联关系默认都是关注或被关注关系这种简单图关系中并不需要模式定义介入。即便在更为复杂的关系网络中例如金融交易网络两个账户顶点间可能存在多笔转账关系多交易等于多边这种图属于多边图在同类型同构顶点间的多笔同类型边的存在也不需要定义模式来加以区分。
动态模式是相对静态模式而言的显然在上面的例子中如果有多种类型的顶点账户、商户、POS机、借记卡、信用卡等、多种类型的边转账、汇款、刷卡、还款等那么定义模式可以更清晰地描述对象及对象间的关系。如果图数据还是动态改变的例如新的类型的数据点、边出现后那么就需要动态定义新的模式或改变原有的模式来更灵活地描述和处理数据而不需要像传统数据库的静态模式定义一样需要停机、重启数据库等一系列复杂的操作。
图数据库因为不存在表、主键、外键等概念可以很大程度被简化为只包含以下组件
·节点也称为顶点对应的复数为nodes和vertices。
·边通常称为关系每条边通常连接一对顶点也有复杂的边模式会连接大于2个节点但非常罕见且混乱。为避免复杂化本书不处理此类情况。
·边的方向对于由边连接在一起的每对节点来说方向是有意义的。例如A→父亲是→B用户A→拥有账户→账号A。
·节点的属性每个节点相关的属性每个属性用一个键值对来表达例如参考书-与神对话符号前是主键的名称符号后是数值字符串。
·边的属性边的属性可能包括很多内容如关系类型、时间跨度、地理位置数据、描述信息以及装饰边的键值对等。
·模式在图数据库中模式的定义可以在图数据库对象创建后发生并且可以动态地调整每个模式所包含的对象。点、边可以分别定义各自的多组模式。
·索引及计算加速数据结构磁盘索引部分与传统数据库无二计算加速则是图数据库特有的创新这一部分与内存数据库有一些相似之处。
·标签标签可以被看作是一种特殊的属性某些图数据库采用标签的方式来模拟模式的效果但是两者之间存在较大的区别标签只能算作一种简化但功能不完整的类模式实现无法替代模式。
图数据库的数据源中所对应的数据类型如表1所示 表1典型图数据类型部分 3、核心引擎如何处理不同的数据类型
需要记住的一点是某些类型的数据对内存不友好以字符类型或唯一标识码UUID为例这些数据类型往往会在内存中膨胀如果不做处理数据蒸馏很快就会有内存不足的问题。
举个例子一张图有10亿个顶点、50亿条边每条边用最简单的形式记录包含2个顶点起点和终点如果使用唯一标识码UUID来代表每个顶点每个UUID是64B的字符串那么这张图最少占用内存的计算公式如下
64×2×5 000 000 000640 Billion Bytes640GB RAM
如果以无向图或双向图存储允许反向遍历那么就需要将每条边反转图遍历中的一种常见技术则使用UUID的内存消耗倍增为1 280GB而且这不包括任何边ID、点-边属性数据不考虑任何缓存、运行时动态内存需要等。
为了减少内存占用和提高性能我们需要做如下几件事。
·序列化把UUID类型的主键类数据转换为整型存储并在源数据与序列化数据间建立对照表例如Unordered Map或某种哈希映射表对照表的建立相当于为10亿顶点逐一分配整型ID即便使用8B长整型低至100G200GB的连续内存。数据结构就有可能覆盖全部UUID-ID的映射关系。
·近邻无索引使用适合的数据结构来实现最低算法复杂度的点-边-点遍历。读者可以参考前面介绍的近邻无索引数据结构设计来构建自己的高效、低延时图计算数据结构。 ·想办法使CPU饱和并让它们全速运行是每个高性能系统的终极目标因为内存仍然比CPU慢1000倍。当然这也与多线程代码如何组织和操作工作线程以尽可能高效地生产有关。这与所使用的数据结构密切相关——如果你在Java中使用过堆heap它一定不像映射或矢量那样的类型有效率列表和数组等也是一样。
另外一方面并非所有数据都应该直接加载到图核心计算引擎中这里要特别注意的是点、边属性的数量分别乘以点、边的个数结果可能远远大于点和边的数量。很多人喜欢用传统数据库的字段数量来统计图数据库的规模如10亿的点、50亿的边假设的点有20个属性字段边有10个属性字段它的字段规模10×2050×10700亿相当于千亿规模。很多所谓的千亿或万亿规模的图实际上可能远远小于真实的情况。
图计算的本质是对图的拓扑结构图的骨骼、骨架以及对必要的、有限的点、边属性进行查询、计算与分析。因此在大多数的图计算和查询过程中大量的点、边及属性与当前查询的内容无关。这也意味着它们在实时图计算的过程中没有必要占用宝贵的计算引擎资源也不需要在实时处理的路径之中。
为了更好地说明这些特点下面列举一些例子
·为了计算一个人朋友的朋友的朋友等同于图计算中的3跳3-Hop操作是一个典型的广度优先BFS查询操作。
·要了解2个人之间的所有4度以内关系是一种典型的AB路径查询BFS或DFS或两者兼而有之中间涉及非常多的节点可能是人、账户、地址、电话、社保号、IP地址、公司等。
·监管机构查看某企业高管的电话记录比如近30天内的来电与呼出电话以及这些来电者和接听者如何进一步打电话了解他们延展5步之内的通话网络并查询他们之间的通话关系网络。
这三个例子是典型的网络分析或反欺诈的场景并且查询深度以及复杂度逐级升高。不同的图系统会采用不同的方法来解决这一问题但关键是
·如何进行数据建模数据建模的优劣会影响作业的完成效率以及存储与计算资源的消耗程度甚至会制造出大量噪声这些噪声不仅会降低查询作业的完成速度还会使作业准确性难以保证。例如同构图、异构图、简单图、多边图不同的建模逻辑都可能会影响最终的查询效率。
逻辑都可能会影响最终的查询效率。
·如何尽可能快地完成工作只要成本可以接受实时返回结果总是更好的。
·性价比一直是考虑的因素如果相同的操作总要一遍又一遍运行那么为它创建一个专用的图表是有意义的。另外在数据并没有频繁更新的条件下缓存结果也可以达到同样的效果。
·如何优化查询这个工作是由图遍历优化器graph traversal optimizer来完成的。图遍历优化器有两种工作方式一是遍历所有的边后再进行过滤二是遍历的同时进行过滤。这两种遍历优化的核心区别如下
·在第一种方法中遍历是通过一个高度并发的多线程图引擎完成的先获得一张子图然后再根据过滤规则筛选并保留可能的路径集合。
·在第二种方法中过滤规则在图遍历过程中以动态剪枝的方式来实现一边遍历一边筛选。
·这两种方法在真实的业务场景中可能有很大的不同因为它会影响属性对于节点/边的处理方式。第二种方法要求属性与每个节点/边共存而第一种方法则可以允许属性单独存储。不同的图数据模型建模机制和不同的查询逻辑可能会让一种方法比另一种方法运行得更快。同时支持两种方法并同时运行两个实例通过比较可以帮助优化并找到图数据建模和模式的最合适方法。
不同的图数据模型建模机制和不同的查询逻辑可能会让一种方法比另一种方法运行得更快。同时支持两种方法并同时运行两个实例通过比较可以帮助优化并找到图数据建模和模式的最合适方法。
4、图计算引擎中的数据结构
在图数据库的存储引擎中可以按照行存储、列存储、KV存储三大类方式划分持久化存储方案。在图计算引擎层尽管我们渴望高维的计算模式但是数据结构层面依然分为两大类顶点数据结构和边数据结构。
注在一些图计算框架中因为点、边都没有属性可以只存在边数据结构而不需要顶点数据结构因为每条边都是由起点与终点构成的有序的一对整数已经隐含了顶点。
当然以上两种数据结构还分别包含点属性、边的方向、边的属性等字段。显而易见可能的数据结构方案有如下几种。
·点、边分开存储点、边及各自属性字段采用两套数据结构分别表达。
·点、边合并存储顶点数据结构包含边或边数据结构包含顶点。
·点、边及各自的属性字段分开存储可能用4套或更多的数据结构来表达。
下图给出的图数据结构是点、边及属性的“一体化”数据结构设计方案第一竖行是顶点而后面部分是起始顶点的属性以及边和边对应的属性。
这一数据存储模型非常类似谷歌的分布式存储系统big table。这类数据模型设计的优点如下 图7 点、边合并存储模式的图计算数据结构 ·对图遍历来说这是一种边优先edge-first的数据模型遍历速度高。
·数据模型可以用最合适的数据结构进行优化以获得最佳的遍历性能。
·它将使分区或分片更加容易。·这种数据结构对于持久化存储层也同样适用行存储模式。
缺点如下 ·使用连续存储内存空间的数据结构无法快速地更新删除数据。 ·如果使用对齐的字段边界不可避免地会导致空间浪费所谓空间换时间。 按照上图的思路延展开来大家可以自由发挥来设计更为高效的图计算数据结构。
未完结明天继续再聊。
