Chinaunix首页 | 论坛 | 博客
  • 博客访问: 509889
  • 博文数量: 35
  • 博客积分: 3472
  • 博客等级: 中校
  • 技术积分: 935
  • 用 户 组: 普通用户
  • 注册时间: 2007-08-04 06:54
文章分类
文章存档

2014年(4)

2013年(2)

2011年(3)

2010年(9)

2009年(9)

2008年(8)

分类: 服务器与存储

2013-12-21 10:38:42


在分布式存储解决方案中,当客户需要访问某块数据时(通过对象的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的文件定位比较简单,但是在节点扩展的时候操作就更麻烦些。具体选择起来,还要根据业务的特征来决定哪一种更合适。


阅读(9895) | 评论(0) | 转发(5) |
给主人留下些什么吧!~~