在分布式存储解决方案中，当客户需要访问某块数据时（通过对象的id或者文件的路径及偏移量），首先要做的就是定位数据保存在哪一台服务器上。有两种做法，一种是单独指定一台或几台服务器来管理数据的位置映射，另一种是通过某种精巧设计的算法使用对象的id或者文件的路径及偏移量直接计算出位置。
第一种方法虽然容易想到并且实现简单，比如hdfs的namenode，swift的proxy node，但是缺点也很明显，一个是单点故障问题，必须使用HA或者loadbalancer来保证足够的安全以及分流请求。
现实中数据的存储要保证安全性，所以一定要有备份，非常重要的一般是三份，普通数据也可以配置成两份，为了节省空间并不失安全性，还可以采用EC(Erasure Coding)，但是EC的计算量大一些，如果存储节点的CPU有空闲，可以考虑一下。另外出于安全性考虑，备份一般有个规则，同一份数据的不同备份往往存在不同机架上，使用了EC之后，为了安全性，EC的数据最好要分布到不同机架上。
另外分布式存储非常看重的是横向扩展性，也就是节点的自动增减。这又有两种做法，一是原有数据不懂，只把新的数据存储到放到新增节点上；另一种方法是对原有数据重新分布，这就必然要修改数据到物理存储的映射关系。现在的存储方案为了考虑磁盘使用的平均化，往往对原有数据做重新分布，如果实现的不够好，很可能导致存储节点间数据流量过大，对外访问的一致性和性能变差，甚至系统变得不可用。
Swift的一致性Hash算法
Swift提供的是对象接口，对象数据定位的算法是这样的：
1. 对所有对象的名字做hash，hash之后的数值取0-2^n，将hash空间首尾相连形成一个环
2. 每个存储device也被分配不同的hash值，并且均匀分布在hash环上。（后来为了减少增减设备引起的数据迁移造成的不平衡，每个device被分配多个虚拟的hash值，不同device的虚拟hash值交错分布）
3. 当有对象写入时，计算这个对象的hash值，从hash环上对应位置开始向前寻找，找到的第一个device即为该对象的存储位置。
4. 当有device增减时，原有的device的hash值保持不变，但邻近的device需要进行数据迁移，以保证数据的可访问性。
在实现上，两个device的hash之间被称为一个Partition，因为hash算法固定，因此一个对象在生命周期中只有一个partition id, 然后通过一个二维数组(_replica2part2dev_id)来找到devs.如partition 9527对应的dev分别是：_replica2part2dev_id[0][9527]，_replica2part2dev_id[1][9527]，_replica2part2dev_id[2][9527]
由此可见，swift中数据定位的关键是从hash环到device的映射，发生设备变化的时候该映射也发生变化。由于swift采用了proxy节点来管理数据，proxy节点之间必须同步该映射关系。
Ceph的Crush算法
Ceph中提供多种存储接口，但是底层还是使用对象方式存储的。
Ceph中在对象和设备之间有两个概念，Pool和Placement Group(PG)，每个对象要先计算对应的Pool，然后计算对应的PG，通过PG可得到该对象对应的多个副本的位置，三个副本中第一个是Primary，其余被称为replcia。
假设一个对象foo，其所在的pool是bar，计算device的方式如下：
1. 计算foo的hash值得到0x3F4AE323
2. 计算bar的pool id得到3
3. pool bar中的PG数量为256，0x3F4AE323 mod 256 = 23，所以PG的id为3.23
4. 通过PG的映射表查到该PG对应的OSD为[24, 3, 12]，其中24为primary，3,12为replica
其中第四步是CRUSH算法的核心，CRUSH
算法通过每个设备的权重来计算数据对象的分布。对象分布是由cluster map和data distribution
policy决定的。cluster
map描述了可用存储资源和层级结构(比如有多少个机架，每个机架上有多少个服务器，每个服务器上有多少个磁盘)。data distribution
policy由placement
rules组成。rule决定了每个数据对象有多少个副本，这些副本存储的限制条件(比如3个副本放在不同的机架中)。
CRUSH根据cluster, rule和pgid算出x到一组OSD集合(OSD是对象存储设备)：
(osd0, osd1, osd2 … osdn) = CRUSH(cluster, rule, pgid)
CRUSH利用多参数HASH函数，HASH函数中的参数包括x，使得从x到OSD集合是确定性的和独立的。CRUSH只使用了cluster map、placement rules、x。CRUSH是伪随机算法，相似输入的结果之间没有相关性。
CRUSH和swift的一致性hash不同点就在于，swift的hash环是设备线性分布的，CRUSH是采用层级结构，用户可以定义细致的策略，因此ceph的配置文件也比较复杂。
# begin crush map
# devices
device 10 device10
device 11 osd.11
device 12 osd.12
device 13 osd.13
device 21 osd.21
device 22 osd.22
device 23 osd.23
}
# buckets
host ceph1 {
id -2
item osd.11 weight 1.000
item osd.12 weight 1.000
item osd.13 weight 1.000
}
host ceph2 {
id -4
item osd.21 weight 1.000
item osd.22 weight 1.000
item osd.23 weight 1.000
}
rack unknownrack
{
id -3 alg straw
hash 0 # rjenkins, hash
algorithm
item ceph1 weight 3.000
item ceph2 weight 3.000
}
Pool
(root) default {
id -1
item unknownrack weight 24.000
}
# rules
rule data {
ruleset 0
type replicated
min_size 1
max_size 10
step take default
step chooseleaf firstn 0 type host
step emit
}
#
end crush map
GlusterFS的弹性Hash算法
GlusterFS对外提供的是普通文件系统接口，因此访问时客户端提供的只有文件的路径名。
GlusterFS采用的是去中心化的存储方式，文件定位在客户端即可完成。
GlusterFS在服务前端创建和客户端相同的目录结构，也就是说，任何客户端创建的文件夹，在每一个存储节点上都会对应一个真实文件夹，但是具体一个文件存在哪个节点上是需要计算得到的。存储节点上文件定位方式如下：
1. 所有的文件会被hash到一个32位的整数空间
2. 对于每个文件夹，存储节点上该文件夹的扩展属性里会标明该文件夹的hash range，落到该range的文件会存储到该节点上
3. 客户端在连接服务器端时，会要求获取某个文件夹在所有存储节点上的hash range
4. 访问文件时，客户端会计算该文件的hash值，然后访问对应的节点
5. 新增节点时，不改变已存在的文件夹的扩展属性，因此在已存在的文件夹下创建新文件时，该文件仍会放到老节点上
6. 为了平衡磁盘利用率，可以通过在老节点上创建远程链接，在新节点上创建真正的文件。（这样会造成数据在节点间大量传输）
7. 可以通过人工rebalance来重新映射文件和存储节点的对应关系。
相比较而言，glusterfs的文件定位比较简单，但是在节点扩展的时候操作就更麻烦些。具体选择起来，还要根据业务的特征来决定哪一种更合适。
阅读(735) | 评论(0) | 转发(0) |
