Fountain Codes：为雾计算CDN赋能

海量节点CDN正在成为内容分发领域的新实践，它能撬动近乎无限的带宽和存储资源，部署下沉至用户身边，从而彻底解决内容分发中“最后一公里”的问题，然而组网节点运算能力弱、上传带宽小、在线时间不稳定也带来很多挑战。本文是上海云熵网络科技有限公司联合创始人、CTO刘炜在LiveVideoStackCon 2017上的演讲整理，简述了Fountain Code的原理和实现，并介绍如何利用它为海量“弱”节点赋能，在不稳定的节点之上打造一个稳定、高效、低成本的直播分发网络。

演讲 / 刘炜

整理 / LiveVideoStack

从云到雾，内容分发的新趋势

众所周知，长久以来内容分发一共有两种主要解决方案：一种是CDN，一种是P2P。在大多数人的印象中，CDN高大上但价格比较贵，相对而言P2P则成本比较低，但质量不可靠。我希望能通过本次分享让大家扭转对P2P的印象，基于P2P这种弱节点分发的方式能够比传统云计算CDN做的更好。

近两年内容分发领域的价格战愈演愈烈，越来越多的人从云计算CDN转到替代性的解决方案上，大家也更关注使用用户节点的内容分发方式，因此我们说内容分发有从云到雾的新趋势。

上图是传统云计算CDN的树形架构，相信大家都非常熟悉，这里就不做展开。雾计算CDN与传统云计算CDN的区别，主要体现在边缘服务器和所有播放节点之间会增加非常稠密的雾节点。这些雾节点，首先它的数量非常庞大，这样就能够提供很多资源，并且总是能找到比较近的雾节点来提供服务，这就有希望解决传统云计算CDN最后一公里的问题；此外这些雾节点通常是用户闲置资源的共享，能够用相对较低的价格获得，因此它有希望能解决成本问题；最后在这个架构中我们可以看到，它其实与传统P2P的概念还是有很大区别，它将消费节点和生产节点分开——Player和雾节点可能都是一些小型的设备，不过有的专门负责分享，有的专门负责消费。

虽然我们希望通过引入雾计算的方式来解决CDN的一些问题，但它是否会引入新的问题，或者是否能从根本上达到内容分发的质量要求，其实目前还是不能完全确定的。那我们接下来具体分析下它的优势和不足。

雾CDN只是看上去很美？

• 简单拓扑延展

引入这么多雾节点，如何将它们组织起来呢？最容易想到的方式就是简单的拓扑结构延伸，也就是让雾节点去做原来边缘服务器的工作，其中的好处显而易见，架构基本不需要改变，沿用此前的设计即可，但有一个非常明显的缺点就是不实用：因为现在中国的宽带家庭接入下行有可能已经达到几百兆，但上行还处于几百K到几兆的范围内，这种带宽服务能力也就和目前常规的一路视频码流差不多，也就是说雾节点向边缘服务器回源一路视频，却也只能提供一路对Player的服务，这在经济上是不合算的。并且在这种情况下（单个雾节点带宽不足）服务质量也是很难得到保障的，因此这种简单的拓扑延展的组织方式基本上就被否定了。

• Substream

从回源成本的角度来看，我们可以在边缘服务器将一个视频流拆散——比如视频每一帧的前一半构成一个流叫做X，后一半构成一个流叫做Y，有了这两个Substreams就能有所区别地对雾节点进行组织，这样有的雾节点拿到的是X，有的雾节点拿到的是Y，那么播放器想要完整地播放一路视频就必须进行多路下载，也就是同时连接X和Y两路子流，当码流拆的更散时也就需要连上更多的雾节点。这样的方式有一个明显的好处，就是极大的降低了回源成本，之前每个提供服务的雾节点需要下载一个完整的视频流，现在只需要下载原来的N分之一即可，而N通常取得比较大——几十甚至上百，这样基本上所有雾节点的回源成本就忽略掉了。

但是这种服务框架在服务质量上的效果却依然并不理想，虽然每个人连到多个节点下载能够获得比较多的带宽资源，但这些雾节点都是分布在家庭里的，并不是特别稳定。我们知道，当一个Player需要连到N个Substreams时，只要任何一个出现问题，那么这个视频的播放就会受到影响，这个框架相当于将发生卡顿危险放大到原来的N倍，因此Substream方式可能不仅不能提高服务质量，反而有可能变得更差。

虽然使用雾计算确实可以降低成本，但雾节点的不稳定性是根深蒂固的，而我们希望能够得到一个两全其美的解决方案，那么如何在这些不稳定的节点上面，有一套的稳定的内容分发服务，就成为关键，也同样是一件有挑战的事情。

不稳定节点→稳定服务

• A Digital Fountain

我们找到了这么一个解决方案——Digital Fountain Codes，即数字喷泉编码。上图是一个喷泉，国内的喷泉主要是用作观赏，在国外有很多这样的喷泉，可以用杯子来接水喝，那么在接水的过程中，我们不会关心一开始漏掉的一些水，也不会关心接满水以后漏出去的，因为在我们看来所有的水都是一样的，我们所关心的是接满了一杯水，这也是喷泉的特点，而前面提到的喷泉码也有相似的特性。

• Fountain Codes

我们假设给定N个原始符号，用喷泉码对它进行编码，产生无穷无尽的码字，我们需要做的就是进入简单的接听模式，在这个过程中可能会错过一些编码的码字，不过没关系，因为后面不断地会有新的进来，直到我们收到N个不同的码字为止，然后通过perform逆向解码的过程得到N个原始信号。当然这里会有非常低的一个概率会出现接到信号仍然无法解码，不过解码失败率会伴随接收更多码字而快速降低。

• 随机线性编码：A Naive Example

经过前面抽象的概念讲解之后，我们再举一个具体的例子——随机线性编码的方法，我们假设在编码端输入了N个符号X0到XN-1，编码过程是通过一个随机数种子生成一系列系数p0到pN-1，将这些系数和符号做一个线性组合得到编码符号C。因为这个线性组合是在有限域上的运算，因此它编出来的码字跟原来单个符号的数据量是相等的，然后就可以把编码符号C和它的随机数种子一起传到编码端，当然随机数种子的数据量是很小的。

当解码端收到一组信号后，首先可以通过随机数种子恢复出编码系数p0到pN-1，又知道编码结果C，那么将它放在方程的右边，方程左边则剩X0到XN-1的未知数，这就是一个N元一次的方程：

p0 * X0 Å … Å pN-1 * XN-1 = C

那么收到N个不同的编码符号就能列出N个方程，也就变成N元一次方程组，这样未知数个数跟方程个数相等时就能大概率解出来。

这是一个非常简单的例子来实现喷泉码，但它的缺点是复杂度太高，对于一个N元一次方程组用矩阵求逆的方法，通常要达到O(N^3)的复杂度，因此在实际工程中不会用到这种随机线性编码。但实用的fountain codes，其原理是与之相通的。

The Game Changer

我们认为将喷泉码技术应用到雾计算CDN中能够起到胜负手的作用。

• Fountain Coded

在这种服务框架中，我们仍然在边缘服务器将数据流拆成N个子流，但并不是像前面简单的将N个子流直接分发到雾节点，而是在分发前进行Fountain Codes的编码。我们仍然使用随机线性编码的方式举例，经过编码每个雾节点拿到了一份编码后的数据，而每个雾节点拿到的数据也基本是互不相同的。Player需要拿到N个不同的编码码字，那么就可以通过随机的连到离它比较近的N个雾节点，并且下载这些码字，再进行反向的解码过程，从而将原始数据恢复出来。这也是我们认为最合适的雾计算架构。

• CrazyCDN=雾+ Fountain

下面我们针对我们的雾计算产品CrazyCDN的一些关键性能进行分析。首先前面提到这个编码过程是一个有限域上的运算，因此它的数据量和单个原始符号是相等的，也就说明每一个雾节点的回源与前面提到的Substream方式基本相同，回源成本仍然在比较低的水平。

第二，复杂度是一个缺点，因为需要在Player内embed一个Decoder，这个Decoder需要进行逆向的解码，因此会消耗额外的CPU。不过经过不断优化，目前云熵提供的SDK已经可以达到100MB/s的解码速度，并且对于目前常见的视频流媒体码率，额外消耗的CPU不会超过1%，因此也是可以接受的。

最后在服务质量上，我们认为它能够极大提升内容分发的服务质量。众所周知，传统CDN底层的infrastructure大多数都依赖于TCP的传输，而TCP的设计用途最初是为了传输大文件，而当它应用在视频流媒体时则会有一些问题，比如丢失一帧会反复重传，传不到的话后面的帧也无法使用，因此有很多私有的协议也会去支持UDP，它会增加像FEC (Forward Error Correction)的功能。而Fountain Codes其实就是一种特殊的FEC，它具有FEC通常的一些性质，因此雾CDN解决方案也拥有前向纠错的优点。

但光有前向纠错还并不能解决网络传输问题，因为它虽然可以很容易的recover一两个随机丢包错误，但在实际工程中我们发现现实网络经常出现在时间轴上非常大的相关性的连续丢包，有时甚至一秒钟连续丢十几个包，那么在这种情况下FEC是没办法帮助解决的。而雾CDN另一个优势和特点——多路传输特性——就可以极大的帮助我们解决问题，因为我们不是直接从边缘服务器到播放节点建立一条逻辑连接，而是首先分散到N个不同的雾节点，也就是经由N条不同的路径再传到终端，因此这些不同路径丢包的相关性比原来单一路径大大降低，这样同时发生大规模丢包的可能性也就减少了。因此前向纠错和多路径传输这两个相辅相成的特性也使雾CDN在传输方面展现了极大的优势。

当CrazyCDN遇见直播

• 对比1：弱网下的直播流畅度

我们希望CrazyCDN能够在对于实时性和流畅性要求比较强的视频直播场景下带来很好的效果，因此我们也做了一系列的对比试验。首先是尝试在弱网条件下播放直播视频流，如上图所示，橙色Bars是通过CrazyCDN方式进行直播内容的分发，蓝色Bars是SRS服务器的，横轴是不同延时和丢包率组合的弱网场景，纵轴是每小时平均发生的卡顿次数，以上每个sample都是至少连续播放50小时以上采集到的数据。 我们可以看到使用传统云CDN的方式在弱网条件下的流畅度是比较糟糕的，而雾CDN的表现则明显优于传统云。

• 对比2：实时传输定长数据块

在直播中除了视频流畅度，我们关心的另外一个非常关键的指标就是端到端的延时，而人们常常提出一个问题，就是在雾CDN中多引入一跳是否会对延时造成影响，因为本来是直接传过来，但现在要先传到雾节点，再由雾节点分发。

我们做了一个测试，在服务器端不停的定时产生定长的数据块，来模拟视频帧。第一种方式通过TCP长连接的方式，直接从服务器传到客户端；另一种方式是通过雾CDN传过来。我们在数据产生时打一个时间戳，在收到时再把该时间戳拿出来减一下，从而统计这个数据经过多长时间被播放器拿到。TCP因为有一个Buffer，如果后面的数据传到了，但前面被卡住，它仍然会在Buffer里面。因此我们对CrazyCDN也做出了类似的规定：对于一个数据块，如果它前面的数据块没有都拿到，则这个数据块也不算数。那么在这种情况下，我们还是可以看到CrazyCDN的表现要远远超出TCP，特别是TCP有一些延时非常长、甚至超过一秒钟还没有被接收。

• 多传一跳，延时反而降低了？

那么为什么多传一跳以后，实际接收到数据的时间反而变短了？其实在流媒体应用中，delay和流畅度这两个量之间是一个互相tradeoff的关系，必须在同样流畅度的情况下比较延时才是有意义的。在这里面我们引入了工作曲线的概念，当系统其他所有参数（例如流媒体内容，网络条件，传输方式等）都固定的时候，播放器总是可以通过增加Jittering Buffer——也就是说增大延时——来减少卡顿率，也就是在工作曲线越往X轴的方向卡顿率越低；相反，我们也可以通过缩小Jittering Buffer的方式，降低延时，相应代价是卡顿率提高。

那么在CrazyCDN应用场景下，通过多路传输和FEC的结合，极大强化了网络的传输能力，因此可以把工作曲线大大向原点推进一步，这种在固定同样的卡顿率情况下，还是能够把延时做到更低。当然以上讨论是基于有损网络的，如果一个网络既没有丢包，也没有乱序，那么显然还是点对点直接传输更快。

总结

最后我们对今天的分享做一个总结，首先雾计算是什么？雾计算希望把计算推向边缘、推向场景发生的地方，因此我们认为CDN或者说内容分发应该是雾计算非常合适的一个切入场景，因为它可以把内容部署到离用户更近的地方。但因为众多的雾节点能力弱小且不稳定，因此将设想变成工程实践并不容易，探索过程中我们发现Fountain Codes和雾CDN的结合迸发出了强大的能量，它有可能成为雾CDN的关键性技术。

对于雾计算的定位，并非是比云计算更便宜的解决方案，而是针对于某些应用和场景而言雾计算更好，它应该是承担一些云计算不能完成的任务，而内容分发是其中之一。当直播真正应用到雾计算场景下，我们发现从成本、流畅度、延时以及复杂度等多方面得到了一个非常令人满意的结果。我也希望通过本次分享让大家了解雾计算，或者说用弱小节点组网，能够在内容分发领域发挥它应有的作用，谢谢大家。