找Bug一则

需求

上个月接到个竞技场的需求，大概功能就是根据玩家的积分来匹配对手，玩家分为三十个段，积分一定落在这三十个段里面，每个玩家先从对应的段里面随机匹配对手，如果在当前段位匹配失败，则向下一个段位匹配，直至匹配成功或者找不到匹配。 由于我们游戏活跃玩家很多，所以要尽量快速的匹配对手。

设计

首先每个段位中的玩家使用一个双链表表示，链表中每个节点结构如下 struct ListNode { unsigned uin; unsigned points; }； 每个双链表作为一个队列，队列的长度不能超过max_length，超过时则使用LRU算法淘汰玩家。 当玩家进行匹配时，首先根据分数计算出缩在的段位，然后根据段位找到对应的双链表，然后从双链表中随机选择一个对手，如果对应的双链表没有其它玩家，则向下一个段位寻找，直至找到匹配的玩家。

同时，为了快速定位每个玩家的信息所在的ListNode，使用一个叫做active_的map来管理所有的用户数据，由uin映射到MapNode, 节点结构如下 struct MapNode { unsigned rank; list::iterator iter; };

当玩家和他的对手战斗技术后会向服务器更新自己的积分，这时

1. 计算上报的积分所属的段位current_rank
2. 根据玩家uin在active_中查找是否已经保存了玩家的信息
   • 如果保存了玩家信息
     • 从active_中取出uin对应的MapNode
     • 根据rank(称为old_rank)找到对应的双链表
     • 根据iter从对应的双链表中将ListNode解开，同时更新ListNode中对应的值
     • 判断old_rank和current_rank是否相等，若相等则直接将对应的ListNode塞到原队列尾部，结束本步* 若不等，否则根据currentrank找到对应的队列，判断队列长度是否唱过maxlength`，不超过则塞到队列尾部，结束本步
     • 从对应的队列中淘汰一个玩家，同时移除active_中被移除玩家的信息，然后ListNode入列，结束本步
   • 如果没有保存玩家信息
     • 则新创建一个ListNode, 对对应的域进行赋值
     • 根据current_rank找到的对应的队列，处理过程同前
3. 更新玩家在active_中的数据

分析

• 当玩家匹配时，计算对应的段位O(1)，然后找到对应的队列O(1)，在队列中随机寻找对手O(k)(k为随机范围), 最差情况下会遍历三十个段位的队列，但是这时每个队列上做的操作都是O(1), 所以匹配的时间复杂度为O(k)
• 当玩家更新自己的积分时，计算对应的段位，最多两次出队和一次入队，一次对active_的查找更新或插入操作，所以更新操作的时间复杂度为O(n)

BUG现场

系统上线后十几分钟后第一个Coredump出现，使用gdb查看无法查看堆栈，怀疑是使用了高版本的clang编译导致找不到对应的debug符号，无奈之下只好将日志写到stderr，观察coredump位置，最后发现挂在出队其它玩家时的情况 assert (list_node.uin == uin); 这个assert用来判断出队的玩家对应的ListNode中的uin与查找active_的uin是否相等，这原本不可能出错的地方居然出错了。

BUG分析

这次使用的自己写的map和list，其中map是由红黑树实现 * 首先怀疑是不是map实现的有问题，因为当时对红黑树的理解确实也不够深，基本上是照着《algorithms》这本书上的Java代码翻译过来的，但是测试用例也算比较充分，仔细看了多遍代码也没有发现有什么问题。 * 然后怀疑是不是list有问题，但是list本身属于比较简单的结构，不久之后也被排除。 * 然后开始看程序逻辑，发现玩家更新自己积分的时候，对active_的更新并没有把iter也给对应更新上去，导致出队了一个不属于自己的节点，遂改之。 *改完之后重新上线，大概30分钟后仍然出现coredump, 而且还在同一行，这让我非常费解，又看了几遍代码都没发现有什么问题，于是只有把线上的操作都给记录下来，然后在本地重现coredump, 在不断打日志试了一天之后，终于发现coredump发生在A玩家从Rank1变成Rank2, 又回到Rank1的过程中，B玩家复用了A玩家在Rank1时候使用的节点，然后出队A的时候发现A对应的MapNode中的iter神奇地仍然指向B，于是导致assert触发。 但是代码逻辑中确实在更新rank的时候已经更新的对应的iter, 否则很快就能触发这个BUG, 而不需要等几十分钟。

代码看了一天仍然没有头绪，外网环境的服务器仍然在不停的coredump, 拉起, coredump...循环，只好硬着头皮用STL重写了一遍，结果十分稳定，再也没有问题了，这更加让我确定是map的问题。

周一上班，尝试只替换map, 不替换list, 工作正常，排除list问题。 最后就剩下map了，又一点一点的修改了部分代码，最后定位到对map的一个迭代器操作可能有问题。

对于STL中的map来说，如果你获得了某个元素的迭代器, 那么除非调用map.erase，否则这个迭代器是一直有效的，即使你进行了很多次insert和erase操作。

但是在我自己实现的map中，由于erase的时候使用了常见的DeleteMin方法，这个方法首先会交换要删除的节点和它的后继。 由于内部是使用mmap来进行数据落地，map中的RBNode还保存了一个nodeid，用来在mmap中索引对应的内存区域，交换节点时由于map的key和value都是POD Type, 而如果要避免拷贝进行真实交换的话，需要设计到很多节点，还有两种情况需要考虑，于是决定直接拷贝value, 这样当调用erase的时候错误地影响了被删除节点的后继的迭代器的有效性。

而更新玩家积分时，为了避免一次额外的查找，在潜在的出队其它玩家和active_的erase操作后仍然使用了出队前的迭代器，而实际上这个时候这个迭代器已经被active_回收的节点，导致更新操作无效。下一次通过uin查找时仍然找到的是旧数据，导致了coredump.

BUG处理

很简单，在更新active_之前重新获得对应的迭代器，使用外网操作验证，已经不会出现coredump.

总结教训

• 涉及迭代器的时候要谨慎判断迭代是否已经失效，而STL中迭代器失效规则又不一致(vector resize的时候失效, list一般不失效，map一般也不失效), 避免太多情况，其实可以考虑更易性操作之后假定迭代器必失效。
• 没有彻底吃透某项技术的时候不要轻易使用，万一要用也要做好应急方案。这一次红黑树自己其实并不太懂，很多地方都知其然不知其所以然, 于是国庆回家又恶补了一遍，算是基本吃透了。
• 排查问题的时候一定要分块判断，这次由于基础的数据结构也是自己写的，所以排查起来其实挺困难的，又要怀疑是不是基础结构有问题，又要想是不是逻辑又写错了。