Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

1. 前言

xtaci/kcp-go的作者,在KCP标准协议的基础上做了扩展,增加了加密和FEC(Forward error correction,前向纠错)那么前向纠错到底是干什么用的

2. reed-solomon算法概述

xtaci/kcp-go中,FEC的实现使用的是reed-solomon编码(实现库为klauspost/reedsolomon),这是一种诞生于上个世纪60年代的一种纠错码。详细的解释见参考资料1

原始数据如下图所示
Reed-Solomon
它由4个piece组成, "ABCD" "EFGH" "IJKL" "MNOP", 每行当做一个piece

reed-solomon算法构造了一个编码矩阵(别问萌叔怎么构造,反正是挺深奥的数学问题),使得这个矩阵与原始矩阵相乘以后,得到的新矩阵。可以观察出来,新矩阵的前4个piece与旧矩阵完全相同,剩余的2个piece,被叫做parity, 权且翻译为校验块吧。

Reed-Solomon

即使新矩阵丢失了2个piece
Reed-Solomon

在等式2边乘以编码矩阵的逆矩阵,就可以消去编码矩阵,重新恢复出原始数据

3. reed-solomon算法结论总结

包含有n个symbol的消息可以通过reed-solomon算法,得到包含 n + k 个 symbol的新消息。任意丢失至多k个symbol,原始消息仍然能够被恢复出来。这里symbolpiece的概念类同。

因为reed-solomon算法的这个特性,它被广泛的用于

1)DVD、CD、二维码

碟片即使有部分被刮花,仍然能够播放
二维码即使部分被遮挡,仍然能够识别

2)远距离空间传输

空间探测器在向地球发送数据包时,每个包的传输可能需要耗费几个小时,传输过程中,极有可能由于其他陨石遮挡等原因,造成丢包。有了reed-solomon算法,丢失的包可以被直接恢复出来,不需要再重传。

3)存储系统,比如 minio

甚至萌叔发现它在 minio/minio 一个支持Amazon S3协议的对象存储系统中也有使用

缺点

增加了额外的存储和传输量,另外在做数据恢复时,有额外的计算开销。

4. FEC

KCP协议中前向纠错相关的字段是这样设定的,它和块加密一样,都是可选的

  • FEC TYPE:
    typeData = 0xF1 原始数据块
    typeParity = 0xF2 校验数据块

  • FEC SEQID:
    递增的计数器

+-----------------+
| SESSION         |
+-----------------+
| KCP(ARQ)        |
+-----------------+
| FEC(OPTIONAL)   |
+-----------------+
| CRYPTO(OPTIONAL)|
+-----------------+
| UDP(PACKET)     |
+-----------------+
| IP              |
+-----------------+
| LINK            |
+-----------------+
| PHY             |
+-----------------+
(LAYER MODEL OF KCP-GO)

注意 和网络分层模型一样,FEC只对自己这层负责,FEC对自己的数据包中到底存的是什么并不感兴趣。因此校验数据块中的数据应该被理解为2进制数据,它们是不能按照ARQ被解析的。

读者可以按照萌叔提供的代码示例抓包加深理解
wireshark 插件请使用vearne/kcp-dissector-plugin

package main

import (
    "github.com/xtaci/kcp-go"
    "io"
    "log"
    "time"
)

func main() {
    if listener, err := kcp.ListenWithOptions("127.0.0.1:8082", nil, 3, 1); err == nil {
        // spin-up the client
        go client()
        for {
            s, err := listener.AcceptKCP()
            if err != nil {
                log.Fatal(err)
            }
            go handleEcho2(s)
        }
    } else {
        log.Fatal(err)
    }
}

// handleEcho send back everything it received
func handleEcho2(conn *kcp.UDPSession) {
    buf := make([]byte, 4096)
    for {
        n, err := conn.Read(buf)
        if err != nil {
            log.Println(err)
            return
        }

        n, err = conn.Write(buf[:n])
        if err != nil {
            log.Println(err)
            return
        }
    }
}

func client() {
    // wait for server to become ready
    time.Sleep(time.Second)

    // dial to the echo server
    if sess, err := kcp.DialWithOptions("127.0.0.1:8082", nil, 3, 1); err == nil {
        for {
            data := time.Now().String()
            buf := make([]byte, len(data))
            log.Println("sent:", data)
            if _, err := sess.Write([]byte(data)); err == nil {
                // read back the data
                if _, err := io.ReadFull(sess, buf); err == nil {
                    log.Println("recv:", string(buf))
                } else {
                    log.Fatal(err)
                }
            } else {
                log.Fatal(err)
            }
            time.Sleep(time.Second * 10)
        }
    } else {
        log.Fatal(err)
    }
}

抓包结果如下:
Reed-Solomon
每发出3个原始数据块,就会有1个校验数据块被发出。

参考资料

  1. Backblaze Open Sources Reed-Solomon Erasure Coding Source Code
  2. Erasure_code
  3. Reed–Solomon error correction

微信公众号

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注