天天看點
傳回

主流圖資料庫Neo4J、ArangoDB、OrientDB綜合對比：架構分析

1： 本地存儲方式

2： 内置查詢語言分析

3： 性能分析

4： 圖算法支援

本地存儲方式

Neo4J

neo4j資料庫支援最大多少個節點？最大支援多少條邊？

  • 目前累積統計它有34.4億個節點，344億的關系，和6870億條屬性。

在資料庫中，讀/寫性能跟節點/邊的數量有關嗎？

  • 這個問題意味着兩個不同的問題。單次讀/寫操作不依賴資料庫的大小。不管資料庫是有10個節點還是有1千萬個都一樣。 — 然而，有一個事實是如果資料庫太大，你的記憶體可能無法完全緩存住它，是以，你需要頻繁的讀寫磁盤。雖然很多使用者沒有這樣大尺寸的資料庫，但有的人卻有。如果不巧你的資料庫達到了這個尺寸，你可以擴充到多台機器上以減輕緩存壓力。

是否有備份恢複機制？

  • Neo4j 企業版提供了一個線上備份（完整備份和增量備份）功能。

寫資料庫是線程安全的嗎？

  • 不管在單服務模式還是HA模式，資料庫在更新之前都通過鎖定節點和關系來保證線程安全。

檔案存儲結構

node，relationship，property存儲都是固定大小的。 如下圖：

  • 固定大小可以快速查找，基于此，可以直接計算一個節點的位置，時間複雜度$O(1)$，比查詢的$O(log n)$快。
主流圖資料庫Neo4J、ArangoDB、OrientDB綜合對比：架構分析

image.png

節點

存儲檔案

neostore.nodestore.db

，

  • 第一個位元組，是否被使用的Flag
  • 下4個位元組，代表第一個關系的ID，連接配接到這個節點上的 ：ID
  • 緊接着的4個字元，代表第一個屬性ID，連接配接到這個節點上的
  • 緊接着的5個字元是代表目前結點的Label，指向Label存儲的。 ：LABEL
  • 最後一個字元是标志字元，用來标志緊密相鄰的點，或者留備後用。 這就是Neo4J索引實作的方案。Index-Free Adjacency
這些指向的ID都是鍊式ID中的第一個，比如關系ID是關系鍊中的第一個。

關系

neostore.relationshipstore.db
  • 1：同上
  • 1-5：第一個節點
  • 5-9：第二個節點
  • 9-13：關系類型 ：TYPE
  • 13-21：前一個關系的前後節點 ID
  • 21-29：後一個關系的前後節點 ID
  • 29-33：屬性ID
  • 34：是都是關系鍊中的第一個的标志
關系是雙向連結清單，屬性是單向連結清單

屬性檔案

neostore.propertystore.db
  • 每個屬性檔案包含4個屬性塊，一個指向下個屬性的ID，在屬性鍊中
  • 屬性包括屬性類型，指向屬性索引檔案

    neostore.propertystore.db.index

     的指針
    • 屬性是鍵值對存儲的，資料類型可以使用JVM的所有私有屬性，加上字元串和數組類型；
    • 屬性值也可以使用動态存儲，就是大檔案，類型如下：字元串&數組

查找時檔案調用模型

主流圖資料庫Neo4J、ArangoDB、OrientDB綜合對比：架構分析
  • 節點包含指向關系鍊和屬性鍊的第一個指針。
  • 指向Label的指針，可能多個。
  • 屬性讀取從單向連結清單的第一個開始
  • 關系讀取直接在雙向連結清單中查找，直到找到想要的關系。

Index-Free Adjacency

查詢時，算法複雜度，$O(n)$，$n$是節點數，其他正常索引的複雜度都是$O(n log n)$

删除修改一個有很多很多邊的節點時會有點麻煩，因為沒有正常索引，隻能從關系鍊中開始删除。

  • 為了去除所有的事件邊，你必須通路每個相鄰的頂點，并且為每個相鄰的頂點執行一個潛在的昂貴的移除操作。

ArangoDB

文檔在ArangoDB中的存儲格式非常類似JSON，叫做

VelocyPack

格式的二進制格式存儲。

  • 文檔被組織在集合中。
  • 有兩種集合：文檔（V），邊集合（E）
  • 邊集合也是以文檔形式存儲，但包含兩個特殊的屬性

    _from

     和

    _to

     ，這兩個屬性被用來建立在文檔和文檔之間建立關系

存儲空間占用下：采用了中繼資料模式存儲資料

  • 可通過記憶體提速，CPU占有率低。

索引

索引類型

  • Primary Index

     ，預設索引，建立字段是

    _key

     或

    _id

     上，一個哈希索引

  • Edge Index

     ，預設索引，建立在

    _from

     、

    _to

     上，哈希索引；不能用于範圍查詢、排序，弱于OrientDB

  • Hash Index

     ，自建

  • Skiplist Index

     ，有序索引，
    • 用于快速查找具有特定屬性值的文檔，範圍查詢以及按索引排序順序傳回文檔。
    • 用于查找，範圍查詢和排序。補全範圍查詢的缺點。

Primary Index

Edge Index

 ，是記憶體索引，文檔加載速度很慢，推測是在重建索引。沒有見到ArangoDB說有記憶體索引持久化。

  • Persistent Index

    RocksDB

     的索引。
    • 持久性索引是具有持久性的排序索引。當存儲或更新文檔時，索引條目将寫入磁盤。
    • 使用持久性索引可能會減少集合加載時間。

  • Geo Index

     ，使用者可以在集合中的一個或多個屬性上建立其他地理索引。地理索引用于快速找到地球表面的地方。

  • Fulltext Index

     ，全文索引

Hash查詢很快，幾乎為$O(1)$。

Novel Hybrid Index

主流圖資料庫Neo4J、ArangoDB、OrientDB綜合對比：架構分析

把所有的邊都存儲在一個大哈希表中，把每個頂點V都放到一個雙連結清單中。

  • 将節點放傳入連結表中，周遊所有節點的複雜度時$O(k)$，k是節點總數。
    • 節點鄰接點是通過邊集确定的，邊集的起始點和結束點都是預設Hash索引的，是以查找一個節點的時間複雜度是$O(1)$。
  • 周遊邊的複雜度是$O(log E) + O(k)$，E是邊的數量。
    • 邊的周遊是通過周遊節點開始的。
    • 删除和修改邊的時候，是通過節點的

      key

       查找的，确認邊是不是節點的連結清單中的第一個，不是就通過連結清單繼續找。
    • 邊索引不僅是邊集的索引，也是頂點的鄰接點的索引。

存儲引擎

在ArangoDB 3.0 這個版本，arangodb切換了自己的存儲引擎，

RocksDB

。

Persistent indexes via RocksDB is the first step of ArangoDB to persist indexes in general.

在docker下這個版本的ArangoDB的接口沒有做好，挂在存儲卷時會導緻RocksDB IO異常。

架構變動很頻繁。3.2版本還會引入pregel架構。

  • 資料庫的Bug不但存在于本身還存在于其它引用的架構處。

OrientDB

  • SB-Tree Index：從其他索引類型中獲得的特性的良好組合，預設索引
  • Hash Index：
  • Auto Sharding Index：提供一個DHT實作；不支援範圍查詢
  • Lucene Spatial Index：持久化，支援事物，範圍查詢
在 Java中，如果哈希函數不合理，傳回值過于集中，會導緻大字典更慢。Java 由于存在連結清單和紅黑樹互換機制，搜尋時間呈對數級增長，而非線性增長。在理想的哈希函數下，無論字典多大，搜尋速度都是一樣快。

SB-Tree Index
  • UNIQUE：這些索引不允許重複的鍵。對于複合索引，這指的是組合鍵的惟一性。
  • NOTUNIQUE：這些索引允許重複的鍵。
  • FULLTEXT：這些索引是基于任何單個文本的。可以通過

    CONTAINSTEXT

     操作符在查詢中使用它們。
  • DICTIONARY：這些索引類似于使用惟一的索引，但是在重複鍵的情況下，它們用新的記錄替換現有的記錄。

Lucene Engine
  • FULLTEXT：這些索引使用Lucene引擎來索引字元串内容。可以在LUCENE操作符的查詢中使用它們。
  • SPATIAL：這些索引使用Lucene引擎來索引地理空間坐标。

SB索引

SB索引，B樹上優化了資料插入和範圍查詢，時間複雜度$O(log(N))$，其底數大約500。

  • 磁盤消耗大。

使用類似繼承的方式去實作包含特殊屬性的頂點集和邊集。

OrientDB本地存儲原則

OrientDB本地存儲原則：使用包含由固定大小部分（頁面）分割的磁盤資料并寫入日志記錄方法的磁盤緩存（當頁面中的更改首先記錄在所謂的持久存儲器中時），我們可以實作以下特性：OrientDB 2.2.x——PLocal Engine

  • Operations on single page are atomic.
  • Changes applied to the page can be restored after server crash even if they were not flushed to the disk.
保護資料
主流圖資料庫Neo4J、ArangoDB、OrientDB綜合對比：架構分析
叢集實作就是通過Class的類似繼承機制實作的分表。Clusters

内置查詢語言分析

AQL

arangod

與

arangosh

是用CPP寫的。

  • 網絡/磁盤IO處理也是通過CPP寫的
  • AQL執行器：CPP
  • AQL函數大部分是通過CPP寫的，少部分是通過JS寫的。
  • AQL調用的使用者函數全是JS函數

但，

arangod

arangosh

依賴V8 JS引擎

  • 所有的JS指令行進入

    arangosh

     都會被V8執行。

  • arangod

     JS孤島，

    --javascript.v8-contexts

     ，在多線程中用JS，但是JS本身還是單線程的。

類SQL語言，與ES6無縫連接配接，可以使用ES6文法。

  • JS的引入功能類似存儲過程，提供Foxx架構
  • 以V8作為語句執行引擎，性能有問題，而且導緻很多坑；
  • V8和Neo4J與OrientDB的JVM相比差距有點大，執行的性能感覺和Node.JS差不錯，适合事物密集型而不适合計算密集型的程式。
  • 個人認為，

    arangosh

     使用V8的目的是通過異步回掉調用本地cpp代碼提供計算性能，而不是使用V8去直接計算，是以在用各圖資料庫實作圖算法的時候如果使用JS去實作的話，性能會不是那麼的友善，對于ArangoDB值得期待的就是

    pregel

     将會在3.2版本面世。

Cypher

語義清晰，Neo4J唯一支援的語言

OrientDB SQL

類SQL，文法和SQL基本類似，冗長。

性能分析

少量資料分析

省

億級資料分析

arangoimp

插入效率感人，推測原因：

  • 導入方式是邊插入邊建立索引的，可能性不高，因為同一資料集在多台主機上嚴重了其卡住的位置是不同的
  • 其hash函數設定不好，導緻不停的哈希沖突，hash索引是arangodb的預設索引，可能性也不高；
  • 官網上有模糊的說明，arangodb的索引是存儲在記憶體中的，官網特意說明

    Persistent Index

     這個索引是存儲在磁盤上的，其他索引是需要在文檔加載時候重建立立索引的。

arangoimp

 在預設情況下到達1300萬資料之後導入性能很差。

在都沒有支援複雜圖算法的情況下，十萬級資料ArangoDB的圖計算效率比較低，因為是單線程JS在V8上運作的。

arangodb對于邊的插入不支援批量插入：

  • 在

    arangosh

     中已經驗證，其隻能一條邊一條邊的插入，後面的資料會被無視掉。

arangoimp

上存在無效參數：

  • 比如建立邊集選項，無論是否選擇是true，都不會建立，Github上官方解釋必須在資料庫中先建立邊集才可以，也就是說這個指令中的建立邊集的參數是一個無效參數。

neo4j-import

導入資料很快。

root@ubuntu:/var/lib/neo4j/data/databases# neo4j-import --into njaq --nodes /home/dawn/csv/perosnInfo.csv --relationships /home/dawn/csv/know.csv  --skip-bad-relationships true --skip-bad-entries-logging true --bad-tolerance true
WARNING: neo4j-import is deprecated and support for it will be removed in a future
version of Neo4j; please use neo4j-admin import instead.

Neo4j version: 3.2.1

Importing the contents of these files into njaq:

Nodes:

/home/dawn/csv/perosnInfo.csv

Relationships:

/home/dawn/csv/know.csv


Available resources:

Total machine memory: 3.84 GB

Free machine memory: 1.61 GB

Max heap memory : 875.00 MB

Processors: 4

Configured max memory: 700.35 MB


Nodes, started 2017-06-08 05:35:30.741+0000

[>:18.87 MB|NODE:152.59 MB----|PROPERTIES(3)============|LABEL SCAN--|v:37.14 MB/s-----------]20.0M ∆21.8K

Done in 51s 548ms

Prepare node index, started 2017-06-08 05:36:22.495+0000

[DETECT:419.62 MB----------------------------------------------------------------------------]20.0M ∆-6500000

Done in 9s 126ms

Relationships, started 2017-06-08 05:36:31.678+0000

[>:7|T|PREPARE(4)=========================================================|RE|CALCULATE-|P|v:]79.9M ∆10.9K

Done in 4m 17s 742ms

Relationship --> Relationship  1/1, started 2017-06-08 05:40:49.548+0000

[>-----------------------------------------------------------------------|LINK------------|v:]79.9M ∆ 405K

Done in 2m 5s 784ms

RelationshipGroup 1/1, started 2017-06-08 05:42:55.404+0000

[>:??----------------------------------------------------------------------------------------]    0 ∆    0

Done in 11ms

Node --> Relationship, started 2017-06-08 05:42:55.439+0000

[>:13|>-------------------------------------------------|LIN|v:26.00 MB/s--------------------]19.9M ∆2.18M

Done in 11s 833ms

Relationship <-- Relationship 1/1, started 2017-06-08 05:43:07.308+0000

[>-------------------------------------------------------------------------------|LINK----|v:]79.9M ∆ 168K

Done in 11m 29s 787ms

Count groups, started 2017-06-08 05:54:37.570+0000

[>:??----------------------------------------------------------------------------------------]    0 ∆    0

Done in 1ms

Gather, started 2017-06-08 05:54:38.061+0000

[>:??----------------------------------------------------------------------------------------]    0 ∆    0

Done in 4ms

Write, started 2017-06-08 05:54:38.156+0000

[>:??----------------------------------------------------------------------------------------]    0 ∆    0

Done in 15ms

Node --> Group, started 2017-06-08 05:54:38.213+0000

[>:??----------------------------------------------------------------------------------------]    0 ∆    0

Done in

Node counts, started 2017-06-08 05:54:38.264+0000

[>(4)==============================|COU]20.0M ∆80.0K

Done in 1m 26s 338ms

Relationship counts, started 2017-06-08 05:56:04.625+0000

[*>(4)|COUNT----------------------------]80.0M ∆1.81M

Done in 2m 47s 277ms

              IMPORT DONE in 23m 22s 420ms.

Imported:

20000000 nodes

79994052 relationships

80000000 properties

Peak memory usage: 899.62 MB
Neo4J使用導入方法之後會建立索引，否則基本沒有性能，建立索引很快。

圖算法支援

ArangoDB圖算法支援

    1. 周遊：從指定開始點，通過一定算法、邊類型、圖類型、深度擷取與指定開始點相關連通的點。
      1. 資料源：圖、邊集合
      2. 邊方向：出邊、入邊、全部
      3. 周遊方式：BFS Or DFS
    2. 最短路徑：兩點最短路徑，選項基本和上面類型
  2. Pregel

    1. @arangodb/pregel

       檔案夾下，很多分布式的圖算法
    2. PageRank
    3. CC 強弱連通算法
    4. 單源最短路徑算法

JS擴充

  • 通過JS可以完成對内置算法的擴充，但是自定義方法是單線程JS函數，如果用來做算法，性能堪憂，最佳選擇就是選擇内置的方法去實作圖算法。
  • 通過JS可以實作很多算法，但是在ArangoSH下代碼單線程運作，雖然arangod的JS是在多線程中運作的，但是arangosh是在單線程中運作的，且JS本身并不擅長處理計算型代碼，相比之下通過内置的資料庫語言而不是這種内置語言與JS混雜方式的代碼會快很多；比如Neo4J，OrientDB的查詢語言。

對于普通的周遊最短路徑算法支援和ArangoDB一樣都支援，但Neo4J的圖的周遊深度的門檻值設定比較難，且深度超過6算法會效率比較低。

相比之下，ArangoDB的算法參數設定全部依賴于Key-Value實作，算法在編碼層次靈活性很高。

對于PageRank，CC等算法的實作，Neo4J提供兩種方式：

  • 編寫Jar包，GitHub上有個未被官方承認的Jar包
  • Cypher直接實作

同上，圖算法也支援Jar包導入。

内置圖算法

最短路徑

Cypher:

match (p1:person{no:'%s'}),(p2:person{no:'%s'}) match p=shortestPath((p1)-[*..3]->(p2)) return p

OrientDB SQL:

select dijkstra((select @RID from persons where no='%s'),(select @RID from persons where no='%s'),'E')

AQL:

for v,e in outbound shortest_path '%s' to '%s' graph 'graphPersons' return [v._key,e._key]

鄰接點 

MATCH (js:person)-[:know]-(surfer) WHERE js.no = '%s' return surfer
           
select from E where out = (select @RID from persons where no='%s
           
traversal_results = graphPersons.traverse(
      start_vertex='persons/'+getSingleInfo(id).no,
      strategy='bfs',
      direction='outbound',
      edge_uniqueness='global',
      vertex_uniqueness='global',
      max_depth=1
  )

參考資料

  • 附錄 B. 常見問題_Neo4J最新版本
  • ArangoDB 3.0 – A Solid Ground to Scale
  • OrientDB calculate PageRank

原文位址：https://www.jianshu.com/p/6cab7a150755

java經驗集錦 通用實踐 db sql Oracle mysql neo4j 圖庫 NoSQL
上一篇: mysql常見的hint
下一篇: 使用MHA實作MySQL主從複制高可用

繼續閱讀