高级检索

    基于生成矩阵变换的跨数据中心纠删码写入方法

    A Cross-Datacenter Erasure Code Writing Method Based on Generator Matrix Transformation

    • 摘要: 近年来,为了避免数据因数据中心故障而永久丢失,各大机构开始尝试采用容错技术将数据存放在跨数据中心存储系统中.作为一种具有高容错性和低冗余度的容错技术,纠删码被广泛应用于单数据中心存储系统中.然而,在跨数据中心存储系统中,已有纠删码写入方法的网络资源消耗量大、编码效率低且传输效率低,这使得跨数据中心纠删码的写入速度难以适应于日益增长的数据生成速度.为提高跨数据中心纠删码的写入速度,提出了一种基于生成矩阵变换的跨数据中心纠删码写入方法(cross-datacenter erasure code writing method based on generator matrix transformation, CREW).通过对传输拓扑和生成矩阵进行优化,CREW可使写入过程中需要长距离传输的数据块尽可能地少,从而达到降低网络资源消耗量的目的.通过在数据中心间采用分布式的数据传输和数据编码、在各数据中心内部采用集中式的数据传输和数据编码,CREW可在编码效率和传输效率间取得较好权衡.在跨数据中心环境下的实验表明:与2种广泛使用的传统纠删码写入方法相比,CREW的写入速度提高了36.3%~57.9%;与现有的跨数据中心纠删码写入方法IncEncoding相比,CREW的写入速度提高了32.4%.

       

      Abstract: In cross-datacenter storage systems, existing writing methods of erasure code usually has low encoding efficiency, low transmission efficiency, and large network resource consumption. Therefore, cross-datacenters erasure code usually has a low writing rate. This paper proposes a cross-datacenter erasure code writing method based on generator matrix transformation called CREW. Specifically, we first propose a greedy strategy-based transmission topology construction algorithm called GBTC, which can construct a tree-structured transmission topology with incremental weights (the weights are set to the network distances between datacenters) from top to bottom to organize data transmission between datacenters. Then, we propose a generator matrix transformation algorithm called GMT. Without changing the linear relationship of coded blocks, GMT can transform the generator matrix so that the number of data blocks related to a coded block is negatively correlated with the network distance between the datacenter where the coded block is located and the root of the tree-structured topology. Therefore, CREW only needs to transfer a small number of data blocks through a long network distance to write data. Thus, the network resource consumption is reduced. Finally, we propose a distributed pipelined writing algorithm called DPW to distribute encoding operations to different nodes for parallel execution and limit the number of forwards of data blocks, thereby improving encoding efficiency and transmission efficiency. Experiments show that compared with writing methods of traditional erasure code, the write rate of CREW is increased by 36.3%~57.9%. And compared with the existing writing method of cross-datacenter erasure code (IncEncoding), the writing rate of CREW is increased by 32.4%.

       

    /

    返回文章
    返回