Git
英文 ▾ 主題 ▾ 最新版本 ▾ 多包索引 (multi-pack-index) 最後更新於 2.47.0

Git 物件目錄包含一個 pack 目錄，其中包含 packfile（副檔名為 ".pack"）和 pack-index（副檔名為 ".idx"）。pack-index 提供了一種查詢物件並導航到它們在 pack 中的偏移量的方式，但它們必須與 packfile 成對出現。這種配對取決於檔案名稱，因為 pack-index 僅在副檔名上與其 pack 檔案不同。雖然 pack-index 為每個 packfile 提供快速查詢，但隨著 packfile 數量的增加，這種效能會下降，因為縮寫需要檢查每個 packfile，並且我們更有可能在我們最近使用的 packfile 上錯失。對於一些大型儲存庫，由於儲存空間或過長的重新打包時間，重新打包成單個 packfile 是不可行的。

多包索引（簡稱 MIDX）儲存了物件列表及其在多個 packfile 中的偏移量。它包含

  • packfile 名稱列表。

  • 排序後的物件 ID 列表。

  • 第 i 個物件 ID 的中繼資料列表，包含

    • 一個值 j，指向第 j 個 packfile。

    • 物件在第 j 個 packfile 中的偏移量。

  • 如果需要大偏移量，我們會使用另一個類似於版本 2 pack-index 的大偏移量列表。

    • pseudo-pack 順序中物件的可選列表（與 MIDX 位圖一起使用）。

因此，我們可以為任何數量的 packfile 提供 O(log N) 的查詢時間。

設計細節

  • MIDX 儲存在 .git/objects/pack 目錄下名為 multi-pack-index 的檔案中。這可以儲存在備用目錄的 pack 目錄中。它僅參考同一目錄中的 packfile。

  • core.multiPackIndex 設定必須開啟（預設為開啟）才能使用 MIDX 檔案。將其設定為 false 會阻止 Git 讀取 MIDX 檔案，即使該檔案存在。

  • 檔案格式包含物件 ID 雜湊函數的參數，因此未來雜湊演算法的變更不需要變更格式。

  • MIDX 每個物件 ID 僅保留一條記錄。如果一個物件出現在多個 packfile 中，則 MIDX 會選擇首選 packfile 中的副本，否則會從最近修改的 packfile 中選擇。

  • 如果 pack 目錄中存在未在 MIDX 中註冊的 packfile，則這些 packfile 會載入到 packed_git 列表和 packed_git_mru 快取中。

  • pack-index（.idx 檔案）保留在 pack 目錄中，因此我們可以刪除 MIDX 檔案、將 core.midx 設定為 false 或降級，而不會遺失任何資訊。

  • MIDX 檔案格式使用基於區塊的方法（類似於 commit-graph 檔案），允許新增選用資料。

增量多包索引

隨著儲存庫規模的增長，撰寫包含所有 packfile 的多包索引 (MIDX) 的成本會越來越高。「增量多包索引」功能旨在解決此問題，允許組合多包索引的「鏈」。

鏈的每個單獨組件只需要包含少量 packfile。附加到鏈不會使鏈的早期部分失效，因此儲存庫可以透過確定 MIDX 鏈中每一層的包數來控制更新 MIDX 鏈所花費的時間。

設計狀態

目前，增量多包索引功能缺少兩個重要的組件

  • 重新撰寫 MIDX 鏈早期部分的能力（即，將相鄰 MIDX 層的某些集合「壓縮」為單個 MIDX）。目前，縮減 MIDX 鏈的唯一支援方式是從頭重新撰寫整個鏈，而不使用 --split 旗標。

    沒有任何根本的限制會妨礙實作此功能。為了降低複雜性，它在初始實作中被省略，但稍後會新增。

  • 支援可達性位圖。傳統的單個 MIDX 實作確實支援可達性位圖（有關詳細資訊，請參閱 gitformat-pack[5] 中標題為「多包索引反向索引」的部分）。

    如上所述，沒有任何根本的限制會妨礙擴展增量 MIDX 格式以支援可達性位圖。下面的設計特別考慮到了這一點，並且將在未來的修補程式系列中新增對可達性位圖的支援。由於與上述相同的原因，它在目前的實作中被省略。

    簡而言之，為了支援增量 MIDX 功能的可達性位圖，pseudo-pack 順序的概念會跨增量 MIDX 鏈的每一層擴展，以形成串聯的 pseudo-pack 順序。此串聯的順序與鏈本身的順序相同（換句話說，鏈 {$H1, $H2, $H3} 的串聯 pseudo-pack 順序將是 $H1 的 pseudo-pack 順序，後跟 $H2 的 pseudo-pack 順序，然後是 $H3 的 pseudo-pack 順序）。

    然後，將擴展版面配置，以便增量 MIDX 鏈的每一層都可以寫入 *.bitmap。每一層位圖中的物件會根據鏈的前一層中的物件數量進行偏移。

檔案版面配置

增量 MIDX 不儲存單個 multi-pack-index 檔案（在 $GIT_DIR/objects/pack 中具有可選的 .rev 和 .bitmap 副檔名），而是儲存在以下版面配置中

$GIT_DIR/objects/pack/multi-pack-index.d/
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-chain
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H1.midx
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H2.midx
$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H3.midx

multi-pack-index-chain 檔案包含鏈中增量 MIDX 檔案的列表，依序排列。上面的範例顯示了一個鏈，其 multi-pack-index-chain 檔案會包含以下行

$H1
$H2
$H3

multi-pack-index-$H1.midx 檔案包含多包索引鏈的第一層。multi-pack-index-$H2.midx 檔案包含鏈的第二層，依此類推。

當同時存在增量 MIDX 和非增量 MIDX 時，始終會先讀取非增量 MIDX。

增量 MIDX 的物件位置

在原始多包索引設計中，我們透過物件在儲存庫的單個多包索引中的字典順序位置（按物件 ID）來參照物件。在增量多包索引設計中，我們透過物件在 MIDX 鏈中每個元件之間的串聯字典順序中的索引來參照物件。

如果 objects_nr() 是一個返回給定 MIDX 層中物件數量的函數，那麼物件在 $H3 內字典順序位置 i 的索引定義為

objects_nr($H2) + objects_nr($H1) + i

（在 C 實作中，這通常計算為 i + m->num_objects_in_base）。

未來工作

  • 多包索引允許許多 packfile，尤其是在重新打包成本高昂（例如非常大的儲存庫）或無法接受意外維護時間（例如高需求的建置機器）的情況下。但是，多包索引每次都需要完全重新撰寫。我們可以擴展格式以實現增量，以便寫入速度更快。透過儲存指向大型「基礎」MIDX 檔案的小型「提示」多包索引，我們可以保持寫入速度快，同時減少物件查詢所需的二元搜尋次數。

  • 如果擴展多包索引以儲存「穩定物件順序」（對於給定的雜湊，即使在多包索引更新時也是常數的函數 Order(hash) = 整數），則 MIDX 位圖可以獨立於 MIDX 進行更新。

  • 可以使用空檔案將 packfile 標記為「特殊」，這些空檔案共用初始名稱，但將 ".pack" 替換為 ".keep" 或 ".promisor"。我們可以向多包索引新增一個可選的資料區塊，其中記錄有關 packfile 的資訊旗標。這允許新的狀態，例如 重新打包 或 重新增量化，有助於多包環境中的 pack 維護。按物件類型（commit、tree、blob 等）組織 packfile，並使用此中繼資料來協助維護也可能會有所幫助。

相關連結

[0] https://bugs.chromium.org/p/git/issues/detail?id=6 Chromium 針對多包索引 (MIDX) 的工作項目

[1] https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/ 多包索引功能的早期 RFC

[2] https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/ Git Merge 2018 貢獻者高峰會筆記（包含 MIDX 的討論）

scroll-to-top