1.问题描述
上周末一个做视频直播的朋友向我咨询他们遇到的一个关于大量内存对象并发的问题，具体问题描述是这样的，在游戏视频直播的时候，需要向观看直播的人提供一个可以自由聊天的功能（相当于QQ群），这就要涉及到在服务器端实现一个管理用户列表的功能，这个用户列表可能很大（最大可以容纳300万人观看和聊天）。他们的做法是在后端服务分为两层，如图：
图-1
gate用来做客户端连接和消息分发的服务，chat是用来做用户认、管理和消息转发。那么需要在chat上维护一下用户
列表。他们遇到的问题就是当用户列表比较大的情况下，chat的处理能力急剧下降。我详细询问了他关于用户列表维
护的数据结构和并发控制，初步定位到了问题所在。
2.问题分析
我们先来分析一下他们的实现，他们采用的是C++和STL，熟悉C++/STL的朋友很快就会想到使用std::map 来实现管理，对的，这正是他们的思路，下面是他们实现的简单描述:
class user{public:uint64_tuser_id;/*todo:用户信息基本信息*/pthread_mutex_t mutex;/*用于保护user的多线程并发*/}std::map<uint64_t, user*> user_map;pthread_mutex_tuser_map_mutex; /*多线程操作时保护user_map*/
对map管理的用户列表需要提供增、删、改、查和遍历。例如向某一个用户进行操作：
LOCK(user_map_mutex);std::map<uint64_t, user*>::iterator it = user_map.find(id);if(it != user_map.end()){UNLOCK(user_map_mutex);LOCK(it->second->mutex);operator(it->second); /*可能时间比较长，可能是发送网络报文、信息写盘、RPC调用等*/UNLOCK((it->second->mutex);}elseUNLOCK(user_map_mutex);
其他操作类似。这个实现有几个严重的并发问题:
1.每次操作都需要对user_map进行LOCK
2.每次对某个用户操作都需要对用户LOCK
3.每次对用户操作的函数可能时间会比较长，例如socket发包、RPC调用等。
3.user并发竞争优化
由于chat是个单点多线程并发系统，在网络事件多的情况下，会发生大量的线程锁竞争问题。最为明显的就是第二三个问题，其实这两个是一个问题。解决这个我们只要把user中的mutex去掉即可。怎么去？我的想法是采用user对象引用计数来实现。例如：
class user{public:stringuser_id;/*其他的一些用户信息*/Int ref;/*引用计数为0时，free掉这个对象*/} void add_ref(user* u){u->ref ++;}void release_ref(user* u){u->ref –;if(u->ref <= 0) delete u;}引用计数的操作规则：
在用户信息加入用户列表的时候，add_ref
在用户从用户列表中删除的时候，release_ref
在用户信息被引用的时候，add_ref
在用户信息引用完毕的时候，release_ref
那么对某个用户的操作就会变成:
LOCK(user_map_mutex);std::map<uint64_t, user*>::iterator it = user_map.find(id);if(it != user_map.end()){user* u = it->second;add_ref(u);UNLOCK(user_map_mutex);operator(it->second); /*有可能时间比较长*/release_ref(u);}elseUNLOCK(user_map_mutex);User对象引用计数很好的解决的User加锁的问题，但引用计数的引入了一个新的问题就是在多个线程同时修改某一个用户信息时，会引发数据无法保护的问题。我们处理里这个问题很简单。不管是增加操作、修改操作和删除操作，都遵循先必须将user_map中已存在的对应的user信息从map中删除，再做信息新增。例如修改操作：
LOCK(user_map_mutex);std::map<uint64_t, user*>::iterator it = user_map.find(id);if(it != user_map.end()){/*将旧的信息拷贝出来*/user* u =it->second;user_map.erase(it);copy(update_u, u);release_ref(u); /*解除引用*/update(update_u); /*修改用户数据*/Add_ref(update_u);user_map.insert(update_u);UNLOCK(user_map_mutex);}elseUNLOCK(user_map_mutex);增加和删除的实现类似。对象引用计数很好的解决的用户数据锁竞争的问题，但在user_map的用户数小于1万以下，使用引用计数可以把增删改查操作的并发问题避免掉。不能解决全map扫描并发问题，也不能解决在user_map很大时大量需要操作用户信息的并发问题。问题出在不管是全map扫描还是对单个用户都需要对user_map进行上锁，这就是第一个问题了。在高并发请求下，这个user_map锁会产生大量的竞争，造成资源损耗。
4.放弃std::map要去掉这个锁，这就回到了在问题分析中的第一个问题上，众所周知，std::map是不支持多线程并发的，而且std::map操作对CPU cache并不友好。去掉这个全局锁改用更小粒度的锁，那就需要放弃std::map。在大量数据的情况下，一般会采用hash table或则btree来组织数据（研究过数据库存储引擎的人都知道，呵呵！）。简单起见，这里就以hash table为例来展开分析。
图-2
图-2是一个hash table的结构图，其中hash buckets是个数组。数组内有一个指向user结构的指针。好，，了解了hash table的结构我们再回到前面缩小锁粒度的问题上来。例如我们定义了一个hash table，它的buckets个数为1024，我们再定义一个pthread_mutex_t数组，长度为256。缩小锁的粒度很简单。
第一个mutex数组单元负责0 256 512 768序号bucket的互斥，第二个负责1 257 512 769序号的并发互斥，类推。计算一个bucket序号是由哪个mutex负责互斥的其实就是:
mutex下标 = bucket_seq % mutex_array_size；
只是需要垮上后座的勇气和一颗想走即走的心，
