【介绍一个组件】go: Copy-On-Write map,对读极多和写极少的场景做优化

作者:张富春(ahfuzhang),转载时请注明作者和引用链接,谢谢!


代码请看:https://github.com/ahfuzhang/cowmap

有这样一种场景:数据量不多的map,在使用中读极多写极少。为了在这种场景下做极致的优化,我实现了 copy-on-write 的map:
其实现原理为:所有的读都可以不加锁的并发读取,一旦需要写,则 copy 一份原来的map,在备份上修改,然后通过原子操作把指针切换到新的对象上。

我对比了CowMap(Copy-On-Write Map) 和 sync.Map , 以及普通map + 读写锁三种方式的性能:

Read-write rate Type ns/op
99.99% : 0.01% CowMap 4.649
99.99% : 0.01% map + sync.RWMutex 187.5
99.99% : 0.01% sync.Map 15.06
99.90% : 0.10% CowMap 32.70
99.90% : 0.10% map + sync.RWMutex 159.9
99.90% : 0.10% sync.Map 14.08
99.00% : 1.00% CowMap 303.6
99.00% : 1.00% map + sync.RWMutex 105.7
99.00% : 1.00% sync.Map 14.08

因此,当读的比例超过 99.99%时,CowMapsync.Map 的 3.24 倍。是 map+sync.RWMutex 的 40.33 倍。

不过我认为更好的视线方法,还是应该参考 rust hashbrown 的实现(see: 《Swisstable:C++中比std::unordered_map更快的hash表》),这样有可能实现这样一些优化:

  • 因为hash的结构是平坦的数组,理论上在不扩容和缩容的前提下,读写都能做到无锁
  • 使用simd指令集来搜索位置,能够提供更好的查找速度。

Have Fun. 😃

热门相关:公子别秀   亿万老公,送上门!   九龙神鼎   来自异世界的诺诺   学霸你女朋友掉了