《大规模分布式存储系统》 第5章 分布式键值系统【5.1】

javazx

第5章　分布式键值系统
分布式键值模型可以看成是分布式表格模型的一种特例。然而，由于它只支持
7 ]& ]% W" M: X4 P针对单个key-value的增、删、查、改操作，因此，适用3.3.1节提到的哈希分布算
法。
Amazon Dynamo是分布式键值系统，最初用于支持购物车应用。Dynamo将很多
分布式技术融合到一个系统内，学习Dynamo的设计对理解分布式系统的理论很有帮
助。当然，这个系统的主要价值在于学术层面，从工程的角度看，Dynamo牺牲了一
致性，却没有换来什么好处，不适合直接模仿。
  e2 p5 o, R$ V9 b) \Tair是淘宝网开发的分布式键值系统，它借鉴了Dynamo系统的一些设计思路并
做了一些创新，其中最大的变化就是从P2P架构修改为带有中心节点的架构，笔者认
8 ]- a9 s  |# _& c为，这种思路在大方向上是正确的。
- B; H0 M" J* @/ J- }4 z: g2 ~本章首先详细介绍Amazon Dynamo的设计思路，接着介绍淘宝网的Tair系统。
/ ^1 q3 v8 J0 X0 W# d5.1　Amazon Dynamo
Dynamo以很简单的键值方式存储数据，不支持复杂的查询。Dynamo中存储的是
: B, A" C4 _/ g- ]9 y数据值的原始形式，不解析数据的具体内容。Dynamo主要用于Amazon的购物车及S3
+ K$ e: W( P' G+ M  j5 d云存储服务。
Dynamo通过组合P2P的各种技术打造了线上可运行的分布式键值系统，表5-1中
列出了Dynamo设计时面临的问题及最终采取的解决方案。
: }& z8 H, N+ s# `0 M& ^5.1.1　数据分布
Dynamo系统采用3.3.1节（见图3-2）中介绍的一致性哈希算法将数据分布到多个
存储节点中。一致性哈希算法思想如下：给系统中每个节点分配一个随机token，这
些token构成一个哈希环。执行数据存放操作时，先计算主键的哈希值，然后存放到
顺时针方向第一个大于或者等于该哈希值的token所在的节点。一致性哈希的优点在
* E: d  k8 ?: W8 O2 [$ l于节点加入/删除时只会影响到在哈希环中相邻的节点，而对其他节点没影响。
考虑到节点的异构性，不同节点的处理能力差别可能很大，Dynamo使用了改进
的一致性哈希算法：每个物理节点根据其性能的差异分配多个token，每个token对应
一个“虚拟节点”。每个虚拟节点的处理能力基本相当，并随机分布在哈希空间中。
$ a# {' d/ C- Y/ q9 W' U存储时，数据按照哈希值落到某个虚拟节点负责的区域，然后被存储在该虚拟节点
所对应的物理节点中。
. _8 a- ^: \8 L0 c如图5-1所示，某Dynamo集群中原来有3个节点，每个节点分配了3个token：节点
3 }& O9 R9 t+ }6 u% L9 }1（1，4，7），节点2（2，3，8），节点3（0，5，6）。存放数据时，首先计算主
键的哈希值，并根据哈希值将数据存放到对应token所在的节点。假设增加节点4，
* S9 S1 j( G5 t* Z- c. P0 _Dynamo集群可能会分别将节点1和节点3的token 1和token 5迁移到节点4，节点token分
: c2 C) K3 r; Q7 ~" C) M配情况变为：节点1（4，7），节点2（2，3，8），节点3（0，6）以及节点4（1，
5）。这样就实现了自动负载均衡。
图　5-1　Dynamo虚拟节点
为了找到数据所属的节点，要求每个节点维护一定的集群信息用于定位。
5 j( _0 v; u# W/ x, c! rDynamo系统中每个节点维护整个集群的信息，客户端也缓存整个集群的信息，因
6 j: M1 }$ H0 \此，绝大部分请求能够一次定位到目标节点。
& b. j- Q6 T1 B9 V7 r由于机器或者人为的因素，系统中的节点成员加入或者删除经常发生，为了保
; s- C% c; s. w2 B9 ~证每个节点缓存的都是Dynamo集群中最新的成员信息，所有节点每隔固定时间（比
如1s）通过Gossip协议的方式从其他节点中任意选择一个与之通信的节点。如果连接
成功，双方交换各自保存的集群信息。
Gossip协议用于P2P系统中自治的节点协调对整个集群的认识，比如集群的节点
9 M! c# I( Q$ m# \0 R状态、负载情况。我们先看看两个节点A和B是如何交换对世界的认识的：
$ U$ N/ K' [4 Q* T8 t5 d1）A告诉B其管理的所有节点的版本（包括Down状态和Up状态的节点）；
' @7 {. L! Z% K- T2）B告诉A哪些版本它比较旧了，哪些版本它有最新的，然后把最新的那些节
8 e2 {& f9 {7 g6 p点发给A（处于Down状态的节点由于版本没有发生更新所以不会被关注）；
) N0 Z- S/ W1 p( C8 x. _$ r3）A将B中比较旧的节点发送给B，同时将B发送来的最新节点信息做本地更
: m' ]3 `4 D5 h4 S' U; _2 `3 \# r0 L新；
4）B收到A发来的最新节点信息后，对本地缓存的比较旧的节点做更新。
由于种子节点的存在，新节点加入可以做得比较简单。新节点加入时首先与种
2 P2 n3 P; a1 T+ H子节点交换集群信息，从而对集群有了认识。DHT（Distributed Hash Table，也称为
, F4 f- u% r( l9 `; w# U. \一致性哈希表）环中原有的其他节点也会定期和种子节点交换集群信息，从而发现
% S$ ?9 q: Q( N7 {/ j# h新节点的加入。
: H3 J  n# y9 f; H: E( p集群不断变化，可能随时有机器下线，因此，每个节点还需要定期通过Gossip协
. t- f8 V  p8 n3 _6 D5 N' J议同其他节点交换集群信息。如果发现某个节点很长时间状态都没有更新，比如距
$ d; w8 R5 z* [/ f/ C# X1 U离上次更新的时间间隔超过一定的阈值，则认为该节点已经下线了。
% [' ~$ z& _  }5.1.2　一致性与复制
8 q& V) w: Q! E/ ?( F; r& a* _为了处理节点失效的情况（DHT环中删除节点），需要对节点的数据进行复
制。思路如下：假设数据存储N份，DHT定位到的数据所属节点为K，则数据存储在
节点K，K+1，……，K+N-1上。如果第K+i（0≤i≤N-1）台机器宕机，则往后找一台
机器K+N临时替代。如果第K+i台机器重启，临时替代的机器K+N能够通过Gossip协
# u' E4 b8 j8 J- I4 X  l议发现，它会将这些临时数据归还K+i，这个过程在Dynamo中叫做数据回传（Hinted
Handoff）。机器K+i宕机的这段时间内，所有的读写均落入到机器[K，K+i-1]和
! {0 g* B; R+ C# Z8 z- [[K+i+1，K+N]中。如果机器K+i永久失效，机器K+N需要进行数据同步操作。一般来
说，从机器K+i宕机开始到被认定为永久失效的时间不会太长，积累的写操作也不会
太多，可以利用Merkle树对机器的数据文件进行快速同步（参见下一小节）。
- g* W. B+ }  `& {  O' gNWR是Dynamo中的一个亮点，其中N表示复制的备份数，R指成功读操作的最
少节点数，W指成功写操作的最少节点数。只要满足W+R＞N，就可以保证当存在不
% q) O8 k) H6 [超过一台机器故障的时候，至少能够读到一份有效的数据。如果应用重视读效率，
* ~- u, s& V9 T; f; f% Y1 @) Q可以设置W=N，R=1；如果应用需要在读/写之间权衡，一般可设置N=3，W=2，
8 _: x# @  T9 Y( zR=2；当然，如果丢失最后的一些更新也不会有影响的话，也可以选择W=1，R=1，
4 y/ o2 n6 r; H1 v7 E  CN=3。
  r4 ~) p. x; a. b# A6 TNWR看似很完美，其实不然。在Dynamo这样的P2P集群中，由于每个节点存储
- M9 c1 S9 Z. H1 }$ I' p9 u的集群信息有所不同，可能出现同一条记录被多个节点同时更新的情况，无法保证
多个节点之间的更新顺序。为此Dynamo引入向量时钟（Vector Clock）的技术手段来
8 o& x. _1 {+ }) I尝试解决冲突，如图5-2所示。
( r+ J, P; s, ~1 y2 Q; D) e- U图　5-2　向量时钟
* {  h, d# q1 L- @( q. _. b" ^Dynamo中的向量时钟用一个[nodes,counter]对表示。其中，nodes表示节点，
; E: {- T$ L+ e5 ^, e3 Wcounter是一个计数器，初始为0，节点每次更新操作加1。首先，Sx对某个对象进行
一次写操作，产生一个对象版本D1（[Sx，1]），接着Sx再次操作，counter值更新为
2，产生第二个版本D2（[Sx，2]）；之后，Sy和Sz同时对该对象进行写操作，Sy将
自身的信息加入向量时钟产生了新的版本D3（[Sx，2]，[Sy，1]），Sz同样产生了新
的版本信息D4（[Sx，2]，[Sz，1]），这时系统中就有了两个冲突的版本。最常见的
冲突解决方法有两种：一种是通过客户端逻辑来解决，比如购物车应用；另外一种
常见的策略是"last write wins"，即选择时间戳最新的副本，然而，这个策略依赖集群
: q2 f) B* @: J. [8 X2 J内节点之间的时钟同步算法，不能完全保证准确性。
0 y- }( e% e& J1 |5 ~; J向量时钟不能完美解决冲突，即使N+W＞R,Dynamo也只能保证每个读取操作能
读到所有的更新版本，这些版本可能冲突，需要进行版本合并。Dynamo只保证最终
5 \+ C4 X2 j( \0 g  d" Y7 r一致性，如果多个节点之间的更新顺序不一致，客户端可能读取不到期望的结果。
7 a1 e5 x' m% t这个不一致问题需要注意，因为影响到了应用程序的设计和对整个系统的测试工
作。
5.1.3　容错
Dynamo把异常分为两种类型：临时性的异常和永久性异常。有一些异常是临时
性的，比如机器假死；其他异常，如硬盘报修或机器报废等，由于其持续时间太
# f+ t2 N1 T9 {1 r" G: c长，称为永久性的。下面解释Dynamo的容错机制：
' g4 d# _! q# I3 y3 v●数据回传　在Dynamo设计中，一份数据被写到K，K+1，……，K+N-1这N台
机器上，如果机器K+i（0≤i≤N-1）宕机，原本写入该机器的数据转移到机器K+N，
( D0 Z6 Y4 `1 b如果在指定的时间T内K+i重新提供服务，机器K+N将通过Gossip协议发现，并将启
动传输任务将暂存的数据回传给机器K+i。
●Merkle树同步　如果超过了时间T机器K+i还是处于宕机状态，这种异常被认为
是永久性的。这时需要借助Merkle树机制从其他副本进行数据同步。Merkle树同步的
原理很简单，每个非叶子节点对应多个文件，为其所有子节点值组合以后的哈希
0 L$ u" W9 j8 V值；叶子节点对应单个数据文件，为文件内容的哈希值。这样，任何一个数据文件
不匹配都将导致从该文件对应的叶子节点到根节点的所有节点值不同。每台机器对
! v& D7 Z3 C8 g( v1 J$ R每一段范围的数据维护一颗Merkle树，机器同步时首先传输Merkle树信息，并且只需
* ^/ E2 y, m2 r% z* C; V要同步从根到叶子的所有节点值均不相同的文件。
●读取修复　假设N=3，W=2，R=2，机器K宕机，可能有部分写操作已经返回客
# D3 L0 h1 M; N3 \2 S- C& q户端成功了但是没有完全同步到所有的副本，如果机器K出现永久性异常，比如磁盘
2 Q8 @/ {/ T, o! O, G故障，三个副本之间的数据一直都不一致。客户端的读取操作如果发现了某些副本
0 t" i4 f7 o: i+ q版本太老，则启动异步的读取修复任务。该任务会合并多个副本的数据，并使用合
2 u4 I# ^0 `1 s. o1 C1 u并后的结果更新过期的副本，从而使得副本之间保持一致。
5 ?# U9 W5 n  o, s6 j5.1.4　负载均衡
& D- R# g7 k& D3 uDynamo的负载均衡取决于如何给每台机器分配虚拟节点号，即token。由于集群
1 I% P, N; d$ F( @$ U环境的异构性，每台物理机器包含多个虚拟节点。一般有如下两种分配节点号的方
  V% @$ y, {( y+ _7 N/ K  y% j5 F法。
●随机分配。每台物理节点加入时根据其配置情况随机分配S个Token。这种方法
的负载平衡效果还是不错的，因为自然界的数据大致是比较随机的，虽然可能出现
* _# t- V4 [  x* X: B0 o某段范围的数据特别多的情况（如baidu、sina等域名下的网页特别多），但是只要切
分足够细，即S足够大，负载还是比较均衡的。这个方法的问题是可控性较差，新节
; J1 Y- c# z1 R0 p1 u点加入/离开系统时，集群中的原有节点都需要扫描所有的数据从而找出属于新节点
$ `7 s, P; k4 O! j/ C的数据，Merkle树也需要全部更新；另外，增量归档/备份变得几乎不可能。
●数据范围等分+随机分配。为了解决上种方法的问题，首先将数据的哈希空间
8 t4 a- Q2 v  A等分为Q=N×S份（N=机器个数，S=每台机器的虚拟节点数），然后每台机器随机选
择S个分割点作为Token。和上种方法一样，这种方法的负载也比较均衡，并且每台
机器都可以对属于每个范围的数据维护一颗逻辑上的Merkle树，新节点加入/离开时
$ F! d! {5 @' |+ X只需扫描部分数据进行同步，并更新这部分数据对应的逻辑Merkle树，增量归档也
7 {; ^1 I% @6 l' K" p变得简单。
5 q& [3 ]9 s1 {; h; m3 j* h另外，Dynamo对单机的前后台任务资源分配也做了一些工作。Dynamo中同步操
9 y5 u3 m; U/ i作、写操作重试等后台任务较多。为了不影响正常的读写服务，需要对后台任务能
; x* C6 w) J: A+ f% T( i- T够使用的资源做出限制。Dynamo中维护一个资源授权系统。该系统将整个机器的资
源切分成多个片，监控60秒内的磁盘读写响应时间，事务超时时间及锁冲突情况，
根据监控信息算出机器负载从而动态调整分配给后台任务的资源片个数。
5.1.5　读写流程
Dynamo的读写流程如图5-3和图5-4所示。
图　5-3　Dynamo写入流程
图　5-4　Dynamo读取流程
Dynamo写入数据时，首先，根据一致性哈希算法计算出每个数据副本所在的存
- x( I, ]5 e4 c' O% B7 r储节点，其中一个副本作为本次写操作的协调者。接着，协调者并发地往所有其他
$ _; t5 v( d- `6 ~9 ^$ }. i副本发送写请求，每个副本将接收到的数据写入本地，协调者也将数据写入本地。
当某个副本写入成功后，回复协调者。如果发给某个副本的写请求失败，协调者会
# i- O" u4 Y7 D, A) X8 h将它加入重试列表不断重试。等到W-1个副本回复写入成功后（即加上协调者共W个
副本写入成功），协调者可以回复客户端写入成功。协调者回复客户端成功后，还
0 M, p# D( d. T会继续等待或者重试，直到所有的副本都写入成功。
6 y9 k' W. O0 j* i% ~Dynamo读取数据时，首先，根据一致性哈希算法计算出每个副本所在的存储节
( t7 |7 Y  R8 g* ?  `0 M1 G点，其中一个副本作为本次读操作的协调者。接着，协调者根据负载策略选择R个副
  t1 f& l- O; y) \7 W* k1 D本，并发地向它们发送读请求。每个副本读取本地数据，协调者也读取本地数据。
当某个副本读取成功后，回复协调者读取结果。等到R-1个副本回复读取成功后（即
加上协调者共R个副本读取成功），协调者可以回复客户端。这里分为两种情况：如
6 R0 f, ]" s: i% E4 T5 S% W3 @* @. j果R个副本返回的数据完全一致，将某个副本的读取结果回复客户端；否则，需要根
据冲突处理规则合并多个副本的读取结果。Dynamo系统默认的策略是根据修改时间
- _& D) g! c7 Q4 e7 H戳选择最新的数据，当然用户也可以自定义冲突处理方法。读取过程中如果发现某
& w  A4 {# m* x: m* m# V+ _& y% m! j9 `# `些副本上的数据版本太旧，Dynamo内部会异步发起一次读取修复操作，使用冲突解
! g6 o2 S) Y/ [3 J决后的结果修正错误的副本。
/ Q" p4 `) k1 f  W! g5.1.6　单机实现
5 U9 j  Z- A* ?- T* wDynamo的存储节点包含三个组件：请求协调、成员和故障检测、存储引擎。
Dynamo设计支持可插拔的存储引擎，比如Berkerly DB（BDB），MySQL InnoDB
等。存储的需求很多，设计成可插拔的形式允许用户根据应用特点选择合适的存储
引擎，比如BDB存储的对象大小一般在几十KB之内，而MySQL可以处理更大的对
$ F3 c7 Y' Z/ Z. y象。用户会根据应用对象大小选择存储引擎，默认为BDB。
% ]6 b( j+ C4 B3 p2 R( \请求协调组件采用基于事件驱动的设计，每个客户端的读写请求对应一个状态
机，系统根据发生的事件及状态机中的状态决定下一步的操作。比如读取操作对应
的状态包括：
, d1 o5 M  O$ b" |. ^7 ]●协调者发送读请求到其他节点；
●等待其他节点返回读取结果，最少需要R-1个；
+ z$ H! @, w7 g9 k+ R6 s7 D●如果请求其他节点返回失败，需要按照一定的策略重试；
●如果到达时间限制成功的节点仍然小于R-1个，返回客户端请求超时；
3 l' b4 r4 p( a% j, P( c' d●合并协调者及其他R-1个节点的读取结果，并返回客户端，合并的结果可能包
+ Q0 }! `% Z! P2 l- Z4 b/ p7 ~" G3 O含多个冲突版本；如果设置了冲突解决方法，协调者还需要解决冲突。
读操作成功返回客户端以后对应的状态机不会立即被销毁，而是等待一小段时
间，这段时间内可能还有一些节点会返回过期的数据，协调者将更新这些节点的数
据到最新版本，这个过程称为读取修复。
5.1.7　讨论
. `* p* L$ N# R4 z3 \) A$ K& sDynamo采用无中心节点的P2P设计，增加了系统可扩展性，但同时带来了一致
, R- [5 w& ^) y; `% q+ k- J/ x, I' A性问题，影响上层应用。另外，一致性问题也使得异常情况下的测试变得更加困
; X# ^% g2 P) L" K# Z8 j5 k难，由于Dynamo只保证最基本的最终一致性，多客户端并发操作的时候很难预测操
作结果，也很难预测不一致的时间窗口，影响测试用例设计。
总体上看，Dynamo在Amazon的使用场景有限，后续的很多系统，如Simpledb，
采用其他设计思路以提供更好的一致性。主流的分布式系统一般都带有中心节点，
( K% m7 Z+ e/ Y: x/ [+ k这样能够简化设计，而且中心节点只维护少量元数据，一般不会成为性能瓶颈。
5 S+ I5 z8 d2 l; {从Amazon、Facebook等公司的实践经验可以得出，Dynamo及其开源实现
* @" L" Y" F) F, I* [2 u7 _0 rCassandra在实践中受到的关注逐渐减少，无中心节点的设计短期之内难以成为主
2 \8 w$ M* H; E' l, g2 J流。另一方面，Dynamo综合使用了各种分布式技术，在实践过程中可以选择性借
+ H4 N+ i. `, z4 j鉴。
. O, O* M' j5 Z: w4 p