« 开发笔记(22) : 背包系统 | 返回首页 | C 的 coroutine 库 »

开发笔记(23) : 原子字典

问题是早就提出了的。在 开发笔记 18 中,就写到一个需求:一个玩家数据的写入者,可以批量修改他的属性。但是,同时可能有其他线程在读这个玩家的数据(通过共享内存)。这可能造成,读方得到了不完整的数据。

我们可以不在乎读方得到某个时间的旧数据,但不可以读到一份不完整的版本。就是说,对玩家数据的修改,需要成组的修改,每组修改必须是原子的。

起先,我想用读写锁来解决这个问题。方案想好了,一直没有实现。只是把读写锁的基本功能实现了。

这几天这个问题被重提出来。因为,前段我们都采用了鸵鸟政策,当问题不存在(事实上我们也没有发现实际中出现可观测到的问题)。

反正探讨了好几个解决方案,一开始都是围绕怎么加锁,锁的粒度有多大来展开的。甚至,我们把其中的一种方案都实现出来了,并写了压力测试程序测试。不过,这些方案都不太令人满意。大家担心锁的开销,以及逻辑代码编写者所需求关心的问题太多,导致有死锁的可能性。

昨天差一点决定用一个地图锁来解决这个问题,就是用牺牲同一个地图进程上,玩家间并行的可能性为代价的。这个方案也不无不可。但昨晚躺在床上一直睡不安稳。因为这样做,就失去了一开始我期望用并行方案来设计游戏服务器的初衷。如果这样,还不如全部退化到单地图单进程来编写程序。那么一定有方法是可以避开锁以及避免让写逻辑的程序员去关心数据共享的读写冲突问题的。


今天,我实现了一个数据结构,暂时命名为原子字典。

这个模块用 C 编写,在 Lua 中使用。从 Lua 中看起来和 Lua 的 table 无异。只是多了写限制,比如 key 只能是 string 。value 只能是 number 和 string 。没有层次结构。 当然这些限制只是为了简化实现而已,并不被算法限制。

我们可以把一组相关数据放在一个原子字典中。原子字典可以被同进程,不同线程的 Lua State 共享(稍微改进,也可以利用共享内存跨进程)。自己的 Lua State 读写这个字典,感觉不到任何差异。

我提供了一个 barrier 函数,由应用程序间隙调用。对于我们的系统,是由单一源的数据包驱动的,所以只需要在数据包处理函数处写上 barrier 的调用即可。

当前 Lua State 对字典内容的修改,只在调用了 barrier 之后,才对其它线程上的 Lua State 可见。所以,你永远看不到别的 Lua State 对字典内容的修改过程,而看到的是一个个快照。


我是这样实现的:

估算出系统物理线程的上限(我们的系统中,是严格小于等于系统的核数的)。我给每个字典对象都预先开辟了 N 个副本空间(N 大于最大线程数)。

字典有一个引用,标识了当前的最新版本的副本。

任何人读写字典,都引用最新版本,且把这个版本引用计数加一。这个引用是直读的。同时,把字典的引用计入当前 Lua State 的 Barrier 控制器上。

当你想改写字典,先检查从上次 Barrier 调用以来,是否曾经修改过。如果是第一次修改,在对象的预留副本池中找到一个空闲空间,引用加一,并把原始的只读副本复制过去,接着再修改。

每次 Barrier 调用时,遍历所有记录在案的读写过的字典对象。如果是经过改写的,就把它更新为最新版本(同时做一些整理工作,主要是针对字符串类型的处理。这里字符串值类型,我是放在预分配的字符串池中的);否则,直接减掉引用。这个方案不解决并发写问题。如果有两个以上并发写,只有一个会生效,另一个版本则丢弃掉。这是我们框架的一个约定。我们同时只允许一个写入者。当然,如果有必要,理论上也可以做一些回滚重写的过程。


差不多一个玩家身上的属性组大约在 100 这个数量级。大部分是数字(float)。所以每次改写,需要有额外 0.5K 左右的数据拷贝。每个玩家的处理逻辑中,一秒大约发生十个左右会有数据写操作,所以我认为这个代价(为每个玩家每秒多 5K 的数据拷贝)是可以接受的。

为了测试我的模块的正确性。我构造了一个有 30 个线程的多线程程序,每个持有一个原子字典对象。这个字典对象中放有 A B C D 四个字段。循环 10000 次,每次更新它的四个字段,前三个取随机数,第四个用 100 减去前三个的总和。

同时,每个线程在每个循环周期内,检查其它 29 个线程的对象,检验这些对象内四个字段的和是否为 100 。


很高兴我能花一天实现完成了这个模块,大约有 800 行 C 代码,200 行测试代码。虽然一开始有点小 bug ,没能通过我自己写的测试。但花了一点时间就修正了。

开源版本: https://github.com/cloudwu/atomdict

Comments

很不错,留脚印了.

@david xu

刚才把 tinystm 的文档看了一遍。我的确可以用它来实现这个东西。

不直接用 STM 实现上层逻辑而需要一个中间数据结构是因为上层是用 lua 写的。我很难让 lua 基于 STM 来工作。

不让上层逻辑关心锁的问题也是因为不能把锁管理的复杂性放出去。

这几天我实现了另一个东西也是为了让 lua 可以共享数据。

https://github.com/cloudwu/lua-stable

保留两份数据,在写操作完成后把指针移到写完的数据,读的时候永远只读指针指向的

如果不想用锁也可以考虑用Transaction memory。好像有基于C语言的实现,例如tinystm。接口是很简单的。是个软件内存事物跟踪的实现。
具体性能的话我也没测试过。

比读写锁更加细化的是数据库种常用的Intention Lock:
http://en.wikipedia.org/wiki/Multiple_granularity_locking
我曾经在杭研这里为他们实现过一个demo.
此锁和行级锁等细锁配合使用。先用Intention Lock具体声明你想操作的意图,例如是读写大片数据还是小局部。然后结合具体的内部细锁。例如你想对数组的一个元素操作,如果是只读,你可以用IS, 如果你是写,你指定用IX, 如果是读全部数据,你用S,如果你基本上要全部写一边,你用X,等等。然后结合这个锁,你修改某个元素时,也许用某个对应的mutex解决具体的锁定问题。

读写锁的内部实现,还有读者优先和写者优先的问题。如果更新数据是重要的,那就是写者优先。但是写者优先,会有死锁的可能。例如一个线程A已经对该读写锁获得了读锁,如果后来有一个线程B,是个写者等着,这个时候,如果A再想获得这个锁的读锁(也就是递归),它会等待让B先获取,而A已经有一个读锁,结果B永远也获取不了写锁。死锁就产生了。我们在FreeBSD中避免这问题的方式是在线程控制块里记录当前线程拥有了几次reader lock,如果大于0,那么就无视等待着的写者。这是比较简单的方法,不需要具体跟踪每一个读写锁。

貌似只能解决不相关的并行操作,对于有顺序相关的操作是有问题的,比如两个人同时给第3个人加HP,如果两个读HP操作是并发的,最终加HP的效果只有1个生效,而不是同时生效.

使用版本的方式可以解决您的问题吗?对于进行修改的数据,则写时复制版本,当该线程处理完毕后,提交版本,此时版本可见,在提交之前,其他线程访问的都是之前的版本。

没看得太仔细,不过复制、修改、更新,和内核里的RCU锁一致?

@sam

哈哈, 谢谢

https://github.com/cloudwu/atomdict/blob/master/README.md似有几处笔误:

Atomdict implement(implements) a data structure for multi lua state.

You can use it in multi-threads , create one lua state per thread. Atomdict will helps(help) you to(可省略to) exchange a group data atomic between lua states.

。。。give(giving) a typename will improve the performance.

。。。Delete a(an) atomdict handle

。。。Call barrier for(to?) commit atomdict objects (+so) that their changes could be been(seen?) by others.[偷笑]

这个数据结构可以用HAMT实现,每次修改和查找的开销都是O(1),远远小于复制整个表。
https://en.wikipedia.org/wiki/Hash_array_mapped_trie

HAMT很通用,是Scala默认的关联数组格式。

有点像oracle中的多版本无锁读

Post a comment

非这个主题相关的留言请到:留言本