Advanced Topics in Programming Languages: A Lock-Free Hash Table

编程语言高级专题：无锁哈希表 Cliff Click 博士介绍了一种纯 Java 实现的无锁哈希表，可作为分段锁结构（如 java.util.concurrent.ConcurrentHashMap）的高性能替代方案。该数据结构采用步长为 1 的线性探测开放寻址法，并通过 sun.misc.Unsafe 进行硬件级 CAS 操作，完全消除了全局锁并避免了读端内存屏障。表的变更、扩容以及协同数据迁移依赖于哨兵标记和预备值（primed values），允许并发线程协助完成后台表复制而不会阻碍执行进度。在多达 768 至 800 核的 Azul 硬件上进行的基准测试显示，该算法每秒可支持多达 12 亿次操作，并在传统分段锁因竞争而性能崩塌的场景下实现了接近线性的扩展。 Cliff Click 博士展示了 NonBlockingHashMap，这是一种使用 sun.misc.Unsafe CAS 操作实现的无锁并发哈希表，消除了高并发写入下的分段锁瓶颈。 (0:22) 其正确性是通过详尽的槽位状态机而非传统的 Java 内存模型 happens-before 内存屏障来建模的，从而允许读取时进行原始 CPU 加载，并将一致性开销限制在局部而非整机范围。 (12:18) 在可扩展至 768 到 800 个 Azul CPU 的大规模多核硬件上，该无锁哈希表实现了每秒 12 亿次读取操作以及 1200 万次并发更新，性能优于在写入竞争下出现瓶颈的分段哈希表。 (38:58) 哈希表扩容利用带有哨兵标记和预备值包装器的协同两阶段提交迁移，在不停止操作的情况下将分块复制任务分配给活动的变更线程。 (27:40)

Dr. Cliff Click presents a fully lock-free hash table designed to overcome the concurrency bottlenecks of striped locking on massive multi-core systems. By relying on atomic compare-and-swap operations and formal slot-level state machines rather than memory fences or coarse locks, the design achieves near-linear scalability up to hundreds of processor cores. The Scaling Limits of Striped Locking (0:22) Modern enterprise applications rely heavily on concurrent key-value maps for caching, but traditional synchronization techniques face severe bottlenecks on modern multi-core hardware. Standard Java collections like `ConcurrentHashMap` utilize striped locking—typically 16-way write striping—which Dr. Click points out quickly degrades when systems scale past 100 CPUs, such as the 750-CPU architectures developed at Azul Systems. State-Machine Correctness Without Fences (12:18) To eliminate locks, spin-locks, and synchronization primitives entirely, the hash table operates strictly on atomic compare-and-swap (CAS) instructions. Rather than reasoning through complex language memory models and ordering fences across threads, Click proves algorithmic correctness by modeling slot transitions as an exhaustive state machine where every possible state and interleaving yields a legal result. Dynamic Resizing via Two-Phase Migrations (20:35) Dynamic resizing represents the primary failure mode of most concurrent container designs. Click handles table expansion and tombstones cleansing by treating the resize state as a first-class citizen within the state machine. Transitions rely on sentinel values ('X') to seal completed or empty slots in the old table and temporary 'primed' wrappers in the target array, preventing lost updates from late-arriving writes. Empirical Scaling and High-Contention Workloads (38:58) Under benchmarks evaluating up to 768 to 800 CPUs, Click's non-blocking implementation sustained up to 1.2 billion read operations and 12 million concurrent updates per second on a 99% read mix. In write-heavy scenarios where striped maps seize up—such as 75% reads and 25% writes—the lock-free table maintained 600 million reads and 150 million updates per second. Distributed Accounting and Portability Trade-Offs (49:38) Global operations like `size()` cannot rely on a single variable without inducing severe cache-line bouncing across multi-core chips. Instead, the container employs striped CAS counters that are summed on demand, returning an instantaneous snapshot rather than a transactional invariant. Furthermore, Click deliberately engineered the implementation in pure Java rather than exploiting Azul's custom hardware read barriers or stealing pointer bits in C, prioritizing broad portability so enterprise systems can deploy the data structure across commodity JVMs. While the non-blocking hash table demonstrates linear scaling across massive thread counts, continuous resizing under heavy churn introduces substantial allocation pressure on garbage collectors due to primed wrapper objects. Dr. Click noted that while Doug Lea had shown interest in integrating aspects of the design into Java's standard concurrency package, future work remains focused on formal state verification tools and expanding non-blocking state-machine patterns to structures like dynamic vectors.

Azul Systems 工程师兼前 HotSpot 架构师 Cliff Click 提出了一种纯无锁哈希表设计，该设计放弃传统分段锁与内存栅栏，依托状态机理论与硬件 CAS 指令，在大规模多核系统上实现了线性扩展与高吞吐量。 分段锁在高度并发下的扩展瓶颈 (0:22) 在现代企业级计算中，哈希表广泛应用于缓存系统。然而，旧有方案如 Hashtable 依赖全局粗粒度锁，而标准库的 ConcurrentHashMap 采用 16 路写分段锁机制。Click 指出，当硬件扩展至 100 到 750 个 CPU 时，固定数量的分段锁会迅速沦为严重的性能瓶颈，难以支撑高并发写入。Click 倡导的无锁（Lock-Free）不仅意味着摒弃 synchronized 和 ReentrantLock，而且严格禁止自旋锁等任何可能独占排他资源的机制。这种无锁设计能保证即便某个线程在执行插入或更新途中被终止，其余线程依然可以安全推进，避免系统死锁或内存损坏。在底层实现上，该算法依赖现代硬件广泛支持的单字 CAS（Compare-And-Swap）原子指令，并通过 sun.misc.Unsafe 直接调用。 以状态机替代内存栅栏的正确性证明 (12:18) Click 没有沿用基于 happens-before 关系或硬件内存栅栏的传统并发证明体系，而是将单槽位的读写演进建模为一个有限状态机。算法采用开放寻址法配合步长为 1 的线性探测，保证数据在 CPU 缓存行内连续预取，并限制数组容量为 2 的幂以规避昂贵的取模计算。槽位状态由键与值组合构成，初始为 [null, null]。键写入后永久不可变，值则在有效指针与删除标记 Tombstone 之间转换。所有变更（插入、更新、条件删除）最终均收敛到针对单个槽位的单次 CAS 指令。 由于硬件和编译器的乱序执行，读者可能会先预取值再读取键，从而观察到奇怪的 [null, Value] 状态；状态机将这一情况安全归为缓存未命中，使读写操作无需强制插入内存屏障。Click 强调，算法在单个哈希表内仅提供类似未同步全局变量的单键松弛一致性，并利用弱 CAS（weakCAS）降低开销。唯一的例外是新对象引用的发布，此时必须插入内存栅栏以建立 happens-before 关系，防止读者读取到尚未初始化完成的对象。 两阶段提交与协助式并发扩容机制 (20:35) 动态扩容是无锁哈希表最复杂的环节。当容量耗尽、发生哈希聚集导致探测过深，或大量删除残留死键（Tombstone）时，系统会触发扩容。由于开发者预估容量常出现偏差，该表主动忽略初始容量提示，自适应动态分配。为了在旧表与新表之间安全迁移数据，Click 引入了两阶段提交机制与哨兵状态 X 以及带撇号的“准备状态”（Primed Value，如 V'）。 扩容启动时，多个线程竞争 CAS 安装新分配的数组引用，胜出者确立新表，失败者立即丢弃多余分配。随后，所有触碰哈希表的线程通过协同机制分担固定批次的迁移任务。迁移线程先在旧表槽位 CAS 写入 X 彻底封锁后续写入，同时在新表写入包裹了 Prime 包装对象的 V'；确认封锁完成后再剥离 Prime，还原为常规值。若新表已存在更新的直接写入，旧表的过时数据将被安全丢弃。这种两阶段设计构筑了天然的 CAS 自旋重试边界，仅受未感知扩容的迟到写线程数量限制。 多核基准性能评测与开销权衡 (38:58) 在 99% 读与 1% 写的基准测试中，Click 的实现较配置了 4000 路分段锁的 ConcurrentHashMap 表现更稳定，并在 Azul 拥有 768 至 800 个 CPU 的系统上跑出每秒 12 亿次读操作（对应每秒 1200 万次并发写操作）。在 75% 读与 25% 写的重度写载荷下，分段锁结构彻底停滞，而无锁表仍能维持每秒 6 亿次读和 1.5 亿次写。即使在 100 万个键轮转、仅 1000 个活跃键的高频扩容清理测试中，其吞吐量仍约为分段锁版本的 5 倍。 为避免集中式计数器引发缓存行颠簸，哈希表采用分段 CAS 计数器维护容量，导致 size() 仅能提供瞬时快照而非严格全局事务一致性。虽然算法表现出色，但纯 Java 环境下因缺乏指针位标记技术，必须使用包装对象表示 Prime 状态，导致重度扩容时在 500 线程规模下产生每秒数 GB 的垃圾分配压力。此外，Click 明确表示该表仅扩容而不收缩，这与 ArrayList 和 Vector 等标准集合的设计哲学一致。 Click 总结认为，基于状态机的局部 CAS 迁移模型成功规避了全系统内存排序的复杂性。尽管 Doug Lea 曾对通用哈希码碰撞处理提出考量，Click 预计该算法的变体未来有望纳入 java.util.concurrent 标准库，并计划以开源形式发布该设计。

## Background 该视频由 YouTube 频道 GoogleTalksArchive 于 2012 年 8 月 22 日发布，记录的是 2007 年 3 月 28 日在 Google 举办的 Google Tech Talks 技术讲座。根据页面描述，时任 Azul Systems 首席 JVM 架构师的 Cliff Click 博士在此分享了一种完全无锁的高并发哈希表实现，展示了其在高达 768 颗 CPU 下的线性扩展能力，并提出了一种跳出传统 happens-before 和内存屏障思维、完全基于有限状态机来证明并发正确性的全新视角。 ## TL;DR Cliff Click 博士针对多核环境下 16 路分段锁哈希表在高写入负载下的瓶颈，设计了一种基于开放寻址法、线性探测和单指令原子 CAS 的真正无锁哈希表。他打破了依靠复杂内存屏障推演 happens-before 关系的传统并发证明方式，转而构建了一个能够天然容忍硬件乱序与投机预取的有限状态机。通过引入带撇标记（Prime Values）的两阶段提交协作搬迁机制，该哈希表实现了完全并发的增量式安全扩容与死键清洗。基准测试表明，该算法在通用 x86 以及多达 768 核的 Azul 硬件上展现出接近线性的吞吐扩展表现，并具备被纳入官方 Java 并发库的前景。 ## Atmosphere & style 整场讲座洋溢着资深系统底层专家的硬核幽默与从容自信。Cliff Click 讲课风格平实质朴、直击本质，面对白板上复杂纠缠的多状态转移图，他总能用“状态机无论从哪开始都合法”的通透视角化繁为简。台下的 Google 工程师提问锋利、直击要害，多次在指针打标、GC 屏障与并发 OOM 等边界条件上展开激烈交锋，而 Cliff 则在会心一笑与生动调侃中举重若轻地拆解疑问，呈现出一场兼具学术严谨性与工业实战美感的顶级系统架构盛宴。 ## Bulletin - [02:15](https://www.youtube.com/watch?v=HJ-719EGIts&t=135s) 前 HotSpot 首席架构师 Cliff Click 提出了全无锁的 Java 并发哈希表，在多达 768 核的超多核硬件上突破了 ConcurrentHashMap 分段锁的性能瓶颈，最高跑出每秒 12 亿次操作的吞吐量。 - [12:18](https://www.youtube.com/watch?v=HJ-719EGIts&t=738s) 该算法放弃了传统 JMM 中复杂的 happens-before 内存屏障推演，转而使用有限状态机证明每个并发组合的合法性，从而规避了昂贵的机器级缓存一致性与读端内存屏障。 - [29:07](https://www.youtube.com/watch?v=HJ-719EGIts&t=1747s) 扩容机制采用类似复制式垃圾回收与两阶段提交的协作搬迁策略，通过引入哨兵标记 X 与 Prime 包装值，使多线程能够在无锁状态下协同完成旧表向新表的数据迁移。 - [38:58](https://www.youtube.com/watch?v=HJ-719EGIts&t=2338s) 在极端写入压测下（如 75% 读、25% 写或只插删的持续扩容场景），即便配置了 4,000 路分段锁的并发哈希表性能彻底崩盘，该无锁实现依然能维持线性伸缩并快出数倍。 ## Key takeaways - [02:15](https://www.youtube.com/watch?v=HJ-719EGIts&t=135s) 当硬件扩展至数百核时，采用 16 路甚至 4,000 路分段锁的 ConcurrentHashMap 会在写入密集场景下因锁争用彻底沦为系统性能瓶颈。 - [02:15](https://www.youtube.com/watch?v=HJ-719EGIts&t=135s) 本算法践行严格的 Lock-Free 定义：严禁使用任何互斥锁或自旋锁，且具备强进度保证，即使某个线程在更新中途中断，其他线程仍能正常安全推进。 - [06:29](https://www.youtube.com/watch?v=HJ-719EGIts&t=389s) 底层工程上采用 2 的幂次封闭哈希表与步长为 1 的线性探测开放寻址法，规避昂贵的取模指令并最大化利用 CPU 缓存预取，且实现写操作全路径零内存分配。 - [10:24](https://www.youtube.com/watch?v=HJ-719EGIts&t=624s) 所有插入、修改、删除及条件变更在底层统一抽象为针对槽位的单条 CAS 操作，删除则通过写入 Tombstone 墓碑值实现逻辑删除。 - [12:18](https://www.youtube.com/watch?v=HJ-719EGIts&t=738s) 摒弃传统内存屏障与 happens-before 证明，通过定义有限状态机证明任何瞬时观察到的状态组合均合法，彻底解除了单表内读写操作的强顺序约束。 - [14:14](https://www.youtube.com/watch?v=HJ-719EGIts&t=854s) 槽位确立键不可逆原则：Key 一旦通过 CAS 写入槽位便终身不变且永不擦除，彻底杜绝并发下错配键值的竞态可能。 - [16:06](https://www.youtube.com/watch?v=HJ-719EGIts&t=966s) 硬件读乱序可能导致读端观察到非空 Value 但 Key 仍为 null 的奇特状态，状态机将其直接统一判定为合法未命中（Miss）。 - [18:41](https://www.youtube.com/watch?v=HJ-719EGIts&t=1121s) 普通的 CAS 并不等同于 volatile 屏障，但向哈希表发布新对象值时仍需确保 happens-before 可见性，避免其他线程读到未初始化的脏对象。 - [21:58](https://www.youtube.com/watch?v=HJ-719EGIts&t=1318s) 扩容被建模为状态机的一个常规合法中间态，所有并发读写线程均可通过分摊固定份额的拷贝任务来协作搬迁数据，避免长时间单点停顿。 - [29:07](https://www.youtube.com/watch?v=HJ-719EGIts&t=1747s) 扩容通过哨兵标记 X 封锁旧表槽位，并借助带撇值（Prime Values）实现两阶段提交，确保旧表上的迟到写入能够被可靠捕捉或被新表覆盖。 - [34:47](https://www.youtube.com/watch?v=HJ-719EGIts&t=2087s) 为了保持标准纯 Java 代码的跨平台可移植性，该算法采用私有包装对象配合快速 instanceof 检查来模拟带撇标记，而非依赖底层硬件位偷取（Bit-stealing）。 - [44:36](https://www.youtube.com/watch?v=HJ-719EGIts&t=2676s) 哈希表刻意忽略调用者指定的初始容量建议，以自适应自动扩容规避用户预估失误导致的内存灾难或海量小实例造成的百倍内存浪费。 - [49:38](https://www.youtube.com/watch?v=HJ-719EGIts&t=2978s) 为避免全局计数器破坏并发伸缩性，哈希表采用分段 CAS 计数器维护 size，导致并发场景下 size() 返回的是惰性求和而非强一致瞬态快照。 - [49:38](https://www.youtube.com/watch?v=HJ-719EGIts&t=2978s) 哈希表根据槽位利用率阈值以及探测链过长的惩罚来触发翻倍扩容，但工程上明确放弃支持缩容设计，认为缩容在实际工作负载中得不偿失。 - [56:00](https://www.youtube.com/watch?v=HJ-719EGIts&t=3360s) 并发扩容时多线程竞争分配新数组，以单个原子 CAS 安装决出胜负，失败者立即丢弃分配的大数组并在后续 GC 中低成本回收，具备天然的 OOM 容错韧性。 ## Detailed walkthrough ### [00:22](https://www.youtube.com/watch?v=HJ-719EGIts&t=22s) 开场介绍与演讲主题 Google 的技术讲座主持人向观众隆重介绍了演讲嘉宾 Cliff Click 博士。主持人戏称 Cliff Click 是“住在街对面”Azul Systems 的特邀嘉宾，专注研发拥有超多处理器的超级计算机系统；在此之前，他曾任 Sun Microsystems 的 HotSpot 虚拟机首席架构师，目前在 Azul 负责类似的核心虚拟机架构工作。本次讲座的主题是他在 Java 中构建高可扩展性无锁哈希表（Lock-Free Hash Table）的实战经验。 Cliff Click 上台后幽默地调侃自己“跟上了时代的步伐”：他在一周前刚刚开通了自己的个人博客，这正反映了他做事的速度。他明确了本次演讲的两大核心主题： 1. 深入剖析无锁哈希表（Lock-Free Hash Table）的具体实现； 2. 探讨一种完全不同的并发算法思考方式。 哈希表本质上是提供常数时间复杂度（$O(1)$）的键值映射（Key-Value Mapping），但借助这种机制，开发者可以在运行时动态定义和扩展任意映射函数。在大规模企业级应用中，哈希表几乎无处不在，最常见的用途就是构建各种缓存范式（内容缓存、Web 资源缓存、数据库访问缓存等）。然而，这类企业应用本身既极其庞大，又高度并发，传统的哈希表极易成为整个系统的伸缩性瓶颈。 ### [02:15](https://www.youtube.com/watch?v=HJ-719EGIts&t=135s) 并发哈希表的瓶颈与“无锁”的严格定义 在 Java 生态中存在几种广为人知的哈希表实现： - 老旧的 `Hashtable`（全局锁同步，并发度极差）； - 完全非线程安全的 `HashMap`； - `java.util.concurrent` 包下的 `ConcurrentHashMap`。 `ConcurrentHashMap` 在内部采用了 16 路分段锁（16-way striping），其并发机制是读取操作完全无锁，但写入操作必须争抢这 16 把锁之一。Cliff Click 指出，在当时的硬件环境下，拥有超过 100 颗 CPU 的机器已经很常见，而在 Azul Systems，他们制造的机器已经拥有高达 750 颗 CPU，且客户的真实工作负载确实在同时跑满这些核心。在这种超多核架构下，仅仅 16 个写锁的分段哈希表瞬间就会沦为灾难性的性能瓶颈。 ```mermaid flowchart TD accTitle: 并发哈希表并发策略对比 accDescr: 对比传统分段锁哈希表在写操作时的锁竞争瓶颈与真正无锁哈希表的自由写入机制 subgraph StripedLock["ConcurrentHashMap (16路分段锁)"] W1["并发写入 1..N"] --> L["16 个写锁桶 (Stripes)"] L -->|"严重锁争用 (750 核场景)"| Bot["吞吐受限瓶颈"] end subgraph LockFree["Cliff Click 无锁方案"] W2["并发写入 1..N"] --> CAS["原子 CAS 状态翻转"] CAS -->|"无阻塞 / 永不休眠"| Scale["线性伸缩 (768 CPU)"] end ``` 这促使 Cliff Click 探索并实现了一个完全无锁的哈希表。他特别强调了本设计中“无锁（Lock-Free）”的绝对定义： - 不允许存在任何形式的锁：不仅仅是摒弃 `synchronized` 关键字或 `java.util.concurrent.locks`，自旋锁（Spinlock）以及任何“获取共享资源并长期持有”的机制也全部被严格禁止； - 具备强进度保证（Progress Guarantee）：即使某个线程在执行表插入或删除等变更操作的中间状态被强制杀死，系统中的其他所有线程也绝不会被挂起或产生死锁，整个哈希表的数据结构完好无损，其余线程依然能继续安全推进。 Cliff Click 阐述其底层核心依赖于原子更新指令，并在现场调查了多少人了解 CAS。针对部分不熟悉的听众，他详细解释了 CAS（Compare-and-Swap）： - CAS 是所有现代 CPU 的原子操作基石，它会先检查内存中某处的值是否等于预期值，如果相等则执行更新并成功返回；如果不等则放弃更新并返回失败报告； - 系统的锁和并发基础原语全部构筑在 CAS 之上； - 尽管不同硬件架构存在差异（例如 PowerPC 采用 Load-Link / Store-Conditional，即 LL/SC），但 CAS 广泛存在于 x86、SPARC、Azul、Itanium 等几乎所有主流现代架构中。在 Java 层面，可以通过 `sun.misc.Unsafe` 直接调用底层的 CAS 指令操作内存对象。 ### [05:01](https://www.youtube.com/watch?v=HJ-719EGIts&t=301s) 性能指标与极端压测表现 仅实现“无锁”在工程上是远远不够的，无锁哈希表必须在实际运行速度上超越加锁方案。许多无锁算法理论优美，但在底层工程实现中复杂度极高，常数开销（Constant Factors）巨大，反而导致实际性能暴跌。Cliff Click 对比了自己的实现与行业标杆 `java.util.concurrent.ConcurrentHashMap`： - **99% 读、1% 写的缓存基准**：在常规 CPU 数量下，该无锁哈希表不仅打平，甚至比 `ConcurrentHashMap` 还要快 10% 左右（99% 读是绝大多数 Web / 数据库缓存系统的典型真实比例）； - **提升写比例（95% 读、5% 写）**：随着写入操作增加，分段锁的冲突开销迅速显现，而该无锁哈希表拉开显著的性能优势； - **纯写入极端工况（100% 插入/删除，读比例接近 1%）**：由于完全摒弃了写锁竞争，性能依然几乎不发生严重退化，在超多核心机器上展现出接近线性的横向扩展能力。 Cliff Click 强调：“它伸缩得非常好，基本上是线性伸缩的，在执行更新操作时，它的伸缩性绝对比我见过的任何其他实现都要好。”（“it scales extremely well it scales basically linearly and it certainly scales better than anything else I've ever seen for doing updates”） ### [06:29](https://www.youtube.com/watch?v=HJ-719EGIts&t=389s) 底层工程设计：封闭式寻址与缓存行对齐 在进入核心并发证明之前，Cliff Click 先介绍了哈希表的“非核心工程细节”。他提到，如何保证无锁状态下并发读写 key-value 对的安全性是本次讲座的理论核心，但容器本身的内存布局工程学同样决定生死，否则常数因子的开销就会彻底拖垮算法。 为了对 CPU 缓存友好（Cache-Aware），他做出了以下核心工程权衡： 1. **采用 2 的幂次大小的封闭式哈希表（Closed, Power-of-Two Hash Table）**： - 传统 `Hashtable` 使用素数表长并通过取模运算（`%`）计算索引，但取模指令极其昂贵，其耗时甚至超过了 L1 缓存未命中、L2 缓存命中的代价； - 2 的幂次大小使得哈希槽位映射可以通过极快的位掩码（`& mask`）完成； 2. **开放寻址法（封闭哈希）替代链地址法（桶链表）**： - 发生冲突时不使用链表串联，而是直接在数组内部重新探测（Reprobe）； - 使用步长为 1（Stride-1，即线性探测 Linear Probing）进行重探测。因为这让哈希冲突转化为线性的内存连续扫描，相比于在堆中穿梭遍历链表节点，具有远为优越的 CPU 缓存预取与命中表现； 3. **极简读写路径与零内存分配**： - 将 Key 和 Value 紧密结合，甚至将其尽力排布在同一缓存行（Cache Line）上； - 在执行 `put` 写入操作时，全路径实现零内存分配（No allocation on a put）； - 支持自动动态扩容（Auto-resize），完全忽略用户传入的初始大小建议，在运行中自适应增长。 Cliff Click 展示了其内部极简的 `get` 查找核心逻辑代码框架： ```java // 核心读取操作伪代码逻辑 int h = hash(key); while (true) { int idx = h & mask; Object k = getKey(idx); // 内部仅为一次原子 load 指令 if (k == null) return null; // 目标不存在，直接未命中 if (k.equals(key)) { return getVal(idx); // 内部仅为一次原子 load 指令 } h = h + 1; // 步长为 1 的线性探测 } ``` 他解释道，整个 `get` 函数执行极其迅捷的关键在于：`getKey()` 和 `getVal()` 在底层仅仅对应一条简单的内存加载（Load）指令，没有任何同步锁开销与间接指针跳转。 在结束这些工程实现细节的讲解后，Cliff Click 向现场观众征询是否有关于哈希表基本构造的疑问，现场听众随即提问，核心关注点是否主要在于将查找（Lookup）操作的速度优化到极致。 ### [10:24](https://www.youtube.com/watch?v=HJ-719EGIts&t=624s) 统一的 Put 操作语义与延迟维护的 Table Size Cliff Click 解释道，虽然他的 `put` 操作测出来极快，但这并非最初的设计首要目标。最根本的初衷是：在面临海量并发读请求（`get`）的同时，依然能够稳定支撑相当高吞吐量的写入操作。在底层实现中，无论是新键插入、更新已有键的值、删除、还是带条件的 `putIfAbsent`、匹配旧值才更新或删除，所有对哈希表的变动（Mutation）全都被归为广义的“put”。 在代码的最终执行点，所有写操作最终都会汇聚到同一条 CAS（Compare-And-Swap）指令上。正是这“一招鲜”的操作，同时统一覆盖了插入、更新、删除与各类条件修改。现场有听众提问删除与修改该如何处理，以及如何维护表的元素总数（size）。Cliff Click 明确表示，所有修改操作在底层语义上是完全等价的，走的是同一条代码路径。 针对 `size` 的维护，Cliff Click 强调该哈希表旨在作为 `java.util.HashMap` 或 `java.util.concurrent.ConcurrentHashMap` 的无缝替换（Drop-in replacement），因此必须实现 `size()` 方法。在并发算法中，元素计数的维护往往是“惰性”的：单线程内能立即保证读到自身最新的修改，但跨线程之间则是硬件层面对不相交写入（Disjoint writes）进行异步追赶，展现出一种最终一致性的惰性同步。 ```mermaid flowchart TD accTitle: Unified Put Mutation Flow accDescr: All table mutation operations funnel into a single CAS instruction to update values. subgraph Mutations["各类表修改请求"] M1["插入 (Insert / putIfAbsent)"] M2["更新 (Update)"] M3["删除 (Delete)"] M4["条件变更 (Conditional Put/Delete)"] end subgraph CoreEngine["底层核心引擎"] CASNode["单条 CAS 指令原子写入"] LazySize["惰性计数维护 (Lazy Size)"] end M1 --> CASNode M2 --> CASNode M3 --> CASNode M4 --> CASNode CASNode --> LazySize ``` ### [12:18](https://www.youtube.com/watch?v=HJ-719EGIts&t=738s) 跳出内存屏障陷阱：用状态机证明正确性 传统的并发算法在证明正确性时往往极为痛苦。学者和工程师通常依赖于复杂的内存屏障（Fencing）推演，或是搬出编程语言规范层面繁琐的“Happens-before”内存模型（如 Jeremy Manson 讨论的 Java 内存模型）。针对这种现状，Cliff Click 提出了截然不同的解决思路：放弃纠缠内存屏障和读写重排，转而通过构建一个有限状态机（Finite State Machine）来保证正确性。 “Instead I'm going to prove things via a state machine that is, I'm going to define a pile of states and some transitions that together makes a state machine and then I'm just going to show that all states are legal and I don't care what state you start in or what state you end up in you get something legal out of it.”（“相反，我打算通过状态机来证明：定义一堆状态和状态转移构成状态机，然后证明所有状态都是合法的；我根本不管你从哪个状态开始、最终落到哪个状态，你得到的结果全都是合法的。”） 这种设计的巨大威力在于彻底解除了对内存访问顺序（Memory Ordering）的严苛要求： - 读操作（`get`）可以以任何次序读取键（Key）和值（Value），读代码中没有任何屏障指令。 - 即便编译器不做指令重排，现代 CPU 硬件也会为了性能自由重排 Load 指令或进行投机预取（Prefetch）。 - 既然读端完全能容忍乱序，写端（Put）同样不再需要强顺序约束，直接通过 CAS 推进状态转移即可。 - 无论硬件或编译器如何重排读写，每次读取到的状态组合在状态机内都有定义且合法，因此无需昂贵的内存屏障就能保证逻辑正确。 ### [14:14](https://www.youtube.com/watch?v=HJ-719EGIts&t=854s) 键值状态转移与插槽不可逆原则 在哈希表的基础槽位中，单个键值对的状态由键与值两部分的组合决定。Cliff Click 确立了一条铁律：**键一旦写入槽位，就永远不再改变、永不擦除**。这是杜绝并发下“给错误的键匹配了错误的值”的核心基石。值的演变则通过特定哨兵来控制： - **Key 的取值**：要么为 `null`（空槽），要么为某个具体不变的键对象。 - **Value 的取值**：要么为 `null`（尚未填入值），要么为合法的值对象，要么为墓碑（`Tombstone`，代表已删除）。 - **状态转移**：仅在 CAS 操作原子成功时触发。 在初始状态下，槽位为 `[Key: null, Value: null]`。当线程通过 CAS 成功将 `null` 替换为新键时，由于 CAS 杜绝了数据竞争，该线程确切知晓自己赢得了该槽位的终身所有权。随后，该槽位的值通过后续 CAS 填入真实对象；修改操作直接在槽位内原地 CAS 变更对象指针；删除操作则是向槽位内打入一个墓碑（`Tombstone`）；若后续又有对该键的插入操作，则通过 CAS 将墓碑替换回新值，实现键的“复活”。 ```mermaid flowchart LR accTitle: Key-Value Slot State Machine accDescr: Transitions between states within a single table slot during mutation. Init["[null, null] (初始空槽)"] KeySet["[Key, null] (CAS 占键成功)"] Active["[Key, Value] (正常有效数据)"] Deleted["[Key, Tombstone] (逻辑删除)"] Init -->|"CAS: null → Key"| KeySet KeySet -->|"CAS: null → Value"| Active Active -->|"CAS: Value → NewValue"| Active Active -->|"CAS: Value → Tombstone"| Deleted Deleted -->|"CAS: Tombstone → NewValue"| Active ``` - 现场有听众立刻敏锐指出：如果只用墓碑而不回收键，频繁插入和删除将导致垃圾收集器（GC）永远无法回收这些键，最终造成内存泄漏。 - Cliff Click 笑着回应：“You're about two slides ahead of me.”（“你把我想讲的提前了两页 PPT。”），并承诺随后会专门讲解如何通过表迁移和清洗机制来释放这些残留的死键。 ### [16:06](https://www.youtube.com/watch?v=HJ-719EGIts&t=966s) 读乱序下的奇异步态与全局一致性解耦 在枚举所有状态组合时，Cliff Click 发现了一个奇特的状态：`[Key: null, Value: 非 null]`。在正常的写路径上，这种状态在逻辑上绝不会被产生，因为写端一定是先 CAS 写入 Key，再去 CAS 写入 Value。然而，硬件级别的读乱序与数据预取却会让读线程看到这一幕。 读线程在执行 `get` 时，可能硬件投机预取了该槽位的 Value，但紧接着去读 Key 时读到的却是写线程尚未提交完毕的 `null`。这种情况下，预取出来的 Value 对应的是未知甚至尚未关联的垃圾数据。在状态机模型中，只要 Key 为 `null`，该槽位就直接被读端视作未命中（Miss）。这个状态并非代码设计出来的，而是他在穷举所有排列组合建立状态机时“多出来”的一个边缘状态，经过反向推导，精准解释了底层硬件读乱序的实际物理表现。 进一步地，Cliff Click 指出，这个并发哈希表从不承诺维持全局一致性状态（Machine-wide coherent state）。在没有同步锁保护的多核系统上，针对同一个键发生无序并发更新时，不同 CPU 核心因本地硬件缓存刷新快慢与读取顺序差异，可能会在同一时刻观察到不同的值序列。这完全符合 Java 规范允许的语义，甚至比大多数语言的并发保证都要严格。他将这种场景类比为： - 假设哈希表退化到只有一个键。 - 该设计所提供的保证，完全等价于多个读写线程在没有任何同步（Unsynchronized）的情况下并发访问一个共享的全局变量 `X`。 ### [18:41](https://www.youtube.com/watch?v=HJ-719EGIts&t=1121s) 现场争辩：Weak CAS 与 Volatile 发布语义 探讨到此时，现场听众展开了交锋，有听众提出质疑：既然使用了 CAS 操作，那它难道不具备 Volatile 的读写内存屏障语义吗？ “No, CAS does not give you volatile semantics.”（“不，CAS 并不必然提供 volatile 语义。”）Cliff Click 纠正道。他指出，这完全取决于具体平台的 CAS 实现版本。以 Azul Systems 自身的定制硬件系统为例，底层 CAS 默认是不带内存屏障的，除非指令显式要求加屏障；不带屏障的 CAS 开销要廉价得多，而当前哈希表的键写入状态流转在算法层面恰恰不需要任何屏障。在 Java 的底层并发支持中，这种操作对应的是不带全屏障保证的“弱 CAS”（Weak CAS）。 然而，Cliff Click 随后补充，对于“值”（Value）的发布，通常确实需要更严格一点的语义——即 Happens-before 关系。这是为了解决经典的“安全发布”问题： - 线程 A 在内存中实例化了一个新对象，填充了其内部字段。 - 线程 A 将指向该对象的指针写入哈希表的 Value 槽位。 - 线程 B 从哈希表中读出这个指针，并解引用去访问该对象内部的字段。 如果没有 Happens-before 屏障，硬件可能会导致线程 B 读到了非空的对象指针，却在访问对象内容时看到了未初始化的脏数据。因此，必须在 Value 发布时建立起恰当的可见性边界，确保对象内部状态在跨线程读取前已完全构造完毕。 ### [19:46](https://www.youtube.com/watch?v=HJ-719EGIts&t=1186s) 内存屏障与并发扩容的挑战 在并发编程中，要建立值之间的先行发生（happens-before）关系，其语义本质上与 `volatile` 关键字所提供的保证相同。Cliff Click 指出，如果省略 `volatile`，当你写入一个对象并将其引用推入某个全局共享变量时，其他线程在读取时完全无法保证能看到刚刚写入的内容。这在经典模式中被称为双重检查锁定（double-checked locking）习惯用法；在没有 `volatile` 支持前，这种做法在 Java 中完全是破碎的。因此，为了在此处确立正确的 happens-before 关系，必须在算法中引入内存屏障（fence）。这是该哈希表实现中第一次显式需要 fence，而在硬件层面实际派发的屏障语义，则完全取决于底层的具体硬件架构及其提供的硬件内存模型。 在此之前讨论的都是简单的 `get` 和 `put` 操作，而真正的重头戏在于如何实现完全并发的扩容（concurrent resizing）。Cliff Click 坦言，在此处状态机的设计将面临真正的考验：“这也是我能找到的所有其他并发哈希表算法基本上都……我想说败下阵来，或者变得极其丑陋的地方。我这里的做法也会稍微有一点丑陋，但绝不会像我见过的其他方案那样丑陋。” 哈希表需要扩容的场景主要有三类： 1. 初始分配的 2 的幂次方大小过小。哈希表通常从极小的容量启动（因为大部分哈希表实际只存放少量元素），随着数据填满必须翻倍。 2. 哈希函数质量较差，导致大量碰撞与反复重新探测（reprobing）。 3. 表中积累了过多的墓碑（dead keys / tombstones），需要将其清理出去。这种情况下并不改变表大小，而是“清洗（cleanse）”——将存活数据拷贝到同等大小的新表中，死数据自然被剔除。 在不同表之间（between the tables）进行拷贝时，必须依靠 fence 来协调。整个设计中最棘手的问题，在于如何正确捕捉“旧表上正在发生的最后一次写入”与“拷贝线程向新表搬迁数据”之间的并发竞争（race）。 ```mermaid flowchart TD accTitle: 哈希表并发扩容触发与数据搬迁概览 accDescr: 展示哈希表扩容的三种触发条件以及旧表向新表并发搬迁时的数据状态流转 subgraph Triggers["扩容与清洗触发条件"] T1["表已填满<br/>（容量不足）"] T2["哈希碰撞严重<br/>（探测链过长）"] T3["死键过多<br/>（积累大量墓碑）"] end subgraph Migration["表间数据搬迁"] OldTable["旧哈希表 (Old Table)<br/>含存活项与墓碑"] Fence["内存屏障 (Memory Fence)<br/>保障 happens-before 顺序"] NewTable["新哈希表 (New Table)<br/>扩容翻倍或清洗同容"] end Triggers --> OldTable OldTable --> Fence Fence -->|"只拷贝存活键值对<br/>剔除墓碑"| NewTable ``` --- ### [21:58](https://www.youtube.com/watch?v=HJ-719EGIts&t=1318s) 扩展状态机与协作式数据搬迁策略 为了支撑并发扩容，Cliff Click 扩展了原有的状态机，将“扩容中（mid-resize）”本身也视为一种完全合法的内部状态。这种架构使得扩容过程完全无锁且高度并发： - 读者可以继续直接读取处于半搬迁状态的旧表并立即返回； - 线程也可以选择先协助搬迁部分数据，再去执行自己的操作； - 扩容可以并行化、增量化执行，甚至在理论上允许嵌套/堆叠的多重扩容（stacked partial resizes）。 虽然扩容期间会引入一层间接访问开销，促使系统希望尽快完成扩容，但在搬迁过程中，所有并发操作都可以按照各自的节奏推进。在具体协调逻辑上，`get` 操作默认直接在旧表上进行，直到碰到哨兵（Sentinel）；而 `put` 或其他修改操作每次都必须检查是否存在新表。一旦发现新表存在，写操作必须跳转到新表执行，并在旧表与新表之间插入 fence。依靠这道 fence，旧表上的最后一次写入得以在 Java 内存模型层面上严格 happens-before 扩容搬迁操作。 对于数据搬迁的启发式策略（heuristics），系统提供了极大的灵活性： - **全员协助策略（当前采用）**：任何触碰哈希表的线程（无论是执行 get、put、delete 还是 insert），都必须先分摊固定份额（constant amount）的拷贝任务，然后才能执行自己的业务逻辑。这确保了每个线程在扩容期间只会被阻滞一个固定时间片，而不是承担从 1MB 复制到 2MB 的全量开销。 - **纯写者协助策略**：仅让执行写入的线程承担拷贝工作，从而保证读者的极致低延迟。 - **后台线程协助策略**：在多核硬件资源充足的环境下，唤醒不相关的后台工作线程异步完成表拷贝。 --- ### [24:00](https://www.youtube.com/watch?v=HJ-719EGIts&t=1440s) 哨兵标记 X 与扩容槽位状态流转 扩容的核心机制是引入了一个名为 `X` 的哨兵状态（Sentinel），其语义是“数据不在此处，请前往新表”。通过该哨兵，线程无需在每个操作中反复全局轮询是否存在新表；同时，它也精确表征了槽位在扩容过程中的中间态——某些槽位尚留在旧表，某些槽位已经复制到了新表，而已经复制到新表的旧槽位则会被打上 `X` 标记进行覆盖封死（stomp）。 键槽位（Key Slot）的流转逻辑随之发生变化：它原本只能从 `null` CAS 到具体的 `Key`，现在还可以从 `null` CAS 到 `X`。一旦一个键槽位被置为 `X`，就意味着该槽位已被宣告作废，迟到的插入操作（late arriving insert）再也无法写入旧表，必须强制转去新表。值槽位（Value Slot）也是如此，在经历若干次插入（写入具体值）与删除（写入墓碑 Tombstone）之后，最终会被标记为带 `X` 的状态，表示“该槽位已复制完毕，旧表禁止写入，请去新表”。 整个扩容状态机在原有模型的基础上，在右侧新增了两个关键状态： 1. **空槽位标记封死**：直接将一个空的键槽位标记为 `X`，彻底阻止新键被插入到旧表中。 2. **存活项复制封死**：将已存在的键值对标记为 `X`，表明该项已经成功拷贝至新表，任何后续访问旧表的线程都会意识到自己“找错了表”。 ```mermaid flowchart LR accTitle: 槽位扩容状态流转图 accDescr: 展示键槽位与值槽位在常规操作与遭遇扩容哨兵 X 时的转换路径 subgraph KeySlot["键槽位 (Key Slot)"] KNull["null (空槽位)"] KVal["Key (写入具体键)"] KX["X (哨兵标记：禁止新插入)"] KNull -->|"CAS 写入键"| KVal KNull -->|"扩容封死"| KX end subgraph ValueSlot["值槽位 (Value Slot)"] VVal["Value (有效值)"] VTomb["Tombstone (墓碑/已删除)"] VX["X (哨兵标记：已拷贝至新表)"] VVal <-->|"并发 put / delete"| VTomb VVal -->|"拷贝完成封死"| VX VTomb -->|"拷贝完成封死"| VX end ``` 如果按照组合计算，矩阵中存在 3 × 4 = 12 种状态组合，其中某些状态在算法中已不可能发生，另一些则是无趣的未命中状态（如 get 读到 X 时立即得知需要去新表查找）。 --- ### [26:06](https://www.youtube.com/watch?v=HJ-719EGIts&t=1566s) 链式扩容与并发写入竞争处理 Cliff Click 深入剖析了“链式/堆叠扩容（chain / stacked resizes）”的场景。在算法设计之初，堆叠扩容在理论和功能上是完全可行的：线程如果访问最老的表发现 `X`，就顺藤摸瓜跳到下一层表；如果下一层表也在扩容并打上了 `X`，就继续向上跳转。这种情况经常发生在极端并发压力下： - 例如 700 多个线程同时扑向一个刚初始化的空表（默认最小容量可能只有 32 槽）； - 上百个线程瞬间执行并发 `put`，原表刹那间被填满； - 线程立刻开始搬迁到两倍容量的新表，但新表瞬间又被填满； - 这种连锁反应可能导致表连续翻倍 5 次，才能完全容纳这 750 个并发并发写入。 虽然链式扩容在逻辑上运转完备，但从性能角度出发，Click 最终选择的启发式策略是强制要求旧表在创建下一个新表之前必须被完全清理完毕。通过强制线程在推进时分摊固定的拷贝开销，换取了系统实现的整洁与确定性。 在展开具体的状态流转微观步骤时，包含以下几种核心情形： 1. **空槽位拦截**：当试图拷贝一个尚未被占用的空槽位时，通过 CAS 将其置为 `X`。如果 CAS 成功，证明在此期间没有任何键插入进来（若有并发键写入，CAS 必将失败）。 2. **死槽位封锁**：对于旧表中已经带有墓碑的死槽位，只需就地将其打上 `X` 标记，宣告该死槽位彻底作废，禁止后续复用；后续若有对该键的重新插入，必须强制去新表。 3. **新旧值冲突与时序仲裁**：最复杂的情节发生于旧表中有值，而新表中同样已经出现了该键的值。Click 强调，借助 Java 内存模型的 happens-before 语义，可以证明新表中的更新（记为 $V_2$）在时序上必定晚于旧表中的值。这是因为执行 `put` 的线程必须先检查扩容标记，一旦它在旧表之外的新表进行了写入，说明该更新是一个更新的并发写入。此时，数据拷贝流程完全可以直接忽略旧表中的旧值，旧值已被新表的竞争写入安全覆盖（stomped）。 - 在扩容期间，每个访问哈希表的线程承担固定常量级的拷贝开销，避免长时间停顿。 - 链式扩容机制允许应对突发数百个并发线程瞬间冲垮小容量表的极端场景。 - 借助 fence 建立的 happens-before 屏障，旧表残留写入与新表并发 put 发生竞争时，新表数据在时序上始终占优，保证了数据覆盖的确定性与一致性。 ### [29:07](https://www.youtube.com/watch?v=HJ-719EGIts&t=1747s) 两阶段提交与带撇标记（Prime Values） 为了在无锁哈希表扩容时把旧表的数据安全搬移到新表，Cliff Click 引入了一种类似两阶段提交（two-phase commit）的机制，通过“带撇值”（primed values，如 $V'$ 或 $T'$）来区分数据的生命周期。任何直接插入新表的操作都发生在扩容流程启动之后，因此新表里原生的、不带撇的值必然比从旧表复制进来的带撇值更新。当扩容开始时，旧表可能仍有迟到的线程在并发写入，搬迁算法必须捕捉到写入旧表的最后一个最新值，直到新表出现更新的写入、彻底废弃旧表数据为止。 ```mermaid flowchart TD accTitle: Two-Phase Commit State Machine for Lock-Free Copying accDescr: State transitions showing how a slot value transitions from old table to new table via primed states and tombstones. subgraph NewTable["新表状态转换"] N0["Null (空槽位)"] -->|"CAS 写入旧值副本"| NP["Primed V' (带撇副本)"] NP -->|"旧表成功打上 X 标记"| NV["V (剥离撇号，复制完成)"] N0 -->|"并发的新 Put 操作"| NV NP -->|"并发的新 Put 覆盖"| NV NV -->|"下一次扩容搬迁"| NX["X (打上结束标记)"] end subgraph OldTable["旧表槽位"] OV["最新值 V"] -->|"CAS 写入 X 封锁旧槽位"| OX["X (已搬移)"] end OV -.->|"读取并复制到"| NP OX -.->|"旧表封锁成功后通知"| NV ``` 整个状态机在原有规则上增加了一个关键状态——橙色的带撇复制状态。迁移线程通过 CAS 将旧表中的值作为带撇值写入新表，随后回头尝试用 CAS 在旧表的槽位中打下一个 $X$ 墓碑标记。一旦成功在旧表中填入 $X$，就证明该槽位已彻底封锁，绝不会再有迟到的线程将更新写入旧表，此时搬迁者便可安全地将新表槽位上的撇号剥离（从 $V'$ 变成 $V$），两阶段复制宣告达成。 - **带撇（Prime）标记的语义**：表示该值仅仅是从旧表复制过来的陈旧镜像，并非直接写入新表的最新数据。 - **状态变迁规则**：新表槽位从 `null` 变为 `V'`；旧表成功被打上 $X$ 后，新表槽位从 `V'` 变为 $V$；若新表在复制中途直接接收到更晚的写入操作，新值会直接以非带撇状态覆盖写入。 - **防止并发旧写入**：打在旧表槽位上的 $X$ 确保不会再有任何线程向旧表该槽位提交数据。 --- ### [31:36](https://www.youtube.com/watch?v=HJ-719EGIts&t=1896s) 槽位迁移细化：CAS 自旋与迟到线程处理 Click 进一步放大了跨表搬迁的微观执行过程。在不同线程并发穿梭于旧表与新表之间时，状态机必须严密处理读写时序与内存可见性。搬迁线程首先读取新表槽位：若其中的值已经没有撇号（非带撇），说明已经有更新的 `put` 写入或者其他线程已经完成了复制，当前线程无需做任何事直接退出；若新表中依然是带撇值，线程需比对它与旧表当前值是否一致。如果旧表已产生更新的值，线程必须先用 CAS 将新表中的带撇值替换为对应更新值的带撇版本，再回到旧表尝试 CAS 写入 $X$。 ```mermaid flowchart LR accTitle: Slot Migration and Conflict Handling Flow accDescr: Step-by-step logic when copying a single slot from the old hash table to the new table with rollback on failure. A["读取新表槽位"] --> B{"已是非带撇值?"} B -- "是 (已被更新覆盖或已完工)" --> Exit["退出复制"] B -- "否 (仍是 Primed)" --> C{"新旧两表值一致?"} C -- "否 (旧表有更新)" --> D["CAS 更新新表为最新 V'"] C -- "是" --> E["CAS 旧表 slot 为 X"] D --> E E -- "CAS 成功" --> F["剥离新表撇号 (变为 V)"] E -- "CAS 失败 (遭遇迟到写入)" --> G["回滚重试 (重新自旋)"] ``` 如果打入 $X$ 的 CAS 失败，意味着在这极窄的时间窗口内，有迟到的更新线程抢先修改了旧表中的值。此时原子复制未完成，搬迁线程必须回滚到起点重新自旋重试。现场有听众听得一头雾水，Click 扫视全场后打趣道：“Lot of glazed eyes. There's a few people going 'I got it', a lot of people going 'Oh my God.'” 他安抚大家不必担心死循环：这种 CAS 自旋重试的上限极其有限，仅取决于那些在进入哈希表时未能及时看到扩容标志、且尚未提交更新的活跃线程总数。在生产实践中，这种撞车重试极其罕见，用 Click 的话说就是“千载难逢（once in a blue moon）”。 - **嵌套扩容支持**：旧表中读出的值本身可能已是带撇值（嵌套扩容引发）或者是删除墓碑（$T$），带撇逻辑同样能正确处理这些变体。 - **协作与让路**：新表上的 CAS 若失败，可能代表其他搬迁线程正在并发推进或发生了新写入，当前线程只需顺势退出，让推进更快的线程完成工作。 - **CAS 自旋上限**：自旋失败的次数受限于刚好卡在旧表逻辑判断空隙内的迟到写入线程数，绝不会无限发散。 --- ### [34:47](https://www.youtube.com/watch?v=HJ-719EGIts&t=2087s) 应对内存一致性的思维转变与硬件考量 解释完复杂的状态流转后，Click 分享了一个非常深刻的心智模型转变过程：永远不要假设执行完某条指令后“内存就呈现确定状态”。因为槽位由键（Key）和值（Value）两个分离的部分组成，在多核流水线和缓存一致性协议的作用下，它们会在底层“以极快的速度随机剧烈晃动（waffle randomly）”。并发算法的真正诀窍在于：无论任何线程在任何时刻观察到底层状态槽，都仅基于当前瞬时观察到的状态去驱动状态机步进，并接受 CAS 落地后可能呈现出的多种合法结果分支。 现场有工程师提问，既然 Azul 自己定制硬件，为什么不在硬件层把原子操作做大，比如直接做跨多个字的原子指令？Click 明确回应指出，Azul 确实有能力定制硬件，但他刻意克制了这种冲动：“I went to this to work with Java, which is going to only be limited to what other Hardware does.” 他的目标是产出能够在标准商品硬件（如 Intel 平台）上通用的纯 Java 算法。 ```mermaid flowchart TD accTitle: Hardware DCAS vs JVM Software Solution accDescr: Contrast between ideal hardware double CAS and the pure Java Indirection Object implementation. subgraph HardwareApproach["理想硬件方案 (若通用硬件支持)"] H1["硬件 DCAS (双字 CAS)"] --> H2["原子写入 Key-Value 对"] end subgraph JavaApproach["Cliff 的纯 Java 兼容实现"] J1["值包装 (Indirection Object)"] --> J2["运行时 instanceof 检查"] J2 --> J3["高效区分标准值与 Prime 状态"] end ``` 针对带撇状态的具体实现，听众追问在 Java 中如何不依赖硬件支持给指针打标。Click 解释说，在 C/C++ 等原生代码中可以借用指针低位偷取一个比特，但在标准 Java 中，他是通过一个专用的内部私有包装对象（Indirection Object）来实现的。由于它拥有完全私有的类型，代码只需执行极快的 `instanceof` 判断即可识别，完全不破坏缓存一致性协议；而且不管扩容发生多少层嵌套，只要代表比当前表更老的数据，全局都只需复用这一种带撇包装类型。 - **舍弃确定性时序假设**：“Mentally it worked for me too, but it took me a while to get there to realize: I can't know what the state really is in memory, because there isn't a state defining memory; it's floating around the cache coherency protocol in the machine, flipping randomly all over the place.”（Cliff Click 阐述多核编程的心智模型）。 - **指针打标工程权衡**：纯 Java 环境无法直接像 C/C++ 那样做位偷取（Bit-stealing），采用私有包装类与高效的运行时 `instanceof` 测试是性价比最高的工程解法。 - **无需多重 Prime 标记**：嵌套扩容时只需复用一层 Prime，因为只要比当前操作的目标表更旧，它就是统一意义上的“历史遗留值”。 --- ### [37:15](https://www.youtube.com/watch?v=HJ-719EGIts&t=2235s) 性能基准测试与多核扩展表现 进入基准测试数据环节，Click 展示了在多种硬件平台上的测试图表，涵盖了 x86 四路平台（实为双核超线程）、双 CPU 的 Sun UltraSPARC III、32 核的 Niagara 架构 Sun 机器以及新老两代 Azul 专用服务器系统。基准负载设定为 99% 读操作配合 1% 插入/更新/删除操作，指标采用每秒处理的操作数（Operations per second）。在图表对比中，无锁哈希算法表现出了稳定的平滑线性增长，而对比的工业界参考标准——配置了多达 4,000 路分段锁条带化（4,000-way striping）的 `java.util.concurrent` 并发哈希表，则在不断增加并发时频繁出现性能陡降。 Click 强调，为了公平对比并在后续图表中容纳巨量线程，他特意给标准并发哈希表调优配置了多达 4,000 路锁条带，否则该实现会在内置锁上剧烈争用并彻底窒息。即便如此，在核数扩展到 32 核及更高时，分段锁版本由于不可避免的局部锁争用，仍然在图表上砸出了若干怪异的性能跌落断崖（dropouts）；而无锁算法则一骑绝尘，不仅在 x86 上能轻松跑出每秒 2500 万次读写吞吐，更展现了随着处理器核心数增多而持续上攻的强悍扩展力。 - **基准测试配比**：99% 读、1% 插入/更新/删除的高读并发典型业务模型。 - **锁条带化调优极限**：`java.util.concurrent` 并发哈希表即使配置了 4,000 个并发分段条带，在线程爆发涌入时仍然会因局部锁碰撞引发断崖式吞吐跌落。 - **绝对性能表现**：在普通的 x86 配置下，无锁哈希表即可达到每秒 25,000,000 次操作，并在数十核架构上保持了优秀的线性延伸。 ### [38:58](https://www.youtube.com/watch?v=HJ-719EGIts&t=2338s) 基准测试对比：极高线程与不同读写比下的扩展性 Dr. Cliff Click 深入展示了性能测试数据。在 Niagara 架构（即 Sun 的 UltraSPARC T1 处理器）上出现了一个唯一的“异常值”：非阻塞实现没有明显击败带锁的并发版本（ConcurrentHashMap），而在其他硬件架构上，非阻塞哈希表通常要比对手快 10% 左右。Cliff Click 解释道，这主要是因为基准测试中选取的哈希表尺寸恰好能完美塞入 Niagara 的缓存，使得并发版本占了便宜，换个尺寸测试结果就会大不相同。 当线程数在 Azul 系统上继续飙升至 400 线程时，图表中的浅色曲线（非阻塞算法）展现出巨大的优势。即使并发哈希表采用了多达 4,000 路的分段锁条带化（4,000-way striping），非阻塞算法依然领先它 50% 以上。随着扩展继续拉升到 800 个 CPU，非阻塞实现最终触及了令人惊叹的吞吐峰值——每秒 12 亿次操作（1.2 billion operations per second）；而带锁的并发版本则深陷于线程争用（contention）和垃圾回收算法引发的怪异问题中。 在不同的读写混合比下，两者的差距更加显著： - **99% 读 / 1% 写**：在每秒 12 亿次读取的同时，哈希表还承受着每秒 1200 万次并发写更新。 - **95% 读 / 5% 写**：整体吞吐量有所下移，但并发版本下滑得更为惨烈。在 400 到 800 线程阶段，非阻塞实现已展现出近 3 倍的优势，每秒维持着 7.5 亿次读操作以及数千万次写操作。 - **75% 读 / 25% 写**：写操作占比极高。面对每秒 1.5 亿次更新的高压负载，即便有 4,000 路分段锁，并发哈希表也彻底被压垮，吞吐曲线完全平躺（Flatlined），无法承受如此高频的锁竞争；而非阻塞算法仍能在 Azul 768 核架构和旧款 Sun 服务器上强劲提升。 --- ### [41:53](https://www.youtube.com/watch?v=HJ-719EGIts&t=2513s) 扩容机制的开销与极端测试下的压力极限 有观众提问：“在基准测试期间是否发生过扩容（resizing）？”Cliff Click 解释了他的基准测试方法论：他总是让哈希表从一个微小的初始容量启动，使其在高并发写入下迅速自我膨胀到理想尺寸。测试运行 7 次两秒的试验，去掉一个最高值和一个最低值后取平均。在这一过程中，非阻塞算法由于在第一轮运行中执行扩容操作，性能明显受到冲击，“性能会缩水两到三倍（suck meaning factor of two to three slower than steady state）”；然而一旦达到稳态容量，其性能立刻稳定在对手的两倍左右。 为了探究算法的极限，Cliff Click 甚至设计了一种最严酷的极端场景：只执行插入与删除，并采用滚动的键集合，使得哈希表中活跃的 Key 始终维持在 1,000 个左右，但总计插入了 100 万个甚至更多的死亡键（Tombstones）。这迫使哈希表必须永无止境地频繁扩容与复制以清理死键。在这场“不间断扩容（non-stop resize operation）”的残酷考验中，带锁版本由于 4,000 个条带锁发生近乎死锁级别的争用而性能崩盘，而非阻塞哈希表凭借无锁复制机制，依然比对手快 5 倍。 在这种持续扩容的极端极限下，瓶颈转移到了内存与垃圾回收（GC）： - **GC 吞吐瓶颈**：由于需要将老数据包裹成带有 `Prime` 包装对象的标记以便安全拷贝，这会产生瞬时极高的对象分配率（每秒消耗数 GB 内存分配），系统在约 500 线程时触及 GC 垃圾回收器的吞吐上限。 - **锁争用枯竭**：并发哈希表则很早就触碰到了锁的物理瓶颈，除非将锁的分区条带扩展到远超 4,000 的规模。 ```mermaid flowchart TD accTitle: Extreme Churn Resize Flow accDescr: 滚动键集持续插入与删除导致哈希表频繁触发基于 Prime 包装器的非阻塞复制流程。 subgraph ChurnLoad["极端流失负载 (High Churn Load)"] A["高频写入与删除: 仅 ~1,000 个活跃 Key"] --> B["残留大量 Dead Keys / 墓碑标记"] B --> C{"触发连续扩容与拷贝"} end subgraph LockFreeCopy["非阻塞搬迁机制"] C --> D["为槽位包裹 Prime 对象"] D --> E["多线程协作将数据复制至新表"] E --> F["每秒产生数 GB 的短暂分配"] F --> G["触碰 Azul 垃圾回收器 (GC) 吞吐极限"] end ``` --- ### [44:36](https://www.youtube.com/watch?v=HJ-719EGIts&t=2676s) 为什么不信任用户设置的初始容量？ 观众随后追问，既然扩容有成本，为什么不直接允许调用者提供预估的初始容量呢？Cliff Click 直截了当地指出了生产环境中的真实痛点：“答案是，用户以为他们自己知道（the users think they know）”，但无数次实践证明他们常常大错特错。 如果哈希表坚决遵循自适应扩容，用户只需在最开始的两秒内支付微小的初始扩容开销，之后便能一劳永逸。相反，如果完全听信用户设置的超大容量，内存浪费将难以想象： - **单个超大表预估失误**：如果一个表预计只需要 100 万项，而开发者盲目设置成了 1,000 万项，多出来的 900 万个槽位按每项 8 字节 Key 加上 8 字节 Value 计算，白白浪费掉的内存就高达数十兆字节。 - **海量小表乘数效应**：更为致命的情况是微小实例被过度配置。许多人习惯在创建集合时随手指定初始大小为 100 或 200，但实际上每个表终其一生只会存入一两个元素；如果系统内实例化了 10,000 个这样的哈希表，内存在不知不觉中就被放大了上百倍。 正如 Cliff Click 所断言：“在某个节点上我也许会把它当做一个 Hint（提示），但眼下我很乐意忽略这个提示，按自己的方式来。” --- ### [46:18](https://www.youtube.com/watch?v=HJ-719EGIts&t=2778s) 总结、状态机模型与未来展望 Cliff Click 在总结演讲时强调，该设计的核心成就不仅仅是“在更多 CPU 下跑得更快”或者“在高频修改率下远超传统实现”，最令他兴奋的是**使用有限状态机（State Machine）来进行并发正确性推演**。 开发人员无需在黑盒中盲目猜测内存模型。面对一个（Key, Value）状态对，算法只需根据当前状态机定位状态，然后执行一个精准的 CAS 原语推动状态迁移： - **规避 JMM 内存栅栏游戏**：在该算法中，同表内的并发读写在很大程度上避开了 Java 内存模型（JMM）中昂贵且复杂的偏序与内存屏障（Fencing）限制；唯独在旧表与新表跨表迁移时才需要细致处理屏障与可见性。 - **从机器级一致性转向局部一致性**：“这实际上极大地帮助了扩展性，它意味着我不必在更新时做全机范围的缓存一致性，我只需要做局部一致性即可（I don't have to do machine-wide coherency on updates, I just need to do local coherency on updates）。” - **代码即状态机**：代码本身与草稿纸上绘制的状态转移图保持着一一映射的优美结构，不仅使得代码极度紧凑轻量，更让死锁和竞态逻辑在视觉上无可遁形。 谈及未来工作，Cliff 提出了几项探索： - 编写工具形式化校验所有状态是否穷举完整、转移是否完全合法，甚至探讨从状态机规格自动生成并发代码的可能性。 - 将状态机建模推广到其它并发容器中（例如对 `java.util.Vector` 进行基于非阻塞状态机的改造，以支持并发工作队列（Work-list）场景）。 - 关于开源与代码发布：Cliff 表示他计划将实现发布在个人博客上，目前团队唯一的阻碍是取一个合适的名字以及敲定开源软件许可证类型。由于外部受众与内部客户需求迫切，该项目很快会公开发布。 --- ### [48:54](https://www.youtube.com/watch?v=HJ-719EGIts&t=2934s) 现场问答：并发哈希表的大小统计（Size）难题 在演讲尾声的问答环节中，一位听众指出了哈希表实现中的经典难题：在并发环境下，哈希表如何维护内部元素计数（`size`）并决定何时扩容？如果计数更新滞后，会不会导致线程遍历了大量条目却一无所获？ Cliff Click 解释，无锁并发数据结构的 `size` 统计从来无法保证强一致性。正如他在回答中所澄清的那样：“除非当时没有任何人正在执行更新，否则 `size` 绝不保证与对哈希表的迭代遍历保持一致（the size is never guaranteed to be coherent with like an iteration over the table unless no one else is doing updates）。” Cliff 指出，该问题的真正核心技术挑战在于：**如何设计一个高可扩展的计数更新机制**。如果有 750 个线程同时尝试递增一个全局计数器，若不用同步保护就会丢失计数（Lost Counts）；但如果使用重量级的互斥锁，整个哈希表在极高核心下的可扩展性就会被这唯一的计数器彻底摧毁。Cliff 随即开始阐述针对高并发计数的解决思路。 ### [49:38](https://www.youtube.com/watch?v=HJ-719EGIts&t=2978s) 分段计数器与无锁哈希表的扩容及缩容考量 Cliff Click 解释了哈希表内部大小统计的实现挑战。在高度并发的环境下，单变量的同步更新（`synchronized`）会成为性能瓶颈，因此他采用了分段 CAS 计数器（Striped CAS Counters）。这样虽然使得计数能在大规模并发下扩展，但调用 `size()` 方法时就必须遍历并累加各个分段的计数，而不是简单地读取单个变量。而且，除非没有任何其他线程并发修改表格，否则返回的 `size()` 无法与哈希表的瞬时内容形成强一致性保证。 关于哈希表何时决定扩容（Grow），Cliff Click 指出主要有两个触发条件：第一是当被永久键占用的槽位数量达到了容量的某一比例（利用率阈值）；第二是单线程的探测次数过多（Reprobe 过多）——当一个线程反复探查槽位发现全都被占用、经历了过长时间的寻找后，便会主动判定“找得太久了，该扩容了”，进而触发哈希表翻倍扩容以分散键的分布。 现场听众提问是否会缩容（Shrink）。Cliff Click 坦言自己反复权衡后目前的决定是“不缩容”。尽管可以通过统计存活槽位（Live Slots）来实现缩容，但他认为这在实际工程中缺乏吸引力。如果一张哈希表已经膨胀到如此大的规模，通常意味着系统并不受制于内存瓶颈，而且它之后很可能还会再次增长，缩容后再扩容往往得不偿失。面对听众提到“其他线程可能也需要内存”的交替膨胀场景，Cliff Click 笑着表示这属于极端的“打乒乓球”式复杂用例，并指出 `ArrayList` 和 `Vector` 等标准数据结构同样从不缩容，即使某些人认为这是 Bug，他仍觉得在无锁哈希表中做缩容“很无趣”（Uninteresting）。 - **分段计数机制**：采用 Striped CAS Counters 避免写入热点，`size()` 调用时需要遍历各个分段并求和。 - **扩容触发机制**：槽位消耗达到设定阈值，或单线程因哈希冲突连续探测失败过多（Reprobe 惩罚）。 - **放弃缩容设计**：正如 Cliff Click 所评价的：“I'm convinced that it's an interesting thing to do, not that I don't think it can't be done, I just think it's uninteresting to do it.”（我相信做这件事在技术上是有可能的，我不是觉得做不到，我只是觉得做这个很无趣。） --- ### [52:32](https://www.youtube.com/watch?v=HJ-719EGIts&t=3152s) 并发扩容的状态机机制与垃圾回收类比 ```mermaid flowchart TD accTitle: 哈希表并发扩容与迁移状态机 accDescr: 展示两个线程并发申请扩容、CAS 安装新表以及协助迁移键值对的状态流转过程。 subgraph Alloc["表分配与安装"] T1["线程 A 分配新数组"] T2["线程 B 分配新数组"] CAS{"CAS 安装新表指针<br/>(null -> New Table)"} Winner["胜者成功安装空数组"] Loser["败者直接丢弃其分配的数组"] end subgraph Migration["细粒度并行数据迁移"] Old["旧表槽位 (Old Table)"] WorkSplit["所有活跃线程协同并行迁移"] PrimeSlot["将旧值封装为 Prime 对象<br/>(加锁标记状态)"] StripPrime["去除 Prime 标记并填入新表"] New["新表槽位 (New Table)"] end subgraph Finalize["完成与替换"] RootSwitch["提升新表为 Root Table"] GC["旧表被垃圾回收器回收"] end T1 --> CAS T2 --> CAS CAS -->|"CAS 成功"| Winner CAS -->|"CAS 失败"| Loser Winner --> WorkSplit Old --> WorkSplit WorkSplit --> PrimeSlot PrimeSlot --> StripPrime StripPrime --> New New --> RootSwitch RootSwitch --> GC ``` 当多个线程同时检测到需要扩容时，会出现竞争分配新表的局面。Cliff Click 说明，系统通过一个专门存储新表指针的字段来控制并发，所有线程都尝试通过一次 CAS 操作将其从 `null` 更新为新分配的空数组。CAS 胜出的线程成功挂载新表，而失败者则直接丢弃自己分配的数组。紧接着，整个扩容演变为一个包含海量细粒度子状态的状态机：所有访问哈希表的线程协同参与，逐个将槽位从旧表拷贝到新表；拷贝时通过在旧值上包装 `Prime` 对象来封锁并发写，并在写入新表时解开 `Prime` 包装；所有数据迁移完毕后，新表被提升为根表（Root Table），旧表则静待垃圾回收器回收。 一位现场听众指出，这种迁移算法本质上与复制式垃圾回收器（Copying Garbage Collector）直接同构，`Prime` 包装值扮演的正是 GC 中的 Forwarding Pointer（转发指针）。Cliff Click 欣然认同这一类比。他透露 Azul 内部曾考虑直接把该数据结构与底层 GC 运行时深度绑定，甚至利用硬件的读屏障（Read Barrier）来提供支持。但他为了保证代码的**跨平台可移植性**（Portability）放弃了这一做法。如果不考虑可移植性，他完全可以像 C 语言实现那样直接窃取指针中的空闲位（Steal a pointer bit）来做标记，从而免去额外创建 `Prime` 包装对象的对象开销。 - **并发挂载**：多个线程同时发起扩容时，以单个 CAS 决出胜负，败者直接放弃自身分配的数组。 - **协同迁移**：扩容不是单线程停机操作，而是切分为无数微小状态，由后续读写线程共同推进迁移。 - **便携性权衡**：为了让代码能够在标准 JVM 上直接运行，Cliff Click 选择使用 Java 引用封装而非平台特有的指针位标记或 GC 读屏障特性。 --- ### [54:52](https://www.youtube.com/watch?v=HJ-719EGIts&t=3292s) 与 Doug Lea 的交流及进入 Java 标准库的前景 Cliff Click 谈到了他与 Java 并发大师 Doug Lea（`java.util.concurrent` 的主导者）的深入探讨。两人经常就该算法的演进交换意见。数月前他们交流时，Doug Lea 曾倾向于该方案更适合于恒等比较版本（Identity-test version，如 `IdentityHashMap`），而对于需要 `equals()` 深度比较的版本可能存在关于是否需要缓存哈希值（Memoize Hash）等方面的疑虑。 但在这几门探讨之后的数月里，Cliff Click 对算法进行了大量细化与提炼，在算法正确性上取得了更加坚实的保证，并且在一系列严苛的基准测试中证明了其优异的伸缩性——即便与采用超大分段因子（Striping Factor）的 `ConcurrentHashMap` 相比，该无锁哈希表仍表现出色。Cliff Click 预测，该算法的某种变体版本未来很可能会被正式纳入 Java 官方的并发工具库（`java.util.concurrent`）。 - **标准库前景**：算法经过数轮重构与调优，正逐步向并入官方 `java.util.concurrent` 推进。 - **与 Doug Lea 讨论的核心**：关于引用相等性（Identity）与对象内容相等性（`equals`）处理逻辑的权衡与性能开销。 --- ### [56:00](https://www.youtube.com/watch?v=HJ-719EGIts&t=3360s) 内存膨胀上限、Azul 硬件清零与问答结语 现场听众就极端情况下的内存占用提出了疑问：如果一个 1GB 的哈希表需要扩容到 2GB，而线程 A 与线程 B 同时触发扩容并分别尝试分配 2GB 的数组，在理论上内存占用会不会飙升到“单表大小 × 线程数”？ Cliff Click 分析了这一极端竞态： 1. **理论与实际差异**：理论上限确实是所有线程在瞬间同时发起大对象分配，但实际工程中往往只有寥寥数个线程会真正撞上并发分配的窗口。 2. **容错机制**：如果某个并发线程在尝试分配巨型数组时抛出了 `OutOfMemoryError`，它可以直接捕获异常并放弃扩容，回退到继续使用旧表，因此系统不会直接崩溃。 3. **保持无锁属性**：不能为了防止多重分配而在此处加锁阻塞，因为一旦阻塞就破坏了算法的“Lock-Free”（无锁）保证。目前的做法是线程分配完数组后立即执行 CAS 安装，极大缩短竞争窗口。 Cliff Click 补充道，在 Azul 拥有 700 多个 CPU 且哈希表频繁扩容的极限压测下，实际观测到的冗余数组分配通常也只有两三个。如果分配出的数组因为 CAS 失败而未能使用，它们会立刻被丢弃，并在下一次新生代 GC（Young Gen GC）中以近乎零的代价被迅速回收。针对现场听众关于大内存清零（Zeroing）开销的追问，Cliff Click 强调 Azul 的专有硬件配备了专门的硬件清零支持（Zeroing Hardware），使大内存的分配与初始化开销显著低于普通通用架构。演讲在热烈的掌声中结束。 - **内存竞争上限**：理论上存在多线程同时分配大数组的风险，但实践中通过分配后立即 CAS 挂载新表，将多余分配降至极低数量。 - **OOM 韧性**：若并发扩容线程耗尽内存，可安全放弃分配退回旧表。 - **硬件清零辅助**：正如 Cliff Click 针对大数组分配开销所解答的：“We have zeroing hardware, it's not totally free or anything, but it helps.”（我们拥有硬件清零支持，虽然谈不上完全零成本，但确实大有帮助。） ## Notable quotes > [18:41](https://www.youtube.com/watch?v=HJ-719EGIts&t=1121s) CAS does not give you volatile semantics. — Cliff Click > [46:18](https://www.youtube.com/watch?v=HJ-719EGIts&t=2778s) I don't have to do machine-wide coherency on updates, I just need to do local coherency on updates — Cliff Click > [48:54](https://www.youtube.com/watch?v=HJ-719EGIts&t=2934s) the size is never guaranteed to be coherent with like an iteration over the table unless no one else is doing updates — Cliff Click ## Mentioned Cliff Click, Doug Lea, Jeremy Manson, Azul Systems, Sun Microsystems, Google, HotSpot Server Compiler, ConcurrentHashMap, HashMap, Hashtable, IdentityHashMap, ArrayList, Vector, Java, x86, SPARC, UltraSPARC III, UltraSPARC T1, Itanium, PowerPC ## Video description Google Tech Talks March 28, 2007 ABSTRACT I present a lock-free concurrent Hash Table implementation with better single-thread performance than most Hash Tables, and better multi-thread performance than all other implementations I tried. I demonstrate scaling up to 768 CPUs even with high mutation rates. I show correctness by looking at the problem in a very different light than the usual "happens-before" / memory-order / fencing style of thinking. Speaker: Dr. Cliff Click Dr. Cliff Click, Azul Systems. Chief JVM Architect, Distinguished Engineer With more than twenty-five years experience developing compilers Cliff serves as Azul Systems' Chief JVM Architect. Cliff joined Azul in 2002 from Sun Microsystems where he was the architect and lead developer of the HotSpot Server Compiler, a technology that has delivered dramatic improvements in Java performance since its inception. Previously he was with Motorola where he helped deliver industry leading SpecInt2000 scores on PowerPC chips, and before that he researched compiler technology at HP Labs. Cliff has been writing optimizing compilers and JITs for over 15 years. He is invited to speak regularly at industry and academic conferences, and has published many papers about HotSpot technology. Cliff holds a PhD in Computer Science from Rice University. Google engEDU Speaker: Cliff Click [Source](https://www.youtube.com/watch?v=HJ-719EGIts)

[18:41] Cliff Click: CAS does not give you volatile semantics. [46:18] Cliff Click: I don't have to do machine-wide coherency on updates, I just need to do local coherency on updates [48:54] Cliff Click: the size is never guaranteed to be coherent with like an iteration over the table unless no one else is doing updates

[3:00] Dr. Cliff Click: No locks here means nothing that looks like a lock: not just synchronized keywords or java.util locking, you can't have spin-locks or anything that basically grabs onto a shared resource and holds it permanently. [56:00] Dr. Cliff Click: If you're not going to use the array you just allocated because somebody beat you to the punch, you drop it on the floor; the next young generation GC cycle will reclaim it for no work. [52:29] Dr. Cliff Click: One guy wins the CAS, the other guy loses; the loser throws his table away.

[0:22] welcome to the latest in our series of [0:24] talks on programming languages um today [0:27] we have a very special guest star a [0:30] uh a man who works across the street at [0:33] Azul on uh computers that have many many [0:37] processors he uh he formerly worked at [0:40] Sun where he was one of the chief [0:41] architects of the hotspot VM um and he [0:44] is doing some very similar work at UH at [0:47] aul and uh he's here to talk to us today [0:50] about his experiences creating a lock [0:53] free hash table um for Java that scales [0:57] very well um his name is Cliff click and [1:00] this is [1:01] he [1:07] thanks so um just to show that I'm only [1:11] sort of not too far behind the time I [1:13] actually have a Blog now I started a [1:15] week [1:16] ago this is how fast I end up moving [1:19] with with things here so I'm going to [1:21] talk today about about two things about [1:23] hash tables and about um a different way [1:26] of thinking about concurrent algorithms [1:28] um and and and I'm going to start with [1:31] the hashtable piece um and I assume [1:33] everyone here knows what a hashtable is [1:35] but maybe I can I can throw in a few [1:36] extra things that maybe you haven't [1:38] thought about okay so the obvious thing [1:39] is it's a constant time key value [1:40] mapping sort of by by definition right [1:43] um but from a a a key value mapping you [1:46] can build arbitrary functions out of it [1:48] and they're extendable they're defined [1:49] at runtime what the function is so [1:51] that's totally useful thing and then [1:53] there's a thousand uses for it I gave a [1:54] few here turns out that it's incredibly [1:56] useful in these large business [1:58] applications for usually for cash [2:00] Paradigm some form of uh content caching [2:03] web materials DB access whatever and uh [2:06] and these applications are themselves [2:07] both very large and very heavily [2:09] multi-threaded um and it's very quickly [2:11] it's very easy to get these hash tables [2:13] to become a scaling bottleneck right so [2:15] there's a bunch of um Java [2:17] implementations out there that are all [2:19] well known well understood you know [2:20] hashtable the old one hashmap which is [2:22] not thread safe then now there's a [2:24] concurrent one um which has uh 16 way [2:27] striping internally that's only on [2:28] rights readers are concurrent Riders [2:31] have to fight for one of 16 way um but [2:33] it turns out that uh it's easy to get [2:35] machines with more than 100 CPUs these [2:37] days you go to a you get one with 750 [2:39] CPUs um and we do have people using all [2:42] those CPUs all the same time so rapidly [2:46] a 16-way striping hash table is like a [2:48] major [2:49] bottleneck um and you can make it a [2:51] bottleneck on on lots of machines these [2:54] days so um somewhere along the line I [2:57] started looking at uh a lock free hash [2:59] table [3:00] I guess I sort of fell into it um and [3:04] what I came up with uh is in fact [3:06] entirely lock free so so no locks here [3:08] means um nothing that looks like a lock [3:11] not just synchronized keywords or reent [3:13] you know java.util loocking uh you can't [3:16] have spin locks or anything that [3:17] basically uh grabs onto a shared [3:20] resource and holds it permanently so [3:22] among the other effects that come out of [3:24] this is that means that um you can make [3:26] progress even if other threads die in [3:28] the middle of doing table updates so you [3:30] can have arbitrary uh ulations going on [3:32] table people inserting deleting elements [3:34] uh and shoot them down mid operation and [3:36] the table will not be damaged um all the [3:38] threads make full progress without [3:40] anything uh without any problem here so [3:42] uh we also out of this I think I lost my [3:46] mic okay it's back okay um I need uh [3:50] some sort of atomic update instruction [3:52] and I've been informed that maybe not [3:54] everyone knows what a Cass is anyone [3:56] here want to admit they don't know what [3:57] a Cass is so there's actually Fair [4:00] number okay so C stands for compare and [4:02] swap it's essentially the unit of atomic [4:06] operations on all modern CPUs it allows [4:09] you to um test for a value in memory and [4:13] if it's equal to what you expect it to [4:15] be equal to then do an update and if [4:17] it's unequal you get a report back [4:19] saying I didn't do the update so from [4:21] this sort of uh building block of atomic [4:24] operations all your locks and [4:26] synchronization Primitives are all built [4:27] out of that um and then from that you [4:29] can build all kinds of other things all [4:31] your concurrent algorithms involve this [4:32] kind of operation there's a couple [4:34] variations of this load Link store [4:36] conditional happens on power PCS um and [4:39] there are other things floating around [4:40] that do similar stuff but Cass happens [4:42] to be the one that's on x86 spark azool [4:46] itanium uh I don't know almost every [4:48] modern machine you can think of and you [4:51] can get at it directly from java you can [4:53] write a little bit of unsafe code [4:54] directly C uh objects in memory [4:59] so uh so it's not just sufficient to [5:02] have a lock free hash table I actually [5:04] have to have one that's you know faster [5:06] than locking um and the usual problem [5:09] with the sort of Lock Free algorithms is [5:10] that they're very complicated under the [5:12] hood and the constant factors just kill [5:14] you but not in this case so I end up [5:17] with something that's essentially tied [5:19] May 10% faster than Java U concurrent [5:21] which is sort of the fastest concurrent [5:22] hash table I can find uh for people for [5:25] tables where you're doing like 99% reads [5:28] on a mon count of CPUs so 99% read [5:32] applications are very common for people [5:33] doing caching you occasionally update [5:36] the cache and rest of the time you're [5:37] hitting in the cach right um however if [5:39] I add more CPUs I get somewhat faster uh [5:43] even with uh very large striping uh [5:46] compared to the Java util concurrent um [5:48] certainly I'm much faster if I take the [5:50] default arguments of 16-way striping as [5:53] I start to add more rights so 95% reads [5:56] 5% table mutates uh I start getting a [5:59] lot fter faster and I continue to remain [6:01] faster essentially my performance does [6:03] not degrade very much as I start to do [6:05] uh you know more and more updates and in [6:07] fact I get a decent amount of scaling if [6:09] I do only updates to the table if I have [6:11] 100% you know inserts and deletes in the [6:13] table and maybe 1% reads I still get you [6:16] know very high performance so it's a [6:18] it's it scales extremely well it scales [6:20] basically linearly uh and it certainly [6:23] scales better than anything else I've [6:24] ever seen for uh doing updates [6:29] okay so so enough bragging rights here [6:33] uh so uninteresting hashtable details so [6:35] when I say uninteresting mean I mean uh [6:38] good engineering stuff I assume anyone [6:40] who's written a hashtable can can work [6:42] their way through all these kind of [6:43] details so basically a hashtable is a [6:45] collection of key value Pairs and what [6:48] I'm going to show you the meat of the [6:49] talk is about how to manipulate the key [6:51] and the value pairs in a way that's [6:52] concurrent and provably concurrent impr [6:54] provably safe right so but really you [6:56] still have to have a collection of them [6:57] and the collection has to have its own s [7:00] with dealing with a large set of keys [7:01] and values um and you have to be fast or [7:03] you get constant time effects kill you [7:05] that's what usually happens with these [7:06] locking algorithms fast means these days [7:08] have to be cash aware right uh and I'll [7:11] present this uh sample solution but I [7:13] don't claim it's the only possible way [7:15] to do this there's lots of ways to to [7:16] skin this cat uh and different solutions [7:19] probably make sense in different kinds [7:21] of domains so I ended up using a closed [7:24] power of two hashtable that means my my [7:27] table is an array it's a power of two [7:29] sized array it uh it means that I can uh [7:32] uh limit my hash function into the uh [7:34] table by simply doing and mask on the [7:36] size right um closed means that instead [7:39] of having a um a bucket a chain of uh [7:42] key value pairs on bucket lists uh you [7:45] reprobe into the array itself and uh uh [7:48] it turns out that because you know if [7:49] I'm using stride one reprobe I get [7:51] better cache Behavior because collisions [7:53] turn into linear scan as opposed to [7:56] linkless [7:57] traversal um so you know I I messed [8:00] around a bunch to get my key and my [8:01] value to land on the same cach line I [8:03] memorize the hash function um other cool [8:06] things I don't actually have to do any [8:08] allocation on a put that's kind of [8:10] unusual and then the big one is I auto [8:12] resize the table so um I ignore whatever [8:15] argument you give me on what the table [8:17] size ought to be and I'll just get a [8:18] size as it comes [8:22] up so here is sample get [8:26] code um and I'm again I'm going to [8:28] assume people mostly know what's going [8:30] on here um compute your hash function [8:35] you know while true that's the reprobing [8:36] loop mask to the size of the table get a [8:39] key well the magic git key function and [8:41] the magic G valve function I'm going to [8:42] talk about in a minute that's sort of [8:44] the meat of the talk how you do that in [8:46] a way that's safe in the face of uh [8:48] people mutating the table out from under [8:50] you right and then you look for a hit no [8:52] you've got your keys equal then you're [8:53] going to return the value if your key [8:55] was a null you must have missed and [8:56] otherwise you Repro by adding one and [8:58] trying again um so the actual git code [9:01] is I mean this is essentially it I have [9:02] a little tiny bit more code in the [9:04] actual implementation um but it's very [9:06] very fast and one of the reasons this [9:08] table is so fast is because what goes [9:10] into git key and get Val is nothing more [9:12] than a load instruction so so this is [9:14] the entire get call and that's why it's [9:17] fast it just hash table look up got to [9:20] hit on the key [9:22] done okay so odds and ends here these [9:25] are all engineering decisions that [9:27] people might choose to do differently uh [9:29] hash table the existing one uses a prime [9:32] siiz table in the mod function but a mod [9:35] is like it's like the cost of an L1 Miss [9:38] L2 hit it's a little more expensive than [9:40] that um if I'm going to be hitting in my [9:42] L1 I'd rather not screw with a mod I [9:44] lost already I'd rather just reprobe a [9:46] few times um I want to get my hash [9:50] function on the same cach line but keys [9:52] and values are object pointers and [9:53] hashes and int and Java it's hard to [9:56] Mush that all into a package that fits [9:58] on the same cach line [10:00] um but you know so there's some [10:01] engineering decisions to make here and [10:03] that's sort of the end of the [10:05] uninteresting [10:06] stuff so does anyone here have any [10:08] questions on that because that's just [10:10] like how to build a hash table [10:12] right just couple of questions on uh [10:17] is uh looking up is is your primary [10:21] thing that you want to speed up um it [10:24] turns out that my put is extremely fast [10:26] as well but that wasn't original goal [10:30] the original goal was to sustain some [10:31] interesting number of puts while having [10:33] a huge count of people doing [10:35] GS same as uh same table mutation [10:39] Whatever It Is insert change an existing [10:41] value delete uh insert only if it's not [10:44] there already so you guaranteed exactly [10:46] one insert that kind all those [10:47] operations I'm calling put but it's [10:50] they're uh they're actually implemented [10:51] the same piece of code under the hood in [10:53] the very Bitter End there's a place [10:55] where I do a cast to insert a value into [10:58] a table and that [10:59] one C instruction covers delete it [11:02] covers insert covers change it covers [11:05] put if absent put if matching old value [11:07] delete if matching whatever all the [11:09] variations there up maintaining the size [11:11] of the number of entries on the table [11:14] yes could repat the question oh I'm [11:16] sorry am I okay yeah yeah so what about [11:19] um what about operations other than the [11:22] classic put or insert what about delete [11:24] what about change and the answer is it's [11:26] all the same piece of code it's all [11:27] using the same tiny of work to do the [11:30] same operation to the table I'll show in [11:32] a minute why those are all semantically [11:34] equivalent operations any table mutation [11:36] goes to the same path and then also am I [11:39] uh collecting size uh table size which I [11:42] am um and that's uh this is intended to [11:45] be a dropin replacement for uh hashmap [11:47] or Java util concurrent hashmap um in [11:51] which case you have to have a size now [11:52] the size um as with all these concurrent [11:56] algorithms the size function is sort of [11:58] uh lazily maintained within a single [12:01] thread you're guarant to see guaranteed [12:02] to see your own uh updates to the size [12:06] but other threads will see your size [12:08] changes sort of lazily as the hardware [12:10] plays ketchup on the disjoint rights to [12:14] things okay so let's go look on on sort [12:18] of getting into the meat of this thing [12:19] here right so the real problem with all [12:22] of these concurrent algorithms is how do [12:24] you prove correctness and and [12:26] classically it's very difficult to prove [12:28] correctness right I want to know if I'm [12:30] updating my table uh how do I show that [12:32] I got it right and um people [12:35] traditionally have done uh arguments [12:38] relating to fencing or memory model [12:40] fencing sort of the hardware [12:41] implementation of proving something [12:43] happened before after something else uh [12:46] and memory models I guess Jeremy talked [12:47] about these very recently um that's sort [12:49] of the the the language lawyer semantic [12:52] way of talking about what happens when [12:54] right or you know getting your load [12:55] store ordering right that happens before [12:57] relationship so instead I'm going to [12:59] prove things via a state machine that is [13:02] I'm going to define a pile of states and [13:04] some transitions that together makes a [13:06] state machine and then I'm just going to [13:07] show that all states are legal and I [13:09] don't care what state you start in or [13:10] what state you end up in you get [13:12] something legal out of [13:15] it um [13:17] so what I get out of this is I'm not [13:20] going to care about memory ordering that [13:22] means the gets can read keys and values [13:25] in any order so in particular in my git [13:27] code I said here's G key and get value [13:30] in different places it didn't have any [13:31] fencing in there didn't have any [13:32] ordering constraints even if the [13:34] compiler didn't reorder those loads or [13:36] tried to prefetch one or the other the [13:37] hardware is free to reorder the loads [13:39] and that's very common for the hardware [13:40] to do that so you know I'm going to [13:43] allow them to read keys and values in [13:45] any order and as soon as I can read them [13:47] in any order I can write them in any [13:48] order if I don't have strong ordering on [13:50] the read side I don't have strong [13:51] ordering at all and now I don't care [13:53] about ordering on the right side so [13:54] suddenly I can just use C alone to [13:57] change keys and value and I don't care [13:59] what order any of it happens and I'm [14:00] just going to get a different state if I [14:01] change a piece my state changes and it's [14:04] legal however that works and I'll show [14:05] that coming up so no fencing required [14:08] for correctness and and I claim the [14:10] proof as simple although maybe I've [14:11] stared at it too long and so it's not [14:13] fair for me to claim [14:14] that um so what are the states what do [14:16] you mean by state here a state is okay [14:18] so a key is either null or it's some key [14:22] and I'm never going to change that key [14:24] again if I change if I add put a key in [14:25] the table it can never go away uh and [14:27] that's key to getting correct out and uh [14:30] value is either no or it's some value or [14:32] it's a tombstone meaning it's been [14:34] deleted you insert it and then later [14:35] delete it and you can resurrect Somebody [14:37] by putting a new value in if you insert [14:38] and delete and insert and delete same [14:40] key over and over again you'll flip from [14:42] Tombstone and value back and forth right [14:44] and a state is just a pair of those and [14:46] a transition in the state machine is [14:48] taken on a successful Cass on an atomic [14:50] update right and here is the state [14:54] machine and I'll talk people through it [14:56] and then I'll shut up a minute you can [14:57] stare at it some more so upper left [14:59] corner has the obvious empty set this is [15:01] the key value pair which uh you know [15:05] it's the initial state of the table and [15:06] if I insert a key then I'm just going to [15:09] Cass and so a transition's on a [15:10] successful Cass of null to some key and [15:13] because I'm using a Cass I know that [15:15] there's no race here and there weren't [15:16] two people putting different Keys down [15:18] in that slot of which you know I don't [15:20] know which one won in fact because I'm [15:21] using a Cass I know which guy won and [15:23] he's the guy who now owns that slot [15:25] forever in all time and then I have a [15:27] still have a null for a and eventually [15:29] insert some legit value there and if I [15:32] would do a change I'm just going to [15:33] mutate the value in place and if I do a [15:35] delete I Jam a tombstone out over the [15:37] value and if I want to insert after [15:38] leion then the tombstone gets replaced [15:40] back and so forth so that's a state [15:46] machine that is not as ideal if you have [15:50] if you want to inser lots of stuff and [15:52] remove and garbage collect you're never [15:54] going to be able to garbage collect tra [15:56] so you're about two slides ahead of me [15:58] but in fact I'll talk about how to how [16:00] to free up keys that get stuck in the [16:04] table and then I have this funny empty [16:06] State down here which is uh somebody [16:09] looks and sees a null key but they see [16:11] an actual value inserted which doesn't [16:13] happen in the put side the puts don't do [16:16] that but a git can read out of order and [16:18] see this so I'll talk about all this [16:20] stuff here okay so a couple things so [16:23] once a key is set it never changes and [16:25] that's the that's the key to never [16:29] getting the wrong value for the wrong [16:30] key right if I actually change a key [16:33] then I might get a hit on a slot on one [16:35] key and pull a value out from a [16:36] different key so that no chance of that [16:39] but it also means that my keys leak [16:41] right because my table fills up with [16:42] dead Keys that's your question okay so [16:44] I'll fix in a few [16:45] slides uh by cleaning the table out in a [16:48] minute okay and then I have no ordering [16:50] guarantees so this is a bring your own [16:52] ordering bring your own synchronization [16:53] party here right uh and more on this in [16:56] a second and then you know this weird [16:57] state which really basically means that [16:59] a reader has uh uh fetched a key and [17:02] prefetched a value hoping the key is [17:04] correct and he got a null key and the [17:05] pre-etched value is he didn't know what [17:07] it's for it's for some random key he has [17:08] no clue so it's counts as a [17:11] Miss I only found that state because I [17:14] went and computed all possible [17:16] combinations built the whole state [17:17] machine and I had this weird State left [17:19] over and I tried to deduce what's the [17:20] meaning of the weird State and the [17:22] meaning is some GS side red junk and got [17:25] a Miss in the table okay so other things [17:27] here that there's no ma machine wide [17:29] coherent State here that means for any [17:32] key value pair different parts of the [17:35] same machine might see different [17:37] combinations of key value pair set [17:39] setups according to whatever read order [17:41] the hardware is handing you and that is [17:43] correct if you are doing racing updates [17:46] that is you have multiple people [17:47] inserting the same key but with [17:49] different values then you don't know [17:51] which value is going to end up in the [17:52] table and different people might see [17:53] different values at different times and [17:54] that's that's the all the semantics you [17:56] get out of java and more than you get [17:58] out of most other languages right okay [18:00] so so no machine wide coherent State and [18:02] no need for it either so this is sort of [18:05] what you can think about this is um [18:06] consider the degenerate case of a hash [18:08] table with but a single key and for that [18:12] single key I'm going to provide you the [18:13] same guarantees as if you had a single [18:16] shared Global variable named that key [18:19] and you had whole lot whole lot of [18:20] readers and writers who are accessing [18:22] that single shared variable without any [18:24] synchronization you just Define a global [18:27] X and a bunch of people writing into X a [18:28] bunch of people reading from X I give [18:30] you the same guarantees if you have a [18:32] key and a bunch of people reading to [18:33] that key and a bunch of people are [18:34] writing to that key you get the same [18:36] answer out right which is not a whole [18:38] lot of of guarantees but at least [18:41] it's uh no not yet but I will be in a [18:44] minute this this as presented so far [18:48] you're doing a c no Cass does not give [18:51] you volatile [18:53] semantics uh [18:55] Java no if you well depends on which [18:58] flavor of c and in particular my [19:01] Hardware on aul does not fence unless I [19:04] ask it to and it's much cheaper [19:06] therefore so I'm happy to have a non- [19:08] fencing Cass and exactly here I don't [19:10] need a fence and so uh there is a [19:13] version of Cass in Java that does not [19:14] fence called weak Cass and that's the [19:16] version I'm [19:18] using but I want volatile [19:21] semantics here so I probably want a [19:24] slightly stronger guarantee than what I [19:26] just presented I probably want what's [19:28] called happen before relationship but [19:30] only on the value side that is to say if [19:32] I construct new value in memory and I [19:34] Jam I publish a pointer to it into the [19:36] hash table and another thread fetches [19:38] the pointer out of the hash table and [19:39] then reads through that pointer to see [19:41] what I just wrote you want him to see [19:43] the initialized state of stuff that went [19:44] in there right and that's the happens [19:46] before relationship on the values it's [19:48] essentially the same semantics as what [19:50] volatile gives you so if you if you [19:53] don't use volatile if you write an [19:55] object and you jam its value into uh uh [19:57] some Global shared [19:59] and somebody else reads it and you're [20:00] not using the volatile keyword you don't [20:02] have a guarantee that you're going to [20:04] see what was written and uh classically [20:06] it's called the double checked locking [20:07] idiom and until you add the volatile [20:09] keyword it's broken you could go Google [20:12] double checked locking if you don't [20:13] believe me anyhow so this one is [20:17] actually pretty easy I want to have a [20:18] fence in here um to get happens before [20:21] this is the first time I need a fence [20:23] turns out that the actual fencing [20:25] semantics I end up issuing in the [20:26] hardware depends on um the exact piece [20:29] of Hardware you're on and what kind of [20:30] memory model the hardware provides under [20:32] the [20:35] hood okay so so far I've talked about [20:39] get and put the actual Wheel part this [20:42] is where I'm going to um put my my state [20:45] table to its test here I'm going to talk [20:47] about how to do concurrent resizing and [20:49] this is where all the other uh [20:51] concurrent hash table algorithms I could [20:53] find sort of I want to say fell down but [20:55] got really really ugly this is going to [20:58] get a little bit ugly but it's not going [20:59] to get nearly as ugly as the other stuff [21:01] I've seen so one of the things that [21:03] happens here is that I have to resize my [21:05] power of two table if it gets full if [21:06] I've picked too small a number and in [21:08] fact I start out with a very small [21:09] number because most hash tables are [21:11] actually only used to hold like a [21:12] handful of things and then no maybe I [21:15] want to resize if my hash function is [21:17] ugly and I'm reprobing because I'm [21:18] getting bad collisions or maybe I want [21:20] to resize because I got a bunch of Li a [21:23] bunch of dead uh keys in the table and I [21:25] want to clean them up and resize to the [21:28] same size not really resize it's cleanse [21:30] it's basically copy the table from here [21:32] to there copy only the live stuff and [21:35] the dead Parts get cleaned out so that [21:37] was there was your question how do you [21:37] handle that I'm going to copy the table [21:39] and at this point I actually need a [21:40] fencing in the algorithm uh between the [21:43] tables not within a table but with [21:45] between it and and the hard bit the [21:47] thing you have to look out for here is [21:49] um how do you handle picking up the last [21:51] update to the old table that's racing [21:53] with your copy into the new table that's [21:56] the tricky piece Okay so the way I'm [21:58] going to do this is I'm going to expand [22:00] my state machine that is you know I'm [22:03] going to add new States and and as the [22:05] side effect of this uh mid resize is [22:07] sort of a valid State and it also means [22:09] that my um my resize is entirely [22:12] concurrent that is people can read from [22:15] the existing uh half copy table and and [22:18] just go or they can help with the copy [22:20] and then you know go or I can do it in [22:22] parallel I can do it incrementally [22:23] partial copy is okay I can have stacked [22:25] partial resizes in progress that's okay [22:28] um I do want to get rid of the resize [22:31] eventually I want to because I'm paying [22:34] this extra IND Direction while resize is [22:35] in progress So eventually I want to get [22:37] it over with um but while it's in [22:39] progress everything sort of charges [22:40] ahead at whatever Pace they want to go [22:42] there's a bunch of heuristics here that [22:44] you can pick from oh here I go yeah I'm [22:46] talking about heris [22:50] sticks so um git in general will work on [22:55] the old table unless it sees a sentinel [22:57] talk about the Sentinel a minute um put [23:00] or other modifications have to go modify [23:02] the new table and they have to check for [23:05] the new table every time and if they see [23:06] the new table they have to go run to it [23:08] and they have to fence between the [23:09] tables and that means that because I'm [23:11] fencing between tables that the last [23:13] right to the old table is guaranteed to [23:16] be happens before that Java memory model [23:19] semantics before the resize operation [23:21] that's key to getting this thing done um [23:25] but actually copying the key value pairs [23:27] is independent of getting put so I have [23:30] a lot of heris to choose from um [23:32] theistic I'm using right now is [23:34] everybody who touches the table does a [23:36] little bit of copy work and then they do [23:37] their operation whether it's a get or a [23:39] put or delete or insert whatever but I [23:41] could have like only the writers copy [23:43] the table if I want the readers to be [23:44] really fast they can just read and go on [23:46] the old table unless they're told to go [23:47] to the new table kind of thing I could [23:49] have it with unrelated background [23:50] threads right I could spawn extra [23:51] threads I got extra cores I got [23:52] background threads do the table copy for [23:56] me so let's look at the new States here [24:00] um I have to add a new state I'm going [24:02] to add the X state which is a sentinel [24:05] and it tells me uh not here go to the [24:07] new table and I'm going to use this as a [24:09] way to avoid having to look to see if I [24:11] have a new table all the time or [24:13] actually to say I'm halfway between [24:16] table copies and some of the slots are [24:19] still in the old table not copied and [24:21] some are now in the new table and the [24:23] ones that are in the new table have an X [24:24] in the old table right so I added to X [24:28] as a way to stomp a key and a slot now a [24:31] key slot either goes from null to a key [24:33] or from null to an X if I'm going to say [24:35] this slot is dead now you cannot insert [24:38] something a late [24:40] arriving insert cannot update in the old [24:42] table anymore you has to go to the new [24:43] table okay and a value slot has the same [24:46] kind of thing it has what it had before [24:48] plus one of these new things meaning uh [24:51] it's not here now go to the new table [24:52] it's been [24:54] copied so this is the transitions that [24:56] can go through from null to some numbers [24:59] of uh tombstones or values as you do [25:01] inserts and deletes on a slot until [25:03] somebody comes along and says I'm done [25:04] with a copy now no more updates to the [25:06] old table go to the new table so I have [25:09] a state machine this is the same state [25:10] machine I had before except I added the [25:12] two yellow states on the [25:14] right and one of them is I take an empty [25:17] slot and I Mark the key out so no one [25:20] can try to insert a new key into the old [25:23] table and the other one is I took an [25:27] existing key value hair and I've marked [25:29] it out indicating that I have [25:31] successfully copied it into the new [25:32] table and you're on the wrong table [25:35] now and there are some states that are [25:38] no longer possible and if you do the [25:41] math you can count 3 * 4 12 States in [25:44] here and there's more states that are [25:46] uninteresting if a a git comes along [25:49] he'll realize he's in the wrong place [25:51] he'll realize that he's just got to [25:54] miss so I'm going to stare at this let [25:57] people stare at this a little bit longer [25:59] and then I'm going to break down what [26:00] the little transitions mean a little bit [26:01] more in the coming [26:06] slides chain resizes yes as I mentioned [26:10] before maybe make it clear it's possible [26:13] to have stacked partial resizes and I [26:16] did um the current heris I've chosen [26:19] doesn't allow that but I I waffled [26:21] around with various theistic that uh did [26:23] do change stacked resizes and and the [26:26] algorithm all works I mean it's all fine [26:28] it's functional if you have stacked [26:29] resizes it just means know you go to the [26:32] you look at the oldest table yeah and [26:33] you see an X oh go to the next table up [26:35] and you see another X you go to the next [26:36] table up and and yada y y and you can do [26:39] this if for instance you know you got [26:40] 700 threads like jump on an empty table [26:42] and they immediately all insert and the [26:43] table's brand new it's got like 32 Ines [26:46] or whatever the default minimum size is [26:48] and you know a couple hundred people [26:49] jump and try to do an insert well [26:50] immediately it's full so they imediately [26:52] start coping to the next Double siiz [26:54] table well that's full too instantly and [26:55] so's the next and the next and the next [26:57] and you you get like five doublings in a [26:58] row before you can swallow the 750 [27:00] instant concurrent puts right so you [27:03] know and the copies are all in progress [27:05] and and moving along and it all works [27:06] it's just as a performance thing it was [27:09] more convenient to force the old table [27:10] to clean out before making get another [27:12] new table so I make you do more copy [27:15] work essentially till the table cleans [27:17] out till the old one cleans out uh it [27:19] turns out I still end up with a constant [27:20] amount of copy work per update to the [27:22] table if you do a touch on a table you [27:25] get a a a it's fixed amount of work um [27:28] as part of your copy before you go on so [27:30] every thread is stalled by a fixed [27:31] amount of time during the resize not by [27:33] like the time it takes to copy a [27:34] megabyte table to a 2 megabyte table [27:36] they just do whatever piece of [27:38] it okay so we all bored with this slide [27:41] here so let's look at these transitions [27:43] in a little uh more piece this is an [27:44] easy one this is the transition that [27:46] says I have an empty slot I want to [27:48] prevent another key from being inserted [27:50] in the table I just C an X in if I C an [27:52] none X Then I then no key was in there [27:56] uh cuz the the C would have failed with [27:57] a key if the key showed up right so [28:00] here's another one which is I got a dead [28:01] slot in the old table and all I'm going [28:03] to do is put an X down saying no more [28:05] updates to this dead slot um if you want [28:07] to do another if you want to reinsert [28:09] this key you got to go to the new table [28:10] and insert it aesh there and a more [28:13] complicated one is I have something in [28:15] the old table but I also have something [28:17] in the new [28:18] table except that I can happens before [28:21] Java memory model style prove that this [28:23] thing is older than this thing and I'll [28:24] talk about more that about that in a [28:26] minute but the um the way I can know [28:29] this is uh operations that happen on the [28:32] old table are guaranteed to happen [28:34] before the resize because a guy doing a [28:35] put looked to see if a resize is in [28:37] progress right so what this means is [28:39] that this update this V2 down here [28:41] that's a newer put and there's a race [28:44] going on between people doing updates [28:46] this is a more recent put and I can just [28:48] ignore the last put I can ignore the guy [28:50] in the old table I can claim I'm [28:52] uninterested in his value got stomped by [28:54] somebody racing to do a put [28:55] here so the the trick here is I know [28:58] that this is a more recent putot than [29:00] that and I'll talk about that in a [29:02] second but that's these are all uh copy [29:05] uh pieces of the copy where I don't [29:07] actually copy any values I simply say [29:09] I'm uninterested in the old table [29:11] anymore so if I actually have to do a [29:14] copy I'm going to do essentially a [29:15] two-phase commit I'm going to introduce [29:18] primed versions of values and tombstones [29:21] and the primed values represent things [29:24] that are copied into the new table from [29:27] the old so they are values which were [29:30] not recent in the new table but they are [29:33] merely copies of what was in the old [29:35] table anything that's put directly in [29:38] the new table happens after the table [29:40] resize has begun and that's guaranteed [29:43] to be a more recent update than any [29:46] primed [29:48] value and this is how I'm going to get [29:50] the last late arriving right from the [29:52] old table I'm going to do I'm going to [29:54] attempt uh uh uh to copy atomically [29:57] between the two table tables and the old [29:59] table might be getting continuous uh [30:01] late arriving updates I need to get the [30:04] last one out and eventually a new update [30:06] to the new table might appear and make [30:08] me uninterested in anything in the old [30:10] table um but until that happens I have [30:12] to assume I'm going to keep trying to [30:13] get stuff out of the old table so let's [30:15] look uh at this a little more detail [30:17] here I have the same key values I had [30:20] before no key X the same value slots [30:23] there's a new version where I just take [30:24] a Prime on tops of tnv and it's my old [30:28] things copied in the new table to phase [30:30] commit right and so now the the [30:31] transitions I'm allowing here I'm going [30:32] to go from null to primed and this is in [30:35] the new table taking a copy from the old [30:37] table I'm going to strip the prime off [30:39] either that or I'm going to get a recent [30:41] update to the new table which is going [30:43] to make me uninterested in the old table [30:44] and that will also be with no Prime and [30:46] eventually I'm going to copy again to [30:47] the next table down the road and that's [30:49] what the x is there [30:51] for so I have a state machine and I add [30:53] one state although it's getting pretty [30:55] thick up there and it's the orange one [30:58] here and it represents the point where [31:01] I'm copying in a value from the older [31:02] table and I'm going to copy it in with a [31:05] Cass to get it in and a prime to say [31:07] it's an old value and if I can [31:10] successfully uh slap an X down in the [31:13] old table so this is what's in the new [31:14] table if I can successfully slap an X [31:16] down in the old table then I know I'm [31:18] done I successfully did my copy no one [31:20] else can update the old table because I [31:21] got an X there so this is all [31:23] complicated to read here because I'm [31:24] doing updates into the old table and [31:26] updates into the new table table using [31:29] the same state machine but different [31:30] state transitions so I really kind of [31:33] want to stare at this in a little more [31:34] detail I'm going to look at in the new [31:36] table how do I get a prime value in it [31:39] and then get rid of the Prime saying [31:41] I've got the right thing no more updates [31:43] are showing up from the old table and I [31:45] want to look at what's going on the old [31:46] table where I'm going to say uh I'm [31:48] still pounding in values in the old [31:49] table because I'm a late arriving update [31:52] uh and somebody wants to you know put an [31:53] X down and tell me I'm in the wrong [31:54] place I need to go to the new table so [31:56] those are the I'm going to zoom in on [31:57] those sets of States and I get this [31:59] thing and these are things happening on [32:02] the old table up and things happening on [32:04] the new table down and this way I'm [32:06] going to read something from this is my [32:09] unfortunately my fencing now between [32:11] tables I have to do happens before via [32:13] fencing via Java memory model kind of [32:15] things read something from the new table [32:18] if it's not primed by the way I'm just [32:19] done because I know it's more recent if [32:21] it's primed it's it's an old thing [32:24] that's been copied and a more recent old [32:26] thing has appeared it's different [32:28] if it was the same then I'm going to [32:29] step over to the state where I know that [32:31] the new and old tables are the same but [32:32] if they're different then I need to [32:34] update the new table by uh replacing the [32:37] prime value I got with another primed [32:39] version of V1 so that the new table now [32:42] has uh the most recent copy from the old [32:45] table now I want to go uh hammer the old [32:49] table so no one can do any more updates [32:51] and again it's a Cass and if this one [32:53] succeeds I got my X in and I know that [32:55] the new table has a copy of what was in [32:57] the last thing that made it to the old [32:58] table and at that point I can strip my [33:00] Prime and the copy's complete if any of [33:03] these CES fail along the way then I [33:05] didn't get my copy done automically uh [33:08] and I have to try again I have to roll [33:09] back to the beginning and and do this [33:10] copy again that copy effort failed [33:12] because a late arriving update uh [33:15] screwed with the old table basically um [33:19] there's a finite number of those that [33:21] can happen because it can only be the [33:24] count of threads that entered the table [33:26] past the point where they tested for rec [33:27] and didn't see it but haven't yet [33:29] committed their updates so this is a c [33:32] spin Loop if I fail but it's limited by [33:35] the count of threads that arrive late in [33:36] the table in practice it's almost never [33:39] it's once in a blue [33:44] moon lot of lot of glazed eyes there's a [33:47] few people going I got it a lot of [33:49] people going oh my [33:52] God okay so um some things to to look at [33:56] here old values could be V or t it could [34:00] be I end up copying a tombstone if I [34:02] first tried to copy a value and that [34:04] copy failed and then somebody deleted [34:06] and now I'm stuck having to copy the [34:07] tombstone over so I still have to handle [34:09] that it might be a primed version if I [34:11] have a nested table resize in [34:13] progress um turns out that I can uh uh [34:16] quit trying the copy if I discover that [34:18] the new value no longer has a Prime on [34:20] it it means somebody either stripped a [34:22] prime from an old copy because it was [34:23] successful or a put happened in the new [34:26] table and it stomped anything I care [34:28] about in the old table right um I can [34:32] get uh uh if my C into the new table [34:35] fails here it means somebody either did [34:37] a put or there's somebody else doing a [34:38] copy I could have multiple guys copying [34:40] the same slot and if my C failed I [34:43] should just get out of the way let the [34:44] guy finish his copy right and and really [34:47] the way to think about this is that any [34:49] thread can see any of those States at [34:51] any time and you just look at the state [34:53] machine and say if I see this state [34:55] here's the action I go do to go to the [34:57] next state [34:58] that's sort of the the real trick there [35:00] um thinking about it saying you know I [35:02] did this Cass therefore the state looks [35:04] like X isn't the right way to think [35:06] about it because there's two pieces a [35:07] key and value and they can both waffle [35:10] randomly up from under you as fast as [35:11] they possibly can you just really have [35:13] to say you know I think I'm at this [35:14] state so I should Transit and then I'm [35:16] going to get one of several states in [35:17] the end depending on which the other [35:19] value [35:23] flipped it [35:25] works I understand this works okay [35:28] mentally it worked for me too but it [35:29] took me a while to get there to to [35:31] realize oh I don't care I I can't know [35:34] what the state really is in memory [35:36] because there isn't a estate defining [35:37] memory it's floating around the cash [35:39] coherency protocol in the machine [35:40] flipping randomly all over the place [35:42] what think you guys control the hardware [35:45] can't you make larger atomic oh we can [35:48] but I don't want to okay it's no it's [35:51] really um I I went to this to work with [35:52] Java which is going to only be limited [35:54] to what other Hardware does so as soon [35:57] as I can convince Intel to provide me [36:00] with dcas I it would it would work right [36:03] and it's all over with I got dcas I'll [36:04] just decas key value pairs as a pair and [36:07] I'm done right so assuming that's not [36:09] happening I want this to work without [36:13] decas don't you also need to convince [36:15] them to have a prime so the prime is [36:17] easy there's lots of ways to do the [36:18] prime um if you're in code you just [36:21] steal a bit from a pointer if you're in [36:22] Java I wrapped it with an indirection [36:25] object so it's an engineering hack and [36:28] and yeah there's more than one way to [36:29] skin that [36:30] cat of course wrapping it with pointer [36:33] means that that c coherency proper no if [36:37] I wrap it with an indirection object all [36:39] I have to do is test for are you an [36:40] instance of prime or prime prime objects [36:42] are never any valid value they're own my [36:44] own private class uh so I just ask the [36:47] instance of test which is actually very [36:49] fast on all machines these [36:53] days no I don't I only need one prime I [36:57] did I did work through the nested resize [36:59] what happens when you pull a Prime from [37:00] the old table to the new table and [37:01] answers you only need one prime it [37:03] represents a value which is older than [37:06] the table you're coping into right and [37:08] if you're nested prime it means you're [37:10] definitely older you're from an extra [37:12] table [37:15] ago okay so here are some performance [37:18] numbers let's see here if I can okay so [37:20] how to do this here so um this is [37:23] impossible to read so I I'll figure how [37:26] to summarize here so the orange lines [37:29] are uh uh I say x04 here and it means uh [37:35] x86 four-way it's actually a dual [37:37] hyperthreaded so it kind of cheats it's [37:39] really too CPU non-blocking algorithm is [37:41] the faint line on top and the diamond [37:44] the triangle down is Java util [37:46] concurrent co4 concurrent with 4,000 way [37:49] striping and I have 4,000 way striping [37:51] because I'm going to jam a lot of [37:52] threads on the future graphs here and if [37:54] I don't have tons and tons of striping [37:56] then I'm just going to choke on the lock [37:57] that are built into that uh in the hash [37:59] table um this is a uh ultr spark [38:03] 3 uh with two CPUs that's the sun2 and [38:07] everything else is either Niagara uh an [38:09] older Sun box with 32 CPUs or an old aul [38:13] box or newbox and we're all on an upward [38:15] ramp uh and that's the end of that chart [38:18] and I'll quit showing some of the the [38:19] two CPU things going forward this is a [38:22] table doing 99% reads 1% insert updates [38:26] um this is operations per second so I'm [38:30] doing you know the x86 is doing 25 [38:32] million uh reads a second and 1% of [38:35] those are actually inserted [38:37] Elite so ramping up to [38:40] 32 I get some funky dropouts usually on [38:45] the concurrent Guy usually for uh places [38:48] where he starts to get contention on [38:50] locks and gets funny dropouts as he goes [38:52] most things just ramp up pretty [38:54] straightforwardly and I dropped the two [38:55] CPU guys out here and we're all going up [38:57] up to [38:58] 32 and the only the only anomaly I have [39:01] here is that I'm not faster than the [39:03] concurrent guy on Niagara it's generally [39:06] 10% faster on on the other platforms not [39:09] Niagara and that's because the size of [39:11] the table I've chosen happens to fit [39:13] perfectly in the Niagara cache and uh [39:16] for the concurrent version and not for [39:18] my version sort of uh I could have [39:21] picked a different size and it would uh [39:23] play the numbers a little differently so [39:25] then I keep ramping up the isul guy to [39:26] 400 thread [39:28] and uh and the light lines are the [39:30] non-blocking algorithm and you can see [39:32] they're running uh you know 50% up over [39:35] the blocking algorithm even with 4,000 [39:37] way striping and if I keep going out [39:40] here to 800 CPUs this eventually hits [39:43] 1.2 billion operations a second uh and [39:47] the concurrent guy gets all kinds of [39:49] weird problems uh with contention and [39:53] garbage collection algorithms and stuff [39:54] going on so that's uh 1.2 billion reads [39:57] a second of which 1% so 12 million oper [40:01] updates a second into the same hash [40:05] table and I looked at a 95% table which [40:08] has exactly the same scaling [40:10] characteristics except everything [40:11] shifted down and my version doesn't [40:14] suffer so badly in general as the [40:16] concurrent algorithm guy and going [40:19] forward I get the same scaling algorithm [40:21] everything pushed down concurrent guy [40:22] pushed down harder [40:24] generally and then again here 400 [40:26] threads and go 800 threads here I'm [40:28] getting like a 3X difference here [40:30] between concurrent and the non-blocking [40:33] algorithm so it's a [40:35] 95% guy so he's getting 750 million [40:39] reads a second and uh whatever 12th that [40:42] comes in updates a second and I did for [40:45] 90% has the same thing let me go swich [40:47] to the 75 [40:49] here 75% so this is a table with a lot [40:51] more modifications here and basically [40:54] this guy's flatlined he can't even with [40:56] 4,00 way striping he can't handle the [40:58] update rate so that's 600 million reads [41:01] a second uh no a quarter of 150 million [41:05] updates a second on the shared hash [41:08] table [41:11] so I'm [41:14] sorry the 75 uh we have to back [41:21] up it yeah it's it's all it's like tied [41:23] on Niagra and for everyone else it beats [41:25] pretty handily so here's green which is [41:27] the older sunbox splitting non-blocking [41:30] beats blocking here is aul 384 way [41:35] here's a 768 way uh and here's Niagara [41:39] just a flatline [41:40] tide ramping up I didn't keep going here [41:42] on the on the Niagara thread count but [41:45] he hasn't pegged out yet even though [41:47] he's like should be pegging out at 32 [41:49] you'd [41:53] think any resizing occur during The [41:55] Benchmark so right so um I always [41:59] started the Benchmark with uh uh a tiny [42:02] hash table and so uh it rapidly inflated [42:06] to whatever the the ideal size was um I [42:09] ran uh seven 2C trials and threw away [42:13] the high and the low and then averaged [42:15] and uh in that time the first run was [42:18] always sucked on the non-blocking while [42:20] he was doing his resizing so suck [42:22] meaning factor of two to three slower [42:25] than sort of steady state and once he [42:27] got to the right volume then he was [42:29] consistently up by 2X or so so there's [42:32] clearly an overhead paid during the [42:34] resize [42:36] um I could go through and [42:39] do the you know do a version which [42:42] showed what the resize costs were a [42:44] little more directly but I kind of think [42:46] that in a normal case the resize should [42:49] get out of the way pretty quick you [42:50] should end up with the right size and be [42:51] done now I did run a version just second [42:54] I did run a version where I forc sort of [42:56] the worst possible Behavior out of my [42:57] hash table where I did only inserts and [42:59] deletes of a continuous rolling key set [43:02] such that I only had like a thousand [43:03] Keys live but I inserted a million of [43:05] the table and the other 999 billion were [43:07] all dead and so I had to resize the [43:09] table constantly to clean it so this is [43:11] a Non-Stop resize operation um and there [43:15] uh uh you know the performance was [43:18] clearly down from these numbers by an [43:19] interesting amount but it's still held [43:22] at a at a throughput rate compared to [43:25] the concurrent guy which has to do now [43:27] now uh non-stop blocks in order to do [43:30] concurrent updates on his 4,000 way [43:32] striping um I was still like 5x faster [43:35] um so the update rate was killing him as [43:38] well now my on my version of things [43:41] because I'm using prime wrappers I'm [43:44] doing gar uh allocation to do uh copy [43:47] and I hit GC limits and so uh the the [43:51] maximum throughput I achieved uh hit [43:53] like at like 500 threads and it was [43:56] because I was turnning [43:57] some number of gigabytes a second of [43:59] allocation in order to do the continuous [44:01] table copies uh and the concurrent guy [44:03] pegged out at a much lower number um [44:05] because he just ran out of locks I [44:07] needed to stripe it much bigger than [44:08] 4,000 [44:10] way you a question just answer this [44:15] okay so yeah and I don't know what the [44:18] right the right Benchmark to show here [44:20] because I don't have somebody who who [44:22] has a need for you know I mean I I do [44:26] have customers who are [44:27] screaming they want a better hash table [44:29] so I'm going to hand this off and we'll [44:30] see how it goes but I don't yet have an [44:32] obvious use case that I can talk about [44:33] in public where this beats anything you [44:35] could do any other [44:36] way I'm just wondering why you start [44:39] always with the small hash table if if [44:41] the uh if the user knows the correct [44:44] size and it is so the answer is that the [44:46] users think they [44:48] know and and you know time and time [44:50] again that's sort of proven correct [44:52] sometimes they're right and sometimes [44:54] they're badly wrong and then and if I [44:57] just do it all the time then they pay a [45:00] cost to get started except that that [45:03] cost is always over with in a couple [45:04] seconds and there's no more cost and [45:06] then then they're never wrong again [45:08] right if the if the caller guesses too [45:12] low then no different then it's no [45:15] different they get too high it's they [45:17] waste a lot of memory so right so if I [45:20] have a million inry table and the guy [45:21] guesses 10 million then I can blow off [45:24] you know 9 million times 8 bytes for key [45:27] times 8 bytes for Value I can blow off [45:29] you know 20 Megs 40 Megs it's pretty [45:31] easy to get when you get really big you [45:33] get small numbers you don't care when [45:34] you get the big numbers it's easy to get [45:35] it wrong by big factors and then you can [45:38] blow off big chunks of ram the other [45:40] thing that happens is that people will [45:41] guess that they need a a modest Siz [45:43] table uh but they need lots and lots of [45:46] them and and the real answer is you know [45:48] they picked a number which knows pretty [45:49] much bigger than what they really need [45:50] but not a whole lot bigger so they say I [45:52] need 100 elements or 200 elements and [45:53] they only put one or two in ever but [45:55] then they make 10,000 of these tables [45:57] and every one of them's too big by a [45:58] factor of 100 and then they they lose a [46:01] lot of memory that way too and I've seen [46:02] it go both ways so you just resize and [46:05] do your thing and and you know at some [46:07] point maybe I want to take it as a hint [46:08] and I can use it as a hint but at the [46:10] moment I'm happy to ignore the hint and [46:12] Go My Own [46:18] Way okay so that's sort of the end of [46:20] the talk [46:22] um it's a faster hash table faster for [46:25] more CPUs much faster for higher table [46:28] modification rate and the more [46:30] interesting thing to me is that I'm [46:32] using a state machine to do my reasoning [46:35] to figure out how I can be correct to [46:38] look at you know I don't know what's [46:39] really going on but I got a key in value [46:41] so I'm going to pick a spot in the state [46:42] machine here I'm going to go attempt a [46:45] cast go to there and that means that I [46:47] can [46:48] um I can dodge the ordering uh and [46:51] fencing games that go into the JMM turns [46:53] out that I have to pay attention when I [46:55] go between tables but within the same [46:57] table I can ignore that ordering um and [46:59] that actually helps scaling a lot as [47:00] well it means I don't have to do uh [47:02] machine wide coherency on updates I just [47:04] need to do local coherency on updates um [47:08] and you know more games any thread can [47:10] see any state any time it kind of [47:12] changes the way you think about things [47:13] and that state machine picture I drew I [47:16] drew lots of those on pieces of paper [47:17] while I was working through this those [47:19] really helped coding and debugging and [47:20] really in the end the code I wrote [47:22] looked like the state machine I mean it [47:24] it it just look at the state machine and [47:26] every point there some transition to go [47:28] to somewhere else and that's what the [47:29] code does so I end up with some piece of [47:31] code that's really small and [47:34] fast so obvious future work uh tools to [47:38] check the states did I get them all did [47:40] I have all same transitions right um [47:43] given I got a state machine that I'm [47:45] just coding exactly an algorithm [47:46] straight from the state machine why [47:47] can't I just automatically generate the [47:49] code right um the whole notion of using [47:53] a state machine to think about things uh [47:55] seems like it ought to have Broad water [47:57] applicability I haven't got sort of like [47:59] another Smoking Gun here's an obvious [48:01] thing to do with it although I have been [48:03] looking at a concurrent version of java [48:04] util Vector um and you know some pieces [48:08] of that are you know Mak sense now do [48:10] append and delete and uh you know get [48:13] last or whatever there's a bunch of [48:14] things people you use Vector sometimes [48:16] for work list style algorithms I think I [48:18] can do that [48:19] concurrently um I'm I've got a Blog and [48:22] I'm tending to put the code there uh at [48:26] this point um I think I we're stuck on a [48:28] name and we're stuck on uh picking your [48:31] favorite open source license toour so I [48:34] don't know what the right license is [48:37] here we're debating that at work but [48:39] it's clear that we have customers who [48:41] are interested and we clearly we have a [48:43] broader audience that's interested in it [48:44] as well so we open source it at some [48:46] point [48:47] here that's [48:54] it do you have raise issues with [48:59] maintaining the size and deciding when [49:01] to resize like if the size gets updated [49:04] too late you might go through [49:07] entries and never find one [49:10] to so the size is never um never [49:14] guaranteed to be coherent with like an [49:16] iteration over the table unless no one [49:19] else is doing [49:20] updates right um so is that one of your [49:22] questions I mean that basically how do [49:24] you keep the size coherent really the [49:26] the the issue is um how do I update the [49:29] size in a scalable way because if I have [49:32] 750 threads all like uh incrementing a [49:34] counter then I'll I'll drop counts [49:36] unless that count is synchronized and if [49:38] it's synchronized then it's a choke [49:40] point so I had to have striped counter [49:42] updates to have a chance of scaling the [49:44] counts up that was the sort of the step [49:46] one solution problem there that's um [49:49] striped Cass counters to get counter [49:51] updates once I did all that work uh I [49:53] can do the counts accurately and asking [49:55] for size has to walk through the striped [49:57] updates and tell you the you know sum [49:59] them all so it's not not a variable read [50:01] it's a little bit more complicated um [50:04] but there is no guarantee than otherwise [50:05] on the size that you got back and the [50:08] contents of the table unless nobody else [50:10] is updating the table right so you were [50:13] asking maybe you know if somebody came [50:15] along and deleted 10 elements out and [50:17] you asked for size and got 100 now [50:18] there's 95 or 90 because pun things got [50:20] deleted and you do a for Loop and try to [50:22] iterate over the table you don't have [50:24] any guarantees there any in the first [50:25] place decide when [50:28] to grow the table or when to shrink the [50:31] table okay so um growing happens when I [50:35] run out of slots which I count the same [50:37] way I count size slots are when the keys [50:40] get consumed by a permanent entry of a [50:42] key right and when that hits some [50:44] fraction of the size of the table uh I [50:47] it's time to grow the table the other [50:48] way I decide is if a single thread [50:51] repoes too hard too often he he he he's [50:54] looking for a key that slots full [50:56] looking for another slot looking in the [50:58] next slot next slot it's all full full [50:59] full full full he hunts a long time [51:01] decides I've hunted a long time it's [51:02] time to grow the table and that will [51:04] double theze of the table and spread the [51:05] keys out better and then I can go you [51:07] know uh find an empty slot to insert my [51:09] key in will you sh the table I debated [51:13] back and forth on this at this point the [51:14] answer is no I could same issue I have [51:17] to decide the table's full of dead Keys [51:21] uh and and after resize realize that it [51:23] remains you know I mean have to count [51:26] the key have to count the live slots to [51:28] debate to re to shrink it at the moment [51:30] I'm not counting live slots directly [51:32] guess I could I haven't size yeah I [51:35] could do I could figure out how to do it [51:37] do it really an interesting thing though [51:39] if you've already inflated to some large [51:42] size uh aren't you going to get back [51:44] there again you've you've survived being [51:47] big now why shrink and then have to grow [51:52] again at some point I'm sorry probably [51:55] not memory constrained already yeah [51:58] you've already shown you're not memory [51:59] constrained somebody else might want to [52:00] get big well so it's an issue if you're [52:03] playing pingpong with somebody over here [52:05] right you're growing and then shrinking [52:06] so he can grow and Shrink so you can [52:07] grow and shrink it seems a very [52:09] complicated use case I'm convinced that [52:12] it's an interesting thing to do not that [52:13] I don't think it can't be done I just [52:15] think it's uninteresting to do [52:16] it all all the standard data structures [52:19] have the same issue a raist and Vector [52:21] they also never shrink and and some [52:24] people think that's a bug [52:26] that's an open question [52:29] right uh so at some point in time [52:32] someone decides that it needs to regrow [52:35] and you know it needs to grow the table [52:36] it needs to allocate a new table right [52:39] right right how how how are you sure [52:42] that that there are not two different [52:44] threads that suddenly decided at the [52:46] same time that they need to grow oh they [52:48] do they absolutely do so but there's one [52:50] word which holds the point to the next [52:52] new table and they C it from a null to [52:54] the new table one guy wins the Cass the [52:57] other guy loses the loser throws his [52:59] table away he doesn't copy it he first [53:01] CES it in once you inserted the new [53:03] table all you've inserted as a blank [53:05] array an empty array and then now people [53:07] have to start copying from the old to [53:08] the new so it's all this state machine [53:10] based thing one of the states is insert [53:12] the table and then it's fractioned into [53:14] a billion little states where everyone [53:16] copies individually the slots from the [53:17] old to the new and then there's you know [53:20] stripping the primes off things in the [53:22] new table uh and then when that's all [53:24] done I can say you know I'm done with [53:25] the copy on the old table I can now [53:28] promote the new table to be the root [53:30] table uh and then the old table will get [53:32] garbage collected at some [53:34] point I was noticing that that really [53:37] your algorithm is directly alfus to a [53:39] copy garbage collector it is and the uh [53:42] Prime value acts as [53:44] your sure um although it wouldn't be [53:49] portable did this and one of their goals [53:52] was affordable um we considered uh [53:55] actually linking this in and making the [53:57] garbage collector do all the support for [53:59] you you know like I said like you said [54:01] like I I want to be portable if I didn't [54:03] want to be portable the first thing I do [54:05] is I get rid of the Prime wrapper and [54:06] use a prime bit and that was the sort of [54:09] the major cost in any of the table copy [54:11] operations is messing with that extra [54:13] bit by doing a [54:15] wrapper um you know if I would write [54:18] this in C code yeah I'd use a prime bit [54:20] in a second I you know I'd steal a [54:21] pointer bit in a second um doesn't your [54:23] machine have the re barrier oh sure I [54:27] just don't want to integrate at that [54:29] level [54:30] I I'm trying to push this out in the [54:33] public domain so I get people customers [54:35] who come to us with it already in their [54:37] code so I don't have to go say okay well [54:40] you managed to use four out of 700 CPUs [54:43] let's rewrite the hashtable [54:44] implementation you got right it starts [54:46] out the good side good version that I [54:47] don't [54:52] care um yeah so all right so yes um I [54:56] have uh talked long and hard with Doug [54:59] Lee on this we go back and forth all the [55:01] time um some version of this is likely [55:03] to hit Java util concurrent at some [55:05] point uh last time Doug and I talked he [55:08] was of the opinion that the identity [55:12] test version made sense and the regular [55:16] uh and the non-identity requiring a an [55:18] equals test did not for whatever reason [55:20] whether to whether you memorized hash or [55:22] something you had some version a reason [55:24] why one was better than the other I [55:26] can't remember the exact details but the [55:29] end result was uh yeah some instance of [55:31] this probably goes back that was say [55:33] three or four months AG since then I [55:35] have sort of refined the algorithm a [55:36] bunch uh got correctness a lot more I'm [55:39] lot more comfortable with the [55:40] correctness of the algorithm and I've [55:41] shown the performance uh is very good [55:44] across a wide range of things including [55:46] against Java util concurrent hashmap [55:48] with very large scaling with very large [55:50] striping [55:51] factors so some version of this is [55:54] likely to hit the the libraries [55:56] eventually [56:00] anyhow what what is the bound on memory [56:03] usage of this seems to me that it would [56:05] be the size of your hash table times the [56:07] number of [56:09] threads because let's say you have a [56:11] hash table which is 1 gab and it's [56:14] getting full so thre a wants to double [56:17] it to 2 gb so thre a goes to allocate a [56:19] 2 GB object that takes a while so thread [56:22] B comes along and Ela wants to double it [56:24] so it allocates on 2 GB subject does [56:27] that right um so so the the Practical [56:33] upper bound is that you only get a [56:34] handful of guys attempting to do the [56:36] concurrent uh allocation the theoretical [56:39] upper bound is that everyone tries to go [56:40] at the same time and grab a large array [56:43] and if they throw an out of memory while [56:45] trying to do that you can simply throw [56:46] it away and say I give up and go back [56:48] doing the old table not bother with the [56:49] resize um so it's survivable in that [56:52] sense um I could certainly do a version [56:56] where uh uh you were discouraged from uh [57:01] making multiple copies but I can't block [57:03] on the allocation or it becomes no [57:05] longer Lock Free right so uh what I [57:07] really do now is I do the allocation uh [57:10] and immediately install it before I do [57:12] any sort of table cleanup preparation [57:16] kind of things so that people quit [57:17] trying to make concurrent copies and in [57:20] practice with 700 guys and table [57:21] resizing rapidly um I only get a handful [57:25] of extra arrays [57:27] it doesn't it seems very hard to hit [57:29] that particular race uh you'll get a [57:31] couple um and then the question becomes [57:35] how long does it take to allocate a [57:36] large [57:37] array and for aul it's not so bad I [57:41] think for other folks might be a little [57:43] more [57:49] expensive so if you uh if you're not [57:52] going to use the array you just [57:54] allocated because somebody beat you to [57:55] the punch [57:56] it's garbage collection you drop it on [57:57] the floor the next Young Generation GC [58:00] cycle will reclaim it for no [58:07] work [58:10] yes yes that was what I was getting at [58:13] we have zeroing Hardware it's not [58:15] totally free or anything but it helps [58:25] [Applause] [58:30] [Music]