编程语言高级主题:无锁哈希表
Advanced Topics in Programming Languages: A Lock-Free Hash Table
频道:GoogleTalksArchive · 时长:58:35 · 发布:2012-08-22 · 播放:29135
简介
2007 年的一场 Google Tech Talk,Azul Systems 的 Cliff Click 介绍了一个可扩展到 768 个 CPU 的无锁并发哈希表。他解释了为何它正确,其推理方式不同于通常的 happens-before 和内存序论证。
HN 为什么推荐
HN 认为它是最好的技术演讲之一,深入清晰地讲解了基于 compare-and-swap 的可扩展无锁哈希表。
我强烈推荐 Cliff Click 这场关于通过 Compare And Swap 构建高可扩展哈希表的演讲 — HN, 2024
中文字幕节选
欢迎来到我们编程语言系列讲座的最新一期,嗯,今天我们 有一位非常特别的嘉宾,呃,一位在街对面Azul工作的男士 研究拥有众多处理器的计算机。他呃,他之前在Sun工作, 是HotSpot VM的首席架构师之一,嗯,他现在在 呃,在Azul做着非常类似的工作,呃,他今天来这里和我们聊聊他的经验, 关于为Java创建一个无锁哈希表的经验,嗯,这个表扩展性非常好。嗯,他的名字 是Cliff Click,这位就是他。 谢谢。嗯,先说明一下,我还不算太落后于时代,我 现在其实有博客了,一周前刚开的,这就是我做事的速度, 嗯,所以今天我要讲两件事,关于哈希表, 以及关于嗯,一种不同的思考并发算法的方式。嗯, 我先从哈希表这部分开始。嗯,我假设在座各位都知道 哈希表是什么,但也许我可以补充一些你们可能 没想过的东西。好,最明显的是,它是一种常数时间的键值 映射,按定义来说就是这样,对吧。嗯,但从键值映射你可以 构建出任意函数,而且它们是可扩展的,函数是什么 是在运行时定义的,所以这非常有用,然后它有 上千种用途,我在这里列了几个。事实证明它在 这些大型商业应用中极其有用,通常用于缓存范式,某种 内容缓存、网页素材、数据库访问等等。呃,这些应用 本身既非常庞大又高度多线程化。嗯,很快 就很容易让这些哈希表成为扩展瓶颈,对吧。所以 市面上有一堆嗯Java实现,都是众所周知、 广为人知的,你知道,Hashtable是老的,HashMap不是线程安全的,然后现在 有一个并发的,嗯,它内部有16路分段,那只是在 写操作上,读是并发的,写者必须争夺16路之一。嗯,但结果 是,呃,如今很容易搞到超过100个CPU的机器,你去 弄一台有750个CPU的。嗯,我们确实有人同时使用所有这些CPU, 所以很快,一个16路分段的哈希表就成了主要瓶颈。 嗯,如今在很多机器上你都能让它成为瓶颈。所以嗯, 不知什么时候我开始研究呃,无锁哈希表,我想我 算是掉进去了。嗯,我最终做出来的东西,事实上是完全无锁的,所以 这里没有锁意味着嗯,没有任何看起来像锁的东西,不只是synchronized 关键字或可重入锁,你知道,java.util.concurrent.locks。呃,你不能有自旋锁或 任何基本上呃,抓住共享资源并永久持有它的东西。所以 由此产生的其他效果之一是,嗯,这意味着 即使其他线程在更新表的过程中死掉,你也能继续推进。所以你可以 有任意的呃,波动发生在表上,人们插入、删除元素,呃, 在操作中途把它们干掉,表也不会损坏。嗯,所有线程 都能完全推进,没有任何呃,没有任何问题。所以呃,我们还从这个 我想我的麦克风掉了。好了,回来了。嗯,我需要呃, 某种原子更新指令,我被告知也许不是每个人 都知道CAS是什么。在座有人愿意承认自己不知道CAS是什么吗?所以 其实有相当一部分人。好,CAS代表compare and swap,它本质上是
HN 上的讨论
对于对这个话题感兴趣的人,我强烈推荐Cliff Click关于通过比较并交换构建高度可扩展哈希表的演讲:[VIDEO] — benreesman, 2024-09
可能是这个: [VIDEO] 克里夫·克里克的任何东西都相当不错。这个人对编译器、虚拟机和CPU及其相互作用有非常深入的理解。JVM能做到吗? [LINK] 在1000个核心上的Java [LINK] — qznc, 2013-04
值得注意的是,对很多人来说,很长一段时间内,Intel TSO实际上是内存模型(据我所知,这使得`std::memory_order_seq_cst`在Intel上几乎免费)。在将C++从Intel移植到更宽松的架构时,许多衣服被撕破,许多牙齿被咬碎。过去,这通常意味着像SPARC这样的架构,今天通常意味着ARM。“获取”和“释放”在孤立的例子中相对容易理解,但直觉并不容易组合。即使使用像CAS这样最简单的无锁原语,也很容易最终出现ABA类型的问题或架构依赖性。再加上在大多数平台上`std::mutex`非常便宜,它真的只是最后的手段,至少在服务器级硬件上。谷歌工程师在这方面比任何人都更有经验,他们在这里很好地总结了:[LINK]。直接使用原子操作并不完全是“自己动手加密”,但显然属于“如果你必须问,就不要使用”的范畴。我已经数不清有多少次我把某个东西模糊测试到火星再回来以证明它“正确”… — benreesman, 2022-08
我一直钦佩Cliff Click的并发哈希的魔法:[LINK] [VIDEO] 我不确定如何看待“原子”哈希。我认为楼主也不确定:“这难道不是有点违背了并发算法的意义吗?嗯,从某种意义上说,它确实使其非原子化,但它并不是真正的自旋锁之类的,尽管它看起来可能像:”并发哈希似乎更正确和清晰。 — eternalban, 2017-05
Cliff Click博士关于无锁哈希表的Google演讲在这里:[VIDEO] 根据Click博士的说法,如果你没有一台拥有30多个CPU的机器,ConcurrentHashMap(JDK内置)在大多数情况下都能解决问题。如果你对设计感到好奇,这个演讲真的值得一看,尤其是Click博士还与Rich Hickey就STM进行过令人难忘的辩论。他在h2o.ai工作,两年前写过关于构建键值存储的文章:[LINK] — ignoramous, 2016-02
相关视频
- JVM 会做那个? · Google TechTalks · 52:37
- Dtrace 回顾 · GoogleTalksArchive · 1:18:02
- John Carmack 主题演讲 - Quakecon 2013 · IGN · 2:49:18
- 在1000核上运行Java - 硬件/软件协同设计的故事 · Google TechTalks · 1:12:01
- AWS re:Invent 2016:周二晚间直播 with James Hamilton · Amazon Web Services · 1:33:27
- Tracy Young 在 2015 年女性创始人大会上的演讲 · Y Combinator · 26:51
- AWS re:Invent 2018:AWS 如何最小化故障影响范围 (ARC338) · Amazon Web Services · 55:43
- Zebras All the Way Down - Bryan Cantrill, Uptime 2017 · Code & Supply · 46:36
- 杰夫·贝索斯 1997 年访谈 · Chuck Severance · 5:39
- 模拟流行病 · 3Blue1Brown · 23:12
- Paxos 讲座(Raft 用户研究) · Diego Ongaro · 1:06:33
- Bret Victor - 在原则中发明 · Rui Oliveira · 54:20
- DNA 动画 (2002-2014) 由 Drew Berry 和 Etsuko Uno 制作 wehi.tv #ScienceArt · WEHImovies · 7:19
- 嘿 Underscore,你做错了! · InfoQ · 36:30
- 主题演讲 - JSON Graph:Netflix 的反应式 REST · Association for Computing Machinery (ACM) · 54:57
- AWS re:Invent 2015 | (NET403) 又一天,又十亿个数据包 · Amazon Web Services · 42:25
- 软件设计哲学 | John Ousterhout | Talks at Google · Talks at Google · 1:01:40
- 用 Linux 替换充满漏洞的固件 - Ronald Minnich, Google · The Linux Foundation · 38:02
- Bryan Cantrill 谈 Jails 和 Solaris Zones · PapersWeLove · 1:45:46
- CppCon 2017: Carl Cook “当一微秒即是永恒:C++ 高性能交易系统” · CppCon · 1:00:07