前言

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

糾刪碼 (erasure code) 簡介

網路上介紹糾刪碼的文章總喜歡講解背後的數學原理 , 真要了解背後的數學理論才能知道如何應用的話 , 那只會讓人想打退堂鼓 。 所以 , 山姆鍋在這裏只說明抽象概念 [1] 。 簡單地說 , 糾刪碼是一種演算法 , 可以將 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% 的可用性 [2], 這已經是 A 級資料中心的要求等級 。 當然整體資料可用性有許多因素決定 , 例如 : 對外網路可用性如果只有 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 擴充介面 [3], 於是山姆鍋選擇 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/


[1] 其實是山姆鍋也不了解背後艱深的數學原理 。
[2] 也就是俗稱 4 個 9 的可用性 。
[3] 如果您了解 Python 的 C 擴充介面 , 記得跟社群分享 。