CopyOnWriteArrayList源码学习
1.Copy-On-Write 策略
Copy-On-Write 简称COW,意思是写入时复制;大家共享同一个变量,多个人读取的时候都是那一个变量;当有一个人要修改变量,则先复制一份,修改变量的副本,这个过程中不影响其他人读取原来的变量。 这种优化策略在Linux系统、Redis、文件系统中都有应用,这里我们讲解这种思想在Java中的应用。 CopyOnWrite容器,当向一个共享容器进行写入或修改操作时,不直接操作原有容器,先拷贝一份新容器,在新容器中进行写入或修改操作,最后将共享变量的地址指向新容器。这个过程中写操作不影响并发读,读和写是分离的。 Java中的CopyOnWriteArrayList和CopyOnWriteArraySet是对这种思想的实践。
2. CopyOnWriteArrayList
在Java中要保证一个List线程安全,要么使用Vector要么使用Collections.synchronizedList方法生成一个线程安全的包装类SynchronizedList。这两种方式都是通过加锁的方式实现了线程安全,区别在于Vector是在声明方法的时候加synchronized,而SynchronizedList是在包装方法内部添加synchronized实现。 这两种方式有个共同的缺点,增删改查方法都加锁了,在读多写少的情况下很影响性能。
特点:
线程安全,无须手动加锁;
通过锁+数组拷贝+violate保证了线程安全;
2.1 构成
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
//....
}
CopyOnWriteArrayList实现了List接口,内部数据存储和ArrayList同样使用数组实现,这里需要注意的是:
(1)这里使用ReentrantLock作为独占锁,相比于synchronized,ReentrantLock更灵活,但需要手动释放锁。
(2)array 使用volatile修饰,保证了可见性,有最终一致性,但不是实时一致的。
2.2 添加元素
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();
}
}
写入操作的第一步是加锁,这里可以学习下ReentrantLock的使用,记得在finally语句中释放锁。剩下的就是拷贝数组,在新数组上添加元素,最后将array指向新数组。
这里有个点需要注意下:这里已经加锁了,为什么不直接在原数组上修改?
一是修改原数组会导致读取数据异常,二是violate修饰的是array变量,修改原数组虽然数组变了,但array指向的是同一块地址,无法触发其可见性。所以必须要复制新数组来实现元素新增。
在指定位置插入元素的源码如下:
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)// 移动元素数为0说明是在末尾插入元素。
newElements = Arrays.copyOf(elements, len + 1);
else {
// 分两次插入元素。
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
}
这里总结一下:
(1)加锁保证了同一时刻,只能有一个线程进行修改操作。
(2)使用数组拷贝生成新的数组,在新数组上进行修改操作,不影响并发读取数据的一致性。
(3)使用violate修饰array,指向新数组时,其他线程可以立即读到最新值。
2.3 删除元素
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;// 从后向前移动元素数量
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
// 先复制前部再复制后部
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
指定索引删除元素的过程和按索引添加元素的过程类似,都是加锁判断位置进行拷贝最后解锁。
修改元素的过程同样也是加锁后对复制的新数组进行修改,最后更改数组引用,这里不贴代码了,直接看迭代的代码。
2.4 迭代过程
由于CopyOnWriteArrayList修改的都是老数组,所以对原数组在结构上时没有修改的,在迭代过程中修改元素不会抛ConcurrentModificationException异常。但需要注意的时一旦迭代开始,迭代器持有的数组时不变的,此时修改数组不会影响迭代的顺序。
static final class COWIterator<E> implements ListIterator<E> {
// 迭代器持有的数组快照,
private final Object[] snapshot;
// 迭代的游标
private int cursor;
// 创建迭代器时就决定了快照的版本
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
// 支持向后迭代
public boolean hasNext() {
return cursor < snapshot.length;
}
// 支持向前迭代
public boolean hasPrevious() {
return cursor > 0;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
// 不支持修改操作
public void remove() {
throw new UnsupportedOperationException();
}
public void set(E e) {
throw new UnsupportedOperationException();
}
public void add(E e) {
throw new UnsupportedOperationException();
}
// 遍历操作同样只是针对快照操作
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
Object[] elements = snapshot;
final int size = elements.length;
for (int i = cursor; i < size; i++) {
@SuppressWarnings("unchecked") E e = (E) elements[i];
action.accept(e);
}
cursor = size;
}
}
2.5 小结
这里总结一下CopyOnWriteArrayList的特点,CopyOnWriteArrayList读写分离,适合读多写少的场景;使用ReentrantLock作为独占锁,保证增删改操作的互斥性。当然缺点也很明显,首先是占用内存多,每次修改都会复制新数组;其次正因为读写分离了,所以写操作不具有实时一致性,只有最终一致性,如果对读取数据有实时一致性要求则不要使用该容器;同样迭代过程读到的是快照数组中的值,同样不具备实时性。
3.CopyOnWriteArraySet
CopyOnWriteArraySet内部使用的是CopyOnWriteArrayList实现。
引用:
聊聊并发-Java中的Copy-On-Write容器,by 方腾飞
CopyOnWriteArrayList你都不知道,怎么拿offer?,by Java3y