很酷的糾刪碼(erasure code)技術

很早之前在寫 QR Code 解碼器的時候就接觸過「糾刪碼」(erasure code)這種技術， 因為 QR Code 有使用到 Reed—Solomon error correction ⎘ 。雖然知道是數學的運算結果，但至今還是對它的功用感到很神奇！背後的編碼理論已經超過山姆鍋的理解範圍，但撇除背後的數學理論，身為工程師要如何理解糾刪碼，以及作何應用呢？

糾刪碼(erasure code)簡介

網路上介紹糾刪碼的文章總喜歡講解背後的數學原理，真要了解背後的數學理論才能知道如何應用的話，那只會讓人想打退堂鼓。 所以，山姆鍋在這裏只說明抽象概念 ¹。 簡單地說，糾刪碼是一種演算法，可以將 K 個相同大小的資料區塊(data block)，轉成 (K + M) 個編碼後的區塊，接收者可以從這 (K + M) 個區塊中， 任選 K 個區塊，便足以還原編碼前的 K 個資料區塊。也就是說，它允許最多 M 個資料區塊在傳輸或讀取過程中遺失或錯誤！ 進一步的介紹可以參考這篇：Dummies Guide to Erasure Coding

糾刪碼的應用情境

糾刪碼的幾種應用範例：

• 像 QR Code 這種二維條碼，通常會運用糾刪碼來更正條碼透過光學鏡頭讀取所產生的變形錯誤。
• 衛星通訊單向傳輸，由於接收方無法要求重送，使用糾刪碼在有封包遺失的情況下自動更正。
• 資料儲存應用中，用來遮蔽(mask)儲存媒體故障造成的讀取錯誤。

為什麼糾刪碼很酷?

最近糾刪碼會再度引起關注，跟雲端儲存服務(cloud storage service)的崛起有很大的關係。背後的理由很簡單： 為了資料可靠性(reliability)與可用性(availability)，雲端儲存服務通常會儲存同組資料多個備份(通常是 3 份)在不同的裝置，機架，甚至不同的資料中心。 在這樣的組態下，服務允許最多 2 個資料來源發生故障而不遺失資料。在這樣的組態下， 其空間冗餘率是 200%。透過糾刪碼，在(6 + 4)的組態下，除了允許最多任意 4 個資料來源不可用外，其空間冗餘率只有 4/6 ~= 67%，節省的空間比例相當明顯 。

允許 4 個資料來源不可得是怎樣的概念，對於資料可用性有什麼影響？假設一個資料來源任一時間點可用性為 90%，也就是不可用機率為 10% = 0.1。 對於資料中心的儲存裝置，這個假設可能有點低，但對於點對點的儲存服務，如 Symform，可能就有點高，這也是為何他們會要求參與者保證基本上線時間。 運用基本的機率公式，單一個資料來源不可用的機率既然是 0.1，2 個資料來源 同時 不可用的機率卻變成 0.1 x 0.1 = 0.01，以此類推。 當可以接受 4 個資料來源不可用時，資料不可用的機率只剩下 0.0001，也就是有 99.99%的可用性 ²，這已經是Ａ級資料中心的要求等級。當然整體資料可用性有許多因素決定，例如：對外網路可用性如果只有 95%，最終資料可用性最高就不會超過 95%。

既然糾刪碼這麼厲害，為什麼沒有廣泛地被應用在儲存方案中？山姆鍋想得到的原因：

1. 計算糾刪碼很耗 CPU 運算能力。
2. 當存儲媒體數量不大時， 現有 RAID 技術便足以應付。
3. 專利問題：除了少數演算法專利已經過期外，其餘都尚有專利存在。

但隨著雲端儲存的流行，其背後龐大的存儲裝置數量驚人，透過糾刪碼技術能夠節省的裝置數量提供很大的經濟誘因。

現有 Python 糾刪碼程式庫

想要應用糾刪碼，除非您有非常深厚的編碼學基礎，不然使用別人開發好的程式庫在所難免。底下是幾個山姆鍋所知，可以透過 Python 使用的開源程式庫：

1. PyECLib ⎘

   : 底層使用 C 實作; BSD 授權。支援多種的原生(native)糾刪碼實作，但是相依套件顯然不支援 Windows，在 Unix-like 的環境編譯也很困難。

2. zfec ⎘

   : 底層使用 C 實作; GPL 授權。如果 GPL對您不是問題的話，可以考慮。

3. py_ecc ⎘

   : 純 Python 實現; 不確定授權模式，應該類似 BSD。 除非只是為了驗證概念，不然使用純 Python 實作無法實際應用。

假如上述的程式庫，不合乎您的需要的話，請繼續看下一節。

自行包裝糾刪碼程式庫

山姆鍋發現一個在 GitHub 上的 Longhair 專案有提供所需的程式碼。 使用 C++ 開發，但提供 C 語言呼叫介面，New BSD 授權，剛好符合需要。 唯一的問題：它不支援 Python 支援！

還好 Python 的特性之一便是容易整合原生(native)程式庫，這讓我興起自行整合的想法。因為不想學習 Python 完整的 C 擴充介面 ³，於是山姆鍋選擇 Cython 來進行包裝工作。

完成的相關程式碼在 GitHub ⎘ 上。

測試程式碼

底下的測試碼示範如何使用 fec_encode 編碼，以及 fec_decode 解碼：

def test_fec_encode(self):
    block_size = 8192
    k = 10
    m = 4
    data = os.urandom(k * block_size)
    parity = bytearray(m * block_size)
    assert fec_encode(k, m, block_size, data, parity) == 0

def test_fec_decode_without_sufficient_blocks(self):
    block_size = 8192
    k = 10
    m = 4
    data = os.urandom(k * block_size)
    parity = bytearray(m * block_size)
    assert parity == b'\x00' * (m * block_size)
    assert fec_encode(k, m, block_size, data, parity) == 0

    blocks = []
    for row in range(k-1):
        offset = row * block_size
        block_data = data[offset:offset + block_size]
        blocks.append((row, block_data))

    blocks.append((k, bytearray(parity[:block_size])))
    assert fec_decode(k, m, block_size, blocks) == 0
    offset = (k-1) * block_size
    assert blocks[(k-1)][1] == data[offset:offset + block_size]

解碼測試案例故意將最後一個(索引值 k-1)原始資料區塊，換成第一個同位檢查資料區塊來驗證解碼正確。

結語

數學對山姆鍋而言，通常是要敬而遠之的東西，但是糾刪碼實在很酷，讓我還是想寫寫關於它的應用。試想：將資料加密後，再使用糾刪碼切成 (K + M) 份， 分散到網路上 (K + M) 台主機。理論上，不僅沒有一台主機有完整資訊可以還原資料外，還可以容忍其中 M 台主機離線或故障。最重要的是： 只有自己擁有最終解碼所需的金鑰(secret key)，這才是雲端存儲的終極之道啊！關於雲端資料加密的作法，以後有機會再介紹。

參考資料

Cython: http://cython.org/ ⎘

Longhair: https://github.com/catid/longhair ⎘

Symform: http://www.symform.com/ ⎘

Dummies Guide to Erasure Coding: http://smahesh.com/blog/2012/07/01/dummies-guide-to-erasure-coding/ ⎘