Neo4j图数据库简介(从MySQL到graph database)



  • 1. DB简史

    1.1 MySQL时代

            上世纪90年代,大多数网页都是静态网页,动态交互网站不多,并且网站访问量一般不大,单个数据库就能满足后台需求,常用的网络数据库架构是APP → DAL(Data Access Layer数据访问层) → Mysql Instance。

    DAL 主要是对原始数据(数据库或者文本文件等存放数据的形式)的操作层,而不是指原始数据,也就是说,是对数据的操作,而不是数据库,具体为业务逻辑层或表示层提供数据服务。

    Imgur
    这一背景下会遇到的数据存储瓶颈是:

    1. 数据总量一个机器放不下时
    2. 数据的索引(B+ Tree)一个机器放不下时
    3. 访问量(读写混合)一个实例不能承受

    一旦出现了以上情况,就只能对数据库的整体架构进行重构。

    1.2 Memcached(缓存)+MySQL+垂直拆分

            随着后来网站访问量的上升,为了解决使用MySQL架构网站的性能问题,开始使用缓存技术环节数据库的压力,优化数据库的结构和索引。最开始比较流行的是通过文件缓存的方式来缓解数据库压力,但是访问量继续增大的时候,多台web服务机器之间的文件缓存不能共享,大量小文件缓存也会带来很大的IO压力。在这个时候 Memcached(一种分布式的高速缓存系统)就成为了一个非常时尚的技术产品。
    Imgur
    Memcached作为一个独立的分布式的缓存服务器,为多个web服务器提供了一个共享的高性能缓存服务,在Memcached服务器上,又发展了根据hash算法来进行多台Memcached缓存服务的扩展,然后又出现了一致性hash来解决增加或减少缓存服务器导致重新hash带来的大量缓存失效的弊端。

    memcached的API使用三十二比特的循环冗余校验(CRC-32)计算键值后,将数据分散在不同的机器上。当表格满了以后,接下来新增的数据会以LRU机制替换掉。由于memcached通常只是当作缓存系统使用,所以使用memcached的应用程序在写回较慢的系统时(像是后端的数据库)需要额外的代码更新memcached内的数据。

    1.3 MySQL主从读写分离

            由于数据库的写入压力增加,Memcached只能缓解数据库的读取压力。读写集中在一个数据库上让数据库不堪重负,大部分网站开始使用主从复制技术来达到读写分离,以提高读写性能和读库的可扩展性。Mysql 的 master-slave 模式成为这个时候的网站标配了。
    Imgur

    1.4 分库分表+水平拆分+mysql集群

            在Memcached的高速缓存,MySQL的主从复制,读写分离的基础之上,这时MySQL主库的写压力开始出现瓶颈,而数据量的持续猛增,由于MyISAM在写数据的时候会使用表锁,在高并发写数据的情况下会出现严重的锁问题,大量的高并发MySQL应用(在5.6版本之后)开始使用InnoDB引擎代替MyISAM。
    Imgur
    同时,开始流行使用分表分库来缓解写压力和数据增长的扩展问题。这个时候,分表分库成了一个热门技术,是面试的热门问题也是业界讨论的热门技术问题。也就在这个时候,MySQL推出了还不太稳定的表分区,这也给技术实力一般的公司带来了希望。虽然MySQL推出了MySQL Cluster集群,但性能也不能很好满足互联网的要求,只是在高可靠性上提供了非常大的保证。

    1.5 MySQL的扩展性瓶颈

            MySQL数据库也经常存储一些大文本字段,导致数据库表非常的大,在做数据库恢复的时候就导致非常的慢,不容易快速恢复数据库。比如1000万4KB大小的文本就接近40GB的大小,如果能把这些数据从MySQL省去,MySQL将变得非常的小。关系数据库很强大,但是它并不能很好的应付所有的应用场景。同时其扩展性差(需要复杂的技术来实现),大数据下IO压力大,表结构更改困难,正是当前使用MySQL的开发人员面临的问题。

    1.6 今天的MySQL架构

            用户的数据访问首先经过的是企业级防火墙,后面通过负载均衡主机(软负载:Nginx,硬负载:F5)在 web 服务器集群之间进行调度,再由具体的 web 服务器(Tomcat)去访问缓存,访问数据库。

    1.7 为什么用NoSQL

            今天我们可以通过第三方平台(如:Google,Facebook等)可以很容易的访问和抓取数据。用户的个人信息,社交网络,地理位置,用户生成的数据和用户操作日志已经成倍的增加。我们如果要对这些用户数据进行挖掘,那SQL数据库已经不适合这些应用了, NoSQL数据库的发展也却能很好的处理这些大的数据。

    2 关于NoSQL

    2.1 NoSQL简介

            NoSQL(NoSQL = Not Only SQL ),意即"不仅仅是SQL",泛指非关系型数据库。随着互联网web2.0网站的兴起,传统的关系数据库在应付web2.0网站,特别是超大规模和高并发的SNS类型的web2.0纯动态网站已经显得力不从心,暴露了很多难以克服的问题,而非关系型的数据库则由于其本身的特点得到了非常迅速的发展。NoSQL数据库的产生就是为了解决大规模数据集合多重数据种类带来的挑战,尤其是大数据应用难题,包括超大规模数据的存储。例如Google和Facebook每天会收集万亿比特的用户数据。这些类型的数据存储不需要固定的模式,无需多余操作就可以横向扩展。

    2.2 NoSQL代表

    MongoDB、Redis、Memcached

    3 关系型数据库与NoSQL的区别

    RDBMS

    • 高度组织化结构化的数据
    • 结构化查询语言(SQL)
    • 数据和关系都存储在单独的表中
    • 数据操纵语言,数据定义语言
    • 严格的一致性
    • 基础事务
    • ACID规则
      • A (Atomicity) 原子性
                原子性很容易理解,也就是说事务里的所有操作要么全部做完,要么都不做,事务成功的条件是事务里的所有操作都成功,只要有一个操作失败,整个事务就失败,需要回滚。比如银行转账,从A账户转100元至B账户,分为两个步骤:1)从A账户取100元;2)存入100元至B账户。这两步要么一起完成,要么一起不完成,如果只完成第一步,第二步失败,钱会莫名其妙少了100元。
      • C (Consistency) 一致性
                一致性也比较容易理解,也就是说数据库要一直处于一致的状态,事务的运行不会改变数据库原本的一致性约束。例如现有完整性约束a+b=10,如果一个事务改变了a,那么必须得改变b,使得事务结束后依然满足a+b=10,否则事务失败。
      • I (Isolation) 独立性
                所谓的独立性是指并发的事务之间不会互相影响,如果一个事务要访问的数据正在被另外一个事务修改,只要另外一个事务未提交,它所访问的数据就不受未提交事务的影响。比如现在有个交易是从A账户转100元至B账户,在这个交易还未完成的情况下,如果此时B查询自己的账户,是看不到新增加的100元的。
      • D (Durability) 持久性
                持久性是指一旦事务提交后,它所做的修改将会永久的保存在数据库上,即使出现宕机也不会丢失。

    NoSQL

    • 没有声明性查询语言
    • 没有预定义模式
    • 键-值对存储,列存储(HBase),文档存储(MongoDB),图数据库
    • 最终一致性而非ACID属性
    • 非结构化和不可预知的数据
    • 高性能,高可用性和可伸缩性
    • CAP定理
      • C (Consistency) 一致性 (所有节点在同一时间具有相同的数据)
      • A (Availability) 可用性 (保证每个请求不管成功或者失败都有响应)
      • P (Partition tolerance) 分区容错性/可靠性 (系统中任意信息的丢失或失败不会影响系统的继续运作)

    CAP理论的核心是:一个分布式系统不可能同时很好的满足一致性,可用性和分区容错性这三个需求,因此,根据CAP原理将NoSQL数据库分成了满足CA原则、满足CP原则和满足AP原则三大类:

    • CA - 单点集群,满足一致性,可用性的系统,通常在可扩展性上不太强大。(传统Oracle数据库)
    • CP - 满足一致性,分区容忍性的系统,通常性能不是特别高。(大多数网站架构)
    • AP - 满足可用性,分区容忍性的系统,通常可能对一致性要求低一些。(Redis、MongoDB)

    4 当下NoSQL的经典应用

            当下的应用是SQL与NoSQL一起使用的,例如阿里的商品信息存放以及去IOE化(I:IBM小型机,O:Oracle数据库,E:EMC存储设备)

    5 NoSQL在数据关系处理方面的局限性

            大多数的 NoSQL 数据库,无论是基于键-值对存储,文档存储或是列存储,都是存放的一些没有关联的文档/值/列,所以很难用来管理有联系的数据和图。目前在NoSQL中,一种比较流行的引入关系的策略是将一个数据集合中的标识符嵌入到另一个集合中,从而有效地引入外键。但是这就需要在应用层将数据集合整合,成本是难以估量的。
    Imgur
    在上图中,为了在用户(user)和订单(order)物品(item)之间建立关系,我们在用户数据集合中引入了order键,并且与对应的订单进行配对,同时订单数据集合中又引入了item键,与对应的商品进行配对。尽管这种策略表面上解决了不同数据集合之间建立关系的问题,但是大多数情况下这些"外来键"是以内嵌子图的形式关联到数据集合之中的,当关联关系复杂起来之后就不得不考虑在删改数据项的时候如何删除所有相关"外来键"的问题,否则就会产生严重的数据遗留,浪费数据库的存储资源。

    6 什么是图数据库

    6.1 技术背景

    整个图领域,所有要解决问题都能分为两大类:

    1. Technologies used primarily for transactional online graph persistence, typically accessed directly in real time from an application(在线处理)
    2. Technologies used primarily for offline graph analytics, typically performed as a series of batch steps(离线分析)

    另一种分类是从采用的技术上,3 种主要的图数据模型:

    1. property graph
    2. Resource Description Framework (RDF) triples
    3. hypergraphs

    目前市面上大多数图数据库都是基于 property graph 来做的。

    6.2 简介

            图数据库(Graph Database)是一种使用图结构进行语义查询的数据库,它使用 ++节点、边和属性++ 来表示和存储数据。GDB中存储区的数据项被分别对应到节点和边的集合中,边表示节点之间的关系,而节点和边都可以视为属性的容器。在图数据库中,节点与边的地位是对等的,这就意味着数据间的关系是直接被存储在数据库之中的,所以查询起来效率很高并且非常直观。所以GDB能很好地应用于数据高度互联的场合。
            图数据库是NoSQL的一部分,其创建目的也是为了解决传统关系数据库的局限性。传统关系数据库和其他NoSQL数据库中数据之间的关系是隐含连接的,而在图数据库中数据之间的关系则是显式连接的。图数据库与上世纪七十年代的网络数据库有相似之处,两者都是基于广义图,但是网络数据库仅仅是一种较低程度的抽象,并且不能很好地遍历一系列的边。
            图数据库的底层存储方式很多样。有的依赖于一个关系引擎并且将图数据"存储"在一张表中(虽然表只是一个逻辑元素,但是这也在图数据库、图数据库管理系统和用于存放数据的物理设备之间增加了另一层抽象)。除此以外还有键-值存储,或是面向文档的数据库,这就包含了一些NoSQL的固有元素。许多基于非关系存储引擎的数据库还会引入标签和属性的概念,其实质是文件之间存在相互指向的指针。
            SQL是专门为操作关系数据库而设计的,而关系数据库的逻辑是基于表的,所以SQL并不能"优雅地"处理图的遍历等操作,因而GDB就需要其他的查询语言来完成CRUD操作。目前在图数据库这一领域查询语言的规范还没有得到很好的统一,加上对于不同应用情景使用的图数据库不同程度地特化,这就衍生了许多不同的查询语言,例如GremlinSPARQLCypher等。除了查询语言接口之外,一些图数据库还有自己的API。

    7 关于Neo4j图数据库

    在划分不同的图数据库的时候,我们从两个技术点切入:

    1. The underlying storage
    2. The processing engine
      Imgur

    从图中我们可以看出Titan使用的不是native存储,后端可以使用

    • Apache Cassandra
    • Apache HBASE
    • Oracle BerkeleyDB

    而Neo4j则是使用的 native graph storage 和 native graph processing

    7.1 native graph process

            定义:如果一个图数据库的存储具有 index-free adjacency 属性,那么我们称其具有 native processing 属性。 index-free adjacency 指的是每个节点直接指向关联的节点,相当于每个节点都有一个自己的局部索引,这样相比起全局索引来说成本更低,处理速度更快。
            例如在传统关系数据库中,我们通过表格的形式来记录关系:
    image
    通过索引查找Alice的时间复杂度是 O(log n) ,而获得直接关系的时间复杂度是 O(1) ,因此检索 "Alice有哪些朋友" 的时间复杂度是 O(log n) ,而检索 "Alice是哪些人的朋友" 的时间复杂度是 O(m log n)
            而通过无索引邻接的方式就能够直接引入关系,从而规避索引查询:
    image
    在这种情况下,检索 "Alice有哪些朋友" 只需要追溯从 Alice 节点指向的节点,时间复杂度是 O(1) ;同样的,检索 "Alice是哪些人的朋友" 只需要追溯指向 Alice 节点的节点,时间复杂度也是 O(1)

    7.2 native graph storage

            index-free adjacency 是图数据库相比传统 MySQL 数据库更具优势的核心关键,因而图数据库用什么结构来实现 index-free adjacency 是设计的关键。
    image
    上图是Neo4j图数据库的架构,上层是对外访问的API,右边是事务管理,左边有cache等,我们要关注的是其在 disk 上的存储结构:
    Imgur

    Neo4j在磁盘上将节点(node),关系(realtionship)以及属性(property)分到不同的 store file 中

    • neostore.nodestore.db:存储 node
    • neostore.propertystore.db:存储属性
    • neostore.relationshipstore.db:存储关系

    其中,store中存储的 record 大小都是固定的,固定大小带来的好处是:给定id就能快速定位(类似邻接表),从而极大地提升查询效率。
    Imgur
    首先是 node record 的结构:

    • 1byte:in-use flag,表明该 node 是否在使用
    • 4byte:第一个 relation id
    • 4byte:第一个 property id
    • 5byte:label 信息(信息较少时可能直接内联存储)
    • 1byte:reversed

    接下来是 relationship record 的结构:

    • 1byte:in-use flag,表明该 node 是否在使用
    • 4byte:起始节点的id
    • 4byte:终止节点的id
    • 4byte:指向关系类型的指针(存放在 relationshiptypestore 中)
    • 4byte:指向起始节点上一条关系的指针
    • 4byte:指向起始节点下一条关系的指针
    • 4byte:指向终止节点上一条关系的指针
    • 4byte:指向终止节点下一条关系的指针
    • 4byte:is-the-first flag,表明是 关系链 中的第一条关系

    形象一点的存储关系图:
    Imgur
    一个可能的搜索过程是:对于给定的一个 node record,可以通过 id 进行简单的偏移计算得到 node,然后通过 relation_id 定位到 relation record,然后得到 end node id,通过偏移计算得到 node。

    7.3 双向存储

            在Neo4j中,所有的关系都是有方向的,当关系为单向的时候,一个节点作为 relationship 的起点,而另一个作为 relationship 的终点。而当关系为双向的时候,由于Neo4j中每个关系都有一个 start node 和一个 end node 以及它们所关联的双向链表,这个链表记录了从某节点引出的所有关系以及指向该节点的所有关系,这样就能保住总能从一个节点找到有关系的另一个节点,从而实现双向关系。
    例如一张关系图结构如下:
    Imgur
    其中A~E表示Node 的编号,R1~R7 表示 Relationship 编号,P1~P10 表示Property 的编号。

    对应的双向链表的示意图如下:
    Imgur

    上图中 B 节点的 prev 和 next 我们就能看到在这个链表中,B 有时候是 start node 有时候是 end node,我们总能在双向链表中遍历与B相关的所有节点。



  • 【手动置顶】补充一下,本篇文章是在前两篇关于Neo4j的学习之后出的总结篇,引用了很多图片,但是上传的图床是Imgur,所以可能要翻墙才能加载出来(之前没有发现团队的bbs能缓存图片所以就没用)



  • 其实关于关系数据库还有很多表述不是很准确的地方,或者是比较基本的知识没有介绍到,毕竟只是一时兴起就去研究了一下(而且后面时间不太够了就回去鼓捣VOSviewer了),所以欢迎大家在回复中补充相关的信息(我也想进一步了解一下)



  • 跟着师傅学习!


 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

Looks like your connection to Dian was lost, please wait while we try to reconnect.