前言：論文還是得吃透才行，不然很多細節有問題

---

q1 object和data chunck哪一個大

根據論文，一個 data chunk 通常比一個 object 大，因為它是由多個 object 組合而成的 。 論文中提到，cross-coding 會將多個 object 組合成固定大小的 data chunk 。例如，默認的 data chunk 大小被設置為 4 KiB 。而 KV 存儲系統中的 object 大小各異，很多情況下 object 都很小

q2 傳統 Cross-Coding 中 Data Chunk 不能映射到兩個節點的原因

在傳統的 cross-coding 和一致性哈希結合的方案中，data chunk 被視為一個整體單元，并且與一個特定的物理節點綁定 。當進行伸縮操作（如添加新節點 N4）時，如果一個 object（例如 object ‘a’）根據一致性哈希的規則從節點 N1 遷移到新的節點 N4，那么包含 object ‘a’ 的原始 data chunk（在 N1 上）就會發生邏輯上的改變（因為它失去了 object ‘a’）。同時，object ‘a’ 到了新節點 N4 后，會成為 N4 上某個新 data chunk 的一部分
核心原因在于：

數據塊的整體性與節點綁定： 在傳統設計中，一個 data chunk 被認為是一個不可分割的單元，存儲在單個節點上 。它不是被設計為可以“跨越”多個物理節點存在的。

一致性哈希的對象級映射： 一致性哈希是根據對象的鍵來決定對象應該存儲在哪個節點上 。當節點變化導致對象重新映射時，是整個對象從一個節點移動到另一個節點。
校驗塊的依賴性： 由于 data chunk 發生了改變（舊的 data chunk 少了一個 object，新的 data chunk 多了一個 object），那么依賴于這些 data chunk 計算出來的所有 parity chunk（校驗塊）也必須隨之更新，以保證數據的可恢復性 。

論文中引用的圖1(b) 就清晰地展示了這個問題：當 object ‘a’ 和 ‘c’ 遷移到新節點 N4 后，原來 N1 和 N2 上的 data chunk 都發生了變化，導致了 parity chunk 的更新 。

FragEC 如何解決這個問題：

FragEC 模型允許一個邏輯上的 data chunk 的組成部分（即 objects 或 sub-chunks）物理上分布在不同的節點上 。通過 OIRList（Object Index Reference List）來維護 data chunk 的邏輯組成 。即使 object 遷移了，只要 OIRList 不變，邏輯上的 data chunk 就沒變，因此無需更新 parity chunk 。這就是 FragEC 如何解決 “Challenge 1” 的關鍵

q3一個服務器會出現在多個哈希環中嗎

不，在 ECHash 的設計中，一個物理服務器通常在同一時間只會被分配到一個哈希環中。論文中提到：“all the M nodes are dispersed across n isolated hash rings” ，這意味著所有物理服務器（節點）的總集合被劃分到這 n 個哈希環中 。其目的是創建隔離的區域，以便一個哈希環中的伸縮操作不會直接影響到同一個條帶在另一個哈希環中的數據放置策略。

q4所有的條帶都是n個塊嗎

是的，在 ECHash 使用的 (n,k) 糾刪碼的上下文中，所有條帶都由 n 個塊組成 。這是 (n,k) 糾刪碼工作方式的基礎：k 個原始數據塊被編碼以產生額外的 n?k 個校驗塊，從而每個條帶總共有 n 個塊 。這 n 個塊中的任意 k 個塊足以重建原始的 k 個數據塊 。

q5 ECHash 將所有節點劃分到 n 個隔離的區域，這里的節點定義是啥，是服務器嗎

在論文中，“節點 (nodes)” 和 “服務器 (servers)” 是可以互換使用的 。因此，當 ECHash “將所有 M 個節點劃分到 n 個隔離的區域 (n isolated hash rings)” 時 ，它指的是所有的 M 臺物理服務器被分配到這 n 個哈希環中 。論文還澄清說：“一個哈希環至少包含一個用于存儲對象的節點”

q6 論文中的self coding 和 crossing coding的區別

論文中提到的 self-coding (自編碼) 和 cross-coding (跨節點編碼) 是應用 (n,k) 糾刪碼的兩種不同方法 。它們的主要區別在于編碼操作的對象粒度和數據組織方式：

Self-Coding (自編碼):

操作粒度： 以單個對象為單位進行操作 。
數據分割： 將每一個對象分割成 k 個數據單元（splits） 。

編碼過程： 對這 k 個數據單元進行糾刪編碼，生成 n?k 個校驗單元 。
存儲分布： 屬于同一個對象的這 n 個單元（k 個數據單元和 n?k 個校驗單元）被存儲在 n 個不同的節點上 。
適用場景： 適合存儲大對象（例如，大于1MB），常用于大數據分析場景 。
在分布式KV存儲中的缺點：
不適合處理極小的對象（例如，2字節），因為將小對象再切分成更小的數據單元不切實際 。
由于每個對象都被分割成多個小的數據單元，訪問或重建對象時需要中心化的元數據查找來確定和管理所有這些小單元的位置，效率較低 。
Cross-Coding (跨節點編碼):

操作粒度： 以跨節點的數據塊 (data chunk) 為單位進行操作。
數據組織： 對象首先被分布存儲在不同的節點上 。在每個節點內部，該節點存儲的多個對象被組合成一個固定大小的數據塊 。

編碼過程： 選擇來自不同節點的 k 個數據塊，然后將這 k 個數據塊編碼生成 n?k 個相同大小的校驗塊 。

存儲分布： 這 k 個數據塊和 n?k 個校驗塊（共同構成一個條帶）被分布存儲在不同的節點上 。

適用場景/優點：
可以通過將小對象組合成固定大小的數據塊來支持小對象存儲 。

可以通過一致性哈希直接計算（而非查找）對象的位置，從而無需中心化的元數據查找即可訪問對象，便于實現去中心化的對象管理 。

論文作者認為，對于去中心化鍵值存儲系統而言，cross-coding 是一種更合理的糾刪碼應用技術，因此他們的工作主要集中在優化 cross-coding 。

q7 為什么擴展后parity chunk不需要更新

無需更新校驗塊的原因：
盡管對象 d 和 h 的物理位置改變了，但定義 data1 和 data2 的OIRList（即它們的邏輯組成和對象順序）并沒有改變 。data1 在邏輯上仍然是 {a, b, c, d}，data2 在邏輯上仍然是 {e, f, g, h} 。

校驗塊（parity chunk）是基于這些邏輯數據塊（data1 和 data2）的內容計算出來的 。
由于邏輯數據塊的內容和組成沒有發生任何變化，因此之前計算出的校驗塊依然有效，不需要進行任何更新 。

元數據的角色：
Object Index 記錄每個對象（碎片）的當前物理位置（在哪個節點上）以及它屬于哪個條帶和塊等信息 。
Chunk Index (特別是 OIRList) 記錄每個邏輯數據塊是由哪些對象（碎片）以及按什么順序組成的 。

當系統需要使用 data1 時（例如用于解碼或響應讀取請求），它會查看 data1 的 OIRList 知道它包含哪些對象，然后通過 Object Index 找到這些對象當前分別存儲在哪個物理節點上，再將它們聚合起來形成邏輯上的 data1。

q8 OIRList是啥

OIRList (Object Index Reference List) 的工作原理，根據論文中的描述，主要是作為邏輯數據塊 (data chunk) 和構成它的實際對象 (objects/fragments) 之間的橋梁和定義者。它的核心作用是記錄一個數據塊是如何由多個對象組成的。

具體來說，OIRList 的工作原理如下：

定義數據塊的組成和順序：

對于每一個邏輯數據塊 (data chunk)，都有一個與之關聯的 OIRList。
這個列表詳細指明了哪些對象（或者說對象的引用/索引）構成了這個特定的數據塊。
OIRList 還定義了這些對象在這個數據塊中的組織順序。
與 Chunk Index 關聯：

OIRList 是 Chunk Index 的一部分。
Chunk Index 是一個哈希表，它將一個數據塊的唯一標識符 (Chunk ID) 映射到該數據塊的 OIRList。
解耦邏輯塊與物理存儲：

通過 OIRList，FragEC 模型實現了數據塊的邏輯定義與其組成對象物理存儲位置的分離。
一個邏輯數據塊的內容是由 OIRList 中列出的對象及其順序決定的。這些對象（作為數據塊的碎片或子塊）可以物理地存儲在不同的節點上。
在伸縮操作中保持不變：

當發生節點伸縮（添加或刪除節點）導致對象遷移時，對象的物理位置會改變（這個變化會更新在 Object Index 中）。
然而，只要數據塊的邏輯組成（即哪些對象以及它們的順序）沒有改變，那么對應的 OIRList 就會保持不變。
因為 OIRList 不變，所以邏輯數據塊本身被認為是未改變的。這是實現“伸縮過程中無需更新校驗塊”的關鍵，因為校驗塊是根據邏輯數據塊的內容計算的。
在數據操作中的作用：

當需要讀取、更新或參與糾刪碼計算（如解碼、修復）一個邏輯數據塊時，系統會首先通過 Chunk ID 找到其 OIRList。
然后，根據 OIRList 中列出的對象引用，系統會去 Object Index 中查找這些對象的具體物理位置和元數據（如在塊內的偏移、長度）。
接著，系統從各個物理位置收集這些對象（碎片），按照 OIRList 定義的順序將它們組合起來，從而在內存中（或邏輯上）重建出完整的數據塊。
簡單來說，OIRList 就像一個**“配方單”**，它告訴系統一個邏輯數據塊是由哪些“原料”（對象/碎片）以及按照什么“步驟”（順序）組成的。即使這些“原料”的存放“倉庫”（物理節點）發生了變化，只要“配方單”不變，那么最終“烹飪”出來的“菜品”（邏輯數據塊）就是一樣的，因此之前基于這個“菜品”調制的“醬汁”（校驗塊）也依然適用。

q9 一些metadata

圖6，我們從左到右，從上到下來看這些組件：

Object Index (對象索引)

功能：這是一個哈希表，它將對象的鍵 (Key) 映射到一個64位的存儲桶 (bucket) 。
存儲桶內容 (Bucket Format - 見圖右側表格1) ：每個存儲桶包含四部分關鍵信息 ：

Length (L): 對象值的長度 。
Offset (O): 對象在其所在數據塊中的偏移量 。
Stripe ID (S): 該對象所屬的條帶 (stripe) 的唯一標識符 。
Chunk index ?: 該對象在其所屬條帶中的塊索引（從0到n-1）。
作用：通過 Object Index，系統可以快速定位到一個對象的元數據，知道它的大小、在哪個邏輯塊的哪個位置、屬于哪個糾刪碼條帶。
Chunk Index (塊索引)

功能：這也是一個哈希表，它將一個數據塊的唯一標識符 (Chunk ID) 映射到一個列表，這個列表顯示了該數據塊是如何組織其內部的對象的 。
OIRList (Object Index Reference List - 對象索引引用列表) ：這個列表（圖中用 “OIRList” 框表示，內部有指向 Object Key 的箭頭）是 Chunk Index 的核心部分。它指定了構成該數據塊的所有對象的索引引用（即這些對象在 Object Index 中的條目），以及這些對象在該數據塊中的組織順序 。

圖中的 OIRList 包含多個小方塊，每個小方塊代表一個對象，并有一個指針 (ptr) 指向下一個對象，形成一個鏈表結構，定義了對象在數據塊內的排列順序 。
作用：Chunk Index (通過 OIRList) 定義了一個邏輯數據塊的構成。即使組成這個數據塊的對象物理上存儲在不同的節點上，OIRList 依然定義了這個數據塊的邏輯完整性和內部結構。這是實現“無需更新校驗塊”的關鍵，因為只要 OIRList 不變，邏輯數據塊就不變。
Data Chunk (數據塊)

構成：如圖所示，一個 Data Chunk 由多個對象的實際值 (Value1, Value2, …) 按照 OIRList 定義的順序組合而成 。這些對象的值是從 Object Index 間接指向的。
編碼單元：這些 Data Chunk 是進行糾刪編碼的基本單元。k 個 Data Chunk 會被編碼成 n-k 個 Parity Chunk 。
碎片化：論文的核心思想是，構成一個 Data Chunk 的這些對象（即圖中的 Value1, Value2 等）可以根據一致性哈希分布在不同的物理節點上，實現了 Data Chunk 的“碎片化”存儲 。

Stripe Index (條帶索引)

功能：這是一個哈希表，它將一個條帶的唯一標識符 (Stripe ID) 映射到該條帶的元數據 。

條帶元數據 (Stripe Metadata)：這些元數據包括了該條帶中所有 k 個數據塊的 Chunk ID 和所有 n?k 個校驗塊的標識信息（例如校驗塊的 Parity Object Key）。
作用：Stripe Index 用于在需要進行數據恢復（如降級讀取或節點修復）時，快速定位一個條帶中的所有相關數據塊和校驗塊。
Parity Chunk (校驗塊)

生成：由 k 個 Data Chunk 經過糾刪編碼（如 Reed-Solomon 編碼）生成 n?k 個 Parity Chunk 。
存儲：校驗塊本身也被視為一個對象（圖中標為 “Coded Information”），并有其對應的 Parity Object Key 。這個 Key 可以基于其 Stripe ID 和它在條帶中的校驗塊序號生成 。這些校驗塊會存儲在與對應數據塊不同的節點上 。

工作流程串聯（示例）：

寫入一個對象 (Object Key, Value)：

對象信息（Key, Stripe ID, Chunk index, Offset, Length）被存入 Object Index。
對象的值 (Value) 會成為某個 Data Chunk 的一部分。
這個 Data Chunk 的組成（即它包含了哪些對象以及順序）會被記錄在 Chunk Index 的 OIRList 中。
當足夠的數據塊形成后，它們會被編碼產生 Parity Chunk。
這個 Data Chunk 和 Parity Chunk 所屬的條帶信息（如各塊的 Chunk ID 和 Parity Object Key）會被記錄在 Stripe Index 中。
讀取一個對象 (Object Key)：

系統使用 Object Key 查詢 Object Index，獲取其 Stripe ID, Chunk index, Offset, 和 Length。
通過 Chunk index 和 Stripe ID (如果需要整個塊)，可以找到對應的 Data Chunk。
如果 Data Chunk 是碎片化的，系統會通過其 OIRList (從 Chunk Index 獲取) 找到所有組成該 Data Chunk 的對象，再通過 Object Index 找到這些對象的物理位置，將它們聚合起來。
最后根據 Offset 和 Length 從重組的 Data Chunk 中提取出所需對象的值。
數據恢復（例如，一個 Data Chunk 損壞）：

通過損壞對象的 Object Key，從 Object Index 得到 Stripe ID。
使用 Stripe ID 查詢 Stripe Index，獲取該條帶中其他所有可用 Data Chunk 的 Chunk ID 和所有 Parity Chunk 的 Parity Object Key。
系統會收集到至少 k 個可用的塊（數據塊或校驗塊）。
對于每個需要的數據塊，系統會利用其 OIRList (從 Chunk Index 獲得) 和 Object Index 來聚合其所有碎片。
利用這些塊進行解碼，恢復出損壞的 Data Chunk。

q10 uint32_t waitting_length; 和 uint32_t sealing_chunk_num區別

uint32_t waitting_length;

含義：表示在當前哈希環的 chunk_waitting_list 鏈表中，所有 chunk_waitting_st 實例的總數量。
代表的狀態：這些 chunk_waitting_st 實例可以是：
正在被新的鍵值對填充數據，但尚未達到“封存”條件（即 can_sealing == 0）。
已經達到“封存”條件，等待被編碼（即 can_sealing == 1）。
作用：反映了當前哈希環中有多少個正在“工作”的、用于聚合數據的臨時塊緩沖區。每當一個新的 chunk_waitting_st 被創建并加入到 chunk_waitting_list 時（通過 chunk_waitting_push），這個計數會增加。每當一個 chunk_waitting_st 被從列表中移除（例如，在 chunk_waitting_pop 中被彈出用于編碼后），這個計數會減少。
uint32_t sealing_chunk_num;

含義：表示在當前哈希環的 chunk_waitting_list 鏈表中，已經達到了“封存”條件（即其 can_sealing 標志位為 1）的 chunk_waitting_st 實例的數量。
代表的狀態：這些是已經填充了足夠的數據（通常是達到 CHUNK_SIZE 的 CHUNK_SEALED_FACTOR 比例），并且準備好被選取用于糾刪碼編碼的邏輯數據塊。
作用：這個計數是 check_encode 函數判斷是否可以進行編碼操作的關鍵。當一個 chunk_waitting_st 的 chunk_used_size 達到封存閾值時，它的 can_sealing 會被設置為 1，并且 sealing_chunk_num 會增加。當一個這樣的塊被 chunk_waitting_pop 函數成功彈出用于編碼時，sealing_chunk_num 會減少。
區別總結：

waitting_length 是 chunk_waitting_list 中所有 chunk_waitting_st 的總數，無論它們是否已滿、是否可以封存。它代表了當前正在使用的臨時塊緩沖區的總數。
sealing_chunk_num 只是 chunk_waitting_list 中那些已經達到封存條件、可以被拿去編碼的 chunk_waitting_st 的數量。它是 waitting_length 的一個子集。
可以理解為：

waitting_length：環中“正在排隊等待裝滿或已裝滿”的籃子總數。
sealing_chunk_num：環中“已經裝滿，可以拿去打包（編碼）”的籃子數量。