Bazel 的平行評估和增量模型。
資料模型
資料模型包含下列項目:
SkyValue
,又稱為節點。SkyValues
是不可變動的物件,其中包含建構過程中建立的所有資料,以及建構作業的輸入內容。例如:輸入檔案、輸出檔案、目標和已設定的目標。SkyKey
:用於參照SkyValue
的簡短不可變名稱,例如FILECONTENTS:/tmp/foo
或PACKAGE://foo
。SkyFunction
:根據節點的鍵和依附節點建構節點。- 節點圖表。包含節點之間相依性關係的資料結構。
Skyframe
. Bazel 所依據的增量評估架構的程式碼名稱。
評估
建構作業包括評估代表建構要求的節點 (這是我們努力要達到的狀態,但有許多舊程式碼會妨礙這項作業)。系統會先找到 SkyFunction
,然後使用頂層 SkyKey
的鍵呼叫該類別。接著,函式會要求評估所需的節點,以便評估頂層節點,這會導致其他函式呼叫,如此類推,直到葉節點為止 (通常是代表檔案系統中輸入檔案的節點)。最後,我們會取得頂層 SkyValue
的值、一些副作用 (例如檔案系統中的輸出檔案),以及建構作業中涉及的節點之間的依附元件有向無環圖。
如果 SkyFunction
無法預先指出執行工作所需的所有節點,則可在多個階段中要求 SkyKeys
。舉個簡單的例子,假設您要評估的輸入檔案節點其實是符號連結,函式會嘗試讀取檔案,並發現該檔案是符號連結,因此會擷取代表符號連結目標的檔案系統節點。但這本身可以是符號連結,在這種情況下,原始函式也需要擷取目標。
程式碼中,這些函式由 SkyFunction
介面代表,而服務則由名為 SkyFunction.Environment
的介面提供。函式可執行以下操作:
- 透過呼叫
env.getValue
要求評估其他節點。如果節點可用,系統會傳回該節點的值,否則會傳回null
,而函式本身應會傳回null
。在後者情況下,系統會評估依附的節點,然後再次叫用原始節點建構工具,但這次相同的env.getValue
呼叫會傳回非null
值。 - 請呼叫
env.getValues()
,要求評估多個其他節點。這兩種方法的運作方式大致相同,唯一差別是會並行評估依附的節點。 - 在叫用期間執行運算
- 有副作用,例如將檔案寫入檔案系統。請注意,兩個不同的函式不得互相干擾。一般來說,寫入副作用 (資料從 Bazel 流出) 是可以接受的,但讀取副作用 (資料從 Bazel 流入,但未註冊相依性) 則不行,因為這是未註冊的相依性,可能會導致不正確的增量建構作業。
SkyFunction
實作項目不應以任何其他方式存取資料,而應要求依附元件 (例如直接讀取檔案系統),因為這會導致 Bazel 未在所讀取的檔案上註冊資料依附元件,進而導致不正確的增量建構。
函式取得足夠的資料來執行工作後,應傳回非 null
值,表示已完成。
這種評估策略有許多優點:
- 密封性。如果函式只會依賴其他節點來要求輸入資料,Bazel 就能保證,如果輸入狀態相同,就會傳回相同的資料。如果所有 Sky 函式都是確定性的,則整個版本也會是確定性的。
- 正確且完美的增量。如果所有函式的所有輸入資料都已記錄,Bazel 就能在輸入資料變更時,只讓需要失效的節點失效。
- 平行處理。由於函式只能透過要求依附元件來相互互動,因此不相依附的函式可以同時執行,Bazel 可保證結果與依序執行時相同。
成效增幅
由於函式只能依賴其他節點來存取輸入資料,因此 Bazel 可以建立從輸入檔案到輸出檔案的完整資料流圖,並使用這項資訊,只重建實際需要重建的節點:變更的輸入檔案集合的反向傳遞閉包。
具體來說,有兩種可能的漸進策略:自下而上和自上而下。最適合的選項取決於依附元件圖的樣貌。
在自底向上的無效化期間,建構圖表並瞭解變更的輸入集之後,所有依序依附於變更檔案的節點都會失效。如果我們知道同一個頂層節點會再次建構,這會是最佳做法。請注意,由下而上的無效化作業必須針對先前建構作業的所有輸入檔案執行
stat()
,才能判斷這些檔案是否已變更。您可以使用inotify
或類似機制,瞭解變更檔案的情況,藉此改善此問題。在由上而下的無效化期間,系統會檢查頂層節點的傳遞閉包,並只保留傳遞閉包為空的節點。如果我們知道目前的節點圖表很大,但在下一個版本中只需要其中的一小部分,那麼這會是較好的做法:自下而上的無效化會使第一個版本的大型圖表失效,而自上而下的無效化只會檢查第二個版本的小型圖表。
我們目前只會進行自下而上的無效化作業。
為了進一步提升增量性,我們使用了變更修剪:如果節點失效,但在重建時發現新值與舊值相同,則因該節點變更而失效的節點會「復活」。
舉例來說,如果有人變更 C++ 檔案中的註解,那麼從該檔案產生的 .o
檔案會保持不變,因此我們不需要再次呼叫連結器。
遞增連結 / 編譯
這個模型的主要限制是,節點的失效情形是全有或全無的:當依附元件變更時,依附節點一律會從頭重建,即使有更好的演算法可根據變更變更節點的舊值,也是如此。以下列舉幾個實用範例:
- 增量連結
- 當
.jar
中的單一.class
檔案發生變更時,我們理論上可以修改.jar
檔案,而非從頭開始建構。
Bazel 目前不以原則方式支援這些功能 (我們已在某種程度上支援逐步連結,但並未在 Skyframe 中實作),原因有二:我們只能獲得有限的效能提升,且難以保證突變結果與重新建構的結果相同,而 Google 重視的是可逐位元重複的版本。
到目前為止,只要簡單地分解耗時的建構步驟,並以這種方式進行部分重新評估,我們就能一貫獲得足夠好的效能:分解應用程式中的所有類別,並分別對這些類別進行解析。這樣一來,如果群組中的類別沒有變更,就不需要重新執行解析作業。
對應至 Bazel 概念
以下是 Bazel 用來執行建構作業的部分 SkyFunction
實作方式概略說明:
- FileStateValue。
lstat()
的結果。對於現有檔案,我們也會計算其他資訊,以便偵測檔案的變更。這是 Skyframe 圖表中最低層級的節點,沒有任何依附元件。 - FileValue。此類別會用於任何需要檔案實際內容和/或已解析路徑的項目。取決於對應的
FileStateValue
和需要解析的任何符號連結 (例如a/b
的FileValue
需要a
的解析路徑,以及a/b
的解析路徑)。FileStateValue
之間的差異很重要,因為在某些情況下 (例如評估檔案系統 glob (例如srcs=glob(["*/*.java"])
) 時),檔案內容實際上並不需要。 - DirectoryListingValue。基本上是
readdir()
的結果。取決於與目錄相關聯的FileValue
。 - PackageValue。代表已剖析的 BUILD 檔案版本。取決於相關聯
BUILD
檔案的FileValue
,並且會以遞迴方式取決於用於解析套件中 glob 的任何DirectoryListingValue
(代表BUILD
檔案內容的資料結構) - ConfiguredTargetValue。代表已設定的目標,也就是在分析目標時產生的動作組合,以及提供給依賴此目標的已設定目標的資訊。取決於對應目標所在的
PackageValue
、直接依附元件的ConfiguredTargetValues
,以及代表建構設定的特殊節點。 - ArtifactValue。代表建構中的檔案,無論是來源或輸出成果皆然 (成果幾乎等同於檔案,可用於實際執行建構步驟時參照檔案)。對於來源檔案,取決於相關聯節點的
FileValue
;對於輸出構件,取決於產生構件的任何動作的ActionExecutionValue
。 - ActionExecutionValue。代表執行動作。取決於輸入檔案的
ArtifactValues
。目前執行的動作包含在 Sky 鍵中,這與 Sky 鍵應小型化的概念相違。我們正在努力解決這個差異問題 (請注意,如果未在 Skyframe 上執行執行階段,ActionExecutionValue
和ArtifactValue
就不會使用)。