玩转KCP(4)-FEC(前向纠错)

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | 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

原始数据如下图所示

它由4个piece组成, "ABCD" "EFGH" "IJKL" "MNOP", 每行当做一个piece。

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

即使新矩阵丢失了2个piece

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

3. reed-solomon算法结论总结

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

因为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)
    }
}

抓包结果如下：

每发出3个原始数据块，就会有1个校验数据块被发出。

参考资料

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

---