基于纠删码的区块链存储优化

Blockchain Storage Optimization Based on Erasure Code

区块链具有去中心化、不可篡改、可追溯以及公开透明等特性,可以解决去中心化网络中节点之间相互不信任的问题,为构建价值互联平台提供了可能.然而,区块链要求每个节点都存储一份完整的数据,以高存储冗余来保证数据的可靠性,给节点带来了巨大的存储压力,降低了存储资源的利用效率,也导致系统的存储可扩展性成为区块链性能的一个瓶颈.采用纠删码来编码存储在区块链中的数据可以有效地减少存储冗余,但存储冗余的减少会降低数据的可靠性,引发数据的重组消耗,提高数据的读取延迟.目前已有研究在区块链编码数据块的存储分配阶段并没有考虑节点间延迟、区块存储位置等因素对数据可靠性和读取延迟的影响.本文在基于纠删码的BFT联盟链中,研究编码数据块的存储数量及存储位置决策问题,以在满足数据可靠性的约束下实现数据存储代价和数据读取性能的平衡.针对编码数据块的存储数量及存储位置决策问题,本文提出了延迟感知的编码数据块分配算法(Latency-aware Encoded data chunks Allocation algorithm,LEA).算法LEA首先求解编码数据块的存储数量及存储位置决策问题的松弛问题以及该松弛问题的对偶问题,然后根据松弛问题及其对偶问题的最优解依次为每个编码数据块确定其存储数量和存储位置,最后调整得到的编码数据块存储分配方案使其满足被松弛的约束条件.理论分析证明,算法LEA是ln 3+2近似算法.仿真环境和真实联盟链系统中的实验结果表明,算法LEA可以有效降低区块链系统的存储冗余,提高系统的存储可扩展性,并实现良好的数据存储代价和数据读取性能的平衡.

Blockchain has the characteristics of decentralization,unforgeability,traceability,transparency,etc.Therefore,blockchain can solve the problem of mutual distrust between nodes in the decentralized network and provide a viable way to build a value-connected platform.However,blockchain requires each node to store a complete copy of data to ensure data reliability with high storage redundancy.Unfortunately,it also brings huge storage pressure to blockchain nodes and reduces the utilization of storage resources,which makes the storage scalability be a bottleneck of blockchain.Meanwhile,with the increasing number of transactions,the size of blockchain also increases rapidly,which hinders the nodes with limited storage capacity to join the blockchain system and hence weakens the decentralization of the system.Using erasure code to encode the data stored in the blockchain can effectively reduce the storage redundancy.Nevertheless,the reduction of storage redundancy will reduce the reliability of the data,incur data recovery costs,and increase the data access delay.The existing work on reducing the storage redundancy in blockchains ignores the impact of inter-node delay and encoded data chunk storage locations on data reliability and data access delay during the data chunk placements,while there is a tradeoff between data storage cost and data access latency.In this paper,we study the decision problem of the number and locations of encoded data chunk copies with the erasure code in BFT permissioned blockchains,with the aim to achieve a good balance between data storage cost and data access latency under the data reliability constraint.We also propose a Latency-aware Encoded data chunks Allocation algorithm(LEA).Firstly,algorithm LEA solves the relaxation problem of the studied problem and the dual problem of the relaxation problem.The relaxation simplifies the problem model and facilitates the solution of the problem.We classify the solutions of the relaxation problem into clusters.Specifically,we select a node as the cluster center based on the optimal solution of the dual problem,and put the nodes into different clusters according to the optimal solution of the relaxation problem.Secondly,at least one node in each cluster is randomly selected to store the copy of the coded data chunk according to the optimal solution of the relaxation problem.Finally,the algorithm adjusts the storage allocation solution to satisfy the constraints of the decision problem.Theoretical analysis proves that algorithm LEA is a ln 3+2 approximation algorithm to the data allocation decision problem.We conduct extensive experiments in both the simulation environment and the real permissioned blockchain system.The experimental results show that algorithm LEA can achieve good performance in terms of the tradeoff between data storage cost and data access delay,while satisfying the data reliability constraint.Algorithm LEA can effectively reduce the blockchain storage cost,enhance the blockchain storage capacity with the increase of the number of nodes,and realize the horizontal scalability of the system storage.Compared with the existing algorithms,algorithm LEA can achieve better data access performance in different networks,and the performance improvement can reach 15.2%.In addition,we evaluate the impact of the number of malicious nodes on the performance of the algorithm.When there are malicious nodes in the network,algorithm LEA can still obtain favorable data access performance while ensuring data reliability,which outperforms the existing algorithms by 15.4%.