對(duì)象存儲(chǔ)的數(shù)據(jù)冗余

如果數(shù)據(jù)只存儲(chǔ)一份滋觉，存儲(chǔ)設(shè)備壞了數(shù)據(jù)就丟失了，所以需要做數(shù)據(jù)冗余齐邦。

常見(jiàn)的數(shù)據(jù)冗余策略就是多副本冗余，該策略實(shí)現(xiàn)簡(jiǎn)單第租，但是代價(jià)比較高措拇。書(shū)中介紹的冗余策略是使用Reed-Solomon糾刪碼實(shí)現(xiàn)的。

RS糾刪碼中有數(shù)據(jù)片和校驗(yàn)片的概念慎宾，假如說(shuō)選擇4個(gè)數(shù)據(jù)片丐吓，那么就會(huì)將數(shù)據(jù)分成4個(gè)分片對(duì)象。每個(gè)分片的大小是原始對(duì)象的25%趟据，如果選擇2個(gè)校驗(yàn)片券犁，那么會(huì)同時(shí)生成2個(gè)和數(shù)據(jù)片大小一樣的校驗(yàn)片，所以一個(gè)文件最后會(huì)得到6個(gè)分片汹碱。

神奇的是粘衬，6個(gè)分片里面，只要有任意4個(gè)分片沒(méi)有損壞咳促，都可以還原出原始文件稚新。

評(píng)價(jià)一個(gè)數(shù)據(jù)冗余策略的好壞，主要是衡量該策略對(duì)存儲(chǔ)空間的要求和其抗數(shù)據(jù)損壞的能力跪腹。

• 對(duì)存儲(chǔ)空間的要求是指我們采用的冗余策略相比于不使用冗余要額外支付的存儲(chǔ)空間褂删，用百分比表示。
• 抗數(shù)據(jù)損壞的能力以允許損壞或丟失的對(duì)象數(shù)量來(lái)衡量冲茸。

例如屯阀，在不使用冗余策略的情況下缅帘，我們的對(duì)象占用存儲(chǔ)空間的大小就是它本身的大小，一旦該對(duì)象損壞难衰，我們就丟失了這個(gè)對(duì)象钦无，所以它對(duì)存儲(chǔ)空間的要求使100%，抵御能力是0召衔；如果使用雙副本冗余策略铃诬，存儲(chǔ)空間要求是200%，抵御數(shù)據(jù)損壞的能力是1（可以丟失兩個(gè)副本中的任意1個(gè)）苍凛；而使用4+2的RS碼的策略趣席，存儲(chǔ)空間的要求是150%，抵御能力是2（可以丟失6個(gè)分片對(duì)象中的任意2個(gè)）醇蝴；而對(duì)于一個(gè)M+N的RS碼（M個(gè)數(shù)據(jù)片加N個(gè)校驗(yàn)片）宣肚，其對(duì)存儲(chǔ)空間的要求是(M+N)/M*100%，抵御能力是N悠栓。

RS碼原理簡(jiǎn)介

原理比較復(fù)雜霉涨，這里抄一個(gè)網(wǎng)上博客的例子：假設(shè)選擇4個(gè)數(shù)據(jù)片，2個(gè)校驗(yàn)片惭适，有一個(gè)文件需要備份笙瑟，文件內(nèi)容是ABCDEFGHIJKLMNOP。首先將其分成4個(gè)分片癞志，得到一個(gè)二維數(shù)組往枷，每一行是一個(gè)數(shù)據(jù)分片，共4行凄杯。

The Original Data.png

而RS算法會(huì)使用一個(gè)6*4的矩陣（6是總分片數(shù)错洁，4是數(shù)據(jù)分片數(shù)，文中稱(chēng)之為Coding Matrix）戒突，和原始數(shù)據(jù)（Original Data）做乘法屯碴，得到一個(gè)新的矩陣（Coded Data）：

Applying the Coding Matrix.png

可以看到，新的矩陣（Coded Data）前四行和原始數(shù)據(jù)還是一樣的膊存，新增了兩行不知道什么含義的數(shù)據(jù)导而。

現(xiàn)在，假設(shè)是3膝舅，4行數(shù)據(jù)被損壞了（索引從1開(kāi)始）!

兩行數(shù)據(jù)被損壞.png

那么嗡载，怎么由剩余的四行還原數(shù)據(jù)呢？

刪除兩行之后的等式.png

如上圖仍稀，將Coding Matrix的3洼滚、4行也去掉，這個(gè)等式依然成立技潘。最重要的是遥巴，剩下的這個(gè)Coding Matrix是一個(gè)可逆矩陣（這個(gè)特殊的矩陣是怎么尋找出來(lái)的）千康，等式兩邊同時(shí)乘以該矩陣的可逆矩陣：

兩邊同時(shí)乘以Coding Matrix的逆矩陣.png

最后總結(jié)，根據(jù)以下公式可以得到原始數(shù)據(jù)（由等式右邊可以得到等式左邊）：

重建數(shù)據(jù)的公式.png

golang實(shí)現(xiàn)的RS庫(kù)

github上有一個(gè)用golang實(shí)現(xiàn)的rs庫(kù)铲掐。

使用go get -u -v github.com/klauspost/reedsolomon 進(jìn)行安裝拾弃。

關(guān)鍵函數(shù)

查看他的doc文檔，使用New方法可以得到一個(gè)實(shí)現(xiàn)了Encoder接口的對(duì)象摆霉。函數(shù)原型是func New(dataShards, parityShards int, opts ...Option) (Encoder, error)豪椿，需要傳入數(shù)據(jù)片和校驗(yàn)片的大小。

其中Encoder接口有以下幾個(gè)關(guān)鍵的函數(shù)携栋。

1. Verify(shards [][]byte) (bool, error)搭盾。每個(gè)分片都是[]byte類(lèi)型，分片集合就是[][]byte類(lèi)型婉支，傳入所有分片鸯隅，如果有任意的分片數(shù)據(jù)錯(cuò)誤，就返回false向挖。
2. Split(data []byte) ([][]byte, error)蝌以。將原始數(shù)據(jù)按照規(guī)定的分片數(shù)進(jìn)行切分。注意：數(shù)據(jù)沒(méi)有經(jīng)過(guò)拷貝何之，所以修改分片也就是修改原數(shù)據(jù)跟畅。
3. Reconstruct(shards [][]byte) error。這個(gè)函數(shù)會(huì)根據(jù)shards中完整的分片溶推，重建其他損壞的分片碍彭。
4. Join(dst io.Writer, shards [][]byte, outSize int) error。將shards合并成完整的原始數(shù)據(jù)并寫(xiě)入dst這個(gè)Writer中悼潭。

demo

官方提供了demo，學(xué)習(xí)一下simple-encoder.go和simple-decoder.go文件舞箍。

下面的代碼做了一點(diǎn)修改舰褪。

simple-decoder.go：打開(kāi)并讀取D:/objects/文件夾下面的test文件（文件內(nèi)容隨便），使用rs庫(kù)將其分為6個(gè)文件（4個(gè)數(shù)據(jù)片疏橄，2個(gè)校驗(yàn)片）占拍，保存在"D:/objects/encoder/"文件夾下。

文件內(nèi)容如下（A,B,C,D分別20個(gè)）捎迫，移動(dòng)80個(gè)字節(jié)晃酒，注意不要使用windows的記事本進(jìn)行編輯：

AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDD

Enocder

simple-encoder.go代碼如下:

package main

import (
    "fmt"
    "io/ioutil"
    "os"
    "path/filepath"

    "github.com/klauspost/reedsolomon"
)

const (
    dataShards = 4 // 數(shù)據(jù)分片數(shù)
    parShards  = 2 // 校驗(yàn)分片數(shù)
)


func main() {

    fname := "D:/objects/test"
    // Create encoding matrix.
    enc, err := reedsolomon.New(dataShards, parShards)
    checkErr(err)

    fmt.Println("Opening", fname)
    b, err := ioutil.ReadFile(fname)
    checkErr(err)

    // Split the file into equally sized shards.
    shards, err := enc.Split(b)
    checkErr(err)
    fmt.Printf("File split into %d data+parity shards with %d bytes/shard.\n", len(shards), len(shards[0]))

    // Encode parity
    err = enc.Encode(shards)
    checkErr(err)

    // Write out the resulting files.
    _, file := filepath.Split(fname)
    dir := "D:/objects/encoder/"
    for i, shard := range shards {
        outfn := fmt.Sprintf("%s.%d", file, i)

        fmt.Println("Writing to", outfn)
        err = ioutil.WriteFile(filepath.Join(dir, outfn), shard, os.ModePerm)
        checkErr(err)
    }
}

func checkErr(err error) {
    if err != nil {
        fmt.Fprintf(os.Stderr, "Error: %s", err.Error())
        os.Exit(2)
    }
}

Opening D:/objects/test
File split into 6 data+parity shards with 20 bytes/shard.
Writing to test.0
Writing to test.1
Writing to test.2
Writing to test.3
Writing to test.4
Writing to test.5

可以看到每個(gè)shard（分片）是20個(gè)字節(jié)，生成了6個(gè)文件窄绒，打開(kāi)之后發(fā)現(xiàn)贝次，test.0是20個(gè)A，test.1是20個(gè)B彰导，test.2是20個(gè)C蛔翅，test.3是20個(gè)D敲茄，正好可以拼接成完整的文件，和前面的理論符合山析。

Decoder

simple-decoder.go代碼如下:

package main

import (
    "fmt"
    "io/ioutil"
    "os"

    "github.com/klauspost/reedsolomon"
)

const (
    dataShards = 4
    parShards  = 2
)

func main() {
    // Create matrix
    enc, err := reedsolomon.New(dataShards, parShards)
    checkErr(err)

    fname := "D:/objects/encoder/test"
    // Create shards and load the data.
    shards := make([][]byte, dataShards+parShards)
    for i := range shards {
        infn := fmt.Sprintf("%s.%d", fname, i)
        fmt.Println("Opening", infn)
        shards[i], err = ioutil.ReadFile(infn)
        if err != nil {
            fmt.Println("Error reading file", err)
            shards[i] = nil
        }
    }

    // Verify the shards
    ok, err := enc.Verify(shards)
    if ok {
        fmt.Println("No reconstruction needed")
    } else {
        fmt.Println("Verification failed. Reconstructing data")
        err = enc.Reconstruct(shards)
        if err != nil {
            fmt.Println("Reconstruct failed -", err)
            os.Exit(1)
        }
        ok, err = enc.Verify(shards)
        if !ok {
            fmt.Println("Verification failed after reconstruction, data likely corrupted.")
            os.Exit(1)
        }
        checkErr(err)
    }

    outfn := "D:/objects/decoder/test"
    fmt.Println("Writing data to", outfn)
    f, err := os.Create(outfn)
    checkErr(err)

    // We don't know the exact filesize.
    err = enc.Join(f, shards, len(shards[0])*dataShards)
    checkErr(err)
}

func checkErr(err error) {
    if err != nil {
        fmt.Fprintf(os.Stderr, "Error: %s", err.Error())
        os.Exit(2)
    }
}

Opening D:/objects/encoder/test.0
Error reading file open D:/objects/encoder/test.0: The system cannot find the file specified.
Opening D:/objects/encoder/test.1
Error reading file open D:/objects/encoder/test.1: The system cannot find the file specified.
Opening D:/objects/encoder/test.2
Opening D:/objects/encoder/test.3
Opening D:/objects/encoder/test.4
Opening D:/objects/encoder/test.5
Verification failed. Reconstructing data
Writing data to D:/objects/decoder/test

刪除test.0和test.1這兩個(gè)文件堰燎，執(zhí)行程序，最后還是能正常的回復(fù)成原始數(shù)據(jù)笋轨。

殘留問(wèn)題

• 具體算法還沒(méi)有了解秆剪，如，Coding Matrix如何得到的爵政。
• 官方demo中還有stream-encoder.go仅讽，stream-decoder.go沒(méi)有閱讀。
• 該算法的一些限制茂卦，如數(shù)據(jù)分片和校驗(yàn)分配的個(gè)數(shù)有沒(méi)有限制何什？

參考

• 《分布式對(duì)象存儲(chǔ)--原理架構(gòu)及Go語(yǔ)言實(shí)現(xiàn)》
• github:klauspost/reedsolomon
• Backblaze blog post
• reedsolomon包介紹