OpenJDK 英文原文：OpenJDK and HashMap …. Safely Teaching an Old Dog New (Off-Heap!) Tricks

从Java 6开始，要求标准化非堆存储（off-heap）作为Java内部API的提议就已经在JDK强化提案（JEP）中被提出。这种方式的处理能力和堆存储（on-heap）一样高效，并且没有堆存储使用中的一些局限问题。堆存储在百万数量级瞬时使用的对象/值下工作的相当好，但是一旦你试图存储十亿数量级的对象/值时，你就要想办法去避免垃圾回收带来的持续增加的延迟。并且有时系统会要求同时保证大量数据处理和低延迟。非堆存储就是有这样一种能力：独立管理内存空间而不产生垃圾回收压力。Java中管理集合的两个类”Queue“和"HashMap"使用起来相当方便，如果使用这两个已有接口再加上我们自己的垃圾回收机制实现起来应该不是很难。这样既能实现大量数据存储并且能大大减少延迟，相比而言，原有的堆存储方式很容易产生内存不足错误，随之就要重启服务了。

这篇文章将会研究 JEP所带来的影响，将使得我们获悉类似于Java HashMap和新的off-heap的性能。简言之，JEP可能就有“指导”HashMap这个可爱的老家伙的一些新特性的魔法。 JEP所述的特性，在OpenJDK的发布来看，相对于传统的Java平台优先级做了许多重大的改变。

1、关于安全性的重构，这一sun.misc.Unsafe上的有用的部分，被放入了 新的API包。
2、提倡使用新的API包，直接影响高性能的本地内存操作（在off-heap上的本地内存操作对象上）。
3、（通过新的API）提供一个 外部函数接口(FFI)桥 针对Java直接操作系统资源和系统调用。
4、许可了Java运行时能辅助 硬件事务性内存（Hardware Transactional Memory）的提供者能把焦点集中在重写低并发字节码到高并发的 speculatively branched机器码。
5、移除了FUD（坦率的讲这是一种技术偏见），这与使用off-heap编程策略来提升Java的执行性能有关。总的来讲，JEP有几点是很清楚的，在OpenJDK平台上，相对于曾经的   dark craft, secret society of off-heap practitioners，现在的主流对开放是拥抱的。

本文力求（用普遍而温和的方式）让所有对此感兴趣的 Java 开发者都能有所收获。作者希望即使新手也能跟上本文节奏，而不会有看不懂的“磕磕绊绊”；因此不要气馁，耐心坐下来读完吧。本文努力介绍一些历史背景，为以下问题提供思路：

• 堆存储 HashMap 的问题是怎么产生的?

• 在解决这个问题上面，有过哪些经验/教训？

• 在堆存储 HashMap 的应用情景中，有哪些仍未解决的问题？

• 新的 JEP 提供的功能（将 HashMap 非堆存储）能带来哪些好处？

• 未来的 JEP 在解决现在尚未解决的问题上面，有哪些值得期待之处？

那就让我们一起开始这段旅程吧。值得记住的是，在 Java 出现之前，hash 表是实现在原生内存堆中的，如C 和 C++ 都是如此。某种意义上来说，重新引入非堆存储是重新介绍一些古老的技巧，这些技巧当代的开发者往往不曾了解。各种意义上来说，这都是一次“回到未来”的旅程。旅途愉快！

OpenJDK的非堆存储（Off-Heap）的强化提案（JEP）

已经有一些非堆存储（Off-Heap）的强化提案（JEP）被提出来。下面描绘了一个提供非堆存储（Off-Heap）内存的最低要求。方案试图替代现在sun.misc.Unsafe所提供的内容，不仅如此，这些方案还提供了另外一些有用的功能。
提案总结：总的来说就是为sun.misc.Unsafe创建了一个替代的部分，这样就可以不用直接使用那个库。
直接目标：移除需要直接访问的内部类。
间接目标：不提供那些不推荐的方法，也不实现那些不安全（Unsafe）的方法。
成功标准：提供一种方式去实现那些重要的功能，并且达到与那些不安全（Unsafe）和 FileDispatcherImpl的方式一样的性能。
提案动机：当前不安全（Unsafe）的方式就意味着就需要构建更大的，线程上更安全的非堆存储（Off-Heap）结构。这对于最小化垃圾处理器（GC）的开销有益。这对于在进程和内嵌数据库之间的内存共享可以不用C语言和JNI，这也就有可能提供更快更多的移动计算性能。当前的FileDispatcherImpl方式用于实现任意大小内存的映射。（标准API被限制在2GB以内。）

描述：为非堆存储（off-heap）提供一个包装类(类似于 ByteBuffer) ，还需要下面的增强。

• 64位的大小和偏移量

• 对于易失（volatile）的和有序的访问以及比较和交换的操作上有线程安全的结构。

• JVM优化边界检查，开发者控制边界检查。（允许提供安全性设置）

• 有能力在同一缓冲区的不同记录复用一份缓冲。

• 有能力去映射一个非堆存储（off-heap）数据结构，让缓冲区在优化过的方式下进行边界检查。

保留关键功能

• 支持内存映射文件 

• 支持NIO 

• 支持把写操作提交到磁盘

候选方案：直接使用sun.misc.Unsafe
测试：sun.misc.Unsafe和内存映射文件有同样的测试需求。附加的测试应该工作在同样的方式下，要求展示的线程安全的操作为AtomicXxxx类。AtomicXxxx类应该被重写并且单独使用公共的API。

风险: 当一群开发者使用了Unsafe之后，他们可能一致认为没有更适合的替代品。这意味着JEP的范围很广，或者创建了新的JEP覆盖了Unsafe中的其他功能。

其他JDK : NIO

兼容性: 提供了向后兼容的库。它兼容java7，如果你有足够的兴趣去研究的话，也有可能兼容java6。（截止到这篇文章，Java 7是当前的版本）。

安全性: 在理想情况下，安全的风险性不能超过ByteBuffer太多。

性能和可扩展性: 优化边界检查是困难的。为了添加更多的普通操作，则需要把功能添加到新的缓冲区，以减少开销，例如读写UTF。

HashMap简史

“Hash Code”这个概念第一次出现是在1953年1月的《Computing literature》中，H. P. Luhn  (1896-1964) 在一篇 IBM 的内部备忘录中提出了这个术语。当时 Luhn 是要解决这个问题：“给出组成一本教科书的一系列单词，要得出 100% 完整的（单词，出现页码集）对应关系，最好的算法和数据结构是什么？”

H.P. Luhn (1896-1964)

Luhn 写道， “hashcode” 是基本的运算符。 Luhn 写道， “Associative Array” 是基本的运算数。 由此， ‘HashMap’ (也称为 HashTable) 就这样产生了。 注: HashMap 是由 1896 年出生的计算机科学家提出来的。HashMap 可是个老 家伙啦!

从 HashMap 的诞生讲到它的早期应用场景，我们从1950年代跳到1970年代

Niklaus Wirth 在他1976年编写的经典著作《算法 + 数据结构 = 程序》中，谈到对于所有的程序，都可以将“算法”视为基本的运算符，将“数据结构”视为基本的运算“数”。 从那时起，数据结构(HashMap，Heap等)发展缓慢。1987年有一个重大突破， Tarjan 提出了非常著名的 F-Heap ；但除此之外，乏善可陈。要知道，HashMap 是1953年第一次提出的，已经过去60余年啦！ 与此同时，算法方面 (Karmakar 1984, NegaMax 1989, AKS Primality 2002, Map-Reduce 2006, Grover’s Quantum search - 2011) 则进展迅速，为计算的基础建设带来了崭新的、强大的运算符。 然而，现在到了2014，也许又轮到数据结构来取得重大进展了。从 OpenJDK 平台来看， 非堆 HashMap 就是一个正在发展的数据结构。 HashMap 的历史就介绍到这。下面我们来探索今天的 HashMap 吧。具体来说，我们先来看一看这个老家伙在 Java 中现存的 3 种实现。

N. Wirth 1934-

java.util.HashMap (非线程安全)

对于任何真正的多线程并发用例，它会立即失败，而且是每次都会失败。所有用到它的代码必须使用 Java 内存模型(JMM)的内存屏障(memory barrier)策略(如 synchronized 或 volatile) 来保证顺序执行。

一个简单的失败样例如下： - synchronized 的写入 - 没加 synchronized 的读取 - 真正并发 (2 个 CPU/L1)   我们来看看为什么会失败...

假设线程1写入 HashMap，那么它做出的改动只会保存在 CPU 1的1级缓存中。然后线程2，在几秒钟后开始在 CPU 2上运行；它读取 HashMap，是从 CPU 2的1级缓存中读出来的——它看不到线程1做出的改动，因为在读和写的线程中都没有读、写间的内存屏障，虽然 Java 内存模型要求线程共享 HashMap 的情形下必须要有。即使线程1的写操作加了 synchronize 也会失败，这样虽然能把它做出的改动写入到主内存中，但线程2仍然看不到这些改动，因为线程2只会从 CPU 2的1级缓存中读取。所以在写操作上加 synchronized 只能避免写操作的冲突。要对于所有的线程都添加必要的内存屏障，你必须也要 synchronize 读操作。

thrSafeHM = Collections.synchronizedMap(hm) ; （粗粒度锁定）

使用“同步”时实现高性能要求低竞争率。这是很常见的，而且在很多情况下这并不像听起来那么坏。然而，一旦你引入任何竞争（多个线程试图同时操作同一集合），性能就会受到影响。在最坏的情况下，如具有很高的锁争用，你可能会得到多个线程比单个线程（操作没有锁定或任何种类的争夺）的性能表现更差的结论。

Collections.synchronizedMap() 返回一个 MT-Safe HashMap.

这是一个通过粗粒度的锁来实现所有关键部分的mutate()和access()操作，这样可以让多个线程操作整个Map。这个结果在Zero  MT-concurrency中，意味着一个时刻仅有一个线程可以访问。另一个后果就是作为高锁争用（High Lock Contention）的粗粒度锁，锁住的途径是一种非常不受欢迎的已知条件。关于高锁争用（High Lock Contention）（请看在左边的图片，N个线程争用一个锁，但是迫于阻塞只好等待着，锁已经给了正在运行的线程）。

幸好这是完全同步的，不会真正的同步，隔离（isolation）=序列化（SERIALIZABLE）（总体上这是令人失望的）HashMap陷阱，我们期待的OpenJDK非堆存储（off-heap）JEP已经有一个 值得推荐的期待：硬件事务性内存（Hardware Transactional Memory (HTM)）。关于HTM，粗粒度的同步写操作在Java中将会再一次变得很酷！就让HTM通过代码上的零并发和在硬件的零并发来帮助我们，实现真正的并发并且100%的多线程安全。这很酷，对吧？

本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。 2KB翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务