Java 容器 --- 并发一致性问题（ConcurrentHashMap/CopyOnWriteList总结）

并发读写数据一致性保证（Java并发容器）

写在前

业务开发过程，其实就是用户业务数据的处理过程，因而开发的核心任务就是维护数据一致不出错。现实场景中，多个用户会并发读写同一份数据（如秒杀），不加控制会翻车、加了控制则降低并发度，影响性能和用户体验。

如何优雅的进行并发数据控制呢？本质上需要解决两个问题：

• 读-写冲突
  
• 写-写冲突

让我们看下Java经典的并发容器CopyOnWriteList以及ConcurrentHashMap是如何协调这两个问题的

CopyOnWriteList

读写策略

CopyOnWrite顾名思义即写时复制策略

针对写处理，首先加ReentrantLock锁，然后复制出一份数据副本，对副本进行更改之后，再将数据引用替换为副本数据，完成后释放锁

针对读处理，依赖volatile提供的语义保证，每次读都能读到最新的数组引用

读-写冲突

显然，CopyOnWriteList采用读写分离的思想解决并发读写的冲突

当读操作与写操作同时发生时：

• 如果写操作未完成引用替换，这时读操作处理的是原数组而写操作处理的数组副本，互不干扰
  
• 如果写操作已完成引用替换，这时读操作与写操作处理的都是同一个数组引用
  

可见在读写分离的设计下，并发读写过程中，读不一定能实时看到最新的数据，也就是所谓的弱一致性。

也正是由于牺牲了强一致性，可以让读操作无锁化，支撑高并发读

写-写冲突

当多个写操作的同时发生时，先拿到锁的先执行，其他线程只能阻塞等到锁的释放

简单粗暴又行之有效，但并发性能相对较差

ConcurrentHashMap（JDK7）

读写策略

主要采用分段锁的思想，降低同时操作一份数据的概率

针对读操作：

• 先在数组中定位Segment并利用UNSAFE.getObjectVolatile原子读语义获取Segment
  
• 接着在数组中定位HashEntry并利用UNSAFE.getObjectVolatile原子读语义获取HashEntry
  
• 然后依赖final不变的next指针遍历链表
  
• 找到对应的volatile值
  

针对写操作：

• 先在数组中定位Segment并利用UNSAFE.getObjectVolatile原子读语义获取Segment
  
• 然后尝试加锁ReentrantLock
  
• 接着在数组中定位HashEntry并利用UNSAFE.getObjectVolatile原子读语义获取HashEntry链表头节点
  
• 遍历链表，若找到已存在的key，则利用UNSAFE.putOrderedObject原子写新值，若找不到，则创建一个新的节点，插入到链表头，同时利用UNSAFE.putOrderedObject原子更新链表头
  
• 完成操作后释放锁

读-写冲突

• 若并发读写的数据不位于同一个Segment，操作是相互独立的
  
• 若位于同一个Segment，ConcurrentHashMap利用了很多Java特性来解决读写冲突，使得很多读操作都无锁化

当读操作与写操作同时发生时：

• 若PUT的KEY已存在，直接更新原有的value，此时读操作在volatile的保证下可以读到最新值，无需加锁
  
• 若PUT的key不存在增加一个节点，或删除一个节点时，会改变原有的链表结构，注意到HashEntry的每个next指针都是final的，因此得复制链表，在更新HashEntry数组元素（即链表头节点）的时候又是通过UNSAFE提供的语义保证来完成更新的，若新链表更新前发生读操作，此时还是获取原有的链表，无需加锁，但是数据不是最新的

可见，支持无锁并发读操作还是弱一致的

写-写冲突

• 若并发写操作的数据不位于同一个Segment，操作是相互独立的
  
• 若位于同一个Segment，多个线程还是由于加ReentrantLock锁导致阻塞等待

ConcurrentHashMap（JDK8）

读写策略

与JDK7相比，少了Segment分段锁这一层，直接操作Node数组（链表头数组），后面称为桶

• 针对读操作，通过UNSAFE.getObjectVolatile原子读语义获取最新的value
  
• 针对写操作，由于采用懒惰加载的方式，刚初始化时只确定桶的数量，并没有初始默认值。当需要put值的时候先定位下标，然后该下标下桶的值是否为null，如果是，则通过UNSAFE.comepareAndSwapObject(CAS)赋值，如果不为null，则加Synchronized锁，找到对应的链表/红黑树的节点value进行更改，后释放锁

读-写冲突

• 若并发读写的数据不位于同一个桶（Node数组），则相互独立互不干扰
  
• 若位于同一个桶，与JDK7的版本相比，简单了许多，但还是基于Java的特性使得许多读操作无锁化

当读操作与写操作同时发生时：

• 若PUT的key已经存在，则直接更新值，此时读操作在volatile的保证下可以获取最新值
  
• 若PUT的key不存在，会新建一个节点 或 删除一个节点的时候，会改变对原有的结构，这时next指针是volatile的，直接插入到链表尾（超过一定长度变成红黑树）等对结构的修改，此时读操作也是可以获取到最新的next
  

因此只要写操作happens-before读操作，volatile语义就可以保证读的数据是最新的，可以说JDK8版本的ConcurrentHashMap是强一致的（此处只关注基本读写（GET/PUT），可能会有弱一致的场景遗漏，例如扩容操作，不过应该是全局加锁的，如有错误烦请指出，共同学习）

写-写冲突

• 若并发读写的数据不位于同一个桶，则相互独立互不干扰
  
• 若位于同一个桶，注意到写操作在不同的场景下采取不同的策略，CAS或Synchronized
  
• 当多个写操作同时发生时，若桶为null，则CAS应对并发写，当第一个写操作赋值成功后，后面的写线程CAS失败，转为竞争Synchronized锁，阻塞等待

小结

为什么这么设计（个人观点）

对数据进行存储必然涉及数据结构的设计，任何对数据的操作都得基于数据结构，常规思路是对整个数据结构加锁，但是锁的存在会大大影响性能，所以接下来的任务，就是找到哪些可以无锁化的操作。

操作主要分为两大类，读和写。

先看写，因为涉及到原有数据的改动，不加控制肯定会翻车，怎么控制呢？写操作也分两种，一种会改变结构，一种不会：

• 对于会改变结构的写，不管底层是数组还是链表，由于改动得基于原有的结构，必然得加锁串行化保证原子操作，优化的点就是锁层面的优化，例如最开始HashTable等synchronized锁到ConcurrentHashMap1.7版本的ReentrantLock锁，再到1.8版本的Synchronized改良锁 。或者数据分散化，concurrnethashmap等基于hash的数据结构比CopyOnWriteList的数据结构就多了桶分散的优势。
  
• 对于不会改变结构的写，或者改动的频率不大（桶扩容频率低），由于锁的开销实在是太大了，CAS是个不错的思路。为什么CopyOnWriteList不用CAS来控制并发写，我个人觉得主要原因还是因为结构变化频繁，可以看下ActomicReferenceArray等基于CAS的数组容器，都是创建后就不允许结构发生变化的。
  

确保数据不会改错之后，读相对就好办了，主要考虑是不是要实时读最新的数据（等待写操作完成），也就是强一致还是弱一致的问题：

• 强一致的话，读就得等写完成，读写竞争同一把锁，这就相互影响了读写的效率。大多数场景下，读的数据一致性要求没有写的要求高，可以读错，但是坚决不可以写错。要是在读的这一刻，数据还没改完，读到旧数据也没关系，只要最后写完对读可见即可。
  
• 还好JMM（Java内存模型）有个volatile可见性的语义，可以保证不加锁的情况下，读也能看到写更改的数据。此外还有UNSAFE包的各种内存直接操作，也可相对高性能的完成可见性语义，
  
• 对读操作而言，最好的数据，就是不变的数据，不用担心被修改引发的各种问题。唯一的不变是变化，一些数据还是有变化的可能，如果要支持这种不变性，或者说尽量减少变化的频率，变化的部分就得在别的地方处理，也就是所谓的读写分离

常见面试问题分析

1.ConcurrentHashMap和Hashtable的区别？

ConcurrentHashMap与HashTable都可以用于多线程的环境（都是线程安全的容器），但是当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。

（1）底层数据结构：

• JDK1.7的ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，Node数组+链表/红黑树;
• Hashtable和JDK1.8之前的HashMap的底层数据结构类似都是采用数组+链表的形式，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的；

（2）实现线程安全的方式（重要）：

• 在JDK1.7的时候，ConcurrentHashMap（分段锁，可重入锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。（JDK1.6以后 对 synchronized锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本；
• Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态。如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

2.ConcurrentHashMap有哪些构造函数？

//无参构造函数
public ConcurrentHashMap() {
}
//可传初始容器大小(initialCapacity)的构造函数
public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}
//可传入map的构造函数
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    this.sizeCtl = DEFAULT_CAPACITY;
    putAll(m);
}
//可设置阈值(加载因子*容量)和初始容量
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
    this(initialCapacity, loadFactor, 1);
}
//可设置初始容量和阈值和并发级别（concurrencyLevel）
public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    if (initialCapacity < concurrencyLevel)   // Use at least as many bins
        initialCapacity = concurrencyLevel;   // as estimated threads
    long size = (long)(1.0 + (long)initialCapacity / loadFactor);
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?
        MAXIMUM_CAPACITY : tableSizeFor((int)size);
    this.sizeCtl = cap;
}

3.ConcurrentHashMap底层具体实现知道吗？实现原理是什么？（怎么保证线程安全的？）

JDK1.7

在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。

• Segment(分段锁)：ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。
  
• 内部结构：ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：

从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

JDK1.8

• ConcurrentHashMap取消了Segment分段锁，采⽤CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表⻓度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红⿊树（寻址时间复杂度为O(log(N))）。
• 对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产⽣并发，效率又提升N倍。
• ConcurrentHashMap的get方法不需要加锁，get方法采用了unsafe方法，来保证线程安全。

ConcurrentHashMap用什么技术保证线程安全？

• jdk1.7：Segment分段锁+HashEntry（存储键值对数据）来进行实现的；
• jdk1.8：放弃了Segment臃肿的设计，采用Node+CAS+Synchronized来保证线程安全；

4.ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？ConcurrentHashMap能完全替代HashTable吗？

HashTable虽然性能上不如ConcurrentHashMap，但并不能完全被取代，两者的迭代器的一致性不同的。

ConcurrentHashMap弱一致性：ConcurrentHashMap可以支持在迭代过程中，当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException，取而代之的是在改变时new新的数据从而不影响原有的数据，iterator完成后再将头指针替换为新的数据，这样iterator线程可以使用原来老的数据，而写线程（添加元素等）也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。ConcurrentHashMap的get，clear，iterator 都是弱一致性的。

hashmap强一致性：HashMap则抛出了ConcurrentModificationException，因为HashMap包含一个修改计数器modCount，当你调用他的next()方法来获取下一个元素时，迭代器将会用到这个计数器。

两者应用具体分析：

• Hashtable的任何操作都会把整个map锁住，是阻塞的。好处是总能获取最实时的更新，比如说线程A调用putAll写入大量数据，期间线程B调用get，线程B就会被阻塞，直到线程A完成putAll，因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队，效率较低。
• ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据，但不会把整个map都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下，效率很高。坏处 是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据，期间线程B调用get，则只能get到目前为止已经顺利插入的部分 数据。

选择哪一个，是在性能与数据一致性之间权衡。ConcurrentHashMap适用于追求性能的场景，大多数线程都只做insert/delete操作，对读取数据的一致性要求较低。

5.ConcurrentHashMap如何发生ReHash？

ConcurrentLevel并发级别（ 实际上是Segment的实际数量 默认16） 一旦设定的话，就不会改变。ConcurrentHashMap当元素个数大于临界值的时候，就会发生扩容。但是ConcurrentHashMap与其他的HashMap不同的是，它不会对Segment 数量增大，只会增加Segment 后面的链表容量的大小。即对每个Segment 的元素进行的ReHash操作。