Step 1

题目摘要引言

题目

Erasure-coding-supported 版本的 Raft（协议？），目的是降低存储消耗和网络消耗。

摘要

共识协议可以为分布式系统提供高效可用的分布式服务。在这些写一下，对系统的访问日志复制到多个 server 上。但是完整的 replication 产生了很大的网络与存储开销。

Erasure coding 是降低存储和网络开销的一种常见手段。将 complete-entry replication 替换为 erasure coding replication，可以极大地降低开销。RS-Paxos 式第一个支持 Erasure-coding 的共识协议，本文指出 RS-Paxos 的活力问题，尝试解决并提出了 CRAFT。 不仅使用Erasure coding来减少开销，同时又具备与 Raft 一样的活动性。

基本理论概况

1

结论部分

回答基本问题

1. 类别

2. 内容

3. 正确性

4. 创新点

5. 清晰度

阅读选择

Step 2

细读笔记

问题记录

未读（且值得读）文献记录

Step 3

思路复现

证明与推理复现

实验验证复现

ReadingGroup 会议

目标

减少网络存储开销

Erasure Code

切割编码，一种冗余 Replication 的技术。

和密码学中的秘密分割不同，从需求看，秘密分割需要保证分割部分不能推测出原有秘密信息（哪怕部分）。纠删码则不考虑这一层，它只需要保证可恢复，且可应用于传输 transport 过程中。

• Reed-Solomon(RS) Code

流程解释

Raft

只讲所需部分

• Term 任期
  • 逻辑时间
  • 一个任期最多有一个 leader
• Tree states
  • Follower: 已有 Leader 的 Follower
  • Candidate： 没有 Leader 的时候称为候选人
  • Leader： 具备 Leader 性质
• Preoperty
  • Safty
  • Liveness 容灾能力 N=2F+1
    • 本文要考虑的性质
    • 最大容灾能力 F level

RS-Paxos

• User (k,m)-RS code

这个协议的问题，容灾能力有问题，小于 F。

CRaft 设计思考

需要一个完整块，反证法证明

Code-fragment Replication

编码分块副本策略

• 当数据被 F+k 块存储后，Data 就被承认了
  • 选取任意 F+1 个分块，
• 如果数据被小于 F+k 块存储
  • 需要使用 完整块
  • p = 0

如何把编码分块和完整块共同利用

Prediction

一种贪心的策略

• 使用最近的心跳回答来预测，可能会失败

New Leader

需要增加新的过程 LeaderPre。

分类讨论，对于新 Leader。

Log 分类

• commited 保证了 F+1 可用？？
• uncommitted 好一点的情况，能搜寻够 Fragment，或者搜寻到完整块，最差的情况，需要抛弃。

设计总结

Cheng Li: 很想 RS-Paxos

Raft 中：Leader 一定不会 merge、删除我的日志。

CRaft 中：三类情况下的最差情况，可能会删除。

理论证明删除的影响。。

Theorem

• Log Matching Property

• Leader Completeness Property 完全信任性质

  • 如果一个 log entry，在 givern term T 时提交，那就会。。。 没太懂，这个性质在 CRaft 中满足性质。
• State Machine Safety Property
  • 由前两个性质可以推得，在 CRaft 中也同样满足的性质。

一个重要的东西