内容

1. 红黑树

红黑树

在计算机科学中，红黑树是一种自平衡二叉搜索树。典型用途是实现关联数组(即map)。红黑树是从 4 阶 B 树（即2-3-4树）衍生出来的形式。

以下内容来自wiki：https://en.wikipedia.org/wiki/Red–black_tree
1972年，鲁道夫·拜耳发明了一种B 树的特殊 4 阶形式。这个 4 阶 B 树维护从根到叶的所有路径，节点数相同，从而创建完美平衡的树（然而，并不是二叉搜索树）。拜尔在他的论文中称呼他们为“对称二叉 B 树”（symmetric binary B-tree），后来这种 4 阶 B 树被称为2-3-4 树。

在 1978 年的论文《A Dichromatic Framework for Balanced Trees》中，Leonidas J. Guibas和Robert Sedgewick从 2-3-4 树中衍生出了红黑树。

之所以选择“红色”是因为它是作者在Xerox PARC工作时可用的彩色激光打印机打印出的最好看的颜色。Guibas 的另一个回应是，这是因为他们可以使用红色和黑色的笔来画树。

1993 年，Arne Andersson 提出右倾树的概念，以简化插入和删除操作。
1999 年， Chris Okasaki展示了如何使插入操作纯粹函数化（purely functional）。其平衡函数只需要处理 4 种不平衡情况和 1 种默认平​​衡情况。
原始算法需要处理 8 种不平衡情况，但 2001 年，Cormen 等人将其简化为 6 种不平衡情况。Sedgewick 通过实践证明，插入操作仅需46行Java代码即可实现。
2008 年，Sedgewick 基于 Arne Andersson 简化插入和删除操作的理念，提出了左倾红黑树。该结构初期允许节点拥有两个红色子节点（更接近2-3-4树特性），后期通过增加节点限制使其更贴近2-3树结构。改进后，Sedgewick将插入算法的代码量从46行精减至33行，显著提升了代码效率。

每个节点存储一个表示“颜色”（“红色”或“黑色”）的额外位，用于确保树在插入和删除期间保持平衡。

当树被修改时，新树被重新排列并“重新绘制”以恢复限制树在最坏情况下可能变得多么不平衡的着色属性。这些属性被设计成可以有效地执行这种重新排列和重新着色。

重新平衡并不完美，但保证在$O(\log n)$时间内搜索，其中$n$是条目数。插入和删除操作以及树的重新排列和重新着色也在$O(\log n)$时间内执行。

跟踪每个节点的颜色只需要每个节点的一位信息，因为只有两种颜色。该树不包含任何其他特定于它是红黑树的数据，因此它的内存占用几乎与经典（未着色）二叉搜索树的内存占用相同。在许多情况下，无需额外的内存成本即可存储额外的信息位。

红黑树与AVL的对比

实际上树节点的结构与AVL一模一样, 只是balance的状态值只有两个, 然后又在这个基础上, 对其进行了一些限制;

这样的好处就是, 对于红黑树的插入/删除操作, 在编写代码时, 只需考虑其两种状态即可, 这有利于开发实践; 而AVL需要考虑三种状态, 对于开发代码来说难度加大, 并且AVL树过于理想化, 导致旋转操作过多, 反而会影响性能;

AVL树本来想解决什么问题呢? 是为了防止不加限制的二叉搜索树在持续插入一些极端的值(依次插入有序的数)后, 搜索树的结构退化为了一个长度为n的链表, 因此查找性能也会退化;

但是, 对二叉搜索树的极度限制, 使其保持一个理想化的平衡又显得矫枉过正, 虽然插入数据时不用做过多的旋转(最多做2次旋转操作), 但是删除操作的时候, 可能会涉及到一长串的旋转处理($\log n$次), 这也会导致性能的退化;

于是, 红黑树的性质就像是同时克服了两者的缺点, 但是在高度平衡上, 做出了一些妥协, 但是这也是无伤大雅的, 红黑树节点的左右子树高度差, 长的长度不超过短的长度的2倍;

根据上表, 可以得出, 如果操作涉及到查询/插入较多, 优先选择AVL树, AVL是绝对平衡的树, 查询效率不会低于红黑树; 而插入效率两者等效;

如果操作涉及修改较多, 查询不多, 则选择红黑树; 除此之外, 红黑树在百万级数据或更大规模的数据场景中表现将会脱颖而出;

如果增删查三者操作都比较多, 红黑书综合性能要更优;

红黑树的性质

红黑树是每个节点都带有颜色属性的二叉查找树，颜色是红色或黑色。基于二叉查找树的强制要求，对于任何有效的红黑树我们增加了如下的额外要求：

1. 每个节点不是红色就是黑色。
2. 如果左右孩子是NIL, 则把此孩子看作黑色节点; 实际上这个NIL节点是哨兵节点, 可看作一个公共叶子节点;
3. 根节点是黑色。
4. 从每个叶子到根的所有路径上不能有两个连续的红色节点; 如此, 每个红色节点的两个子节点都是黑色。
5. 从任一节点到其每个叶子(可以包含NIL公共叶节点)的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

是性质4导致路径上不能有两个连续的红色节点确保了这个结果。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

思考: 为什么满足上面的性质，红黑树就能保证: 其最长路径中节点个数不会超过最短路径节点个数的两倍(红黑树节点的左右子树高度差, 长的长度不超过短的长度的2倍; )？

可以做个假设: 一个节点到其叶子节点1, 全部是黑色节点, 共10个; 而到其叶子节点2, 黑红节点交替, 共20个, 这种是满足性质5最大的极限了, 由于性质5的限制, 其最长路径中节点个数不会超过最短路径节点个数的两倍;

用途和好处

红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。不只在时间敏感的应用如实时应用（real time application）中有价值; 而且在提供最坏情况担保的其他数据结构中作为基础模板有价值, 例如，在计算几何中使用的很多数据结构都可以基于红黑树实现。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了$O(\log n)$的时间之外，红黑树的持久版本对每次插入或删除需要$O(\log n)$的空间。

红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。

红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

RB树的结构设计

红黑树相比于AVL树, 有一个伎俩, 就是设置了一个哨兵节点, 作为每个叶节点的左右孩子, 或者是: 不为叶节点, 但有一孩子指针为空时指向的一个节点, 这会使编程难度降低;

还可以引入一个作为整个红黑树的头节点, 双亲指针指向红黑树根节点, 左孩子指针指向红黑树最左节点(最小值), 右孩子指针指向红黑树最右节点(最大值), 根节点的双亲指针指向该头节点;

节点结构

1
2
3
4
5
6
7
8
9
10
11

typedef enum { RED = 0, BLACK = 1 } ColorType;
typedef int KeyType;
typedef struct rb_node
{
    rb_node * leftchild;
    rb_node * parent;
    rb_node * rightchild;
    ColorType color;
    KeyType key;
}rb_node, *RBTree;
static rb_node *NIL = BuyNode();

新建节点函数 - BuyNode

1
2
3
4
5
6
7
8
9
10

rb_node * BuyNode()
{
    rb_node * s = (rb_node*)malloc(sizeof(rb_node));
    if(nullptr == s) exit(1);
    memset(s, 0, sizeof(rb_node));
    s->leftchild = NIL;
    s->rightchild = NIL;
    s->color = RED;		//出生的红黑树节点默认为红色
    return s;
}

插入

建根函数

1
2
3
4
5
6
7

rb_node * MakeRoot(KeyType kx)
{
    rb_node * root = BuyNode();
    root->color = BLACK;		//默认根节点为黑色
    root->key = kx;
    return root;
}

Insert

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

bool Insert(rb_node *& tree, KeyType kx)
{
    if(tree == nullptr)
    {
        tree = MakeRoot(kx);
        return true;
    }
    rb_node * pa = nullptr;
    rb_node * p = tree;
    while(p != nullptr && p->key != kx)
    {
        pa = p;
        p = kx < p->key ? p->leftchild : p->rightchild;
    }
    if(p != nullptr && p->key == kx) return false;
    p = BuyNode();
    p->key = kx;
    p->parent = pa;
    if(kx < pa->key)
    {
        pa->leftchild = p;
    }
    else
    {
        pa->rightchild = p;
    }
    PassRBTree(tree, p);    //红黑树调整
    return true;
}

红黑树调整

左单旋 - RotateLeft

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

void RotateLeft(rb_node *& tree, rb_node * ptr)
{
    rb_node * newroot = ptr->rightchild;
    newroot->parent = ptr->parent;
    ptr->rightchild = newroot->leftchild;  //1 原根继承 轴节点的左孩子
    if(newroot->leftchild != nullptr)
    {
        newroot->leftchild->parent = ptr;  
    }
    
    newroot->leftchild = ptr;              //2 轴节点包揽原根
    //3 处理 原根父节点(或无父节点) 的左右孩子指针(或tree指针)
    if(ptr == tree)
    {
        tree = newroot;
    }
    else
    {
        if(ptr->parent->leftchild == ptr)
        {
            ptr->parent->leftchild = newroot;
        }
        else
        {
            ptr->parent->rightchild = newroot;
        }
    }
    
    ptr->parent = newroot;
}

右单旋 - RotateRight

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

void RotateRight(rb_node *& tree, rb_node * ptr)
{
    rb_node * newroot = ptr->leftchild;
    newroot->parent = ptr->parent;
    ptr->leftchild = newroot->rightchild;
    if(newroot->rightchild != nullptr)
    {
        newroot->rightchild->parent = ptr;
    }
    newroot->rightchild = ptr;
    if(ptr == tree)
    {
        tree = newroot;
    }
    else
    {
        if(ptr->parent->leftchild == ptr)
        {
            ptr->parent->leftchild = newroot;
        }
        else
        {
            ptr->parent->rightchild = newroot;
        }
    }
    ptr->parent = newroot;
}

调整函数

对红黑树修改时, 出现不平衡或颜色冲突, 对其调整使其平衡, 颜色正确的函数

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

void PassRBTree(rb_node *& tree, rb_node *p)
{
    rb_node * _X = nullptr;
    for(; p != tree && p->parent->color == RED; )
    {
        if(p->parent->parent->rightchild == p->parent)//说明在爷爷的右边插入
        {
            _X = p->parent->parent->leftchild;
            if(_X->color == RED)
            {
                _X->color = BLACK;
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;	//接下来循环看他爷爷的双亲是不是红
            }
            else //左单旋
            {
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                RotateLeft(tree, p->parent->parent);
            }
        }
        else
        {
            
        }
        
    }
    tree->color = BLACK;
}

加上双旋的情况

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

void PassRBTree(rb_node *& tree, rb_node *p)
{
    rb_node * _X = nullptr;
    for(; p != tree && p->parent->color == RED; )
    {
        if(p->parent->parent->rightchild == p->parent)//说明在爷爷的右边插入
        {
            _X = p->parent->parent->leftchild;
            if(_X->color == RED)
            {
                _X->color = BLACK;
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;	//接下来循环看他爷爷的双亲是不是红
            }
            else
            {
                if(p->parent->leftchild == p)//在父节点的左边, 需要双旋
                {
                    p = p->parent;       //关键一步, 偷换p, 以与下面语句串联
                    RotateRight(tree, p);//这是双旋第1步, 之后p调到其父节点的右边了
                }
                //不管上面的情况, 到这一步, p肯定在父节点的右边, 只需要左旋
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                RotateLeft(tree, p->parent->parent);
            }
        }
        else
        {
            _X = p->parent->parent->rightchild;
            if(_X->color == RED)
            {
                
            }
            else //要旋转
            {
                
            }
        }
        
    }
    tree->color = BLACK;
}

内容

1. 阻塞、非阻塞、同步、异步
2. 五种IO模型
3. 好的网路服务器设计思路
4. Reactor模型
5. select/poll/epoll、LT/ET模式对比
6. muduo网络库编程环境配置
7. muduo网络库的多线程模型
8. 基于muduo的服务器程序实例
9. muduo网络库提供的类
10. muduo网络库中TcpServer类中的回调类型
11. 代码示例ChatServer及运行测试结果

阻塞、非阻塞、同步、异步

网络IO阶段分为两个：数据准备和数据读写

• 数据准备–根据系统IO操作的就绪状态
  • 阻塞：调用IO方法的线程进入阻塞状态
  • 非阻塞：不会改变线程的状态，通过返回值判断
• 数据读写（IO层面的同步和异步）–根据应用程序和内核的交互方式
  • 同步：用户的recv完成了所有的动作，而且因此阻塞或者空转等待。数据是用户从TCP的接收缓冲区搬移的。
  • 异步：应用程序把任务交给操作系统，自己去做别的事情，操作系统处理完后，通知用户层“buf的数据已经准备好了”。可以通过sigio通知或者实现约定的回调方式通知

1
2
3
4
5
6
7
8
9
10

ssize_t recv(int sockfd, void* buf, size_t len, int flags);
int size = recv(sockfd, buf, 1024, 0);	//recv阻塞至sockfd上有数据准备好
//如果recv的属性设置为set non-block，则即使sockfd没有数据也会返回，cpu空转

/*
	返回值：
		size == -1; # 原因可能为1.系统内部错误; 2.当前处于非阻塞模式，无数据
			若 errno == EAGAIN 则说明 当前的错误是因为处于非阻塞模式。
		size == 0;	# 是由于远端的正常close而返回
*/

陈硕：（非）阻塞和异/同步IO的关系：在处理IO的时候，阻塞和非阻塞都是同步IO，只有使用了特殊的API才是异步IO。

即使epoll也是同步的IO，返回发生事件的event，读的时候需要调用recv，所以是同步IO。

• 业务层面的一个逻辑处理是同步还是异步？
  • 同步：A操作等待B操作完毕，得到返回值，继续处理
  • 异步：A操作告诉B操作它感兴趣的事件及通知方式，A操作继续执行自己的业务逻辑了，等B监听到相应。

总结

一个典型的网络IO接口调用，分为两个阶段，分别是“数据就绪”和“数据读写”，数据就绪阶
段分为阻塞和非阻塞，表现得结果就是，阻塞当前线程或是直接返回。

同步表示A向B请求调用一个网络IO接口时（或者调用某个业务逻辑API接口时），数据的读写都
是由请求方A自己来完成的（不管是阻塞还是非阻塞）；异步表示A向B请求调用一个网络IO接口
时（或者调用某个业务逻辑API接口时），向B传入请求的事件以及事件发生时通知的方式，A就
可以处理其它逻辑了，当B监听到事件处理完成后，会用事先约定好的通知方式，通知A处理结
果。

五种IO模型

• 阻塞 blocking
• 非阻塞 non-blocking
• IO复用 IO multiplexing
• 信号驱动 signal-driven
• 异步 asynchronous

好的网络服务器设计

在这个多核时代，服务端网络编程如何选择线程模型？libevent作者的观点：one loop(事件循环, 一般用IO复用作为事件分发器) per thread is usually a good model. 多线程服务端编程的问题就转换为如何设计一个高效且易用的event loop，然后每个线程run一个event loop就行了【即muduo库的思想】（当然线程间的同步、互斥少不了，还有其他的耗时事件需要起另外的线程来做）。

• event loop是non-blocking网络编程的核心，在现实生活中，non-blocking几乎总是和IO-multiplexing一起使用，原因有二：
  • 不要单独使用非阻塞IO：没有人真的会用轮询(busy-polling)来检查某个non-blocking IO操作是否完成，太浪费CPU资源
  • 不要单独使用IO复用（比如阻塞的IO复用）：IO multiplexing一般不能和blocking IO用在一起，因为blocking IO中read()/write()/accept()/connect()都有可能阻塞当前线程，这样线程就没办法处理其他socket上的IO操作了
  • 所以当我们提到non-blocking的时候，实际上指的是non-blocking + IO multiplexing，单用其中任何一个都没有办法很好地实现功能。
  • 结论：epoll + 非阻塞IO + 线程池(线程的数目一般对应电脑的CPU核数)

nginx使用的是epoll + fork，是不是不如epoll + pthread？

nginx采用了epoll+fork模型作为网络模块的架构设计，实现了简单好用的负载算法，使各个fork网络进程不会忙的越忙、闲的越闲，并且通过一把乐观锁解决了该模型导致的服务器惊群现象，功能十分强大。

Reactor模型

muduo库和libevent库都是“基于事件驱动的Reactor模型”。

Wikipedia给出的Reactor Design Pattern的解释：

The Reactor design pattern is an event handling pattern for handling service requests delivered concurrently to a service handler by one or more inputs. The service handler then demultiplexes the incoming requests and dispatchers them synchronously to the associated request handlers.

Google Translate:

Reactor 设计模式是一种事件处理模式，用于处理通过一个或多个输入同时交付给服务处理程序的服务请求。 然后，服务处理程序对传入的请求进行多路分解，并将它们同步分配给相关联的请求处理程序。

• Reactor四个重要组件
  • Event事件
  • Reactor反应堆
  • Demultiplex事件分发器
  • EventHandler事件处理器

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

%%时序图例子
sequenceDiagram
	participant Event
	participant Reactor
	participant Demultiplex
	participant EventHandler
	Event ->> Reactor: 注册Event和Handler
	loop 事件集合
		Reactor -> Reactor:Event集合
	end
	Reactor ->> Demultiplex: 向Epoll add/mod/del Event
	Reactor ->> Demultiplex: 启动反应堆
    loop 事件分发器
    	Demultiplex -> Demultiplex:开启事件循环epoll_wait
    end
    Demultiplex ->> Reactor: 返回发生事件的Event
    Reactor ->> EventHandler: 调用Event对应的事件处理器EventHandler

epoll

select和poll的缺点

• select的缺点：
  • 单个进程能够监视的文件描述符的数量存在最大限制，通常是1024（可更改：#define __FD_SETSIZE 1024），但由于select采用轮询的方式扫描文件描述符，则文件描述符数量越多，性能就越差。
  • 内核/用户空间内存拷贝问题，select需要复制大量的句柄数据结构，产生巨大的开销
  • select返回的是含有整个句柄的数组，应用程序需要遍历整个数组才能发现哪些句柄发生了事件
  • select的触发方式是水平触发，应用程序如果没有完成对一个已经就绪的文件描述符进行IO操作，那么之后每次select调用还是会将这些文件描述符通知进程（意思就是一件事情处理得太拖沓，拖延好几次才完成，影响效率）。其实epoll的LT模式也是这样。但是ET模式效率不一定比LT好。
• poll
  • 相比select模型，poll使用链表保存文件描述符，因此没有了监视文件数量的限制，但其他三个缺点依然存在。

以select模型为例，假设我们的服务器需要支持100万的并发连接，则在__FD_SETSIZE 为1024的情况下，则我们至少需要开辟1k个进程才能实现100万的并发连接。除了进程间上下文切换的时间消耗外，从内核/用户空间大量的句柄结构内存拷贝、数组轮询等，是系统难以承受的。因此，基于select模型的服务器程序，要达到100万级别的并发访问，是一个很难完成的任务。

epoll原理及优势

epoll的实现机制与select/poll机制完全不同。

epoll通过在Linux内核中申请一个简易的文件系统，提升了效率。

文件系统一般用什么数据结构实现——B+树，磁盘IO消耗低、效率很高。

把原先的select/poll调用分成以下3个部分：

1. 调用epoll_create()建立一个epoll对象（在epoll文件系统中为这个句柄对象分配资源）

   • epoll_create在内核上创建的eventpoll结构如下：

     1 2 3 4 5 6 7 8 9

     struct eventpoll { //... /* 红黑树的根节点，这棵树中存储着所有添加到epoll中的需要监控的事件*/ struct rb_root rbr; /* 双链表中则存放着将要通过epoll_wait返回给用户的满足条件的事件*/ struct list_head rdlist; //... }

2. 调用epoll_ctl向epoll对象中添加这100万个连接的套接字

3. 调用epoll_wait收集发生的事件的fd资源

如此一来，要实现上面说的场景，只需在进程启动时建立一个epoll对象，然后在需要时像这个epoll对象中添加或者删除事件。同时epoll_wait时，并没有向操作系统复制这100万个连接的句柄数据，内核也不需要去遍历全部的事件。

• LT模式，muduo采用的是LT模式
  • 特点：内核数据没被读完，就会一直上报数据
  • 不会丢失数据或者消息
    • 应用没有读取完数据，内核会不断上报
  • 低延迟处理
    • 每次读数据只需要一次系统调用，照顾了多个连接的公平性，不会因为某个连接上的数据量过大而影响其他连接处理消息
  • 跨平台处理
    • 像select一样可以跨平台使用
• ET模式
  • 特点：内核数据只上报一次，效率相对较高

muduo网络库编程准备

开发环境

1. ubuntu linux
2. 安装json开发库
3. 安装boost + muduo网络库开发环境muduo库源码编译安装
4. 安装redis环境
5. 安装mysql数据库环境
6. 安装nginx
7. 安装cmake环境

• 配置远程开发环境
  • windows+vscode配置远程linux开发环境
    1. linux系统运行sshd服务
    2. 在vscode上安装Remote Development插件，其依赖插件会自动安装
  • VS环境创建远程linux跨平台项目
  • vscode在linux环境下直接开发

安装流程

1. muduo库是基于boost开发的，所以需要先在Linux平台上安装boost库。需要注意，boost库的编译需要安装gcc、make等基础工具才行。环境：Ubuntu 20.04.6，太新的Ubuntu由于无法兼容旧代码，不能安装。

   1. tar -xzvf boost_1_69_0.tar.gz解压

   2. 执行./bootstrap.sh：也可以在后面加--prefix=/usr/local指定安装目录（默认路径）

   3. ./b2安装（如果Linux系统没有安装g++编译器，需要先安装）

   4. 最后，再把上面的boost库头文件和lib库文件安装在默认的Linux系统头文件和库文件的搜索路径下，运行下面命令（因为要给/usr目录下拷贝文件，需要先进入root用户）：sudo ./b2 install

   5. sudo ldconfig​更新链接库缓存

   6. 验证安装boost是否成功，通过下面的代码验证一下：

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

      #include <iostream> #include <boost/bind.hpp> #include <string> using namespace std; class Hello { public: void say(string name) { cout << name << " say: hello world!" << endl; } }; int main() { Hello h; auto func = boost::bind(&Hello::say, &h, "zhang san"); func(); return 0; }//运行结果zhang san say: hello world!

2. unzip muduo-master.zip
3. cd muduo-master
4. muduo库源码编译会编译很多unit_test测试用例代码，编译耗时长，我们用不到，vim编辑上面源码目录里面的CMakeLists.txt文件，如下修改：

7. ./build.sh源码编译构建程序，运行该程序（注意：muduo是用cmake来构建的，需要先安装cmake，ubuntu下sudo apt-get install cmake就可以，redhat或者centos可以从yum仓库安装）
8. 编译完成后，输入./build.sh install命令进行muduo库安装。但这个./build.sh install实际上把muduo的头文件和lib库文件放到了muduo-master同级目录下的build目录下的release-install-cpp11文件夹下面了

1
2
3
4
5
6
7
8

root@tony-virtual-machine:/home/tony/package# ls
build  muduo-master  muduo-master.zip
root@tony-virtual-machine:/home/tony/package# cd build/
root@tony-virtual-machine:/home/tony/package/build# ls
release-cpp11  release-install-cpp11
root@tony-virtual-machine:/home/tony/package/build# cd release-install-cpp11/
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11# ls
include  lib

所以上面的install命令并没有把它们拷贝到系统路径下，导致我们每次编译程序都需要指定muduo库的头文件和库文件路径，很麻烦，所以我们选择直接把inlcude（头文件）和lib（库文件）目录下的文件拷贝到系统目录下（需要sudo）：

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

root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11# ls
include  lib
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11# cd include/
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11/include# ls
muduo
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11/include# mv muduo/ /usr/include/
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11/include# cd ..
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11# ls
include  lib
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11# cd lib/
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11/lib# ls
libmuduo_base.a  libmuduo_http.a  libmuduo_inspect.a  libmuduo_net.a
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11/lib# mv * /usr/local/lib/
root@tony-virtual-machine:/home/tony/package/build/release-install-cpp11/lib# 

拷贝完成以后使用muduo库编写C++网络程序，不用在指定头文件和lib库文件路径信息了，因为g++会自动从/usr/include和/usr/local/lib路径下寻找所需要的文件。

测试代码

测试muduo是否能够正常使用，编写一个简单的echo回显服务器，如下：

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
55
56
57
58
59
60
61
62
63
64
65
66
67

#include <muduo/net/TcpServer.h>
#include <muduo/base/Logging.h>
#include <boost/bind.hpp>
#include <muduo/net/EventLoop.h>

// 使用muduo开发回显服务器
class EchoServer
{
 public:
  EchoServer(muduo::net::EventLoop* loop,
             const muduo::net::InetAddress& listenAddr);

  void start(); 

 private:
  void onConnection(const muduo::net::TcpConnectionPtr& conn);

  void onMessage(const muduo::net::TcpConnectionPtr& conn,
                 muduo::net::Buffer* buf,
                 muduo::Timestamp time);

  muduo::net::TcpServer server_;
};

EchoServer::EchoServer(muduo::net::EventLoop* loop,
                       const muduo::net::InetAddress& listenAddr)
  : server_(loop, listenAddr, "EchoServer")
{
  server_.setConnectionCallback(
      boost::bind(&EchoServer::onConnection, this, _1));
  server_.setMessageCallback(
      boost::bind(&EchoServer::onMessage, this, _1, _2, _3));
}

void EchoServer::start()
{
  server_.start();
}

void EchoServer::onConnection(const muduo::net::TcpConnectionPtr& conn)
{
  LOG_INFO << "EchoServer - " << conn->peerAddress().toIpPort() << " -> "
           << conn->localAddress().toIpPort() << " is "
           << (conn->connected() ? "UP" : "DOWN");
}

void EchoServer::onMessage(const muduo::net::TcpConnectionPtr& conn,
                           muduo::net::Buffer* buf,
                           muduo::Timestamp time)
{
  // 接收到所有的消息，然后回显
  muduo::string msg(buf->retrieveAllAsString());
  LOG_INFO << conn->name() << " echo " << msg.size() << " bytes, "
           << "data received at " << time.toString();
  conn->send(msg);
}


int main()
{
  LOG_INFO << "pid = " << getpid();
  muduo::net::EventLoop loop;
  muduo::net::InetAddress listenAddr(8888);
  EchoServer server(&loop, listenAddr);
  server.start();
  loop.loop();
}

使用g++进行编译，注意链接muduo和pthread的库文件，编译命令如下：

1

g++ main.cpp -lmuduo_net -lmuduo_base -lpthread -std=c++11

编译链接完成，生成a.out可执行程序，上面的echo服务器监听8888端口，运行上面的a.out回显服务器如下：

1
2

root@tony-virtual-machine:/home/tony/code# ./a.out 
20190404 08:00:15.254790Z 42660 INFO  pid = 42660 - main.cpp:61

等待客户端连接，可以打开一个新的shell命令行用netcat命令模拟客户端连接echo服务器进行功能测试，命令如下：

1
2
3

tony@tony-virtual-machine:~$ echo "hello world" | nc localhost 8888

hello world #客户端数据回显

客户端数据回显正确，看看服务器接日志信息打印如下：

1
2
3
4
5

root@tony-virtual-machine:/home/tony/code# ./a.out 
20190404 08:00:15.254790Z 42660 INFO  pid = 42660 - main.cpp:61
20190404 08:00:59.438626Z 42660 INFO  TcpServer::newConnection [EchoServer] - new connection [EchoServer-0.0.0.0:8888#1] from 127.0.0.1:33480 - TcpServer.cc:80
20190404 08:00:59.438707Z 42660 INFO  EchoServer - 127.0.0.1:33480 -> 127.0.0.1:8888 is UP - main.cpp:42
20190404 08:00:59.438812Z 42660 INFO  EchoServer-0.0.0.0:8888#1 echo 12 bytes, data received at 1554364859.438723 - main.cpp:53

到此，muduo安装成功，能够正常进行C++网络程序开发！

配置链接库、头文件

muduo库的使用需要链接lib库文件，一般为.so文件。一般.so文件都在/usr/lib或/usr/local/lib路径下。

编译链接使用muduo库的程序需要加后缀-l ...

1
2
3
4

# /usr/lib or /usr/local/lib
# 3 lib: libmuduo_base.so; libmuduo_net.so; libpthread.so
-lmuduo_net -lmuduo_base -lpthread
# 注意顺序，net需要写在前面，因为net依赖base；base写中间，因为依赖phtread

如何在vscode配置这三个库？

vscode中按F1键，搜索edit configurations，将会打开：

项目目录下的.vscode文件夹下的c_cpp_properties.json

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

{
    "configurations": [
        {
            "name": "Linux",
            "includePath": [
                "${workspaceFolder}/**"
            ],
            "defines": [],
            "compilerPath": "/usr/bin/gcc",
            "cStandard": "c17",
            "cppStandard": "c++20",
            "intelliSenseMode": "linux-gcc-x64"
        }
    ],
    "version": 4
}

build构建项目的快捷键是ctrl+shift+B键，但若你没有配置过build流程，将会弹出选项让你配置。实际上就是让你配置.vscode下的tasks.json。

除了上面这两个json文件，vscode下的cpp项目中还有一个json配置文件是launch.json，是关于调试的配置信息。

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

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558
    // for the documentation about the tasks.json format
    "version": "2.0.0",
    "tasks": [
        {
            "type": "shell",
            "label": "build",
            "command": "/usr/bin/g++",
            "args": [
                "-g",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}",
            ],
            "options": {
                "cwd": "/usr/bin"
            },
            "problemMatcher": [
                "$gcc"
            ],
            "group": "build"
        }
    ]
}

其中，args键就是build时编译链接命令后面加的参数。

我们在此使用muduo库，若想用vscode来一键build，则可以在args里加上三个参数。

1
2
3
4
5
6
7
8
9
10

{
          // ...
	"args": [
              // ...
              "-lmuduo_net",
              "-lmuduo_base",
              "-lpthread"
          ],
          // ...
      }

如果配置文件写好了，则就可以在vscode下一键build。

muduo网络库的多线程模型

• 网络服务器编程常用模型
  1. accept + read/write : 不是并发服务器
  2. accpet + fork (process-pre-connection) : 适合并发连接数不大，计算任务工作量大于fork的开销
  3. accept + thread (thread-pre-connection) : 比方案2的开销小了一点，但是并发造成线程堆积过多
  4. reactors in threads (one loop per thread) : 是muduo的网络设计。有一个main reactor负载accept连接，然后把连接分发到某个sub reactor(采用round-robin的方式来选择sub reactor)，该连接的操作都在sub reactor所处的线程中完成。多个连接可能被分派到多个线程中，以充分利用CPU。
  5. reactors in process (one loop pre process) : 是nginx服务器的网络模块设计，基于进程设计，采用多个Reactors充当I/O进程和工作进程，通过一把accept锁完美解决多个Reactors的“惊群现象”。
• muduo底层的模型

muduo的网络设计：reactors in threads - one loop per thread.

方案的特点是"one loop per thread"，有一个main reactor负责accept连接，然后把连接分发到某个sub reactor（轮询方式选择）。该连接的所有操作都在该reactor所处的线程中完成。多个连接可能被分派到多个线程中，以充分利用CPU。如果有过多的耗费CPU IO的计算任务，可以设置一个专门处理耗时计算任务的线程负责处理该类任务。

reactor poll的大小根据CPU核心的数目确定。

1
2

//设置EventLoop的线程个数，底层通过EventLoopThreadPool线程池管理线程类EventLoopThread
_server.setThreadNum(10);

基于muduo的服务器程序

muduo网络库提供的类

1. TcpServer：用于编写服务器程序的。
2. TcpClient：用于编写客户端程序的。

这两个类，实际上就是把epoll+线程池封装在一起了。好处就是把网络IO代码和业务代码区分开，使程序员可以专心开发业务代码。

业务代码关注的两件事情：

1. 用户的连接与断开
2. 用户的可读写事件

但这两件事情，如果我们使用了网络库，则如何监听、何时发生事件全都由网络库给程序员上报。

muduo库中TcpServer类中重要的回调属性

1
2
3
4
5
6
7
8

void setConnectionCallback(const ConnectionCallback& cb)
{
    connectionCallback_ = cb;
}
void setMessageCallback(const MessageCallback & cb)
{
    messageCallback_ = cb;
}

1
2

typedef std::function<void (const TcpConnectionPtr&)> ConnectionCallback;
typedef std::function<void (const TcpConnectionPtr&, Buffer*, Timestamp)> MessageCallback;

代码示例 - ChatServer

需要包含的头文件

1
2
3
4
5

#include<muduo/net/TcpServer.h>
#include<muduo/net/EventLoop.h>
#include<functional>
using namespace std::placeholders;
#include<iostream>

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

class ChatServer
{
public:
    /* 在其中：
     * 1、类内构造TcpServer，初始化EventLoop指针
     * 2、给TcpServer注册用户连接的创建、连接的断开回调
     * 3、给TcpServer注册用户读写事件回调
     * 4、设置TcpServer的线程数量，muduo库会自己分配IO线程和工作线程
     */
    ChatServer(muduo::net::EventLoop* loop, //事件循环
               const muduo::net::InetAddress& listenAddr,   //IP+port
               const std::string& nameArg)  //服务器的名字
        : m_server(loop, listenAddr, nameArg),
          m_loop(loop)
    {
        m_server.setConnectionCallback(std::bind(&ChatServer::onConnection, this, _1));
        m_server.setMessageCallback(std::bind(&ChatServer::onMessage, this, _1, _2, _3));
        m_server.setThreadNum(4);
    }
    //开启事件循环
    void start()
    {
        m_server.start();
    }
private:
    //当发生用户的连接创建、连接断开事件后，调用函数
    void onConnection(const muduo::net::TcpConnectionPtr &conn)
    {

    }
    //读写事件发生后，调用函数
    void onMessage(const muduo::net::TcpConnectionPtr &conn,
                   muduo::net::Buffer * buffer,
                   muduo::Timestamp time)
    {

    }
private:
    muduo::net::TcpServer m_server;
    muduo::net::EventLoop * m_loop;
};

编写回调函数

OnConnection和OnMessage

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

//当发生用户的连接创建、连接断开事件后，调用函数
void onConnection(const muduo::net::TcpConnectionPtr &conn)
{
    std::cout << conn->peerAddress().toIpPort() << " -> " <<
        conn->localAddress().toIpPort() << " state:";
    if(conn->connected())
    {
        std::cout << " online.";
    }
    else
    {
        std::cout << " offline."
        conn->shutdown();
        //_loop->quit();
    }
    std::cout << std::endl;
}
//读写事件发生后，调用函数
void onMessage(const muduo::net::TcpConnectionPtr &conn,
               muduo::net::Buffer * buffer,
               muduo::Timestamp time)
{
    std::string buf = buffer->retrieveAllAsString();
    std::cout << "recv data: " << buf << " time: " << time.toString() << std::endl;
    conn->send(buf);
}

主函数

1
2
3
4
5
6
7
8

int main()
{
    muduo::net::EventLoop loop; //相当于创建了一个epoll
    muduo::net::InetAddress addr("127.0.0.1", 6000);
    ChatServer chatserver(&loop, addr, "mychat");
    chatserver.start();
    loop.loop();    //相当于调用epoll_wait，以阻塞方式等待新用户连接事件、已连接用户的读写事件
}

测试服务器程序

首先，编译链接需要加后缀-lmuduo_net -lmuduo_base -lpthread。

编译链接后，执行程序。

1

./chatserver

可以通过telnet连接服务器。

1

telnet 127.0.0.1 6000

运行结果

1
2
3
4
5
6
7
8
9

xcg@ubuntu:~$ telnet 127.0.0.1 6000
Trying 127.0.0.1...
Connected to 127.0.0.1.
Escape character is '^]'.
hello!					#客户端输入显示到屏幕上的，发送给服务器的内容
hello!					#收到的服务器复制后回发的一模一样的内容。
^]
telnet> quit
Connection closed.

1
2
3
4
5
6
7

xcg@ubuntu:~/muduo-0528$ ./chatserver 
20220528 08:10:49.554317Z  8116 INFO  TcpServer::newConnection [mychat] - new connection [mychat-127.0.0.1:6000#1] from 127.0.0.1:60338 - TcpServer.cc:80
127.0.0.1:60338 -> 127.0.0.1:6000 state: online.
recv data: hello!
 time: 1653725453.563665
127.0.0.1:60338 -> 127.0.0.1:6000 state: offline.
20220528 08:10:56.835295Z  8116 INFO  TcpServer::removeConnectionInLoop [mychat] - connection mychat-127.0.0.1:6000#1 - TcpServer.cc:109