-
一、
分布式存储系统的设计原则:
CAP
理论:一个分布式存储系统不可能同时满足一致性、可用性和分区容
错性这三个需求,
最多能够同时满足两个,
因此不要把精力
浪费在如何设计才能
同时满足
CAP
三
者的完美分布式存储系统,而是应该研究如何进行取舍,满足
实际的业务需求。
其中
C:Consistency
在分布式环境中,多点的数据时一致的。
A:Availability
每个操作总能在确定的时间返回,即系统随时都是可用的。
P:Tolerance of network
Partition(
分区容忍性
)
:在出现网络分区
(
如断网
)
的情
况下,分离的系统也能正常运行。
对于分布式存储系统而言,分区容忍性是基本需求,因此只有
CP
p>
和
AP
两种
选择。
CP
模式保证分布在网络上不同节点数据的一致性,
但对可用性支持不足
;AP
模式主要实现
”
最终一致性
”
来确保
可用性和分区容忍性,但弱化了一致性需求。
二、
结构化的
P2P
分布式存储系统
对于
P2P
分布式存储系统涉及的问题主要包括覆盖网以及路由协议、
p>
数据放
置与一致性维护、副本管理、负载均衡算法、安全性等问题,
下面介绍几种
P2P
分布式存储系统,如
OceanStore
、
CFS
、<
/p>
KVStore
等。
2.1.
OceanStore <
/p>
OceanStore
的基本数据是对象
(Object)
,用一个
128
位的
objectId
标识。
它的覆盖网是
Tapstry
。
< br>OceanStore
的访问控制提供两种基本的控制原语,即读控制和写控制。
更复杂的控制策略可以由这两个组合构成。
< br>OceanStore
的定位和路由机制:
Oceans
tore
中数据对象可以存储在任何
节点上,这为副本策略和缓
存策略提供了很大的灵活性,但是增加了定位的
难度,为此
Oc
eanstore
。有两种文件定位机制不确定性算法和确定性算法
,
如果数据在邻居节点则用不确定算法非常快,如果不确定算法没有找到数
据,那么就要用确定的算法,这两种算法如下
:
?
不确定算法
不确定算法的文件定位机
制是在局部使用,
这里面主要用到了一种随机
的数据结构
Bloom Filter
,
BloomFi
lter
利用位数组很简洁的来表示一个集合,
并能判断一个元
素是否属于这个集合,其主要思想如下
初始状态时,
BloomFilter
是一个包含
m
位的位数组,每一位都置为
0
,为了
表达
S={x
1
, x<
/p>
2
,…,x
n
}
这样一个
n
个元素的集合,
Bloom Filter
使用
k
个相互独
立的哈希函数
(
Ha
sh Function
)
,
它们分别
将集合中的每个元素映射到
{1,…,m}
的范围中。对任意一
个元素
x
,第
i
个哈希函数映射的位置
h
i
(x)<
/p>
就会被置为
1
(
1
≤
i
≤
k<
/p>
)
。
注意,
如果
一个位置多次被置为
1
,
那么只有第一
次会起作用,
后面几次将没有任何效果。在下图中,
k=3
p>
,且有两个哈希函数选中同一个
位置(从左边数第五位)
。
在判断
y
是否属于这个集合时,我们对
y
应用
k
次哈希函数,如
果所
有
h
i
(
y)
的位置都是
1
(
< br>1
≤
i
≤
k
)
,那么我们就认为
y
是集合中的元素,否则
就认为
y
< br>不是集合中的元素。下图中
y1
就不是集合中的元素。<
/p>
y2
或者属于
这个集合,或者刚好是一个
false
positive
。
以上就是
BloomFilter<
/p>
,
Oceanstore
中的节点利用<
/p>
BloomFilter
来标识本节点上存
在哪些文件,节点之间交互
BloomFilter
,这样节
点可以通过交互的邻居节点的
BloomFilter
来判断邻
居节点是否含有该文件,文件定位过程如下:
查找对象
X
,
对象
X
通过
3
个哈希函数映
射到
BloomFilter
位数组的第
0
、
1
、
3
的位置。
a)
n
1<
/p>
节点的
BloomFilter
是
10101
,它的第
0
、
1
、
3
位
不全是
1
,所以可以
判断
X
不在
n
1
上,这是
n
1
存有它的邻居节
点
n
2
的
Bl
oomFilter11100
以
及另一个
11011
,显然
n
2
更有可能含有
X
,然后查询步骤到达
n
2
节点
b)
n
2<
/p>
BloomFilter
的第
0
、
1
位虽然是
1
,但第
3
位是
0
p>
,所以不在
n
2
上
,然
后从
n
2
保存的邻居节点
n
3
和
n
4
的
BloomFilte
r
,发现
n
3
的
BloomFilter
的第
0
p>
、
1
、
3
位全为
1
,则可以判定
X
在
n
3
节点
上
c)
上
面就是一次利用
BloomFilter
的一次文件定位过程,
用于局部。
?
确定算法
当不确定算法的文件定位失败后,则进行比较慢的确定的定位算法。
这种确定的文件定位算法跟
Pastry
中的文件定位机制一样,
不过这
里采用的是后缀匹配路
由算法,将文件定位到节点
ID
与文件
ID
最近的
节点上面。当一个文件的副本放置在系统的某个节点
上时,它的存储位
置就被发布到与该文件
ID
< br>最近的节点上
(
称为该文件的根节点
)
,然后将
副本存放位置的指针存在该根节点上;当需要去
文件时,先路由到根节
点,从根节点获取副本存放位置,然后直接和副本节点通信。
p>
归档存储:
O
ceanStore
还使用了归档存储,主要是利用了纠删码
(
erasure
coding)
的方法将数据分散到大量节点
上,纠删码将原数据分成等大的
n
块,
通过编码生成
m
块
(m>n)
,然后将
m
块数据用
D
HT
方式进行存储,它的特点
是只需要
m
块中的
n
块就可以恢复出原始数据,
所以通过这种方式提高了数
据的可靠性。
内省机制:
OceanStore
由上百万的结点共同组成,这些结点的存储空间、
带宽、计算能
力都不相同,并且结点不断地加入、退出或者失效,内省机制
让系统对环境具有自适应的
能力,它在运行中增加了
”
观测
”
p>
和
”
优化
”
两个部
分,观测模块监测并记录系统的运行状况,之后从所有记录的历
史数据中提
取有用的特征进行分析。优化模块根据这些分析结果调整系统的运行参数和<
/p>
各种策略的选择以适应环境的变化。内省机制主要在两个方面使用:一是聚
集分辨,判断哪些对象数据之间有着密切的联系;另一个是副本管理,调整
副本
的个数和存放位置以使得这些副本可以更高效更合理地满足用户需求。
2.2.
CFS(Cooperative File System)
CFS
是一个只读的
P2P
存储系统
,该系统将需要存储的文件分成若干块
(block),
将每块
复制多份存储,
CFS
主要由两层构成,一层是
Dhash
,一层是
Chord
,
Dhash
层用来为客户端取数据块,以及将数据块分布到
CFS
系统中,
以及维持副本和缓存;
Chord
层是用来定位
Block<
/p>
的。
CFS
的结构如下:
垂直方向通过
API
p>
相互连接,水平方向通过
RPC
API
来连接。如图所示,
CFS C
lients
由三层组成,分别是
FS
层,
Dhash
层,
Chord
层,
FS
层利用
Dh
ash
层去存取数据,
Dhash
层利
用
Chord
层去定位数据;
CFS
Server
有两层
Dhash
和
Chord
层,
D
hash
层用来存储数据块,
维持合适副本以及缓存流行的数据
块。
2.2.1.
Chord
层
用来数据块定位,定位方式就是覆盖网
Chord
的定位方式
2.2.2.
Dhash
层
Dhash
层用来存储并查找固定
ID
的块,并且处理副本、缓存等,
它利用
Chord
层来帮组它定位数据块。该层将文件分块,然后决定将这
些数据块放到哪些
Server
上。
将文件分块存储虽然
增加了查询开销
(
获得
一个文件需要找
到该文件所有的块
)
,
但是它从一定程
度上解决了负责均
衡的问题。
-
-
-
-
-
-
-
-
-
上一篇:配电柜面板中英文对照
下一篇:模具、手板模型、机械加工机器名称-日语词汇