事務(wù)深度遍歷過程詳解 - 全文

事務(wù)

創(chuàng)建事務(wù)：

想顯式地回滾一個事務(wù)，例如從一個條件代碼塊，可以調(diào)用failure方法，則事務(wù)將在程序塊的結(jié)束做無條件的回滾。既不調(diào)用success方法也不調(diào)用failure方法也將會導(dǎo)致事務(wù)回滾（默認(rèn)）。

在一個事務(wù)中定義USER標(biāo)簽的name作為模式可索引的屬性，然后使用分離的事務(wù)實際設(shè)置一個真實用戶的值：

許多數(shù)據(jù)庫管理系統(tǒng)使用鎖機(jī)制來管理對同一個數(shù)據(jù)庫的同時訪問。Neo4j 事務(wù)是由清晰的讀鎖和寫鎖來控制每一個圖形數(shù)據(jù)庫資源（節(jié)點和關(guān)系）。

多個讀鎖之間并不相互排斥，在同一時間的多線程中，可以在同一數(shù)據(jù)資源中獲得多個讀鎖。在給定的時刻，對同一數(shù)據(jù)資源只能獲得一個寫鎖，還必須沒有其他激活的鎖，不管是讀鎖還是寫鎖。

Neo4j事務(wù)的默認(rèn)設(shè)置并不自動獲取讀鎖。因此，讀的數(shù)據(jù)是節(jié)點、關(guān)系、索引實體最新提交的狀態(tài)，除非在它自己的事務(wù)中，局域的修改（即使沒提交）是可見的。

寫鎖則是在對任意圖形資源試圖做變更操作時自動獲得，在事務(wù)的持續(xù)時 間內(nèi)都有效。每一個事務(wù)確保在完成時自動釋放所有的鎖。

如果需要一個更高級別的隔離以確保其他人不能修改正在讀的圖形資源， Neo4j提供了一個潛在的顯式獲取對圖形資源的讀鎖。程序7-5給出了相應(yīng) 代碼，但是這一次在讀取任何的屬性之前有一個額外的顯式請求獲取對節(jié)點的讀鎖。

當(dāng)讀數(shù)據(jù)時，有兩個很好的理由避免使用系統(tǒng)的鎖。就像以前提及的，首先這將產(chǎn)生事務(wù)的狀態(tài)，并且很占內(nèi)存。第二，這里主要的權(quán)衡是同時寫數(shù)據(jù)，因為線程希望更新任何有顯式讀鎖的節(jié)點或關(guān)系，在鎖被釋放或事務(wù)完成前是鎖定的。

如果事務(wù)A試圖按節(jié)點1和節(jié)點2的順序鎖定它們，而事務(wù)B試圖對相同的節(jié)點按相反的順序獲取鎖，那么每一個事務(wù)可能會鎖定一個節(jié)點并且無限期地等待另一個節(jié)點釋放，從而產(chǎn)生一個無效鎖。

當(dāng)無效鎖發(fā)生的時候，Neo4j具有一個內(nèi)置的機(jī)制對其進(jìn)行探測，若有，則 拋出一個DeadlockDetectedException異常并且事務(wù)回滾。當(dāng)鎖定是由Neo4j專門管理時，才能進(jìn)行無效鎖的探測，這意味著通過依賴于Neo4j的自動默認(rèn)鎖定機(jī)制，或者僅僅通過使用我們前面討論過的Neo4j API的相關(guān)鎖定方法（acquireReadLock和acquireWriteLock）。如果使用任何其他的鎖定機(jī)制，例如使用Java的同步（synchronized）關(guān)鍵詞，即使發(fā)生 無效鎖也不會被探測出，應(yīng)用程序很有可能出現(xiàn)終止。

要有效處理無效鎖：第一個堅持使用Neo4j提供的核心API而不使用任何外部的鎖定機(jī)制。這將確保Neo4j的無效鎖探測機(jī)制是有效的，確保你的應(yīng)用程序不會完全鎖死，并且數(shù)據(jù)會保持一致性。在Neo4j核心API中的所有操作（除非另有指定）都是線程安全的，因此，一般不需要外部的同步。另一個是通過確保圖形資源能夠以同樣的順序進(jìn)行訪問來避免無效鎖。

深度遍歷

① 遍歷的順序

每一次遍歷器訪問一個節(jié)點，它都需要決定下一步沿著哪個關(guān)系訪問哪個節(jié)點，重復(fù)這個過程直至遍歷結(jié)束。通過在圖形中選擇一個合適的路徑，遍歷可以很快結(jié)束并且使用很少內(nèi)存。這是圖論中的兩個主要順序算法，并且這兩個算法用于大多數(shù)的Neo4j遍歷中：深度優(yōu)先（depth-first）算法和廣度優(yōu)先（breadth-first）算法。

深度優(yōu)先：

深度優(yōu)先順序表明你應(yīng)該首先跳到現(xiàn)在所在且以前沒有訪問過的節(jié)點的第一級子 節(jié)點。如果所有的下一代子節(jié)點都已經(jīng)訪問過，就應(yīng)該返回具有沒有訪問過的子節(jié)點的第一個節(jié)點上。

使用Neo4j遍歷API深度優(yōu)先遍歷整個圖形：

深度優(yōu)先是Neo4j默認(rèn)的分支順序策略。當(dāng)建立遍歷描述時，如果不指定遍歷的順序，則默認(rèn)為深度優(yōu)先。

廣度優(yōu)先：

作為廣度優(yōu)先算法的一部分，遍歷在訪問子節(jié)點之前將首先訪問當(dāng)前節(jié)點的所有同級節(jié)點。同級在這里是指從根節(jié)點開始與你正在訪問的具有相同距離的節(jié)點。

1→2→3→4→5→6→7→8→9

在廣度優(yōu)先遍歷中，離根節(jié)點越近的節(jié)點訪問得越早，將遠(yuǎn)離根節(jié)點的節(jié)點放在后面 訪問。

使用Neo4j遍歷API的廣度優(yōu)先遍歷：

深度優(yōu)先與廣度優(yōu)先的比較：

圖形越大，遍歷順序?qū)Ρ闅v性能的影響就越大。當(dāng)結(jié)果節(jié)點靠近起始節(jié)點時，廣度優(yōu)先排序一般會給出較好的性能。但是遠(yuǎn)離起始節(jié)點時，廣度優(yōu)先排序總是比較慢，而深度優(yōu)先排序可能非常高效，取決于結(jié)果節(jié)點是在圖形的左邊還是右邊。

在最壞的情況下，是整個圖形都需要遍歷（當(dāng)結(jié)果節(jié)點在圖形的右下角時），深度優(yōu)先和廣度優(yōu)先都需要訪問所有的節(jié)點。由于廣度優(yōu)先遍歷需要更大的內(nèi)存記憶遍歷的足跡，這種情況下最好使用深度優(yōu)先。

除速度之外，當(dāng)決定遍歷的順序時，另一個需要考慮的方面是遍歷的內(nèi)存消耗。遍歷 時必須記住一些狀態(tài)，從哪個節(jié)點來，哪個節(jié)點已經(jīng)訪問過。圖形越大，存儲這個狀態(tài)需要的內(nèi)存就越多。

當(dāng)使用深度優(yōu)先時，你試圖用最快的速度深入到圖形。一旦你到了圖形的最底層（訪 問了一個以前沒有訪問過的且沒有子節(jié)點的節(jié)點），你就可以完全忘掉圖形的這個分支——從遍歷的角度，可以認(rèn)為已完成。

廣度優(yōu)先遍歷在開始下一深度的節(jié)點之前，試圖在圖形中走得盡可能廣。因此，在遍歷期間，需要記住所有訪問過的節(jié)點和哪一個子節(jié)點還沒有訪問。圖形越大越復(fù)雜，需要記住的節(jié)點就越多，會導(dǎo)致一個巨大的內(nèi)存占用。

一般來講，每一個節(jié)點的關(guān)系越多，廣度優(yōu)先需要的內(nèi)存就越多。

如果結(jié)果靠近起始節(jié)點，廣度優(yōu)先順序可能會更好。但是，如果圖形非常密（即每一個節(jié)點有許多關(guān)系），則廣度優(yōu)先順序在實際中可能會使用太多的內(nèi)存。

② 路徑擴(kuò)展器

擴(kuò)展器是Neo4j遍歷API的一個部件，負(fù)責(zé)決定遍歷期間訪問過的任意節(jié)點應(yīng)該跟蹤哪個關(guān)系。除選擇關(guān)系類型和訪向外，擴(kuò)展器還負(fù)責(zé)跟蹤關(guān)系的順序。

③ 管理唯一性

NODE_GLOBAL唯一性

Neo4j遍歷中最典型的唯一性設(shè)置是NODE_GLOBAL。它基本上意味著每一個節(jié)點只能訪問一次并且在遍歷期間只能訪問一次。NODE_GLOBAL是默認(rèn)的遍歷設(shè)置，因此，如果你不指定唯一性，這樣的設(shè)置會在你的遍歷中使用。

NODE_PATH唯一性

NODE_PATH唯一性設(shè)置指定了從起始節(jié)點到當(dāng)前節(jié)點，沒有路徑可以被遍歷兩次。多次訪問同一個節(jié)點是允許的，但只有它們屬于不同的路徑才可以。

RELATIONSHIP_GLOBAL唯一性

聲明圖形中的每一個關(guān)系只能被訪問一次。如果圖形中節(jié)點之間具有多個關(guān)系，每一個節(jié)點的訪問次數(shù)是連接該節(jié)點的關(guān)系數(shù)。

RELATIONSHIP_PATH唯一性

與NODE_PATH唯一性相似，其中的關(guān)系能被多次訪問，只要從起始節(jié)點到當(dāng)前節(jié)點之間的關(guān)系組合是唯一的。這種唯一性設(shè)置也可以使節(jié)點被多次訪問。

當(dāng)設(shè)置NODE_GLOBAL唯一性或者RELATIONSHIP_GLOBAL唯一性時，遍歷可能耗盡內(nèi)存，尤其是在有很多連接的大型圖形數(shù)據(jù)庫中。由于唯一性的限制原因，每一個節(jié)點（在NODE_GLOBAL唯一性的情況下）或關(guān)系（在RELATIONSHIP_GLOBAL唯一性的情況下）都必須記憶。這里NODE_RECENT和RELATIONSHIP_RECENT設(shè)置開始起作用。當(dāng)使用這些設(shè)置時，唯一性的限制稍微可以放寬。

對于NODE_RECENT，記憶訪問過的節(jié)點有一個上限數(shù)。這個規(guī)則對 RELATIONSHIP_GLOBAL也是一樣的，即一個節(jié)點只能訪問一次，但是只是最近訪問的節(jié)點集合才被記憶用于比較。最近訪問需要記憶的節(jié)點能夠以第二個參數(shù)傳遞給唯一性方法

·NODE_LEVEL　確保處于同一級的節(jié)點（從起始節(jié)點開始具有相同距離的節(jié)點）在遍歷期間只被訪問一次。

·RELATIONSHIP_LEVEL　確保處于同一級的關(guān)系（從起始節(jié)點開始具有相同距離 的關(guān)系）在遍歷期間只被訪問一次。

④ 雙向遍歷

在一個大型圖形上做一個標(biāo)準(zhǔn)單向遍歷可能會有低于最佳的性能。在這種情況下通過使用雙向遍歷，有效地利用了兩個遍歷去遍歷圖形，把問題的尺度降低了一半。對于經(jīng)典的單向遍歷，遍歷的關(guān)系數(shù)量隨著遍歷的深度成指數(shù)增長。當(dāng)使用雙向遍歷時，每一側(cè)的遍歷將只需要訪問一半的圖形深度，做較少的節(jié)點— 關(guān)系—節(jié)點跳躍，從而獲得更好的性能。