再生码（RC Regenerating Code）是07 年Infocomm 会议中Network Coding for Distributed Storage Systems 提到的一种分布式存储编码方式，相比RS 编码具有更小的恢复带宽，参考这里的分布式存储数据恢复问题。这笔记也是为了记录这篇文章。
再生码 Regenerating Code
1
标签归档：分布式
Dynamo: Amazon’s highly available key-value store
原文 中文翻译 参考：Kai – An Open Source Implementation of Amazon’s Dynamo
本文一直为分布式key-value 存储系统以及分布式存储的业内人士所推崇，个人觉得有两个原因：
- 分布式key-value 存储近年发展迅速。Dynamo 更是集成了近些年最新的技术如：DHT（分布式哈希表）、consistent hashing（一致性哈希）、多版本、副本策略和Merkle tree 等。
- 文章从设计、实施者的角度分析了分布式key-value 存储在实践中的问题和解决方法，并总结了Dynamo 在实现、配置等方面的经验与教训，对后来者非常有借鉴意义。
拜占庭将军问题
参考 The Byzantine Generals Problems 。
这个问题的最初描述是：n 个将军被分隔在不同的地方，忠诚的将军希望通过某种协议达成某个命令的一致（比如一起进攻或者一起后退）。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport 证明了在将军总数大于3m ，背叛者为m 或者更少时，忠诚的将军可以达成命令上的一致。
为了保证上面的需求，必须满足下面两个条件：
1. 每两个忠诚的将军必须收到相同的值 v(i)（v(i)是第i 个将军的命令）
2. 如果第i 个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同
为了简化以上模型，我们使用一个将军发送命令给多个副官的形式来证明，发送命令的将军称为发令者，接收命令的将军为副官，那么上面的两个条件可以表述为：
IC1. 所有忠诚的副官遵守相同的命令
IC2. 如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守相同的命令
特别提示：发送命令的每次只有一个将军，将其命令发送给n-1 个副官。m 代表叛国者的个数，因为将军总数为n，所以副官总数为n-1 个。IC2 中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。
一、通过口头消息
通过口头消息传递达到一致，如果有m 个叛国将军，则将军们的总数必须为3m+1 个以上。下面是口头消息传递过程中默认的一些条件：
A1. 每个被发送的消息都能够被正确的投递
A2. 信息接收者知道是谁发送的消息
A3. 能够知道缺少的消息
A1 和A2 假设了两个将军之间通信没有干扰，既不会有背叛者阻碍消息的发送（截断）也不会有背叛者伪造消息的情况（伪造）。即是每个将军都可以无误地将自己的消息发送给其他每个将军。（下一节中可以不需要这个必要条件）
我们定义口头消息算法OM(m) 。对于所有的非负整数m ，每个发令者通过OM(M) 算法发送命令给n-1 个副官。下面将说明OM(m) 算法在最多有m 个背叛者且总将军数为3m+1 或者更多的情况下可以解决拜占庭将军问题。（考虑到网络应用实际环境，原文使用了收到值代替收到命令，本文不做修改）
算法定义一个函数：
等于多数派命令。
OM(0)算法
（1）发令者将他的命令发送给每个副官。
（2）每个副官采用他从发令者发来的命令，或者默认使用撤退命令，如果没有收到任何命令。
OM(m)算法
（1）发令者将他的命令发送给每个副官。
（2）对于每个i ，vi 是每个副官i 从发令者收到的命令，如果没有收到命令则为撤退命令。副官i 在OM(m-1) 中作为发令者将vi 发送给另外n-2 个副官。
（3）对于每个i，并且
，vj 是副官i 从第（2）步中的副官j 发送过来的命令（使用OM(m-1) 算法），如果没有收到第（2）步中的副官j 的命令则默认为撤退命令。最后副官i 使用
得到命令。
关于 hadoop （hdfs）
一、首先是一些网上资料
- hadoop源码分析 [ 蔡斌博客 ] [ doc文档 ]——这两个文档也是对hadoop的蔡斌博客内容进行的总结《综合文档一》《综合文档二》
- hadoop 的 wiki（资料非常全面，源码分析结合来看）
- hadoop 资料总结（简介，与KFS 比较，配置，改进等）
- 从 hdfs 看分布式文件系统设计需求
- hadoop 快速入门
- hadoop 集群搭建
- 在ubuntu 上安装 hadoop （实战hadoop）
- hadoop 源码分析（namenode部分）
- hadoop 原理与代码分析
OceanStore:An Architecture for Global-Scale Persistent Storage
OceanStore 声称是一个全球规模的存储网络。因为这个网络基于不可信服务器，数据进行冗余和加密处理，为提供高可用性与性能，数据可能在任何地方、任何时间被缓存，OceanStore 能够忍受区域性中断服务和 DOS 服务攻击。在 CMU 已经有了原型，可参见上面 OceanStore 项目地址。
