用於連續圖更新和計算的平臺的製作方法

2023-04-23 15:26:46

用於連續圖更新和計算的平臺的製作方法
【專利摘要】連續流數據(例如，消息、推特(tweet))通過平臺的各攝取節點來接收。攝取節點可分析數據以創建圖更新的事務，將序列號分配給該事務，並且將具有該序列號的圖更新分發到平臺的圖節點。圖節點可存儲來自攝取節點的圖更新，並且隨後攝取節點可在進度表中報告圖更新進度。可基於該進度表來拍攝快照，並且隨後可實現圖挖掘計算。可支持容錯和衰減，並且可允許增量式擴展以應對增加的更新速度和計算需求。
【專利說明】用於連續圖更新和計算的平臺
[0001]背景
[0002]日益流行的在線服務(例如，Twitter?、Facebook?和Foursquare?)提供了來自各個用戶在相對短時間量內的更新信息。這些服務上可獲得的信息被持續生成並且比大多數靜態網頁在時間上敏感得多。例如，突發新聞出現並且由這些在線服務中的某些快速傳播，伴隨著新的流行活動或熱點話題不斷地從物理世界中的實時事件產生。儘管每一消息或更新可能較小且包含有限的文本內容，但數據流可包含用戶、話題和消息之間的豐富連接，並且這些連接可用來生成重要的社會現象。
[0003]概述
[0004]分布式設計可採用數據流來構建持續變化的圖結構以捕捉該流中存在的關係。這些設計可將圖挖掘與圖結構的圖更新解耦。分布式系統可將圖結構元數據與圖結構的應用數據分開。可以實現時期提交協議以生成圖結構的全局一致的快照。基於這些一致的快照，可以執行圖挖掘算法以從該流中提取及時的洞察。
[0005]提供本概述是為了以簡化的形式介紹將在以下【具體實施方式】中進一步描述的概念選擇。本概述並不旨在標識所要求保護主題的關鍵特徵或必要特徵，也不旨在用於限制所要求保護主題的範圍。
[0006]附圖簡述
[0007]參考附圖來描述【具體實施方式】。在附圖中，附圖標記最左邊的數字標識該附圖標記首次出現於其中的附圖。在不同的附圖中使用相同的附圖標記指示類似或相同的項。
[0008]圖1是處理流送數據的說明性架構的示意圖。
[0009]圖2是用來示出跨圖節點的分區創建一致的快照的示例的示意圖。
[0010]圖3是處理流送數據的說明性過程的流程圖。
[0011]圖4是產生一致分布的快照的說明性過程的流程圖。
[0012]圖5是執行圖挖掘計算的說明性過程的流程圖。
[0013]圖6是實現增量式圖挖掘計算的說明性算法。
[0014]圖7是實現攝取節點中的容錯的說明性過程的流程圖。
[0015]圖8是可在圖1所示的環境中部署的說明性計算設備的框圖。

【具體實施方式】
[0016]概覽
[0017]數據流(例如，消息、推特(tweet))通過平臺的一組攝取節點來接收。該組攝取節點中的一個攝取節點可分析數據流的每一傳入饋源(例如，推特及其關聯上下文)以創建圖更新的事務，向該事務分配序列號，並且將具有該序列號的圖更新分發到平臺的多個圖節點。圖節點可提供具有增強的圖支持的分布式存儲器中密鑰/值存儲。這些圖節點中的每一個可存儲與關聯應用數據分開的數據流的圖結構元數據。
[0018]另外，在圖節點存儲這些圖更新之後，攝取節點可在進度表中報告圖更新進度。快照可基於進度表被周期性地拍攝。該進度表可用作邏輯時鐘以定義時期的結束。在該時期內，可遵循預定次序在圖節點中執行所有存儲的局部圖更新。圖更新的執行可觸發對新快照的增量式圖計算，以更新關聯應用數據並且從該數據流提取及時的洞察。
[0019]在某些實例中，本文討論的技術可支持容錯和衰減，並且允許增量式擴展以應付增加的更新速率和計算需求。
[0020]此處所描述的過程和系統可以按多種方式實現。各示例的實現在下文中參考以下附圖來提供。
[0021]說明性體系結構
[0022]圖1是處理流送數據的說明性架構100的示意圖。架構100包括數據流102和用於連續圖更新和計算的平臺104。平臺104包括一組攝取節點106、一組圖節點108、全局進度表110和快照拍攝器112。平臺104可通過包括攝取節點114的攝取節點106接收數據流102 (例如，消息、推特)。攝取節點114可分析每一傳入記錄(例如，消息以及與該消息相關聯的上下文)。基於該分析，攝取節點114可創建圖更新操作116的事務。對於該事務，攝取節點114可分配序列號118，並且將具有該序列號的圖更新操作116分發到包括圖節點120的圖節點108。
[0023]圖節點120可包括兩層:存儲層122和計算層124。存儲層122可維護圖數據，而計算層124可執行增量式圖挖掘計算。具體而言，存儲層122可使用鄰接列表維護每一頂點作為圖結構126的元數據，並且分開地存儲關聯數據128以供圖挖掘計算。計算層124可基於對關聯數據128進行操作的圖挖掘算法來執行計算。
[0024]圖節點108可存儲由攝取節點106發送的圖更新操作所指示的圖更新。攝取節點106可在可由中央服務維護的全局進度表110中報告圖更新進度。例如，攝取節點106可使用包括多個序列號的序列號140的全局進度表110。快照拍攝器112可基於全局進度表110中的序列號所指示的當前向量周期性地指令圖節點108來拍攝快照。當前向量可用作全局邏輯時鐘以定義時期的結束。在時期被定義之後，圖節點108可以執行並且提交在該時期中所有存儲的局部圖更新以產生圖結構快照。在各個實施例中，可遵循預定次序執行這些局部圖更新。
[0025]在圖結構126中進行因該時期引起的更新之後，計算層124可對新快照執行增量式圖計算以更新感興趣的關聯值。
[0026]說明性的創建一致的快照
[0027]圖2是用來示出跨圖1的圖節點108的分區創建一致的快照的示例的示意圖200。一致的快照可通過攝取節點106、圖節點108、快照拍攝器112和全局進度表110之間的合作來創建。根據各個實施例，一致的快照機制實現時期提交協議，該時期提交協議推遲應用更新直到時期被定義，如以下說明性過程中討論的。
[0028]根據各個實施例，攝取節點106中的一個攝取節點(例如，攝取節點202或攝取節點204)可將數據流102的每一傳入記錄轉變成包括可跨圖節點108的邏輯分區206的一組圖更新操作的事務。例如，這些操作可包括創建頂點V2，將傳出邊添加到頂點V1並且將傳入邊添加到頂點V2。這些操作中的每一個可完全在與頂點相關聯的圖結構126上執行。另外，攝取節點可創建連續事務序列，每一事務具有連續增加的序列號。那些序列號可用來構建全局邏輯時鐘以決定哪些事務應被包括在快照中，並且還用作該快照的標識符。
[0029]在各個實施例中，可將圖拆分成固定數量的(例如，512個)邏輯分區206，這些邏輯分區可進一步被分配給圖節點108的物理機。例如，圖分區可基於頂點ID的散列來執行，而局部性考慮可能不是必要的。在一些實施例中，邏輯分區206中的每一個可包括一組頂點，每一頂點具有存儲在已排序列表中的一組有向加權邊。同時，各邊緣可被認為是圖結構126的一部分，並且在存儲層122中被添加和/或修改。該組頂點中的每一頂點還可具有為計算層124中的圖挖掘計算的算法存儲關聯數據128的一組頂點欄位。存儲在頂點欄位中的值的類型可以是任意的，只要該類型可被串行化。
[0030]例如，如圖2中所示，攝取節點202可分別向分區V和分區u發送具有關聯序列號的圖更新操作。具體而言，在分區u中，對應操作可被分組以生成第一已分組操作208，第一已分組操作208可基於關聯序列號的次序來排序並且被表示為(0，3，5)。類似地，在分區V中，對應操作可被分組並且被排序以生成第二分組操作210(即，(1，2，4))。
[0031]假定攝取節點202已經接收到來自圖節點108中的所有相關分區(例如，分區u和分區V)的確認:具有序列號多至3的所有事務的圖更新操作已被接收並存儲。結果，攝取節點202可將其條目更新為第一序列號214「3」。為發起快照，快照拍攝器112可從全局進度表110中取包括一個或多個序列號118的全局向量212(即，{3，...，7})。全局向量212可用作全局邏輯時鐘以定義時期216的結束。可向圖節點108廣播該新定義的時期，使得屬於時期216的圖更新在邏輯分區206中以相同確定性但人為次序來處理。因此，若且唯若序列號s不大於第一序列號214 「3」的情況下，來自具有序列號s的攝取節點202的圖更新才被包括在時期216中。
[0032]類似地，若且唯若序列號s不大於第二序列號218 「7」的情況下，來自具有序列號s的攝取節點204的圖更新才被包括在時期216中。在一些實施例中，邏輯分區上的操作被串行處理，並且在每一圖節點上可存在足夠的邏輯分區206，導致伺服器級處足夠的並發性。
[0033]在一些實施例中，創建快照的過程可繼續傳入更新。攝取節點106可連續地將新圖更新發送到具有較高序列號的圖節點108中。通過應用那些更新，攝取節點106分派和攝取節點108存儲圖更新操作的過程可與創建快照的過程重疊。因此，延遲執行不會影響足夠長的時間段上的吞吐量。本公開的一致的快照機制可在小時期窗口中有效地對操作進行批處理，以在合理的時間線與能夠處理高傳入更新速率之間尋求平衡:速率越高，該批處理可更有效。
[0034]時期提交協議可確保原子性，因為事務中所有操作中的任一個被包括在快照中、或者它們都不被包括在快照中。這可排除包括一個頂點的快照，該快照具有傳出邊但沒有與目的地頂點匹配的傳入邊。該協議可進一步確保按序列號次序處理來自相同攝取節點的所有事務。歸功於圖更新與圖挖掘分開，在創建一致的快照時可僅處理簡單的圖更新，並且由此利用每一事務包括各自能在單個頂點結構上被應用的一組圖結構更新的事實。對於那些取決於其他頂點狀態的更新，它們可在圖挖掘階段被執行。
[0035]在一些實施例中，本公開中描述的快照機制可確保快照中要包括的該組事務的一致性，並且在該組內施加人為次序，使得所有事務可按相同次序來處理。在一些實施例中，次序可以是人為的。例如，在按順序處理來自攝取節點114的更新之前，可指令圖節點按特定序列號來處理那些更新。該外部施加的次序可能不需要考慮任何因果關係，部分原因是該機制將圖更新與圖挖掘分開，並且圖更新通常簡單且直接。因此，外部施加的次序可能既不反映物理時間次序也不反映任何因果次序。在各個實施例中，可應用不同的外部施加的次序，並且所得圖可以是類似的。在一些實施例中，使頂點創建成為確定性的。例如，如果存在針對每個推特用戶ID創建的頂點，則該頂點可具有確定性地取決於該推特用戶ID的內部ID。因此，可在創建該頂點之前創建來自或去往該頂點的邊，由此消除跨操作依賴性。
[0036]說明性操作
[0037]圖3是處理流送數據的說明性過程的流程圖。過程300被示為邏輯流程圖中一組框的集合，這表示可用硬體、軟體或其組合實現的一系列操作。在軟體的上下文中，各個框表示在由一個或多個處理器執行時使得一個或多個處理器執行既定操作的計算機可執行指令。一般而言，計算機可執行指令包括執行特定功能或實現特定抽象數據類型的例程、程序、對象、組件、數據結構等。描述操作的次序並不旨在被解釋為限制，並且任何數量的所述框可以按任何次序和/或並行地組合以實現該過程。除了過程400之外，本發明通篇所描述的其他過程(包括過程400、500和700)也應如此解釋。
[0038]在302，平臺104可接收數據流102 (例如，消息和推特)。在一些實施例中，數據流102可包括動態流送數據饋源，動態流送數據饋源可被連續地生成。動態流送數據饋源的新信息可比大多數靜態網頁在時間上更敏感。例如，突發新聞可能出現並且在動態流送數據饋源內快速傳播，並且新的流行活動和熱門話題可不斷地從物理世界中的實時事件而產生。同時，實體(諸如用戶)、話題和數據饋源之間的豐富連接可用來揭示重要的社會現象。在一些實施例中，動態流送數據饋源可使用多個元數據(例如，井號標籤(hashtag))來標識與消息相關聯的有爭議信息。
[0039]在304，平臺104可產生快照以定義與數據流102相關聯的圖結構數據126。在一些實施例中，平臺104可通過使用時期提交協議(以下參考圖4更詳細地描述)來產生一致分布的快照。
[0040]在306，平臺104可執行圖計算以執行操作，例如，編譯與圖數據126相關聯的應用數據。在一些實施例中，平臺104可執行增量式圖挖掘，使得計算結果可基於數據流102中的最近變化來更新。這些最近變化反映在新快照中。在一些實施例中，圖挖掘算法(例如，搜索算法和TunkRank算法)可對存儲關聯數據128的一組頂點欄位操作。
[0041]在308，平臺104可基於應用數據128向用戶呈現計算結果。例如，平臺104可呈現搜索結果、用戶影響力、圖中兩個頂點(例如，兩個用戶)之間的最短路徑、以及與數據流102相關聯的有爭議話題。
[0042]圖4是產生一致分布的快照的說明性過程400的流程圖。在402，攝取節點114可接收數據流102的傳入記錄(例如，消息和與該消息相關聯的上下文)。在404，攝取節點114可基於接收到的記錄來創建圖更新操作的事務。在一些實施例中,攝取節點114可通過解析記錄來定義圖結構126，並且隨後產生包括一組圖操作(例如，添加邊和/或頂點)的事務。在一些實施例中，可以定義定製圖更新操作(例如，添加10%的權重)，以便提供在生成快照時當對攝取節點114應用這些操作時要調用的回調函數。
[0043]在406，攝取節點114可向事務分配序列號。在408，攝取節點114可使用序列號在圖節點之間分發操作。在一些實施例中，可在邏輯分區206中對來自攝取節點106的一組圖更新操作進行排序和分組，以生成按照原始攝取節點分組的操作。
[0044]在410，圖節點120可存儲來自攝取節點114的圖更新。在一些實施例中，圖節點120可用鄰接列表維護每一頂點作為圖結構126的元數據。因此，圖更新可修改定義圖結構126的元數據。在一些實施例中，圖節點120可分開存儲關聯數據128。在一些實施例中，攝取節點114可被配置成將頂點ID映射到邏輯分區206，並且將邏輯分區206及其副本分配給伺服器。
[0045]在412，在圖節點108存儲事務的操作之後，攝取節點114可在全局進度表110中標記圖更新進度。全局進度表I1可記錄攝取節點114的序列號以監視圖更新進度。
[0046]在414，快照拍攝器112可基於全局向量212來定義時期216的結束，全局向量212包括全局進度表110中每一攝取節點(例如，攝取節點202和攝取節點204)的當前序列號。全局向量212可用作全局邏輯時鐘以定義時期216的結束。
[0047]在416，圖節點108可執行時期216中所存儲的局部圖更新，以在時期216被定義之後產生圖結構快照。快照拍攝器112可向每一圖節點廣播時期216的定義，使得時期216中的所有圖更新在邏輯分區206中按同一確定性次序來處理。
[0048]例如，假定在攝取節點i已從對應圖節點接收到關於多至Si的事務的圖更新操作已被接收並存儲的確認的情況下，該攝取節點將其條目更新為序列號Si。快照拍攝器112可周期性地(例如，10每秒)從當前全局進度表中取序列號的向量(例如，Sl，S2,…，sn)，其中Si是與攝取節點i相關聯的序列號。快照拍攝器112隨後可使用該向量作為全局邏輯(向量)時鐘以定義當前時期的結束。該決定被廣播給所有圖節點，其中屬於該時期的所有圖更新在所有邏輯分區中按同一確定性但人為的次序來處理。若且唯若序列號s不大於Si成立時，來自具有序列號s的攝取節點i的圖更新才被包括在當前時期中(即，S1, S2,…，sn)。
[0049]在一些實施例中，圖結構126中的更新響應於時期216的定義可觸發對快照的增量式圖計算以更新關聯數據128。各種算法可用來實現增量式圖計算。
[0050]說明性增量式圖挖掘計算
[0051]如上所討論的，圖節點108的計算層124可執行增量式圖挖掘。計算結果可基於圖中的最近變化來更新。圖結構變化可反映在新的快照中；圖挖掘算法可對存儲這些算法的關聯數據的一組頂點欄位操作。
[0052]在一些實施例中，基於頂點的計算模型可用於圖挖掘計算。在該模型中，感興趣的數據可連同頂點一起被存儲，並且計算通過跨每一頂點進行處理來前進。另外，圖尺度縮減可用來計算全局值，全局值可以是任意的複合值(例如，前X名有影響力的用戶或某種類型的頂點數量)。
[0053]在一些實施例中，平臺104可基於拉模型和推模型來實現計算模型的混合，該混合帶有變化以支持增量式計算和高效的分布式執行。在該混合模型下，關聯數據128中的變化通常可在子圖中傳播，該子圖由圖結構126中的變化(例如，添加邊)而引發。
[0054]圖5是執行圖挖掘計算的說明性過程500的流程圖。在502，平臺104可應用用戶定義的規則通過比較當前快照與先前快照來檢查圖結構126的頂點狀態。如果頂點未被修改(例如，邊被添加以及值被改變)，則在504，平臺104可調用用戶指定的函數來計算與頂點相關聯的新值。在506，平臺104可例如基於預定規則來確定值是否顯著地改變。如果值未顯著地改變(自判定506的「否」分支)，則操作502至506可通過循環過程(經由導致返回判定502的自操作的506虛線)來執行。如果值顯著地改變(自判定506的「是」分支)，則在508，平臺104可將這些變化傳播給一組頂點(例如，鄰域中的頂點或基於預定規則定義的頂點)。
[0055]在510，可實現頂點的圖尺度聚集以使用圖尺度縮減來計算全局值。這些全局值可以是任意的複合值(例如，前X名有影響力的用戶或特定類型的數個頂點)。操作502至510可通過循環過程(經由自操作506導致返回判定502的虛線)來執行，如果需要的話該循環過程可包括傳播變化。在一些實施例中，由其他頂點驅動的傳播可改變頂點的狀態。在一些實施例中，用戶定義的頂點欄位中的變化可響應於圖結構中的特定變化(例如，添加邊)來在子圖中傳播。在跨圖結構126中的所有頂點未檢測到狀態變化時，可終止該傳播。
[0056]在推模型中，每一頂點可將部分更新發送給另一頂點的頂點欄位。例如，頂點的頁排名(pagerank)是其相鄰頂點的頁排名的加權總和，並且每一頂點將其頁排名發送給其向外的鄰居，並且系統將它們添加在一起以形成總體頁排名。在增量式算法中，每一頂點可發送其頂點欄位值的增量式變化。例如，在頁面排名中，每一頂點可發送其當前與先前頁排名之間的差異。為使模型起作用，更新可以是可結合且可交換的。模型的一個特徵在於執行發送者側聚集的能力。對於每一頂點欄位，編程者可定義將若干頂點所發送的更新組合成一單個更新的局部聚集函數。
[0057]推模型上的修改可通過跟蹤針對新快照且在計算期間的「髒」欄位來啟用增量式計算。當欄位被聲明為「髒」時，其更新函數可被調用。更新函數的角色是將其新值與先前值的差異「推」到相鄰頂點。平臺104可跟蹤發送給相鄰頂點中的每一個的值以執行增量式計算。
[0058]在一些實施例中，各過程不僅可用來支持推模型，而且提供一種在頂點更新函數中分開地處理每一個別消息的方式。在本公開中，這些消息可由平臺來處理並且通過用戶定義的聚集函數來組合。更新函數可看到存儲在頂點欄位中的最終值。
[0059]可為分布式計算修改拉模型。拉模型中的頂點更新函數可讀取其相鄰頂點的值並且為自己產生新值。如果頂點更新函數確定改變是顯著的，則它將要求平臺更新其鄰居，並且該計算在圖中動態地傳播。在平臺104中，更新函數可不限於讀取其鄰居，並且可能想要讀取特定類型的鄰居或個別頂點(例如，新創建的頂點)。因此，為了最優性能，可建議編程者降低用於執行更新函數所要求的頂點信息量。另外，不同的更新函數可需要不同類型的數據。在一些實施例中，一些函數可能要求相鄰頂點的特定頂點欄位的值；但其他函數可能要求更多數據(例如，該鄰居的邊的列表)。
[0060]在一些實施例中，平臺104可按使網絡通信最小化的方式來調度對頂點的更新。具體而言，在若干更新函數請求同一頂點的情況下，平臺可組合對相同頂點的請求，並且在所有所請求的數據可用時執行這些更新。同步模型可在程序發出對頂點的同步調用時被執行。請求可被進取性地批處理，使得有更多機會合併這些請求並且降低伺服器之間的RPC
調用量。
[0061]在一些實施例中，用戶可定義當快照中有新頂點或新的內/外邊時被調用的函數。這些新頂點或新的內/外邊可用作增量式圖挖掘的初始化。在推模型中，與髒對應的頂點欄位可被設置成隨後導致對該頂點調用更新函數。類似地，在拉模型中，初始化階段可涉及要求系統準備好用於執行更新函數所需的數據。
[0062]除了基於頂點的計算以外，平臺104可提供一種使用在所有頂點上執行分布式縮減的聚集器函數來計算全局值的機制。
[0063]在一些實施例中，平臺104還可針對頻繁增量式計算步驟來設計。它可採用調度機制。計算可通過執行連續的超步驟來前進，被調度要在連續的超步驟上運行的每一頂點由每一分區執行。計算一致性可不被強迫，從而相鄰頂點可被並行更新。
[0064]在一些實施例中，平臺104可在每一快照處執行定義的最大數量的超步驟，除非任務隊列為空且沒有頂點要更新，這可能是收斂計算的指示。平臺的執行模型還可與海量同步並行(BSP)和動態調度有關，並且全局聚集器可在每一 BSP步驟之後被更新。
[0065]說明性算法
[0066]圖6是實現增量式圖挖掘計算的說明性算法600。具體來說，該算法600可被實現為對特定用戶的影響計算某種度量。算法600用來呈現以上討論的特徵的各種說明性實現。下列討論涉及說明性算法600，行號602示於的算法的左手側。該討論提供了可以模塊的任何順序、功能或變型來實現的各種特徵，以執行上面更為一般地描述的各種特徵。因此，上文所討論的技術不受到說明性算法600的實現的限制。
[0067]算法600可包括行1-4，其可處理具有連接彼此提及的用戶的邊的用戶頂點的圖。例如，可使用用戶之間的較強連接(基於在Twitter中誰提到誰)。如果推特包含username (用戶名)」，則這可意味著微博的提交者提到用戶的用戶名(即，注意到用戶名)。在行5,每一 EmitOperat1ns (發出操作)可發出兩個createEdge (創建邊)操作:一個用於源添加傳出邊而另一個用於目的地添加傳入邊。如行8中所示，可添加代碼以標記新的向外邊和頂點以發起推送。
[0068]在行9-17, updateFunct1n (vertex)(更新函數(頂點))可將新的與先前加權的TunkRank的差異發送給其鄰居。在行19，可添加代碼以執行求和運算。在行20，可添加代碼以檢測欄位是否改變得足以(髒)到觸發計算(即，updateFunct1n) 0在一些實施例中，通過觸發器中的調整參數(即，e )，算法可調整準確性/計算時間的折衷。另外，算法可使用全局聚集器對象來維護K個最有影響力的用戶列表。在一些實施例中，將e設置為
0.001，這是足以找到最有影響力的用戶的值。
[0069]說明性容錯
[0070]圖7是用於實現圖1中的攝取節點106中的容錯的說明性過程700的流程圖。如以上討論的，時期提交協議可假定每一攝取節點為圖結構更新的事務產生連續單調遞增的序列號。然而，攝取節點在向多個圖節點發送更新中間有可能會失敗。平臺104提供具體化數並且利用全局進度表來解決該潛在的問題。
[0071]在702，平臺104可將具體化數分配給攝取節點114，並且該具體化數可與同攝取節點114中的事務相關聯的序列號配對。因此，各序列號可由對(例如，(c，s))來替換，其中c是具體化數而s是序列號。在704，這些對可用在發往圖節點108的圖結構更新中，並且可被記錄在全局進度表110中。
[0072]在706，平臺104可確定攝取節點是否失敗和恢復，或者新機器是否扮演已失敗攝取節點的角色。在708，經恢復的攝取節點或經替換的攝取節點在攝取節點失敗和恢復的情況下或在新機器扮演已失敗攝取節點的角色的情況下可密封具體化數。經恢復的攝取節點可諮詢全局進度表，以尋找包括與該攝取節點相關聯的具體化數和與事務相關聯的序列號的對。
[0073]在710，平臺可通過使原始具體化數加一來生成新的具體化數，並且可通過將序列號重置為零(O)或使原始序列號加一來生成新的序列號。
[0074]在712，平臺可丟棄與攝取節點相關聯的、具有大於該序列號的序列號的操作。為避免事務的任何損失，所有傳入數據饋源可被可靠地存儲，並且僅在它們已反映在全局進度表110中之後才能對其進行垃圾收集。
[0075]例如，當攝取節點失敗和恢復時、或當新機器扮演已失敗攝取節點的角色時，該復活的攝取節點i可諮詢全局進度表以尋找與攝取節點i相關聯的對(Ci，Si)。復活的攝取節點可將Ci密封在Si處，並且使用si+Ι作為新的具體化數。該攝取節點可將序列號重置為零(O)或在Si+1處繼續。通過將Ci密封在Si處，具有(Ci，Si)的所有請求被視為無效並且被丟棄，其中s>Si。
[0076]在一些實施例中，平臺可通過使用不同機制來分開處理存儲層122處與計算層124處的容錯。在存儲層122，需要將圖更新操作可靠地存儲在各圖節點上。平臺可利用各攝取節點並且使用基於簡單選出成員的複製機制。具體地，每一邏輯分區可在k(例如，3)個不同機器上被複製，並且可容忍f(例如，I)個出錯，其中k>2f+l成立。圖更新操作隨後可被發送給所有副本，並且只要f+Ι個副本已響應，攝取節點就可認為該操作已被可靠地存儲。攝取節點可保存用於每一邏輯分區的操作數量的計數器，並且將該計數器附連於每一操作。副本可使用該計數器來標識漏洞並且向其他副本要求丟失信息。副本可創建與它們按相同順序應用相同組操作相同的快照。
[0077]在一些實施例中，如以上討論的，在計算層124處，平臺可觸發對一致的快照的增量式圖挖掘計算。計算的每一調用可花費相對少的時間量(例如，分鐘級)。由於快照與複製被可靠地存儲在存儲層處，因此平臺在計算階段遭遇任何失敗的情況下可回退並且重新執行。計算結果可被複製以便容錯。平臺可實現主要/備份複製方案，其中主要複製方案執行計算並且將結果複製給次要複製方案。
[0078]說明性增量式擴展和衰減
[0079]平臺104的規模可取決於某些因素，包括傳入數據饋源的速率、所得圖的大小、以及圖挖掘計算的複雜性。在一些實施例中，平臺104可吸收更多機器進入系統以便處理更高負荷、更大量的數據、和/或更繁重的計算。例如，平臺104可事先創建大量邏輯分區，並且增量式擴展隨後可通過將特定邏輯分區移至新機器來實現。例如，假定平臺可能想要將邏輯分區從S遷移到T。平臺104可就以下各項與每一攝取節點s通信:關於該遷移以及關於承諾向S和T兩者發送始於序列號\的所有對該邏輯分區的未來操作。一旦對於每一 I < i < n，具有邏輯時鐘(Sl，S2,…，sn)滿足Si彡\的快照被創建，平臺就指令將該快照從S複製到T。一旦T接收到該快照，T就具有從S接管該邏輯分區所需的所有信息。由於計算與傳入更新重疊，因此T通常能快速趕上S，而不會導致任何性能降級。
[0080]在一些實施例中，信息隨時間衰減的值以及過期信息對結果的影響可逐漸變得越來越小。平臺104可通過利用基於序列號的全局邏輯時鐘來支持衰減。例如，假定過去η天中感興趣的信息並且那η天內的該信息取決於哪天而具有不同權重。平臺104實質上可創建η+1個並行圖以跟蹤過去η天加上當前的一天。當經過一天時，窗口可滑動。平臺104可將那些衰減時間邊界與由序列號的邏輯時鐘定義的時期對齊。當經過實時的一天時，平臺104可查看當前時期號並且使用該當前時期號作為邊界。因此，用於計算的實圖可通過取那些並行圖的加強平均來構建。
[0081]說明性計算設備
[0082]圖8示出了可用於實現連續圖更新和計算的圖1的平臺104的說明性計算設備800。容易理解，可在其他計算設備、系統和環境中實現上述各種實施例。圖8所示的計算設備800隻是計算設備的一個示例，且並非旨在對計算機和網絡體系結構的使用範圍或功能提出任何限制。計算設備800也不旨在被解釋成對於在該示例計算設備中所示出的任一組件或其組合有任何依賴或要求。
[0083]在非常基本的配置中，計算設備800通常包括至少一個處理單元802和系統存儲器804。取決於計算設備的確切配置和類型，系統存儲器804可以是易失性的(諸如RAM)、非易失性的(諸如ROM、快閃記憶體等)或是兩者的某種組合。系統存儲器804通常包括作業系統806、一個或多個程序模塊808，並且可包括程序數據810。作業系統806包括基於組件的框架812，該框架支持組件(包括屬性和事件)、對象、繼承、多態性、反射，並且提供面向對象的基於組件的應用程式編程接口(API)。計算設備800具有由虛線814劃分的非常基本的配置。同樣，一終端可具有更少的組件，但將與可具有這一基本配置的計算設備交互。
[0084]計算設備800可具有附加特徵或功能。例如，計算設備800還可包括附加數據存儲設備(可移動和/或不可移動)，諸如，例如磁碟、光碟或磁帶。在圖8中通過可移動存儲816和不可移動存儲818示出這樣的附加存儲。計算機可讀介質可包括至少兩種類型的計算機可讀介質，即計算機存儲介質和通信介質。計算機存儲介質可包括以用於存儲諸如計算機可讀指令、數據結構、程序模塊或其他數據等信息的任何方法或技術來實現的易失性和非易失性、可移動和不可移動介質。系統存儲器804、可移動存儲816和不可移動存儲818都是計算機存儲介質的示例。計算機存儲介質包括，但不限於，RAM、ROM、EEPR0M、快閃記憶體或其他存儲器技術、CD-ROM、數字多功能盤(DVD)或其他光碟存儲、磁帶盒、磁帶、磁碟存儲或其他磁性存儲設備、或能用於存儲所需信息且可以由計算設備800訪問的任何其他非傳輸介質。任何這樣的計算機存儲介質都可以是計算設備800的一部分。此外，計算機可讀介質可包括在由處理器802執行時執行此處所描述的各種功能和/或操作的計算機可執行指令。
[0085]作為對比，通信介質可用諸如載波或其他傳輸機制等已調製數據信號來體現計算機可讀指令、數據結構、程序模塊或其他數據。如本文所定義的，計算機存儲介質不包括通信介質。
[0086]計算設備800還可具有諸如鍵盤、滑鼠、筆、話音輸入設備、觸摸輸入設備等輸入設備820。還可包括諸如顯示器、揚聲器、印表機等輸出設備822。這些設備在本領域是公知的，因此不在此詳細討論。
[0087]計算設備800還可包含允許該設備諸如通過網絡來與其他計算設備826進行通信的通信連接824。這些網絡可包括有線網絡以及無線網絡。通信連接824是通信介質的一個示例。
[0088]可以理解，計算設備800隻是合適的設備的一個示例，並不旨在對所述各實施方式的使用範圍或功能提出任何限制。適用於各實施例的其他公知的計算設備、系統、環境和/或配置包括但不限於，個人計算機、伺服器計算機、手持式或膝上型設備、多處理器系統、基於微處理器的系統、機頂盒、遊戲控制臺、可編程消費者電子產品、網絡PC、小型計算機、大型計算機、包括上述系統或設備中的任一個的分布式計算機環境等。例如，計算設備800的某些或全部組件可被實現在雲計算環境中，使得可使得資源和/或服務可經計算機網絡可用而供行動裝置選擇性使用。
[0089]結論
[0090]雖然已經用對結構特徵和/或方法動作專用的語言描述了各項技術，但是應該理解，所附權利要求不必限於所述的具體特徵或動作。相反，這些具體特徵和動作是作為實現這些技術的示例性形式而公開的。
【權利要求】
1.一種用於處理連續數據流的計算機實現的方法，所述方法包括: 接收所述連續數據流的記錄； 由攝取節點基於所述記錄來生成一個或多個圖更新操作； 將序列號分配給所述一個或多個圖更新操作； 將具有所述序列號的所述一個或多個圖更新操作分發到多個圖節點； 在所述一個或多個圖更新操作被所述多個圖節點存儲之後，將所述序列號記錄在全局進度表中； 基於所述全局進度表來定義時期的結束；以及 通過執行存儲在所述多個圖節點中且在所述時期內的圖更新操作來產生圖結構快照。
2.如權利要求1所述的計算機實現的方法，其特徵在於，所述多個圖節點分開地存儲與所述連續數據流相關聯的圖結構數據與應用數據。
3.如權利要求2所述的計算機實現的方法，其特徵在於，還包括: 基於所述圖結構快照來更新所述圖結構數據；以及 響應於更新所述圖結構數據，基於已更新圖結構數據以及存儲在所述多個圖節點中的所述應用數據來執行增量式圖計算。
4.如權利要求1所述的計算機實現的方法，其特徵在於，所述一個或多個圖更新操作中的每一個包括創建一個或多個頂點或添加一個或多個傳出邊中的至少一項。
5.如權利要求1所述的計算機實現的方法，其特徵在於: 所述全局進度表包括向量，所述向量包括所述序列號和另一序列號，所述另一序列號由生成一個或多個特定圖更新操作並將其分發到所述多個圖節點的另一攝取節點分配；基於所述全局進度表來定義所述時期的結束包括基於所述向量來定義所述時期的結束；以及 執行圖更新操作包括執行所述一個或多個圖更新操作以及所述一個或多個特定圖更新操作。
6.如權利要求1所述的計算機執行的方法，其特徵在於，所述一個或多個圖更新操作包括通過向所述一個或多個圖更新操作中的一個圖更新操作添加預定加權的定製圖更新操作。
7.一種計算機實現的方法，包括: 由一個或多個伺服器接收動態流送數據饋源； 產生快照以定義與所述動態流送數據饋源相關聯的圖結構數據； 執行圖計算以編譯與所述圖結構數據相關聯的應用數據；以及 至少部分地基於所述應用數據來呈現結果。
8.如權利要求7所述的計算機實現的方法，其特徵在於，所述結果反映所述動態流送數據饋源的一個或多個變化。
9.如權利要求7所述的計算機實現的方法，其特徵在於: 產生所述圖結構數據的快照包括通過使用時期提交協議來產生所述快照，以及 所述圖結算包括增量式計算。
10.如權利要求7所述的計算機實現的方法，其特徵在於，所述動態流送數據饋源包括至少一組連續生成的消息。
11.如權利要求7所述的計算機實現的方法，其特徵在於，所述動態流送數據饋源包括多個井號標籤。
12.如權利要求7所述的計算機實現的方法，其特徵在於，產生所述圖結構的所述快照包括: 基於數據流來創建各自包括指示與所述動態流送數據饋源相關聯的一個或多個圖更新的一個或多個操作的一組事務； 按遞增順序分配一組序列號，該組序列號中的每一個對應於該組事務中的一個事務； 將包括在該組事務中的操作分派給與一個或多個伺服器相關聯的多個圖節點；以及 通過使用時期提交協議，基於所述操作以及該組序列號來產生所述快照。
13.如權利要求12所述的計算機實現的方法，其特徵在於，基於所述操作以及該組序列號來產生所述快照包括: 在與該組序列號中的一個序列號相關聯的所述一個或多個操作被存儲在所述多個圖節點之後，記錄所述序列號；以及 通過執行與不大於所述序列號的序列號相關聯的操作來生成所述數據流的所述快照。
14.如權利要求12所述的計算機實現的方法，其特徵在於: 多個圖節點中的每一個包括: 存儲所述圖結構數據的存儲層，以及 存儲所述應用數據的計算層；以及 分派所述操作包括將所述操作分派到所述多個圖節點的存儲層。
15.存儲計算機可執行指令的一個或多個計算機可讀介質，所述計算機可執行指令當在一個或多個處理器上被執行時導致所述一個或多個處理器執行如下動作，包括: 基於連續數據流按時間次序生成一組事務； 由攝取節點生成各自與該組事務中的一個事務相關聯的一組序列號，該組序列號為順序; 在該組事務中的一個或多個事務被存儲在多個圖節點中之後，通過使用該組序列號中的特定序列號來記錄更新進度，所述一個或多個事務各自具有不大於所述特定序列號的序列號；以及 由所述多個圖節點通過執行所述一個或多個事務來產生快照，以更新與所述連續數據流相關聯的圖結構元數據。
16.如權利要求15所述的一個或多個計算機可讀介質，其特徵在於，該組事務中的每一個包括應用於基於所述連續數據流所生成的圖的頂點結構的一個或多個操作。
17.如權利要求15所述的一個或多個計算機可讀介質，其特徵在於，所述動作進一步包括: 將具體化數分配給所述攝取節點；以及 生成包括所述具體化數和所述特定序列號的對，並且其中記錄所述更新進度包括通過使用所述對來記錄所述更新進度。
18.如權利要求15所述的一個或多個計算機可讀介質，其特徵在於，所述動作進一步包括: 將具體化數分配給所述攝取節點； 確定所述攝取節點是否失敗； 在所述攝取節點失敗之後，生成新的具體化數和新序列號； 將所述新的具體化數分配給所述攝取節點；以及 丟棄該組事務中與所述攝取節點相關聯且具有大於所述新序列號的序列號的一個或多個事務。
19.如權利要求15所述的一個或多個計算機可讀介質，其特徵在於，所述多個圖節點分開地存儲與所述連續數據流相關聯的圖結構數據與應用數據。
20.如權利要求19所述的一個或多個種計算機可讀介質，其特徵在於，所述動作進一步包括: 基於所述圖結構快照來更新所述圖結構數據；以及 響應於更新所述圖結構數據，基於存儲在所述多個圖節點中的所述應用數據來執行增量式圖計算，執行所述增量式圖計算包括: 基於所述圖結構快照來確定所述圖結構數據的頂點被改變， 傳播所述頂點的對應變化，以及 實現所述頂點的圖尺度聚集。
【文檔編號】G06F17/30GK104205095SQ201280072231
【公開日】2014年12月10日 申請日期:2012年4月5日 優先權日:2012年4月5日
【發明者】F·楊, L·周, M·吳, A·克羅拉, R·程, Y·苗, X·翁, J·洪 申請人:微軟公司