Ourdark

CAP理论及延伸

Ourdark -

大数据的变革正在进行，基于很多因素使得关系型数据库被迫转向大数据（NoSql/NewSql）：

  • 可扩展性（Scalablity） -- 硬件价格
  • 高性能（Performance） -- 传统数据库性能瓶颈
  • 弱一致性（Relaxed consistency) -- CAP理论
  • 敏捷性（Agility） -- 持久多样性
  • 复杂定（Intricacy） -- 海量数据
  • 必然性（Necessity）-- 开源

其中CAP是NoSql数据管理系统构建的基础
C（Consistency）强一致性
A（Availability）可用性，每一个操作总是能在一定的时间内返回结果
P（Partition Tolerance）分区容错性（孤立区域/集群管理）

假设网络中存在两个节点N1和N2，A1和A2是运行在对应节点上的数据交互应用（或平台框架），两个节点有一致的数据副本V0，以更新为例过程如下：

  • A1将V0更新为V1
  • A1更新成功后发送消息给A2，信息为“更新V0为V1”
  • 请求获取A2中的V1

如果在第二个步骤中，网络中断，那么A2内的副本将无法得到更新，此时步骤三将会受到影响。将会带来问题：

  • 系统不提供服
  • 继续读取脏数据

放弃P：不允许分区错误发生，那么必须使用分布式悲观锁（两阶段提交），影响系统性能，从而导致可用性降低。
放弃A：系统必须一直可用，这似乎不太可能，必然会引起数据不一致
放弃C：不保值强一致性，保持软状态和最终一致性

Leverage这个问题的方法可以采取降低一致性要求（这并不等于不满足一致性需求）的方式。首先一致性包含：强一致性（分布式事务协议）、弱一致性（更新时间会产生不一致窗口）、最终一致性（到达某个时间点后，系统处于一致）。

ACID理论是强一致性约束，即传统数据库中的原子性、一致性、隔离性和持久性。而Base方法牺牲了一定的一致性和鼓励性提高可用性和系统性能，基本原则：
基本可用（Basically Available）：系统能够基本运行、一直提供服务
软状态（Soft State）：系统不要求强一致性，允许存在不一致窗口
最终一致性（Eventual consistency）：系统在某一时刻后到达一致性要求

为了满足一致性需求以及系统的性能以及高可用，最终一致性模型可以采取：

  • 因果一致性（Causal）：如果是一个逻辑传递关系，A->B->C，那么C需要保持一致性
  • 读自写一致性（Read Your Own Writes）
  • 会话一致性（Session）
  • 单调读一致性（Monotonic Read）：当用户读取一个数值后，后续操作读取到历史版本
  • 时间轴一致性（Monotonic Write）：所有操作必须按照相同的顺序执行
    ...

根据不同的业务需求，可以采用适当的最终一致性模型。

对于一个分布式系统的一致性实现技术，Quorum系统NRW策略：

N表示数据所具有的副本数
R完成读操作需要的最小副本数
W完成写操作需要最小的副本数

只要满足R+W>N即可保证强一致性
几个特例：
N=2，W=2=N，R=1 要求读性能高可用，但对写操作要求高
W=1，R=N=2 要求写操作高性能，但度操作会因为节点故障无法完成操作
R=W=Q（Q=N/2 +1）读写均衡

两阶段提交协议：

在分布式系统中，尤其是在分布式关系数据库中，强一致性两阶段提交协议，其缺点是阻塞以及协调者离线。该协议：请求阶段/表决阶段（commit-request phase/voting phase）以及提交阶段（commit phase）

图解参见另文大数据基础理论（ppt尚未总结为博文，敬请谅解）

时间戳策略

  • 时间戳
  • 逻辑时钟

Paxos

R:当提议被大多数批准者批准，则表明该协议被批准

准备阶段：

  • 提议者选择一个恰当的版本号N，并发送一个版本号为N的“准备请求”到每一个批准者大多数集
  • 如果某个批准者接收到该“准备请求”，并且该请求版本号N大于该批准者响应过的任意“准备请求”版本号，那么批准者向提议者承诺不会再响应任何版本号小于N的提议，并告知批准者曾经批准过的提议的最高版本号。

批准阶段

  • 如果提议者收到来自大多数集对于版本号为N的“准备请求”的响应信息，那么它该向大多数集发送关于“版本号为n，值为v的提议”的“批准请求”，如果该响应不为空，其中v值为该响应信息中最高版本号提议的值：如果该响应为空，那么它可以自行指定提议的值。
  • 如果批准者接收到了版本号为N的提议的“批准请求”，那么除非它曾经响应过版本号大于N的提议的“准备请求”，否则它必须批准该协议。

批准者将关于提议的信息发送给某几个不同的学习者，然后这个学习再通知其它的学习者该信息。

实例：Zookeeper

向量时钟

  • 初始时，每个节点设置为0。每当有数据更新发生，该节点所维护的时钟将增长一定的步数d（系统提前设定）
  • 在节点i的数据更新之前，我们对节点i所维护的向量Vi进行更新Vi=Vi[j]+d(d>0)
  • 当节点i向节点j发送更新消息时，将携带自身所了解的其他节点的向量时钟信息。节点j将收到的向量与自身的向量时钟信息进行比较，然后进行更新：
    Vj[k]=max{Vi[k],Vj[k]}
    确定偏序关系：
    对于N维向量，Vi>Vj为如果对于任意k（K<[0,n-1])，均有Vi[k]>Vj[k]
    如果Vi不大于Vj，Vj也不大于Vi，那么需要解决冲突，方法可以是合并或客户端处理。

向量时钟使得节点间不需要同步，也不需要全局时钟，也不需要维护数据版本，但可能会占据大量空间。