CopyOnWriteArrayList

Posted on |

本篇主要介绍juc内部针对数组提供的并发容器CopyOnWriteArrayList，主要的思想是针对增删改等修改操作都将原数组拷贝一份新数组，然后做完修改操作后，通过原子的方式写入到原数组的引用，通知到其他线程。

CopyOnWriteArrayList实现

设计一个线程安全的容器主要针对改（增删改）和查操作，CopyOnWriteArrayList对put操作通过RetrantLock加锁，将数组定义为volatile类型，再通过加锁完成新数组的生成之后，将新数组赋值给volatile数组，通知到其他线程。这里的lock同样我们可以用synchronized关键字或者cas来实现。put操作源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return {@code true} (as specified by {@link Collection#add})
    */
   public boolean add(E e) {
       final ReentrantLock lock = this.lock;
       lock.lock();
       try {
           Object[] elements = getArray();
           int len = elements.length;
           Object[] newElements = Arrays.copyOf(elements, len + 1);
           newElements[len] = e;
           setArray(newElements);
           return true;
       } finally {
           lock.unlock();
       }
   }

Iterating过程中不允许修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.souche.study.CopyOnWriteArrayList;

import java.util.Iterator;

/**
 * @autor yeqiaozhu.
 * @date 2019-07-01
 */
public class CopyOnWriteArrayListTest {

    public static void main(String[] args) {
        Integer[] integers={1,2,3,4,5};
        DefinedCopyOnWirteArrayList list=new DefinedCopyOnWirteArrayList(integers);

        Iterator iterator=list.iterator();
        while (iterator.hasNext()){
            //不允许操作，抛出异常
            iterator.remove();
        }
    }
}
1
2
3
4
//迭代器浅拷贝，不允许修改，只能查询而且是临时快照
default void remove() {
  	throw new UnsupportedOperationException("remove");
}

通过CAS改写CopyOnWriteArrayList

继承CopyOnWriteArrayList进行方法的重写，重新实现的add方法供参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package com.souche.study.CopyOnWriteArrayList;

import java.util.Arrays;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.atomic.AtomicReference;

/**
 * 自定义CopyOnWriteArrayList的方法
 * @autor yeqiaozhu.
 * @date 2019-07-01
 */
public class DefinedCopyOnWirteArrayList extends CopyOnWriteArrayList<Integer> {

    private AtomicReference<Integer[]> atomicIntegers;

    public DefinedCopyOnWirteArrayList(Integer[] integers) {
        this.atomicIntegers = new AtomicReference<>(integers);
    }

    public Integer get(Integer index){
        if(index >atomicIntegers.get().length-1){
            throw new ArrayIndexOutOfBoundsException("数组越界");
        }
        return atomicIntegers.get()[index];
    }
    @Override
    public boolean add(Integer insertData){
        //step 1:拷贝一份数组
        Integer[] integers=atomicIntegers.get();
        int length=integers.length;
        Integer[] newIntegers=Arrays.copyOf(integers,length+1);
        //step 2:将新值添加到新的数组中
        newIntegers[length]=insertData;
        //step 3:采用cas替换引用
        return this.atomicIntegers.compareAndSet(integers,newIntegers);
    }

}

CopyOnWriteArrayList设计 vs RetrantWriteReadLock

对比一下CopyOnWriteArrayList设计和RetrantWriteReadLock的实现。

  • CopyOnWriteArrayList设计读不加锁，写加锁。RetrantWriteReadLock读和写都加锁。
  • CopyOnWriteArrayList设计针对读多写少场景表现优。RetrantWriteReadLock虽然针对读锁做了共享，读多写少依旧阻塞。

总结

感觉CopyOnWriteArrayList的设计还是蛮巧妙的，之前在了解读写锁的这种设计时还是蛮质疑这个设计的实际意义的。类比innodb的MDL表锁（如果一个写操作（修改表结构）获取到写锁前面有一个长事务获取读锁，那么所有的ddl操作（读锁）都有被阻塞），inndb因此设计了更小粒度的行锁。行锁同时设计了写锁，但是取消了读锁，用MVCC多版本并发控制取代，类比CopyOnWriteArrayList保留了写锁，通过线程通信的方式取消了读锁。