folly::AtomicHashmap源码分析(二)

时间:2021-06-02 10:42:06

本文为原创,转载请注明:http://www.cnblogs.com/gistao/

背景

上一篇只是细致的把源码分析了一遍,而源码背后的设计思想并没有写,设计思想往往是最重要的,没有它,基本无法做整体性的优化或正确的使用,

但是根据结果反推原因是困难的,也极容易不到位,这里‘磕磕绊绊’写下自己的理解,另外对源码里的‘问题’也写出来。

简单

调试一个多线程程序是比较头疼的,而使用atomic来编写一个正确的多线程数据结构更是困难的,出了问题一般都是随机问题,且等着复现看log吧,

所以简单这个特性在设计里应是第一位的。

AtomicHashmap的key只支持int,为什么不像tbb的concurrent_hash_map一样也支持自定义类型的key呢?它完全可以通过把现有的key定位为

纯的状态机,再设置一个字段来保存自定义的key,我想就是为了简单,因为使用者可以自行通过hash算法将自定义的key转换为int来解决。这样还

节省了一个指针空间占用,够用够简单。

28原则

这里说的28原则是指80%的cpu在执行20%的代码。rehash是hashmap必不可失的功能,但它明显不在20%代码之内的范畴。

所以,AtomicHashmap可以不支持传统的rehash,一方面是atomic的能力限制,另一方面是rehash够复杂效率够低,但Facebook的工程师选择了

让80%的cpu执行要够快,而剩余的20%cpu稍低点也可以接受的思路。

AtomicHashmap的rehash类似于dequue的扩充策略,这会有两个结论

  • 当容量未满时,这属于80%的概率事件,依然可以O(1)
  • 当容量满时,这属于20%的概率事件,依然可以O(2),O(3),O(4...)

简单+28原则

AtomicHashmap的冲突解决策略是线性探测,线性探测会因为本次冲突而影响其他key的插入,而拉链法没有这个问题。为什么Facebook的工程师

选择这个呢,我想首先冲突也是属于20%概率事件,那么代码效率稍差也是可以接受的,其次这个拉链其实就是个多生产者多消费者模式下的队列,

参见boost的一个无锁实现,比线性探测复杂多了,而线性探测也有个优点就是局部性好。

O(1)变成O(N)

看个场景

step1:100个并发,每个并发做100次的随机插入,AtomicHashmap的size设置为10w,总共插入14w数据。

step2:2个并发查询,查询的key不存在

step3:cpu idle降为0

folly::AtomicHashmap源码分析(二)

如何解决

通过上一篇的源码分析,得出有三个怀疑点

  • 要查的key发生过冲突,那么查找最好的情况是往后遍历一个或者几个(取决于hash算法和容量大小)找到元素,
    或者发现空元素,然后结束查找;而最坏的情况(map里空间全部被占用)是遍历查找一遍,
    当然这种可能性很小,取决于填充因子和插入的并发度
  • 要查的key没有插入过,那么最好的情况是遇到第一个空元素结束查找,最坏的情况是遍历查找一遍
  • 要查的key已经被删除了,这种情况同上

总结就是空间上空元素的分布很重要,而分布情况有三种

  • 所有元素都被使用,没有空元素
  • 被使用元素集中分布,相应的空元素也集中分布
  • 被使用元素和空元素相隔/均匀分布

后两种分布主要取决于hash算法,好的hash算法能尽量保证每一bit变化的输入反映在输出上。

测试场景使用的hash算法是通用的Murmurhash,此算法效果是比较好的,在实际使用中并不会发生这两种情况,

那么问题就只有第一种分布:没有空元素

insertInternal(KeyT key_in, T&& value) {
......
if (isFull_.load(std::memory_order_acquire))
return false; //满了,不让再插入这个map了 ++numEntries_; //已插入的数量
if (numEntries_.readFast() >= maxEntries_) {
isFull_.store(true, std::memory_order_relaxed); //isfull设置为true
......
}

这是AtomicHashmap的插入逻辑:当插满时,不允许插入。那应该不会出现没有空元素的情况吧?no

maxEntries_为10w,填充因子为0.8,那么元素的容量=12.5w(10/0.8),那么空元素的容量为2.5w(12.5w-10w)。

可是为什么空元素的容量为0呢?

numEntries_为thread_cache_int类型,这个类的大致思想是可以配置一个cache_size,那么访问这个numEntries_对象

的所有线程的局部变量++到cache_size后才会同步给其他线程(即readFast可以获取到)。

比如cache_size配置为1000,线程数为100,那么理论上readFast的最大延迟同步为100*1000=10w。

10w远大于空元素的容量2.5w,即有可能发生实际插入元素已经满了(空元素容量为0),而isFull_依然为false。

遇到这种问题,解决思路是把容量调大。