簡介

　　在眾多不同的數據模型里，關系數據模型自80年代就處于統治地位，而且有不少實現，如Oracle、MySQL和MSSQL，它們也被稱為關系數據庫管理系統（RDBMS）。然而，最近隨著關系數據庫使用案例的不斷增加，一些問題也暴露了出來，這主要是因為兩個原因：數據建模中的一些缺陷和問題，以及在大數據量和多服務器之上進行水平伸縮的限制。兩個趨勢讓這些問題引起了全球軟件社區的重視：

1. 用戶、系統和傳感器產生的數據量呈指數增長，其增長速度因大部分數據量集中在象Amazon、Google和其他云服務這樣的分布式系統上而進一步加快。
2. 數據內部依賴和復雜度的增加，這一問題因互聯網、Web2.0、社交網絡，以及對大量不同系統的數據源開放和標準化的訪問而加劇。

　　在應對這些趨勢時，關系數據庫產生了更多的問題。這導致大量解決這些問題某些特定方面的不同技術的出現，它們可以與現有RDBMS相互配合或代替它們-亦被稱為混合持久化（Polyglot Persistence）。數據庫替代品并不是新鮮事物，它們已經以對象數據庫（OODBMS）、層次數據庫（如LDAP）等形式存在很長時間了。但是，過去幾年間，出現了大量新項目，它們被統稱為NOSQL數據庫（NOSQL-databases）

本文旨在介紹圖形數據庫（Graph Database）在NOSQL運動里的地位，第二部分則是對Neo4j（一種基于Java的圖形數據庫）的簡介。

　　NOSQL環境

　　NOSQL（Not Only SQL，不限于SQL）是一類范圍非常廣泛的持久化解決方案，它們不遵循關系數據庫模型，也不使用SQL作為查詢語言。

　　簡單地講，NOSQL數據庫可以按照它們的數據模型分成4類：

1. 鍵-值存儲庫（Key-Value-stores）
2. BigTable實現（BigTable-implementations）
3. 文檔庫（Document-stores）
4. 圖形數據庫（Graph Database）

　　就Voldemort或Tokyo Cabinet這類鍵/值系統而言，最小的建模單元是鍵-值對。對BigTable的克隆品來講，最小建模單元則是包含不同個數屬性的元組，至于象CouchDB和MongoDB這樣的文檔庫，最小單元是文檔。圖形數據庫則干脆把整個數據集建模成一個大型稠密的網絡結構。

　　在此，讓我們深入檢閱NOSQL數據庫的兩個有意思的方面：伸縮性和復雜度。

　　1.伸縮性

　　CAP: ACID vs. BASE

　　為了保證數據完整性，大多數經典數據庫系統都是以事務為基礎的。這全方位保證了數據管理中數據的一致性。這些事務特性也被稱為ACID（A代表原子性、C表示一致性、I是隔離性、D則為持久性）。然而，ACID兼容系統的向外擴展已經表現為一個問題。在分布式系統中，高可用性不同方面之間產生的沖突沒有完全得到解決-亦稱CAP法則：

• 強一致性（C）：所有客戶端看到的數據是同一個版本，即使是數據集發生了更新-如利用兩階段提交協議（XA事務），和ACID，
• 高可用性（A）：所有客戶端總能找到所請求數據的至少一個版本，即使集群中某些機器已經宕機，
• 分區容忍性（P）：整個系統保持自己的特征，即使是被部署到不同服務器上的時候，這對客戶端來講是透明的。

　　CAP法則假定向外擴展的3個不同方面中只有兩個可以同時完全實現。

　　為了能處理大型分布式系統，讓我們深入了解所采用的不同CAP特征。

　　很多NOSQL數據庫首先已經放寬了對于一致性（C）的要求，以期得到更好的可用性（A）和分區容忍性（P）。這產生了被稱為BASE（基本（B）可用性（A）、軟狀態（S）、最終一致性（E））的系統。它們沒有經典意義上的事務，并且在數據模型上引入了約束，以支持更好的分區模式（如Dynamo系統等）。關于CAP、ACID和BASE的更深入討論可以在這篇介紹里找到。

　　2.復雜度

　　蛋白質同源網絡（Protein Homology Network），感謝Alex Adai：細胞和分子生物學院-德州大學

　　數據和系統的互聯性增加產生了一種無法用簡單明了或領域無關（domain-independent）方式進行伸縮和自動分區的稠密數據集，甚至連Todd Hoff也提到了這一問題。關于大型復雜數據集的可視化內容可以訪問可視化復雜度（Visual Complexity）。

　　關系模型

　　在把關系數據模型扔進故紙堆之前，我們不應該忘記關系數據庫系統成功的一個原因是遵照E.F. Codd的想法，關系數據模型通過規范化的手段原則上能夠建模任何數據結構且沒有信息冗余和丟失。建模完成之后，就可以使用SQL以一種非常強大的方式插入、修改和查詢數據。甚至有些數據庫，為了插入速度或針對不同使用情況（如OLTP、OLAP、Web應用或報表）的多維查詢（星形模式），對模式實現了優化。

　　這只是理論。然而在實踐中，RDBM遇到了前面提到的CAP問題的限制，以及由高性能查詢實現而產生的問題：聯結大量表、深度嵌套的SQL查詢。其他問題包括伸縮性、隨時間的模式演變，樹形結構的建模，半結構化數據，層級和網絡等。

　　關系模型也很難適應當前軟件開發的方法，如面向對象和動態語言，這被稱為對象-關系阻抗失配。由此，象Java的Hibernate這樣的ORM層被開發了出來，而且被應用到這種混合環境里。它們固然簡化了把對象模型映射到關系數據模型的任務，但是沒有優化查詢的性能。尤其是半結構化數據往往被建模成具有許多列的大型表，其中很多行的許多列是空的（稀疏表），這導致了拙劣的性能。甚至作為替代方法，把這些結構建模成大量的聯結表，也有問題。因為RDBMS中的聯結是一種非常昂貴的集合操作。

　　圖形是關系規范化的一種替代技術

　　看看領域模型在數據結構上的方案，有兩個主流學派- RDBMS采用的關系方法和圖-即網絡結構，如語義網用到的。

　　盡管圖結構在理論上甚至可以用RDBMS規范化，但由于關系數據庫的實現特點，對于象文件樹這樣的遞歸結構和象社交圖這樣的網絡結構有嚴重的查詢性能影響。網絡關系上的每次操作都會導致RDBMS上的一次"聯結"操作，以兩個表的主鍵集合間的集合操作來實現，這種操作不僅緩慢并且無法隨著這些表中元組數量的增加而伸縮。

　　屬性圖形（Property Graph）的基本術語

　　在圖的領域，并沒有一套被廣泛接受的術語，存在著很多不同類型的圖模型。但是，有人致力于創建一種屬性圖形模型（Property Graph Model），以期統一大多數不同的圖實現。按照該模型，屬性圖里信息的建模使用3種構造單元：

• 節點（即頂點）
• 關系（即邊）-具有方向和類型（標記和標向）
• 節點和關系上面的屬性（即特性）

　　更特殊的是，這個模型是一個被標記和標向的屬性多重圖（multigraph）。被標記的圖每條邊都有一個標簽，它被用來作為那條邊的類型。有向圖允許邊有一個固定的方向，從末或源節點到首或目標節點。屬性圖允許每個節點和邊有一組可變的屬性列表，其中的屬性是關聯某個名字的值，簡化了圖形結構。多重圖允許兩個節點之間存在多條邊。這意味著兩個節點可以由不同邊連接多次，即使兩條邊有相同的尾、頭和標記。

　　下圖顯示了一個被標記的小型屬性圖。

　　TinkerPop有關的小型人員圖

　　圖論的巨大用途被得到了認可，它跟不同領域的很多問題都有關聯。最常用的圖論算法包括各種類型的最短路徑計算、測地線（Geodesic Path）、集中度測量（如PageRank、特征向量集中度、親密度、關系度、HITS等）。然而，在很多情況下，這些算法的應用僅限制于研究，因為實際中沒有任何可用于產品環境下的高性能圖形數據庫實現。幸運的是，近些年情況有所改觀。有幾個項目已經被開發出來，而且目標直指24/7的產品環境：

• Neo4j -開源的Java屬性圖形模型
• AllegroGraph，閉源，RDF-QuadStore
• Sones -閉源，關注于.NET
• Virtuoso -閉源，關注于RDF
• HyergraphDB -開源的Java超圖模型
• Others like InfoGrid、Filament、FlockDB等。

　　下圖展示了在復雜度和伸縮性方面背景下的主要NOSQL分類的位置。

　　關于“規模擴展和復雜度擴展的比較”的更多內容，請閱讀Emil Eifrem的博文。

　　Neo4j -基于Java的圖形數據庫

　　Neo4j是一個用Java實現、完全兼容ACID的圖形數據庫。數據以一種針對圖形網絡進行過優化的格式保存在磁盤上。Neo4j的內核是一種極快的圖形引擎，具有數據庫產品期望的所有特性，如恢復、兩階段提交、符合XA等。自2003年起，Neo4j就已經被作為24/7的產品使用。該項目剛剛發布了1.0版 -關于伸縮性和社區測試的一個主要里程碑。通過聯機備份實現的高可用性和主從復制目前處于測試階段，預計在下一版本中發布。Neo4j既可作為無需任何管理開銷的內嵌數據庫使用；也可以作為單獨的服務器使用，在這種使用場景下，它提供了廣泛使用的REST接口，能夠方便地集成到基于PHP、.NET和JavaScript的環境里。但本文的重點主要在于討論Neo4j的直接使用。

開發者可以通過Java-API直接與圖形模型交互，這個API暴露了非常靈活的數據結構。至于象JRuby/Ruby、Scala、Python、Clojure等其他語言，社區也貢獻了優秀的綁定庫。Neo4j的典型數據特征：

• 數據結構不是必須的，甚至可以完全沒有，這可以簡化模式變更和延遲數據遷移。
• 可以方便建模常見的復雜領域數據集，如CMS里的訪問控制可被建模成細粒度的訪問控制表，類對象數據庫的用例、TripleStores以及其他例子。
• 典型使用的領域如語義網和RDF、LinkedData、GIS、基因分析、社交網絡數據建模、深度推薦算法以及其他領域。

　　甚至“傳統”RDBMS應用往往也會包含一些具有挑戰性、非常適合用圖來處理的數據集，如文件夾結構、產品配置、產品組裝和分類、媒體元數據、金融領域的語義交易和欺詐檢測等。

　　圍繞內核，Neo4j提供了一組可選的組件。其中有支持通過元模型構造圖形結構、SAIL -一種SparQL兼容的RDF TripleStore實現或一組公共圖形算法的實現。

　　要是你想將Neo4j作為單獨的服務器運行，還可以找到REST包裝器。這非常適合使用LAMP軟件搭建的架構。通過memcached、e-tag和基于Apache的緩存和Web層，REST甚至簡化了大規模讀負荷的伸縮。

　　高性能？

　　要給出確切的性能基準數據很難，因為它們跟底層的硬件、使用的數據集和其他因素關聯很大。自適應規模的Neo4j無需任何額外的工作便可以處理包含數十億節點、關系和屬性的圖。它的讀性能可以很輕松地實現每毫秒（大約每秒1-2百萬遍歷步驟）遍歷2000關系，這完全是事務性的，每個線程都有熱緩存。使用最短路徑計算，Neo4j在處理包含數千個節點的小型圖時，甚至比MySQL快1000倍，隨著圖規模的增加，差距也越來越大。

　　這其中的原因在于，在Neo4j里，圖遍歷執行的速度是常數，跟圖的規模大小無關。不象在RDBMS里常見的聯結操作那樣，這里不涉及降低性能的集合操作。Neo4j以一種延遲風格遍歷圖-節點和關系只有在結果迭代器需要訪問它們的時候才會被遍歷并返回，對于大規模深度遍歷而言，這極大地提高了性能。

　　寫速度跟文件系統的查找時間和硬件有很大關系。Ext3文件系統和SSD磁盤是不錯的組合，這會導致每秒大約100,000寫事務操作。

　　示例-黑客帝國

　　前面已經說過，社交網絡只是代表了圖形數據庫應用的冰山一角，但用它們來作為例子可以讓人很容易理解。為了闡述Neo4j的基本功能，下面這個小型圖來自黑客帝國這部電影。該圖是用Neo4j的Neoclipse產生的，該插件基于Eclipse RCP：

　　這個圖鏈接到一個已知的引用節點（id=0），這是為了方便的從一個已知起點找到條路進入這個網絡。這個節點不是必須的，但實踐證明它非常有用。

　　Java的實現看上去大概是這個樣子：

　　在“target/neo”目錄創建一個新的圖形數據庫

　　關系類型可以動態創建：

　　或通過類型安全的Java Enum：

　　現在，創建2個節點，給每個節點加上“name”屬性。接著，把兩個節點用一個“KNOWS”關系聯系起來：

　　任何修改圖或需要數據隔離級別的操作要包在事務中，這樣可以利用內置的回滾和恢復功能：

　　創建“黑客帝國”圖的完整代碼：

　　以及創建節點和關系的成員函數

　　誰是Neo的朋友？

　　Neo4j的API有一組面向Java集合的方法可輕易地完成查詢。這里，只消看看“Neo”節點的關系便足以找出他的朋友：

　　但是，Neo4j的真正威力源自Traverser-API的使用，它可以完成非常復雜的遍歷描述和過濾器。它由Traverser和ReturnableEvaluator組成，前者計算StopEvaluator來獲知何時停止，后者則用于在結果中包含哪些節點。此外，你還可以指定要遍歷關系的類型和方向。Traverser實現了Java的Iterator接口，負責延遲加載和遍歷整個圖，在節點被首次要求訪問（如for{...}循環）時進行。它還內置了一些常用的Evaluator和缺省值：

　　我們在繼續訪問更深一級的節點之前首先從起點訪問處于同一深度的所有節點（Order.BREADTH_FIRST），在深度為1的一次遍歷后停止（StopEvaluator.DEPTH_ONE），然后返回除了起點（"Neo"）之外的所有節點（ReturnableEvaluator.ALL_BUT_START_NODE）。我們在兩個方向只遍歷類型為KNOWS的關系。這個遍歷器再次返回Morpheus是Neo僅有的直接朋友。

　　朋友的朋友？

　　為了調查誰是Neo朋友的朋友，KNOWS網絡需要再進行深度為2的步驟，由Neo開始，返回Trinity和Cypher。實際編程中，這可以通過調整我們的Traverser的StopEvaluator，限制遍歷深度為2來實現：

　　還要定制ReturnableEvaluator，只返回在深度2找到的節點：

　　現在“朋友的朋友”遍歷器就成了：

　　它的結果是Cypher和Trinity。

　　誰在戀愛？

　　另一個有趣的問題是，這個圖上是否有人正在熱戀，比方說從架構師（Architect）開始。

　　這次，整個圖需要沿著由架構師（假定他的節點ID是已知的，但要到很晚才知道）開始的任何關系開始檢查，返回擁有向外LOVE關系的節點。一個定制的ReturnableEvaluator可以完成這件事：

　　為了遍歷所有關系，需要知道整個圖的所有關系類型：

　　上述代碼的返回結果只有一個節點：Trinity，因為我們只返回擁有向外LOVE關系的節點。

　　給圖建立索引

　　盡管沿著所有關系的遍歷操作是Neo4j的亮點之一，但也需要在整個圖之上進行面向集合的操作。所有節點屬性的全文檢索就是一個典型的例子。為了不重新發明輪子，Neo4j在這里使用了外部索引系統。針對常見的基于文本的搜索，Neo4j已經跟Lucene和Solr進行了深度集成，在Lucene/Solr里增加了給具有事務語義的任意節點屬性創建索引的功能。

　　在黑客帝國的例子里，如給“name”屬性創建索引：

　　Lucene是圖的外部索引的一個例子。但是，作為一個快速圖形引擎，有大量的策略來構建圖本身內部的索引結構，針對特殊數據集和領域縮短遍歷模式。例如，有針對一維數據的timeline和B樹，給二維數據（在空間和GIS社區非常普遍）建立索引的RTrees和QuadTrees等。另一個常見的有用模式是將重要的子圖直接連接到根節點，以創建重要開始節點的快捷路徑。

　　Java太麻煩了。拜托，有沒有簡短點的？

　　Neo4j甚至還提供了一組優秀的語言綁定來簡化圖結構操作。這個例子使用了優秀的Neo4j-JRuby-綁定，它極大地減少了整個代碼量：

　　先安裝neo4j gem

　　這時，整個黑客帝國的圖和前面提到的查詢，用JRuby代碼編寫就成了這個樣子：

　　圖編程語言- Gremlin

　　直到最近，還沒有任何查詢語言涉及大型的圖領域和圖相關項目。在語義網/RDF領域，有SPARQL，受SQL啟發的查詢語言，專注于描述用來匹配元組集合的樣本圖。但是，大量的圖并不兼容RDF，而且采用不同或更側重于更實用的方式進行數據建模，象本文中的黑客帝國例子，以及其他領域特定的數據集。其他查詢語言都是面向JSON的，如MQL，一種用于Freebase的查詢語言。這些語言只工作于它們自己定義的數據模型，完全不支持或只非常有限地支持深度圖算法和啟發式分析方法，而這又是當今大型圖里不可或缺的內容。

　　至于針對各種圖數據模型（如RDF）的更復雜有趣的查詢，Gremlin -一種面向XPath，圖靈完備的圖形編程語言-正由TinkerPop團隊開發，主要由Marko A. Rodriguez推動。借助引入屬性圖模型，它創造了一個針對現有大多數模型的超集，以及最小的公共操作集合。此外，它允許連接其他圖形框架（如Gremlin使用JUNG），同時支持在不同的圖實現上都能表達圖的遍歷。已支持的一組實現包括，從簡單的如內存中的TinkerGraph，到其他通過針對AllegroGraph、Sesame和ThinkerPop LinkedData SAIL（最開始由Josh Shinavier為Ripple編程語言開發）的RDF-SAIL適配器，一直到Neo4j。

　　Gremlin的語法建立在XPath基礎之上，這是為了可以簡單地表達整個圖的深度路徑描述。很多簡單的例子幾乎就像普通的XPath。

　　在安裝Gremlin或在線試用之后，黑客帝國例子里的圖的Gremlin會話大致是：

　　深度圖算法-關系的價值

　　鑒于Gremlin的能力，黑客帝國的例子顯得相當幼稚。更有趣的是開發和測試大型圖上的算法。象特征向量集中度和Dijkstra這類窮舉算法并不會擴展到這些圖上，因為它們需要了解網絡里的每個頂點。對于針對這些問題的如基于語法的隨機訪問器和擴散激活（Marko Rodriguez和這里有更深入的解釋）這類概念，啟發式方法更合適。　　Google PageRank算法就是啟發式的，而且可以用Gremlin建模，代碼如下（Greatful Dead的歌曲、演唱會和相冊圖的一個例子，圖從這里裝入，2500個循環，每次重復能量損失15%）：

　　它返回如下的歌曲權重列表：

　　其底層圖的另一個有趣的例子是LinkedData圖，在互聯網上可在線了解：LinkedData和DBPedia的音樂推薦算法。

　　總結

　　就像RDBMS和其他持久化解決方案一樣，圖不是解決所有問題的銀彈。數據才是最重要的東西，它是關鍵，然后是查詢類型、要處理的操作結構，以及什么需求要考慮伸縮性和CAP。

　　將采用NOSQL數據庫的高伸縮性方面作為使用非關系解決方案的唯一考量往往是不必要的，而且也不符合預期。使用Neo4j和當今的硬件，大多數情況下，完全可以在單實例里容納整個領域模型和查詢數十億領域對象。

　　如果那還不夠，總是有辦法引入針對領域優化過的數據分區概念，無需引入文檔或鍵/值系統的硬數據建模限制。最終導致的結果是一個文檔模型、或領域特定的“對象數據庫”還是其他模型則取決于領域上下文和應用場景。

　　本文的代碼可以從這里下載。

　　我要感謝Michael Hunger和Marko Rodriguez給我提供了優秀的反饋和有幫助的建議。

　　作者簡介

　　Peter Neubauer是Neo Technology的COO，他同時還是幾個基于Java和圖開源項目的合伙創辦人，如Neo4j、Gremlin、LinkedProcess、OPS4J、Qi4j。你可以通過peter@neotechnology.com.聯系到Peter。