支持并发遍历、修改的map

问题

在游戏开发中,经常要存储大量对象,比如玩家、怪物,在增加、删除的同时,还需要遍历。在此,我们只讨论单线程并发,不考虑多线程。在多线程情况下处理这种情况,更是自找麻烦,况且效率低下。

  1. 删除、增加<=>遍历, 是矛盾的。遍历过程中新增、新删的对象,应该如何影响遍历?
  2. 遍历还有可能是并发的。如果使用了协程,这种情况出现的机率很高;就算不使用协程,还是有可能出现:那就是遍历嵌套,遍历vector的过程中,又开启了第二次遍历(有可能你调用了一个函数,这个函数启动了遍历)。

设计原则

根据实际情况,遍历过程中的一致性,不是绝对需求,这一帧遍历不到,下一帧遍历到就可以了,而绝对不想要程序崩溃、乱抛异常,这个结构就是根据实际可以接受的范围,一步步做出来。就是个“弱一致、最终一致”的数据结构 。它遵循的原则:

  1. 遍历过程中的增加、删除,不影响遍历过程。就相当于在遍历开启时,启动了一个镜像,遍历在这个镜像上进行。(最终实现的是增加没影响,删除时可以立即影响遍历结果的)

2.支持并发遍历,遍历中的增加、删除尽量不影响现有遍历过程。增加一个foreach(function<bool(pair<K,V>&)>)函数,把遍历功能封装起来,同时对遍历者进行计数。通过这个计数,来感知是否有遍历、是否有并发遍历。

3. bool exists(K),对元素是否存在的判断,是高度一致的。

实现方法

使用四个结构:

private:
  boost::unordered_map<K, V> map_;
  boost::container::deque<NODE> q_;
  boost::container::deque<NODE> task_q_;
  ezg::local_shared_ptr<iint> iter_num_;

第一个map,实际上是时时刻刻都完全一致的,任何增删都会在map上实时反应。

第二个q_是我们遍历的对象,它在静态时,会和map保持一致。

第三个task_q_,则是个任务队列,它的作用在遍历过程中缓存所有的add请求(这种请求可以立即对map操作),并在最后一个遍历结束之后,立即把它们放入q_,达到最终一致。

第四个iter_num_,是个智能指针,用于并发遍历的计数。初始计数是1,也就是没有遍历,每次进入遍历函数时,我们复制一个它的拷贝,就会增加一个计数,退出一个遍历,会自动销毁一个拷贝,减少一个计数,当最后计数为2的时候,也就是只存在一个遍历过程的时候,此时把task_q_中的任务刷到q_,即可。

以下是要点:

  • 在这个过程中,要保持map的强一致性,元素是否存在,以map为基准。在不确定元素是否存在的时候,就可以查找map。
  • add、remove函数中,要判断是否存在正在进行的遍历,如果不存在,可以直接对map和q操作。如果存在,那么可以直接对map操作,并缓存一份到task_q_。
  • 遍历:用q_来进行正常的遍历。遍历结束后注意把 task_q_中的任务刷到q_。

到此为止,并发的遍历、增、删,就可以约束在我们的期望范围之内,而不会出现崩溃、或者无法预测的情况。

这里是用boost c++实现的,用标准库,也一样。别的语言用类似的数据结构,应该也可以做相同的实现。

发表评论

电子邮件地址不会被公开。 必填项已用*标注