并发 Hash Map 的实现

Lua 中的短字符串做了 string interning 的处理，即在同一个虚拟机内，值相同的字符串只存在一份。这可以极大的提高用字符串做 key 的 hash 表的查询速度。因为字符串比较的时间复杂度从 O(n) 下降到 O(1) ，比较查询的 key 和 hash 表内的 key 是否一致，只需要对比一下对象的指针是否相同即可。

我在解决多 Lua 虚拟机共享字符串对象这个问题时，合并了不同的 Lua 虚拟机中的短字符串表。让同一进程所有虚拟机共享一个短字符串表（ SSM ）。

我最初在实现 SSM 的时候，考虑到多虚拟机 GC 的复杂性，采用了只增不减的方案。即让部分短字符串进入 SSM ，设置一个上限，避免 SSM 无线膨胀。但 Lua 并没有把经过 interning 处理的字符串作为独立类型，目前只用字符串长度作为区分，也就是无法和不 interning 的短字符串共存。所以，那些已存在本地虚拟机短字符串表中的字符串，就不从 SSM 中获取对象。

修改过 Lua 的 string interning 算法是这样的：

1. 查看字符串是否存在于本地字符串表 (LSM) 如果存在，就立刻返回。这一步和原版 Lua 一致。

2. 查看字符串是否存在于 SSM ，如果存在，就返回。

3. 检查是否 SSM 上限已到，如果不能再增加新字符串，把字符串添加到 LSM ，返回。

4. 将字符串添加到 SSM ，返回。

考虑到我们通常在一个进程中运行数千个 Lua 虚拟机，SSM 是一个比 LSM 大得多的 hash 表，需要极高的并发访问性能。

我在最初设计时，考虑到 SSM 会设定一个容量上限，所以完全可以预估 hash map 大致需要多少个桶来避免最糟糕的 hash 冲突。如果桶的数量固定，那么就不必考虑 rehash 的过程。提高并发性能最简单的方法是对单个桶加小锁，避免对整个 hash map 加大锁。

做 string interning 时，先算出 hash 值，既而可以判定归属在哪个桶，这个过程是不需要加锁的。而大多数情况，我们对单个桶的读操作数量远超过写操作数量。因为 Lua 虚拟机在运作时，只有从外部构建字符串才会进行 interning ，内部字符串传递是不需要的。

每个桶一个读写锁非常合适。在没有 hash 碰撞发生时，不会有任何锁碰撞。如果桶的规模预估合理，hash 碰撞的概率就会降低到一个相对小的程度。我对 Lua 的 hash 算法和 hash 表的实现用大量数据做过测试，在 hash 表装满时，同一个桶下不同的字符串数量平均在 1.2 到 1.3 之间。可以认为，每次锁操作基本是 O(1) 的。

前段时间，我们增加了函数原型常量表的共享。每次加载新的代码，都临时打开了 SSM ，让新代码中的常量可以顺利进入 SSM 。做这次修改时，我在苏梅岛度假，没有太仔细考虑，结果放到线上，引起了一起事故。事故表现为服务器开启 2 天后，运行 CPU 负荷上升，导致玩家登录很慢，最终无法正常游戏。

事后追查原因是多方面造成的。首先，原来假定每次加载新代码临时打开 SSM ，这个操作是有限的，次数和源代码文件数量相关。实则并不是。打开 SSM 的位置不合理，lua require 时，整个搜索过程，包括那些尝试过，无法打开的文件，也被计入在内。最终打开 SSM 的次数远高于预期。

其次，打开 SSM 是通过增加上限容量 4096 来实施。给一个上限是为了控制最坏情况的出现。因为SSM 是全局的，不能单独控制当前工作线程。如果同时有另一个线程上跑了个 VM 在这段时间大量构造字符串，就会不断向 SSM 添加新元素。用一个上限控制，可以防止短时间添加了太多字符串。但是，我没有在关闭 SSM 后把这个容量调整回去。导致只要打开一次，SSM 最终一定会增加 4096 个新字符串。

由于我们一开始设计时，SSM 是不做任何 rehash 的，固定了 64K 个桶，所以在运行 2 天后，终于向 SSM 里添加了太多的元素。每个桶里都放了数百个元素，最长的超过了一千。这远超预估的 1.3 。

临时解决线上问题很简单，关闭 SSM 在加载源文件时，自动打开的机制即可。不过我在度假回来好好调查了整个问题，固然把 SSM 的开关控制可以更好的解决，依然能够把字符串重量控制在一个预计范围内，但我觉得还是有必要增加 SSM 的桶扩充的能力。

不过，实现 hash map 的 resize ，又不影响并发性能，就不那么简单了。避免在 hash map 的 resize 时 stop the world ，是需要解决的核心问题。

我现在采用的方案是这样的：

hash map 被分成两张表，A 表是读写表，可以插入新元素，也可以查询；B 表是只读表，只能查询。A 表和 B 表可以有重复项，任何一张表里存在一个元素，都认为这个元素存在。我们不处理删除元素的操作，所以不用考虑删除操作在 A B 表的同步问题。

插入操作一定向 A 表写入，查询操作则依次查询 A B 表。

在通常情况下，B 表是不存在的，所以无论是插入还是查询，都按过去的算法工作针对 A 表操作即可。

resize 是由固定线程主动检查整个 hash map 的状况触发，一旦发生，就创建出 B 表。这是通过给整个 hash 表加一个读写锁实现的。对于非 resize 操作，加读锁，保证操作过程中不会创建出 B 表；resize 则使用写锁，锁成功后，仅仅把原来的 A 表放到 B 的位置，转换为只读表；再创建出空的 A 表即可。这个过程极短，仅有两次指针操作。

所以，resize 启动本身可能被大量其它操作推延（任何操作都需要对 hash map 加读锁），但切换到 resize 状态， stop the world 的过程仅两次指针操作而已。

resize 的过程不可并行，也就是不能两个线程同时做 resize 。这是通过写锁后检查状态来判定的。如果两个线程同时想进行 resize ，第 2 个线程在写锁成功后，就能检查出已经有另外线程进入了 resize 工作（B 表已经存在），就立刻退出。

所以，对于 B 表，也就是过去一个阶段所有的元素都在这里，不会有人再修改它们。resize 过程就可以安全的把它们逐个转移到 A 表，即 resize 过程对 B 表是在不断改写的，但其它线程只能读取它。resize 过程就是循环逐个对 B 表中的每个桶做 rehash ，它是单独对每个桶上锁的，不会 stop the world 。一旦 resize 过程完成，再次对 hash 表加写锁，把已经是空表的 B 表删除。

下一步，我会给 SSM 加入 gc ，采用引用计数来删除不用的元素。因为删除是可选的，所以完全可以在查询字符串时，再判断引用计数是否为零，且只在非 resize 状态下，才进行删除操作。

在实现完后，Yang Xi 同学建议我看一下 2007 年 Google Tech Talks 上的 Advanced Topics in Programming Languages: A Lock-Free Hash Table 。我觉得思路是类似的。但是我需要解决的问题更简单，因为我无需处理删除 key 和修改 key/value 的操作。所以，resize 过程就只有 0 和 1 两个状态，无需做一个复杂的状态机。

我没有使用 lock free 的算法，是因为我认为只要把读写锁粒度控制的很细，锁内做的事务控制的足够少，性能上并没有劣势。结合我们的实际业务，我并需要实现一个通用的并行 hash map ，可以说这里采用 lock free 毫无优势。锁住后不加其它的锁，也不会有死锁的隐患。改成 lock free 难度并不大，但是要证明实现的正确，却比读写锁要复杂的多。