« 不同虚拟机间共享不变的 Table | 返回首页 | Windows 下 UTF-16 的坑 »

并发 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 难度并不大,但是要证明实现的正确,却比读写锁要复杂的多。

Comments

java的hash是做到了并发读取, 但没有做到无锁写入, 通常的实用情况, 是不可能存在高并发写入同一个 key 的. 不同的key高并发写入是存在的, 但同一个key的高并发写入是不存在的, 即使存在, 也无可避免出现一种情况: N个线程同一写入key为 abc 的value, 那么到底这N个线程, 谁的value留为最新? 这个是计算机无法确定的行为, 因为 线程存在切换, 谁最后领到锁, 谁就是赢家, 但这样的Set, 对Get有什么用? 然后对于并发Set不同的Key来说, 这样分一下粒度的锁, 对于高并发Set来说. 20个桶或者是会分成20份, 但针对两个key均为同一个桶的情况, 还是单线程的形式来走, 只是降低了机率. 不过也足够很多场景下应用了. 搜索了很久, 只要是有关 线程并发, 无锁, 无一例外都是空白闭源, 开源的一般都是整体lock或分体lock的方案.
注意:这是一个为专用需求定制的数据结构,并不是一个通用 hash map 。 1. 写操作是非常少的(相对读)。 2. 只有新增,没有改写。 3. 整个系统只有一个实例。 4. 删除操作不重要,可以延迟处理。 5. rehash 过程和删除清理过程是可控的,可以安排到唯一线程进行。
intel TBB并不能在所有平台使用。。
目前很多读写锁的读锁实现是通过对一个全局的变量做CAS自增,是否并发大了之后,还是会有比较严重的cache一致性的开销,好像之前在哪看过读写锁的多核伸缩性还比不上spinlock。
感觉不大需要自己设计哈,IntelTBB不是有concurrent_unordered_map.h吗?
请问大神: unity2017.2.1用的是simpleframework_UGUI0.4.1导出xcode 运行 1.在release Fastest,Smallest[-Os] LuaDLL.lua_pcall(L,0,-1,-2)闪退 2.在debug None[-o0] 不闪退
学习了,谢谢博主
这是个读写锁,且是完全在用户态实现的。不仅是大多数是读操作,而且是只有可控的单次写锁,即在我可控的时机(主动扩展 slots),明确的只有一个线程会调用写锁。 获取读锁在这种情况下是没有额外成本的。
"这是通过给整个 hash 表加一个读写锁实现的" 我的理解是 给SSM加了一个全局的锁,每次读写都需要require这个读写锁,那会不会对整体还是有影响?还是说因为大多数是读操作,所以require速度很快可以忽略不计?

Post a comment

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