reed solomon符号化の実践

raidの原理をよく知っていれば、このreed solomon(リード・ソロモンコード)符号化には慣れていない.原理の第一歩はまずVandermonde行列によって符号化され、以下のように簡単に説明する.
これで元のABCD-MNOPのデータが符号化されます.このとき選択されるparityフォーマットは2であり、2行のデータの損失を許容し、Vandermonde行列の逆行列に乗算することで元のデータを以下のように得られる.
これがデータリカバリの原理を実証したものです.原理はやはりcode実践してみましょう、このコードはすでに大神が実現して、主義を持ってきました.reed-solomonはまずどのようにコードするかを見ます.

func main() {
    // Parse command line parameters.
    flag.Parse()
    args := flag.Args()
    if len(args) != 1 {
        fmt.Fprintf(os.Stderr, "Error: No input filename given
")
        flag.Usage()
        os.Exit(1)
    }
    if *dataShards > 257 {
        fmt.Fprintf(os.Stderr, "Error: Too many data shards
")
        os.Exit(1)
    }
    fname := args[0]

    // Create encoding matrix.
    enc, err := reedsolomon.NewStream(*dataShards, *parShards)
    checkErr(err)

    fmt.Println("Opening", fname)
    f, err := os.Open(fname)
    checkErr(err)

    instat, err := f.Stat()
    checkErr(err)

    shards := *dataShards + *parShards
    out := make([]*os.File, shards)

    // Create the resulting files.
    dir, file := filepath.Split(fname)
    if *outDir != "" {
        dir = *outDir
    }
    for i := range out {
        outfn := fmt.Sprintf("%s.%d", file, i)
        fmt.Println("Creating", outfn)
        out[i], err = os.Create(filepath.Join(dir, outfn))
        checkErr(err)
    }

    // Split into files.
    data := make([]io.Writer, *dataShards)
    for i := range data {
        data[i] = out[i]
    }
    // Do the split
    err = enc.Split(f, data, instat.Size())
    checkErr(err)

    // Close and re-open the files.
    input := make([]io.Reader, *dataShards)

    for i := range data {
        out[i].Close()
        f, err := os.Open(out[i].Name())
        checkErr(err)
        input[i] = f
        defer f.Close()
    }

    // Create parity output writers
    parity := make([]io.Writer, *parShards)
    for i := range parity {
        parity[i] = out[*dataShards+i]
        defer out[*dataShards+i].Close()
    }

    // Encode parity
    err = enc.Encode(input, parity)
    checkErr(err)
    fmt.Printf("File split into %d data + %d parity shards.
", *dataShards, *parShards)

}

まず元のファイルを開き、データを割り当て、enc.Splitでデータスライスを行い、parityをenc.Encodeで符号化します.私はこの中で4つのスライスと3つのparityを制定して、結果は以下の通りです.

Opening /mnt/download/kubernetes.tar.gz
Creating kubernetes.tar.gz.0
Creating kubernetes.tar.gz.1
Creating kubernetes.tar.gz.2
Creating kubernetes.tar.gz.3
Creating kubernetes.tar.gz.4
Creating kubernetes.tar.gz.5
Creating kubernetes.tar.gz.6
File split into 4 data + 3 parity shards.

もちろん3つを削除しても復元できます
次はdecodeコードです

func main() {
    // Parse flags
    flag.Parse()
    args := flag.Args()
    if len(args) != 1 {
        fmt.Fprintf(os.Stderr, "Error: No filenames given
")
        flag.Usage()
        os.Exit(1)
    }
    fname := args[0]

    // Create matrix
    enc, err := reedsolomon.NewStream(*dataShards, *parShards)
    checkErr(err)

    // Open the inputs
    shards, size, err := openInput(*dataShards, *parShards, fname)
    checkErr(err)

    // Verify the shards
    ok, err := enc.Verify(shards)
    if ok {
        fmt.Println("No reconstruction needed")
    } else {
        fmt.Println("Verification failed. Reconstructing data")
        shards, size, err = openInput(*dataShards, *parShards, fname)
        checkErr(err)
        // Create out destination writers
        out := make([]io.Writer, len(shards))
        for i := range out {
            if shards[i] == nil {
                //dir, _ := filepath.Split(fname)
                outfn := fmt.Sprintf("%s.%d", fname, i)
                fmt.Println("Creating", outfn)
                out[i], err = os.Create(outfn)
                checkErr(err)
            }
        }
        fmt.Println("reconstruct")
        err = enc.Reconstruct(shards, out)
        if err != nil {
            fmt.Println("Reconstruct failed -", err)
            os.Exit(1)
        }
        // Close output.
        for i := range out {
            if out[i] != nil {
                err := out[i].(*os.File).Close()
                checkErr(err)
            }
        }
        shards, size, err = openInput(*dataShards, *parShards, fname)
        ok, err = enc.Verify(shards)
        if !ok {
            fmt.Println("Verification failed after reconstruction, data likely corrupted:", err)
            os.Exit(1)
        }
        checkErr(err)
    }

    // Join the shards and write them
    outfn := *outFile
    if outfn == "" {
        outfn = fname
    }

    fmt.Println("Writing data to", outfn)
    f, err := os.Create(outfn)
    checkErr(err)

    shards, size, err = openInput(*dataShards, *parShards, fname)
    checkErr(err)

    // We don't know the exact filesize.
    err = enc.Join(f, shards, int64(*dataShards)*size)
    checkErr(err)
}

func openInput(dataShards, parShards int, fname string) (r []io.Reader, size int64, err error) {
    // Create shards and load the data.
    shards := make([]io.Reader, dataShards+parShards)
    for i := range shards {
        infn := fmt.Sprintf("%s.%d", fname, i)
        fmt.Println("Opening", infn)
        f, err := os.Open(infn)
        if err != nil {
            fmt.Println("Error reading file", err)
            shards[i] = nil
            continue
        } else {
            shards[i] = f
        }
        stat, err := f.Stat()
        checkErr(err)
        if stat.Size() > 0 {
            size = stat.Size()
        } else {
            shards[i] = nil
        }
    }
    return shards, size, nil
}

この中で得られたスライスは,まずVerifyスライスが完全であるかどうかをチェックし,不完全であればReconstructを再構築する.次に例を示します

rm -rf kubernetes.tar.gz.1
rm -rf kubernetes.tar.gz.3
rm -rf kubernetes.tar.gz.5


Opening /mnt/download/kubernetes.tar.gz.0
Opening /mnt/download/kubernetes.tar.gz.1
Error reading file open /mnt/download/kubernetes.tar.gz.1: no such file or directory
Opening /mnt/download/kubernetes.tar.gz.2
Opening /mnt/download/kubernetes.tar.gz.3
Error reading file open /mnt/download/kubernetes.tar.gz.3: no such file or directory
Opening /mnt/download/kubernetes.tar.gz.4
Opening /mnt/download/kubernetes.tar.gz.5
Error reading file open /mnt/download/kubernetes.tar.gz.5: no such file or directory
Opening /mnt/download/kubernetes.tar.gz.6
Verification failed. Reconstructing data
Opening /mnt/download/kubernetes.tar.gz.0
Opening /mnt/download/kubernetes.tar.gz.1
Error reading file open /mnt/download/kubernetes.tar.gz.1: no such file or directory
Opening /mnt/download/kubernetes.tar.gz.2
Opening /mnt/download/kubernetes.tar.gz.3
Error reading file open /mnt/download/kubernetes.tar.gz.3: no such file or directory
Opening /mnt/download/kubernetes.tar.gz.4
Opening /mnt/download/kubernetes.tar.gz.5
Error reading file open /mnt/download/kubernetes.tar.gz.5: no such file or directory
Opening /mnt/download/kubernetes.tar.gz.6
Creating /mnt/download/kubernetes.tar.gz.1
Creating /mnt/download/kubernetes.tar.gz.3
Creating /mnt/download/kubernetes.tar.gz.5
reconstruct
Opening /mnt/download/kubernetes.tar.gz.0
Opening /mnt/download/kubernetes.tar.gz.1
Opening /mnt/download/kubernetes.tar.gz.2
Opening /mnt/download/kubernetes.tar.gz.3
Opening /mnt/download/kubernetes.tar.gz.4
Opening /mnt/download/kubernetes.tar.gz.5
Opening /mnt/download/kubernetes.tar.gz.6
Writing data to /mnt/download/kubernetes.tar.gz
Opening /mnt/download/kubernetes.tar.gz.0
Opening /mnt/download/kubernetes.tar.gz.1
Opening /mnt/download/kubernetes.tar.gz.2
Opening /mnt/download/kubernetes.tar.gz.3
Opening /mnt/download/kubernetes.tar.gz.4
Opening /mnt/download/kubernetes.tar.gz.5
Opening /mnt/download/kubernetes.tar.gz.6

decodeのときにデータを再構築します.この符号化を紹介するのは,後続の記述対象格納のための理論的基礎である.