原文链接：https://www.slideshare.net/howarddgreen/2007-lock-freehash?from_action=save
由于本人才疏学浅，翻译难免有误，望各位不吝惜指正。
感谢作者给我们带来的基于状态机的高效无锁哈希表。
- 常量时间的键值映射
- 执行高效
- 可以在运行时扩展
- 适合符号表，数据库缓存，网络数据缓存，url缓存等等
- 适合大型商业应用
- 适合大量使用线程的应用
- HashTable
- 单线程，扩展性差
- HashMap
- 高效，但不能满足线程安全
- java.util.concurrent.HashMap
- 使用了内部锁；默认16路并发
- Azul，IBM，Sun出售的机器可能包含超过100个CPU
- Azul的客户在一个应用中可能使用了全部CPU
- Java自带的哈希表对于大量CPU的情况存在扩展瓶颈
- 无锁，即使在哈希表容量大小改变时也不需要锁
- 没有自旋锁
- 不会被阻塞
- 尝试CAS操作的循环次数有限
- 不受其它线程挂起的影响
- 需要原子操作
- CAS(比较并交换)，LL/SC(Load-Linked/Store-Conditional，仅PowerPC支持)或类似指令
- 使用sun.misc.Unsafe进行CAS操作
- 在使用小于32个CPU的情况下进行读操作占比99%的测试比java.util.concurrent略快
- 在使用更多CPU的情况下更加高效(快2倍)
- 即使在4096路并发下
- 比使用默认的并发级别设置快10倍
- 进行读操作占比95%的测试快3倍(快30倍 vs 默认并发级别设置)
- 进行读操作占比75%的测试快8倍(快100倍 vs 默认并发级别设置)
- 扩展至768个CPU，进行读操作占比75%的测试仍表现良好
- 接近硬件带宽极限
- 为什么我们需要一个高效的无锁哈希表
- 无聊的细节
- 为什么要基于状态机
- 哈希表容量改变
- 性能表现
- 问答
- 哈希表：一个键值对容器
- 可以和其它容器协作
- 容器的适应性，锁，瓶颈
- 需要执行高效
- 需要缓存友好
- 我们这里给出了一个Java实现
- 其它语言实现也是完全可行的
- 2的幂大小容量
- 碰撞再次探测
- 再次探测偏移粒度小：缓存友好
- 键和值在同一cache line
- 哈希记录
- 应该将K+V记录在同一cache line上
- 但只使用Java难以做到
- get和put操作不进行分配操作
- 自动调整容量大小
- 可以使用素数表和MOD运算
- 可以获得更好的哈希分布，减少哈希碰撞
- 但MOD运算比AND运算慢30倍
- 可以使用开放链表
- put()需要进行分配操作
- 使用next指针代替探测
- 使用next指针意味着缓存失效
- 如果哈希分布不佳就会导致大量的链表遍历
- 其它变种
- 为什么我们需要一个高效的无锁哈希表
- 无聊的细节
- 为什么要基于状态机
- 哈希表容量改变
- 性能表现
- 问答
- 哈希表操作是否正确
- put，putIfAbsent，change，delete等等
- 使用内存屏障，内存模型，load/store顺序和happens-before证明？
- 通过状态机证明
- 定义所有可能的{Key，Value}状态
- 定义状态机的状态转移
- 表明所有状态合法
- 定义所有{Key，Value}状态和状态转移
- 不需要关心内存顺序
- get可以以任意顺序读取键和值
- put可以以任意顺序修改键和值
- put必须使用CAS来修改键或值
- 但不需要使用double-CAS
- 不需要内存屏障来保证正确性
- 为了更健壮可以使用内存屏障
- 证明简单
- 一个键槽
- null - 空
- K - 键；不能被再次修改
- 一个值槽
- null - 空
- T - 墓碑
- V - 值
- 一个状态是一个{Key，Value}
- 一次状态转换是一次成功的CAS操作
- 设置一个键后，就不能修改
- 也就不可能使用一个错误的键获得值
- 意味着键会泄漏；哈希表可能被死键填满
- 在后面我们介绍如何解决这一问题
- 不能保证执行顺序
- 需要我们自己保证执行顺序和同步
- {null，V}状态的意义
- 表示读取时获得了一个失效的空键
- 可能是预读取了错误的值
- 表示读取时获得了一个失效的空键
- 状态在整个机器范围内不具有一致性
- 不保证可以读取到相同的状态
- 除非在同一CPU上，且没有其它的写入操作
- 当然也不需要状态在整个机器范围内具有一致性
- 考虑一个键退化的情况
- 这和下面这些情况一样
- 单个共享全局变量
- 多读多写，没有同步
- 等等
- 值能够满足happens-before
- java.util.concurrent可以保证这点
- 使用以volatile定义共享全局变量类似的方法
- 在put前写入一个值
- 都可以保证在之后可以get到之前put的值
- 在CAS操作前，需要st/st屏障
- 对于Sparc，X86来说不需要
- 在载入一个值后需要ld/ld屏障
- 对于Azul来说不需要
- 为什么我们需要一个高效的无锁哈希表
- 无聊的细节
- 为什么要基于状态机
- 哈希表容量改变
- 性能表现
- 问答
- 哈希表满了之后需要扩容
- 或进行重探测的次数太频繁
- 改变哈希表大小需要复制存活的键值对
- 同时可以用来清除死键
- 在删除操作之后进行可以起到清理作用
- 可以只在每一次GC进行来节约资源
- 需要内存屏障，happens before
- resize操作和put操作很难并发
- 不能丢掉对旧表的最后一次更新
- 扩展状态机
- 副作用：需要添加mid-resize状态
- 表明改变哈希表容量大小
- 可以和读操作并发，读操作可以帮助进行resize操作，或着只进行读操作
- 可以并行加速resize操作
- 可以渐进进行resize操作，允许只复制一部分
- 当resize操作进行时需要花费额外的时间
- 最后仍会完成操作
- 可以将resize操作堆叠分批执行
- 在旧表上进行get操作
- 除非检测到标记信息
- 在新表上进行put或其它修改操作
- 每次操作都要检查新表
- 写入旧表的操作发生在resize操作之前
- 复制键值对独立于get/put操作
- 复制操作有多种选择
- 在所有可以访问哈希表的线程上，或只在会写入哈希表的线程上，或完全不相干的后台线程上
- X：在复制表时使用的标记
- 表示不在旧表中，请检查新表
- 一个键槽的内容可能是
- null，K
- X - 'use new table'，不属于合法键
- null -> K 或 null -> X
- 一个值槽的内容可能是
- null，T，V
- X - 'use new table'，不属于合法值
- null -> {T，V}* -> X
- 新的状态V'，T' - V，T的初始版本
- 新表的初始值是从旧表直接复制得来的
- 新表中的非初始值是最近的put操作产生的
- 发生在初始值写入之后
- 初始值的复制可以使用2PC方式同步
- 工程实现：包装类(Java)，偷位(C)
- 必须保证复制较晚写入旧表的数据
- 尽量原子地复制
- 复制可能失败
- 但旧表和新表的数据不会因此破坏
- 一个键槽的内容
- null，K，X
- 一个值槽的内容
- null，T，V，X
- T'，V' - T和V的初始版本
- 旧表的数据复制到新表
- 2PC同步
- null -> {T'，V'} -> {T，V}* -> X
- 再次状态机...
- 旧值可能是V或T
- 或者是V'或T'(如果处于嵌套的resize操作下)
- 如果新值不是初始态的就跳过复制
- 说明最近的put操作已经覆盖了旧值
- 如果CAS操作失败
- 说明有put操作或其它复制操作在进行
- 所以可以结束此次复制
- 任意线程可以在任意时间检测到任意状态
- 使用CAS操作转换到下一状态
- 为什么我们需要一个高效的无锁哈希表
- 无聊的细节
- 为什么要基于状态机
- 哈希表容量改变
- 性能表现
- 问答
- 通过插入/查询/删除字符串进行
- 非常紧凑的循环：只包含哈希表上的操作和测试相关代码
- 测试是保守估计
- 使用所有屏障；完全的并发哈希表语义
- 变量
- 99%的get操作，1%的put操作(典型的缓存特征) vs 75/25
- Dual Athalon，Niagara，Azul Vega1，Vega2
- 线程数从1到800
- 非阻塞 vs 并非级别为4096的ConcurrentHashMap
- 1K 条目的表 vs 1M条目的表
- 这是一个更高效的哈希表
- 使用的CPU越多越快
- 在修改操作占比很高的情况下仍非常高效
- 基于状态机
- 没有顺序要求，没有JMM，没有屏障
- 任意线程可以在任意时间检测到任意状态
- 必须假定值可能会在每一步发生修改
- 状态图能够帮助我们编码和调试
- 这一哈希表的实现代码很短小，并且执行高效
- 更进一步
- 通过工具检测状态
- 通过工具编写代码
- 设计思想可以应用在其它数据结构上
- 并发j.u.Vector
- 可扩展近似FIFO工作队列