概念
三态(RPC)
成功
失败
超时
状态未知
重新读检查
写操作设计为幂等(idempotence)
副本(replica)
这里统一指存储副本, 在不同节点上持久化同一数据
副本一致性(consistency)
一致是指在一定条件下, 系统的数据保持相同
常见一致性
强一致性(strong consistency)
任一用户,任一时间,任一节点读到的都是最新的变更
单调一致性(monotonic consistency)
任一用户,任一时间,读到某次变更后的数据后, 不会读到比这个更旧的数据
会话一致性(session consistency)
任一用户,该次会话中读到某次变更后的数据后,不会读到比这更旧的数据
最终一致性(eventual consistency)
数据更新成功后, 各副本上的数据最终将达到一致的状态(时间不保证, 存在上限?)
用户始终读一个副本,就能满足单调一致性
弱一致性(weak consistency)
评价指标
性能(performance)
可用性(availiability)
扩展性(scalability)
一致性(consistency)
数据
分片(sharding)
hash
扩展性不高, 加/减机器, 所有数据需要重分布
解决方式, 映射和机器分离,用metaserver保存hash(key)->node的关系
metaserver开支高,成瓶颈
数据倾斜(data skew)
热点用户数据落到同一节点上
range
元信息保存映射信息,开支高
chunk
和数据本身的特征没有了关系,只和数据大小有关
所有数据线性排列,按照大小划成chunks.
使用metaserver保存映射信息,也是挑战
consistent hash
应用
最早, p2p网络, 分布式哈希表(DHT)的数据分布算法.
hash函数的改进
将hash函数的值域限制在长度为N的封闭环上, 令N为虚节点(virtual node)的数量, 远大于实际节点数.
每个node上绑定一定的虚节点,数据映射到虚节点上.
副本和分片
不以节点作为副本单位,以数据块作为副本单位
副本控制协议(分布式算法)
CAP定理(Brewer’s theorem)
consistency, availiability, partition tolerance三者只能保证两个
并发控制
多个客户端读写,写写冲突时的解决
分类
中心化(centralized)
简化分布式并发控制, 为中心节点单机并发控制
中心节点宕机,会停服务
primary-secondary(master-slave)
副本分为两种, primary, secondary
primary副本作为中心节点,负责更新,并发控制,协调副本一致性
secondary
问题
数据更新
primary处理并发控制
向其它N个secondary发送变更操作(数据)
集中发送(扇出)涉及到x * N的带宽问题
GFS, secondary之间接力发送
数据读取
读secondary, 最低满足最终一致性.
通过副本版本号, 每次更新后递增版本号, 可以打到会话一致性
强一致性比较困难
只读primary (资源浪费)
副本和节点不绑定的话, 每个节点会有很多数据片的primary, 这样可以降低浪费问题.