版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://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，原始消息仍然能够被恢复出来。这里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)
	}
}

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

参考资料

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

微信公众号