当前位置:   article > 正文

java集合深入学习--并发集合_copyonwritearraylist和arraylist会导致内存溢出吗

copyonwritearraylist和arraylist会导致内存溢出吗

CopyOnWriteArrayList/CopyOnWriteArraySet:

——几乎不更新,通常只做遍历

Copy-On-Write简称COW,字面意思为修改内容时进行拷贝。这是一种用于程序设计中的优化策略。其基本思路是,从一开始大家都在共享同一个内容,当某个人想要修改这个内容的时候,才会真正把内容Copy出去形成一个新的内容然后再改,这是一种延时懒惰策略。

然而,由于数组的拷贝开销很大,因此这种策略在需要对集合元素进行频繁更新时

实现细节:

CopyOnWriteArrayList以数组实现,保存了一个transient final ReentrantLock lock的锁,用于在对元素进行写入操作时进行加锁。CopyOnWriteArraySet则是以CopyOnWriteArrayList为基础,其保存了CopyOnWriteArrayList的一个引用,所有操作与CopyOnWriteArrayList类似,只是新增时要检查集合中是否有相同元素。

因为每次写集合时都会创建新副本,所以并不会遇到扩容问题。但是,向集合中添加元素时最好按批次添加,如果每一条新数据添加一次,每次都会复制集合副本,开销过大。

此外,CopyOnWrite机制还解决了其他集合由于快速失败机制带来的问题:在一个线程遍历集合时,如果另一个线程向集合中添加或删除了元素,会抛出ConcurrentModificationException。CopyOnWrite机制允许在遍历集合时向集合中增删元素,因为两者操作的不是一个集合对象。

使用场景:

CopyOnWriteArrayList/CopyOnWriteArraySet尤其适用于极少更新,但是存在大量查询操作的场景。

缺点:(引用自点击打开链接

内存占用问题:

因为CopyOnWrite的写时复制机制,所以在进行写操作的时候,内存里会同时驻扎两个对象的内存,旧的对象和新写入的对象(注意:在复制的时候只是复制容器里的引用,只是在写的时候会创建新对象添加到新容器里,而旧容器的对象还在使用,所以有两份对象内存)。如果这些对象占用的内存比较大,比如说200M左右,那么再写入100M数据进去,内存就会占用300M,那么这个时候很有可能造成频繁的Yong GC和Full GC。之前我们系统中使用了一个服务由于每晚使用CopyOnWrite机制更新大对象,造成了每晚15秒的Full GC,应用响应时间也随之变长。

数据一致性问题:

CopyOnWrite容器只能保证数据的最终一致性不能保证数据的实时一致性。所以如果你希望写入的的数据,马上能读到,请不要使用CopyOnWrite容器。

性能比价:(引用自:点击打开链接

CopyOnWriteArrayList:专为多线程并发设计的容器,“写入时复制”策略。
Collections.synchronizedMap:同步容器,独占策略。

结果:

线程数量 平均访问时间平均访问时间

CopyOnWriteArrayList
Collections.synchronizedMap
220100
425500
8502200
161208000
3220030000
64550120000

分析:
可以看到随着线程数不断翻倍,CopyOnWriteArrayList的访问时间基本也是翻倍,但Collections.synchronizedMap的时间则是*4。在两个线程下Collections.synchronizedMap访问时间大概是CopyOnWriteArrayList的5倍,但在64线程的时候就变成了200倍+。所以如果在容器完全只读的情况下CopyOnWriteArrayList绝对是首选。但CopyOnWriteArrayList采用“写入时复制”策略,对容器的写操作将导致的容器中基本数组的复制,性能开销较大。所以但在有写操作的情况下,CopyOnWriteArrayList性能不佳,而且如果容器容量较大的话容易造成溢出。代码中如果CopyOnWriteArrayList cl按照ArrayList al的方法初始化就会造成溢出。


Collections.synchronizedMap、Collections.synchronizedSortedMap、ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListMap、TreeMap


Collections.synchronizedMap和Collections.synchronizedSortedMap实际上是对传入的Map对象作了个包装,每个方法都加上锁。
ConcurrentHashMap的实现使用了分段锁以及其他一些技术,多线程环境下读不用加锁,写也得到很大程度的优化。
ConcurrentSkipListMap的实现利用了跳表的数据结构,天生为了并发操作而生,同样多线程环境下可以无锁读取。
ConcurrentSkipListMap和TreeMap相同,查找是二分查找,遍历时需要按照Key的排序来返回结果。

ConcurrentHashMap(应用了分拆锁技术):
HashTable可以被认为是HashMap的同步版本,由于其在所有方法上加了sychonized修饰符,实现了多线程的安全访问,但是由于所有线程都申请同一把锁,所以效率很低。ConcurrentHashMap使用了锁分离技术。ConcurrentHashMap将数据分成一段一段的存储,然后给每一段数据分配一把锁,所以当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

分拆锁与分离锁:
如果一个锁守护着多个相互独立的状态变量,那么可以通过将锁分拆成多个锁,每个锁守护不同的状态变量,以提升可伸缩性。对于中等竞争程度的锁,通过分拆可以有效将大部分锁转化成非竞争的锁。
对于竞争激烈的锁,通过锁分拆可能会得到两个竞争激烈的锁,虽然可以对可伸缩性有小的改进,但并不能大幅地提高多个处理器在同一个系统中的并发性。这个时候可以使用锁分离技术。锁分离是对分拆锁的扩展,通过将一个锁扩展成一个包含了若干锁的集合,每个锁对应了一部分相互独立的对象。ConcurrentHashMap中默认使用了16个分离锁,每一个锁都守护 HashMap 的 1/16 。假设 Hash 值均匀分布,这将会把对于锁的请求减少到约为原来的 1/16 。这项技术使得 ConcurrentHashMap 能够支持 16 个的并发 Writer 。当多处理器系统的大负荷访问需要更好的并发性时,锁的数量还可以增加。
在很多应用中,类似于计数器,队列size之类的共享变量会被多个线程访问,这些变量需要用锁保护,形成热点域(hot field)这些热点域很可能会成为系统的瓶颈,尤其是在高吞吐量的情况下。这个时候可以考虑使用分离锁技术,将这些热点域分离,使用多个分离锁进行保护 。 ConcurrentHashMap 中为了避免这个问题,在每个分片的数组中维护一个独立的计数器,使用分离的锁保护,而不是维护一个全局计数。

ConcurrentHashMap还使用了自旋机制。自旋锁是采用让当前线程不停地的在循环体内执行实现的,当循环的条件被其他线程改变时 才能进入临界区。自旋适用于很短时间的等待,不适合长时间的等待,长时间等待会严重耗费CPU资源。
类似HashMap,Segment中内部数组的每一项都是一个单项链节点,它包含了key、hash、value等信息:
  1. static final class HashEntry<K,V> {
  2. final int hash;
  3. final K key;
  4. volatile V value;
  5. volatile HashEntry<K,V> next;
  6. HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
  7. this.hash = hash;
  8. this.key = key;
  9. this.value = value;
  10. this.next = next;
  11. }
  12. /**
  13. * Sets next field with volatile write semantics. (See above
  14. * about use of putOrderedObject.)
  15. */
  16. final void setNext(HashEntry<K,V> n) {
  17. UNSAFE.putOrderedObject(this, nextOffset, n);
  18. } }
注意,HashEntry只提供了setNext方法,所以所有节点的修改只能从头部开始。

由于HashEntry中value被申明为volatile,所以由java内存模型的happen before原则保证了数据的可见性,多线程操作也不会读取到过期值。所以ConcurrentHashMap的 读操作是不加锁的,效率高。

ConcurrentSkipListMap/ConcurrentSkipListSet(基于跳表实现,实现元素排序功能):

ConcurrentSkipListMap使用跳表数据结构实现,天生为了并发操作而生,同样多线程环境下可以无锁读取,参考ConcurrentSkipListMap实现。ConcurrentSkipListSet基于ConcurrentSkipListMap实现。

下面我们使用一些通用的标准对skiplis进行一下简单的评价:


1. 是否支持范围查找
因为是有序结构,所以能够很好的支持范围查找。


2. 集合是否能够随着数据的增长而自动扩展
可以,因为核心数据结构是链表,所以是可以很好的支持数据的不断增长的


3. 读写性能如何
因为从宏观上可以做到一次排除一半的数据,并且在写入时也没有进行其他额外的数据查找性工作,所以对于skiplist来说,其读写的时间复杂度都是O(log2n)


4. 是否面向磁盘结构
磁盘要求顺序写,顺序读,一次读写必须是一整块的数据。而对于skiplist来说,查询中每一次从高层跳跃到底层的操作,都会对应一次磁盘随机读,而skiplist的层数从宏观上来看一定是O(log2n)层。因此也就对应了O(log2n)次磁盘随机读。
因此这个数据结构不适合于磁盘结构。


5. 并行指标
终于来到这个指标了, skiplist的并行指标是非常好的,只要不是在同一个目标插入点插入数据,所有插入都可以并行进行,而就算在同一个插入点,插入本身也可以使用无锁自旋来提升写入效率。因此skiplist是个并行度非常高的数据结构。


6. 内存占用
与平衡二叉树的内存消耗基本一致。



单线程环境下,毫无疑问synchronizedHashMap 优于ConcurrentHashMap;synchronizedTreeMap 优于ConcurrentSkipListMap。
随着线程数增多,ConcurrentHashMap读写都优于synchronizedHashMap。
由于读不需要加锁,ConcurrentHashMap和ConcurrentSkipListMap读取时间都基本上不随线程数增加而增加,
而synchronizedHashMap和 synchronizedTreeMap, 因为读也要加锁,则随着线程数增加读取时间也增加。
特别是,8个线程下,ConcurrentSkipListMap的读写效率已经基本上接近synchronizedHashMap。如果线程数再增加,ConcurrentSkipListMap的性能应该会超过synchronizedHashMap。

ArrayBlockingQueue 带边界的阻塞式队列):

ArrayBlockingQueue是以数组为基础实现的带有边界的阻塞式队列,边界指的是队列容量是固定的,而且容量必须人为指定,无默认值,且无法扩容。阻塞指的是,如果队列满了,向队列中添加元素的操作会阻塞,直到队列中有空位产生,同样,如果队列为空,向队列请求元素的操作也会阻塞,直到队列中有元素可以取。

三个存入方法:add,offer,put

空间耗尽时offer()函数不会等待,直接返回false,add会抛出异常IllegalStateException("Queue full"),而put()则会wait

三个取出方法:take,poll

使用take()函数,如果队列中没有数据,则线程wait释放CPU,而poll()可以等待time参数规定的时间,到时仍取不到,返回null。在取出元素时,会将数组中的所有元素向前移。

LinkedBlockingDeque / LinkedBlockingQueue(链表队列(带锁),可设定是否带边界)

带边界,线程阻塞-安全的。可以指定容量,如果不指定,默认Integer.MAX_VALUE,这样的话,如果生产者的速度一旦大于消费者的速度,也许还没有等到队列满阻塞产生,系统内存就有可能已被消耗殆尽了。


ArrayBlockingQueue和LinkedBlockingQueue的区别:


1.    队列中锁的实现不同
       ArrayBlockingQueue实现的队列中的锁是没有分离的,存取元素用的是同一个锁;
       LinkedBlockingQueue实现的队列中的锁是分离的,即存入用putLock,取出用takeLock
    
2.    在生产或消费时操作不同
       ArrayBlockingQueue实现的队列中在生产和消费的时候,是直接将枚举对象插入或移除的;
       LinkedBlockingQueue实现的队列中在生产和消费的时候,需要把枚举对象转换为Node<E>进行插入或移除,会影响性能


3.    队列大小初始化方式不同
       ArrayBlockingQueue实现的队列中必须指定队列的大小;
       LinkedBlockingQueue实现的队列中可以不指定队列的大小,但是默认是Integer.MAX_VALUE
    
注意:
1.    在使用LinkedBlockingQueue时,若用默认大小且当生产速度大于消费速度时候,有可能会内存溢出
2.    在使用ArrayBlockingQueue和LinkedBlockingQueue分别对1000000个简单字符做入队操作时,
       LinkedBlockingQueue的消耗是ArrayBlockingQueue消耗的10倍左右,
       即LinkedBlockingQueue消耗在1500毫秒左右,而ArrayBlockingQueue只需150毫秒左右。


BlockingQueue不接收空值


ConcurrentLinkedDeque / ConcurrentLinkedQueue:(无边界的链表队列(CAS)

ConcurrentLinkedQueue的size方法会遍历集合,所以开销大。如果要判断是否有元素,使用isEmpty方法。


PriorityBlockingQueue:

类似于LinkedBlockQueue,但其所含对象的排序不是FIFO,而是依据对象的自然排序顺序或者是构造函数的Comparator决定的顺序.
SynchronousQueue:

特殊的BlockingQueue,对其的操作必须是放和取交替完成的.


DelayQueue——元素带有延迟的队列

LinkedTransferQueue——可将元素`transfer`进行w/o存储



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/821934
推荐阅读
相关标签
  

闽ICP备14008679号