数据管理——Paxos、Raft算法、Storm、Kafka

目的

解决分布式环境下一致性的问题

阶段

• 准备
  • 监督者接受请求、产生判断、返回承诺
  • 发起者依据返回的承诺决定是否继续更新数据而进入下一阶段的请求
• 接受
  • 监督者们接受更新请求并完成多请求

• 算法变种
  • Classisc Paxos
    • 一个实例写入（确定一个值）需要2轮
  • Multi Paxos
    • 约为一轮，第一轮合并，使得只需要进行第二轮
  • Fast Paxos
    • 没冲突一轮RPC确定一个值，有冲突用两轮

原则

• 安全原则
• 存活原则
  • 单Master-slave，Master单一容易挂

单一监督结点不能保证存活，所以依然采用多个监督结点的策略。

保持一致性：

• 主从异步复制
• 主从同步复制
• 主从半同步复制
  • 主节点接到写请求
  • 主节点复制日志到从库
  • 主节点等到n个库返回ok，就打赌所有库都已经写入

• 多数派写
• 多数派读
• 法定集合
  • 任意两个集合，他们有公共结点

算法定义

算法概念

• instance：一次Paxos算法执行
• proposal：一个经过发起但还没批准的提案
• value（决议）：被最终批准通过的议案中的值
• propose：提出议案
• Accepteor：审批议案
• Learner：学习决议

二段提交原则：每个申请者在发送自己的提案之前，先检查有没有已经提议且被批准的值，有则放弃自己的提案——最终只有一个值被批准

上述原则如果在没有诺言的情况下在并发存在问题：

在第一轮时：S1=red，S2=blue，5个accptor，1、2、3先接受了S1，3、4、5又批准了S2（在3中，S1比S3先到达）。出现了多个值批准的问题。

所以使用优先级来解决问题，系统优先考虑比较晚的申请，但较早的申请可能诺言大。

系统最终选择诺言最大的一个作为最终状态。

算法阶段

• Prepare
  • Proposer，选择一个提案n，发请求到Acceptors汇总一个多数派（法定集合）
  • 如果提案编号小于Acceptors回复的编号，则拒绝该prepare消息；
  • …大于…，则Acceptor将自己上次接受的提案回复给Proposer，并承诺不会再响应小于n的提案（接收Proposer的消息）
• Acceptor
  • 当一个Proposer收到了多数acceptors对prepare提案的回复后，就进入了批准阶段，它要向回复prepare请求的acceptors发送accept请求。
  • 如果没有收到过半的回应，会重新进入第一阶段——递增提案号，重新提出prepare请求。

存储信息

• Proposer
  • 已经提交的最大proposal编码，instance编号
• 接受者
  • 已承诺的最大编号
  • 已接受的最大编号和value、instanceid
• 学习者
  • value

Raft算法

与Paxos算法类似

CAP定理

把业务分成

• Leader
• Follower
• Candidate

Kafka的特性

• 持久性
• 支持通过kafka服务器和消费机集群来分区消息
• 高吞吐量，地延迟
• 集群热拓展
• 高并发

消息的组织形式：

• kafka为每个topic维持一个分了区的消息日志。日志都只能有序且末尾添加，日志中的记录都有一个id号用于在该partition序列内唯一标识自己，记为offset.
• 每一个partition，被均匀分配到多个大小相等的segment中。但每个segment文件内的消息数量不一定相等。
• 收到消息后，等到一次满了就flush到磁盘，之后消费者才能在磁盘上看到新信息。

事务性广播

Spark

• 可以直接读写hadoop上的任何格式数据
• 基于内存计算
• 支持DAG图的分布式并行计算
• 提供Cache机制支持反复迭代计算或者多次数据共享
• 减少数据读取的I/O开销
• 使用多线程池模型减少task启动开销
• shuffle避免不必要的sort及磁盘io操作
• 广泛的数据集操作类型，比MapReduct性能好

核心概念

• RDD（Resilient Distributed Dataset, 弹性的分布式数据集）：一个只读的、可分区的分布式数据集
• RDD具有缓存机制