从里德-所罗门算法到Flex EC，数学是华为云真正的“硬核” Erasure Code 和Reed-Solomon Codes： 华为云“On-line Streaming Erasure Coding” 和 “Flex Erasure Coding” 软件的灵魂是算法，算法的硬核是数学
【摘要】 数学算法的优化能让软件产品能力领先业界一个时代
“宇宙之大，粒子之微，火箭之速，化工之巧，地球之变，生物之谜，日用之繁，无处不用到数学。“——华罗庚
2012年，一本由吴军博士编著的《数学之美》畅销中国，书中将高深的数学原理讲得更加通俗易懂，让非专业读者也能领略数学的魅力。吴军博士在书中提到知名的计算机科学家 Randy Katz 发明了RAID（计算机独立磁盘冗余阵列）系统，而正是 RAID 技术奠定了商用存储系统高性能高可靠的根基。
RAID 的核心思想就是使用 EC(Erasure Code) 纠错码来灵活地配置数据冗余度，在保持存储系统高性能高可靠的基础上，提供比多副本技术更优的存储利用率。
随着云计算领域的发展，云端算力成指数型增长，5G 和 AI 应用的崛起，海量的数据上云已经是不可逆的趋势，而云存储系统所管理的数据已经从传统企业存储TB级迈向了EB级（1EB = 1 000 000 TB），在云存储发展初期，受限于技术能力，各云存储厂商主要沿用多副本机制（通常是3副本），导致云存储系统的空间利用率只有33%，数据存储成本居高不下，而后业界通常采用 EC 方式来降低成本。
图1：里德-所罗门码数学公式
传统的的 EC (Erasure Code) 纠错码使用的是里德-所罗门码（Reed-Solomon Codes，简称RS Codes），其在云存储系统中应用方式为：
把云存储（主要是公有云对象存储系统）的所有存储单元（单硬盘或存储节点）视为一个Erasure Code存储池，可以将对象按照N+M的方式存储(N为对象的数据分片，M为校验片)，它将对象切分成N个数据片，M个校验片。
以6+3的EC为例
空间利用率可以达到67%，更大比例的N+M将会具有更高的空间利用率，在成本上非常具有竞争力，同时，系统的吞吐量较3副本(或多副本)有较大的提升。因此，EC技术在云存储领域得到大规模的应用。
但是传统的EC机制在公有云场景下，面临着以下诸多问题：
1.在对象大小不确定的云存储场景下，需进行补零和填充计算，浪费存储空间，成本较高。
2.如不补零, 需进行多次覆盖写以保证EC成员组的原子性。这会导致系统复杂度提升，吞吐量降低，需配置更快的CPU和更大的网络带宽，存储成本增加。
3.此外,还有一种增加Cache-Tier的方式以避免EC时单元不满的问题：先以3副本的形式写入高性能的SSD Tier，凑满EC单元后再进行计算和搬移至HDD Tier。这种off-line的EC方式，其缺点有：
a) 额外的SSD Tier，成本高；
b) 持续写入对SSD可靠性的挑战；
c) 数据搬移消耗大量内部带宽。
4.传统的EC在大比例N+M(如20+3)下，如果出现节点/介质故障，就需要读取大量数据片 和校验片进行数据重构，会导致系统性能陡降。
基于以上，我们可以知道，衡量一个使用EC的数据存储系统的优劣可以通过以下几个维度来综合考虑：
✔ 高效的空间利用率：一个系统能够稳定地提供多少空间利用率，在给定的N+M，空间利用率恒定。
✔ 高效的写入性能：无论业务层如何变化，对象的大小如何变化，应该有恒定的写入带宽、IOPS等。
✔ 高效的重构性能：尽可能少的系统重构IO带宽，尽可能少的占用跨AZ/DC的网络带宽。
华为云“On-line Streaming Erasure Coding” 和 “Flex Erasure Coding”
华为云OBS服务通过创新的“On-line Streaming Erasure Coding”和“Flex Erasure Coding”提供on-line的Erasure Coding存储机制，在公有云对象存储系统中解决了上述的几个关键问题。
1.On-line Streaming Erasure Coding
如下图所示，整系统的核心部件是Streaming Erasure Coding Unit, 多个对象的数据可以流入处理单元，由其进行encoding操作。通过多个对象数据的combine，可以消除对象不满时，数据写入补零计算浪费的空间。
图2: 华为云 On-line Streaming Erasure Coding
此过程不需要复杂低效的分布式事务，也不需要读取已经写入的数据。通过这个Streaming Erasure Coding Unit，提供on-line的EC机制，避免内部的数据搬迁动作。
2.Flex Erasure Coding算法
华为云通过应用全新的 Flex Erasure Coding编解码算法，在保持数据重构效率的基础上，重构带宽需求大幅度降低，极大地提升了故障时数据重构性能，有效地缩短了重构用时，保证数据的持久度和系统吞吐量。
通过上面2个自研算法，华为云OBS单流带宽达到业界友商的3~5倍，超过300MB/S，超千万并发链接能力，并且在高业务负荷下仍然保持稳定低时延，整体性能和空间利用率相比多副本或传统EC技术大幅提升：
-
在大数据应用场景，由于写放大极具减少，单流带宽大幅提升，大数据对象case下性能倍数提升，用户能更快地获取数据分析结果。
-
在IOT场景，海量的IOT设备都需要实时向云端进行数据传输，而OBS超千万的并发能力，能支撑数亿IOT设备的连接访问。
-
在视频应用（视频监控，直播和点播）场景，华为云OBS的稳定低时延支撑高画质视频快速播放且无卡顿。
在更多的应用场景中，华为云OBS用同样出色的表现证明：数学算法的优化能让软件产品能力再次领先业界一个时代。
软件的灵魂是算法，算法的硬核是数学
“ 我认为用物理方法来解决问题已趋近饱和，要重视数学方法的突起。”——任正非
正是由于华为在数学领域长期持续的投入，让其在云+AI+5G时代的产品具有领先的竞争力。
早在1999年，华为就在俄罗斯成立了专门的算法研究所，基于俄罗斯科学家的数学能力，连续突破了3G/4G移动网络技术特殊瓶颈，使华为成为全球4G移动网络设备的领导者。而在2016年，华为再次宣布在法国设立欧洲第二个数学研究所，继续加强基础科学研究。
除了在俄罗斯和法国建立的数学研究所，华为还积极参与并投资包括中国在内的全球数学家的科研项目，积极推动数学研究和数学成果在产业的落地。在华为的长期支持下，Erdal Arikan教授在 Polar 码上取得了多项突破，最终成为5G控制信道编码标准，推动了通信技术的发展。
而正是基于数学和其他基础科学研究成果在芯片设计、集成电路开发、软件算法和质量管理等方面的应用，华为才能成为 ICT 行业的长跑选手，并且能在外部环境风云变幻的当下，保持着持续前行的动力。
图3：”数学是开启一切的工具”
华为曾在其官方媒体上发表了《基础研究与基础教育是产业诞生和振兴的根本》的文章，以官宣的方式阐述了基础研究特别是数学研究对产业发展的贡献，更是提出了“数学是开启一切的工具” 的论断。
数学，是华为继续前行指路灯，也是华为云真正的“硬核”实力。