6.6.1 数独求解服务器

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

Sudoku Solver 是我喜爱的网络编程(www.cppentry.com)例子，它曾经出现在“分布式系统部署、监控与进程管理的几重境界”（§9.8）、“muduo Buffer 类的设计与使用”（§7.4）、“‘多线程服务器的适用场合’例释与答疑”（§3.6）等处，它也可以看成是echo 服务的一个变种（附录A “谈一谈网络编程(www.cppentry.com)学习经验”把echo 列为三大TCP 网络编程(www.cppentry.com)案例之一）。

写这么一个程序在网络编程(www.cppentry.com)方面的难度不高，跟写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）》26，或者见我写的《分布式系统的工程化开发方法》27 第54 页关于out-of-order RPC 的介绍。

<81digits> 是Sudoku 的棋盘，9  9 个数字，从左上角到右下角按行扫描，未知数字以0 表示。如果Sudoku 有解，那么响应是填满数字的棋盘；如果无解，则返回NoSolution。

例子1 请求：

000000010400000000020000000000050407008000300001090000300400200050100000000806000\r\n 

693784512487512936125963874932651487568247391741398625319475268856129743274836159\r\n 

a:000000010400000000020000000000050407008000300001090000300400200050100000000806000\r\n 

a:693784512487512936125963874932651487568247391741398625319475268856129743274836159\r\n 

b:000000010400000000020000000000050407008000300001090000300400200050100000000806005\r\n 

响应：b:NoSolution\r\n

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

基本实现

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

string solveSudoku(const string& puzzle); 

函数的输入是上文的“<81digits>”，输出是“<81digits>”或“NoSolution”。这个函数是个pure function，同时也是线程安全的。

有了这个函数，我们以§6.4.2 “echo 服务的实现”中出现的EchoServer 为蓝本，稍加修改就能得到SudokuServer。这里只列出最关键的onMessage() 函数，完整的代码见examples/sudoku/server_basic.cc。onMessage() 的主要功能是处理协议格式，并调用solveSudoku() 求解问题。这个函数应该能正确处理TCP 分包。

const int kCells = 81; // 81 个格子  
void onMessage(const TcpConnectionPtr& conn, Buffer* buf, Timestamp)  
{  
LOG_DEBUG << conn->name();  
size_t len = buf->readableBytes();  
while (len >= kCells + 2) // 反复读取数据，2 为回车换行字符  
{  
const char* crlf = buf->findCRLF();  
if (crlf) // 如果找到了一条完整的请求  
{  
string request(buf->peek(), crlf); // 取出请求  
string id;  
buf->retrieveUntil(crlf + 2); // retrieve 已读取的数据  
string::iterator colon = find(request.begin(), request.end(), ':');  
if (colon != request.end()) // 如果找到了id 部分  
{  
id.assign(request.begin(), colon);  
request.erase(request.begin(), colon+1);  
}  
if (request.size() == implicit_cast<size_t>(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;  
}  
}  
}  
examples/sudoku/server_basic.cc 

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

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

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