golang分布式存储 读书笔记(3)——数据冗余之RS码

对象存储的数据冗余

如果数据只存储一份，存储设备坏了数据就丢失了，所以需要做数据冗余。

常见的数据冗余策略就是 多副本冗余 ，该策略实现简单，但是代价比较高。书中介绍的冗余策略是使用 Reed-Solomon 纠删码实现的。

RS 纠删码中有 数据片 和 校验片 的概念，假如说选择 4 个数据片，那么就会将数据分成 4 个分片对象。每个分片的大小是原始对象的 25% ，如果选择 2 个校验片，那么会同时生成 2 个和数据片大小一样的校验片，所以一个文件最后会得到 6 个分片。

神奇的是， 6 个分片里面，只要有任意 4 个分片没有损坏，都可以 还原 出原始文件。

评价一个数据冗余策略的好坏，主要是衡量该策略对存储空间的要求和其抗数据损坏的能力。

• 对存储空间的要求是指我们采用的冗余策略相比于不使用冗余要额外支付的存储空间，用百分比表示。
• 抗数据损坏的能力以允许损坏或丢失的对象数量来衡量。

例如，在不使用冗余策略的情况下，我们的对象占用存储空间的大小就是它本身的大小，一旦该对象损坏，我们就丢失了这个对象，所以它对存储空间的要求使 100% ，抵御能力是 0 ；如果使用双副本冗余策略，存储空间要求是 200% ，抵御数据损坏的能力是 1 （可以丢失两个副本中的任意 1 个）；而使用 4+2 的 RS 码的策略，存储空间的要求是 150% ，抵御能力是 2 （可以丢失 6 个分片对象中的任意 2 个）；而对于一个 M+N 的 RS 码（ M 个数据片加 N 个校验片），其对存储空间的要求是 (M+N)/M*100% ，抵御能力是 N 。

RS码原理简介

原理比较复杂，这里抄一个网上 博客 的例子：假设选择 4 个数据片， 2 个校验片，有一个文件需要备份，文件内容是 ABCDEFGHIJKLMNOP 。首先将其分成 4 个分片，得到一个二维数组，每一行是一个数据分片，共 4 行。

The Original Data.png

而 RS 算法会使用一个 6*4 的矩阵（ 6 是总分片数， 4 是数据分片数，文中称之为 Coding Matrix ），和原始数据（ Original Data ）做乘法，得到一个新的矩阵（ Coded Data ）：

Applying the Coding Matrix.png

可以看到，新的矩阵（ Coded Data ） 前四行和原始数据还是一样的 ，新增了两行不知道什么含义的数据。

现在，假设是 3 ， 4 行数据被损坏了（索引从 1 开始）!

两行数据被损坏.png

那么，怎么由剩余的四行还原数据呢？

删除两行之后的等式.png

如上图，将 Coding Matrix 的 3 、 4 行也去掉，这个等式依然成立。最重要的是，剩下的这个 Coding Matrix 是一个可逆矩阵（这个特殊的矩阵是怎么寻找出来的），等式两边同时乘以该矩阵的可逆矩阵：

两边同时乘以Coding Matrix的逆矩阵.png

最后总结，根据以下公式可以得到原始数据（由等式右边可以得到等式左边）：

重建数据的公式.png

golang实现的RS库

github 上有一个用 golang 实现的 rs库 。

使用 go get -u -v github.com/klauspost/reedsolomon 进行安装。

关键函数

查看他的 doc 文档 ，使用 New 方法可以得到一个实现了 Encoder 接口的对象。函数原型是 func New(dataShards, parityShards int, opts ...Option) (Encoder, error) ，需要传入数据片和校验片的大小。

其中 Encoder 接口有以下几个关键的函数。

1. Verify(shards [][]byte) (bool, error) 。每个分片都是 []byte 类型，分片集合就是 [][]byte 类型，传入所有分片，如果有任意的分片数据错误，就返回 false 。
2. Split(data []byte) ([][]byte, error) 。将原始数据按照规定的分片数进行切分。注意：数据没有经过拷贝，所以修改分片也就是修改原数据。
3. Reconstruct(shards [][]byte) error 。这个函数会根据shards中完整的分片，重建其他损坏的分片。
4. Join(dst io.Writer, shards [][]byte, outSize int) error 。将 shards 合并成完整的原始数据并写入 dst 这个 Writer 中。

demo

官方提供了 demo ，学习一下 simple-encoder.go 和 simple-decoder.go 文件。

下面的代码做了一点修改。

simple-decoder.go ：打开并读取 D:/objects/ 文件夹下面的 test 文件（文件内容随便），使用 rs 库将其分为 6 个文件（ 4 个数据片， 2 个校验片），保存在 "D:/objects/encoder/" 文件夹下。

文件内容如下（A,B,C,D分别20个），移动 80 个字节， 注意不要使用windows的记事本进行编辑 ：

AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDD

Enocder

simple-encoder.go 代码如下:

package main

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

    "github.com/klauspost/reedsolomon"
)

const (
    dataShards = 4 // 数据分片数
    parShards  = 2 // 校验分片数
)


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

可以看到每个 shard （分片）是 20 个字节，生成了 6 个文件，打开之后发现， test.0 是20个 A ， test.1 是 20 个 B ， test.2 是 20 个 C ， test.3 是 20 个 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 这两个文件，执行程序，最后还是能正常的回复成原始数据。

残留问题

• 具体算法还没有了解，如， Coding Matrix 如何得到的。
• 官方 demo 中还有 stream-encoder.go ， stream-decoder.go 没有阅读。
• 该算法的一些限制，如数据分片和校验分配的个数有没有限制？

参考

• 《分布式对象存储--原理架构及 Go 语言实现》
• github:klauspost/reedsolomon
• Backblaze blog post
• reedsolomon包介绍