作者介紹

馮錦明，拍拍貸高級(jí)數(shù)據(jù)工程專家。

傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)通過實(shí)體和關(guān)系來建模，在過去的很長(zhǎng)一段時(shí)間內(nèi)都占據(jù)著絕對(duì)的統(tǒng)治地位。但是隨著大數(shù)據(jù)的興起，它的一些缺陷也變得越來越明顯，特別是在需要處理非常復(fù)雜的實(shí)體關(guān)系時(shí)，關(guān)系型數(shù)據(jù)庫(kù)變得越來越力不從心。

當(dāng)我們要表示實(shí)體間的多對(duì)多關(guān)系時(shí)，一般會(huì)建立關(guān)系表。當(dāng)要看實(shí)體間的關(guān)系時(shí)，我們需要把這種關(guān)系再關(guān)聯(lián)起來。這通常是一項(xiàng)非常消耗性能的工作，特別是在關(guān)系非常復(fù)雜或者關(guān)系層次很多的情況下，需要關(guān)聯(lián)非常多的表，甚至產(chǎn)生非常巨大的中間結(jié)果，導(dǎo)致查詢非常緩慢甚至跑不出來。

圖數(shù)據(jù)庫(kù)以圖論為基礎(chǔ)，數(shù)據(jù)本身以圖的方式存儲(chǔ)(比如鄰接表)，在處理與圖相關(guān)的任務(wù)時(shí)占有先天的優(yōu)勢(shì)。所以目前在知識(shí)圖譜，社交網(wǎng)絡(luò)分析等領(lǐng)域開始有越來越多的應(yīng)用。

常見的圖形數(shù)據(jù)庫(kù)

以下是三個(gè)比較流行的圖數(shù)據(jù)庫(kù)及各自的特性對(duì)比。

經(jīng)過我們對(duì)比及試用的結(jié)果，OrientDB 和 Neo4j 使用比 Titan 都要簡(jiǎn)單，社區(qū)也更活躍。但是 Neo4j 最大的缺陷在于并非是真正的分布式，當(dāng)數(shù)據(jù)量超過單機(jī)的承載能力以后很難處理；而且 Neo4j 和OrientDB 的底層存儲(chǔ)都是自主研發(fā)，Titan 支持HBase/Cassandra 作為底層存儲(chǔ)，跟我們目前主要的數(shù)據(jù)平臺(tái) Hadoop 能很好集成在一起；此外，Titan 除了支持 OLTP 操作以外，還可以跟 Spark 結(jié)合進(jìn)行 OLAP 相關(guān)的分析。所以我們最終決定采用 Titan 。

Titan技術(shù)架構(gòu)

Titan 的總體技術(shù)架構(gòu)如上所示，存儲(chǔ)、索引、OLAP 的計(jì)算引擎都是開源的可選組件：

1. 底層存儲(chǔ)支持 HBase/Cassandra，所以存儲(chǔ)是可以平行擴(kuò)展的，幾乎沒有容量限制；

2. 支持 Elasticsearch/Solr/Lucene 作為外部的索引插件，實(shí)現(xiàn)在進(jìn)行非等值查詢時(shí)也能利用到索引；

3. Management API 負(fù)責(zé) Schema 的創(chuàng)建，修改，刪除及實(shí)例管理等操作；

4. 通過 Tinkerpop API提供圖上的操作接口；

5. Internal API、Database Layer、Storage and Index Interface Layer負(fù)責(zé)將 Tinkerpop 和Management API 的圖操作轉(zhuǎn)換成底層存儲(chǔ) Cassandra 和 HBase 上的操作(比如HBase 中的put、get、scan)。

6. GraphComputer 提供以 Spark/MR 的方式進(jìn)行圖上的 OLAP 操作，做子圖或者全圖上的分析(比如計(jì)算 Pagerank )。

Titan圖的表示

Titan用結(jié)點(diǎn)、邊和屬性三類信息來描述一個(gè)圖，如上圖所示。

結(jié)點(diǎn)(Vertex)：用于表示一個(gè)實(shí)體，結(jié)點(diǎn)通過指定不同的標(biāo)簽(LABEL)來區(qū)別具體的實(shí)體類型，如Titan、Location；結(jié)點(diǎn)由唯一的 Vertex ID 標(biāo)識(shí)，該ID由 Titan 自動(dòng)生成并管理。

邊(Edge)：用于描述實(shí)體之前的關(guān)系，有出結(jié)點(diǎn)和入結(jié)點(diǎn)；邊同樣有標(biāo)簽(LABEL)，用于區(qū)分邊的類型，如上圖所示的 father、lives；邊帶有方向；邊可以指定是否只允許單向查詢；邊可以指定 MULTILICITY，表示該 LABEL 的邊能存在幾條；邊也有唯一的 Edge ID，該ID由 Titan 自動(dòng)生成及管理。

屬性(property)：既可以在結(jié)點(diǎn)上，也可以在邊上，用于描述結(jié)點(diǎn)和邊的附加信息；屬性通過 PROPERTY KEY來表示該屬性是什么屬性，如上圖所示 name、age、place；屬性也可以指定 CARDILITY，用于表示該屬性可以存在多個(gè)該屬性；屬性也有唯一的 Property ID，該 ID由 Titan自動(dòng)生成及管理；對(duì)于結(jié)點(diǎn)和邊上的屬性都可以添加索引，這時(shí)通過屬性來查詢特定結(jié)點(diǎn)或者邊的時(shí)候，可以直接通過索引定位到對(duì)應(yīng)的結(jié)點(diǎn)或者邊的 ID，減少掃描的數(shù)據(jù)量，提升性能。

Titan的圖查詢

Titan通過 Tinkerpop 的 Gremlin 語言提供圖的查詢、修改等操作。一個(gè) Titan 實(shí)例對(duì)應(yīng)的就是 Tinkerpop 的一個(gè) Gremlin Server。多個(gè)對(duì)應(yīng)相同存儲(chǔ)后臺(tái)的 Gremlin Server 組成了 Titan 的分布集式集群。用戶可以通過 Gremlin Client 或者Restful API提交查詢請(qǐng)求。

查詢的例子如下：

#創(chuàng)建一個(gè)集群

gremlin> graph = TitanFactory.open('conf/titan-hbase.properties')

==>standardtitangraph[hbase:[titan003, titan004, titan005]]

gremlin> g = graph.traversal

==>graphtraversalsource[standardtitangraph[hbase:[titan003, titan004, titan005]], standard]

#查詢name為'saturn'的結(jié)點(diǎn)

gremlin> saturn = g.V.has('name', 'saturn').next

==>v[256]

#查看saturn結(jié)點(diǎn)有哪些屬性

gremlin> g.V(saturn).valueMap

==>[name:[saturn], age:[10000]]

#saturn的祖父的姓名

gremlin> g.V(saturn).in('father').in('father').values('name')

==>hercules

#查詢hercules的父母的信息

gremlin> g.V(hercules).out('father', 'mother')

==>v[1024]

==>v[1792]

gremlin> g.V(hercules).out('father', 'mother').values('name')

==>jupiter

==>alcmene

gremlin> g.V(hercules).out('father', 'mother').label

==>god

==>human

gremlin> hercules.label

==>demigod

Titan底層存儲(chǔ)格式

Titan 中的結(jié)點(diǎn)和邊按照鄰接表的方式組織，每個(gè)結(jié)點(diǎn)的鄰接表包含該結(jié)點(diǎn)的所有相鄰邊和該結(jié)點(diǎn)的屬性，存儲(chǔ)上遵循Big Table Data Model。

也就是說，表由多行組成，每一行由很多的Cell組成，每個(gè) Cell 由一個(gè)Column和Value組成。行由唯一的 Key 標(biāo)識(shí)，每個(gè) Cell 由 Key+column 標(biāo)識(shí)。

Titan Layout：

Edge & Property Layout：

如上圖所示，對(duì)于 Titan 的實(shí)現(xiàn)來說。每一行的 Key 就是結(jié)點(diǎn)的 Vertex ID，該 ID 是由 Titan自動(dòng)維護(hù)的一個(gè)64bit長(zhǎng)整型數(shù)。每個(gè) Cell 就是結(jié)點(diǎn)的屬性或者該結(jié)點(diǎn)相連的邊。

邊 Cell 的 Column 包含邊的方向,邊上指定的排序?qū)傩缘男畔?，鄰接點(diǎn)的ID, 邊的ID； 邊的 Value 包含邊上的所有屬性( Signature 屬性在前)。

屬性 Cell 的 Column 包含屬性的類型 ID ; Value 包含屬性的 ID 和屬性的值。

拍拍貸圖數(shù)據(jù)庫(kù)應(yīng)用

我們目前將用戶信息、設(shè)備信息及社交關(guān)系構(gòu)建了一個(gè)異構(gòu)網(wǎng)絡(luò)，并將該異構(gòu)網(wǎng)絡(luò)圖應(yīng)用在用戶關(guān)聯(lián)分析及反欺詐檢測(cè)場(chǎng)景。

傳統(tǒng)的方式上，我們的數(shù)據(jù)都是存儲(chǔ)在RDMS上，要查詢用戶的關(guān)聯(lián)關(guān)系時(shí)，都是通過關(guān)聯(lián)多張表來實(shí)現(xiàn)。但這種方式存在很多的問題：

1. 這些表相應(yīng)都較大，在做表關(guān)聯(lián)的時(shí)候效率非常低下；

2. 對(duì)于關(guān)系的層次支持非常有限，出入度很大的結(jié)點(diǎn)，產(chǎn)生的中間結(jié)果會(huì)非常大；

3. 對(duì)于圖上的查詢不夠靈活。

這些都極大地限制了我們分析能力和分析效率。出于以上這些痛點(diǎn)，我們引入了 Titan 圖形數(shù)據(jù)庫(kù)。每天會(huì)通過改寫的 Titan Bulkload 將10億+結(jié)點(diǎn)信息和500億+左右的關(guān)系數(shù)據(jù)導(dǎo)入Titan 后臺(tái) HBase 生成一張包含13類節(jié)點(diǎn)和15類邊的復(fù)雜異構(gòu)網(wǎng)絡(luò)。

通過該網(wǎng)絡(luò)，可以方便快速地回答以下類似問題：

• 和用戶A關(guān)聯(lián)的用戶有哪些；

• 和用戶A關(guān)聯(lián)的用戶有什么特征；

• 用戶A和用戶B怎么關(guān)聯(lián)在一起的。

下圖是我們將圖數(shù)據(jù)庫(kù)應(yīng)用于反欺詐中的示例圖：

根據(jù)原始的數(shù)據(jù)圖我們可以對(duì)用戶做以下調(diào)查分析，來確定特定的用戶是不是欺詐用戶或者是不是與欺詐用戶有關(guān)聯(lián)：

• 通過特定規(guī)則篩選可疑用戶

• 查看與可疑用戶有特定關(guān)聯(lián)的用戶

• 查看與可疑用戶有特定關(guān)聯(lián)的所有用戶組成的子網(wǎng)的網(wǎng)絡(luò)特征及用戶特征

• 分析特定用戶可以通過什么樣的關(guān)聯(lián)關(guān)系關(guān)聯(lián)在一起

• 最多可分析6層關(guān)聯(lián)關(guān)系的數(shù)據(jù)

通過該方式，我們大大減少了調(diào)查過程中的工作量，整體效率提升了25%+。