sync.Map是1.9才推荐的并发安全的map,除了互斥量以外,还运用了原子操作,所以在这之前,有必要了解下 Go语言——原子操作
go1.10\src\sync\map.go
entry分为三种情况:
从read中读取key,如果key存在就tryStore。
注意这里开始需要加锁,因为需要操作dirty。
条目在read中,首先取消标记,然后将条目保存到dirty里。(因为标记的数据不在dirty里)
最后原子保存value到条目里面,这里注意read和dirty都有条目。
总结一下Store:
这里可以看到dirty保存了数据的修改,除非可以直接原子更新read,继续保持read clean。
有了之前的经验,可以猜测下load流程:
与猜测的 区别 :
由于数据保存两份,所以删除考虑:
先看第二种情况。加锁直接删除dirty数据。思考下貌似没什么问题,本身就是脏数据。
第一种和第三种情况唯一的区别就是条目是否被标记。标记代表删除,所以直接返回。否则CAS操作置为nil。这里总感觉少点什么,因为条目其实还是存在的,虽然指针nil。
看了一圈貌似没找到标记的逻辑,因为删除只是将他变成nil。
之前以为这个逻辑就是简单的将为标记的条目拷贝给dirty,现在看来大有文章。
p == nil,说明条目已经被delete了,CAS将他置为标记删除。然后这个条目就不会保存在dirty里面。
这里其实就跟miss逻辑串起来了,因为miss达到阈值之后,dirty会全量变成read,也就是说标记删除在这一步最终删除。这个还是很巧妙的。
真正的删除逻辑:
很绕。。。。
Go map实现原理
深入Go的Map使用和实现原理
go 中的 map 也是 hashmap,由哈和(bucket)数组组成,每个 bucket 可以存放若干元素(默认8个),当超过 8 个元素后,hmap会使用extra中的overflow指向新的 bucket 来拓展该bucket;
bucket 数组 tophash 数组 data字节数组 overflow 链表
哈希冲突后的数据结构:
overflow 表示溢出的意思
负载因子用于表示哈希冲突的情况 = 键数量 / bucket 的数量
哈希因子需要控制在合适的大小,超过阙值后需要 rehash
* 哈希因子过小,说明空间利用率低
* 哈希因子过大,说明冲突严重,存取效率低
每个 hash 表的实现对负载因子的容忍程度不同,redis 中负载因子为 1 时就会触发 rehash,因为 redis 的每个 bucket 只能存储一个键值对。而 go 的能存储 8 个,负载因子为 6.5;
4.1 扩容的前提条件
为保证访问效率,当新元素要添加时,都会检查是否需要扩容,扩容实际是空间换时间;
4.2 增量扩容
负载因子超过阙值后,新建一个 buckets,长度为原来的2倍,旧 buckets 的数量逐渐搬迁至新的 buckets 中。
如果数据量较大,采取渐进式hash, 每次访问 map 都会触发一次搬迁 ,每次搬迁2个键值对,搬迁完成后将会删除 oldbuckets;
4.3 缩容
通过不断地删除,键值对集中在一小部分地 bucket 中,overflow 中大部分是空的,经过重新组织后 bucket 的数量会减少,提高访问效率;