前言

这是前段时间在公司内部关于 paxos 做的一次技术分享，主要围绕 basic-paxos/multi-paxos 协议进行，并会对 raft 协议进行一些对比，简单提及了一下 pbft。

取名“深入浅出 paxos”，意思是从分布式模型的简化和抽象系统，讲到分布式数据一致性的核心问题，再引出 paxos 协议的核心，再从纯理论的 basic-paxos 到落地工程实践的 multi-paxos，最后对比 raft、pbft 协议，从简入深，再从深到核心，再到工程实践。

由于是一次技术分享，所以和我之前的技术博文不太一样，有些东西并没有完全写到博客里，包括一些现场讨论等，所以可能读完之后对 paxos 理解效果会差一点。

名词介绍

• paxos: 应该是分布式领域较早出现的数据一致性协议（本文研究的正是此协议）
• basic paxos: 通常说的 paxos 就是指 basic paxos，或者称为 classical paxos
• multi-paxos: paxos 的改进，迈出了工程实践的步伐（性能改善，工程落地）
• epaxos/fast-paxos: 其他一些 paxos 的改进，特别是 epaxos 最近几年得到较多的讨论和重视
• raft: 从 paxos 而来，类似于 multi-paxos，但是更为简单，容易理解，更为简单
• quorum: 英文翻译：法定人数，可以理解为多数派，大多数，超过半数的一个集合，更为精确的定义是 ”任意两个 quorum 必须有交集)
• state machine replication model: 复制状态机模型
• Crash Fault Tolerance： 故障容错（节点离线，网络延迟等）
• Byzantine Fault Tolerance： 拜占庭容错（节点离线，网络延迟，节点作恶）
• pbft: 实用拜占庭容错算法
• hotstuff: 也是一种拜占庭容错共识算法
• libraBFT: 基于 hotstuff

先认识名词，从整体上有一些概念，战略上藐视。

预先准备

本文重点分析 paxos (basic paxos) 算法。顺带会提及 multi-paxos 以及 raft 算法。

paxos 很难理解？争取听完本次分享，大家能彻底理解 paxos!

先忘记区块链，忘记 pbft，忘记 hotstuff.

单机？分布式？

为什么要有分布式系统？ 单机容易故障，无法保证服务高可用。

于是出现多副本模型，但多副本模型就存在两个问题：

• 如何确保复制是成功的？（高可用）
• 如何确保值是唯一的？（一致性）

诡异的死锁

事情是这样的，观察到某台机器上出现了卡死的现象，即没有刷新日志，cpu 使用也较低，怀疑是不是出现了死锁。

由于程序采用的是 master + worker 的模式，首先 gdb attach 观察 master 情况，发现 master 执行正常，没有 lock wait 相关的堆栈；然后 gdb attach 观察 worker 情况，结果发现 worker 堆栈上有 lock wait 的情况，果然是出现了死锁，但 worker 上的其他线程并没有发现在等待锁的情况。

根据堆栈，找到 worker 的代码，重新梳理了一下代码，检查了 std::mutex 相关的函数调用，并没有出现嵌套调用的情况，也没有出现递归调用的情况，和上面发现 worker 其他线程没有等待锁的情况相吻合。

说明 worker 的死锁，并非由于 worker 内部的多线程造成的。那么就很诡异了，不是 worker 内部死锁，难道是多进程死锁？

排查验证

重新又检查了 worker 各个线程的堆栈情况，发现确实只有一个线程出现 lock wait 相关的堆栈； 并且又检查了一下 master 进程内部的各个线程，堆栈也都正常。

那 worker 锁住的这个线程，到底是因为什么原因？梳理 worker 代码，找到 std::mutex 相关的函数调用，发现 master 调用的一个函数使用到了 std::mutex，但是该函数内部逻辑也较为简单，不会一直占用这把锁。

没有头绪，谷歌搜索了一些类似的问题，找到了一点端倪。主进程 fork 之后，仅会复制发起调用的线程，不会复制其他线程，如果某个线程占用了某个锁，但是到了子进程，该线程是蒸发掉的，子进程会拷贝这把锁，但是不知道谁能释放，最终死锁。

确实符合这个程序的行为，并且确实是多进程下子进程的死锁，而且找不到其他线程也在等待锁。

接下来，写一个 demo 验证一下，是否 fork 不会复制子线程，并且有可能造成死锁。

fork demo 验证

简单写一个 demo:

从何说起

说起 tcp 的连接过程，想必 “3次握手4次挥手”是大家广为熟知的知识，那么关于更细节更底层的连接过程也许就很少人能讲清楚了。

所以本文会先简单回顾一下 tcp 的 3次握手过程，然后重点聊一下 tcp accept 的过程，涉及到 tcp 半连接队列、全连接队列等的内容。

回顾一下

3 次握手

要了解 3 次握手的过程，可能需要先熟悉一下 tcp 协议的格式：

• tcp segment 的头部有两个 2字节的字段 source port 和 dest port，分别表示本机端口以及目标端口，在 tcp 传输层是没有 IP 的概念的，那是 IP 层 的概念，IP 层协议会在 IP 协议的头部加上 src ip 和 dest ip；
• 4 个字节的 seq，表示序列号，tcp 是可靠连接，不会乱序；
• 4 个字节的 ack，表示确认号，表示对接收到的上一个报文的确认，值为 seq + 1;
• 几个标志位：ACK,RST,SYN,FIN 这些是我们常用的，比较熟悉的。其中 ACK 简写为 “.”; RST 简写为 “R”; SYN 简写为 “S”; FIN 简写为 “F”;

注意： ack 和 ACK 是不一样的意思，一个是确认号，一个是标志位

前言

之前其实已经写过一篇博文： 迁移博客到香港虚拟空间，那为什么又要写这篇博客呢？

上次其实是把我的博客迁移到一个香港的虚拟空间里，但是不到半年的时间已经出现过 4 次宕机事件，每次持续时间 4~5 小时，阿里云 和 UpTimeRobot 的监控报警报了一大堆，邮箱都快塞满了。想着宕机就宕机吧，至少还能恢复，还能凑合用，结果呢，就在前几天当时购买虚拟空间的官网都 GG 了，管理员跑路了。。。

可能他没挣到钱吧，买一台服务器打算开很多共享的虚拟空间来卖，可能也只有我买了一个，因为我后来看了下我的博客同 IP 的网站就两个，好嘛，结果就跑路了。。。这里就不点名是哪一家了，八字开头的一个云。

好吧，言归正传，正好双 11，那就干脆直接买服务器吧，所以就购买了腾讯的一台轻量级云服务器，峰值 30Mbps，月流量 1024G，能满足我的需求，况且有了服务器，能做的事情就很多了。比如我还有其他的博客也可以解析到这里，比如可以定制化一些动态博客，比如可以使用自动化发布等。

那本文大致就记录下迁移的一些过程以及踩坑优化等：

• 服务器购买以及初始化
• 安装部署 nginx
• 部署博客源码
• 解析域名
• 设置 https 证书
• 绑定多个域名
• 使用 github actions 自动化部署博客（踩坑）
• https 性能优化

内存泄露？

观察到一台机器上的内存使用量在程序启动之后，持续增长，中间没有出现内存恢复。怀疑是不是出现了内存泄露的问题？

然后使用相关的内存分析工具进行了分析：

• gperf
• valgrind (massif)
• 手工标记内存分配释放

上述的分析结果均不能很肯定的得出是否内存泄露的结论。那么问题可能出现在哪里呢？

程序采用 c++ 编写，大量使用了智能指针以及 new/delete，难道内存没有成功释放？亦或是内存释放有什么条件？于是开始怀疑 free 是不是真的释放了内存？

测试

既然怀疑 free 是不是真的释放了内存，此处的释放，是指程序内存占用下降，内存归还给操作系统，那么直接写一个简单的例子进行验证一下。

attention:

测试前，先关闭 swap：

1
2
3
4
5
6

# swapoff -a

# free -h
              total        used        free      shared  buff/cache   available
Mem:           3.7G        2.5G        1.1G        8.8M         40M        959M
Swap:            0B          0B          0B

测试1

步骤如下：

1. 循环分配大量内存
2. block 程序，top 工具观察进程内存占用情况
3. 再循环释放所有分配的内存
4. block 程序，top 工具观察进程内存占用情况
5. 程序退出

缘起

上一篇博文 模仿nginx修改进程名 中提到了一种修改进程名的方法，就像 nginx 一样，给不同进程命名为 master 以及 worker 等。那么能不能把新进程名设置为空字符串呢？如果能，又会有哪些应用场景呢？

答案可能是能的，设置新进程的名字为空，通常用来隐藏进程，用于攻击或者反攻击。

prctl 函数

上一篇博文 模仿nginx修改进程名 文章末尾提到了 prctl 这个函数，它也可以用来修改进程名。

只不过如果单单使用 prctl 来修改进程名的话，使用 ps 或者 top 等工具看到的可能还是原来的名字。

源代码可以在我的 github 找到：

https://github.com/smaugx/setproctitle/blob/main/hidden_process/prctl_main.cc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <unistd.h>
#include <sys/prctl.h>

int main(int argc, char* argv[], char *envp[])
{
    const char *new_title = "prctl_new_name";
    prctl(PR_SET_NAME, new_title, NULL, NULL, NULL);
    while (true) {
        sleep(2);
    }
    return 0;
}

编译运行：

1
2

#  g++ prctl_main.cc   -o  prctl_main -std=c++11
# ./prctl_main

然后我们查看一下进程的名字：

1
2
3

# ps -ef |grep prctl
root     20758 12289  0 17:39 pts/3    00:00:00 ./prctl_main
root     20791 20422  0 17:39 pts/1    00:00:00 grep --color=auto prctl

可以看到 ps 看到的进程名依然是 prctl_main 而不是 prctl_new_name。那么 prctl 函数到底修改了哪里呢？ ps 命令又是从哪里读取的进程名呢？

nginx 进程名

使用 nginx 的过程中，我们经常看到 nginx 的进程名是不同的，如下：

1
2
3
4
5

$ ps -ef |grep nginx 
smaug    1183  1115  0 05:46 pts/2    00:00:00 grep --color=auto nginx
root     14201     1  0  2019 ?        00:00:00 nginx: master process ./sbin/nginx
nobody   28887 14201  0 Oct14 ?        00:00:00 nginx: worker process
nobody   28888 14201  0 Oct14 ?        00:00:00 nginx: worker process

可以看到 nginx 的进程名是不同的，那么它是怎么做到的呢？

argv[0]

首先来看一下 C 语言中的 main 函数的定义：

1

int main(int argc, char *argv[]);

这个应该大家都是比较熟悉的，argc 表示命令行参数个数， argv 保存了各个命令行参数的内容。其中 argv[0] 表示的是进程的名字，这就是修改进程名的关键点所在。

只需要修改 argv[0] 的值即可完成修改进程名。

hello world

下面以程序员经典入门代码为例说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// filename: hello_world_setproctitle.cc
// build: g++ hello_world_setproctitle.cc -o hello_world_setproctitle

#include <cstdio>
#include <cstring>

int main(int argc, char *argv[]) {
    printf("hello world\n");
    while (true) {
        // block here
        char c = getchar();
    }
    return 0;
}

编译运行：

1
2

g++ hello_world_setproctitle.cc -o hello_world_setproctitle
./hello_world_setproctitle

查看一下进程名：

1
2
3

# ps -ef |grep hello_world
root     26356 12289  0 14:17 pts/3    00:00:00 ./hello_world_setproctitle
root     26366 20422  0 14:18 pts/1    00:00:00 grep --color=auto hello_world

复习一下

上一篇博文 epoll原理深入分析 详细分析了 epoll 底层的实现原理，如果对 epoll 原理有模糊的建议先看一下这篇文章。那么本文就开始用 epoll 实现一个简单的 tcp server/client。

本文基于我的 github: https://github.com/smaugx/epoll_examples。

epoll 实现范式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# create listen socket
int listenfd = ::socket();

# bind to local port and ip
int r = ::bind();


# create epoll instance and get an epoll-fd
int epollfd = epoll_create(1);
 
# add listenfd to epoll instance
int r = epoll_ctl(..., listenfd, ...);


# begin epoll_wait, wait for ready socket

struct epoll_event* alive_events =  static_cast<epoll_event*>(calloc(kMaxEvents, sizeof(epoll_event)));

while (true) {
            int num = epoll_wait(epollfd, alive_events, kMaxEvents, kEpollWaitTime);
    
            for (int i = 0; i < num; ++i) {
            int fd = alive_events[i].data.fd;
            int events = alive_events[i].events;

            if ( (events & EPOLLERR) || (events & EPOLLHUP) ) {
                std::cout << "epoll_wait error!" << std::endl;
                // An error has occured on this fd, or the socket is not ready for reading (why were we notified then?).
                ::close(fd);
            } else  if (events & EPOLLRDHUP) {
                // Stream socket peer closed connection, or shut down writing half of connection.
                // more inportant, We still to handle disconnection when read()/recv() return 0 or -1 just to be sure.
                std::cout << "fd:" << fd << " closed EPOLLRDHUP!" << std::endl;
                // close fd and epoll will remove it
                ::close(fd);
            } else if ( events & EPOLLIN ) {
                std::cout << "epollin" << std::endl;
                if (fd == handle_) {
                    // listen fd coming connections
                    OnSocketAccept();
                } else {
                    // other fd read event coming, meaning data coming
                    OnSocketRead(fd);
                }
            } else if ( events & EPOLLOUT ) {
                std::cout << "epollout" << std::endl;
                // write event for fd (not including listen-fd), meaning send buffer is available for big files
                OnSocketWrite(fd);
            } else {
                std::cout << "unknow epoll event!" << std::endl;
            }
        } // end for (int i = 0; ...
    
}

epoll 编程基本是按照上面的范式进行的，这里要注意的是上面的反应的只是单进程或者单线程的情况。

如果涉及到多线程或者多进程，那么通常来说会在 listen() 创建完成之后，创建多线程或者多进程，然后再操作 epoll.

前言

上一篇博文 Epoll原理深入分析 在讲 accept 事件 的时候提到过 惊群效应，本文就分析一下惊群效应的原因以及解决方法。

惊群效应

什么是惊群

惊群效应就是多个进程（线程）阻塞等待同一件事情（资源）上，当事件发生（资源可用）时，操作系统可能会唤醒所有等待这个事件（资源）的进程（线程），但是最终却只有一个进程（线程）成功获取该事件（资源），而其他进程（线程）获取失败，只能重新阻塞等待事件（资源）可用，但是这就造成了额外的性能损失。这种现象就称为惊群效应。

如果细心的你可能会问，为什么操作系统要同时唤醒多个进程呢？只唤醒一个不行吗？这样不就没有这种性能损失了吗？

确实如此，操作系统也想只唤醒一个进程，但是它做不到啊，因为它也不知道该唤醒哪一个，只好把所有等待在这件事情（资源）的进程都一起唤醒了。

那有没有办法解决呢？当然有，我们后面再说。

惊群效应会造成多个进程白白唤醒而啥也做不了。那么唤醒进程损失了啥？这就涉及到进程上下文的概念。

惊群造成进程切换

进程上下文包括了进程的虚拟内存，栈，全局变量等用户空间的资源，还包括内核堆栈，寄存器等内核空间的状态。

所以进程上下文切换就首先需要保存用户态资源以及内核态资源，然后再去加载下一个进程，首先是加载了下一个进程的内核态，然后再去刷新进程的用户态空间。

然而 CPU 保存进程的用户态以及内核态资源，再去加载下一个进程的内核态和用户态是有代价的，也是耗时的，每次可能在几十纳秒到数微妙的时间，如果频繁发生进程切换，那么 CPU 将有大量的时间浪费在不断保存资源，加载资源，刷新资源等事情上，造成性能的浪费。

所以惊群效应会造成多个进程切换，造成性能损失。

惊群测试

为了直观的了解惊群效应是什么，我们采用 mux 项目当中的 echo_server 为例说明：

https://github.com/smaugx/mux/tree/master/demo/echo

编译命令详见项目说明文档。编译之后得到:

1

echo_server  echo_client

我们在 echo_server 上开启 8 个 epoll 线程，观察当有新连接过来时是否这 8 个线程（epoll） 都被唤醒了。

Epoll 的出现

想必能搜到这篇文章的，应该对 select/poll 有一些了解和认识，一般说 epoll 都会与 select/poll 进行一些对比，select、poll 和 epoll 都是一种 IO 多路复用机制。

select 的问题

select 的问题在于描述符的限制，能监控的文件描述符最大为 FD_SETSIZE，对于连接数很多的场景就无法满足；

另外select 还有一个问题是，每次调用 select 都需要从用户空间把描述符集合拷贝到内核空间，当描述符集合变大之后，用户空间和内核空间的内存拷贝会导致效率低下；

另外每次调用 select 都需要在内核线性遍历文件描述符的集合，当描述符增多，效率低下。

poll 的问题

由于 select 存在上面的问题，于是 poll 被提了出来，它能解决 select 对文件描述符数量有限制的问题，但是依然不能解决线性遍历以及用户空间和内核空间的低效数据拷贝问题。

epoll 是什么

select/poll 在互联网早期应该是没什么问题的，因为没有很多的互联网服务，也没有很多的客户端，但是随着互联网的发展，C10K 等问题的出现，select/poll 已经不能满足要求了，这个时候 epoll 上场了。

epoll 是 linux 内核 2.6 之后支持的，epoll 同 select/poll 一样，也是 IO 多路复用的一种机制，不过它避免了 select/poll 的缺点。下面详细讲解一下 epoll 反应堆的原理。

Epoll 反应堆

epoll 原理

要完整描述 epoll 的原理，需要涉及到内核、网卡、中断、软中断、协议栈、套接字等知识，本文尽量从比较全面的角度来分析 epoll 的原理。

上面其实讨论了 select/poll 几个缺点，针对这几个缺点，就需要解决以下几件事：

• 如何突破文件描述符数量的限制
• 如何避免用户态和内核态对文件描述符集合的拷贝
• socket 就绪后，如何避免线性遍历文件描述符集合