HDFS——数据备份与放置策略(转)
对于分布式文件系统来说，为了保证数据的高可用性和系统容错能力，往往会把同一数据块在多个节点上进行备份，那么如何分配这些复制数据的位置，不同的文件系统会有不同的策略。
一、业界分析
在介绍HDFS之前，先简单了解一些其它文件系统的放置策略：
1. Lustre——一致性哈希环
对于不同的数据备份，需要放到不同的节点上面，一种直观的想法就是利用Hash函数，这样可以把每个备份id对应到一个哈希值，然后再将这个哈希值与某个节点对应起来，就完成了一个数据备份的分配。这样做在时间复杂度上只有O(1)，所以是极好的。但是很多哈希函数有一个问题，就是不稳定。这里所谓的不稳定是指，当节点个数发生变化的时候，原来被分配到节点K上的数据备份可能就会被分配到另一个节点上。举个例子，常用的哈希函数为：hash(x) = x % N，其中N为节点个数，x为备份id，这样当集群中节点出现故障或者扩展新的节点时，原来的计算的哈希值几乎全都变了，那么对于整个系统中的数据访问来说，无疑是一个灾难，因为访问位置全都得改变，并且需要重新迁移数据。
那么有没有可能在N变化的侯，原有数据备份的哈希值不改变呢？这就是一致性哈希的优势所在。
一致性哈希的原理可以这么理解：原来哈希是用x%N，现在是用x%S且N%S，这里的S表示哈希函数本身可以表示的哈希值范围，比如它的范围是0～2^32 - 1，那么S=2^32。见下图：
如果按照图1这种分配方式，一旦出现Data Nodes个数变化的情况，原来的分配位置几乎都得改变（例如使用取模的哈希函数）；
图2展示的方式，如果选取的哈希函数取值范围在0到2^32 - 1之间（Hash Range），那么我们可以同时把Data Blocks和Data Nodes同时哈希到这个范围里面，这些Nodes会把Hash Range划分为若干区域，规定每个Node存储与其相邻的前一个区域中的Blocks，从而完成数据的分配。这种方式的好处在于，即使出现Data Nodes数量变化的情况，也不会影响其它Nodes和Blocls的位置情况，最多是在被删除节点或者新增节点的附近进行调整，比如将原有区域中的Blocks进一步划分或者合并。
细心的读者可能会发现，图2展示的方式中，三个Nodes将Hash Range分为了4个区域，显然不方便分配，所以提出一致性哈希环的概念，即将Hash Range的首位相连，然后在一个环路上面进行划分，N个Nodes一定能够划分出N个区域，然后让每个Node存储前一个相邻区域即可。
2. Ceph——CRUSH
一致性哈希环很好地解决了数据分配与集群扩展的问题，但是它还有一个性能的瓶颈，那就是需要一个中心节点负责存储整个集群的元数据信息，对新增的数据进行分配，在用户查询时提供数据分布的位置。这些工作处理的性能直接影响整个系统的处理速度，而且可能还会带来SPoF。一种可行的办法是对这些中心节点进行备份，或者干脆用一个分布式Hash表代替一个中心节点，虽然能够避免SPoF，但是随之而来的又是信息同步和一致性维护等问题。
在上一篇文章中我们简单了解了Ceph，它是一种基于对象存储的分布式文件系统，最大的特点就是由可以自我管理的OSD构成，这些OSD不需要依赖某个中心节点的管理，它们可以自己完成数据的分配、复制、容错、故障恢复等功能，可以理解为一种P2P的结构，而CRUSH算法就是使它具有以上特性的关键环节。
上图简单说明了Ceph数据放置的过程，对于需要存储的对象，首先哈希到Place Group，然后再通过CRUSH算法找到需要存放数据的具体OSD。CRUSH在执行过程中还是需要一些全局信息的，这些信息在被称作分层集群映射（Hierarchical Cluster Map），这些信息主要是用来描述集群的组成和搭建，它们存放在一些monitors的节点上面。对于每个Storage Client和OSD而言，它们可以利用Hierarchical Cluster Map、放置规则等信息计算数据的位置。相比与原来中心节点的策略，CRUSH的计算负担分发给了每个OSD。
关于CRUSH的详细介绍，可以参考论文：CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data
二、HDFS放置策略
对于HDFS而言，由Namenode负责这个集群的数据备份和分配，在分配过程中，主要考虑下面两个因素：
- 数据安全：在某个节点发生故障时，不会丢失数据备份；
- 网络传输开销：在备份数据同步过程中，尽量减少网络传输中的带宽开销；
这两个因素看起来是有些相互矛盾的：想要保证数据安全，那么就尽量把数据备份到多台节点上，但是就需要向多个节点传输数据；想要减少网络传输开销，那么就尽可能把数据备份到一个节点内部或者一个机架内部，因为系统内部的数据传输速度会远大于网络传输的速度。
上图展示了HDFS中Namenode和Datanode的角色，Namenode中存储了所有数据备份的位置信息。
上图展示了HDFS中的rack（机架）概念，一个rack内部数据传输速度远大于rack之间的传输。对于每个数据备份，比如A要放在Rack1中，在写入HDFS时首先会在Rack1中创建一个备份，同时在另一个Rack2中也创建一个备份。这样做在一定程度上兼顾了数据安全和网络传输的开销。
转自 http://blog.csdn.net/yangning5850/article/details/9256737