preface

This chapter learns about the two HikariCP container classes ConcurrentBag and FastList. Take a look at the advantages of ConcurrentBag over traditional blocking queues, compare FastList with the JDK’s ArrayList, and think about why HikariCP needs these two special container classes.

A, IConcurrentBagEntry

IConcurrentBagEntry is the element in the ConcurrentBag container. It has four states:

  • STATE_NOT_IN_USE: not used. It can be borrowed
  • STATE_IN_USE: the state is in use.
  • STATE_REMOVED: removed. The CAS changes to this state only when the remove method is called. After the modification is successful, the CAS is removed from the container.
  • STATE_RESERVED: indicates that it is reserved and cannot be used. It is often reserved before removal.
public interface IConcurrentBagEntry {
  int STATE_NOT_IN_USE = 0;
  int STATE_IN_USE = 1;
  int STATE_REMOVED = -1;
  int STATE_RESERVED = -2;
  boolean compareAndSet(int expectState, int newState);
  void setState(int newState);
  int getState();
}
Copy the code

ConcurrentBag constructor and member variables

Member variables

public class ConcurrentBag<T extends IConcurrentBagEntry> implements AutoCloseable {
   private final CopyOnWriteArrayList<T> sharedList;
   private final boolean weakThreadLocals;
   private final ThreadLocal<List<Object>> threadList;
   private final IBagStateListener listener;
   private final AtomicInteger waiters;
   private volatile boolean closed;
   private final SynchronousQueue<T> handoffQueue;
}
Copy the code

  • CopyOnWriteArrayList sharedList: Saves all elements in the container. Use CopyOnWriteArrayList to lock the write operation and copy the underlying data. It is suitable for the scenario of reading too much and writing too little. The HikariCP authors recommend that the maximum number of connections in the connection pool be consistent with the minimum number of connections, which may also be one reason. If the connection pool is set to elastic capacity, in case of burst traffic, sharedList expansion causes CopyOnWriteArrayList to lock and make array copy. After traffic, sharedList shrinkage can also result in locking and array copying.

  • Boolean weakThreadLocals: Specifies whether to use WeakReference to save elements in threadList. The default value is no.

  • ThreadLocal threadList: Elements held by the current thread. You can think of sharedList as containing all elements of threadList.

  • IBagStateListener Listener: Notifies the external to add an element to ConcurrentBag.

  • AtomicInteger Waiters: The number of threads currently waiting to get elements.

  • Boolean closed: indicates whether ConcurrentBag is closed. Default is false. ConcurrentBag cannot add new elements when closed.

  • SynchronousQueue handoffQueue: Indicates the handoffQueue. The two main methods used in SynchronousQueue are offer (which returns false if no thread has fetched an element from the offer) and poll(timeout,unit) (which returns null if no element has been fetched for a specified time).

A constructor

Public ConcurrentBag(final IBagStateListener listener) {// IBagStateListener must be passed this.listener = listener; // Whether threadList uses WeakReference to save elements this.weakThreadlocals = useWeakThreadLocals(); SynchronousQueue<>(true); // SynchronousQueue, fair=true this.handoffQueue = new SynchronousQueue<>(true); This. waiters = new AtomicInteger(); This.sharedlist = new CopyOnWriteArrayList<>(); this.sharedList = new CopyOnWriteArrayList<>(); If (weakThreadLocals) {// If WeakReference is used, ArrayList this.threadList = threadlocal.withinitial (() -> new ArrayList<>(16)); } else {// Otherwise use FastList, This default. ThreadList = ThreadLocal. WithInitial (() - > new FastList < > (IConcurrentBagEntry. Class, 16)); {try {} private Boolean useWeakThreadLocals () / / if the system variables (-d parameters or environmental variables) have to configure com. Zaxxer. Hikari. UseWeakReferences, Walking System variable configuration / / the annotation in the document, because generally is not recommended to modify the if (System. GetProperty (" com. Zaxxer. Hikari. UseWeakReferences ")! = null) { of WeakReference behavior return Boolean.getBoolean("com.zaxxer.hikari.useWeakReferences"); } // If the current class loader is inconsistent with the system class loader, return true getClass().getClassLoader()! = ClassLoader.getSystemClassLoader(); } catch (SecurityException se) { return true; }}}Copy the code

Add new elements

Add a new object to the bag for others to borrow. Add an element to bag for the borrow method to borrow.

private volatile boolean closed; private final CopyOnWriteArrayList<T> sharedList; private final AtomicInteger waiters; private final SynchronousQueue<T> handoffQueue; Public void add(final T bagEntry) {// If container is closed, IllegalStateException if (closed) {throw new IllegalStateException("ConcurrentBag has been closed, ignoring add()"); } // add sharedList.add(bagEntry); // Keep trying to put an element into the interface queue while (waiters.get() > 0 && bagentry.getState () == STATE_NOT_IN_USE &&! Handoffqueue.offer (bagEntry)) {// The current Thread abandons CPU execution and returns to the ready state thread.yield (); }}Copy the code

Get () > 0 && bagentry.getState () == STATE_NOT_IN_USE &&! Handoffqueue.offer (bagEntry) this loop condition.

  • waiters.get() > 0: There needs to be a thread waiting for an element to loop.
  • bagEntry.getState() == STATE_NOT_IN_USEBecause the element is already in shareList, it may be changed by other threads, and it is necessary to determine whether the current element is still unused.
  • ! handoffQueue.offer(bagEntry): Attempts to join the transition queue, and continues the loop if it fails.

4. Borrow elements

The method will borrow a BagEntry from the bag, blocking for the specified timeout if none are available. Borrowing elements from bag blocks for a specified period if there are no available elements.

private final CopyOnWriteArrayList<T> sharedList; private final ThreadLocal<List<Object>> threadList; private final AtomicInteger waiters; private final SynchronousQueue<T> handoffQueue; public T borrow(long timeout, final TimeUnit timeUnit) throws InterruptedException { // 1. Get final List<Object> List = threadlist.get (); for (int i = list.size() - 1; i >= 0; I --) {// Remove final Object entry from ThreadLocal = list.remove(I); final T bagEntry = weakThreadLocals ? ((WeakReference<T>) entry).get() : (T) entry; // CAS changes the state of the element to in use. // CAS changes the state of the element to in use. = null && bagEntry.compareAndSet(STATE_NOT_IN_USE, STATE_IN_USE)) { return bagEntry; Final int waiting = waiters. IncrementAndGet (); Try {// 2. Get for (T bagEntry: If (bagEntry.compareAndSet(STATE_NOT_IN_USE, STATE_IN_USE)) {// If (bagEntry.compareAndSet(STATE_NOT_IN_USE, STATE_IN_USE)) { If (waiting > 1) {listener.addbagItem (waiting-1); } return bagEntry; }} // Add element listener.addbagItem (waiting); // Timeout = timeUnit.tonanos (timeout); do { final long start = currentTime(); // 3. Final T bagEntry = handoffQueue. Poll (timeout, NANOSECONDS); / / CAS modifying elements state for the use of the if (bagEntry = = null | | bagEntry.com pareAndSet (STATE_NOT_IN_USE STATE_IN_USE)) {return bagEntry; } // timeout -= timeout -= elapsedNanos(start); } while (timeout > 10000); return null; Great waiters. DecrementAndGet (); }}Copy the code

Is it possible to omit the call after stealing elements from the shared list shareListlistener.addBagItem(waiting - 1)?

No, this will cause other threads to fail to get the element. ThreadA fails to fetch elements from shareList, notifies the Listener to add elements to ConcurrentBag, but the external element is stolen as soon as it is put into shareList, causing ThreadA to fail to fetch elements from the transition queue. The result is a timeout.

Requite return elements

This method will return a borrowed object to the bag. Objects that are borrowed from the bag but never “requited” will The result in a memory leak. requite method returns the elements borrowed from bag. If lent elements are not returned, memory leaks will result.

public void requite(final T bagEntry) { // 1. SetState (STATE_NOT_IN_USE); BagEntry. setState(STATE_NOT_IN_USE); For (int I = 0; waiters.get() > 0; If (bagentry.getState ()!) {if (bagentry.getState ()! = STATE_NOT_IN_USE || handoffQueue.offer(bagEntry)) { return; Else if ((I & 0xff) == 0xFF) {parkNanos(microseconds.tonanos (10)); } else {thread.yield (); ThreadLocal final List<Object> threadLocalList = threadList.get(); If (threadLocallist. size() < 50) {// A maximum of 50 threadlocallist. add(weakThreadLocals? new WeakReference<>(bagEntry) : bagEntry); }}Copy the code

Reserve and unreserve Cancel reservation

To preserve the state, you can first make the element state undebatable, then do some logical operations, and finally call the remove method to remove it.

Public Boolean Reserve (final T bagEntry) {return bagEntry.compareAndSet(STATE_NOT_IN_USE, STATE_RESERVED); } public void unreserve(final T bagEntry) {// Cas changes the state to unused if (bagEntry.compareAndSet(STATE_RESERVED, STATE_NOT_IN_USE)) {// If you have a thread waiting for an element, try putting it on the interface queue while (waiters.get() > 0 &&! handoffQueue.offer(bagEntry)) { Thread.yield(); } } else { LOGGER.warn("Attempt to relinquish an object to the bag that was not reserved: {}", bagEntry); }}Copy the code

Remove the element

Remove a value from the bag. This method should only be called with objects obtained by borrow(long, TimeUnit) or reserve(T).

Removes elements from bag. It can only be called after invoking BORROW or Reserve.

Public Boolean remove(final T bagEntry) {// The cas state can only be STATE_IN_USE or STATE_RESERVED if (! bagEntry.compareAndSet(STATE_IN_USE, STATE_REMOVED) && ! bagEntry.compareAndSet(STATE_RESERVED, STATE_REMOVED) && ! closed) { LOGGER.warn("Attempt to remove an object from the bag that was not borrowed or reserved: {}", bagEntry); return false; Final Boolean removed = sharedList.remove(bagEntry); if (! removed && ! closed) { LOGGER.warn("Attempt to remove an object from the bag that does not exist: {}", bagEntry); } // Remove threadList.get().remove(bagEntry) from ThreadLocal; return removed; }Copy the code

Eight, FastList

Member variables and constructors

Public final class <T> implements List<T>, RandomAccess, Serializable {// Private final class <? > clazz; // array private T[] elementData; Private int size; public FastList(Class<? > clazz, int capacity) { this.elementData = (T[]) Array.newInstance(clazz, capacity); this.clazz = clazz; }}Copy the code

The add method

First take a look at the Add method of ArrayList.

Public Boolean add(E E) {// Ensure array size ensureCapacityInternal(size + 1); ElementData [size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }Copy the code

Take a look at FastList’s Add method.

ElementData [size++] = element; public Boolean add(T element) {if (size < elementdata.length) {elementData[size++] = element;  } else {final int oldCapacity = elementData.length; final int newCapacity = oldCapacity << 1; final T[] newElementData = (T[]) Array.newInstance(clazz, newCapacity); System.arraycopy(elementData, 0, newElementData, 0, oldCapacity); newElementData[size++] = element; elementData = newElementData; } return true; }Copy the code

FastList and ArrayList add methods difference:

  • ArrayList has more layers of methods than FastList and comes in and out of the stack more frequently.
  • Because ArrayList is constructed with no arguments, the elementData array variable is an empty array and needs to be initialized on the first add, there are a few more logical judgments (for Hikari, both FastList and ArrayList are created with initial capacity passed in, and these are useless).
  • FastList eliminates modCount increment compared to ArrayList.
  • The calculation logic of ArrayList expansion is relatively complex and many boundary conditions are considered. Copy Arrays using the array. copyOf method, which also calls System. Arraycopy at the bottom, but the call stack is very deep.

The remove method

The remove method of ArrayList.

Public Boolean remove(Object o) {if (o == null) {// If (o == null) {for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; }} else {// If the input parameter is not empty, loop through equals method to check whether it is equal for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; Int numMoved = size-index - 1; If (numMoved > 0) system. arrayCopy (elementData, index+1, elementData, index, numMoved);  // Empty elementData[--size] = null; }Copy the code

FastList remove method.

Public Boolean remove(Object element) {// For (int index = size - 1; index >= 0; If (element == elementData[index]) {final int numMoved = size-index - 1; if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } elementData[--size] = null; return true; } } return false; }Copy the code

The FastList and ArrayList remove methods are different:

  • The traversal order is different. ArrayList goes front to back, FastList goes back to front.

Why do I traverse backwards and forwards?

First of all, we want the last element to match, because if the last element directly matches numMoved it’s 0, so we don’t have to do the array copy shift. The author must write this because the last element is removed more often with HikariCP.

Why is it that HikariCP tends to be the last element removed first?

Notice that when the Borrow method tries to get free entries from threadList, it starts removing from the last element of the FastList.

Why start with the last one?

Note that the Requite return join method is the only entry into a threadList element, and the elements it puts in are unused. If the BORROW method is paired with trying to fetch from the last element, the CAS has a very high success rate in modifying the state because the previously returned element may have been stolen from the shareList by another thread!

  • Elements are compared differently. ArrayList determines whether the input parameter is empty using == or equals, respectively; FastList only uses == to determine. In this way, direct comparison based on memory address is more efficient.

conclusion

HikariCP contains many micro-optimizations that individually are barely measurable, but together combine as a boost to overall performance. Some of these optimizations are measured in fractions of a Even millisecond amortized over millions of invocations. HikariCP includes many micro-optimizations that are almost impossible to measure individually, but together improve overall performance. Some of these optimizations are amortized in millions of milliseconds.

  • learningConcurrentBagThis container class is very important and is key to the implementation of HikariCP pooling resources.
    • Four state transitions.
    • A couple of key ways.
    • Compared to traditional blocking queues, ConcurrentBag uses ThreadLocal to reduce the probability of locking.
  • contrastFastListAnd the JDKArrayListThe main difference between.

Next, learn about HikariDataSource.

Original is not easy, welcome to comment, like and attention. Welcome to pay attention to the public number: program ape YUE.