Principle of copyonwritearraylist copy on write

CopyOnWriteArrayList It is a kind of copy on write ArrayList, And is a thread safe version . There are many data structures of similar design , Such as CopyOnWriteArraySet.

If you want to understand the specific principle analysis , Look at chapter two principle , Why copy ？

expand ：CopyOnWriteArraySet
Thread safe set, Bottom use CopyOnWriteArrayList
add Called when addIfAbsent To guarantee There is no repetition of elements
And in general set Different , image hashset、treeset The bottom layer is the corresponding call map To operate

1. brief introduction

CopyOnWriteArrayList As the name suggests, copy list on write , Avoid direct read-write mutex locking , Poor performance .

read ： Direct read without lock .

Write ： Copy a , To operate . Multiple write operations Lock Mutual exclusion ensures data security .

Advantages and disadvantages ：

advantage ： Reduce read lock , Improve code performance , At the same time, ensure thread safety .

shortcoming ：

1. When the internal data is large , Copying requires a lot of memory overhead , May lead to OOM Happen .
2. Only the final consistency of data can be guaranteed .

The final consistency is discussed in three cases ：

public boolean add(E e) {
    synchronized(this.lock) {
        Object[] es = this.getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        // 1️⃣
        es[len] = e;
        // 2️⃣
        this.setArray(es);
        // 3️⃣
        return true;
    }
}

• 1️⃣ Data not modified

  At this time, read the old data

• 2️⃣ Modifying data , But the reference is not pointed to the new array

  At this time, the old data will also be read .

• 3️⃣ Modifying data , Point the reference to the new data

  At this time, the latest data can be read .

2. principle

First ask a question

1. Why copy on write , Can't you modify the original array directly ？

   After all, they are locked when writing , There are no multiple threads modifying at the same time , It also saves the memory cost of copying and modifying data 、 Consistency problems when pointing to new arrays .

   I have thought about this problem for a long time . What is the purpose of a write time copy , Why do this ？

To solve this problem , The key is to understand volatile Keyword

volatile There are two things about it

1. Thread visibility
2. Avoid reordering instructions

Here is a brief introduction to visibility , Multiple CPU There will be internal cache to improve the reading efficiency , First read from memory to cache , without volatile Keyword , Other threads have modified the value of this property , Brush back memory , But the current thread is not aware of the changes , Still reading old cache values , The problem of inconsistent data . So add volatile Change can be felt . At the same time, the key point is that only Citation modification Will be perceived , Such as object modification 、 Array object reference modification , Variable modification, etc .

// volatile Embellished 
private transient volatile Object[] array;

As mentioned earlier, this is an array reference type , So if you simply modify elements in the original array, it cannot be perceived by other threads , That's why it's used here Copy To modify the reference point in time “ notice ” Other thread data changes .

That's why a write - time copy method is used , Data security .

3. And ReadWriteLock Compare

Read-write lock ： Can't read while writing , You can't write while reading , So and CopyOnWrite It's different

Read-write lock	read	Write
read	√	×
Write	×	×

4. summary

CopyOnWriteArrayList Very clever use of volatile Keywords to ensure thread read and write security , Although it avoids the low performance scenario of locking while reading and writing , But it also takes up extra memory , Data can not guarantee strong consistency and other shortcomings , You need to use... According to the scene , Suitable for reading more and writing less .