从里德-所罗门算法到Flex EC 数学是华为云真正的“硬核”

2022年 10月 19日 发表评论
腾讯云正在大促:点击直达 阿里云超级红包:点击领取
免费/便宜/高性价比服务器汇总入口(已更新):点击这里了解

“宇宙之大,粒子之微,火箭之速,化工之巧,地球之变,生物之谜,日用之繁,无处不用到数学”----华罗庚 

2012年,一本由吴军博士编著的《数学之美》畅销中国,书中将高深的数学原理讲得更加通俗易懂,让非专业读者也能领略数学的魅力。

从里德-所罗门算法到Flex EC 数学是华为云真正的“硬核”

吴军博士在书中提到知名的计算机科学家Randy Katz发明了RAID(计算机独立磁盘冗余阵列)系统,而正是RAID技术奠定了商用存储系统高性能高可靠的根基。RAID的核心思想就是使用EC(Erasure Code)纠错码来灵活地配置数据冗余度,在保持存储系统高性能高可靠的基础上,提供比多副本技术更优的存储利用率。

一.Erasure Code 和Reed-Solomon Codes:

随着云计算领域的发展,云端算力成指数型增长,5G和AI应用的崛起,海量的数据上云已经是不可逆的趋势,而云存储系统所管理的数据已经从传统企业存储TB级迈向了EB级(1EB = 1 000 000 TB),在云存储发展初期,受限于技术能力,各云存储厂商主要沿用多副本机制(通常是3副本),导致云存储系统的空间利用率只有33%,数据存储成本高居不下,而后业界通常采用EC方式来降低成本。

从里德-所罗门算法到Flex 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副本的形式写入高性能的SSDTier,凑满EC单元后再进行计算和搬移至HDD Tier。这种off-line的EC方式,其缺点有:

a)        额外的SSD Tier,成本高;

b)       持续写入对SSD可靠性的挑战;

c)        数据搬移消耗大量内部带宽。

4.       传统的EC在大比例N+M(如20+3)下,如果出现节点/介质故障,就需要读取大量数据片和校验片进行数据重构,会导致系统性能陡降。

基于以上,我们可以知道,衡量一个使用EC的数据存储系统的优劣可以通过以下几个维度来综合考虑:

1、  高效的空间利用率:一个系统能够稳定地提供多少空间利用率,在给定的N+M,空间利用率恒定。

2、  高效的写入性能:无论业务层如何变化,对象的大小如何变化,应该有恒定的写入带宽、IOPS等。

3、  高效的重构性能:尽可能少的系统重构IO带宽,尽可能少的占用跨AZ/DC的网络带宽。

二.华为云“On-line Streaming Erasure Coding” 和“Flex Erasure Coding”:

华为云OBS服务通过创新的“On-line Streaming Erasure Coding”和” Flex ErasureCoding”提供on-line的Erasure Coding存储机制,在公有云对象存储系统中解决了上述的几个关键问题。

1.       On-line Streaming Erasure Coding

如下图所示,整系统的核心部件是Streaming ErasureCoding Unit, 多个对象的数据可以流入处理单元,由其进行encoding操作。通过多个对象数据的combine,可以消除对象不满时,数据写入补零计算浪费的空间。

从里德-所罗门算法到Flex EC 数学是华为云真正的“硬核”

图2: 华为云 On-line StreamingErasure Coding

此过程不需要复杂低效的分布式事务,也不需要读取已经写入的数据。通过这个Streaming ErasureCoding 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行业的长跑选手,并且能在外部环境风云变幻的当下,保持着持续前行的动力。

从里德-所罗门算法到Flex EC 数学是华为云真正的“硬核”

图3:”数学是开启一切的工具”

华为曾在其官方媒体上发表了《基础研究与基础教育是产业诞生和振兴的根本》(链接)的文章,以官宣的方式阐述了基础研究特别是数学研究对产业发展的贡献,更是提出了“数学是开启一切的工具” 的论断。

数学,是华为继续前行指路灯,也是华为云真正的“硬核”实力。

小咸鱼

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: