這就是冗餘的樣子
冗餘碼*廣泛應用於電腦系統中，以提高資料儲存的可靠性。 在 Yandex 中，它們被用於許多專案中。 例如，在我們的內部物件儲存中使用冗餘程式碼而不是複製可以節省數百萬美元，而不會犧牲可靠性。 但儘管冗餘碼被廣泛使用，但對冗餘碼如何運作的清晰描述卻非常罕見。 那些想要了解的人大約面臨以下情況（來自 ):
我叫 Vadim，在 Yandex 開發內部物件儲存 MDS。 在本文中，我將用簡單的語言描述冗餘碼（Reed-Solomon 和 LRC 碼）的理論基礎。 我將告訴您它是如何工作的，無需複雜的數學和罕見的術語。 最後我將給出在 Yandex 中使用冗餘程式碼的範例。
我不會詳細考慮許多數學細節，但我將為想要更深入研究的人提供連結。 我還要指出，有些數學定義可能不嚴格，因為本文不是為數學家準備的，而是為想要了解問題本質的工程師所準備的。
* 在英文文獻中，冗餘碼通常稱為擦除碼。
1.冗餘碼的本質
所有冗餘程式碼的本質都極為簡單：儲存（或傳輸）數據，以便在發生錯誤（磁碟故障、資料傳輸錯誤等）時資料不會遺失。
在大多數冗餘碼中，資料被分成n個資料區塊，其中m區塊冗餘碼被計算，總共有n+m個區塊。 冗餘碼的構造方式使得僅使用 n + m 區塊的一部分即可恢復 n 區塊資料。 接下來，我們將只考慮區塊冗餘碼，即將資料分為區塊的程式碼。
要恢復所有 n 個資料區塊，您需要至少有 n + m 個區塊，因為您無法僅透過 n-1 個區塊來獲得 n 個區塊（在這種情況下，您必須「憑空取出 1 個區塊」）空氣”）。 n + m 區塊的 n 個隨機區塊是否足以恢復所有資料？ 這取決於冗餘碼的類型，例如，Reed-Solomon 碼允許您使用任意 n 個區塊恢復所有數據，但 LRC 冗餘碼並不總是如此。
數據存儲
在資料儲存系統中，通常，每個資料區塊和冗餘程式碼區塊都被寫入單獨的磁碟。 那麼，如果任意一個磁碟發生故障，仍然可以恢復並讀取原始資料。 即使多個磁碟同時發生故障，也可以復原資料。
數據傳輸
冗餘碼可用於在不可靠的網路上可靠地傳輸資料。 傳輸的資料被分成區塊，並為它們計算冗餘碼。 資料塊和冗餘程式碼區塊都透過網路傳輸。 如果任意區塊（最多一定數量的區塊）出現錯誤，資料仍然可以透過網路傳輸而不會出現錯誤。 例如，里德-所羅門碼用於透過光通訊線路和衛星通訊傳輸資料。
* 還有一些資料不分塊的冗餘碼，例如漢明碼和CRC碼，廣泛用於乙太網路中的資料傳輸。 這些是用於糾錯編碼的代碼，它們旨在檢測錯誤，而不是糾正錯誤（漢明碼還允許部分糾正錯誤）。
2.里德-所羅門碼
Reed-Solomon 碼是使用最廣泛的冗餘碼之一，發明於 1960 世紀 1980 年代，並於 XNUMX 世紀 XNUMX 年代首次廣泛用於光碟的大規模生產。
理解里德所羅門碼有兩個關鍵問題：1）如何創建冗餘碼塊； 2）如何利用冗餘碼塊恢復資料。 讓我們來尋找它們的答案。
為了簡單起見，我們將進一步假設 n=6 和 m=4。 其他方案依序類推。
如何建立冗餘程式碼區塊
每個冗餘碼區塊都獨立於其他區塊進行計數。 所有n個資料塊用於對每個區塊進行計數。 下圖中，X1-X6 為資料區塊，P1-P4 為冗餘程式碼區塊。
所有資料區塊的大小必須相同，並且可以使用零位元進行對齊。 產生的冗餘程式碼區塊的大小將與資料區塊的大小相同。 所有資料塊都分為字（例如，16 位元）。 假設我們將資料塊分成 k 個字。 那麼所有的冗餘碼塊也將被分成k個字。
為了計算每個冗餘區塊的第i個字，將使用所有資料區塊的第i個字。 它們將根據以下公式計算：
這裡的值x是資料區塊的字，p是冗餘程式碼區塊的字，所有的alpha、beta、gamma和delta都是專門選擇的數字，對於所有i都是相同的。 必須馬上說的是，所有這些值都不是普通的數字，而是伽羅瓦域的元素；運算+、-、*、/不是我們大家熟悉的運算，而是對伽羅瓦域的元素引入的特殊運算場地。
為什麼需要伽羅瓦域？
看起來一切都很簡單：我們將資料分成塊，將區塊分成單詞，使用資料塊的單字我們計算冗餘程式碼區塊的單字 - 我們得到冗餘程式碼區塊。 一般來說，它是這樣運作的，但問題在於細節：
- 如上所述，字長是固定的，在我們的範例中為 16 位元。 上述 Reed-Solomon 碼的公式是這樣的：當使用普通整數時，計算 p 的結果可能無法使用有效大小的字來表示。
- 恢復資料時，上述公式將被視為必須求解才能恢復資料的方程組。 在求解過程中，可能需要將整數相除，從而導致無法在電腦記憶體中準確表示實數。
這些問題阻礙了里德-所羅門碼使用整數。 這個問題的解決方案是原始的，可以描述如下：讓我們想出可以使用所需長度（例如16位元）的字來表示的特殊數字，以及對其執行所有操作的結果（加法） 、減法、乘法、除法）也將使用所需長度的字呈現在電腦記憶體中。
這種「特殊」數字已經被數學界研究了很長時間；它們被稱為域。 字段是一組元素，並為其定義了加法、減法、乘法和除法運算。
Galois* 域是對於該域的任兩個元素的每個運算（+、-、*、/）都有唯一結果的域。 伽羅瓦域可以構造為 2 的冪：2、4、8、16 等（實際上是任何質數 p 的冪，但實際上我們只對 2 的冪感興趣）。 例如，對於 16 位元字，這是一個包含 65 個元素的字段，對於每一對，您都可以找到任何運算（+、-、*、/）的結果。 上述方程式中的 x、p、alpha、beta、gamma、delta 的值將視為伽羅瓦域的元素來計算。
因此，我們有了一個方程組，可以透過編寫適當的電腦程式來構造冗餘碼塊。 使用相同的方程組，您可以執行資料復原。
* 這不是嚴格的定義，而是描述。
如何恢復數據
當 n + m 區塊中的某些區塊遺失時，需要進行復原。 這些可以是資料塊和冗餘程式碼區塊。 資料塊和/或冗餘程式碼區塊的缺失將意味著上面的等式中對應的x和/或p變數是未知的。
Reed-Solomon碼的方程式可以看作一個方程組，其中所有的alpha、beta、gamma、delta值都是常數，所有可用塊對應的x和p都是已知變量，其餘的x和p未知。
例如，假設資料塊1、2、3和冗餘碼塊2不可用，則對於第i組字，將有以下方程組（未知數以紅色標記）：
我們有一個包含 4 個未知數的 4 個方程組，這意味著我們可以求解它並恢復資料！
從這個方程組可以得出關於 Reed-Solomon 碼資料恢復的許多結論（n 個資料塊，m 個冗餘碼塊）：
- 如果遺失任何 m 個或更少的區塊，則可以還原資料。 如果 m+1 或更多區塊遺失，則資料無法恢復：不可能求解具有 m + 1 個未知數的 m 個方程組。
- 即使要還原一個資料區塊，也需要使用剩餘區塊中的任意 n 個，並且可以使用任意冗餘碼。
我還需要知道什麼？
在上面的描述中，我避免了一些需要深入數學才能考慮的重要問題。 特別是，我不會對以下內容發表任何言論：
- Reed-Solomon 碼的方程組對於任意未知數組合（不超過 m 個未知數）必須有一個（唯一）解。 根據這個要求，選擇alpha、beta、gamma、delta的值。
- 方程組必須能夠自動建構（取決於哪些模組不可用）並求解。
- 我們需要建構一個伽羅瓦域：對於給定的字長，能夠找到任兩個元素的任意運算（+、-、*、/）的結果。
本文末尾引用了有關這些重要問題的文獻。
n 和 m 的選擇
實際上如何選擇n和m？ 實際上，在資料儲存系統中，冗餘碼用於節省空間，因此m總是選擇小於n。 它們的具體值取決於許多因素，包括：
- 資料儲存的可靠性。 m越大，磁碟故障中能夠存活的次數就越多，即可靠性越高。
- 冗餘儲存。 m/n 比率越高，儲存冗餘度越高，系統成本也越高。
- 請求處理時間。 n + m 總和越大，請求的回應時間就越長。 由於讀取資料（在復原期間）需要讀取儲存在n個不同磁碟上的n個區塊，因此讀取時間將由最慢的磁碟決定。
此外，將資料儲存在多個 DC 中對 n 和 m 的選擇施加了額外的限制：如果關閉 1 個 DC，則資料必須仍然可供讀取。 例如，在3個DC中儲存資料時，必須滿足以下條件：m >= n/2，否則可能會出現1個DC關閉時資料無法讀取的情況。
3.LRC——本地重建碼
要使用 Reed-Solomon 碼恢復數據，您必須使用 n 個任意數據塊。 對於分散式資料儲存系統來說，這是一個非常顯著的缺點，因為要在一個損壞的磁碟上恢復數據，您將不得不從大多數其他磁碟上讀取數據，從而對磁碟和網路造成大量額外負載。
最常見的錯誤是由於一個磁碟故障或過載而導致一組資料無法存取。 在這種（最常見的）情況下，是否可以以某種方式減少資料恢復的額外負載？ 事實證明你可以：有專門用於此目的的 LRC 冗餘碼。
LRC（本機重建程式碼）是 Microsoft 發明的用於 Windows Azure 儲存體的冗餘程式碼。 LRC的想法盡可能簡單：將所有資料區塊分為兩個（或多個）組，並分別讀取每個組的部分冗餘碼區塊。 然後，一些冗餘碼區塊將使用所有資料區塊進行計數（在LRC中，它們被稱為全域冗餘碼），而另一些則使用兩組資料區塊中的一組（它們被稱為局部冗餘碼）。
LRC由三個數字表示：nrl，其中n是資料塊的數量，r是全域冗餘碼塊的數量，l是局部冗餘碼塊的數量。 要在一個資料區塊不可用時讀取數據，您只需要讀取 n/l 區塊 - 這比 Reed-Solomon 碼少 l 倍。
例如，考慮 LRC 6-2-2 方案。 X1–X6 — 6 個資料區塊，P1、P2 — 2 個全域冗餘區塊，P3、P4 — 2 個本地冗餘區塊。
使用所有資料塊對冗餘程式碼區塊P1、P2進行計數。 冗餘程式碼區塊P3 - 使用資料區塊X1-X3，冗餘程式碼區塊P4 - 使用資料區塊X4-X6。
其餘的在 LRC 中通過類比 Reed-Solomon 碼來完成。 計算冗餘程式碼區塊的字數的方程式為：
要選擇數字 alpha、beta、gamma、delta，必須滿足許多條件才能確保資料復原（即求解方程組）的可能性。 您可以閱讀有關它們的更多信息 .
同樣在實務中，XOR運算用於計算局部冗餘碼P3、P4。
LRC 方程組得出許多結論：
- 要恢復任何 1 個資料區塊，讀取 n/l 區塊（在我們的範例中為 n/2）就足夠了。
- 如果r+l區塊不可用，且所有區塊都包含在一組中，則資料無法復原。 用一個例子很容易解釋這一點。 讓區塊 X1-X3 和 P3 不可用：這些是來自同一組的 r + l 個區塊，在我們的例子中是 4 個。 那麼我們就有了一個由 3 個方程式組成的系統，其中有 4 個無法求解的未知數。
- 在r+l區塊不可用的所有其他情況下（當每組中至少有一個區塊可用時），LRC中的資料可以被恢復。
因此，LRC 在單一錯誤後恢復資料方面優於 Reed-Solomon 碼。 在Reed-Solomon碼中，要恢復2塊數據，就需要使用n個塊，而在LRC中，要恢復4塊數據，使用n/l塊（在我們的示例中為n/2）就足夠了。 另一方面，LRC 在最大允許錯誤數方面不如 Reed-Solomon 碼。 在上面的例子中，Reed-Solomon碼可以恢復任意4個錯誤的數據，而對於LRC來說，當數據無法恢復時，有XNUMX種XNUMX個錯誤的組合。
更重要的是取決於具體情況，但通常LRC提供的超額負載節省超過了可靠性稍差的儲存。
4.其他冗餘程式碼
除了Reed-Solomon碼和LRC碼之外，還有許多其他冗餘碼。 不同的冗餘碼使用不同的數學。 以下是一些其他冗餘程式碼：
- 使用 XOR 運算子的冗餘程式碼。 對n個資料塊進行異或運算，得到1塊冗餘碼，即n+1方案（n個資料塊，1個冗餘碼）。 用於 ，其中資料區塊和冗餘程式碼被循環寫入陣列的所有磁碟。
- 基於異或運算的奇偶演算法。 允許建構2塊冗餘碼，即n+2方案。
- 基於XOR運算的STAR演算法。 允許您建立3塊冗餘程式碼，即n+3方案。
- Pyramide 程式碼是 Microsoft 的另一個冗餘程式碼。
5. 在 Yandex 中使用
許多 Yandex 基礎設施專案使用冗餘程式碼來實現可靠的資料儲存。 這裡有些例子：
- MDS 內部物件存儲，我在文章開頭寫過。
- — Yandex 的 MapReduce 系統。
- (Yandex DataBase) - newSQL 分散式資料庫。
MDS 使用LRC 冗餘碼、8-2-2 方案。 具有冗餘程式碼的資料被寫入12個不同DC中不同伺服器的3個不同磁碟中：每個DC中4台伺服器。 閱讀有關此內容的更多信息 .
YT 使用最先實現的 Reed-Solomon 碼（方案 6-3）和 LRC 冗餘碼（方案 12-2-2），其中 LRC 是首選儲存方法。
YDB 使用基於偶數和奇數的冗餘碼（圖 4-2）。 關於YDB中的冗餘程式碼已經 .
由於系統的不同要求而採用不同的冗餘碼方案。 例如，在MDS中，使用LRC儲存的資料被同時放置在3個DC中。 對我們來說重要的是，如果任何一個DC 發生故障，資料仍然可供讀取，因此這些區塊必須分佈在各個DC 上，以便如果任何一個DC 不可用，則不可存取的區塊的數量不超過允許的數量。 在1-8-2方案中，可以在每個DC中放置2個區塊，那麼當任何一個DC關閉時，這4個區塊將不可用，並且可以讀取資料。 無論我們選擇哪一種方案放置在4個DC中，在任何情況下都應該有(r + l) / n >= 3，即儲存冗餘至少為0,5%。
在YT中，情況有所不同：每個YT集群完全位於1個DC中（不同的集群位於不同的DC中），因此沒有這樣的限制。 12-2-2方案提供33%的冗餘，即儲存資料較便宜，而且它還可以承受最多4個同時的磁碟中斷，就像MDS方案一樣。
在資料儲存和處理系統中使用冗餘程式碼還有很多特性：資料復原的細微差別、復原對查詢執行時間的影響、資料記錄的特性等。我將分別討論這些和其他特性如果主題有趣的話，在實踐中使用冗餘程式碼。
6. 連結
- 關於里德-所羅門碼和伽羅瓦域的一系列文章：
他們用簡單易懂的語言更深入地研究數學。 - 微軟關於LRC的文章：
第 2 節簡要地解釋了理論，然後討論了 LRC 的實務經驗。 - 偶奇方案：
- 明星計劃：
- 金字塔代碼：
- MDS 中的冗餘程式碼：
- YT 中的冗餘程式碼：
- YDB中的冗餘程式碼：
來源： www.habr.com