Baixiangcpp's Blog

经常看到网上对Raft 论文 5.4.2 一节的讨论，这里记录一下我对这个问题的理解。

论文开头是这么描述的:

A leader knows that an entry from its current term is committed once that entry is stored on a majority of the servers. If a leader crashes before committing an entry, future leaders will attempt to finish replicating the entry. However, a leader cannot immediately conclude that an entry from a previous term is committed once it is stored on a majority of servers.

后续的领导人不能判断之前任期里的日志在被复制到多数派的服务器后，就一定被马上被提交了。换句话说，也就是说领导人并不知道之前的任期的日志是否已经被提交，即使这条日志已经被复制到了多数派的服务器上。根据 Raft 协议，这条日志是不能被直接提交的。

在探究为什么之前，我们先假设:如果后续的领导人在当选后，发现之前任期的一条日志已经被复制到多数派的服务器上，直接提交这些日志会发生什么？

Raft 虽然在核心思想上基本都是师承 Paxos 祖师爷（Lamport） 的精髓，基于多数派的协议。但是 Raft 论文的发表的主要意义在于”易于理解”。把一致性协议从 “阳春白雪” 变成了让我等普通码农都可以上手的东西。基本上已经把一个易于工程实现的算法讲得非常明白了，没有太多争议和发挥的空间。

以下是论文全文的内容。

摘要

Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能，但是它的算法结构和 Paxos 不同，使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可理解性，Raft 将一致性算法分解成了几个关键模块，例如领导人选举、日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态的数量。一项用户研究的结果表明，对于学生而言，Raft 算法比 Paxos 算法更加容易学习。Raft 算法还包括一个新的机制来允许集群成员的动态改变，它利用重叠的大多数来保证安全性。

作为一个支持增量传输、去重存储的同步盘，实现一个高效率的文件分块算法是重中之重。本篇博客在研究了seafile的分块算法之后，将其中的分块算法实现抽取了出来，并详细描述了它基于可变长度分块(Content Defined Chunking)算法的实现。项目托管在Github上:FileCDC。

编译后，直接将文件名作为参数，即可分块:

同时也很方便集成到其他的项目里,调用cdc_work(const char* filename)会将file分块。

原始指针(raw pointer，为了表述方便，下面提到的‘指针’均指原始指针)是C/C++最强大的工具，它威力无穷，但是稍有不慎，就有引发各种内存问题。智能指针来势汹汹，它利用RAII特性对指针的封装，帮助程序员自动管理内存。其目的是用来代替指针。重载了操作符(operator*,operator->和operator[])，用起来和指针没多大区别。同时也规避了许多指针带来的陷阱，大大减少了程序员犯错的机会。本篇博客我将列举原始指针之罪以及一些不得不使用智能指针的理由。

本文的智能指针(https://en.cppreference.com/book/intro/smart_pointers)是指C++11以来的std::unique_ptr、std::shared_ptr和std::weak_ptr,不包括半吊子的std::auto_ptr，它谈不上智能二字(不支持移动语义，不能存储在容器中)。

标题碰瓷自scott meyers大师的Effective系列，他们是每个C++程序员都应该拜读的神作(有网友打趣到:”c++程序员可以分成两类，读过effective c++的和没读过的”)。

epoll顾名思义就是Event Poll，是Linux上一个非常”屌炸天”的多路复用机制(关于多路复用的概念可以参考知乎网友的解释:https://www.zhihu.com/question/32163005/answer/55772739)。

epoll出现之前Linux上已经有2个多路复用机制:select和poll，但是后两者在epoll面前显得比较鸡肋。

这是《THE LINUX PROGRAMMING INTERFACE》的关于这3个多路复用效率的对比,当需要监听的I/O事件数量比较大的时候，epoll的优势尤为明显。其原因主要体现在两个方面:

• 每次监听I/O事件的时候，不需要往内核传送大量的文件描述符集，epoll的兴趣列表(interest list)由内核维护的红黑树负责。
• epoll只会返回I/O就绪的文件描述符列表(ready list),因此不需要遍历所有的文件集去找发生的事件。（这个其实微不足道，甚至可以忽略，许多博客都喜欢把这个归纳为主要原因，上图的数据，不包括这个时间）

很长一段时间，我曾以为像定时器这样基础的功能，操作系统会有一个完备的实现。当需要开启一个定时任务的时候，会有一个优雅的、如下形式的接口：

1
2

typedef void (*callback)(void*);
void setTimeout(unsigned int second,callback cb，void* arg);

可是事与愿违，Linux下不存在这样的接口。