前言
在技术面试中，我们时常注意到一个现象：许多候选人的简历上赫然写着'熟悉高并发编程'，然而一旦深入追问，却发现不少人对此的理解仍停留在表面。
高并发我理解主要分为两大部分，一部分是分布式系统架构的设计，另外一部分就是系统的实现/编码部分。正是基于这一观察，本文将聚焦第二部分，高并发系统中的关键优化策略，通过解析帮助读者建立更扎实的知识体系。
本文主要介绍以下几个部分：
1：空间换时间
2：并行/异步处理
3：预先/延后处理
4：缓存/批量合并
5：算法和数据结构
6：生产者与消费者
7：锁的使用
空间换时间
比如为了能快速查找定位一些数据，我们会设计一些hash类的数据结构，提高查找效率。
广告系统中，数万的广告正排表，通常会通过id去获取对应的对象。
优化前，使用本质为数组的vector对象，占用内存大小比较小，但是查找时间复杂度为O(n)：
Creative*Find(std::vector<Creative*>& arr,int id){
for(auto it : arr){
if(it->id_ == id){
return it;
}
}
returnnullptr;
}
优化后，使用hash实现的unordered_map，占用空间比较大，但是查找时间复杂度为O(1)
Creative*Find(std::unordered_map<int, Creative*>& mp,int id){
auto it = mp.find(id);
if(it != mp.end()){
return it->second;
}
returnnullptr;
}
比如需要访问一些存储在磁盘上的数据，可以预先加载放到内存里面，这样就可以快速返回了，因为磁盘的访问速度远慢于内存的访问速度。
另外和这个相反的就是时间换空间，当然这种一般就不是高性能服务的常用方法，是系统内存不够用时使用的一些方法，比较典型的就是使用压缩算法了。
并行/异步处理
并行一般是多进程/多线程/多协程来协作处理，提高并发度，提高qps，或者减少请求 处理时间。
我们常见的nginx，一直使用的是多经常的框架，目前很多开源框架都使用了多线程加多协程的方式，比如brpc/trpc cpp都实现了m:n的协程模型，即m个协程映射到n个线程上，当然go语言的协程调度也是这么实现的。
比如需要在一个函数中有两部分任务可以放到协程中去执行的场景(c++代码样例需要借助第三方库来实现，go语言则是原生支持的)：
// 使用 cppcoro 的协程任务
cppcoro::task<>Task1(){
// 执行具体的代码逻辑...
co_return;
}
cppcoro::task<>Task2(){
// 执行具体的代码逻辑...
co_return;
}
intFunc(){
// 同步等待所有任务完成
auto[result1, result2]= cppcoro::sync_wait(cppcoro::when_all(
task1(),
task2()
));
std::cout <<"Task 1 returned: "<< result1 << std::endl;
std::cout <<"Task 2 returned: "<< result2 << std::endl;
return0;
}
异步通常比同步/阻塞的方式要快，也不会比协程慢，但是会增加一些代码的理解难度。
在c++框架中，当协程还不流行的时候，一般高性能场景都是用异步调用，
rpc异步调用的原理是：
1：在socket请求发送之前会保存当时的调用参数，包括回调函数的地址，以及回调的部分参数。
2：在socket收到返回之后，进行处理。
3：在socket发送请求之后，到socket收到请求之前这段时间，cpu可以用来执行其他任务。
voidInvokeBanker(RequestPtr request,const WorkflowCallback& callback){
DmpDataRequest dmp_req;
// TODO 设置dmp_req的值
CustomEvent* cev =newCustomEvent();
dmp_req.SerializeToString(&cev->body);
App::GetInvokeMgr()->Invoke("dmp_server", cev,
std::bind(&InvokeDmpCallBack,this, std::placeholders::_1, request, callback),
-1, request->GetBidRequest().request_id());
}
voidInvokeDmpCallBack(
EventBase* msg, RequestPtr request,const WorkflowCallback& callback){
// TODO 解析返回内容 并进行业务逻辑处理
callback(0, request);
}
预先/延后处理
预先处理，比如连接池，预先预先创建好连接，在业务逻辑处理时能节省几十到几百ms的时间。
// 创建连接池，程序启动的时候调用
intConnectPool::Start(const ClientConfig& cli_config){
for(int idx =0; idx < cli_config.single_addr_connect_count;idx++){
Client* client =BDF_NEW(Client,
cli_config.address, cli_config.timeout, cli_config.heartbeat);
if(0!= client->Start()){
BDF_DELETE(client);
return-1;
}
clients_.push_back(client);
}
return0;
}
// 获取可用连接
Client*ConnectPool::GetValidClient(){
size_t loop_cnt =0;
while((loop_cnt++)< clients_.size()){
int idx = current_++;
Client* cli = clients_[idx%clients_.size()];
if(cli && cli->GetClientStatus()== Client::kWorking && cli->TrySetBusy()){
return cli;
}
}
WARN(logger_,"no valid client,name:"<< name_<<",loop times:"<< loop_cnt);
returnnullptr;
}
再比如提前读取数据，使用的时候能快速返回，不用再去读取，都属于预先处理
延后处理，常见的有异步写日志，异步发送数据到kafka，这些逻辑都是异步的，几乎不会占用主流程的处理时间，这样请求方就可以快速地收到响应。
// 异步处理日志
intLogManageHandler::AsyncProcess(netbasic::CustomEvent* custom_ev, LogManageRequestPtr request){
//逻辑处理
int ret = msg_pipe_->SendMsg(
LogMsgHeader(request->GetLogManageType()),
request->GetLogDataAddr()+consts::log_type_format_size,
request->GetLogDataLength());
if(likely(ret)){
// 加入处理队列成功
}else{
// 加入处理队列失败
}
}
// 发送数据到kafka
RdKafka::ErrorCode resp = kafka_producer_->produce(topic, RdKafka::Topic::PARTITION_UA,
RdKafka::Producer::RK_MSG_COPY/* Copy payload */,const_cast<char *>(log_addr), log_len,NULL,NULL);
if(resp != RdKafka::ERR_NO_ERROR){
INFO(logger_,"Kafka produce failed: "<<RdKafka::err2str(resp));
}
缓存/批量合并
比如LRU缓存，就属于一种缓存加速技术。
typedef lru::LRU_Map_No_Lifetime<std::string,CacheForBid>DmpDataCache;
DmpDataCache dmp_data_cache_;//定义缓存对象
dmp_data_cache_.Reset(custom_cfg->dmp_cache_size_);// 初始化
if(dmp_data_cache_.Get(key, user_data)){
// 成功获取到缓存的数据
}
//获取到数据之后插入到缓存
dmp_data_cache_.Insert(key, std::move(tmp));
其他的还有cpu缓存，cdn缓存，浏览器缓存，redis缓存等。
批量合并，典型的是查询数据，一次可以执行多条命名，如redis的mget，pipeline等。
在广告系统中，比如adx中，有一个很常见的场景，就是请求需要同时发往多个dsp，在大约200ms左右，要么所有dsp都返回了，要么一个或者多个dsp超时了，可以使用boost来实现：
asio::awaitable<std::string> task1() {
// 任务处理
}
asio::awaitable<std::string> task2() {
// 任务处理
}
asio::io_context& io = co_await asio::this_coro::executor;
auto timeout = std::chrono::seconds(1);
// 创建超时定时器
asio::steady_timer timeout_timer(io, timeout);
std::vector<asio::awaitable<std::string>> tasks;
tasks.push_back(task1());
tasks.push_back(task2());
// 使用 || 操作符竞争：所有任务完成 OR 超时
auto results = co_await (asio::experimental::when_all(std::move(tasks))|| timeout_timer.async_wait(asio::use_awaitable));
//TODO 检查是任务完成还是超时，未超时的进行返回处理逻辑
除了可以借助第三方库来实现，我们也曾经自己实现过异步发送多个dsp加超时的逻辑：
// 向多个dsp发送bid请求，超时时间在DspInvokeExtra中提前设置好
//InvokeDsps会遍历将请求非阻塞的发送给dsp，然后收集每个dsp的返回，直到超时，如果超时前所有dsp都返回了，那么触发bind的callback函数，如果超时了，只有部分dsp返回了，也会触发bind的callback函数
GetInvokeMgr()->InvokeDsps(request->GetDspInvokeExtra(), adxev,
std::bind(&WorkflowDspInvokeClient::SendRequestCallBack,
this, request, callback, std::placeholders::_1, std::placeholders::_2));
// 回调处理
void WorkflowDspInvokeClient::SendRequestCallBack(
AdxRequestPtr request,
const WorkflowCallback& callback,
std::tr1::unordered_map<int, netbasic::EventBase*>& resp_info,
netbasic::DspResponsExtra& response_extra){
if (request->IsInternalTimeout()){
// 内部超时处理
}
for (const auto& it : resp_info){
if (!CheckValidResponse(it.first, req_info.slot_id[0], it.second, response)){
// 无效返回处理
}
// 返回处理等逻辑
}
callback(0, request);
}
算法和数据结构
算法这个就比较好理解了，n次方的算法事件复杂度，nlog(n)、O(n)的算法复杂度，执行时间差异还是非常明显的。
数据结构，比如什么场景适合用vector/list，什么场景适合用map/hash_map这也非常重要，需要熟悉每种数据结构的原理，知道各种操作的时间复杂度，来选择合适的数据结构。
这一块涉及的内容其实可以非常多，也非常广，可以以广告引擎这块的迭代来展开吧。
十几年前，程序化广告还没出现的时候，广告网络中引擎的检索，是遍历广告位上的投放来进行检索的，因为每个投放都必须投放在固定的广告位上。所以一次请求只会处理一个广告位上的几个投放，不会出现性能问题。
随着程序化广告的出现，广告投放不会固定在某个广告位上，如果检索时，还是去遍历所有的投放，引擎处理每次请求需要遍历几千，几万，升至数万次，会导致性能急速下降，所以需要使用倒排索引技术来解决这个问题。
什么是倒排索引，就是你的程序在启动的时候，需要构建一张倒排表，当请求来的时候，根据请求参数，可以直接获取到该条件对应的数据。这种场景最初出现的搜索引擎中，简单理解就是，当搜索引擎服务启动时，会将互联网上的每个页面的内容进行语法语义拆分，拆分出很多关键词，每个关键词都维护一个数据结构，如：
std::unordered_map<std::string, std::list<UrlInfo*>> index_;
key表示关键字，值是一个链表，表示能匹配上该关键字的所有网页。
这种场景可以类似的搬到广告引擎中，每次广告检索，我们会处理很多广告定向，其中部分定向可以使用倒排索引的思想来解决，比如地域定向，我们有一个地域定向的倒排表，性别，年龄定向有一个倒排表。数据结构如下：
std::unordered_map<std::string, std::list<AdGroup*>> index_geo_;
std::unordered_map<std::string, std::list<AdGroup*>> index_age_;
std::unordered_map<std::string, std::list<AdGroup*>> index_gender_;
检索时，先选出所有满足地域定向条件的广告，再选出所有满足性别定向条件的广告，求出这两项定向结果的交集，最后选出所有满足年龄定向的广告，和前面的两项交集结果再取交集。依次类推。
我们可以看到第一个版本，求交集的时候，还需要遍历AdGroup之后求交集，时间复杂度是O(M*N)，会比较高，于是想到了一个优化的版本：
std::unordered_map<std::string, std::set<int>> index_geo_;
std::unordered_map<std::string, std::set<int>> index_age_;
std::unordered_map<std::string, std::set<int>> index_gender_;
满足定向条件的列表只存储AdGroup的id，并且存储的id是有序的，那么求交集的时候，时间复杂度是O(M+N)，效率就会高很多。
能否进一步的优化呢，当然可以：
std::unordered_map<std::string, std::bitset<Num>> index_geo_;
std::unordered_map<std::string, std::bitset<Num>> index_age_;
std::unordered_map<std::string, std::bitset<Num>> index_gender_;
将排序的set替换为位图，求交集的时间复杂度是O(n)，但是这样一定更快吗？不一定：
1：当满足条件的id比较稀疏时，比如最小值为1，最大值为1亿，那么求交集的复杂度反而反更高，因为n的范围太大了，遍历的次数很多。
2：只有当满足条件的id比较密集时，求交集才会比较快
那么我们是否可以解决上面的问题呢，答案是可以的，我们将bitset改为Roaring Bitmap（c++需要借助开源的RoaringBitmap库）：
std::unordered_map<std::string, roaring_bitmap_t*> index_geo_;
std::unordered_map<std::string, roaring_bitmap_t*> index_age_;
std::unordered_map<std::string, roaring_bitmap_t*> index_gender_;
生产者与消费者
在高并发的服务中，我们经常会涉及到一些消息的处理，会先将消息保存到一个队列中，然后由其他协程/线程来消费，在这个过程中，线程/协程怎么设计，锁怎么加，都是一门学问。生产者消费者的线程模型有如下几种：
1：单线程生产，单线程消费。
最简单的就是直接使用标准库的队列/链表，一个线程写队列，另外一个线程读取队列，然后做逻辑处理。这样的话至少需要加一个锁。
但是有没有办法不加锁呢，当然可以，可以使用环形队列，在一个线程生产，一个线程消费的情况下，是可以不加锁的，在c++代码里面，经常会实现这种队列。这种无所的场景是可以提高程序的性能。
2：单线程生产，多线程消费。
这种场景可以使用一个队列或者多个队列，无论使用一个队列还是多个队列，都是需要加锁的，但是比较明显，使用多个队列加多个锁时，锁的冲突概率更低，效率会更高。
3：多线程生产，单线程消费。
这种场景就不画图了，将第二种情况的线程数量反过来即可。
实际场景中，通常读取数据之后会做业务处理，而业务处理通常比数据入队列要慢很多，所以这种场景在生产环境中一般很少使用。
4：多线程生产，多线程消费。
这种场景也可以选择使用单队列或者多个队列，如果使用单队列，很明显，锁的冲突会比较多，如果使用多队列，如果加锁了，那么也只有每一组生产线程和消费线程之间才会有锁的冲突。当然如果设计得好，是可以无锁的，比如使用环形队列。
锁的使用
使用锁的时候也有不少注意点。
1：减少加锁的范围
//代码1
Obj obj;
obj.init();
mutex.Lock();
ls_.push_back(obj);
mutex.Unlock();
//代码2
mutex.Lock();
Obj obj;
obj.init();
ls_.push_back(obj);
mutex.Unlock();
上面的代码1是比较ok的，锁加在需要加的地方，不需要包含其他非必要加锁的代码，这样会影响程序的性能。比如代码2中的对象创建和初始化，都不应该放到加锁的内容里面。
2：减少锁的竞争
比如在生产者，消费者模型里面，当有多个队列时，如果必须加锁，我们一定要使用多个锁，每个队列加一把锁，可以大大减少锁的冲突，避免程序性能降低。
3：无锁数据结构
无锁数据结构通常指无锁队列或者无锁map，无锁队列的实现是非常麻烦的，如果实现不够好，很有可能在并发场景下有一些问题。
无所队列真的是完全无锁吗，其实并不是，本质上还是cas加自旋锁类似的方式来实现的，还需要考虑ABA问题[比如使用版本号来解决]，内存顺序混乱[比如使用内存屏障]等。
无锁队列真的效率高吗，这个其实还是要分场景的，比如生产者消费者，如果本来设计的比较合理，是否使用无锁队列，并不会有多大的性能差异。
写在最后
本文写了一些优化方法，其实在高并发/性能优化这块，还涉及到很多的内容，比如：我们的代码要避免大量的内存拷贝，频繁创建的对象可以使用内存池，对象池这些空间换时间的小技巧，还有编译优化，曾经我们在一个c++的项目中，加上几个编译优化选项，程序的qps会直接翻倍。
关于数据库，尽管在广告引擎中不会直接去读取数据库，但是在后台的相关服务中，要注重性能，数据库相关的优化又是必不可少，比如常见的索引优化，读写分离，分库分表都是一些良好的设计。
关于架构设计方面，需要使用负载均衡，将请求分发到多个服务器，至于微服务，需要将系统拆分为多个松耦合的服务，独立扩展。程序处理流程需将耗时的操作异步化，避免阻塞主线程。缓存处理，需要使用多级缓存（如本地缓存、分布式缓存）减少数据库压力。
高并发设计/性能优化，很多时候都是在我们做功能设计的时候，需要选择一个比较优秀的设计方案，在我们的代码实现中注重实现细节，追求技术洁癖，才能做的更好。