Dong Guo's Blog

Notes for Distributed System Theory

| Comments

过去三年参与的广告相关的项目都基于各种各样的分布式存储和计算系统,比如hdfs, hbase, cassandra cluster, memcached cluster, Druid, hadoop和spark。最近在研究各个系统的原理,周末浏览了一本电子书《分布式系统原理介绍》,介绍了很多重要的基础知识,推荐浏览。

Key words:

数据存储方式,consistent hashing,数据副本,副本控制协议,Lease机制,Quorum机制,日志技术,Paxos协议,CAP理论

consistent hashing: 分布式数据存取的经典方案

  1. 背景:数据的分布式存储的一种简单方式为hash, 这种方法简单,无需纪录数据存放在哪台node上。但是当集群需要拓展(或者减少)机器时,由于hash结果一般和机器数目有关,数据需要重新迁移;
  2. Consistent hashing将key组织成一个环,每个node负责一段连续的子环,当增加一个node时,只需要将临近的一个node上的部分数据copy到新node,不停机的情况下,对hit rate的影响明显减小;
  3. 需要额外存储的元数据只有node在环上的顺序,数据量小;
  4. 有一个缺点是:每次加入一个node,只能减轻现有的一个node的压力。且如果是随即分配node在环上的顺序,将很难保证在每个node的’负载均衡’;
  5. 一个较好的解决方案是引入’virtual nodes’: 首先假设有比真实nodes个数明显多的virtual nodes。这个个数是固定的,所以可以预先将其均匀地分布到环上。通过元数据将每个real node关联上多个virtual nodes,注意不是连续的,一般选在环上分隔较远的virtual nodes。这样的话,每加入一个real node,将会将属于其他real nodes的几个virtual nodes分配给新加入的real node,分担了多个real nodes的压力。反之,当一个real node失败,可以有多个real nodes来分担压力。

数据副本: 分布式系统提供高容错高用可行的重要手段

  1. 有2种最常见的数据副本存储方案,一种是以机器为粒度,一种是以数据块为粒度。
  2. 以机器为粒度的缺点:
    • 一旦某台机器数据丢失,数据恢复的效率不高,因为一般需要从非常有限台机器copy数据。而且会比较消耗copy from机器的资源,往往需要让一台机器下线,或者限制copy的速度;
    • 一旦某台机器宕机,压力被有限的几台副本机器分担(若3台机器互为副本,则剩余机器的数据访问压力提高50%)
    • 增加一台机器无法扩容,必须一下增加若干台机器(互为副本)
  3. 以数据块为粒度的好处:(相对应)
    • 一旦某台机器数据丢失,可以从剩余的所有机器上copy数据,数据恢复的效率高
    • 一台机器宕机,不会给任何单台机器增加明显压力;
    • 扩容容易

副本控制协议: 控制各副本数据读写行为,使得副本满足一定可用性和一致性

  1. 中心化副本控制协议:中心结点负责数据的更新,并发控制,协调副本一致性;单点故障
    • primary node在将更新同步到各个secondary nodes时,限于primary node的压力,往往只同步给有限几个secondary nodes,后续采用接力的方式
    • 同步过程的中间状态,包括同步失败的处理,以及access状态的返回,决定了系统的数据一致性
    • primary node宕机由于需要时间来发现(比如10s),在这段时间内无法更新数据
  2. 去中心化副本控制协议
  3. 实例 (大部分分布式数据存储系统都使用primary-secondary副本控制协议)
    • GFS: primary-secondary
    • PUNTS(yahoo!的分布式数据存储平台): 使用primary-secondary协议
    • Dynamo/Cassandra: 使用去中心化副本控制协议
    • Zookeeper: 使用去中心化协议选出primary node,之后就转变为中心化的副本控制协议

Lease机制:保证secondary nodes和primary node的一致性

  1. primary node在向cache nodes同步数据时,还会附带一个时间戳表达这份数据的有效期。在有效期内primary node保证不修改数据,cache nodes可以放心使用数据。
  2. 带来的cost是:若某个cache node提高修改元数据请求,primary node需要阻塞所有cache nodes对该份数据的读写请求,并等待到该份数据的lease超时才修改元数据。
  3. 所以lease的时长比较关键:太长会导致availability下降,太短会导致cache nodes频繁同步primary node;常使用10s
  4. lease机制用于primary node的选择:primary node的更改主要由于结点宕机,而传统的Heartbeat的方法不能有效监控结点状态(存在网络失败,监控机器本身性能问题导致的延时等),故每当nodes给监控机器发heartbeat时,返回一个lease,若primary node心跳失败,则等待lease过期后,监控结点更换primary node
  5. lease机制应用的实例
    • GFS中用于master挑选primary node
    • Chubby(google的分布式文件系统) 有2处使用了lease机制 a). secondary nodes承诺在一段时间内不重新选举primary node; b). primary node用于监控secondary nodes的状态
    • Zookeeper: primary node向client颁发lease

Quorum机制: 可用性和一致性的权衡

  1. 在存在N个副本的情况下,对于更新操作,只要在W在副本上更新成功,则算该更新成功(“成功提交的更新操作”)。当读取R个副本时(限制R+W>N),就可以保证可以读到更新之后的数据。
  2. 注意:仅依赖quorum机制无法知道最新成功提交的版本号,故无法保证强一致性(系统应该始终返回最新的成功提交的数据),需要通过其他方式获取系统最新成功提交的数据;
  3. Quorum机制体现了CAP理论中的availability(update时只需要更新了W个副本,read时只需要读取R个副本)和consistent(由于update或者read只需要在部分副本上成功即可,导致了仅follow Quorum机制不能保证强一致性)的权衡:

Comments