原文連結：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工作隊列