CopyOnWrite ideas

The idea of CopyOnWrite (COW for short) is an optimization strategy in the field of computer programming. The idea is that if multiple Callers request the same resource (such as memory or data storage on disk) at the same time, they will collectively obtain the same pointer to the same resource until one of the Callers views changes the content of the resource. The system actually copies a private copy to the caller, while the original resource seen by other callers remains the same. The process is transparently transparent to other callers. The main advantage of this approach is that if the caller does not modify the resource, no private copy is created, so multiple callers can share the same resource only when reading operations.

CopyOnWriteArrayList implementation principle

Before using CopyOnWriteArrayList, let’s read the source code to see how it is implemented. The following code is an implementation of the add method to CopyOnWriteArrayList (adding elements to CopyOnWriteArrayList). It can be found that the lock is needed to add elements to CopyOnWriteArrayList, otherwise multi-threaded writing will Copy N copies.

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (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(); }}Copy the code

If multiple threads are adding data to CopyOnWriteArrayList while reading, the old data will still be read because the old CopyOnWriteArrayList will not be locked while writing.

public E get(int index) {
    return get(getArray(), index);
}
Copy the code

The JDK does not provide CopyOnWriteMap, we can refer to CopyOnWriteArrayList to implement one, the basic code is as follows:

import java.util.Collection; import java.util.Map; import java.util.Set; public class CopyOnWriteMap<K, V> implements Map<K, V>, Cloneable { private volatile Map<K, V> internalMap; public CopyOnWriteMap() { internalMap = new HashMap<K, V>(); } public V put(K key, V value) { synchronized (this) { Map<K, V> newMap = new HashMap<K, V>(internalMap); V val = newMap.put(key, value); internalMap = newMap; return val; } } public V get(Object key) { return internalMap.get(key); } public void putAll(Map<? extends K, ? extends V> newData) { synchronized (this) { Map<K, V> newMap = new HashMap<K, V>(internalMap); newMap.putAll(newData); internalMap = newMap; }}}Copy the code

The implementation is very simple, as long as we understand the CopyOnWrite mechanism, we can implement a variety of CopyOnWrite containers, and use in different application scenarios.

A few points

  • Implement the List interface
  • ReentrantLock = new ReentrantLock();
  • The underlying array is declared as volatile TRANSIENT
  • Read/write separation, copy a new array while writing, and assign the new array to the array after insertion, modification, or removal

“Note:”

Volatile: Variable modifier, used only to modify variables. A volatile variable forces the value of the member variable to be re-read from shared memory each time it is accessed by a thread. Moreover, when a member variable changes, threads are forced to write the changed value back to shared memory. This way, at any time, two different threads will always see the same value of a member variable.

Add and delete

1) increase

public boolean add(E e) { final ReentrantLock lock = this.lock; // Get lock lock.lock(); try { Object[] elements = getArray(); int len = elements.length; [] newElements = array.copyof (Elements, len + 1); NewElements [len] = e; // Point the new array to the original reference setArray(newElements); return true; } finally {// unlock lock.unlock(); } } 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) 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(); }}Copy the code

2) delete

public E remove(int index) { final ReentrantLock lock = this.lock; // Get lock lock.lock(); try { Object[] elements = getArray(); int len = elements.length; E oldValue = get(elements, index); int numMoved = len - index - 1; SetArray (array.copyof (Elements, Len-1)); if (numMoved == 0) Else {// Create a new array Object[] newElements = new Object[len-1]; Arraycopy (elements, 0, newElements, 0, index); // Move index+1 to the last element one row forward. System.arraycopy(elements, index + 1, newElements, index, numMoved); setArray(newElements); } return oldValue; } finally { lock.unlock(); }}Copy the code

3) change

public E set(int index, E element) { final ReentrantLock lock = this.lock; // Get lock lock.lock(); try { Object[] elements = getArray(); E oldValue = get(elements, index); if (oldValue ! = element) { int len = elements.length; [] newElements = array.copyof (elements, len); NewElements [index] = element; // Point the new array to the original reference setArray(newElements); } else { // Not quite a no-op; ensures volatile write semantics setArray(elements); } return oldValue; } finally {// unlock lock.unlock(); }}Copy the code

4) check

Public E get(int index) {return getArray(), index); } private E get(Object[] a, int index) {return (E) a[index]; }Copy the code

Application scenario of CopyOnWrite

The CopyOnWrite concurrent container is used in concurrent scenarios where more reads and less writes are required. For example, whitelist, blacklist, commodity access and update scenarios, let’s say we have a search site, and the user enters keywords in the search box of the site to search for content, but certain keywords are not allowed to be searched. These unsearchable keywords are put on a blacklist, which is updated every night. When a user searches, the system checks whether the current keyword is in the blacklist. If so, the system prompts that the keyword cannot be searched. The implementation code is as follows:

import java.util.Map; import com.ifeve.book.forkjoin.CopyOnWriteMap; @author fangtengfei ** / public class BlackListServiceImpl {private static CopyOnWriteMap<String, Boolean> blackListMap = new CopyOnWriteMap<String, Boolean>( 1000); public static boolean isBlackList(String id) { return blackListMap.get(id) == null ? false : true; } public static void addBlackList(String id) { blackListMap.put(id, Boolean.TRUE); } /** * @param ids */ public static void addBlackList(Map<String,Boolean> ids) {blackListmap.putall (ids); }}Copy the code

The code is simple, but there are two things to be aware of when using CopyOnWriteMap:

1. Reduce capacity expansion costs. Initialize the size of CopyOnWriteMap as required to avoid the cost of CopyOnWriteMap expansion.

2. Use batch add. Because the container is copied every time you add, reducing the number of times you add reduces the number of times the container is copied. For example, use the addBlackList method in the code above.

The disadvantage of CopyOnWrite

The CopyOnWrite container has many advantages, but it also has two problems: memory footprint and data consistency. So you need to pay attention to it during development.

Memory usage problem. Because CopyOnWrite write replication mechanism, so at the time of writing, in the memory will be stationed at the same time two objects of memory, the old and new writing object (note: just copy the reference in the container when copy, just at the time of writing will create a new object is added to the new container, the old container object is still in use, So there are two pieces of object memory. If these objects take up a lot of memory, say 200 MB, then writing another 100 MB of data will take up 300 MB of memory, which is likely to result in frequent Yong and Full GC. We used a service on our system that had 15 seconds of Full GC per night due to updating large objects using CopyOnWrite every night, resulting in longer application response times.

You can reduce the memory consumption of large objects by compressing the elements in the container. For example, if the elements are all base 10 numbers, consider compressing them to base 36 or 64. Or instead of using the CopyOnWrite container, use another concurrent container, such as ConcurrentHashMap.

Data consistency issues. The CopyOnWrite container only guarantees final data consistency, not real-time data consistency. So if you want to write data that is immediately readable, don’t use the CopyOnWrite container.

Why is CopyOnWriteArrayList concurrency safe and better than Vector

I know that Vector adds synchronized to add, delete, modify, and check methods to ensure synchronization, but the performance of each method will be greatly reduced when it is executed. CopyOnWriteArrayList only locks the add, delete, and change methods, but does not lock the read, so the read performance is better than Vector. CopyOnWriteArrayList supports concurrency with more reads and less writes.

The last

Thank you for reading the last, if the article is not enough, welcome to support in the comment section, give your opinion. If you find my article helpful, give me a thumbs up.

Welcome to pay attention to my public account: programmer Maidong, every day will share Java related technical articles or industry information. Welcome to follow and forward this article.