preface

In concurrent programming, a shared variable accessed by multiple threads may be thread-safe, whereas a variable stored using ThreadLocal is thread-safe because it is thread-local and can only be accessed by the thread itself.

The javaDoc comment on the ThreadLocal class says:

This class provides thread-local variables.  These variables differ from
* their normal counterparts in that each thread that accesses one (via its
* {@code get} or {@code set} method) has its own, independently initialized
* copy of the variable.  {@code ThreadLocal} instances are typically private
* static fields in classes that wish to associate state with a thread (e.g.,
* a user ID or Transaction ID).
Copy the code

This class provides thread-local variables. These variables are different from normal variables because each thread accessing a thread (through its GET /set methods) has its own, independently initialized copy of the variable. ThreadLocal instances are typically served as private static fields (such as user IDS or transaction IDS) in classes that associate state with threads.

ThreadLocal provides a way for each thread in a multi-threaded environment to have its own unique data and to pass it from top to bottom throughout thread execution.

The function of ThreadLocal is to provide local variables in the thread. When accessing in multi-threaded environment, the ThreadLocal variables in each thread are independent. That is, each thread’s ThreadLocal variables are its own and not accessible to other threads.

ThreadLocal exists as a lightweight storage, allowing us to use it without considering its thread-safety concerns.

ThreadLocal is most commonly used in a multi-threaded environment where there is concurrent access to a non-thread-safe object and the object does not need to be shared between threads, but we do not want to lock it. ThreadLocal can be used to make each thread hold a copy of the object.

The above is just a direct introduction to the concept, and the reader will still be confused by this,ThreadLocalHow do you implement only serving the current thread? Don’t worry, in the underlying principle module, we will slowly unfold.

Usage scenarios

In this section, we’ll take a look at a simple use of ThreadLocal.

A class in AOP

In the Spring AOP module (the principles of AOP will not be covered in detail in this article), we see a class like this:

public abstract class AopContext {
    
    /**
	 * ThreadLocal holder for AOP proxy associated with this thread.
	 * Will contain {@code null} unless the "exposeProxy" property on
	 * the controlling proxy configuration has been set to "true".
	 * @see ProxyConfig#setExposeProxy
	 */
	private static final ThreadLocal<Object> currentProxy = new NamedThreadLocal<Object>("Current AOP proxy");
    
    public static Object currentProxy(a) throws IllegalStateException {
		Object proxy = currentProxy.get();
		if (proxy == null) {
			throw new IllegalStateException(
					"Cannot find current proxy: Set 'exposeProxy' property on Advised to 'true' to make it available.");
		}
		return proxy;
	}
    
    static Object setCurrentProxy(Object proxy) {
		Object old = currentProxy.get();
		if(proxy ! =null) {
			currentProxy.set(proxy);
		}
		else {
			currentProxy.remove();
		}
		returnold; }}Copy the code

CurrentProxy objects can be written/read using setCurrentProxy and currentProxy methods respectively.

As you can probably guess, currentProxy actually stores a proxy object, which is the current proxy object from the **”current” in the name. It becomes clear when we look at ThreadLocal that currentProxy refers to the proxy object associated with the current thread.

To solveSimpleDateFormatThe thread is not safe

SimpleDateFormat is thread-safe, and we can eliminate thread-safe issues by storing SimpleDateFormat objects with ThreadLocal.

private static ThreadLocal<SimpleDateFormat> threadLocal = 
    ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"));
Copy the code

The underlying principle

Why can ThreadLocal store thread-local variables?

Once we create a ThreadLocal object, we use the set method to write the value.

 public void set(T value) {
        // Get the current thread
        Thread t = Thread.currentThread();
        / / get ThreadLocalMap
        ThreadLocalMap map = getMap(t);
        if(map ! =null)
            map.set(this, value);
        else
            createMap(t, value);
    }
Copy the code

We find that the ThreadLocal#set method retrieves the current thread and then retrieves the ThreadLocalMap object based on the current thread.

ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}
Copy the code

Surprisingly, ThreadLocalMap is a variable in the Thread class.

public class Thread implements Runnable {... ThreadLocal.ThreadLocalMap threadLocals =null; . }Copy the code

After a brief analysis, ThreadLocal is just a shell. The real data store is the ThreadLocaMap object associated with the Thread object. Therefore, ThreadLocal can be used to store thread-local variables because of the ThreadLocalMap object.

ThreadLocal -> Thread.threadlocalMap

The data structure

From the discussion in the above section, we find that the exploration of the underlying data structure of ThreadLocal is actually an understanding of the internal structure of ThreadLocalMap.

 public void set(T value) {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if(map ! =null)
            map.set(this, value);
        else
            createMap(t, value);
    }
Copy the code

Above is the ThreadLocal#set method, and you can see that the ThreadLocalMap#set method is finally called

 private void set(ThreadLocal
        key, Object value) {
            / / array
            Entry[] tab = table;
            int len = tab.length;
            // Use the hash value to compute the index of an array element
            int i = key.threadLocalHashCode & (len-1);

            for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) { ... }... }Copy the code
  • ThreadLocalMap uses an array structure (Entry[]) to store data

  • Entry is a weak-reference implementation, and as long as no strong reference exists, it will be reclaimed when GC occurs.

     static class Entry extends WeakReference<ThreadLocal<? >>{
                /** The value associated with this ThreadLocal. */Object value; Entry(ThreadLocal<? > k, Object v) {super(k); value = v; }}Copy the code
  • Data elements are stored in hashes, in this case using the Fibonacci hash method

  • Since this differs from the data structure of HashMap, hash collisions are not stored as linked lists or red-black trees, but instead are stored using the zipper method.

    That is, when the same subscript location conflicts, +1 is addressed backwards until an empty location or garbage collection location is found for storage.

Hash algorithm

Since ThreadLocal is zipped based on an array structure, there must be a hash calculation.

   private final int threadLocalHashCode = nextHashCode();

    /** * The next hash code to be given out. Updated atomically. Starts at * zero. */
    private static AtomicInteger nextHashCode =
        new AtomicInteger();

    /** * The difference between successively generated hash codes - turns * implicit sequential thread-local IDs into near-optimally spread * multiplicative hash values for power-of-two-sized tables. */
    private static final int HASH_INCREMENT = 0x61c88647;

    /** * Returns the next hash code. */
    private static int nextHashCode(a) {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }
Copy the code

Mysterious 0 x61c88647

The main hash methods include division hash, square hash, Fibonacci hash, and random number.

ThreadLocal, on the other hand, uses Fibonacci hashing + zipping to store data into array structures. The Fibonacci sequence is used to make the data more hashed and less hashed.

0x61C88647 Magic number selection is related to Fibonacci hash, 0x61C88647 corresponds to decimal 1640531527.

In theory and practice, when we assign each ThreadLocal its own ID using 0x61C88647 as the magic sum, that is, threadLocalHashCode modulo with the power of 2, the results are evenly distributed.

Specifically from the calculation of mathematical formula, formula: F (k) = ((K * 2654435769) >> X) << Y

For a common 32-bit integer, f(k) = (k * 2654435769) >> 28.

We won’t go into the exact math, just know that ThreadLocal uses the Fibonacci sequence to make the data more scattered, thus reducing the frequency of hash collisions.

The source code interpretation

ThreadLocalMapThe structure of the

        // Initial capacity
		private static final int INITIAL_CAPACITY = 16;
		
        private Entry[] table;

        /** * table number of elements */
        private int size = 0;
		
		// The capacity expansion condition threshold is reached
        private int threshold; // Default to 0ThreadLocalMap(ThreadLocal<? > firstKey, Object firstValue) { table =new Entry[INITIAL_CAPACITY];	
           	// Computes the index of the first stored element
            int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
           	// Create an element first
            table[i] = new Entry(firstKey, firstValue);
            size = 1;
            // Set the threshold
            setThreshold(INITIAL_CAPACITY);
      }
	  private void setThreshold(int len) {
          	/ / 16 * 2/3 = 10
            threshold = len * 2 / 3;
      }
Copy the code

set

ThreadLocalMap#set
private void set(ThreadLocal
        key, Object value) {

            Entry[] tab = table;
            int len = tab.length;
            // Fibonacci hashes the array subscript
            int i = key.threadLocalHashCode & (len-1);
			
            // Loop to see if the element exists
    		// e represents the Entry element obtained from the index of the array computed by Fibonacci hash
            for (Entry e = tab[i];
                 // Array elements are not emptye ! =null;
                 e = tab[i = nextIndex(i, len)]) { // 4. Key is not the same, zipper method address
                
                // Get the ThreadLocal object (key) of the Entry elementThreadLocal<? > k = e.get();// 2. If the key is equal, replace the original value
                if (k == key) {
                    e.value = value;
                    return;
                }
				
                // 3. If key is not equal and k is null (this happens when weak references are GC)
                if (k == null) {
                    // Probe to clean up expired elements
                    replaceStaleEntry(key, value, i);
                    return; }}// 1. Insert directly in an empty position
            tab[i] = new Entry(key, value);
    		
    		// The current number of elements in the array
            int sz = ++size;
    		// cleanSomeSlots: heuristic cleaning
            if (!cleanSomeSlots(i, sz) && sz >= threshold){
                rehash();
            }
}
Copy the code

Expansion mechanism

 if(! cleanSomeSlots(i, sz) && sz >= threshold){ rehash(); }Copy the code
  • cleanSomeSlots(i, sz)Heuristic cleanup to remove expired elements
  • If no expired elements are cleared, the system determines whether the number of elements in the Entry array exceeds the threshold. If so, the system expands the number

The core method for capacity expansion is Rehash.

private void rehash(a) {
    		// Probe to clean up expired elements
            expungeStaleEntries();
            // Use lower threshold for doubling to avoid hysteresis
    		// size > = threshold * 3/4
            if (size >= threshold  - threshold / 4)
                resize();
}
Copy the code
ThreadLocalMap#resize
private void resize(a) {
    		// Old Entry array
            Entry[] oldTab = table;
    		// Length of the old array
            int oldLen = oldTab.length;
    		// Calculate the length of the new array
            int newLen = oldLen * 2;
    		// Create a new array
            Entry[] newTab = new Entry[newLen];
            int count = 0;
			
    		// Loop over the old array
            for (int j = 0; j < oldLen; ++j) {	
                // Get the elements of the old array
                Entry e = oldTab[j];
                / / found empty
                if(e ! =null) {
                    / / get the keyThreadLocal<? > k = e.get();// If key is null, set value to null to help GC
                    if (k == null) {
                        e.value = null; // Help the GC
                    } else {
                        // Recalculate the element's hash value using the Fibonacci sequence
                        int h = k.threadLocalHashCode & (newLen - 1);
                        
                        // If there are elements in the current position, proving that a hash conflict has occurred, use the zip method to find the position below
                        while(newTab[h] ! =null)
                            h = nextIndex(h, newLen);
                        // Set the location
                        newTab[h] = e;
                        // Count the elements in the new arraycount++; }}}// Set a new capacity expansion threshold
            setThreshold(newLen);
            size = count;
    		// Associate the new array with the table variable
            table = newTab;
}
Copy the code

Heuristic cleaning

ThreadLocal#cleanSomeSlots
private boolean cleanSomeSlots(int i, int n) {
            boolean removed = false;
            Entry[] tab = table;
            int len = tab.length;
            do {
                i = nextIndex(i, len);
                Entry e = tab[i];
                if(e ! =null && e.get() == null) {
                    n = len;
                    removed = true; i = expungeStaleEntry(i); }}while ( (n >>>= 1) != 0);
    
            return removed;
}
Copy the code

The while loop constantly moves right to find expired elements that need to be cleaned up, and is eventually processed using expungeStaleEntry, which includes the shift of the element.

Exploratory cleaning

Exploratory cleaning, starting with the currently encountered elements and working backwards. The rehash is not stopped until we Encounter NULL Entry elements.

ThreadLocalMap#expungeStaleEntry
 private int expungeStaleEntry(int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;

            // expunge entry at staleSlot
            tab[staleSlot].value = null;
            tab[staleSlot] = null;
            size--;

            // Rehash until we encounter null
            Entry e;
            int i;
            for(i = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();if (k == null) {
                    e.value = null;
                    tab[i] = null;
                    size--;
                } else {
                    int h = k.threadLocalHashCode & (len - 1);
                    if(h ! = i) { tab[i] =null;

                        // Unlike Knuth 6.4 Algorithm R, we must scan until
                        // null because multiple entries could have been stale.
                        while(tab[h] ! =null) h = nextIndex(h, len); tab[h] = e; }}}return i;
        }
Copy the code

conclusion

This article briefly introduces the principle of ThreadLocal, including how ThreadLocal can achieve isolation between threads, Fibonacci hashing to reduce hash conflicts, capacity expansion, heuristic cleaning and probing cleaning, etc. Due to my limited level, MANY places have not done more in-depth discussion, I feel ashamed!

Interviewer: Dude, I hear you’ve read the source code for ThreadLocal

In our understanding of ThreadLocal, we can see that the underlying principles of ThreadLocal are based on excellent data structures and algorithms. Consider the code written by Josh Bloch and Doug Lea.

Refer to the content

  1. Functions and uses of ThreadLocal

  2. If you ask me this question, I’ll hang up!