Muduo 多线程模型：一个 Sudoku 服务器演变

我不是女神ヾ 2022-10-01 00:43 136阅读 0赞

陈硕 (giantchen AT gmail)

blog.csdn.net/Solstice

Muduo 全系列文章列表： [http://blog.csdn.net/Solstice/category/779646.aspx][http_blog.csdn.net_Solstice_category_779646.aspx]

本文以一个 Sudoku Solver 为例，回顾了并发网络服务程序的多种设计方案，并介绍了使用 muduo 网络库编写多线程服务器的两种最常用手法。以往的例子展现了 Muduo 在编写单线程并发网络服务程序方面的能力与便捷性，今天我们看一看它在多线程方面的表现。

本文代码见：[http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/][http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku]

下载：[http://muduo.googlecode.com/files/muduo-0.2.5-alpha.tar.gz][http_muduo.googlecode.com_files_muduo-0.2.5-alpha.tar.gz]

# Sudoku Solver #

假设有这么一个网络编程任务：写一个求解数独的程序 (Sudoku Solver)，并把它做成一个网络服务。

Sudoku Solver 是我喜爱的网络编程例子，它曾经出现在《[分布式系统部署、监控与进程管理的几重境界][Link 1]》、《[Muduo 设计与实现之一：Buffer 类的设计][Muduo _Buffer]》、《[〈多线程服务器的适用场合〉例释与答疑][Link 2]》等文中，它也可以看成是 echo 服务的一个变种（《[谈一谈网络编程学习经验][Link 3]》把 echo 列为三大 TCP 网络编程案例之一）。

写这么一个程序在网络编程方面的难度不高，跟写 echo 服务差不多（从网络连接读入一个 Sudoku 题目，算出答案，再发回给客户），挑战在于怎样做才能发挥现在多核硬件的能力？在谈这个问题之前，让我们先写一个基本的单线程版。

### 协议 ###

一个简单的以 /r/n 分隔的文本行协议，使用 TCP 长连接，客户端在不需要服务时主动断开连接。

请求：\[id:\]〈81digits〉/r/n

响应：\[id:\]〈81digits〉/r/n 或者 \[id:\]NoSolution/r/n

其中\[id:\]表示可选的 id，用于区分先后的请求，以支持 Parallel Pipelining，响应中会回显请求中的 id。Parallel Pipelining 的意义见赖勇浩的《[以小见大——那些基于 protobuf 的五花八门的 RPC（2）][protobuf _ RPC_2] 》，或者见我写的《[分布式系统的工程化开发方法][Link 4]》第 54 页关于 out-of-order RPC 的介绍。

〈81digits〉是 Sudoku 的棋盘，9x9 个数字，未知数字以 0 表示。

如果 Sudoku 有解，那么响应是填满数字的棋盘；如果无解，则返回 NoSolution。

例子1：

请求：000000010400000000020000000000050407008000300001090000300400200050100000000806000/r/n

响应：693784512487512936125963874932651487568247391741398625319475268856129743274836159/r/n

例子2：

请求：a:000000010400000000020000000000050407008000300001090000300400200050100000000806000/r/n

响应：a:693784512487512936125963874932651487568247391741398625319475268856129743274836159/r/n

例子3：

请求：b:000000010400000000020000000000050407008000300001090000300400200050100000000806005/r/n

响应：b:NoSolution/r/n

基于这个文本协议，我们可以用 telnet 模拟客户端来测试 sudoku solver，不需要单独编写 sudoku client。SudokuSolver 的默认端口号是 9981，因为它有 9x9=81 个格子。

### 基本实现 ###

Sudoku 的求解算法见《[谈谈数独(Sudoku)][Sudoku]》一文，这不是本文的重点。假设我们已经有一个函数能求解 Sudoku，它的原型如下

string solveSudoku(const string& puzzle);

函数的输入是上文的"〈81digits〉"，输出是"〈81digits〉"或"NoSolution"。这个函数是个 pure function，同时也是线程安全的。

有了这个函数，我们以《[Muduo 网络编程示例之零：前言][Muduo]》中的 EchoServer 为蓝本，稍作修改就能得到 SudokuServer。这里只列出最关键的 onMessage() 函数，完整的代码见 [http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/server\_basic.cc][http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku_server_basic.cc] 。onMessage() 的主要功能是处理协议格式，并调用 solveSudoku() 求解问题。

// muduo/examples/sudoku/server_basic.cc
    
      const int kCells = 81;
    
      void onMessage(const TcpConnectionPtr& conn, Buffer* buf, Timestamp)
      {
        LOG_DEBUG << conn->name();
        size_t len = buf->readableBytes();
        while (len >= kCells + 2)
        {
          const char* crlf = buf->findCRLF();
          if (crlf)
          {
            string request(buf->peek(), crlf);
            string id;
            buf->retrieveUntil(crlf + 2);
            string::iterator colon = find(request.begin(), request.end(), ':');
            if (colon != request.end())
            {
              id.assign(request.begin(), colon);
              request.erase(request.begin(), colon+1);
            }
            if (request.size() == implicit_cast(kCells))
            {
              string result = solveSudoku(request);
              if (id.empty())
              {
                conn->send(result+"/r/n");
              }
              else
              {
                conn->send(id+":"+result+"/r/n");
              }
            }
            else
            {
              conn->send("Bad Request!/r/n");
              conn->shutdown();
            }
          }
          else
          {
            break;
          }
        }
      }

server\_basic.cc 是一个并发服务器，可以同时服务多个客户连接。但是它是单线程的，无法发挥多核硬件的能力。

Sudoku 是一个计算密集型的任务（见《[Muduo 设计与实现之一：Buffer 类的设计][Muduo _Buffer]》中关于其性能的分析），其瓶颈在 CPU。为了让这个单线程 server\_basic 程序充分利用 CPU 资源，一个简单的办法是在同一台机器上部署多个 server\_basic 进程，让每个进程占用不同的端口，比如在一台 8 核机器上部署 8 个 server\_basic 进程，分别占用 9981、9982、……、9988 端口。这样做其实是把难题推给了客户端，因为客户端(s)要自己做负载均衡。再想得远一点，在 8 个 server\_basic 前面部署一个 load balancer？似乎小题大做了。

能不能在一个端口上提供服务，并且又能发挥多核处理器的计算能力呢？当然可以，办法不止一种。

# 常见的并发网络服务程序设计方案 #

W. Richard Stevens 的 UNP2e 第 27 章 Client-Server Design Alternatives 介绍了十来种当时（90 年代末）流行的编写并发网络程序的方案。UNP3e 第 30 章，内容未变，还是这几种。以下简称 UNP CSDA 方案。UNP 这本书主要讲解阻塞式网络编程，在非阻塞方面着墨不多，仅有一章。正确使用 non-blocking IO 需要考虑的问题很多，不适宜直接调用 Sockets API，而需要一个功能完善的网络库支撑。

随着 2000 年前后第一次互联网浪潮的兴起，业界对高并发 http 服务器的强烈需求大大推动了这一领域的研究，目前高性能 httpd 普遍采用的是单线程 reactor 方式。另外一个说法是 IBM Lotus 使用 TCP 长连接协议，而把 Lotus 服务端移植到 Linux 的过程中 IBM 的工程师们大大提高了 Linux 内核在处理并发连接方面的可伸缩性，因为一个公司可能有上万人同时上线，连接到同一台跑着 Lotus server 的 Linux 服务器。

可伸缩网络编程这个领域其实近十年来没什么新东西，POSA2 已经作了相当全面的总结，另外以下几篇文章也值得参考。

[http://bulk.fefe.de/scalable-networking.pdf][http_bulk.fefe.de_scalable-networking.pdf]

[http://www.kegel.com/c10k.html][http_www.kegel.com_c10k.html]

[http://gee.cs.oswego.edu/dl/cpjslides/nio.pdf][http_gee.cs.oswego.edu_dl_cpjslides_nio.pdf]

下表是陈硕总结的 10 种常见方案。其中“多连接互通”指的是如果开发 chat 服务，多个客户连接之间是否能方便地交换数据（chat 也是《[谈一谈网络编程学习经验][Link 3]》中举的三大 TCP 网络编程案例之一）。对于 echo/http/sudoku 这类“连接相互独立”的服务程序，这个功能无足轻重，但是对于 chat 类服务至关重要。“顺序性”指的是在 http/sudoku 这类请求-响应服务中，如果客户连接顺序发送多个请求，那么计算得到的多个响应是否按相同的顺序发还给客户（这里指的是在自然条件下，不含刻意同步）。![reactor\_comparison][reactor_comparison]

UNP CSDA 方案归入 0~5。5 也是目前用得很多的单线程 reactor 方案，muduo 对此提供了很好的支持。6 和 7 其实不是实用的方案，只是作为过渡品。8 和 9 是本文重点介绍的方案，其实这两个方案已经在《[多线程服务器的常用编程模型][Link 5]》一文中提到过，只不过当时我还没有写 muduo，无法用具体的代码示例来说明。

在对比各方案之前，我们先看看基本的 micro benchmark 数据（前三项由 lmbench 测得）：

*  fork()+exit(): 160us
 *  pthread\_create()+pthread\_join(): 12us
 *  context switch : 1.5us
 *  sudoku resolve: 100us (根据题目难度不同，浮动范围 20~200us)

**方案 0**：这其实不是并发服务器，而是 iterative 服务器，因为它一次只能服务一个客户。代码见 UNP figure 1.9，UNP 以此为对比其他方案的基准点。这个方案不适合长连接，到是很适合 daytime 这种 write-only 服务。

**方案 1**：这是传统的 Unix 并发网络编程方案，UNP 称之为 child-per-client 或 fork()-per-client，另外也俗称 process-per-connection。这种方案适合并发连接数不大的情况。至今仍有一些网络服务程序用这种方式实现，比如 PostgreSQL 和 Perforce 的服务端。这种方案适合“计算响应的工作量远大于 fork() 的开销”这种情况，比如数据库服务器。这种方案适合长连接，但不太适合短连接，因为 fork() 开销大于求解 sudoku 的用时。

**方案 2**：这是传统的 Java 网络编程方案 thread-per-connection，在 Java 1.4 引入 NIO 之前，Java 网络服务程序多采用这种方案。它的初始化开销比方案 1 要小很多。这种方案的伸缩性受到线程数的限制，一两百个还行，几千个的话对操作系统的 scheduler 恐怕是个不小的负担。

**方案 3**：这是针对方案 1 的优化，UNP 详细分析了几种变化，包括对 accept 惊群问题的考虑。

**方案 4**：这是对方案 2 的优化，UNP 详细分析了它的几种变化。

以上几种方案都是阻塞式网络编程，程序（thread-of-control）通常阻塞在 read() 上，等待数据到达。但是 TCP 是个全双工协议，同时支持 read() 和 write() 操作，当一个线程/进程阻塞在 read() 上，但程序又想给这个 TCP 连接发数据，那该怎么办？比如说 echo client，既要从 stdin 读，又要从网络读，当程序正在阻塞地读网络的时候，如何处理键盘输入？又比如 proxy，既要把连接 a 收到的数据发给连接 b，又要把从连接 b 收到的数据发给连接 a，那么到底读哪个？（proxy 是《[谈一谈网络编程学习经验][Link 3]》中举的三大 TCP 网络编程案例之一。）

一种方法是用两个线程/进程，一个负责读，一个负责写。UNP 也在实现 echo client 时介绍了这种方案。另外见 Python Pinhole 的代码：[http://code.activestate.com/recipes/114642/][http_code.activestate.com_recipes_114642]

另一种方法是使用 IO multiplexing，也就是 select/poll/epoll/kqueue 这一系列的“多路选择器”，让一个 thread-of-control 能处理多个连接。“IO 复用”其实复用的不是 IO 连接，而是复用线程。使用 select/poll 几乎肯定要配合 non-blocking IO，而使用 non-blocking IO 肯定要使用应用层 buffer，原因见《[Muduo 设计与实现之一：Buffer 类的设计][Muduo _Buffer]》。这就不是一件轻松的事儿了，如果每个程序都去搞一套自己的 IO multiplexing 机制（本质是 event-driven 事件驱动），这是一种很大的浪费。感谢 Doug Schmidt 为我们总结出了 Reactor 模式，让 event-driven 网络编程有章可循。继而出现了一些通用的 reactor 框架/库，比如 libevent、muduo、Netty、twisted、POE 等等，有了这些库，我想基本不用去编写阻塞式的网络程序了（特殊情况除外，比如 proxy 流量限制）。

单线程 reactor 的程序结构是（图片取自 Doug Lea 的演讲）：

![reactor\_basic][reactor_basic]

**方案 5**：基本的单线程 reactor 方案，即前面的 server\_basic.cc 程序。本文以它作为对比其他方案的基准点。这种方案的优点是由网络库搞定数据收发，程序只关心业务逻辑；缺点在前面已经谈了：适合 IO 密集的应用，不太适合 CPU 密集的应用，因为较难发挥多核的威力。

**方案 6**：这是一个过渡方案，收到 Sudoku 请求之后，不在 reactor 线程计算，而是创建一个新线程去计算，以充分利用多核 CPU。这是非常初级的多线程应用，因为它为每个请求（而不是每个连接）创建了一个新线程。这个开销可以用线程池来避免，即方案 8。这个方案还有一个特点是 out-of-order，即同时创建多个线程去计算同一个连接上收到的多个请求，那么算出结果的次序是不确定的，可能第 2 个 Sudoku 比较简单，比第 1 个先算出结果。这也是为什么我们在一开始设计协议的时候使用了 id，以便客户端区分 response 对应的是哪个 request。

**方案 7**：为了让返回结果的顺序确定，我们可以为每个连接创建一个计算线程，每个连接上的请求固定发给同一个线程去算，先到先得。这也是一个过渡方案，因为并发连接数受限于线程数目，这个方案或许还不如直接使用阻塞 IO 的 thread-per-connection 方案2。方案 7 与方案 6 的另外一个区别是一个 client 的最大 CPU 占用率，在方案 6 中，一个 connection 上发来的一长串突发请求(burst requests) 可以占满全部 8 个 core；而在方案 7 中，由于每个连接上的请求固定由同一个线程处理，那么它最多占用 12.5% 的 CPU 资源。这两种方案各有优劣，取决于应用场景的需要，到底是公平性重要还是突发性能重要。这个区别在方案 8 和方案 9 中同样存在，需要根据应用来取舍。

**方案 8**：为了弥补方案 6 中为每个请求创建线程的缺陷，我们使用固定大小线程池，程序结构如下图。全部的 IO 工作都在一个 reactor 线程完成，而计算任务交给 thread pool。如果计算任务彼此独立，而且 IO 的压力不大，那么这种方案是非常适用的。Sudoku Solver 正好符合。代码见：[http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/server\_threadpool.cc][http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku_server_threadpool.cc] 后文给出了它与方案 9 的区别。

![reactor\_threadpool][reactor_threadpool]

如果 IO 的压力比较大，一个 reactor 忙不过来，可以试试 multiple reactors 的方案 9。

**方案 9**：这是 muduo 内置的多线程方案，也是 Netty 内置的多线程方案。这种方案的特点是 one loop per thread，有一个 main reactor 负责 accept 连接，然后把连接挂在某个 sub reactor 中（muduo 采用 round-robin 的方式来选择 sub reactor），这样该连接的所有操作都在那个 sub reactor 所处的线程中完成。多个连接可能被分派到多个线程中，以充分利用 CPU。Muduo 采用的是固定大小的 reactor pool，池子的大小通常根据 CPU 核数确定，也就是说线程数是固定的，这样程序的总体处理能力不会随连接数增加而下降。另外，由于一个连接完全由一个线程管理，那么请求的顺序性有保证，突发请求也不会占满全部 8 个核（如果需要优化突发请求，可以考虑方案 10）。这种方案把 IO 分派给多个线程，防止出现一个 reactor 的处理能力饱和。与方案 8 的线程池相比，方案 9 减少了进出 thread pool 的两次上下文切换。我认为这是一个适应性很强的多线程 IO 模型，因此把它作为 muduo 的默认线程模型。

![reactor\_multiple][reactor_multiple]

代码见：[http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/server\_multiloop.cc][http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku_server_multiloop.cc]

server\_multiloop.cc 与 server\_basic.cc 的区别很小，关键只有一行代码：server\_.setThreadNum(numThreads);

$ diff server_basic.cc server_multiloop.cc -up
    --- server_basic.cc     2011-06-15 13:40:59.000000000 +0800
    +++ server_multiloop.cc 2011-06-15 13:39:53.000000000 +0800
    @@ -21,19 +21,22 @@ using namespace muduo::net;
     class SudokuServer
     {
      public:
    -  SudokuServer(EventLoop* loop, const InetAddress& listenAddr)
    +  SudokuServer(EventLoop* loop, const InetAddress& listenAddr, int numThreads)
         : loop_(loop),
           server_(loop, listenAddr, "SudokuServer"),
    +      numThreads_(numThreads),
           startTime_(Timestamp::now())
       {
         server_.setConnectionCallback(
             boost::bind(&SudokuServer::onConnection, this, _1));
         server_.setMessageCallback(
             boost::bind(&SudokuServer::onMessage, this, _1, _2, _3));
    +    server_.setThreadNum(numThreads);
       }

方案 8 使用 thread pool 的代码与使用多 reactors 的方案 9 相比变化不大，只是把原来 onMessage() 中涉及计算和发回响应的部分抽出来做成一个函数，然后交给 ThreadPool 去计算。记住方案 8 有 out-of-order 的可能，客户端要根据 id 来匹配响应。

$ diff server_multiloop.cc server_threadpool.cc -up
    --- server_multiloop.cc 2011-06-15 13:39:53.000000000 +0800
    +++ server_threadpool.cc        2011-06-15 14:07:52.000000000 +0800
    @@ -31,12 +32,12 @@ class SudokuServer
             boost::bind(&SudokuServer::onConnection, this, _1));
         server_.setMessageCallback(
             boost::bind(&SudokuServer::onMessage, this, _1, _2, _3));
    -    server_.setThreadNum(numThreads);
       }
    
       void start()
       {
         LOG_INFO << "starting " << numThreads_ << " threads.";
    +    threadPool_.start(numThreads_);
         server_.start();
       }
    
    @@ -68,15 +69,7 @@ class SudokuServer
             }
             if (request.size() == implicit_cast(kCells))
             {
    -          string result = solveSudoku(request);
    -          if (id.empty())
    -          {
    -            conn->send(result+"/r/n");
    -          }
    -          else
    -          {
    -            conn->send(id+":"+result+"/r/n");
    -          }
    +          threadPool_.run(boost::bind(solve, conn, request, id));
             }
             else
             {
    @@ -91,8 +84,23 @@ class SudokuServer
         }
       }
    
    +  static void solve(const TcpConnectionPtr& conn, const string& request, const string& id)
    +  {
    +    LOG_DEBUG << conn->name();
    +    string result = solveSudoku(request);
    +    if (id.empty())
    +    {
    +      conn->send(result+"/r/n");
    +    }
    +    else
    +    {
    +      conn->send(id+":"+result+"/r/n");
    +    }
    +  }
    +
       EventLoop* loop_;
       TcpServer server_;
    +  ThreadPool threadPool_;
       int numThreads_;
       Timestamp startTime_;
     };

完整代码见：[http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/server\_threadpool.cc][http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku_server_threadpool.cc]

**方案 10**：把方案 8 和方案 9 混合，既使用多个 reactors 来处理 IO，又使用线程池来处理计算。这种方案适合既有突发 IO （利用多线程处理多个连接上的 IO），又有突发计算的应用（利用线程池把一个连接上的计算任务分配给多个线程去做）。

![reactor\_hybrid][reactor_hybrid]

这种其实方案看起来复杂，其实写起来很简单，只要把方案 8 的代码加一行 server\_.setThreadNum(numThreads); 就行，这里就不举例了。

# 结语 #

我在《[多线程服务器的常用编程模型][Link 5]》一文中说

总结起来，我推荐的多线程服务端编程模式为：event loop per thread + thread pool。

*  event loop 用作 non-blocking IO 和定时器。
 *  thread pool 用来做计算，具体可以是任务队列或消费者-生产者队列。

当时（2010年2月）我还说“以这种方式写服务器程序，需要一个优质的基于 Reactor 模式的网络库来支撑，我只用过in-house的产品，无从比较并推荐市面上常见的 C++ 网络库，抱歉。”

现在有了 muduo 网络库，我终于能够用具体的代码示例把思想完整地表达出来。

[http_blog.csdn.net_Solstice_category_779646.aspx]: http://blog.csdn.net/Solstice/category/779646.aspx
[http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku]: http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/
[http_muduo.googlecode.com_files_muduo-0.2.5-alpha.tar.gz]: http://muduo.googlecode.com/files/muduo-0.2.5-alpha.tar.gz
[Link 1]: http://blog.csdn.net/Solstice/archive/2011/05/09/6406944.aspx
[Muduo _Buffer]: http://blog.csdn.net/Solstice/archive/2011/04/17/6329080.aspx
[Link 2]: http://blog.csdn.net/Solstice/archive/2010/03/03/5343217.aspx
[Link 3]: http://blog.csdn.net/Solstice/archive/2011/06/06/6527585.aspx
[protobuf _ RPC_2]: http://blog.csdn.net/lanphaday/archive/2011/04/11/6316099.aspx
[Link 4]: http://blog.csdn.net/Solstice/archive/2010/10/19/5950190.aspx
[Sudoku]: http://blog.csdn.net/Solstice/archive/2008/02/15/2096209.aspx
[Muduo]: http://blog.csdn.net/Solstice/archive/2011/02/02/6171831.aspx
[http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku_server_basic.cc]: http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/server_basic.cc
[http_bulk.fefe.de_scalable-networking.pdf]: http://bulk.fefe.de/scalable-networking.pdf
[http_www.kegel.com_c10k.html]: http://www.kegel.com/c10k.html
[http_gee.cs.oswego.edu_dl_cpjslides_nio.pdf]: http://gee.cs.oswego.edu/dl/cpjslides/nio.pdf
[reactor_comparison]: /images/20220705/f5489c684baa4b1e95395c3614fb85f9.png
[Link 5]: http://blog.csdn.net/Solstice/archive/2010/02/12/5307710.aspx
[http_code.activestate.com_recipes_114642]: http://code.activestate.com/recipes/114642/
[reactor_basic]: /images/20220705/6bb98f229cb84a86a1826b758aee9071.png
[http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku_server_threadpool.cc]: http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/server_threadpool.cc
[reactor_threadpool]: /images/20220705/80cf31880c42499db9a9acb9d5cbcee8.png
[reactor_multiple]: /images/20220705/aff88d84b0a840ca947d4869e58ac8a7.png
[http_code.google.com_p_muduo_source_browse_trunk_examples_sudoku_server_multiloop.cc]: http://code.google.com/p/muduo/source/browse/trunk/examples/sudoku/server_multiloop.cc
[reactor_hybrid]: /images/20220705/51e0f844f3214c489915e987531af55e.png