开发笔记(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 ，没能通过我自己写的测试。但花了一点时间就修正了。
Comments
Posted by: 超市耗材 | (13) August 22, 2012 04:16 PM
Posted by: Cloud | (12) July 28, 2012 12:49 AM
Posted by: 4399小杂荽 | (11) July 27, 2012 11:47 PM
Posted by: David Xu | (10) July 25, 2012 10:59 AM
Posted by: David Xu | (9) July 25, 2012 10:54 AM
Posted by: Anonymous | (8) July 25, 2012 10:41 AM
Posted by: dwing | (7) July 23, 2012 11:47 AM
Posted by: Leon | (6) July 20, 2012 10:54 PM
Posted by: lenky | (5) July 20, 2012 11:50 AM
Posted by: Cloud | (4) July 20, 2012 11:42 AM
Posted by: sam | (3) July 20, 2012 11:30 AM
Posted by: Atry | (2) July 20, 2012 07:40 AM
Posted by: Arden | (1) July 19, 2012 10:28 PM