并发编程之并发容器原理分析

一、JUC包下的并发容器Java的集合容器框架中主要有四大类别List、Set、Queue、Map这些集合类ArrayList、LinkedList、HashMap这些容器都是非线程安全的。所以Java先提供了同步容器供用户使用。同步容器可以简单地理解为通过synchronized来实现同步的容器比如Vector、Hashtable以及SynchronizedList等容器。这样做的代价是削弱了并发性当多个线程共同竞争容器级的锁时吞吐量就会降低。因此为了解决同步容器的性能问题所以才有了并发容器。java.util.concurrent包中提供了多种并发类容器1 CopyOnWriteArrayList对应的非并发容器ArrayList目标代替Vector、synchronizedList原理利用高并发往往是读多写少的特性对读操作不加锁对写操作先复制一份新的集合在新的集合上面修改然后将新集合赋值给旧的引用并通过volatile 保证其可见性当然写操作的锁是必不可少的了。2 CopyOnWriteArraySet对应的非并发容器HashSet目标代替synchronizedSet原理基于CopyOnWriteArrayList实现其唯一的不同是在add时调用的是CopyOnWriteArrayList的addIfAbsent方法其遍历当前Object数组如Object数组中已有了当前元素则直接返回如果没有则放入Object数组的尾部并返回。3 ConcurrentHashMap对应的非并发容器HashMap目标代替Hashtable、synchronizedMap支持复合操作原理JDK6中采用一种更加细粒度的加锁机制Segment“分段锁”JDK8中采用CAS无锁算法。4 ConcurrentSkipListMap对应的非并发容器TreeMap目标代替synchronizedSortedMap(TreeMap)原理Skip list跳表是一种可以代替平衡树的数据结构默认是按照Key值升序的。二、CopyOnWriteArrayListCopyOnWriteArrayList 是 Java 中的一种线程安全的 List它是一个可变的数组支持并发读和写。它通过在修改操作时创建底层数组的副本来实现线程安全从而保证了并发访问的一致性。1 应用场景CopyOnWriteArrayList 的应用场景主要有两个方面读多写少的场景由于 CopyOnWriteArrayList 的读操作不需要加锁因此它非常适合在读多写少的场景中使用。例如一个读取频率比写入频率高得多的缓存使用 CopyOnWriteArrayList 可以提高读取性能并减少锁竞争的开销。不需要实时更新的数据由于 CopyOnWriteArrayList 读取的数据可能不是最新的因此它适合于不需要实时更新的数据。例如在日志应用中为了保证应用的性能日志记录的操作可能被缓冲并不是实时写入文件系统而是在某个时刻批量写入。这种情况下使用 CopyOnWriteArrayList 可以避免多个线程之间的竞争提高应用的性能。2 CopyOnWriteArrayList使用基本使用和 ArrayList 在使用方式方面很类似。// 创建一个 CopyOnWriteArrayList 对象 CopyOnWriteArrayList phaser new CopyOnWriteArrayList(); // 新增 copyOnWriteArrayList.add(1); // 设置指定下标 copyOnWriteArrayList.set(0, 2); // 获取查询 copyOnWriteArrayList.get(0); // 删除 copyOnWriteArrayList.remove(0); // 清空 copyOnWriteArrayList.clear(); // 是否为空 copyOnWriteArrayList.isEmpty(); // 是否包含 copyOnWriteArrayList.contains(1); // 获取元素个数 copyOnWriteArrayList.size();IP 黑名单判定当应用接入外部请求后为了防范风险一般会对请求做一些特征判定如对请求 IP 是否合法的判定就是一种。IP 黑名单偶尔会被系统运维人员做更新public class CopyOnWriteArrayListDemo { private static CopyOnWriteArrayListString copyOnWriteArrayList new CopyOnWriteArrayList(); // 模拟初始化的黑名单数据 static { copyOnWriteArrayList.add(ipAddr0); copyOnWriteArrayList.add(ipAddr1); copyOnWriteArrayList.add(ipAddr2); } public static void main(String[] args) throws InterruptedException { Runnable task new Runnable() { public void run() { // 模拟接入用时 try { Thread.sleep(new Random().nextInt(5000)); } catch (Exception e) {} String currentIP ipAddr new Random().nextInt(6); if (copyOnWriteArrayList.contains(currentIP)) { System.out.println(Thread.currentThread().getName() IP currentIP 命中黑名单拒绝接入处理); return; } System.out.println(Thread.currentThread().getName() IP currentIP 接入处理...); } }; new Thread(task, 请求1).start(); new Thread(task, 请求2).start(); new Thread(task, 请求3).start(); new Thread(new Runnable() { public void run() { // 模拟用时 try { Thread.sleep(new Random().nextInt(2000)); } catch (Exception e) {} String newBlackIP ipAddr3; copyOnWriteArrayList.add(newBlackIP); System.out.println(Thread.currentThread().getName() 添加了新的非法IP newBlackIP); } }, IP黑名单更新).start(); Thread.sleep(1000000); } }3 原理很多时候我们的系统应对的都是读多写少的并发场景。CopyOnWriteArrayList容器允许并发读读操作是无锁的性能较高。至于写操作比如向容器中添加一个元素则首先将当前容器复制一份然后在新副本上执行写操作结束之后再将原容器的引用指向新容器。线程安全的多线程环境下可以直接使用无需加锁通过锁 数组拷贝 volatile 关键字保证了线程安全每次数组操作都会把数组拷贝一份出来在新数组上进行操作操作成功之后再赋值回去。从整体架构上来说CopyOnWriteArrayList 数据结构和 ArrayList 是一致的底层是个数组只不过 CopyOnWriteArrayList 在对数组进行操作的时候基本会分四步走加锁从原数组中拷贝出新数组在新数组上进行操作并把新数组赋值给数组容器解锁除了加锁之外CopyOnWriteArrayList 的底层数组还被 volatile 关键字修饰意思是一旦数组被修改其它线程立马能够感知到代码如下private transient volatile Object[] array;整体上来说CopyOnWriteArrayList 就是利用锁 数组拷贝 volatile 关键字保证了 List 的线程安全。3.1 优点读操作不加锁性能很高因为无需任何同步措施比较适用于读多写少的并发场景。Java的list在遍历时若中途有别的线程对list容器进行修改则会抛ConcurrentModificationException异常。而CopyOnWriteArrayList由于其读写分离的思想遍历和修改操作分别作用在不同的list容器所以在使用迭代器进行遍历时候也就不会抛出ConcurrentModificationException异常了。3.2 缺点内存占用问题毕竟每次执行写操作都要将原容器拷贝一份。数据量大时对内存压力较大可能会引起频繁GC无法保证实时性因为CopyOnWrite的写时复制机制所以在进行写操作的时候内存里会同时驻扎两个对象的内存旧的对象和新写入的对象注意在复制的时候只是复制容器里的引用只是在写的时候会创建新对象添加到新容器里而旧容器的对象还在使用所以有两份对象内存4 扩展知识迭代器的 fail-fast 与 fail-safe 机制在 Java 中迭代器Iterator在迭代的过程中如果底层的集合被修改添加或删除元素不同的迭代器对此的表现行为是不一样的可分为两类Fail-Fast快速失败和 Fail-Safe安全失败。4.1 fail-fast 机制fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时就可能会产生 fail-fast 事件。例如当某一个线程A通过 iterator 去遍历某集合的过程中若该集合的内容被其他线程所改变了那么线程A访问集合时就会抛出ConcurrentModificationException异常产生 fail-fast 事件。在 java.util 包中的集合如 ArrayList、HashMap 等它们的迭代器默认都是采用 Fail-Fast 机制。4.1.1 fail-fast解决方案方案一在遍历过程中所有涉及到改变modCount 值的地方全部加上synchronized 或者直接使用 Collection#synchronizedList这样就可以解决问题但是不推荐因为增删造成的同步锁可能会阻塞遍历操作。方案二使用CopyOnWriteArrayList 替换 ArrayList推荐使用该方案即fail-safe。4.2 fail-safe机制任何对集合结构的修改都会在一个复制的集合上进行因此不会抛出ConcurrentModificationException。在 java.util.concurrent 包中的集合如 CopyOnWriteArrayList、ConcurrentHashMap 等它们的迭代器一般都是采用 Fail-Safe 机制。4.2.1 缺点采用 Fail-Safe 机制的集合类都是线程安全的但是它们无法保证数据的实时一致性它们只能保证数据的最终一致性。在迭代过程中如果集合被修改了可能读取到的仍然是旧的数据。Fail-Safe 机制还存在另外一个问题就是内存占用。由于这类集合一般都是通过复制来实现读写分离的因此它们会创建出更多的对象导致占用更多的内存甚至可能引起频繁的垃圾回收严重影响性能。三、ConcurrentHashMapConcurrentHashMap 是 Java 中线程安全的哈希表它支持高并发并且能够同时进行读写操作。在JDK1.8之前ConcurrentHashMap使用分段锁以在保证线程安全的同时获得更大的效率。JDK1.8开始舍弃了分段锁使用自旋CASsynchronized关键字来实现同步。官方的解释中一是节省内存空间 二是分段锁需要更多的内存空间而大多数情况下并发粒度达不到设置的粒度竞争概率较小反而导致更新的长时间等待因为锁定一段后整个段就无法更新了三是提高GC效率。1 应用场景ConcurrentHashMap 的应用场景包括但不限于以下几种共享数据的线程安全在多线程编程中如果需要进行共享数据的读写可以使用 ConcurrentHashMap 保证线程安全。缓存ConcurrentHashMap 的高并发性能和线程安全能力使其成为一种很好的缓存实现方案。在多线程环境下使用 ConcurrentHashMap 作为缓存的数据结构能够提高程序的并发性能同时保证数据的一致性。2 ConcurrentHashMap使用基本用法// 创建一个 ConcurrentHashMap 对象 ConcurrentHashMapObject, Object concurrentHashMap new ConcurrentHashMap(); // 添加键值对 concurrentHashMap.put(key, value); // 添加一批键值对 concurrentHashMap.putAll(new HashMap()); // 使用指定的键获取值 concurrentHashMap.get(key); // 判定是否为空 concurrentHashMap.isEmpty(); // 获取已经添加的键值对个数 concurrentHashMap.size(); // 获取已经添加的所有键的集合 concurrentHashMap.keys(); // 获取已经添加的所有值的集合 concurrentHashMap.values(); // 清空 concurrentHashMap.clear();其他方法V putIfAbsent(K key, V value)如果key已存在则不进行插入并返回原有值如果key不存在则插入新值并返回 null。boolean remove(Object key, Object value)如果 key 对应的值是 value则移除 K-V返回 true。否则不移除返回 false。boolean replace(K key, V oldValue, V newValue)如果 key 对应的当前值是 oldValue则替换为 newValue返回 true。否则不替换返回 false。computeIfAbsent(key,Function)如果存在则返回key的值。如果不存在则Function返回值作为key的值merge(keyvalueBiFunction)不存在指定的key时将value设置为key的值。当key存在值时执行BiFunction接收oldKey和value返回结果设置为key的值。3 统计文件中英文字母出现的总次数将26个英文字母分别循环200次每个字母作为一个单词一共有5200个单词。每个单词中间用\n分隔乱序存入26个文件中生成26个线程对26个文件中的单词进行计数存入map中3.1 生成测试文件/** * 生成测试文件 * throws IOException */ public void produceData() throws IOException { //定义26个字母的字符串 String dataabcdefghijklmnopqrstuvwxyz; ListString listnew ArrayList(); //循环遍历26个字母每个字母循环200次最后将5200个字母放入集合 for (int i 0; i data.length(); i) { for (int j 0; j 200; j) { list.add(String.valueOf(data.charAt(i))); } } //将集合打乱 Collections.shuffle(list); //遍历26次。每次取出集合中的200个元素加上“换行符”放入文件中 for (int i 0; i 26; i) { try(FileWriter fwnew FileWriter((i1).txt)){ fw.write(list.subList(i*200,(i1)*200).stream().collect(Collectors.joining(\n))); } } }3.2 读取文件/** * 定义读文件的方法 */ private static void read(List list, int i) { //创建输入缓冲字符流 try (BufferedReader bf new BufferedReader(new FileReader((i 1) .txt))) { String data; //读取每行数据判断是否为空 while ((data bf.readLine()) ! null) { //将字母加入到集合中 list.add(data); } } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } }3.3 生成线程操作每个文件对应的list存放到线程共享的map/** * 定义26个线程读26个文件并将结果放入map。map由函数式接口作为参数提供放入map由Consumer函数式接口处理。 * * param supplier 提供者提供map集合存放单词计数 * param consumer 消费者对list第二个参数进行计数并存入map第一个参数中 */ private static T void deal(SupplierMapString, T supplier, BiConsumerMapString, T, ListString consumer) { //获得map集合用于存放单词计数 MapString, T map supplier.get(); //利用闭锁保证26个线程都执行完任务 CountDownLatch count new CountDownLatch(26); //循环创建26个线程读取26个文件的内容并进行计数操作 for (int i 0; i 26; i) { int j i; new Thread(() - { ListString list new ArrayList(); //读取文件 read(list, j); consumer.accept(map, list); count.countDown(); }).start(); } try { count.await(); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println(map); }实现两个参数一是提供一个 map 集合用来存放每个单词的计数结果key 为单词value 为计数二是提供一组操作保证计数的安全性会传递 map 集合以及 单词 List正确结果输出应该是每个单词出现 200 次{a200, b200, c200, d200, e200, f200, g200, h200, i200, j200, k200, l200, m200, n200, o200, p200, q200, r200, s200, t200, u200, v200, w200, x200, y200, z200}3.4 测试代码// 换成ConcurrentHashMap可以吗 deal(() - new HashMapString, Integer(), (map, words) - { for (String word : words) { Integer counter map.get(word); int newValue counter null ? 1 : counter 1; map.put(word, newValue); } }); //正确的实现1 deal(() - new ConcurrentHashMapString, LongAdder(), (map, list) - { //遍历集合内容 list.forEach(str - { //单词数累加map中没有str的key则new LongAdder有则进行加1 map.computeIfAbsent(str, (key) - new LongAdder()).increment(); }); }); //正确的实现2 deal(() - new ConcurrentHashMapString, Integer(), (map, list) - { //遍历集合内容 list.forEach(str - { //单词数累加map中没有str的key则set(str,1)有则set(str,Integer.sum(oldvalue,1)) map.merge(str, 1, Integer::sum); }); });4 数据结构4.1 HashTable的数据结构4.2 JDK1.7中的ConcurrentHashMap在jdk1.7中结构是用Segments数组 HashEntry数组 链表实现的 写分散的思想。ConcurrentHashMap内部维护了一个Segment数组。每个Segment继承自ReentrantLock并且它内部本质上是一个Hash表。这样做的好处是能够减小锁的粒度提高并发访问的效率。默认Segment 数量为 16可以通过构造函数来修改默认值。当需要put或get一个元素时线程首先通过hash定位到具体的Segment然后在对应的Segment上进行锁定操作。4.3 JDK1.8中的ConcurrentHashMapjdk1.8抛弃了Segments分段锁的方案而是改用了和HashMap一样的结构操作也就是数组 链表 红黑树结构比jdk1.7中的ConcurrentHashMap提高了效率在并发方面使用了cas synchronized的方式保证数据的一致性链表转化为红黑树需要满足2个条件:链表的节点数量大于等于树化阈值8Node数组的长度大于等于最小树化容量值64#树化阈值为8static final int TREEIFY_THRESHOLD 8;#最小树化容量值为64static final int MIN_TREEIFY_CAPACITY 64;四、ConcurrentSkipListMapConcurrentSkipListMap 是 Java 中的一种线程安全、基于跳表实现的有序映射Map数据结构。它是对 TreeMap 的并发实现支持高并发读写操作。ConcurrentSkipListMap适用于需要高并发性能、支持有序性和区间查询的场景能够有效地提高系统的性能和可扩展性。1 跳表跳表是一种基于有序链表的数据结构支持快速插入、删除、查找操作其时间复杂度为O(log n)比普通链表的O(n)更高效。https://cmps-people.ok.ubc.ca/ylucet/DS/SkipList.html图一图二图三1.1 跳表的特性一个跳表结构由很多层数据结构组成。每一层都是一个有序的链表默认是升序。也可以自定义排序方法。最底层链表图中所示Level1包含了所有的元素。如果每一个元素出现在LevelN的链表中N1)那么这个元素必定在下层链表出现。每一个节点都包含了两个指针一个指向同一级链表中的下一个元素一个指向下一层级别链表中的相同值元素。1.2 跳表的查找1.3 跳表的插入跳表插入数据的流程如下找到元素适合的插入层级K这里的K采用随机的方式。若K大于跳表的总层级那么开辟新的一层否则在对应的层级插入。申请新的节点。调整对应的指针。假设我要插入元素13原有的层级是3级假设K4倘若K22 ConcurrentSkipListMap使用基本用法public class ConcurrentSkipListMapDemo { public static void main(String[] args) { ConcurrentSkipListMapInteger, String map new ConcurrentSkipListMap(); // 添加元素 map.put(1, a); map.put(3, c); map.put(2, b); map.put(4, d); // 获取元素 String value1 map.get(2); System.out.println(value1); // 输出b // 遍历元素 for (Integer key : map.keySet()) { String value map.get(key); System.out.println(key : value); } // 删除元素 String value2 map.remove(3); System.out.println(value2); // 输出c } }五、电商场景中并发容器的选择案例一电商网站中记录一次活动下各个商品售卖的数量。场景分析需要频繁按商品id做get和set但是商品idkey的数量相对稳定不会频繁增删初级方案选用HashMapkey为商品idvalue为商品购买的次数。每次下单取出次数增加后再写入问题HashMap线程不安全在多次商品id写入后如果发生扩容在JDK1.7 之前在并发场景下HashMap 会出现死循环从而导致CPU 使用率居高不下。JDK1.8 中修复了HashMap 扩容导致的死循环问题但在高并发场景下依然会有数据丢失以及不准确的情况出现。选型Hashtable 不推荐锁太重选ConcurrentHashMap 确保高并发下多线程的安全性案例二在一次活动下为每个用户记录浏览商品的历史和次数。场景分析每个用户各自浏览的商品量级非常大并且每次访问都要更新次数频繁读写初级方案为确保线程安全采用上面的思路ConcurrentHashMap问题ConcurrentHashMap 内部机制在数据量大时会把链表转换为红黑树。而红黑树在高并发情况下删除和插入过程中有个平衡的过程会牵涉到大量节点因此竞争锁资源的代价相对比较高选型用跳表ConcurrentSkipListMap将key值分层逐个切段增删效率高于ConcurrentHashMap结论如果对数据有强一致要求则需使用Hashtable在大部分场景通常都是弱一致性的情况下使用ConcurrentHashMap 即可如果数据量级很高且存在大量增删改操作则可以考虑使用ConcurrentSkipListMap。案例三在活动中创建一个用户列表记录冻结的用户。一旦冻结不允许再下单抢购但是可以浏览。场景分析违规被冻结的用户不会太多但是绝大多数非冻结用户每次抢单都要去查一下这个列表。低频写高频读。初级方案ArrayList记录要冻结的用户id问题ArrayList对冻结用户id的插入和读取操作在高并发时线程不安全。Vector可以做到线程安全但并发性能差锁太重。可以使用CopyOnWriteArrayList。选型综合业务场景选CopyOnWriteArrayList会占空间但是也仅仅发生在添加新冻结用户的时候。绝大多数的访问在非冻结用户的读取和比对上不会阻塞。