• 期刊，《计算机工程》

• 2019年

• 关键词：分布式存储系统；纠删码；数据容错；数据编码；数据冗余

• HRC 码是一种具有存储效率高、计算复杂度低等优点的纠删码， 但其存在编解码计算开销大、实现较为复杂等不足。通过对 HRC 码的译码算法进行优化， 提出一种新型的纠删码 HRCSD。采用内外层分层结构， 内部的冗余由 HRC 码的编码结构组成， 外层采用偏移复制策略， 将原始信息进行旋转存储， 能够实现并行读写。实验结果表明， 与三副本技术和 S 2-RAID 纠删码相比， HRCSD 纠删码具有容错性能高、修复开销低等优势， 可满足大规模分布式存储系统的容错需求。

• 引用格式

  孙黎， 苏宇， 张弛， 等． 分布式存储系统中的纠删码容错方法研究[J]. 计算机工程，2019， 45( 11) : 74-80．

• 本文针对目前大规模分布式存储系统中数据容错存储效率低、纠删码的编译码计算复杂等问题， 提出一种具有较高容错能力且能够快速实现的纠删码容错编码 HRCSD。HRCSD 基于 HRC 进行偏移复制得到， 通过复制技术， 可满足在分布式系统中对数据的并行读取需求。实验结果表明， 与三副本技术和 S2-RAID 码相比， HRCSD 具有较低的存储开销、较高的容错能力和单节点故障下快速修复的性能。本文提出的 HRCSD 在故障修复过程中考虑的是单一节点发生故障的情况， 下一步将研究多节点发生故障的修复方式， 以降低修复带宽， 加快数据的修复 。

没怎么仔细看，不过估计作用不大。

2. 基于piggybacking框架的分布式存储编码研究

基本信息

• 硕士论文

• 2019年

• 关键词：Piggybacking编码；MDS码；分布式存储；节点修复修复；带宽比率

• 摘要

  互联网、5 G 及其相关产业的飞速发展使我们迈入了大数据时代，存储海量数据将面临着巨大挑战。为了解决大数据存储中存储节点失效的问题，具有容错能力且节约存储资源的分布式存储编码成为大数据时代重点研究的核心技术之一。Piggybacking 编码作为分布式存储编码中的一类，以其优异的节点修复性能和较高的存储效率，再加上其复杂度低，设计灵活等特点，最近几年受到了越来越多的关注。本论文主要面向数据的容错存储，针对存储中的节点修复问题，为大数据和移动数据的分布式存储编码提供理论基础，为海量数据的高效、可靠存储提供技术支撑。

  首先，本论文对传统的数据存储容错，即多副本机制和 MDS 码进行了概述。接着介绍了三种主要的分布式存储编码，即再生码（RGC）、局部可修复码（LRC）和piggybacking 编码的基本原理、 发展现状以及它们各自的优缺点，为后续深入地研究打好基础。

  其次，本论文针对一种用于修复校验节点的 piggybacking 框架提出了两种改进。在保持编译码复杂度基本不变的前提下，第一种针对修复校验节点的改进使得信息节点和校验节点的修复带宽均有不同程度地降低，且改进后 piggybacking 框架的设计更加灵活多变。第二种针对信息节点修复的改进，通过牺牲校验节点很小部分的修复带宽来换取节点数更多的信息节点的修复带宽是有意义的。

  再次，本论文先对广义 piggybacking 编码进行了深入研究，指出了其校验节点修复存在的部分问题。更重要的是，本文基于广义 piggybacking 编码框架首次提出了 piggybacking 编码的多节点修复策略。经分析得到了诸如修复节点数、保护列比例、设计列比例、信息节点数以及校验节点数等因素对多节点的最小平均修复带宽比率产生的影响。这对设计出多节点修复性能优良的 piggybacking 编码具有一定的参考价值。

  最后，本论文提出了一个全新的双层 piggybacking 框架（D-PB-1），通过最优化预留子条带比例 $p_a$和捎带子条带比例$p_b$同时有效地修复了信息节点和校验节点，大大降低了修复带宽。经分析，当信息节点数 𝑘 和校验节点数 𝑟 趋于无穷大时，所有节点的平均修复带宽比率无限接近于 0。其次，本文又提出了改进的双层piggybacking 框架（D-PB-2），通过改变修复信息节点的 piggyback 块的构造方式进一步降低了修复带宽。与其它 piggybacking 编码相比，这两类双层 piggybacking 编码不仅结构设计灵活，还拥有最佳的综合修复能力，尤其以 D-PB-2 表现最佳。接着本文还给出了双层 piggybacking 框架多例嵌套的模型，在保证修复性能不变的前提下，降低了 piggybacking 框架中的子条带数。最后，本文通过分析一种针对 MDS 码校验节点的构造方式，联系到改进的双层 piggybacking 编码的一种极端情况，揭示了它们修复本质相同的事实。另外，本文据此在理论上还给出了基本 piggybacking框架节点修复下限的猜想。

• 引用格式

  李鑫, 基于piggybacking框架的分布式存储编码研究, 2019, 西安电子科技大学. 第 103页.

摘录

• 首先介绍了传统的多副本，MDS，再生码，局部可修复码；

• Piggybacking 框架是在一个任意的、 我们称之为基本码的基础上操作的，目前的基本码都采用 MDS 码。piggybacking 编码保持了基本码的很多属性，比如最小距离和操作域。简单来说，piggybacking 框架是考虑 MDS 码的多个例（条带），并将某些例的数据通过设计的 piggyback 函数（线性组合）嵌入到其它例中，在修复失效节点的过程中将一部分 MDS 译码的操作转化为求解 piggyback 方程，有效地降低了修复带宽。通常 piggybacking 编码采用系统形式，因为系统形式中的信息节点承载了所有未编码的原始数据。因此用户通过直接访问信息节点就可以得到原始数据而不用访问某些校验节点采用 MDS 译码来恢复原始数据，这样不仅降低了获取原始数据的复杂度，还降低了获取数据的延迟。

  

• 两种改进的piggybacking编码，一种针对修复校验节点的改进，一种针对修复信息节点的改进；

• 多节点修复；

• 双层piggybaing框架的分布式存储编码；

思考

信息量太大，目前为止我还是不知道piggybacking到底是什么玩意儿，最奇怪的是整篇文章貌似并没有做任何实验，更涉及不到什么Ubuntu，什么分布式存储系统，貌似就是纯数学领域的推理，然后用推导出的公式带入不同的数值就形成了曲线，从这个角度来说貌似好像还挺轻松，我压根不需要什么分布式环境，什么多节点机器，只需要一些基础理论知识，加以时日的思考，但涉及到数学又是最难的东西。

• PPT

• 2013

• 关键词：无

• 摘要

  这是Rashmi做的一场关于Piggybacking框架的汇报。

• 引用格式

  无

无

解决了我诸多疑惑：

• MDS码到底是怎么实现的，比如RS code，跟多副本有什么区别：

• piggybacking框架的最简单的实现：

• 一般化的piggybacking框架：

  

• piggybacking does not reduce minimum distance: can choose arbitrary functions (任意函数)for piggybacking.

• 通过piggybacking框架可以：

  • High-rate MDS codes：Lowst known IO & download during repair；
  • Binary MDS（vector）codes：
    • Lowst known IO & download during repair；
    • for all parameter where binary MDS(vector) codes exist
    • lowest when #parity >= 3; En Gad et al. ISIT 2013 for #parity = 2
  • Enabling parity repair in regenerating codes designed for only systematic repair
    • efficiency in systematic repair retained;
    • parity repair improved.
  • Currently implementing (14,10) Piggyback-RS in HDFS:
    • 30% reduction in IO and download;
    • same storage & fault tolerance.

• 为什么不用High-rate Minimum Storage Regenerating(MSR) codes 作为基本码：require block length exponential in k (Tamo et al. 2011)

  

  

• (14,10) Piggybacked-RS code

  

• 需要的connectivity > in RS, 这是否是一个值得关注的问题？

  

• 未来工作与开放性问题：

  

• 2019 IEEE International Conference on Consumer Electronics - Taiwan, ICCE-TW 2019

• 2019年

• 关键词：

• 摘要

  The InterPlanetary File System (IPFS) is a peer-to-peer distributed file system. It can greatly reduce the cost of data storage and improve the performance of data download. Currently, the IPFS-based distributed storage systems mostly uses the centralized backup mechanism. Although it can provide high data availability, centralized nodes will be single fault peer and become the bottleneck of system performance. This paper proposes a high-availability data backup strategy based on QoS and interest of IPFS nodes. Compared with the existing methods, the experimental results demonstrate that our proposed strategy is more effective and practical.

• 引用格式

  Shi, L., Luo, H., Yang, X., & Sun, Y. (2019, May 1). A High-availability Data Backup Strategy for IPFS. 2019 IEEE International Conference on Consumer Electronics - Taiwan, ICCE-TW 2019. https://doi.org/10.1109/ICCE-TW46550.2019.8991855

• 系统模型

• 实验

• 

• 这篇文章首先很短，其实几乎什么都没写。看似好像提出了IPFS的新的备份策略，但他们提出的节点之间的距离d，甚至都没有给出明确的定义，什么是节点距离，如何定义，无法得知，在这种情况下，设计的算法事实上是无法站住脚的。

• 在具体实验中，原文写的是：

  An IPFS system with 50 nodes is constructed using MAT-LAB simulation.

  这句话，无论怎么翻译都是在MATLAB Simulink中实现了IPFS系统。（卧槽，这么高级的吗？！）但事实上，我发了邮件询问之后才发现，并不是。。。一个说不是我做的实验，并没有代码，另一个直接说MATLAB中没有IPFS系统。好吧，是我的英文理解有限，瑞斯拜。

• 最后，事实上这个备份算法的实质：直接复制进行备份。只不过在节点的选择上，设计了一些特别的算法，但在节点选择算法中最关键的节点距离定义却一笔带过，没有详细定义，实在不知道他们是如何进行节点选择的。

• IEEE International Symposium on Information Theory - Proceedings

• 2013年

• 关键词：Distributed storage; bandwidth and I/O; code-design framework; erasure codes; repair

• 摘要

  We present a new piggybacking framework for designing distributed storage codes that are efficient in the amount of data read and downloaded during node-repair. We illustrate the power of this framework by constructing explicit codes that attain the smallest amount of data to be read and downloaded for repair among all existing solutions for three important settings: (a) codes meeting the constraints of being maximum distance separable (MDS), high-rate, and having a small number of substripes, (b) binary MDS codes for all parameters where binary MDS codes exist, and (c) MDS codes with the smallest repair-locality. In addition, we show how to use this framework to enable efficient repair of parity nodes in existing codes that are constructed to address the repair of only the systematic nodes. The basic idea behind this framework is to take multiple stripes of existing codes and add carefully designed functions of the data of one stripe to other stripes. Typical savings in the amount of data read and downloaded during repair are 25% to 50% depending on the choice of the system parameters. © 2013 IEEE.

• 引用格式

  Rashmi, K. V., Shah, N. B., & Ramchandran, K. (2013). A piggybacking design framework for read-and download-efficient distributed storage codes. IEEE International Symposium on Information Theory - Proceedings, 63(9), 331–335. https://doi.org/10.1109/ISIT.2013.6620242

• piggybacking编码示意图

• Four classes of explicit code constructions

  • (Class 1) A class ofcodes meeting the constraints ofbeing MDS, high-rate, and having a small number of substripes, with the smallest known average amount of data read and downloaded for repair.
  • (Class 2) Binary MDS codes with the lowest known average amount of data read and download for repair, for all parameters where binary MDS codes exist.
  • (Class 3) Repair-efficient MDS codes with smallest possi-ble repair-locality.
  • (Class 4) A method for reducing the amount of data read and downloaded during repair of parity nodes in existing codes that address only the repair of systematic nodes.

• Framework

• Desgin 1

• Experiment Results

• 这是冗余纠删领域在2013年的一篇具有很强开创性的具有引领整个领域发展方向的重磅文章。基于现有的MDS再加上新的编码层，在不改变既有的工业界已投入使用的算法上，附加上新的规则，并且能极大降低读取与下载的负荷，应该说是非常厉害的原创性工作，类似于2012年的获得ImageNet第一的AlexNet之于深度学习与图像识别，以及2016年的XGBoost之于机器学习与数据挖掘。
• 就像在那之后AI领域大放异彩，就快取代所有基础自然学科一样，仿佛这世界只有一种学科。当然对于piggybacking没有如此神乎其神，但它确实有着这样的潜力，毕竟Rashmi等人提出的是一种框架，而后人可以在这个框架上进行各种改造，以达在实验上得到更加优秀的存储上传下载实验数值，在这个层面上来说类似于AI调参一样，可以调出优秀的参数，只是从复现上来说，不仅仅是装个python环境，import一些包，安装一些tf，pytorch之类，敲几行代码而已，这里的调参意味着首先要有一套完善的实验环境，从搭建存储系统，构建冗余算法，感觉步步是坑呢。
• 当然还有一个问题就是这篇文章涉及的旧有算法太多，并且又掺杂了自己的新算法，而且是基于MDS实现的，意味着还要熟悉MDS的具体思想与构建方法，此外还有大量的数学推导，又增加了理解难度，不提复现，理解起来难度就不小。只能继续看看往后七年里面有没有将其实现，并且以更加易于理解的方式解析的文章。

• 硕士论文，哈尔滨工程大学

• 2011年

• 关键词：P2P存储系统；冗余策略；服务成本；数据恢复；访问频度

• 摘要

  随着互联网的快速发展,互联网上的数据呈现几何级数态势增长,大量的多媒体数据充斥在网络中,网络上海量数据的增长给传统的存储系统技术带来了严峻的挑战,基于P2P网络的存储系统因具有高可扩展性、能充分地利用各种潜在资源等优点而成为存储主流技术。然而一旦存储系统数据因自然灾害、网络攻击或人为恶意损坏而无法及时访问,就会对工作生产造成影响甚至是难以弥补的损失,因此,如何保证基于P2P存储系统的数据可靠性成了当前的研究热点。

  本文深入研究了结构化P2P覆盖网的数据可靠性,针对P2P网络存储系统数据冗余策略和数据恢复策略进行优化和改进。

  为提高冗余策略的效率,对不同的冗余策略算法进行比较分析,针对传统的P2P存储系统采取单一的冗余策略所带来冗余效率低的问题,提出基于用户体验和服务成本的冗余策略,该策略分析用户数据价值,根据服务成本模型,制定对应的冗余规则。根据冗余规则,对不同的数据特征进行最合适的冗余编码方式。设计原型系统并进行实验,并通过实验验证该方法的有效性。

  针对P2P存储系统本身节点概率性掉线导致数据失效的问题,为保证数据的可靠恢复,提高系统的数据恢复策略的稳定性,提出基于访问频度的数据可靠恢复策略,当冗余数据量不足时,根据恢复节点的访问频度模型制定数据恢复策略。设计模拟仿真试验,并通过实验验证该方法的有效性。

• 引用格式

  许劲斌, P2P网络存储系统的数据可靠性研究, 2011, 哈尔滨工程大学.

1.完全副本复制冗余：

• 纠删码原理图
• 纠删码比较
• 基于用户体验和服务成本的数据冗余策略
  • 其中数据分发流程
• 基于访问频度的数据可靠恢复策略
  • 数据失效的发现机制
    • 定期心跳法，是指每个数据节点定期向其对应的目录主节点报告自己存在数据的状态,如果对应的目录节点一段时间内没有收到该节点发送过来的心跳则认为该数据节点下线。
    • 失效事件广播法，是指存放目录主节点定期主动探测其负责的数据节点的状态,如果探测失败,则认为该数据节点下线。
  • 具体算法：

作者说进一步的研究和探索：在复杂的网络环境中,大量节点的频繁加入或退出的条件下

• 怎样更好的维持数据的负载均衡,以提高可靠访问；
• 各冗余副本之间如何高效、合理的保证数据的一致性；
• 研究如何能够更精确地测量数据的访问频度,以制定更加符合应用的可靠恢复策略；
• 研究如何更好的精确查询。

这篇文章，还是在可以想见的范围内对冗余算法进行了改进，就是基于访问热度的冗余策略，另外让我注意到了(当然以往也有看到)，在冗余之后的如何分发是一个比较困难的问题。

1.分布式存储系统中容错技术综述

基本信息

• 期刊论文，《无线电通讯技术》

• 2019年

• 关键词：分布式存储；MDS码；再生码；局部可修复码；Piggybacking编码

• 摘要

  互联网5G及其相关产业的飞速发展使我们迈入了大数据时代，存储海量数据将面临着巨大挑战。大规模分布式存储系统以其海量存储能力、高吞吐量、高可用性和低成本的突出优势取代了集中式存储系统成为主流系统。由于分布式存储系统中节点数量庞大，经常会产生各种类型故障，从而导致节点失效情况频。因此，必须采用容错技术来保证在部分存储节点失效的情况下，数据仍然能够被正常读取和下载，具有容错能力且节约存储资源的分布式存储编码成为大数据时代重点研究的核心技术之一。讨论了大数据背景下存储与可靠性的问题，从而引出数据容错对分布式存储的重要性。阐述了传统的２种数据存储容错技术，即多副本机制和ＭＤＳ码。重点分析了３种主要的分布式存储编码，即再生码（RGC）、局部可修复码（LRC）和Piggybacking编码的基本原理、优缺点以及发展现状。总结对比了这５种数据容错技术的性能差异。面向数据的容错存储，针对存储中的节点修复问题，为大数据和移动数据的分布式存储编码提供理论基础，为海量数据的高效、可靠存储提供技术支撑。

• 引用格式

  李鑫, 孙蓉与刘景伟, 分布式存储系统中容错技术综述. 无线电通信技术, 2019. 45(05): 第463-475页.

摘录

• MDS码（Maximum Distance Separable最大距离可分）：如Reed——Solomon，RS码，Google Colossus，HDFS Raid，Microsoft Azure，Ocean Store。存储成本更低，但是其拥有更高的修复成本和访问延迟，而且没有考虑存储开销、磁盘Ｉ／Ｏ 开销等，因此并不适合用于大规模分布式存储系统 。如果系统编码设计的目标是在不牺牲磁盘故障容忍度的前提下最大化存储效率，那么存储系统采用MDS码来储存数据，因为它可以为相同的存储开销提供更高的可靠性。也就是说MDS码是一种能提供最优储存与可靠性权衡的纠删码。在一个分布式存储方案中，原始文件首先被分成k个数据块，接着它们编码生成n个编码块并存储在n个节点 中。访问任意l(ｌ≥ｋ)个节点，通过纠删码的译码就可恢复出原始文件，如果ｌ= ｋ ，该码就满足MDS性质，最多能够容忍 (ｎ-ｋ)个节点的失效。
• 目前主流的分布式编码：
  • 再生码(Regenerating Codes，RGC)，修复带宽较小，但由于它们在修复过程中有大量的矩阵运算，计算复杂度很高，因此构造过程非常复杂。
  • 局部可修复码(Locally Repairable Codes，LRC)，同RGC。
  • MDS阵列码，如EVENODD，B-code，X-code，RDP，STAR，Zigzag，它们的编译码过程基本都是构建在低阶域的简单运算之上，复杂度低。但受限于阵列码的构造过程，它们所设计的冗余节点很少，导致其容错能力有限，修复能力一般都比较弱，修复效率较低。
  • Piggybacking编码，研究还处在起步阶段，有很多理论和实际应用还不太完善。
• RGC
  • Dimakis等人受网络编码的启发将编码数据的修复建模为信息流图，从而提出了再生码，其约束条件是维持容忍磁盘故障的能力。
  • 在信息流图中，所有的服务器可以分为源节点、存储节点和数据收集器，其中源节点表示数据对象产生的服务器。
  • 
  • 纵然RGC达到了存储与带宽开销之间的最优权衡，但因为其需要繁琐的数学参数和复杂的编码理论基础，实现过程很难。目前RGC大多在有限域$GF(2^q)$上进行多项式运算。加法在计算机上处理较为简单，然而乘法和除法却相对复杂，更有甚者需要用到离散对数和查表才能处理。这使得RGC的编译码复杂度很高，因而很难满足分布式存储系统对计算复杂度的要求。RGC作为MDS码的改进版，拥有良好的理论基础，但是现有的绝大部分RGC编译码复杂度很高且码率低，所以迫切地提出高码率且编译码复杂度低的RGC，这具有积极的现实意义。若同时结合磁盘Ｉ／Ｏ、数据存储安全和网络结构等方面构造，能进一步推广RGC的应用范围。
• LRC：与通过牺牲磁盘Ｉ／Ｏ开销来节省带宽消耗的RGC不同，LRC具有较少的磁盘访问数量。它是通过强制一个失效节点中的数据只能通过某些特定的存储节点来进行修复，从而减少需要读取和下载的数据量来降低修复带宽。
  • 假定任意３个节点都足以得到原始数据的 MDS码，即ｋ＝ ３。修复一个故障节点，MDS码和再生码需要读取６个编码段，而图６中却只需要读取２个特定的编码段，所以能降低磁盘Ｉ／Ｏ 开销。
  • 以存储为代价，目前采用的系统有：Facebook的分布式文件系统 HDFS和微软的 Azure。主要实现方法有：分层编码(Hierarchical Codes)和简单再生码(Simple Regenerating Codes,SRC)。
  • 发展现状：
    • 2016年，Kumar等人为分布式存储设计了一种可修复喷泉码（Repairable Fountain Codes，RFC），在信息安全理论上提出了针对存储节点的窃听模型，应对通过失效节点的修复来窃取其他幸存节点数据的威胁；
    • Rawat等人通过平衡LRC 的安全性和修复度，提出了安全性最佳的局部修复度结构的编码方案，可有效抵抗监听；
    • 2017年，Kadhe等人又通过内码和外码的联合设计，构造了一种广泛的安全存储码方案，同时考虑了 MSR码和 LRC这２种分布式存储编码；
  • 针对单个节点失效LRC的研究：
    • 基于二元LDPC码的构造 ：2016年，Hao等人阐述了一类有着多修复组的 LRC与二元 LDPC码的关系，提出了用正则LDPC码去构造LRC的方法。 2017年，Su等 人在上述工作基础上基于循环置换矩阵和仿射变换矩阵提出了２种二元LRC的构造方法，达到了距离限 ；
    • 基于联合信息可用性构造
    • 基于联合信息可用性构造
    • 基于平均修复度的构造
    • 基于 Matroid理论的构造
    • 基于Rank-Metric理论的构造
• Piggybacking编码: 2013年 Rashmi等人首次提出了 Piggybacking框架的概念，且将该框架下构造的 Piggybacking编码用来应对存储系统中频发的故障节点。他们解释 Piggybacking的 含 义 是 将 MDS码 作 为 基 本码，将扩展后的 MDS码中某些条带的数据符号通过精心设计好的 Piggyback函数嵌入到其他条带中形成 Piggybacking块的一种设计。失效的数据符号可以通过求解 Piggybacking方程来替代传统的MDS译码来恢复，这样能有效降低修复带宽。
  • Piggybacking框架有一个显著的特点就是在不改变原有存储节点的分布结构下减少了额外的存储开销，即不需要增加除MDS编码以外的校验节点，依旧能保持数据重建性；
  • Piggybacking编码支持任意码长为ｎ 、信息位长度为ｋ 的基本码（码参数的选择取决于基本码的需要）；
  • 目 前 已 经 应 用 于Facebook Warehouse Cluster，HDFS等系统中；
  • 
  • 目前有三种设计：
    • 第1种设计是基于较少的子条带数量，其中最少的子条带数只有２。这类设计修复信息节点时根据码参数不同可以节省25％～50％不等的修复带宽，且该设计也具备修复校验节点的能力；
    • 第2种设计是由(2r-3)列结构相同的MDS码组成，并在最后(r-1)列中增加了Piggyback方程。该设计要求校验节点数ｒ≥３，相比第１种设计拥有更高的修复效率，平均能有效减少约50％的修复带宽；
    • 第3种Piggybacking编码，该码可以有效修复最小修复度可达k+1的MDS码中的信息节点。
  • 
• 最终比较

思考

1. MDS码（Maximum Distance Separable最大距离可分）：如Reed——Solomon，RS码，Google Colossus，HDFS Raid，Microsoft Azure，Ocean Store。
2. 再生码(Regenerating Codes，RGC)，修复带宽较小，但由于它们在修复过程中有大量的矩阵运算，计算复杂度很高，因此构造过程非常复杂。
3. 局部可修复码(Locally Repairable Codes，LRC)，同RGC。
4. MDS阵列码，如EVENODD，B-code，X-code，RDP，STAR，Zigzag，它们的编译码过程基本都是构建在低阶域的简单运算之上，复杂度低。但受限于阵列码的构造过程，它们所设计的冗余节点很少，导致其容错能力有限，修复能力一般都比较弱，修复效率较低。
5. Piggybacking编码，研究还处在起步阶段，有很多理论和实际应用还不太完善。

全篇花了大篇幅在论述piggybacking的理论，构造以及应用，而且19年有一篇硕士论文专门论文了piggyback技术，说明还是一个研究热点，可以做做功夫。

1. 基于HDFS的分布式文件系统数据冗余技术研究

基本信息

• 硕士论文，西安电子科技大学

• 2011年

• 关键词：分布式文件系统；HDFS；数据冗余技术；数据可靠性

• 摘要

  随着信息技术的发展，存储系统占有举足轻重的地位。在数据爆炸性增长的今天，本地的存储很难满足不断增长的海量存储的需要，而且个人移动计算和企业级计算对底层的存储系统也提出了更高的要求，人们越来越多地使用分布式文件系统，它可以带来更高的存储能力、可靠性、安全性和移动性。

  本文主要研究了分布式文件系统的数据冗余技术。传统的分布式系统大多采用独立磁盘冗余阵列（RAID）和复制技术进行数据的冗余，要达到一定的可靠性对存储空间的要求较高。后来又出现了编码方法对数据进行编码存放，这在提高了可靠性的同时又带来了数据读取和写入时性能的较大损失。为了更好地平衡数据可靠性和读取性能，本文提出了综合采用复制和网络编码技术对数据存储的方案。在开源的 HDFS(Hadoop Distributed File System)项目基础上，给出了文件分块编解码、编码块放置策略、文件读取和写入的完整流程和方案，之后又研究了如何进行负载均衡以及怎样在大规模廉价低可靠机器组成的集群上处理机器的频繁退出和加入的问题。借助于这种数据冗余技术，可以在相同的冗余度上提高数据的可靠性，同时又尽可能地降低编码对读取性能的负面影响。

  本文首先介绍了分布式系统的研究现状，研究了主流的架构技术，在介绍了各种数据冗余技术的基础上提出了复制和网络编码结合的方案，在 HDFS 架构下描述了具体的设计。最后对可靠性进行了理论分析和实际仿真，证明了该设计可以达到预期的效果。

• 引用格式

  吴昊, 基于HDFS的分布式文件系统数据冗余技术研究, 2011, 西安电子科技大学.

摘录

• HDFS：Hadoop 是 Apache 基金会支持的一个开源的分布式计算平台项目。基于其的云计算平台的研究正成为一个科研和商业领域的热点问题。HDFS 是 GFS 的开源实现，并有大量的参考文档和实验方式。
  • 总体架构：
  • HDFS与GFS的异同：
    • 相同：
      • GFS 和 HDFS 都采用单一主控机+多台工作机的模式，由一台主控机(Master)存储系统全部元数据，并实现数据的分布、复制、备份决策，主控机还实现了元数据的 checkpoint 和操作日志记录及回放功能。工作机存储数据，并根据主控机的 指令进行数据存储、数据迁移和数据计算等。
      • .GFS 和 HDFS 都通过数据分块和复制（多副本，一般是 3）来提供更高的可靠性和更高的性能。当其中一个副本不可用时，系统都提供副本自动复制功能。针对数据读多于写的特点，读服务被分配到多个副本所在机器，提供了系统的整 体性能。
      • GFS 和 HDFS 都提供了一个树结构的文件系统，实现了类似与 Linux 下的文件复制、改名、移动、创建、删除操作以及简单的权限管理等。
    • 不同：
      • GFS 最为复杂的部分是对多客户端并发追加同一个文件，即多客户端并发Append 模型。GFS 允许文件被多次或者多个客户端同时打开以追加数据，以记录为单位。假设 GFS 追加记录的大小为 16KB ~ 16MB 之间，平均大小为 1MB，如果每次追加都访问 GFS Master 显然很低效，因此，GFS 通过 Lease 机制将每个Chunk 的写权限授权给 Chunk Server。写 Lease 的含义是 Chunk Server 对某个 Chunk在 Lease 有效期内(假设为 12s)有写权限，拥有 Lease 的 Chunk Server 称为 Primary Chunk Server，如果 Primary Chunk Server 宕机，Lease 有效期过后 Chunk 的写 Lease可以分配给其它 Chunk Server。多客户端并发追加同一个文件导致 Chunk Server需要对记录进行定序，客户端的写操作失败后可能重试，从而产生重复记录，再加上客户端 API 为异步模型，又产生了记录乱序问题。Append 模型下重复记录、乱序等问题加上 Lease 机制，尤其是同一个 Chunk 的 Lease 可能在 Chunk Server之间迁移，极大地提高了系统设计和一致性模型的复杂度。而在 HDFS 中，HDFS文件只允许一次打开并追加数据，客户端先把所有数据写入本地的临时文件中，等到数据量达到一个 Chunk 的大小（通常为 64MB），请求 HDFS Master 分配工作机及 Chunk 编号，将一个 Chunk 的数据一次性写入 HDFS 文件。由于累积 64MB数据才进行实际写 HDFS 系统，对 HDFS Master 造成的压力不大，不需要类似 GFS中的将写 Lease 授权给工作机的机制，且没有了重复记录和乱序的问题，大大地简化了系统的设计。然而，我们必须知道，HDFS 由于不支持 Append 模型带来的很多问题，构建于 HDFS 之上的 Hypertable 和 HBase 需要使用 HDFS 存放表格系统的操作日志，由于 HDFS 的客户端需要攒到 64MB 数据才一次性写入到 HDFS 中，Hypertable 和 HBase 中的表格服务节点(对应于 Bigtable 中的 Tablet Server)如果宕机，部分操作日志没有写入到 HDFS，可能会丢数据。
      • Master 单点失效的处理。 GFS 中采用主从模式备份 Master 的系统元数据，当主 Master 失效时，可以通过分布式选举备机接替主 Master 继续对外提供服务，而由于 Replication 及主备切换本身有一定的复杂性，HDFS Master 的持久化数据只写入到本机（可能写入多份存放到 Master 机器的多个磁盘中防止某个磁盘损害），出现故障时需要人工介入。
      • 对快照的支持。 GFS 通过内部采用 copy-on-write 的数据结构实现集群快照功能，而 HDFS 不提供快照功能。在大规模分布式系统中，程序有 bug 是很正常的情况，虽然大多数情况下可以修复 bug，不过很难通过补偿操作将系统数据恢复到一致的状态，往往需要底层系统提供快照功能，将系统恢复到最近的某个一致状态。
• 随机线性网络编码
  • 
  • 为了保证目标节点对收到的数据包可解，需要保证不同数据包的编码向量线性无关，使用规则化统一化的编码方式往往是不可行的。在分布式环境中，如网络中，有时会存在处于中心地位的节点，网络编码方案中中心节点的作用就是了解网络拓扑，为不同节点决定编码向量。然而在实际的实现中，这 样的要求会使中心节点存储的信息和承受的负载严重偏大，同时网络的拓扑结构在不断发生动态的变化，中心节点难以及时掌控这些变化。因而，实际的网络编码倾向于非集中式的编码。
  • 
  • Galois域：是指一个包含 n 个元素的集合，任意两个元素的加法和乘法后得到元素都在这个集合里，即对加法和乘法是封闭的，并且除零元素外每个元素在这个集合内都有加法逆元素和乘法逆元素，这里 n 是素数也可以是素数的幂，除此之外的 n 无法构成 Galois 域。
  • 以$GF(2^4)$为例进行说明，$(1011)_2$和$(0110)_2$相乘，设既约多项式为$x^4+x+1$，$(1011)_2$对应的多项式是$x^3+x+1$，$(0110)_2$对应的多项式$(x^2+x)$，两者相乘，$\left(x^{3}+x+1\right)\left(x^{2}+x\right) \bmod \left(x^{4}+x+1\right)=x^{3}+x^{2}+x+1$，结果为$(1111)_2$。在算法实现较小的域如$GF(2^4)、GF(2^8)、GF(2^{16})$的运算时，可以预先计算出Galois域上的指数和对数表来并存在内存中，计算两个数的加减法时，仍为两个数的异或，计算乘法时等价于通过查表计算两个数的对数和之后再取其和的指数表中的值，同理，计算除法时等价于通过查表计算两个数的对数差之后再取其和的指数表中的值。
• 总体架构设计：
  • 
  • 编码放置策略
  • 中心节点元数据设计
    • 内存中的数据结构
    • Block位置信息
    • 操作日志
• 仿真：
  • 环境
  • 结果

思考

• 主要介绍了HDFS的特点以及与GFS的异同；
• 基于HDFS系统，用随机线性网络编码实现了冗余技术；
• 设计了编码以及相应的放置策略，同时设计了中心节点的元数据包括，数据结构，Blokc位置和操作日志；
• 最后考虑了负载均衡以及在Fedora 13 上用Eclipse进行了仿真。

1.P2P分布式存储系统中冗余策略研究

基本信息

• 期刊论文，《现代计算机》，

• 2009年

• 关键词：P2P 模型；复制；冗余 ；纠删码；数据可用性

• 摘要

  由于 P2P 系统具有高动态性，为了提高存储的可靠性，必须采用冗余策略，使数据文件以副本的形式分布在系统的多个节点中。 阐述 P2P 分布式存储系统中使用的冗余策略，并分析它们对文件可用性的影响以及在真实 P2P 系统中的应用。

• 引用格式

  董辉与雷大军, P2P分布式存储系统中冗余策略研究. 现代计算机(专业版), 2009(09): 第8-10页.

摘录

• 系统的冗余策略主要有复制 （Replication）和纠删码 （Erasure Coding） ， 两种方式，而复制策略主要又可分为全文件复制和分块复制两类。

• 数据可用性定义：数据在时间 t 能被访问到的概率。

• 系统节点总数为 n，从中任意取 h 个节点，其中可用的节点个数为 y 的概率会满足二项式分布概率公式：
  $$ P(y)=\left(\begin{array}{l} h \ y \end{array}\right) \mu^{y}(1-\mu)^{(h-y)} $$

• 在全文件复制中，假如文件有 c 个副本分布在不同的节点上，c 个副本中至少应该有一个副本有效才能用于恢复数据。 因此，全文件复制的可用性定义为 ：

• 分块复制 将文件分割成小块，文件存储负担可由系统中的节点均匀地承担，而且有利于并行下载和负载平衡。 如果将文件划分成 b 块，并对每块生成 c 个副本，文件可用性可定义为：
  $$ P(y \geqslant 1)=\left(1-(1-\mu)^{c}\right)^{b} $$

• 纠删码：

• 三种方式的比较：

• P2P系统：

  • Total Recall ，是圣地亚哥加州州立大学 （UCSD）设计的 P2P 存储系统，设计目标是自动配置系统所需要的各种参数，以避免繁琐且困难的人工设置。系统会根据可用性的需求，基于文件大小、等级以及文件读写请求的访问模式等来自动选择最有效的复制方案和冗余度。小文件采用复制策略和积极修复法，对 大文件采用纠删码和懒惰修复法 。
  • OceanStore ，来自Berkeley， 使用了复制和纠删码两种复制策略，一方面使用纠删码存储归档的数据以减小空间和带宽消耗，另一方面使用复制来提高数据访问的效率。
  • CFS ，是一种只读存储系统，CFS 系统认为存储空间不是稀缺资源，因此不采用纠删码，而只采用复制方式冗余：将数据实施分块复制，然后用 DHT 直接分发的方式将副本按顺序放置在数据 ID 对应的负责节点及后继节点上，当底层覆盖网络检测到有一个副本丢失时，数据的主节点负责立即再修复出一个副本。

思考

水文，首先分析了冗余的定义和数据可用性的定义，然后分别阐述了全文复制，分块复制以及纠删码的冗余因子及其性能，最后罗列了现有的p2p分布式存储系统采用的冗余策略。可以，当科普看看。

2.基于私有云的数据冗余技术研究

基本信息

• 期刊论文，《电脑知识与技术》

• 2011年

• 关键词：云存储；数据冗余；纠删码

• 摘要

  作为云计算技术的一个分支，云存储的应用逐渐兴起。 文章介绍了私有云存储的概念和特点，在此基础上结合私有云存储的环境，对几种数据冗余方式进行了分析比较。

• 引用格式

  周游等, 基于私有云的数据冗余技术研究. 电脑知识与技术, 2011. 7(01): 第16-19页.

摘录

• 纠删码：具备识别错码和纠正错码的功能，当错码超过纠正范围时可把无法纠错的信息删除。 纠删码将一份数据分解成 m 块，通过编码将其转化成 n 块，只需要 t（t≥m）块数据存在，便可以恢复出原始数据。
• 纠删码冗余种类：
  • RS（Reed-solomon）编码：由 Reed 和 Solomon 在 1960 年提出，它是一种前向纠错算法，能够从收到的 t 个数据块中恢复原有的数据，主要用于数据通信和存储中。 RS 编码具有可靠性高、任意冗余度、空间最优等特点，并且实现简单。 编解码性能较低是 RS 编码的缺点，由于所有运算都是在伽罗华域中展开，在进行乘除运算时需要进行两次伽罗华域转换，使 得计算复杂，而不适合对实存储系时性能要求高的统使用。
    • 基于范德蒙德矩阵的 RS 编码(VRS)
    • 基于柯西矩阵的 RS 编码(CRS) ，CRS 在 VRS 基础上有两个改进，一是使用柯西矩阵代替范德蒙德矩阵，二是把 GF 域上的运算全部转换为异或运算。柯西编码极大地提高了 RS 编码的 性能。
  • LDPC编码（Low-Density Parity-Check）是一种线性分组编码，其校验矩阵0多1少，呈现稀疏矩阵特征，因此称为低密度校验码。
  • Tornado编码，是一种速度非常快的LDPC编码，基于稀疏矩阵，对数据对象及与其详尽的数据对象进行异或操作生成校验码，并且通过不规则级联二分图对校验码进行编码，使得可靠性得到保证。由于Tornado校验矩阵的稀疏性，其编解码性能呈线性增长，具有比RS编解码更优良的性能，但由于Digital Fountain对算法版权的保护，有关资料较少。且被证明必须获得$k(1+\varepsilon )$个节点才能完成解码，相比较，RS只需要$k$个。
• RAID冗余：RAID（Redundant Array of Independent Disks）早期使用最简单的奇偶校验码保证数据的可靠性，从RAID0-RAID6，RAID5在N+1的情况下，允许出现1块磁盘损坏，而RAID6中则允许出现2块磁盘损坏。

思考

• 了解到纠删码的种类以及除了纠删码冗余之外还有RAID冗余；
• 总的来说，完全副本实现简单，在高动态的系统，节点平均可用性低的系统中还是适合纠删码，其中基于柯西矩阵的 RS 编码(CRS)又更好，反之，纠删码只会增加系统设计的复杂性；
• RAID有广泛运用的历史，但不能满足新的存储需求。

1.基于P2P的分布式存储的研究与实现

基本信息

• 硕士论文

• 2004年

• 关键词：P2P 模型；资源查找；冗余

• 摘要

  “基于 P2P 的分布式存储系统”是四川省科技厅“青年软件创新工程”资助项目。

  本系统在 P2P 的基础上采用了 Server-to-Server 的模型，各个 Server 之间完全对等，通过路由关系连接起来。客户从任何一个 Server 上都可以查询并访问系统中的所有文件，同时每一个 Server 上的文件及其存储信息都被冗余备份到其他Server 上，提供了较高的容错性。此外，本系统的文件存储信息采用 XML 方式存放，有利于 WEB 方式发布和查询信息。

  在基础理论中，首先介绍了 I/O 模型，并对几种网络服务器内部架构进行了分析和比较，最后介绍了 XML 语言的基本概念和相关语法。随后，我们讨论了P2P 的各种资源查找算法，并详细描述了本系统使用的基于关键字的路由模型的主要算法和设计。在对网络分布存储及其技术研究的基础上，我们设计了一个基于 P2P 模型的分布式存储系统。本系统采用分层结构，以路由层作为基础，在其上实现了对象传输层和命令解释层。在命令解释层实现了一个基于线程池的任务驱动的服务器框架模型，它监听 UDP 端口，并维护一个全局任务队列，所有收到的命令都作为一个任务放到任务队列中由处理线程进行命令分发，调用对象传输层处理；在对象传输层实现了资源查找算法，设计并实现了一套基于 UDP 的传输协议用于客户与服务器之间，以及服务器内部之间的命令交互，同时还设计了以 XML 方式存放的文件存储指针格式；最后，实现了一个定时模块，使得各种网络延时较大的任务可以通过定时队列得到异步响应，从而释放相应的处理线程，并且对于延时太久的任务可以实现超时重发。

  通过对本系统的初步测试，表明该系统实现了设计目标并具有较好的性能。

• 引用格式

  陈刚, 基于P2P的分布式存储的研究与实现, 2004, 电子科技大学.

摘录

• Server-to-Server模型，各个Server之间完全对等，通过路由关系连接起来，同时每一个 Server 上的文件及其存储信息都被冗余备份到其他Server 上。
• 在本系统中冗余备份主要包括：实际文件的冗余和文件存储指针的冗余。
• 实际文件的冗余包括分片冗余和拷贝冗余。这部分工作是上传服务器在文件上传成功后，调用冗余备份模块，进行冗余存储，并将冗余信息记录在文件存储指针中，这些对于用户来说都是透明的。
• 如果是分片存储，在下载时需要客户端的支持。文件存储指针的冗余则分为三个层次。
  • 第一个层次是在通过文件名哈希算法计算出文件 $ID$ 值时，对这个 $ID$ 值加上两个偏移量，从而得到另外两个 $ID$，这样文件存储指针按照三个 $ID$ 值分别存放在三个不同的服务器上，从而实现冗余。偏移量的选取跟 $ID$值的取值空间有关，假设取值空间中最大值为$ID_{max}$，则两个偏移量为$\dfrac{1}{3}ID_{max}$，$\dfrac{2}{3}ID_{max}$，由于本系统的路由算法跟距离相关，$ID$ 值相差越大，节点的实际距离也越大，因此这样取值的偏移量可以使的三个拷贝尽量存放在相隔较远的节点。
  • 第二个层次的冗余是当文件存储指针存放到某个节点服务器后，它会再备份到跟它 $ID$ 值最相近的两个节点上，一个是 $ID$ 值比它大，一个 $ID$ 值比它小，因为如果这个节点出现故障时，那么原来那些把它作为相关节点的文件，当再次进行路由定位时将会定位到跟它 $ID$ 值最接近的两个节点上，而这两个节点就接替它成为那些文件的相关节点。
  • 第三个层次是通过高速缓存来冗余备份，具体来说就是，每个节点都建立自己的高速缓存，在一个文件存储指针从初始节点到目的节点的路由过程中，所经过的所有节点都把该存储指针在自己的高速缓存中留一份拷贝。这样当某个节点查询一个文件时，查询报文在路由过程中将会在每个路由节点的高速缓存中查找，如果发现有匹配项，就可以立刻返回，最坏的情况是直到相关节点才找到。当然，如果查找高速缓存没有命中的话反而会延缓查找过程，为了防止这种情况出现，我们采用旁路技术，即在每个路由节点查找高速缓存的时候，不管是否命中缓存，都直接把查询报文向下一个节点转发。这样就不会因为没有命中缓存而延缓查询过程，但是如果有多个节点命中缓存的话，就会产生多份冗余报文发送给请求服务器。不过对于路由节点不多的情况下，是可以忍受的。
  • 如图 3-2所示，当文件 Myfile 存储到 A 节点后，根据资源定位算法，它的文件存储指针被存放到 F 节点上。当我们在 B 节点访问 Myfile 时，如果没有高速缓存，则需要从 B 路由到 F，才能从 F 节点上获得 Myfile 的文件存储指针，然后 B 再跟 A连接，访问到 Myfile；而引入高速缓存后，在从 A 路由到 F 节点的过程中， C、D 节点上的高速缓存中就保存了 Myfile 的文件存储指针拷贝，此时 B 在路由到C 时就在 C 的高速缓存中发现了 Myfile 的存储指针，从而立刻返回到 B，然后 B就可以直接从 A 中访问到 Myfile 了。
  • 
• 在系统设计的时候我们的目标是在存放文件存储指针的服务器故障的时候，通过冗余备份信息获得文件存储指针。

思考

2.Peer-to-Peer存储系统中一种高效的数据维护方案

基本信息

• 软件学报

• 2009年

• 关键词：对等网络存储;数据维护;永久失效;暂时失效;失效检测;带宽优化

• 摘要

  提出一套完整的数据维护方案.该方案建立在 P2P 环境动态性特点的基础上.一方面,该方案考虑了节点动态性差异,它基于不同的动态性作相应的数据冗余,能够用更少的冗余开销来保证数据的目标可用性;

  另一方面,该方案给出如何利用判别器来区分永久失效和暂时失效,以减少由于不必要的数据修复而带来的额外修复开销.通过在真实 P2P 系统 Maze 上的实验结果表明,该方案比目前主流的方案能够节省大约 80%的数据维护带宽。

• 引用格式

  杨智, 朱君与代亚非, Peer-to-Peer存储系统中一种高效的数据维护方案. 软件学报, 2009. 20(01): 第80-95页.

摘录

• 本文基于 P2P 系统节点的动态性规律,研究存储节点的选择方案,以降低系统屏蔽暂时失效所需的数据冗余度,同时;本文将研究如何使用永久失效判别器来检测系统中节点的永久失效,以降低由于系统无法区分暂时失效和永久失效所带来的额外开销.本文的主要贡献如下:

  • 本文考虑了节点的动态性差异,提出一种基于节点动态性的数据分发算法,它把数据放在动态性相近的节点上,并精确计算出相应的冗余度.相对于传统的随机分发算法,能够在 P2P 这种高动态环境下用更少的冗余开销达到数据的目标可用性.
  • 如何在时间阈值判别器中设置时间阈值来区分永久和暂时失效是当前 P2P 存储系统研究中的一个难题,本文基于漏判抵消误判的思想,给出了永久失效判别器中参数设置的统一原则,使得时间阈值判别器的性能接近于最优的理想判别器.
  • 为了提高判别器精度,本文提出了一种新的永久失效判别器:基于节点离开概率的判别器.它在不同的离线长度下给出相应的永久失效概率,而不是只用一个阈值来确定性地判别永久失效,因此,本文提出的判别器比时间阈值判别器更为精确.

• 冗余方式主要包含两类:副本和纠删码(erasure code).

  • 参数是$(m,n)$的纠删码将原始文件分成$ m$ 个碎片,然后编码成$ n(n>m)$ 个碎片,并保证其中任意 $m$个碎片都可以重构文件.最早人们用量化的方法分析了纠删码和副本方式冗余对系统可靠性的影响,但考虑的是较为稳定的环境.之后,研究者重新考察了纠删码对 P2P 存储 系统可用性的影响,更关注高动态性的系统,指出对于节点可用性比较低的系统,用副本的方式较好,但并没有考虑修复带宽开销[14].关注在 P2P 系统中两种冗余方式下的修复开销,指出副本方式在高动态系统中更为有效.更为复杂的方式是采用副本和纠删码结合的方式,文献[15]的研究表明,这种方式能够更好地优化修复带宽 .

• 数据放置策略决定一个数据对象的副本存放在哪些节点上.数据放置策略可以分为两类:随机放置策略和选择放置策略

• 目前,主流的数据冗余策略是随机分发数据,然后利用节点在线概率的平均值计算出数据的目标冗余度. 但这种方法却忽略了节点间动态性的差异.

  • 冗余度定义为冗余后的数据量与原始数据量的比值.对于副本方式,冗余度就等于数据副本的个数.对于参数是(m,n)的纠删码,冗余度为 n/m.
  • 目标冗余度是指能够达到数据目标可用性的最小冗余度

• 本文提出一种基于节点动态性的数据分发算法,它采用与主流方法相同的可用性计算模型,但根据不同的节点动态性产生不同的冗余度,更好地适用于节点动态性差异较大的 P2P 系统.

• 时间阈值判别器，本文将回答如何自动、合理地设置时间阈值τ的难题.另外,还提出一种新的永久错误判别器:基于概率的判别器.基于真实 P2P 系统运行日志的模拟实验表明,这两种判别器的性能都接近最优的理想判断器(没有误判和漏判的判断器).

• 系统的开销模型 ：冗余和修复会耗费系统的资源,从而产生冗余数据或修复数据,这种开销称为系统维护开销。作出如下假设

  • 假设节点间是相互独立的；
  • 节点加入和永久离开系统的平均速率是恒定的；
  • 系统中节点的数量是稳定的。

• 系统的开销模型具体细节

• 数据的冗余优化：目前,主流的数据冗余算法是在整个系统里随机选择节点分发数据,然后利用节点在线概率的平均值计算出数据的目标冗余度 ，本节提出的优化算法仍能保证系统中节点的负载平衡(即分发后每个节点上存储相等的数据量),而不是通过不断将负载移向高可用节点来减少冗余度。

  • 节点动态性差异对$k_L$的影响：提出一种新的衡量目标冗余度的算法，相对主流算法在理论上能够节省 30%左右的带宽
    $$ I=1-\frac{\tilde{k}{L}}{k{L}}=1-\frac{\int_{0}^{1} h f(h) \mathrm{d} h}{\int_{0}^{1}-\log (1-h) f(h) \mathrm{d} h} $$

  • 基于节点动态性的概率放置算法：

• 数据修复优化

  • 基于判别器的数据修复算法

    • Timeout($\tau$) ,时间阈值判别器，属于确定型永久判别器 $$ f(\text {node,t})=\left{\begin{array}{ll} A, & \text { if } d(t)=0 \ U, & \text { if } 0<d(t)<\tau \ D, & \text { if } d(t) \geq \tau \end{array}\right. $$

    • Probability($f(\xi)$)，概率判别器，$f(\xi)$)是一个以节点离线时间$\xi$为 自 变 量 的 概 率 函 数
      $$ f(\text {node,t})=\left{\begin{array}{ll} Z=A, & \text { if } d(t)=0 \ P(Z=U)=1-f(d(t)), & \text { if } d(t)>0 \ P(Z=D)=f(d(t)), & \text { if } d(t)>0 \end{array}\right. $$

    • 

  • 误判和漏判对$k_R$的影响

  • 两类永久判别器中参数的设置

• 
• 
• 

思考

• 算法构件：
  • 冗余算法
    • 纠删码Erasure code
    • 副本冗余方式
    • 数据的随机分发方式
  • 修复算法
    • 积极修复
    • 懒惰修复
• 服务构件：
  • 数据目录服务：Total Recall 中,每个对象都由一个节点来负责,称为 Master.Master 知道它所负责的对象的每个副本存放在哪个节点上,维护了副本与系统中节点的映射关系.当用户(对应图中的 client)读取数据时,首先联系 Master,获取副本的位置,然后再联系存储副本的节点(对应图中的 Data storage hosts)下载 。
  • 节点监控目录：系统中存储每个存储副本的节点向其对应的存储索引的 Master 节点定期发送心跳信息,汇报自己的在线状态.因此,Master 也维护了节点的在线状态,它同时是目录服务和监控服务的提供者.当用户读取数据时,Master 可以用这两种信息告诉用户一个 当前可用的副本的位置.
  • 
• 系统的运行过程如下:数据对象最初存入系统时,冗余算法被调用.冗余算法根据数据的目标可用性并通过监控服务统计出的节点动态性为对象产生一个配置,包括冗余方式、冗余度和放置策略.当数据存入系统后,系统通过目录服务建立副本和节点的对应关系.对于每个数据对象,系统定期地通过目录服务和监控服务查看存放其副本的节点失效情况,以评估对象的冗余度.如果冗余度低于能够保证目标可用性的最低冗余度,则系统触发修复并调用修复算法产生新的副本。