CIF: Small: Fundamental Analysis and Design of Repair-Efficient Cloud Storage Systems: a Linear Perspective

云存储系统越来越多地被网络搜索、云计算、分布式文件共享等广泛的数据密集型应用所采用，以及各种具有高访问需求的数据网络，包括社交网络、健康和医疗数据库、银行系统。云存储系统由多个数据中心和计算机服务器通过互联网连接而成。虽然系统的各个组件会受到几种类型的故障的影响，但从数据可用性的意义上讲，可靠性和再生故障存储节点的能力是设计云存储系统的两个关键特征。随着存储数据的大小和访问数据的用户数量持续增加，设计健壮、高效和可扩展的系统是一个具有挑战性且至关重要的问题。本研究将为高效云存储系统的设计和分析奠定坚实的理论基础。在技术方面，本研究将集中于(1)研究云存储系统的存储开销和修复需求之间的权衡，以及(2)开发高效的编码方案以保证数据恢复和故障节点的再生。虽然描述一般信息论的权衡似乎是困难的，但通过将问题限制在实际相关的低复杂度的线性码的类，并利用有限域上的线性码和多维子空间之间的对偶，可以取得进展。为这个问题制定了一个优化问题，其中对最优解的智能解释为设计代码构造机制提供了有洞察力的指导方针。最后，提出了一个代码构建的统一框架，不仅包括几个特别设计，而且将构建推广到系统的所有最优运行点。

Cloud storage systems are increasingly being adopted by a wide spectrum of data intensive applications such as web search, cloud computing, distributed file sharing, and various types of data networks with high access demand, including social networks, health and medical databases, and banking system. A cloud storage system consists of several data centers and computer servers that are connected through Internet. While individual components of the system are subject to several types of failure, reliability, in the sense of data availability, and ability of regenerating failed storage nodes are two key features to design cloud storage systems. As the size of stored data and the number of users accessing the data continues to increase, designing robust, efficient, and scalable systems is a challenging and yet critically important problem. This research will develop a solid theoretical foundation for design and analysis of efficient cloud storage systems. On the technical side, this research will focus on (1) studying the tradeoff between storage overhead and repair requirements in cloud storage systems, and (2) development of efficient coding schemes with guarantees on data recovery and failed node regeneration. While characterizing the general information-theoretic tradeoff appears to be intractable, progress can be made by limiting the problem to the class of practically relevant and low-complexity linear codes, and exploiting the duality between linear codes and multi-dimensional subspaces over finite fields. An optimization problem is formulated for this question, where an intelligent interpretation of the optimum solution provides insightful guidelines to devise code construction mechanisms. Lastly, a unified framework is proposed for code construction, to not only encompass several ad-hoc designs, but also generalize construction to all optimum operating points of the system.