伸手黨福利-從零開始玩轉圖庫

名詞解釋

• vetex：節點
• edge：邊
• graph：圖

tinkerpop

tinkerpop是一個圖庫标準，一個架構，學習圖庫，先從這個項目入手比較合适, neo4j, janusGraph隻是它兩個元件（圖storage-engine）的vendor而已。圖庫是節點&邊的集合，邊描述了節點間的關聯關系。

tourist

打開gremlin-console，我們可以通過groovy語言對圖進行curd操作，也可以使用gremlin文法進行周遊

$ bin/gremlin.sh

         \,,,/
         (o o)
-----oOOo-(3)-oOOo-----
plugin activated: tinkerpop.server
plugin activated: tinkerpop.utilities
plugin activated: tinkerpop.tinkergraph
gremlin>           

tourist過程用到的資料庫，可視化展示如下：

tinkerpop提供了一個記憶體圖庫，并提供了上圖demo資料，加載資料

gremlin> graph = TinkerFactory.createModern()
==>tinkergraph[vertices:6 edges:6]
gremlin> g = graph.traversal()
==>graphtraversalsource[tinkergraph[vertices:6 edges:6], standard]
           

開始周遊

gremlin> g.V() //1
==>v[1]
==>v[2]
==>v[3]
==>v[4]
==>v[5]
==>v[6]
gremlin> g.V(1) //2
==>v[1]
gremlin> g.V(1).values('name') //3
==>marko
gremlin> g.V(1).outE('knows') //4
==>e[7][1-knows->2]
==>e[8][1-knows->4]
gremlin> g.V(1).outE('knows').inV().values('name') //5
==>vadas
==>josh
gremlin> g.V(1).out('knows').values('name') //6
==>vadas
==>josh
gremlin> g.V(1).out('knows').has('age', gt(30)).values('name') //7
==>josh
           

gremlin查詢文法就不在此贅述了，請查閱官網文檔

模型

tinkerpop3 模型核心概念

• Graph: 維護節點&邊的集合，提供通路底層資料庫功能，如事務功能
• Element: 維護屬性集合，和一個字元串label，表明這個element種類
• Vertex: 繼承自Element，維護了一組入度，出度的邊集合
• Edge: 繼承自Element，維護一組入度，出度vertex節點集合.
• Property: kv鍵值對
• VertexProperty: 節點的屬性，有一組健值對kv，還有額外的properties 集合。同時也繼承自element，必須有自己的id, label.

• Cardinality: 「single, list, set」

  節點屬性對應的value是單值，還是清單，或者set

記憶體圖庫（TinkerGraph）資料結構

首先必須明确tinkerpop自帶的記憶體圖庫（TinkerGraph）是全記憶體存儲，資料條目不會太多。資料結構也就是标準的圖的結構，持久化存儲方式可參考janusGraph圖庫方式

讓我們先了解Graph，vetex，Edge等資料結構

Graph

Graph成員變量，可以看到有vertices，edges兩個集合，分别管理節點，邊。

protected Map<Object, Vertex> vertices = new ConcurrentHashMap<>();
  protected Map<Object, Edge> edges = new ConcurrentHashMap<>();           

vertex

自身的成員變量有屬性，出度，入度的edge集合

protected Map<String, List<VertexProperty>> properties;
 protected Map<String, Set<Edge>> outEdges;
 protected Map<String, Set<Edge>> inEdges;
 private final TinkerGraph graph; //引用           

edge

一條邊有傳遞方向，成員變量有入度及出度的節點

protected Map<String, Property> properties;
protected final Vertex inVertex;
protected final Vertex outVertex;           

這樣就完成了圖的組織，可以看的出來從任意圖中的一個起始節點，可以先找到出度的邊，然後查詢邊的出度節點，這樣travesal就跳到了下一個節點，反複如此即可完成對圖的周遊。

highlevel-arch

1. gremlin server: httpserver/websocket server接收标準的gremlin dsl文法，自身相當于一個計算節點，完成圖的周遊，或者操作DML語言，操作底層OLTP圖庫。
2. gremlin traversal language: 圖的查詢周遊語言及語言解釋實作，類似sqlparser
3. provider strategies:vendor可自定義的政策，如對某些周遊步驟可優化，g.v("filter")可走全文搜尋，而非全表scan。
4. core api(api for OLTP) 圖庫的curd操作，包括traveral，追求低延時，高吞吐，盡量少的慢查詢。
5. graph computer(api for OLAP) 有MR/spark引擎，通過MR分治思想或DAG圖做一些大資料處理，充分利用多機計算能力,這個規範是可選實作，此篇我們不會過多讨論。

核心在于提供gremlin查詢文法及引擎，類似sqlparse,把查詢語言轉變成執行計劃。還有core-api 節點，邊的抽象，為底層OLTP&OLAP引擎可以自由切換成其他廠商實作，當然也内嵌了一套記憶體圖庫實作，以供vendor參考。

OLTP&OLAP

• OLTP: real-time, limited data accessed, random data access, sequential processing, querying
• OLAP: long running, entire data set accessed, sequential data access, parallel processing, batch processing

oltp vs olap

Graph Process

OLTP對于圖的寫操作都比較簡單，我們就不講了。我們來了解下traversal操作

GraphTraversal是由一組step組成，任何gremlin文法都會最終生成一個traversal，由多個步驟組成，如下示例

g.V(1).out("knows").values("name").iterate()
==>[TinkerGraphStep(vertex,[1]), VertexStep(OUT,[knows],vertex), PropertiesStep([name],value), NoneStep]
           

每個步驟都會變換上個步驟的輸出，像管道pipe一樣，抽像出以下5種變換方式，每個step其實都從這5種方式派生出來。

• map: transform the incoming traverser’s object to another object (S → E).
• flatMap: transform the incoming traverser’s object to an iterator of other objects (S → E*).
• filter: allow or disallow the traverser from proceeding to the next step (S → E ⊆ S).
• sideEffect: allow the traverser to proceed unchanged, but yield some computational sideEffect in the process (S ↬ S).
• branch: split the traverser and send each to an arbitrary location in the traversal (S → { S1 → E, …​, Sn → E } → E*).

圖示

The Traverser

gremlin> g.V(marko).out('knows').values('name')
==>vadas
==>josh
           

當開始執行traversal時，traversal的源在表達式的左邊（示例中的vertex1,marko節點）這些steps在traversal中間（示例種 out('knows')以及values('name')) 通過不斷執行"traversal.next"輸出到右邊的結果（示例中的'vadas'和'josh')

GraphTraversal inside

GraphTraversal通過了頂點，邊等提供了對圖資料的一種解釋，并是以提供圖形周遊DSL。S是起點，E是終點，包含如下4個主要元件

• Step: 獨立的函數用于應用S到生産E，在traversal内部steps是鍊式串起來的。
• TraversalStrategy: 方法攔截器，用于改變預設周遊執行
• TraversalSideEffects: 鍵值對方式儲存了traversal執行的全局資訊。

• Traverser: 代表了在目前周遊過程中資料流的一個狀态，維護了到目前對象的引用

  限于篇幅，更多内容查閱org.apache.tinkerpop.gremlin.process.traversal包對應的源碼

局限

• g.V(... ids) 或g.E(... ids) 指向性query，配合hbase使用沒問題，但g.V().has(filter） 可就是全表掃描了，避免該問題要配合全文搜尋引擎使用。 g.V()預設實作GraphStep會把vetex資訊拉倒目前程序，會dump圖庫所有節點資訊，操作重，條目過多很容易就OOM。
• DSL語言設計之初就沒有考慮過MPP體系，計算能力全壓在目前程序，架設成常駐程序很容易出現CPU打滿，QPS不足等問題。

janusGraph

tinkerpop自帶的圖庫基于記憶體，demo例子而已，我們看看其他一些供應商使用的一些持久化方案。

janusGraph內建了各大開源存儲系統，如hbase，Cassandra，BerkeleyDB，以及整合開源搜尋引擎，如solr, ElasticSearch. 總體來說實作了一個OLTP圖庫，OLAP标準在tinkerpop架構裡面是可選的，我們暫時不關心janusGraph在OLAP方面工作.因為我們生産環境隻使用hbase+solr，其他元件實作功能是鏡像的，重點分析hbase+solr模式就好了。

官方文檔所述優點

重點在強調scale-up

• Support for very large graphs. JanusGraph graphs scale with the number of machines in the cluster.
• Support for very many concurrent transactions and operational graph processing. JanusGraph’s transactional capacity scales with the number of machines in the cluster and answers complex traversal queries on huge graphs in milliseconds.
• Support for global graph analytics and batch graph processing through the Hadoop framework.
• Support for geo, numeric range, and full text search for vertices and edges on very large graphs.
• Native support for the popular property graph data model exposed by Apache TinkerPop.
• Native support for the graph traversal language Gremlin.
• Easy integration with the Gremlin Server for programming language agnostic connectivity.
• Numerous graph-level configurations provide knobs for tuning performance.
• Vertex-centric indices provide vertex-level querying to alleviate issues with the infamous super node problem.
• Provides an optimized disk representation to allow for efficient use of storage and speed of access.
• Open source under the liberal Apache 2 license.

我們關注下OLTP方面，主要有api層，實作tinkpop api，底層storage api，這些是跟hbase/solr等打交道的，比較重要的工作在于database邏輯層，包括事務， 資料管理（節點、邊curd），優化。

可以看出janusGraph功能還是比較少的，主要精力在資料模組化方面，事務實作方面，底層hbase，solr都不支援事務，是以在hbase+solr模式下不支援事務，這方面我們也可以略過

持久化模型

JanusGraph内部資料布局

JanusGraph将鄰接表按行row儲存在背景存儲中。使用64位的頂點Id作Key指向相應頂點的鄰接表row。每個邊或屬性在row中都是一個獨立的cell，并且這些cell可以高效的完成插入和删除。每行（row）可以存儲的cell最大數在hbase做存儲場景下沒限制，schema free随意新增列。

後端存儲hbase key全局有序儲存，指向性query/range query效率很高,key是vetex id，沒有字首比對場景。

單條邊的資料布局

每個邊或者屬性會儲存在頂點的鄰接表row的cell中。序列化之後的column資料位元組序也反映了原來的Edge标簽的key序。一個體系的ID編碼和壓縮的對象序列化易于使得每個cell保持盡可能少地占用後端存儲空間。

一條邊資訊會被出度、入度vetex保留兩遍，便于快速定位到鄰接節點，可避免表級聯查詢。

從目前節點拿到edge資訊，拿到鄰接vetex id，再做一次指向性query即可traversal到其他節點

問題

1. 并沒有實作事務，無論是hbase還是solr均不支援事務，janusGraph隻是号稱說支援事務。
2. 沒有發揮MPP思想，一個計算節點負責所有的圖周遊。存儲層hbase分布式化了，但自身計算節點并沒有分布式化。janusGraph把hbase當做黑盒，純用戶端，圖周遊拉取所有資料，沒有深入定制到表格存儲裡面，這也是可預見可修改的地方。
3. gremlin-server單機運算處理能力有限，勢必要水準擴充，但core包中使用了有很多cache,有狀态的，叢集模式下要考慮記憶體狀态一緻性問題

結束語-圖庫使用場景

推薦系統中，總有類似關聯推薦

如：使用者A喜歡某些item，推薦有相同興趣其他使用者所喜歡的item給使用者A，在圖庫裡面很容易實作。

/*"What has userA liked? Who else has liked those things? What have they liked that userA hasn't already liked?"*/

g.V(userA).out('liked').aggregate('x').in('liked').out('liked').
                where(without('x')).values('name')
           

在搜尋引擎中作為知識圖譜彌補自然語言處理的不足

衆所周知搜尋引擎使用全文搜尋的技術，本質上是term->document反向索引，如下query ”XX明星的老婆的弟弟的舅舅的兒子叫什麼“ 使用全文搜尋方式完全喪失了答案的正确性，使用圖資料庫輕而易舉能得到正确答案。另外edge提供權重屬性，能幫助搜尋引擎做rank打分。

g.V(star).out("wife").out("brother").out("uncle").out("son").values("name")           

在互金領域也可以有廣泛應用

比如在企業，法人/自然人的圖譜裡面，申請貸款，都需要做放貸風險評估，可以通過挖掘出一度人脈/關聯公司，如老婆或管轄的企業有沒有債務違約，有沒有”ppt造車，下周回國“類似事件，通過周遊圖譜，增加足夠的特征，很容易建立一個風控模型，給與借貸人合理的信用級别。

以上簡單舉了幾個圖庫在工業界能使用的上的例子。