微分數(shù)據(jù)流:

本文為翻譯文章

摘要:

現(xiàn)有的用于處理不斷變化的輸入數(shù)據(jù)的計算模型，除了在有限的特殊情況下，無法有效地支持迭代查詢。這使得復雜的任務執(zhí)行起來很困難, 例如在交互的時間尺度上對變化的數(shù)據(jù)進行社交圖分析，這將極大地幫助那些分析服務行為（如Twitter）的人。

在本文中，我們引入了一種稱為差分計算的新模型，該模型擴展了傳統(tǒng)的增量計算以允許任意嵌套的迭代，并參考了一個公開的原型系統(tǒng)Naiad，該方法可以在一個聲明式數(shù)據(jù)并行數(shù)據(jù)流語言中有效地實現(xiàn)差分計算.

最終的系統(tǒng)可以輕松地對以前難以處理的算法（例如，漸進更新的強連接的組件）進行編程，并將它們與數(shù)據(jù)轉換操作集成在一起，從而從真實的數(shù)據(jù)流中獲得實際相關的見解。

1. 介紹:

低成本存儲的發(fā)展和聯(lián)網(wǎng)設備的普及增加了超大的數(shù)據(jù)集的可用性，其中許多數(shù)據(jù)集正在不斷更新。對這些變化的數(shù)據(jù)集執(zhí)行復雜分析的能力是非常有必要的。 例如，在Twitter社交網(wǎng)絡上發(fā)布的每條推文都可能提供有關該服務用戶的社區(qū)結構的新信息，這些信息可利用于實時推薦服務或定向顯示廣告。盡管最近的大量研究都在增強“大數(shù)據(jù)”系統(tǒng)的增量計算功能[4、8、14、26]，添加循環(huán)結構[7、12、17、20、25]，甚至使用增量方法來有效地執(zhí)行迭代計算 [13，19]，但到目前為止，還沒有系統(tǒng)可以有效地支持對常規(guī)增量更新的復雜迭代計算。
例如，之前發(fā)布的系統(tǒng)都無法實時維護由Twitter引起的圖中的強連接組件結構，這是對之前概述的應用程序的潛在輸入。

本文介紹了一種新的差分計算方法，它對傳統(tǒng)的增量計算模型進行了推廣，尤其適用于迭代算法。微分計算的新穎性有兩個方面: 首先，計算的狀態(tài)根據(jù)部分有序的版本集而不是增量計算的標準的完全有序的版本序列而變化;其次，在任何給定版本上重新構建狀態(tài)所需的更新集都保留在索引數(shù)據(jù)結構中，而增量系統(tǒng)通常會依次將每個更新合并到狀態(tài)的“當前”版本中，然后放棄更新。具體而言，狀態(tài)和對該狀態(tài)的更新與多維邏輯時間戳相關聯(lián)（今后的版本）。 這樣可以實現(xiàn)更有效的重用：例如，如果版本（i，j）對應于輸入的第i輪循環(huán)的第j次迭代，則其派生可以重用兩個前導（i ? 1，j ）和（i，j ? 1），而不僅僅是系統(tǒng)最近處理的那個版本。

增量系統(tǒng)必須解決兩個相關的問題：當輸入更改時有效地更新計算，以及跟蹤依賴關系，以便對狀態(tài)的一部分的局部更新正確地反映到全局狀態(tài)中。 微分計算解決了第一個問題，但是正如我們將看到的那樣，它導致的更新規(guī)則要比增量系統(tǒng)的典型規(guī)則復雜得多。因此，我們還描述了當使用數(shù)據(jù)并行性和數(shù)據(jù)流來跟蹤依賴項時如何實現(xiàn)差分計算，從而形成一個完整的系統(tǒng)模型，我們稱之為微分數(shù)據(jù)流。 增量視圖維護（IVM）算法^{[6、15、23]}解決了類似的問題，其目的是在更新視圖以反映稍有不同的輸入時復用先前輸入所做的工作。 但是，現(xiàn)有的IVM算法不適用于交互式大規(guī)模計算，因為它們要么執(zhí)行過多的工作，維護了太多的狀態(tài)，要么限制表達性。

我們在一個名為Naiad的系統(tǒng)中實現(xiàn)了不同的數(shù)據(jù)流，并將其應用于多個真實數(shù)據(jù)集上的復雜圖形處理查詢。強調水中的仙女的特點,我們用它來計算一個24小時的強連通組件結構的Twitter的消息傳遞圖(一個算法要求雙重嵌套循環(huán),而不是之前所知的方式來表述數(shù)據(jù)并行處理設置),并保持這種結構與次秒級延遲,面對Twitter的全量連續(xù)到達的tweet。而且，該算法的結果可以在相同的差異計算中傳遞給后續(xù)的數(shù)據(jù)流操作符，例如為每個組件維護最常見的散列標簽，如附錄中所述。

我們已經在名為Naiad的系統(tǒng)中實現(xiàn)了微分數(shù)據(jù)流，并將其應用于多個實際數(shù)據(jù)集上的復雜圖形處理查詢。 為了突出Naiad的特征，我們用它來計算一個24小時的強連通組件結構的Twitter的消息傳遞圖（該算法需要雙重嵌套循環(huán)，在數(shù)據(jù)并行設置中是未知的）, 并在面對Twitter全量連續(xù)到達的推文中保持這種結構與次秒級延遲。 此外，該算法的結果可以傳遞到同一微分計算中的后續(xù)數(shù)據(jù)流運算符，例如，為每個組件維護最常見的哈希標簽，如附錄中所述。

本文的貢獻可以總結如下:

• 定義了一個新的計算模型: 微分計算，該模型通過允許狀態(tài)根據(jù)版本的部分順序變化來擴展增量計算，并維護單個更新的索引，從而允許它們針對不同版本以不同方式組合（第3部分）。

• 微分數(shù)據(jù)流的定義，它展示了如何在數(shù)據(jù)并行數(shù)據(jù)流環(huán)境中實際應用差分計算(第4部分)。

• 原型Naiad系統(tǒng)的實現(xiàn)草圖，該系統(tǒng)實現(xiàn)了微分數(shù)據(jù)流，并帶有示例結果，表明系統(tǒng)足夠有效，可以在交互式的時間尺度下計算復雜計算的更新(第5部分)。

2. 動機:

為了激發(fā)我們新的計算框架，考慮確定圖的連通部件結構的問題。在這個算法中，每個節(jié)點分配一個整數(shù)標簽(最初是它自己的ID)，然后迭代更新到其鄰域中的最小值。在關系設置中，通過將邊關系連接到當前標注的節(jié)點，取當前標注的并集，計算每個節(jié)點ID對應的最小標注值，可以計算一次迭代:

在i步后，每個節(jié)點在其i-hop鄰域中將具有最小的標簽，并且當運行到固定點時，其連接的組件中將具有最小的標簽。 以下數(shù)據(jù)流圖說明了迭代計算：

為了使問題更具體，請考慮在Twitter在線社交網(wǎng)絡上24小時內由@username提交形成的圖的示例，并對比四種執(zhí)行連接組件算法的每次迭代的方法。 圖1繪制了針對各種算法的每次迭代中標簽更改的次數(shù)，作為每種算法工作量的代表。 我們在第5節(jié)中確認運行時間表現(xiàn)出相似的行為。

圖1:對于24小時的tweet窗口，使用三種不同的技術，通過迭代繪制不同的連接組件標簽的數(shù)量。此外，還繪制出了更新第三條tweet時所需的差異。

最簡單和性能最差的方法將上述查詢重復應用于上一次迭代的結果，直到標簽停止更改。 在這種情況下，所有先前計算的結果將在每一輪中都被新標簽覆蓋，從而導致每次迭代的工作量保持不變，并且圖1中標記為“無狀態(tài)”的平線也不變。 包括MapReduce[10]和Dryad[16]在內的數(shù)據(jù)并行框架在迭代之間不維護任何狀態(tài)，只能以這種方式執(zhí)行算法。
一種更高級的方法(“增量式”)將狀態(tài)從一個迭代保存到下一個迭代，并使用增量評估策略根據(jù)先前迭代中的更改來更新標簽集[13、17、19]。 當標簽收斂到其正確值時，每次迭代所需的計算量就會減少。 在圖1中，每次迭代的差異數(shù)量在第八次迭代之后呈指數(shù)衰減，并且總工作量不到傳統(tǒng)方法所需工作量的一半。 增量方法確實需要在內存中維護狀態(tài)以提高性能，不過不會超過標簽的全部集合。

可以通過重新排序計算來改進增量方法的(“優(yōu)先級”)，從而減少迭代之間的更改。例如，在連接的組件中，我們可以確定較小的標簽的優(yōu)先級，這些較小的標簽在最小計算中更可能占優(yōu)勢，然后在較大的標簽之前引入這些標簽。這種思想在本質上與Zhang等人提出的優(yōu)先迭代相似。 [28]。 實際上，總工作量僅是增量工作的10％，大約相當于無狀態(tài)數(shù)據(jù)流系統(tǒng)完成的工作量的4％。

允許輸入更改

差異數(shù)據(jù)流一般化了增量方法和優(yōu)先級方法，并且可以用于實現(xiàn)其中任何一種，從而在差異中產生相同數(shù)量的記錄。盡管差異數(shù)據(jù)流存儲了多個迭代的差異(而不是丟棄或合并它們)，但為24小時窗口保留的總數(shù)僅比標簽集（增量數(shù)據(jù)流所需的狀態(tài)）多1.5％。

如果修改了輸入圖（例如，通過刪除單個邊），則可以顯示微分數(shù)據(jù)流的功能。 在這種情況下，必須丟棄傳統(tǒng)的，增量的和優(yōu)先的數(shù)據(jù)流計算的結果, 并在新圖上從頭開始重新執(zhí)行其計算. 可以使用支持遞歸查詢的IVM算法，但是會有很大的計算或內存開銷。相比之下，我們的方法(“微分(1s變化)”)能夠重復使用圖中未更改的部分相對應的狀態(tài)。微分數(shù)據(jù)流系統(tǒng)可以區(qū)分由于更新的輸入而產生的變化和由于迭代執(zhí)行而產生的變化，并重用任何適當?shù)南惹盃顟B(tài)。在圖1中，我們看到，當最初的24小時窗口滑動1秒時，系統(tǒng)只處理了67個差異(這在跟蹤期間是典型的)，并且在幾個迭代中不需要做任何工作。更新滑動窗口完成的工作僅是完全優(yōu)先級重新評估中完成工作的0.003％。

我們將在第5節(jié)中表明，差異的減少與執(zhí)行時間的減少相對應, 并且對于這些類型的計算，可以實現(xiàn)多個數(shù)量級的性能改進。

3. 微分計算

在本節(jié)中，我們將描述差分計算如何跟蹤更改并更新其狀態(tài)。由于我們將在后面的部分中使用計算來實現(xiàn)數(shù)據(jù)并行數(shù)據(jù)流，因此我們在這里采用數(shù)據(jù)并行數(shù)據(jù)流系統(tǒng)的術語。 必須適應其不斷變化的輸入的函數(shù)稱為operators ，其輸入和輸出稱為collections 。我們將集合建模為多集，其中對于集合A與記錄x，整數(shù)A（x）表示A中x的多重性。無論本文中的哪個示例描述了通用一元或二元運算符，都應假定運算符的擴展 具有兩個以上明確的輸入。

在計算的生命周期中，集合可以有多個版本，其中版本是某些部分順序的成員。特定版本的集合稱為集合軌跡，用粗體表示，定義為從偏序 的元素到集合的函數(shù); 我們用符號來表示版本t的集合。我們將看到，在一次計算中，不同的集合可能會根據(jù)不同的部分順序而變化。將操作符應用于集合跟蹤的結果本身就是集合跟蹤，這里用符號表示; 例如，對于一般的二進制運算符

計算的輸入和輸出被建模為集合軌跡，因此會按部分順序變化。通常輸入和輸出隨自然數(shù)變化，以表示連續(xù)的計算周期。

3.1 增量計算:

在增量計算中，我們?yōu)槊恳粋€的運算符考慮集合的序列: 和運算[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Fvy7bOgd-1603100189833)(C:/Users/Janus II/AppData/Roaming/Typora/typora-user-images/image-20201018114938846.png)]

最簡單的方法（相當于圖1中的“無狀態(tài)”方法）是為每個t獨立地重新執(zhí)行，如圖2所示。

當連續(xù)的A_t具有較大的交集時，我們可以通過增量評估獲得可觀的效益。 我們可以根據(jù)差異跟蹤來定義后續(xù)版本中兩個集合之間的差異，類似于集合跟蹤，并再次為集合的每個版本取一個值。 差異和差異跟蹤是使用應用于相應集合或跟蹤名稱的一個專用符號δ來表示的。

對于每個版本t>0 , 他們遵循這個公式:

注意可能為負，對應于從版本t的A中刪除記錄r。

運算符可以通過產生相應的輸出對新的做出反應，如圖3所示。增量系統(tǒng)通常會計算

并僅保留最新版本的集合

一旦將和并入各自的集合中，則將其丟棄。

對于隨后的泛化，考慮等效公式將很有幫助:

在實際的增量系統(tǒng)中，運算符被實現(xiàn)為確保通常可以按大致與成正比的時間計算，這與完全重新評估所需的相反。

增量評估和循環(huán)依賴圖可以結合起來影響迭代計算。非正式地說，對于將集合映射到集合的循環(huán)體f，可以將f的輸出重新引入到其輸入中。迭代t為某個初始集合X定義了，并且可以進行固定次數(shù)的迭代，或者直到集合停止變化。這種方法讓人想起樸素的Datalog評估, 實際上可以使用增量計算來評估Datalog程序

不幸的是，增量計算的順序性質意味著可以使用差異來更新計算的輸入集合或執(zhí)行迭代，但不能同時使用兩者。 為了同時實現(xiàn)這兩個目標，我們必須概括差異的概念，以允許使用多個先前版本，這將在下一部分中討論。

3.2 偏序推廣

這里我們介紹了微分計算，它將增量計算有機地融合在一起。數(shù)據(jù)仍然被建模為集合，但不是要求它們形成序列，而是可以部分排序。t一旦計算出來，每個個體差異就會被保留，而不是像增量系統(tǒng)那樣被并入當前的集合中。此功能使我們可以根據(jù)集合可能更改的原因來仔細組合差異，從而使差異數(shù)量大大減少，計算量也減少了。

我們必須重新定義差異，以解決沒有單個定義明確的的可能性。回到等式1，我們使用與之前完全相同的等式，但是s和t現(xiàn)在在偏序的元素范圍內，而≤使用偏序的小于關系。 然后將差定義為和之間的差。 在下一部分中，我們將提供一些具體示例。

與增量計算一樣，每個運算符都使用公式2從輸入差異確定輸出差異。重寫后，我們可以看到，每個都由和嚴格的先驗和確定：

使用偏序的一個結果是，與增量計算相反，輸入和輸出差之間不必一一對應。每個新的可能在多個不同的處產生。這使遞增運算符的邏輯復雜化，第3.4節(jié)將對此進行詳細討論。

3.3 微分計算的應用

現(xiàn)在，我們考慮差分計算的三個示例，以顯示差異的使用與先前的增量方法有何不同。 特別是，我們將概述從抽象的可組合性以及重新定義偏序以選擇集合的最合適前驅的能力中獲得的好處。

例1：增量和迭代計算

想象一個集合，它根據(jù)輸入的回合i和包含它的循環(huán)的迭代j取不同的值。 例如，在第2節(jié)的連接組件示例中，可能是從第i個輸入紀元的j跳鄰域派生的節(jié)點標簽。考慮其中的偏序

圖4顯示了基于此偏序的微分計算將如何消耗和產生差異

的一些區(qū)別很容易描述：

集合的初始值（等于）。
使前進到第二次迭代
將更新為第二個輸入。

因為（0, 1）和（1, 0）都不小于另一個，所以和都不用于另一個推導中。 如果我們必須對版本強加一個總順序，那么這種獨立性將是不可能的，因為這兩個版本中的一個必須首先出現(xiàn)，而第二個版本將被迫減去與第一個版本相關的任何差異。

考慮差異并查看其反映的變化是有益的。 回想

差異使集合的值與已經計算出的先前差異：。 請注意，并非所有先前計算出的差都被使用：即使可用，它也描述了第二次循環(huán)迭代，對于確定沒有用。 在這里，保持每個的好處變得顯而易見：最合適的差異集可以用作計算任何給定的起點。 因此，校正可能很小，實際上常常是完全空白的。 在圖1中，微分計算的幾次迭代（3、5和11之后）完全為空。
如果使用差異的總順序，則可以僅根據(jù)來定義。 盡管已經計算出（一次迭代對可能在很大程度上相同的集合的影響），但的計算將無法訪問此信息，并且會浪費精力進行一些相同的工作。 產品部分訂單更適合遭受來自兩個來源的獨立更改的集合。

示例2：優(yōu)先級和迭代計算。

微分計算也可以用于實現(xiàn)連接的組件優(yōu)化，其中最小的標簽首先在整個圖中傳播，然后是第二個最小的標簽，依此類推，直到引入所有標簽為止^[28]。 這種優(yōu)先級方法更有效，因為在組件內僅傳播最小的標簽：較大的標簽會立即遇到較小的標簽，并且不會進一步傳播。

為了實現(xiàn)此優(yōu)化，我們使用字典順序，如果，則。 每個標簽 l以優(yōu)先級l傳播，并且其傳播通過差異反映出來；當按字典順序使用時，相對于先前優(yōu)先級采用計算極限而不是。 這樣可以減少差異，因為標簽l的進度會在收到任何較低標簽的頂點上立即受到阻礙。 所產生的順序依賴性也減少了可用的并行性，但是在實踐中可以通過批量處理優(yōu)先級來減輕這種并行性，例如使用優(yōu)先級傳播標簽l。
此優(yōu)化是區(qū)分圖1中的增量線和優(yōu)先級線的基礎

示例3：可組合性和嵌套

差分計算的一個吸引人的特點是它的可組合性。 由于增量由迭代組成，并以迭代為優(yōu)先，我們可以輕松地將這三個方法結合起來，以使用簡單的偏序組合器（此處為整數(shù)總階與字典順序的乘積）來創(chuàng)建一個增量，有優(yōu)先權的迭代計算。 圖1中的“ 差異”線是通過增量，優(yōu)先級和迭代計算的組合獲得的。由此產生的復雜性可以向用戶隱藏，從而獲得實際的性能提升，這將在第5節(jié)中看到。
對迭組合迭代計算的支持使嵌套循環(huán)成為可能：可以使用遞增，迭代，優(yōu)先排序，迭代實現(xiàn)（四維部分順序）來計算強連接的組件。 我們在附錄中介紹了針對強連接組件的數(shù)據(jù)并行算法

3.4差分運算符

現(xiàn)在，我們描述基本的運算符實現(xiàn)，該實現(xiàn)采用根據(jù)集合定義的任意運算符，并將其轉換為差值。 在最壞的情況下，這種基本實現(xiàn)最終將重建整個集合并將其傳遞給運算符。 第4.3節(jié)說明了如何優(yōu)化微分數(shù)據(jù)流實現(xiàn)中最常見的運算符，以避免這種最壞的情況。

在執(zhí)行差分計算時，其運算符會被重復調用并帶有差異以合并到其輸入中，并且必須產生反映新差異的輸出差異軌跡。 考慮一個二進制運算符f，它已經處理了兩個相應輸入上的集合軌跡 A和B的一系列更新。 假設必須將新的差異和應用于其各自的輸入，其中差異和均具有版本。
式（3）用差軌跡表示對f輸出的最終更新，公式（3）表明：

當at滿足

對于b也一樣

通過對t的歸納可以清楚地看出，當時，這反映出一種自然的直覺，即更新版本上的差異不會導致對之前的版本進行任何修改。 可能更令人驚訝的是，對于所有，即使，也可能存在的版本，其中。 幸運的是，可能需要更新的版本集并不是無限的，實際上，可以證明，如果，則，其中T是的上界和一些非零增量的

為了有效地計算任意輸入的，我們的基本運算符必須將其完整的輸入微分軌跡和存儲在內存中。 在Naiad原型實現(xiàn)中，此跟蹤存儲在三重嵌套的稀疏計數(shù)數(shù)組中，首先由鍵k，然后由點陣版本t，然后由記錄r。 Naiad僅維護非零計數(shù)，并且當記錄被添加到差異跟蹤中或從差異跟蹤中減去時，Naiad會動態(tài)調整分配的內存。
借助按版本索引的和，可以針對任何t重建和，并使用算法1的偽代碼顯式計算。盡管重建似乎很昂貴，并且與增量計算背道而馳，但必須能夠支持程序員可以為其指定任意（非增量）函數(shù)來處理所有記錄的完全通用運算符。 我們很快將看到許多特定的運算符具有更有效的實現(xiàn)。
一種對算法1中算法的一般優(yōu)化，減少了重建和值所花費的精力。
系統(tǒng)可以更新先前計算出的集合（例如，版本的），而不是針對每個t遍歷所有s <t。 這樣做只涉及差異

這通常導致需要更新的s相對較少，例如在循環(huán)索引前進的情況下僅需要更新一個。 通過確保按照尊重偏序的順序處理差異，系統(tǒng)僅需要從和t的最大下限開始掃描，直到同時通過和t。 另外，如果可用一個以上的版本τ進行更新，則可以對它們進行批處理，從而再次潛在地減少了需要重建的集合數(shù)量和f的評估數(shù)量。

上面的解釋假設微分軌跡將無限期保持，因此算法1中s <t上的重建循環(huán)的成本將隨著t的增加而無限制地增長。 實際上，可以將視為到目前為止已發(fā)生的（部分排序）更新日志。 如果我們知道對于t <的任何版本都不會收到進一步的更新，那么直到[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-9peZ93Nz-1603100190265)(https://gitee.com/janusv/typora-pic-bed/raw/master/img/20201018171935.png)]版本的所有更新都可以合并到一個檢查點中，從而可以節(jié)省存儲成本和重建工作。 Naiad原型包括此合并步驟，但細節(jié)不在本文討論范圍之內。

4.微分數(shù)據(jù)流

現(xiàn)在，我們介紹差分計算的實現(xiàn)：微分數(shù)據(jù)流。 如第6節(jié)所述，增量計算已在多種設置中引入。 我們?yōu)椴罘钟嬎愕牡谝粋€實現(xiàn)選擇了一個聲明性數(shù)據(jù)流框架，因為我們認為它非常適合作為主要動機應用程序的數(shù)據(jù)并行分析任務。
與有關查詢計劃和數(shù)據(jù)并行處理的現(xiàn)有工作相同，我們將數(shù)據(jù)流計算建模為有向圖，其中頂點對應于程序輸入，程序輸出或運算符（例如Select，Join，GroupBy），并且邊表示使用 一個頂點的輸出作為另一個頂點的輸入。 通常，數(shù)據(jù)流圖可能具有多個輸入和輸出。 數(shù)據(jù)流圖可能是循環(huán)的，但是在本文的框架中，我們僅允許系統(tǒng)引入循環(huán)以支持定點子計算。

4.1 語言

我們的聲明式查詢語言基于.NET語言集成查詢（LINQ）功能，該功能通過聲明性運算符（例如Select，Where，Join和GroupBy等）擴展了C＃，這些運算符應用于強類型集合^[5]。 每個運算符對應一個數(shù)據(jù)流頂點，具有來自一個或兩個源運算符的輸入邊。
我們使用兩種新的查詢方法擴展LINQ，以利用不同的數(shù)據(jù)流：

FixedPoint接受一個源集合(某個記錄類型T的集合)以及從T的集合到相同類型的集合的函數(shù)。 該函數(shù)表示循環(huán)的主體，并且可以包括嵌套的FixedPoint調用； 它會產生一個循環(huán)數(shù)據(jù)流子圖，其中主體的結果將反饋給下一個循環(huán)迭代。
PrioritizedFP還具有一個函數(shù)priorityFunc，該函數(shù)應用于源集合中的每個記錄，并表示這些記錄應該被引入主體的順序。 對于每個唯一優(yōu)先級，依次將具有該優(yōu)先級的記錄添加到當前狀態(tài)，并且循環(huán)迭代到到目前為止引入的記錄上的定點收斂。 我們將在以下小節(jié)中更精確地解釋語義。
這兩種方法將任意微分數(shù)據(jù)流查詢作為其主體，其中可能包括進一步的循環(huán)和排序指令。 系統(tǒng)管理部分訂單的復雜性，并向用戶隱藏細節(jié)。

4.2集合數(shù)據(jù)流

在本小節(jié)中，我們描述如何將使用上面的聲明性語言編寫的程序轉換為循環(huán)數(shù)據(jù)流圖。 我們在標準數(shù)據(jù)流模型中描述圖，在該模型中，運算符可立即對整個集合進行操作，因為這簡化了運算符語義的描述。 在4.3節(jié)中，我們將描述如何修改數(shù)據(jù)流運算符以對差異進行操作，而4.4節(jié)將概述系統(tǒng)如何調度計算。

回顧3.2節(jié)，集合軌跡根據(jù)部分順序進行版本控制的模型集合。 我們要求對運算符的所有輸入都以相同的部分順序變化，但是對于我們考慮的所有部分訂單，都存在一個簡單的訂單嵌入，該嵌入是使用Extend運算符實現(xiàn)的：

Extend運算符允許在定點循環(huán)外定義的集合在其中使用。 例如，連接的組件計算中的邊集合相對于循環(huán)迭代i是恒定的，并且在引用循環(huán)中的邊時使用Extend。
標準LINQ運算符（例如Select，Where，GroupBy，Join和Concat）每個都對應于數(shù)據(jù)流圖中的單個頂點，并且將其通常的集合語義提升為適用于集合跟蹤。

定點運算符

盡管定點運算符非正式地像一個循環(huán)體和一個后沿一樣簡單，但是我們必須仔細處理與循環(huán)索引相對應的新整數(shù)坐標的引入和移除。 可以使用三個新的運算符來構建定點循環(huán)（圖5）：擴展部分順序以包括新整數(shù)坐標的入口頂點，將循環(huán)體的輸出作為后續(xù)迭代的輸入的反饋頂點，以及 一個出口頂點，它從部分順序中剝離循環(huán)索引并返回固定點。 （使用標準的Concat運算符來合并入口和反饋頂點的輸出）更準確地說，如果輸入集合X已經以偏序T變化，則入口運算符會產生隨變化的軌跡。

反饋運算符獲取循環(huán)主體的輸出并提高其循環(huán)索引。 對于循環(huán)體W的輸出，我們有

最后，egress運算符觀察循環(huán)體的輸出，并發(fā)出第一個重復的集合

對于這些運算符的實現(xiàn)，我們沒有說什么具體的，但是在這個極限存在的地方, 它們的數(shù)學定義應該清楚地表明：

優(yōu)先定點運算符

此運算符為集合中的每個記錄分配一個優(yōu)先級，并使用此優(yōu)先級對將記錄引入定點循環(huán)施加總順序。 從一個空集合開始，運算符按順序將下一個未引入優(yōu)先級的記錄引入到集合中，迭代到一個固定點（如上所述），并將結果用作下一個優(yōu)先級的起點。
優(yōu)先級定點運算符使用與未優(yōu)先級定點運算符相同的數(shù)據(jù)流模板，包括入口，反饋，出口和Concat運算符（圖5），但是它具有不同的語義。 入口運算符為每個記錄的版本添加兩個坐標，分別對應于其評估的優(yōu)先級（p）和初始迭代（i = 0）：

其中P（r）是對記錄r的priorityFunc的求值。
如第3.3小節(jié)所述，附加坐標（p; i）按字典順序排序。
反饋運算符的作用更為復雜。 對于每個優(yōu)先級的第零次迭代，它會反饋先前優(yōu)先級迭代的固定點； 否則，它的行為就像無優(yōu)先權的反饋一樣。

最后，將egress運算符修改為在插入最終優(yōu)先級之后發(fā)出定點：

4.3運算符的實現(xiàn)

3.4節(jié)概述了差分運算符的一般實現(xiàn)。 盡管可以使用通用運算符更新算法來實現(xiàn)任何微分數(shù)據(jù)流運算符，但我們還是專門實現(xiàn)了以下運算符，以實現(xiàn)更好的性能：數(shù)據(jù)并行運算。

利用數(shù)據(jù)并行結構是從微分數(shù)據(jù)流中受益的最有效方法之一。 對于數(shù)據(jù)流中的每個運算符實例f，假定存在一個鍵類型K，以及為每個運算符輸入定義的鍵函數(shù)，該鍵函數(shù)將該輸入中的記錄映射到K。鍵空間定義f的獨立性概念，可以 被寫成

其中限制根據(jù)其關聯(lián)的鍵功能鍵定義為

由于映射到不同鍵的記錄子集可以在不同的CPU或計算機上進行處理而無需同步，因此在許多系統(tǒng)中都利用了這種獨立性來并行化計算。 微分數(shù)據(jù)流系統(tǒng)可以以相同的方式利用并行性，但同時也可以從以下事實中受益匪淺：對集合的更新可以隔離到傳入差異中存在的鍵，因此運算符只需對對應的集合子集執(zhí)行工作。 在通常情況下，傳入差異的大小和處理差異的計算成本都與這些子集的大小大致成比例。 很容易修改算法1中的偽代碼，使其僅對映射到鍵k的記錄進行操作，并且由于和由鍵索引，因此很容易只對對應的和子集進行工作

諸如Join和GroupBy之類的運算符自然會在其語義中包含關鍵功能。 對于諸如Count，Sum和Min的聚合，我們采用了一種稍微不標準的定義，該定義有效地為每個運算符添加了GroupBy。
例如，Count需要一個鍵函數(shù)并返回一組計數(shù)，該計數(shù)與映射到集合中每個唯一鍵的記錄數(shù)相對應。 通過指定將每個記錄映射到相同鍵的常量鍵函數(shù)，可以獲得這些運算符的標準行為。

流水線運算符

包括Select，Where，Concat和Except在內的多個運算符是線性的，這意味著它們可以將δz確定為僅取決于δa的函數(shù)，而與δA無關。 這些運算符可以與前面的運算符進行流水線化，因為它們不需要維護任何狀態(tài)，也不需要基于關鍵字對記錄進行分組：它們將逐記錄邏輯應用于δa ----非零元素，分別進行轉換，過濾， 重復和否定輸入記錄。

Join

Join運算符通過計算這些輸入的笛卡爾積來組合兩個輸入集合，并且只生成兩個輸入記錄都具有的記錄。 由于Join的分布特性，輸入和輸出之間的關系很簡單

盡管Join的實現(xiàn)仍必須保持其輸入差異跟蹤常駐，但其實現(xiàn)比一般情況要簡單得多。 輸入δa可以直接與δB的非零元素連接，并且對于δb和δA可以類似地連接，而無需遵循算法1中的重建邏輯。

集合體

許多數(shù)據(jù)并行聚合具有非常簡單的更新規(guī)則，不需要重新評估所有記錄。
例如，Count只需要保留由累積權重定義的每個鍵的記錄數(shù)差異記錄，而不是映射到該鍵的記錄集。 Sum具有類似的優(yōu)化。 最小值和最大值必須保持其完整的輸入差異軌跡，因為最小（最大）元素的縮回會導致第二（最小）記錄成為新輸出，但通常可以通過與更新進行比較來快速確定更新而不需要輸出 無需重構A的先前輸出

定點運算符

4.2節(jié)中的Extend，Ingress，Feedback和Egress運算符具有簡單的差分實現(xiàn)。
Extend運算符為任何i報告相同的輸出，因此

Ingress運算符將其輸出從零更改為，然后又恢復為零，要求輸出形式為

反饋運算符最初為零，但隨著其輸入的先前迭代更改而更改

Egress運算符產生最終看到的輸出，這是到目前為止看到的所有累積的結果

非正式地講，Ingress添加了一個新的循環(huán)索引，并為看到的每個輸入生成了正輸出和負的輸出； Feedback推進了看到的每個輸入的循環(huán)索引，而Egress刪除了看到的每個輸入的循環(huán)索引。 優(yōu)先定點運算符PIngress，PFeedback和PEgress的不同實現(xiàn)遵循類似的方式

4.4調度微分數(shù)據(jù)流

調度微分數(shù)據(jù)流計算的執(zhí)行由于需要協(xié)調循環(huán)數(shù)據(jù)依賴性而變得很復雜。 在我們的Naiad原型中，調度程序會跟蹤在每個運算符處處理的未解決差異，并使用數(shù)據(jù)流圖的拓撲對這些差異施加部分順序，從而使系統(tǒng)能夠對其進行拓撲排序，從而獲得有效的調度 。 面臨的挑戰(zhàn)是，與每個差異相關聯(lián)的版本在同一運算符上對兩個未完成的差異進行排序，但是對于兩個不同的運算符存在未完成的差異，則什么也沒有說。

從直覺上講，存在因果關系的概念：如果處理d1可能會導致版本的產生新數(shù)據(jù)，則版本s的運算符與版本s的差d1因果先于的版本t。 回顧一下第4.2節(jié)，有些運算符修改了輸入差異的版本：例如，未優(yōu)先級的Feedback運算符使版本的最后一個坐標前進。 調度程序將此信息與數(shù)據(jù)流圖的邊緣關系結合起來，以確定因果順序并確定一組最小的未完成差異。 此后，重復安排最小差異之一可確保前進。
一些迭代的數(shù)據(jù)并行系統(tǒng)依賴于顯式的收斂性測試[7、20、25]，而在微分數(shù)據(jù)流系統(tǒng)中，由于沒有差異而隱含了收斂性。
因此，如果沒有明顯的差異，則所有輸入都已處理，所有循環(huán)都收斂到固定點。

5.應用

為了支持這種說法，即微分數(shù)據(jù)流可以極大地提高增量計算和迭代計算的性能，我們現(xiàn)在描述一些示例應用，并介紹使用Naiad原型進行的初始性能測量¹.

5.1 Twitter連接組件

我們測量了第2節(jié)中描述的連接組件計算的每次迭代執(zhí)行時間。

我們在具有48個（四個12核）1.9GHz處理器和64GB RAM，運行Windows Server 2008 R2 Enterprise Service Pack 1的AMD 皓龍?zhí)幚砥鳌疢agnyCours’上進行了實驗。圖6顯示了遞增，優(yōu)先和差異時間。 使用8個內核執(zhí)行時（1s更改）版本的計算。 請注意，這些曲線與圖1中的差異計數(shù)具有相同的相對順序和大致相同的形狀。與圖1相比，與24小時差分計算相比，一秒鐘的更新間隔較小的數(shù)量級。 這種低于預期的提速是由于工作量很小時滲透開銷變得更加明顯。 但是，Naiad能夠在24.4毫秒內響應一秒鐘的更新； 這比差分或增量數(shù)據(jù)流使用的7.1s和36.4s快得多，這使Naiad可以實時維護Twitter提及圖的組件結構。

5.2迭代網(wǎng)絡圖算法

我們還使用了適用于ClueWeb的B類網(wǎng)絡圖的幾種圖形算法對Naiad的性能進行了評估。我們借鑒了Najork等人的工作。 [22]評估了三種算法在三種不同類型的平臺上的性能，可伸縮性和易于實現(xiàn)性：Microsoft SQL Server 2008 R2并行數(shù)據(jù)倉庫（PDW）關系數(shù)據(jù)庫，DryadLINQ [24]數(shù)據(jù)并行批處理處理器， 以及可伸縮超鏈接存儲（SHS）[21]分布式內存中圖形存儲。 為了進行直接比較，我們在Najork等人使用的同一實驗集群上運行Naiad的分布式版本：16臺服務器，具有8個內核（兩個2.66GHz四核Intel Xeon E5430處理器）和16GB RAM，所有服務器均連接到 一臺千兆以太網(wǎng)交換機。
表1列出了Naiad的總體改進，這是因為Naiad具有以下功能：它在內存中存儲索引數(shù)據(jù)，在許多工作程序上分布計算以及在收斂時加速迭代計算的能力。值得注意的是，每個其他系統(tǒng)僅實現(xiàn)修整 -SCC的處理步驟，然后在簡化圖上運行單線程SCC； Naiad能夠將SCC計算表示為聲明性雙嵌套定點計算，并在整個集群中分配全部執(zhí)行。 這些工作負載都不是交互性的，并且這些評估并未利用Naiad支持增量更新的能力。 但是，每個計算都會自動遞增，并且可以有效地響應輸入圖的變化。

6.相關工作

已經研究了許多增量執(zhí)行方法。 據(jù)我們所知，微分數(shù)據(jù)流是第一個支持將任意嵌套迭代與輸入數(shù)據(jù)的有效添加和刪除相結合的技術。 但是，現(xiàn)有的增量計算研究發(fā)現(xiàn)了可能與微分計算互補的技術，在本節(jié)中，我們試圖在此領域的相關工作之間建立聯(lián)系。

增量視圖維護

如前所述，微分數(shù)據(jù)流解決了與增量視圖維護（IVM）解決的問題類似的問題，增量目標維護是為了在基于稍有不同的輸入計算新視圖時重用對先前輸入所做的工作。 在過去的三十年中，受支持的查詢集已經從簡單的select-project-join查詢[6]增長到完全通用的遞歸查詢[15，23]。 盡管后一種技術非常廣泛，但對于交互式大規(guī)模計算卻不是理想的選擇，因為它們要么執(zhí)行過多的工作，要么保持過多的狀態(tài)，要么限制了表達能力。 Gupta等人的經典DRed算法[15]可以高估無效元組的集合，并且在最壞的情況下，將執(zhí)行大量工作來“消除”已刪除元組的影響，只是得出以下結論： Nigam等人的擴展PSN算法[23]依賴于每個元組存儲用于導出它的完整元組集合，這可能需要大量的狀態(tài)。 Ahmad等人改進了包含高階聯(lián)接的查詢的增量性能，但目前不支持迭代工作量[3]；這種方法可以適應包含這種聯(lián)接的差分程序的好處。

增量數(shù)據(jù)流

像MapReduce和Dryad這樣的數(shù)據(jù)流系統(tǒng)已經擴展，并支持增量計算。 康迪等。 開發(fā)了MapReduce Online [8]，它可以在內存中維護MapReduce作業(yè)鏈的狀態(tài)，并對其他輸入記錄做出有效反應。 增量數(shù)據(jù)流對于粗粒度更新也很有用：Gunda等。
隨后開發(fā)的Nectar [14]緩存了DryadLINQ程序的中間結果，并使用LINQ運算符的語義生成了利用緩存的增量程序。 Incoop項目[4]通過將輸入緩存到reduce階段，并仔細確保在更改輸入后重新執(zhí)行最少數(shù)量的reducers，從而為任意MapReduce程序提供類似的好處。 這些系統(tǒng)都不支持迭代算法，相反，它們是為處理非常大的數(shù)據(jù)的高吞吐量而設計的。

迭代數(shù)據(jù)流

為了擴展數(shù)據(jù)流系統(tǒng)的通用性，一些研究人員研究了將數(shù)據(jù)依賴的控制流構造添加到并行數(shù)據(jù)流系統(tǒng)的方法。
HaLoop [7]是MapReduce的擴展版本，可以通過重復執(zhí)行MapReduce作業(yè)鏈直到滿足數(shù)據(jù)相關的停止條件，來執(zhí)行以遞歸SQL變體編寫的查詢。 類似的系統(tǒng)包括Twister [12]和iMapReduce [27]。 Spark [25]支持類似于DryadLINQ的編程模型，并為頻繁重復使用的輸入添加了顯式的內存中緩存。 Spark還提供了“彈性分布式數(shù)據(jù)集”抽象，允許在發(fā)生故障時重建緩存的輸入。所有這些系統(tǒng)都使用類似于4.2節(jié)中描述的面向集合的數(shù)據(jù)流的執(zhí)行策略，并且將執(zhí)行 D-Streams [26]通過執(zhí)行一系列小批量計算來擴展Spark來處理流輸入，但它不支持迭代。D-Streams[26]擴展了Spark以處理流輸入。 CIEL分布式執(zhí)行引擎[20]提供了基于“動態(tài)任務圖”的通用執(zhí)行模型，該模型可以對嵌套迭代進行編碼；但是，由于CIEL不支持可變數(shù)據(jù)對象，因此對運算符進行細化的修改進行編碼是不切實際的。
最近，已經開發(fā)了一些支持增量定點迭代的迭代數(shù)據(jù)流系統(tǒng)，這些系統(tǒng)實現(xiàn)了與圖1中“ Incremental”行成比例的性能。Ewen等人擴展了Nephele執(zhí)行引擎，并支持“ bulk”和“ incremental”。 迭代[13]，其中可以使用對當前狀態(tài)的一系列增量更新來執(zhí)行單調迭代算法。Mihaylov等人開發(fā)了REX [19]，它還支持增量迭代中的記錄刪除，但程序員負責編寫 用戶定義函數(shù)（UDF）的增量版本。差分運算符更新算法（算法1）會自動增量許多UDF，但是缺少部分更新順序會限制其用途。最后，Conway等人最近引入了BloomL [ 9]，它支持使用各種單調函數(shù)的組合進行定點迭代，這種方法的優(yōu)點是 可以在無阻塞的分布式系統(tǒng)中執(zhí)行此類程序，這可能比Naiad當前的調度策略（第4.4節(jié)）更為有效，但它不支持撤消或非單調計算。

替代執(zhí)行模型

已經開發(fā)了自動技術來遞增除數(shù)據(jù)流以外的編程模型。 純函數(shù)程序的基本技術是備忘錄[18]，該備忘錄已應用于多種現(xiàn)有系統(tǒng)[14，20]。 Acar率先推出了自調整計算[1]，它可以通過記錄執(zhí)行跟蹤并僅重播跟蹤變量中發(fā)生突變時直接受影響的那些部分，來自動遞增具有可變狀態(tài)的程序。 盡管可以將自調整計算的一般方法應用于任何程序，但使用"traceable“數(shù)據(jù)類型[2]通常更為有效，這些數(shù)據(jù)類型是支持高級查詢和更緊湊操作的抽象數(shù)據(jù)類型。 跟蹤中的表示形式。
響應式命令式編程[11]是一種使用數(shù)據(jù)流約束條件來執(zhí)行程序狀態(tài)更新的編程模型：運行時跟蹤“響應式”變量的突變，這可能會觸發(fā)對依賴于那些變量的約束條件的評估。這些程序中的約束可以是循環(huán)的，這使得連接組件和單源最短路徑等算法可以在這個模型中表達。但是，只有在約束對程序狀態(tài)具有單調影響的程序中才能保證收斂, 這使得在反應性命令式程序中很難表示邊緣刪除。
原則上，可跟蹤的數(shù)據(jù)類型或高級數(shù)據(jù)流約束可用于實現(xiàn)差分計算。 此外，在許多情況下，微分數(shù)據(jù)流可能會受益于遞增的用戶定義函數(shù)（尤其是用戶定義的GroupBy約簡函數(shù)），并且自調整計算技術提供了自動執(zhí)行此操作的潛力。

7. 結論

我們已經提出了差分計算，它概括了增量計算的現(xiàn)有技術。 差分計算的獨特之處在于，它可以通過通用增量更新實現(xiàn)任意嵌套的迭代計算。 我們對Naiad的初步實驗----數(shù)據(jù)并行微分數(shù)據(jù)流系統(tǒng)----展示了該技術可以使以前難以處理的應用程序實現(xiàn)，并在一些實際應用程序中實現(xiàn)最先進的性能。

在數(shù)據(jù)流的背景下，這些有希望的結果使我們得出結論，差分計算技術值得進一步研究，并且有可能類似地增強其他形式的增量計算。

8. 參考文獻

[1] U. A. Acar. Self-adjusting computation. PhD thesis, Carnegie Mellon University, 2005.

[2] U. A. Acar, G. Blelloch, R. Ley-Wild, K. Tangwongsan, and D. Turkoglu. Traceable data types for self-adjusting computation. In ACM PLDI, 2010

[3] Y. Ahmad, O. Kennedy, C. Koch, and M. Nikolic.
DBToaster: Higher-order delta processing for dynamic, frequently fresh views. In 38th VLDB, Aug.
2012.

[4] P. Bhatotia, A. Wieder, R. Rodrigues, U. A. Acar, and R. Pasquini. Incoop: MapReduce for incremental computations. In 2nd ACM SOCC, Oct. 2011.

[5] G. M. Bierman, E. Meijer, and M. Torgersen. Lost in translation: Formalizing proposed extensions to C]. In 22nd OOPSLA, Oct. 2007.

[6] J. A. Blakeley, P.-? A. Larson, and F. W. Tompa.
Efficiently updating materialized views. In 1986 ACM SigMod, 1986.

[7] Y. Bu, B. Howe, M. Balazinska, and M. D. Ernst.
HaLoop: Efficient iterative data processing on large clusters. In 36th VLDB, Sept. 2010.

[8] T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy, and R. Sears. MapReduce Online. In 7th USENIX NSDI, 2010.

[9] N. Conway, W. R. Marczak, P. Alvaro, J. M.
Hellerstein, and D. Maier. Logic and lattices for distributed programming. In 3rd ACM SOCC, 2012.

[10] J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In 6th USENIX OSDI, 2004.
computations. In 2nd ACM SOCC, Oct. 2011.

[10] J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In 6th USENIX OSDI, 2004.

[11] C. Demetrescu, I. Finocchi, and A. Ribichini. Reactive imperative programming with dataflow constraints. In 26th OOPSLA, 2011.

[12] J. Ekanayake, H. Li, B. Zhang, T. Gunarathne, S.-H.
Bae, J. Qiu, and G. Fox. Twister: a runtime for iterative MapReduce. In 19th ACM HPDC, June 2010.

[13] S. Ewen, K. Tzoumas, M. Kaufmann, and V. Markl.
Spinning fast iterative data flows. In 38th VLDB, 2012.

[14] P. K. Gunda, L. Ravindranath, C. A. Thekkath, Y. Yu, and L. Zhuang. Nectar: automatic management of data and computation in datacenters.
In 9th USENIX OSDI, Oct. 2010.

[15] A. Gupta, I. S. Mumick, and V. S. Subrahmanian.
Maintaining views incrementally. In 1993 ACM SigMod, 1993.

[16] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly.
Dryad: Distributed data-parallel programs from sequential building blocks. In EuroSys, Mar. 2007.

[17] G. Malewicz, M. H. Austern, A. J. C. Bik, J. C.
Dehnert, I. Horn, N. Leiser, and G. Czajkowski.
Pregel: a system for large-scale graph processing. In 2010 ACM SigMod, June 2010.

[18] D. Michie. \Memo" functions and machine learning.
Nature, (218):19{22, Apr. 1968.

[19] S. R. Mihaylov, Z. G. Ives, and S. Guha. REX: recursive, delta-based data-centric computation. In 38th VLDB, 2012.

[20] D. G. Murray, M. Schwarzkopf, C. Smowton, S. Smith, A. Madhavapeddy, and S. Hand. CIEL: a universal execution engine for distributed data-flow computing. In 8th USENIX NSDI, Mar. 2011.

[21] M. Najork. The scalable hyperlink store. In 20th ACM Conference on Hypertext and Hypermedia, 2009.

[22] M. Najork, D. Fetterly, A. Halverson, K. Kenthapadi, and S. Gollapudi. Of hammers and nails: An empirical comparison of three paradigms for processing large graphs. In 5th ACM WSDM, Feb. 2012.

[23] V. Nigam, L. Jia, B. T. Loo, and A. Scedrov.
Maintaining distributed logic programs incrementally.
In 13th ACM PPDP, July 2011.

[24] Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P. K. Gunda, and J. Currey. DryadLINQ: A system for general-purpose distributed data-parallel computing using a high-level language. In 8th USENIX OSDI, Dec. 2008.

[25] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, and I. Stoica.
Resilient Distributed Datasets: A fault-tolerant abstraction for in-memory cluster computing. In 9th USENIX NSDI, Apr. 2012.

[26] M. Zaharia, T. Das, H. Li, S. Shenker, and I. Stoica.
Discretized streams: An efficient and fault-tolerant model for stream processing on large clusters. In 4th USENIX HotCloud, 2012.

[27] Y. Zhang, Q. Gao, L. Gao, and C. Wang. iMapReduce: A distributed computing framework for iterative computation. In 1st International Workshop on Data Intensive Computing in the Clouds, May 2011.

[28] Y. Zhang, Q. Gao, L. Gao, and C. Wang. PrIter: A distributed framework for prioritized iterative computations. In 2nd ACM SOCC, Oct. 2011.

演示：

滑動強連接組件在此演示中，我們將展示Naiad如何計算從Twitter流的時間窗口提取的提及圖的強連接組件（SCC）結構，然后將其擴展以構建使用Naiad的交互式應用程序 跟蹤窗口隨時間前后滑動時這些組件的演變。

背景

經典的SCC算法基于深度優(yōu)先搜索，并且不容易并行化。 但是，通過在外部FixedPoint中嵌套兩個連接的組件查詢（圖7），我們可以使用Naiad（圖8）編寫數(shù)據(jù)并行版本。 嚴格來說，ConnectedComponents查詢計算定向可達性，并且SCC算法反復刪除其端點到達不同組件且因此必須位于不同SCC中的邊。
通過反轉每次迭代中的邊緣，以交替的方向迭代地修剪圖形，最終收斂到僅包含端點在相同SCC中的那些邊緣的圖形。
盡管Naiad的聲明性語言使嵌套FixedPoint循環(huán)變得簡單明了，但是生成的數(shù)據(jù)流圖卻相當復雜。 圖9顯示了簡化版本，其中為了清晰起見將一些頂點組合在一起：在我們當前的實現(xiàn)中，該程序的實際數(shù)據(jù)流圖包含58個頂點。 盡管如此，SCC程序接受增量更新，并且微分數(shù)據(jù)流使雙重嵌套定點計算能夠在其輸入發(fā)生更改時有效地做出響應。

演示

交互式演示顯示Naiad繼續(xù)執(zhí)行上述SCC查詢。 輸入的是來自整個Twitter firehose的一個月的推文，我們在給定的時間范圍內計算由Twitter提及圖形成的SCC。 圖形化的前端使我們可以向前和向后滑動感興趣的窗口（至少一秒鐘的步長），并顯示隨著Naiad系統(tǒng)遞增地重新執(zhí)行查詢，SCC的集合如何變化。 另外，我們對每個連續(xù)的SCC計算結果保持連續(xù)的top-k查詢，并顯示每個組件中最流行的主題標簽。
當產生增量輸出時（相對于Twitter流實時），GUI會自動刷新以顯示Naiad計算的SCC的相對大小和最受歡迎的術語。 然后，用戶可以在窗口中調查“熱門話題”，我們甚至可以將特定的對話與當時發(fā)生的實際事件相關聯(lián)（例如，在大約同一時間，我們看到一個包含＃標簽的組件） 一場重要的棒球比賽）。
該演示突出顯示了Naiad在執(zhí)行包含雙重嵌套循環(huán)的復雜增量查詢時的響應能力。 我們認為，SCC代表了復雜的數(shù)據(jù)分析，而該分析在從數(shù)據(jù)倉庫和科學應用程序到Web應用程序和社交網(wǎng)絡的范圍內越來越重要。 我們的演示強調了在單個聲明式查詢中有效組合增量更新，迭代計算和交互式數(shù)據(jù)分析的功能

總結

以上是生活随笔為你收集整理的Differential dataflow 微分数据流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。