Java concurrent programming: Implementation principle of concurrent container CopyOnWriteArrayList

　Copy-On-Write, referred to as COW, is an optimization strategy used in programming. The basic idea is that everyone is sharing the same content from the beginning. When someone wants to modify the content, they will actually copy the content to form a new content and then modify it. This is a kind of delayed laziness. Strategy. Starting from JDK1.5, the Java concurrency package provides two concurrent containers implemented using the CopyOnWrite mechanism, which are CopyOnWriteArrayList and CopyOnWriteArraySet. The CopyOnWrite container is very useful and can be used in many concurrent scenarios.

What is a CopyOnWrite container?

A CopyOnWrite container is a container that is copied when writing. The popular understanding is that when we add elements to a container, we do not add them directly to the current container, but first copy the current container to create a new container, and then add elements to the new container. After adding the elements, Then point the reference of the original container to the new container. The advantage of this is that we can perform concurrent reads on the CopyOnWrite container without locking, because the current container will not add any elements. Therefore, the CopyOnWrite container is also an idea of ​​separation of reading and writing, and reading and writing are different containers.

The implementation principle of CopyOnWriteArrayList

Before using CopyOnWriteArrayList, we first read its source code to understand how it is implemented. The following code is the implementation of the add method in CopyOnWriteArrayList (adding elements to CopyOnWriteArrayList). You can find that you need to lock when adding, otherwise N copies will be copied when writing with multiple threads.

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 <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(); } }

There is no need to lock when reading. If multiple threads are adding data to CopyOnWriteArrayList when reading, the reading will still read the old data because there will be no locking when writing. Live the old CopyOnWriteArrayList.

1 2 3

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

There is no CopyOnWriteMap provided in JDK. We can refer to CopyOnWriteArrayList to implement one. The basic code is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 twenty one twenty two twenty three twenty four 25 26 27 28 29 30 31 32 33

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;         } } }

The implementation is very simple. As long as we understand the CopyOnWrite mechanism, we can implement various CopyOnWrite containers and use them in different application scenarios.

Application scenarios of CopyOnWrite

The CopyOnWrite concurrent container is used in concurrent scenarios with more reading and less writing. For example, whitelist, blacklist, and product category access and update scenarios. If we have a search website, the user enters keywords to search for content in the search box of this website, but some keywords are not allowed to be searched. These keywords that cannot be searched will be placed in a blacklist, which is updated every night. When the user searches, it will check whether the current keyword is in the blacklist. If it is, it will prompt that the search cannot be performed. The implementation code is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 twenty one twenty two twenty three twenty four 25 26 27 28 29 30 31 32 33 34 35

package com.ifeve.book; import java.util.Map; import com.ifeve.book.forkjoin.CopyOnWriteMap; /** * Blacklist Service * * @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); } /** * Add blacklist in batches * * @param ids       */ public static void addBlackList(Map<String,Boolean> ids) {         blackListMap.putAll(ids); } }

The code is very simple, but there are two things you need to pay attention to when using CopyOnWriteMap:

1. Reduce expansion overhead. Initialize the size of CopyOnWriteMap according to actual needs to avoid the overhead of CopyOnWriteMap expansion during writing.

　2. Use batch addition. Because each time you add, the container will be copied every time, so reducing the number of additions can reduce the number of times the container is copied. For example, use the addBlackList method in the above code.

Disadvantages of CopyOnWrite

The CopyOnWrite container has many advantages, but there are also two problems, namely memory usage and data consistency. So you need to pay attention to it when developing.

Memory usage problem. Because of the copy-on-write mechanism of CopyOnWrite, when a write operation is performed, two objects will reside in the memory at the same time, the old object and the newly written object (note: during copying, only the references in the container are copied. Only when writing, new objects will be created and added to the new container, while the objects in the old container are still in use, so there are two copies of object memory). If the memory occupied by these objects is relatively large, for example, about 200M, then writing 100M of data into it will occupy 300M of memory, which may cause frequent Yong GC and Full GC at this time. Previously, we used a service in our system that used the CopyOnWrite mechanism to update large objects every night, resulting in a Full GC of 15 seconds every night, and the application response time also became longer.

In view of the memory usage problem, you can reduce the memory consumption of large objects by compressing the elements in the container. For example, if the elements are all decimal numbers, you can consider compressing them into hexadecimal or hexadecimal numbers. Base 64. Or don't use the CopyOnWrite container, but use other concurrent containers, such as ConcurrentHashMap.

Data consistency issue. The CopyOnWrite container can only guarantee the final consistency of the data, but cannot guarantee the real-time consistency of the data. So if you want the written data to be read immediately, please do not use the CopyOnWrite container.

Related articles:

Java Concurrent Programming: CountDownLatch, CyclicBarrier and Semaphore

[JAVA Concurrent Programming Practice] Lock Sequence Deadlock

Related videos:

Java multi-threading and concurrency library advanced application video tutorial

The above is the detailed content of Java concurrent programming: Implementation principle of concurrent container CopyOnWriteArrayList. For more information, please follow other related articles on the PHP Chinese website!