四元域上最优局部可修复码的分类_奚元霄.pdf

中国科学:数学2023年第53卷第2期:339368SCIENTIA SINICA Mathematica论文英文引用格式:Xi Y X,Kong X L,Ge G N.A classification for optimal quaternary locally repairable codes(in Chinese).Sci SinMath,2023,53:339368,doi:10.1360/SSM-2022-0041c 2022中国科学 杂志社四元域上最优局部可修复码的分类献给朱烈教授80华诞奚元霄1,孔祥粱2,葛根年21.浙江大学数学科学学院,杭州 310058;2.首都师范大学数学科学学院,北京 100048E-mail:yuanxiao ,,收稿日期:2022-03-14;接受日期:2022-05-17;网络出版日期:2022-08-24;*通信作者国家重点研发计划(批准号:2020YFA0712100 和 2018YFA0704703)、国家自然科学基金(批准号:11971325)和北京学者项目资助项目摘要近年来,为了提高分布式存储系统的容错性和可靠性,编码学家们引入了几类新的编码方案,其中局部可修复码(locally repairable codes,LRC)起到了重要的作用.对于一个线性码,若它的一个码字符号能通过其他至多r个码字符号修复,则称其具有局部性参数r.码长为n、维数为k、局部性参数为r的LRC(n,k,r)-LRC),其极小距离d满足Singleton型界d 6 nk k/r+2.自LRC被提出以来,有许多工作研究小域上达到Singleton型界的码类.本文从码的校验矩阵角度出发,利用组合设计和有限几何的工具,研究了达到Singleton型界的最优四元LRC.本文证明了在四元域上共有27类最优的LRC,并且给出了这些最优码的构造.不仅如此,利用有限几何工具,本文还引入了判断最优LRC存在的新方法.关键词局部可修复码组合设计有限几何大数据存储MSC(2020)主题分类51E20,94B05,94B60,68P201引言随着近几十年来互联网及信息产业的飞速发展,数据作为新的生产要素已经渗透到人们生产生活的各个方面,并发挥着无可替代的重要作用.在如今“大数据”时代,为了能够极大地发挥数据这一生产要素的作用,人们面临的首要问题是如何对数据进行有效地存储.为确保存储的可靠性,传统方法是将同一文件的多个副本存储在不同的单元上.就存储开销而言(存储开销是指总存储数据量与文件本身数据量的比率),这种复制策略显然是低效的.现代数据中心可以存储数EB的数据(1 EB=109GB),如此庞大的存储量带来的成本不仅体现在硬件和软件方面,还有电力和人力资源的消耗.因此,减少存储开销至关重要.在不影响存储可靠性的情形下,减少存储奚元霄等:四元域上最优局部可修复码的分类开销的一种有效方法是使用纠错码替代复制策略:使用n,k纠错码存储文件时,文件首先被分成k个片段,再以某种编码形式添加n k个冗余片段,最后将生成的n个片段分别存储在n个存储单元中,由此产生的存储开销即为nk.在最小化存储开销方面,极大距离可分(maximum distance separable,MDS)码十分有效.这是因为在相同参数的纠错码中,MDS码具有最大的纠错能力,因此在存储当中具有最高的存储效率.同时,相较于普通的纠错码,MDS码可以通过连接任意k个存储单元获取整个文件,这意味着一个MDS码可以容忍任意至多n k个存储单元的故障而依旧保持数据的完整性.由于以上诸多优点,基于MDS码的分布式存储系统在过去的一段时间里获得了广泛的应用,其中又以Reed-Solomon(RS)码的应用最为广泛,如Hadoop分布式文件系统(Hadoop distributed system-erasure coding,HDFS-EC)中的9,6-RS码、Facebook的f4-BLOB存储系统中使用的14,10-RS码和百度的Atlas云存储系统中使用的12,8-RS码8.若只考虑存储效率与容错能力的关系,基于MDS码的存储方式是最优的.然而,现实世界中nk个节点同时损坏是很罕见的,最常见的往往是零星一两个节点发生故障(参见文献37,40).于是,存储编码的设计中需要考虑的第二个要素是能否高效修复单个存储单元的故障1).为简便起见,下文将用节点或存储节点来指代每个存储单元.为修复故障节点,需要从其他有效节点中下载数据,这些提供数据的有效节点被称为辅助节点,修复过程中需联系的辅助节点的数目被称为修复度.节点修复过程中从辅助节点下载到替换节点的数据量被称为修复带宽.若使用n,k-MDS码,则修复单个故障节点的常规方法如下:联系某一组k个辅助节点,下载来自这k个辅助节点的全部数据.根据MDS码的性质,这使得我们能够重建整个文件的所有数据,因此也自然能够修复故障节点上的数据.在这种方式下,修复带宽是替换节点存储数据量的k倍,这显然是对网络带宽资源的浪费.在较大规模的高速存储系统中,最终将会堵塞存储网络.为了降低单个节点的修复带宽,编码学家提出了两类新的编码以减少整体修复带宽为目的的再生码(regenerating codes)10和以最小化修复度为目的的局部可修复码(LRC)14.本文主要介绍局部可修复码的相关概念及其进展.关于再生码的相关理论可参见文献15,26,27,29,38,39,43,4547,50,51.特别地,本文将利用组合设计和有限几何的工具,对四元最优局部可修复码的所有参数进行分类.1.1局部可修复码的概念及推广码的局部性概念由Oggier和Datta34及Gopalan等14分别提出.称码字的第i位具有局部性r,若它能被其他至多r位上的信息修复.引入LRC的重点是降低修复度17,23,即减少参与修复某损坏节点的辅助节点的个数.这里有两点需要注意.首先,相比于再生码等其他存储编码,降低修复度确实能够降低修复带宽,这是LRC的重要优点.其次,用非平凡LRC(局部性参数大于1)进行编码的存储系统,其存储开销必然会大于利用MDS码进行编码的存储系统的存储开销.换言之,LRC2)通过牺牲一定的存储开销降低对单个损坏节点(或多个损坏节点)进行修复的修复带宽.在实际应用中,这对于修复带宽的降低是显著的,大大地节约了时间成本.同经典的纠错码一样,LRC的各个参数之间也存在着制约关系.为了能够在保证纠错能力的情形下,尽可能地提升码率,降低局部性参数,编码学家们针对各个参数,分别提出了不同类型的最优LRC,其中包括具有最大极小距离的d-最优局部可修复码、具有最大维数的k-最优局部可修复码和具有最优“局部-整体”纠错性能平衡的极大可修复码.1)节点故障不仅包括存储单元的实际物理故障,还包括存储单元因维护而停机或由于竞争服务请求而无法使用的情形.2)类似于再生码中的MBR(minimum bandwidth regeneration)码.340中国科学:数学第 53 卷第 2 期极小距离作为纠错码纠错能力的一个重要指标,它与其他参数之间的关系是经典编码理论研究中的重要问题.作为一类特殊的纠错码,LRC具有局部性这一新的参数,它是如何同码长、维数一起影响LRC的纠错能力的呢?Gopalan等14给出了LRC的Singleton型界d 6 n k kr+2.(1.1)它可以看作是纠错码的Singleton界的推广:当r=k时,其退化成了经典纠错码的Singleton界.给定n、k和r,如果LRC的极小距离满足(1.1),则称LRC是d-最优的.关于d-最优LRC,编码学者们给出了多种构造.例如,对于一般的d,Tamo和Barg44用一类特殊多项式生成的Reed-Solomon码给出了一类d-最优LRC的构造.在传统的编码研究中,长码具有更加良好的传输性能和更高的鲁棒性.为了现实需要,人们更希望能够在给定域的大小q的情形下,构造尽可能长的d-最优LRC.上述Tamo和Barg构造得到的d-最优LRC,其长度至多为q 1.此后,Jin等25运用有理函数域的自同构群将d-最优LRC的长度提高到q+1.2019年,Li等28运用椭圆曲线构造了特定r下的d-最优LRC,并将其长度提高到了q+2q.当d=3,4时,Luo等30运用循环码给出了无限长度的d-最优LRC.此外,Xing和Yuan49又从稀疏超图的角度给出了当d较大时,长度达到q的超线性级别的d-最优LRC.之前提到的Singleton型界给出的是极小距离与码长、维数、局部性间的权衡关系,并不依赖于码所在有限域的大小.这不禁使人思考,有限域的大小与LRC的极小距离、码长、维数、局部性间是否也存在着某种权衡关系?2015年,Cadambe和Mazumdar2给出了第一个与q相关的LRC各参数间的权衡关系的界,并称其为Cadambe-Mazumdar(C-M)界,k 6 mintZ+tr+k(q)opt(n (r+1)t,d),(1.2)其中k(q)opt(n,d)代表给定q、n和d下的线性码的最大维数.达到(1.2)中上界的LRC也被称为k-最优LRC.关于其构造,也有不少研究,例如,二元的Simplex码2被发现是k-最优LRC,Anticode42被发现可以用来构造r=2,3时的k-最优LRC.此后,Wang等48运用传统编码中球填充界的想法对(1.2)进行了改进.2019年,Ma和Ge31运用纠错码理论中Johnson界的想法再次改进了文献48中的球填充界.随着研究的不断深入,码的局部性这一概念得到了不同方向的推广.例如,Prakash等36引入了(r,)-局部性的概念,将每个修复集只能修复一个错误推广到可以修复 1个错误.上述LRC是=2的特殊情形.类似地,Prakash等证明了(r,)-LRC的Singleton型界:d 6 n k+1(kr 1)(1).(1.3)构造达到(1.3)的d-最优(r,)-LRC的工作也有很多,参见文献3,5,6,52.作为另一类重要的推广,极大局部可修复码(maximally recoverable(MR)-LRC)最初由Blaum等1提出.同一般的LRC相比,MR-LRC给出了最优的局部纠错性能和全局纠错性能的平衡:称q元码C为参数(n,r,h,a,q)的MR-LRC,如果(1)码C具有(r,a)-局部性,即其码字字符能够被分成nr+a个局部修复组,码C限制在每一个局部修复组上均为参数为r+a,r的MDS码;(2)码C具有信息论上的极大可修复性,即对于任意在每个局部修复组中取至多a个、再从全局取至多h个组成的至多nar+a+h个擦除错误,码C均可纠正.341奚元霄等:四元域上最优局部可修复码的分类前文中所介绍的达到Singleton型界的d-最优LRC可以视作是固定局部性参数下的具有最优全局纠错能力的线性码.与之相比,对于具有局部性结构的错误类型,MR-LRC具有更强的纠错性能.因此,MR-LRC可以视作是能够纠正具有局部性结构擦除错误的MDS码的推广.利用Schwartz-Zipple引理,Gopalan等14证明了在n的指数阶大小的域上一般参数的MR-LRC的存在性.由于在实际应用中,小域上具有更快速的编码、译码及运算算法,因此,自MR-LRC提出以来,编码学家们一直致力于在小域上构造MR-LRC.例如,Gabrys等13通过校验矩阵,将特定参数的MR-LRC的存在性与t-组间独立集(t-wise independent set)的存在性联系起来,在具有n的多项式级别大小的域上构造了一类MR-LRC;Guruswami等16利用函数域,也给出了n的多项式级别大小的域上MR-LRC的构造;Mart nez-Pe?nas和Kschischang32进一步利用线性化RS码给出了在ra 6 h时更好的构造;Cai等4也利用了线性化RS码给出了具有最优有限域大小的MR-LRC的构造.1.2四元d-最优LRC的分类同上文中提到的MR-LRC类似,由于在实际应用中,小域上有成熟的快速算法