喷泉码的分布式云存储教学系统设计

袁 磊，付 饶，沈 钰，任秀杰

（兰州大学信息科学与工程学院，兰州 730030）

0 引言

人工智能、第5 代移动通信和物联网等技术的进步推动着我国智能化社会的发展，同时其所产生的数据正呈爆炸式增长，如何处理海量规模的数据成为了亟待解决的问题。针对大规模数据存储领域中传统存储技术存在可拓展性差、成本高等问题，分布式云存储技术凭借高可靠性、高扩展性和高可用性等优势，成为物联网中大规模数据存储的主要方式。近年来，大规模分布式应用关注的焦点逐渐从“计算”向“数据”迁移［1-2］，分布式云存储的相关理论、技术和系统方面的研究也得到了工业界的广泛关注与应用，如百度云、华为云、iCloud等分布式云存储服务。

物联网课程作为一种融合了嵌入式系统、计算机软件和网络通信等多种技术与理论的应用型课程，能有效提高学生的工程实践能力。在物联网课程的以往教学中，我校主要以理论讲授为主，电子信息类专业学生普遍反映缺乏足够的实践机会，使其综合应用物联网课程中的各种理论知识。同时相较于计算机类学生，电子信息类学生普遍存在软件开发能力偏弱的问题，因此，如何通过工程实践提升学生的综合素养显得尤为重要。有鉴于此，以我校电子信息类专业大三下学期开设的“物联网技术及应用”课程进行改革为契机，基于物联网领域的学科前沿知识和前期成果“IPv6协议下基于喷泉码的P2P 文件分发系统设计与实现”（其于2019 年获得第五届下一代互联网技术创新大赛二等奖），开发了一套基于喷泉码的分布式云存储实验教学系统，通过利用Qt（一种C ＋＋图形用户界面应用程序开发框架）的跨平台特性和新型纠删码喷泉码，使学生掌握分布式云存储系统开发的基本流程和原理。通过实验，学生可以自主实现多层次纠删码编译码算法，还可灵活选用传输控制协议（Transmission Control Protocol，TCP）、用户数据报协议（User Datagram Protocol，UDP）等网络协议进行数据传输，以此增强学生的工程实践能力、综合应用能力以及创新意识。

1 系统背景

1.1 分布式云存储和喷泉码

分布式存储是一种数据存储技术，旨在通过将数据分散存储在多台独立的设备上，达到大规模存储的目的。云存储是一种网络在线存储模式，即把信息存放在第三方托管的虚拟服务器上。分布式云存储则是结合两者的优势，使不同类型的存储设备集合起来协同工作，共同对外提供数据存储服务，形成“物理分散，逻辑集中”的高效协同系统，系统架构如图1 所示。分布式云存储可以实现存储资源的有效利用，避免存储资源浪费，也可以将存储文件保存在特定位置，提高安全性，是当下主流的存储应用方式。

现有大型分布式云存储系统的重要工作之一是数据保护［3］，为了防止节点故障造成的数据丢失，选择合适的数据冗余保护策略尤为重要。多副本和纠删码是目前分布式云存储系统中常用的两种数据冗余保护策略。多副本策略中，最常用的是三副本技术，即将原始数据镜像复制到3 个存储节点上，文件恢复速度快，但存储成本非常高［4］。纠删码策略是通过纠删码算法将原始的数据编码得到冗余，并将数据和冗余一并存储起来，以达到容错的目的。它与传统的多副本策略相比，具有冗余度低，磁盘利用率高等优点［5］。现有大型分布式云存储系统，如Swift、Ceph 大多将里德－所罗门（Reed Solomon，RS）码作为纠删码［6］，但诸如RS 码之类的最大距离可分码存在编译码复杂度高、修复带宽开销大的问题。因此，近年来又有学者陆续提出将低密度奇偶校验（Low Density Parity Check，LDPC）码、局部修复码等作为新的纠删码应用到分布式云存储系统中［7］，旨在降低编译码复杂度与修复带宽开销，但固定码率的纠删码（如LDPC 码）在多播广播等传输场景下存在效率低下的问题。

喷泉码是一类新颖且码率不受限的线性纠删码，最初是为解决可靠多播广播问题而提出。卢比变换（Luby Transform，LT）码和Raptor 码是目前主要的两类喷泉码，其中一种系统Raptor码已被多个主流标准所采用，如用于多媒体广播和组播业务的MBMS（Multimedia Broadcast Multicast Service）标准［8］。发送方通过对信息进行喷泉编码，可以产生任意多的喷泉编码包。接收方只要接收到略大于信息数目的喷泉编码包，即可通过译码算法以高概率成功恢复原始数据。喷泉码具有较低的编译码复杂度，通过与UDP协议相结合，可实现快速可靠地数据分发，尤为适合可靠多播广播传输场景［9］。目前，喷泉码除了在通信领域获得了成功，在分布式云存储领域中其作为纠删码数据保护策略也受到了学术界和工业界的广泛关注，如文献［10-11］中研究了基于LT 码的分布式云存储系统性能，美国昆腾公司的Lattus 对象存储系统也采用了喷泉码作为纠删码，文献［12］中提出利用喷泉码构造液态云存储（Liquid Cloud Storage）系统的新概念。

1.2 教学系统创新

基于喷泉码的分布式云存储系统结合了喷泉码优势，创新构建多元化分层次实验教学体系，系统创新架构如图2 所示，其创新点如下：

图2 系统创新架构

（1）教学内容丰富。遵循RFC5053 标准的系统喷泉码（即R10 码）［13］引入分布式存储教学系统中，增强学生学习实际标准的意识。此外，该系统采用具有跨平台特性的Qt 框架开发，方便跨平台移植，学生也可以根据自己的兴趣自主进行系统的图形用户界面（Graphical User Interface，GUI）设计。通过系统实验，学生还可以有效学习C ＋＋、网络编程、数据库、通信传输协议等物联网课程基础知识，加深了学生对物联网课程系统层次结构的理解，增强了学生的实践能力。

（2）灵活使用传输层协议。传统分布式存储系统采用TCP协议作为传输层协议，其可靠性高，但也存在传输时延高、无法适应多播广播传输等问题。2016年，谷歌提出基于UDP 的快速UDP 互联网连接（Quick UDP Internet Connection，QUIC）协议取代传统基于TCP 的超文本传输协议2.0（Hyper Text Transfer Protocol 2.0），以此提升传输效率［14］。UDP 协议具有快速、高效、适合多播广播场景传输等特点，但其无法保证可靠传输，因此QUIC 协议采用了纠删码技术来保证UDP传输的可靠性。喷泉码作为新近出现的纠删码方法，具有传统纠删码所不具备的“无率”和“独立”特性。有鉴于此，该教学系统灵活选择两种传输层协议，对传输信息量相对较少的控制流信息，使用TCP协议传输；对传输信息量较大的数据信息，采用UDP协议传输，将喷泉码无码率和动态生成独立编码包的特点与UDP 协议相结合，实现文件的快速可靠分发。

（3）分层次实验教学。按实验的难易程度和综合知识量，建立了一套注重培养学生实际动手能力的分层次实验教学体系。①在验证型实验中，注重系统的“实现＋验证”，学生以小组为单位通过Qt 开发平台，自主开发基于传统三副本＋TCP模式的分布式存储系统。在单用户下载文件的场景下，通过模拟存储节点宕机后文件能否正常恢复，验证系统的存储可靠性。②在综合型实验中，注重系统的“可靠＋高效”，学生通过实验熟悉喷泉码＋UDP 协议在其典型多用户下载场景下所拥有的传输优势。同时，学生可以自主实现不同难度的喷泉编译码算法，将其作为编译码模块加入系统中，从而有效锻炼自身编程能力。

2 系统设计

基于喷泉码的分布式云存储教学系统由喷泉编译码模块、分布式存储系统模块两部分组成。喷泉码模块贯穿于整个系统中，负责文件的编译码实现。本系统采用了两种喷泉码，即LT 码、R10 码。分布式云存储系统模块则主要负责系统架构与实现，其由客户端、云服务器和云存储节点三部分组成，具体模块设计如下。

2.1 喷泉码模块

2.1.1 LT码

LT码是第1 个实用喷泉码设计方案，其编码过程如图3 所示，首先将源文件划分为k个等长输入符号块，然后利用度分布函数随机均匀选取d（d≤k）个不同的符号块，将这d个符号块异或得到一个编码符号块。重复以上步骤n次，即可得到n个输出编码符号块。

图3 LT编码过程

LT码在删除信道下的译码算法主要为置信传播译码算法（Belief Propagation，BP）和及时高斯消元译码算法（On the Fly Gaussian Elimination，OFG）［15］两种。在接收到一定数量的喷泉编码符号块后开始执行译码算法，如果文件恢复成功，则译码结束，否则继续接收一定量的编码符号块，直到译码成功为止。BP译码的主要过程为首先在每一轮迭代中寻找度值为1 的编码符号，将该编码符号的值赋予与其连接的信息符号，再通过异或操作更新对应的编码符号，重复步骤直到所有文件块恢复成功。BP译码虽然译码简单，但其译码性能比最优的极大似然译码算法差。OFG 译码算法则是一种快速极大似然译码算法实现，其通过将矩阵三角化操作分散到了译码器每一次接收编码符号的过程中，有效地降低了译码复杂度，将译码复杂度控制在O（k2）。表1 给出了LT 码的BP 和OFG 译码算法在不同译码开销下的文件错误率（File Error Rate，FER），即源文件译码失败概率，源文件大小k为200，度分布采用了参数c＝0，03，ε ＝0.5 的鲁棒孤波度分布（Robust Soliton Degree Distribution）［18］，译码开销定义为n／k－1。

表1 LT码的BP和OFG的FER比较

2.1.2 R10 码

相比于LT码，Raptor码具有更好的性能，其在LT码的基础上级联了一个线性分组码作为外码，先将原始信息进行预编码再将外码的码字作为LT 码的输入。

R10 码是一种二进制的系统Raptor码。RFC5053标准详细规定了R10 码的编译码算法，如图4 所示。R10 码的编码过程是由k个源符号编码产生修复符号的过程，分为两个阶段，第1 个阶段由源符号预编码产生中间符号；第2 个阶段由中间符号进行LT 编码，产生修复符号，其译码过程采用失活译码高斯消元（Inactivation Decoding Gaussian Elimination）算法。

图4 R10码编译过程

2.2 分布式云存储系统模块

2.2.1 主要功能

客户端是用户操作及文件恢复的终端，在系统工作过程中的主要功能包括：①与云服务器交互控制信息及文件元数据信息（如文件名、文件大小和文件存储位置等）；②与云服务器交互存储文件；③与云存储节点交互副本及喷泉编码包；④译码恢复源文件。

云服务器是综合调度整个系统的服务终端，主要功能包括：①与客户端及云存储节点交互控制信号，利用Qt支持的结构化查询语言数据库功能完成控制信号数据的组织和记录；②与云存储节点交互副本及喷泉编码包。

云存储节点用来存储和传输副本及喷泉编码包，其在系统工作过程中的主要功能包括：①存储副本及喷泉编码包；②与云服务器及客户端交互副本及喷泉编码包。

2.2.2 工作过程

系统工作模式分为传统三副本＋TCP模式和喷泉码＋UDP模式两种，由云服务器选择工作模式。传输层协议采用TCP 与UDP 协议：其中TCP 协议主要用于传输文件的控制流，以及在三副本模式下传输数据流，保证数据的可靠传输；UDP 协议主要用于在喷泉码模式中传输数据流，将其与无须反馈的喷泉码特性结合，可以实现快速可靠的文件分发，其工作过程如图5 所示。

图5 分布式云存储系统模块工作流程图

文件上传时，客户端将要存储的文件上传到云服务器，其通过TCP 协议传输存储控制信息、文件元数据信息及文件数据信息，其后云服务器采用TCP协议将文件数据信息传输到云存储节点。在三副本模式中，云服务器将3 份文件数据信息存储在不同的云存储节点上。在喷泉码模式中，云服务器将文件数据信息进行喷泉编码，然后将编码后的不同编码包存储在多个云存储节点上。

文件下载时，客户端和云服务器确定下载方式后，由云存储节点向客户端提供下载服务。在单用户下载文件的场景下，三副本模式中n个存储节点分别与客户端建立TCP连接，分别传输文件的n分之一数据信息，达到并行下载的目的。在多用户下载相同文件的场景下，喷泉码模式中的云存储节点利用UDP协议向客户端广播喷泉编码包，客户端接收到足够的编码包即可进行文件的译码恢复，如未译码成功，客户端会继续接收喷泉编码包，直到文件恢复，达到可靠多播的目的。

3 分层次实验实施

3.1 验证型实验：传统三副本＋TCP 模式分布式云存储系统的实现

传统三副本分布式存储通过跨节点的副本保护，可有效防止存储节点宕机或磁盘损坏对数据恢复的影响。在单用户下载文件的场景下，基于三副本机制的分布式云存储系统可以有效保证文件数据恢复的可靠性。实验在此基础上设计而成，由以下三步组成。

（1）系统初步搭建。教师在课堂上给学生讲解该系统的设计流程、工作原理，搭建流程后。学生以小组（4 或5 人）的形式，合理分配客户端、云服务器、云存储节点个数，安装Qt开发环境，自主进行GUI设计，结合给定的参考伪代码，初步搭建三副本分布式云存储系统。

（2）系统功能开发。学生开发系统的主要功能，并通过文件的上传和下载进行功能验证。以5 人小组为例，分配1 个客户端，1 个云服务器，3 个云存储节点。客户端将文件上传后，云服务器与3 个云存储节点建立TCP连接，将文件的副本分别存储在3 个云存储节点。下载时，3 个云存储节点与客户端建立TCP连接，并行传输文件的1／3 数据信息，在客户端进行文件恢复，实现并行下载功能。

（3）模拟节点宕机。以5 人小组为例，学生在存储文件后，使其中一个云存储节点宕机，模拟存储数据丢失情景。学生小组开发功能，使剩余的两个云存储节点通过TCP 连接向客户端传输文件的1／2 数据信息，如文件可以正常恢复，则三副本分布式云存储系统搭建成功。

在验证型实验中，通过利用三副本机制的分布式云存储系统辅助教学，学生在搭建和使用的过程中可以形象、直观地学习系统工作流程及存储领域的前沿知识，同时提高学生的编程能力，极大地调动了学生的学习积极性。

3.2 综合型实验：喷泉码＋UDP 模式分布式云存储系统的实现

多用户下载场景为喷泉码＋UDP 协议的典型优势应用场景。以5 客户端下载为例，传统三副本＋TCP方式中的3 个云存储节点需要分别建立5 个TCP连接，为用户发送副本信息，存在传输效率低下的问题。基于喷泉码的分布式云存储系统通过利用喷泉码＋UDP广播的优势，只需要3 个云存储节点分别建立1 个UDP连接向5 个客户端广播足够的编码包，多个用户即可恢复源文件。学生小组配合进行实验，实现该场景下基于喷泉码的分布式云存储系统，实验由以下步骤组成。

（1）喷泉编译码算法实现。供学生选择实现的编译码算法分为两类：①LT 码编码＋BP 译码／OFG 译码；②遵循RFC5053 标准的R10 喷泉编译码，学生小组可根据能力自主选择不同难度的两种编译码算法。教师讲解两种编译码方案原理，提供设计文档，教师在一段时间后提供文件编译码算法的伪代码，学生小组通过Qt开发框架用C ＋＋语言实现文件的编译码。

（2）系统功能开发。学生将多台客户端加入系统，建立广播组。同时在实验1 实现系统的基础上，开发云存储节点的UDP广播功能，通过文件能否正常恢复测试喷泉编译码模块开发是否成功。文件上传后，云服务器通过步骤1 实现的喷泉编译码模块进行编码，随后将喷泉编码包存储在云存储节点。文件下载时，多个客户端接收云存储节点UDP 广播的编码包，测试接收足够多的编码包后能否译码成功，如果译码成功，则喷泉码＋UDP 广播功能开发成功，完整系统如图6 所示。

图6 基于喷泉码的分布式云存储系统

通过综合型实验，学生不仅可以通过喷泉编译码算法的实现锻炼编程能力和理解纠删码知识，还可以在理解网络传输协议的基础上，锻炼知识迁移能力和工程实践能力。

4 结语

本文设计的基于喷泉码的分布式云存储系统及教学实验对标我校实践教学的人才培养目标，具有极大的研究意义与价值。通过让学生将理论学习与实际应用相结合，激发学生的学习兴趣，充分发挥了学生的主观能动性。该系统专业综合程度高，知识覆盖面广，能够有效培养电子信息类学生软件开发的思维能力，锻炼学生的编程能力，经过实践取到了较好的教学效果，为理论学习与工程案例应用相结合提供了新的思路。在以后的研究中，可以尝试把喷泉编译码算法换成性能更为优秀的RaptorQ 码，译码程序中运算量较大的部分可以考虑放在图形处理器上并行实现，从而提高编译码的性能，同时考虑将存储节点从云端转到边缘，用以提高数据传输性能及降低网络带宽。