The data structure of ThreadLocal#

The Thread class has an instance variable of type ThreadLocal.ThreadLocalMap named threadLocals, meaning each thread has its own ThreadLocalMap.

ThreadLocalMap has its own independent implementation. Its key can be viewed as the ThreadLocal, and the value is the value stored in the map (in fact, the key is not the ThreadLocal itself, but a weak reference to it).

Whenever a thread puts a value into a ThreadLocal, it stores it in its own ThreadLocalMap; reads also use the ThreadLocal as the reference and search for the corresponding key within its own map, achieving thread isolation.

ThreadLocalMap is somewhat like a HashMap in structure, but while a HashMap is implemented as an array plus linked lists, ThreadLocalMap does not use a linked-list structure.

We should also note that the Entry’s key is ThreadLocal<?> k, which inherits from WeakReference, i.e., it is a weak reference type.

Diagrammatic explanation of ThreadLocalMap.set()#

After understanding the hash algorithm, let’s see how set is implemented.

Setting data in ThreadLocalMap (new or updated) falls into several situations; for each situation, we illustrate with diagrams.

1. The slot computed by the hash points to an empty Entry:

   

   Here we simply place the data into that slot.

2. The slot contains data, and the key equals the current ThreadLocal’s hashed key:

   

   Here we directly update the data in that slot.

3. The slot contains data, and while traversing forward, before finding a slot with Entry equal to null, we have not encountered an expired key:

   

   We traverse the hash array linearly; if we find a slot with Entry equal to null, we put the data there; or, during traversal, if we encounter data with the same key value, we update it directly.

4. The slot contains data, and while traversing forward, before finding a slot with Entry equal to null, we encounter an expired key Entry as shown: the Entry at index 7 has key=null:

   

   The hash table index 7 has an Entry whose key is null, indicating that this data’s key value has been garbage collected. In this case the replaceStaleEntry() method is invoked, which handles the logic of replacing expired data. Starting from index 7, it performs a probing cleanup.

   The initialization of the probing cleanup start position is: slotToExpunge = staleSlot = 7

   Starting from the current staleSlot, we iterate backward to find other expired data, updating the starting scan index slotToExpunge. The loop ends when it hits an Entry that is null.

   If expired data is found, we continue forward; if we encounter data with the same key value, we update that Entry’s data and swap the staleSlot element with that Entry (the staleSlot position becomes an expired element). After updating the Entry data, we begin cleaning up expired entries, as shown:

   If during the backward iteration we do not find an expired data, the forward iteration may not find a matching key; in that case, a new Entry is created and replaces the table[staleSlot] position:

   

   After replacement, cleanup of expired elements is performed via two methods: expungeStaleEntry() and cleanSomeSlots().

The source of ThreadLocalMap.set()#

The above diagrams already illustrate the principle of set(); the actual code is as follows:

1
private void set(ThreadLocal<?> key, Object value) {
2
    // Determine the slot using the key and then linearly search forward to find a usable bucket.
3
    Entry[] tab = table;
4
    int len = tab.length;
5
    int i = key.threadLocalHashCode & (len-1);
6

7
    // Iterate forward
8
    for (Entry e = tab[i];
9
         e != null;
10
         e = tab[i = nextIndex(i, len)]) {
11
        // If the bucket’s Entry for the key is not null
12
        ThreadLocal<?> k = e.get();
13

14
        // If k equals key, this is a replacement operation; update and return
15
        if (k == key) {
16
            e.value = value;
17
            return;
18
        }
19

20
        // If k == null, this is an expired entry; perform replaceStaleEntry() and return
21
        if (k == null) {
22
            replaceStaleEntry(key, value, i);
23
            return;
24
        }
25
    }
26

27
    // If we get here, we found a null slot after iterating
28
    // Create a new Entry in this slot and increment size
29
    tab[i] = new Entry(key, value);
30
    int sz = ++size;
31
    // Perform a heuristic cleanup of expired data
32
    // If no cleanup occurred and size exceeds the threshold, perform a rehash
33
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
34
        rehash();
35
}
36

37
private static int nextIndex(int i, int len) {
38
    return ((i + 1 < len) ? i + 1 : 0);
39
}
40

41
private static int prevIndex(int i, int len) {
42
    return ((i - 1 >= 0) ? i - 1 : len - 1);
43
}

When is a bucket usable?

1. The key equals the current key: replacement is allowed.
2. When encountering an expired bucket, perform replacement to occupy the expired bucket.
3. While traversing, when encountering an Entry with Entry=null, use it.

Next, focus on the replaceStaleEntry() method, which provides the logic to replace expired data. We can map this to the fourth scenario’s principle diagram. The code is:

1
java.lang.ThreadLocal.ThreadLocalMap.replaceStaleEntry() …

1
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
2
                                       int staleSlot) {
3
    Entry[] tab = table;
4
    int len = tab.length;
5
    Entry e;
6

7
    // Start of probing cleanup: begin from the current staleSlot
8
    int slotToExpunge = staleSlot;
9
    // Walk backward from the current staleSlot, until we encounter null
10
    for (int i = prevIndex(staleSlot, len);
11
         (e = tab[i]) != null;
12
         i = prevIndex(i, len))
13

14
        // If an expired entry is found, update the start of probing cleanup
15
        if (e.get() == null)
16
            slotToExpunge = i;
17

18
    // Walk forward from staleSlot; until we encounter a null Entry
19
    for (int i = nextIndex(staleSlot, len);
20
         (e = tab[i]) != null;
21
         i = nextIndex(i, len)) {
22

23
        ThreadLocal<?> k = e.get();
24

25
        // If we meet the same key, this is a replacement
26
        // Replace the data and swap the staleSlot element
27
        if (k == key) {
28
            e.value = value;
29

30
            tab[i] = tab[staleSlot];
31
            tab[staleSlot] = e;
32

33
            // If the initial probe didn’t find stale data
34
            // set the new starting expunge index to i
35
            if (slotToExpunge == staleSlot)
36
                slotToExpunge = i;
37
            // Clean up with a heuristic cleanup
38
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
39
            return;
40
        }
41
        // If key is null, and slotToExpunge == staleSlot
42
        // update slotToExpunge to i
43
        if (k == null && slotToExpunge == staleSlot)
44
            slotToExpunge = i;
45
    }
46
    // If no matching key is found, add a new entry at staleSlot
47
    tab[staleSlot].value = null;
48
    tab[staleSlot] = new Entry(key, value);
49

50
    // If there were other expired slots, start cleanup
51
    if (slotToExpunge != staleSlot)
52
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
53
}

The probing cleanup flow for expired keys in ThreadLocalMap#

We mentioned two ways to clean expired keys in ThreadLocalMap: probing cleanup and heuristic cleanup.

1
private int expungeStaleEntry(int staleSlot) {
2
    Entry[] tab = table;
3
    int len = tab.length;
4

5
    // Clear the stale slot and decrease size
6
    tab[staleSlot].value = null;
7
    tab[staleSlot] = null;
8
    size--;
9

10
    Entry e;
11
    int i;
12
    // Iterate forward from the staleSlot
13
    for (i = nextIndex(staleSlot, len);
14
         (e = tab[i]) != null;
15
         i = nextIndex(i, len)) {
16
        ThreadLocal<?> k = e.get();
17
        // If the key has expired
18
        if (k == null) {
19
            e.value = null;
20
            tab[i] = null;
21
            size--;
22
        } else {
23
            // If the key hasn’t expired, recalculate its index
24
            int h = k.threadLocalHashCode & (len - 1);
25
            if (h != i) {
26
                tab[i] = null;
27

28
                while (tab[h] != null)
29
                    h = nextIndex(h, len);
30
                tab[h] = e;
31
            }
32
        }
33
    }
34
    return i;
35
}

1
private boolean cleanSomeSlots(int i, int n) {
2
    boolean removed = false;
3
    Entry[] tab = table;
4
    int len = tab.length;
5
    do {
6
        i = nextIndex(i, len);
7
        Entry e = tab[i];
8
        if (e != null && e.get() == null) {
9
            n = len;
10
            removed = true;
11
            i = expungeStaleEntry(i);
12
        }
13
    } while ( (n >>>= 1) != 0);
14
    return removed;
15
}

The growth mechanism of ThreadLocalMap#

In ThreadLocalMap.set(), after performing heuristic cleanup, if nothing was cleaned and the size has reached the threshold (len * 2/3), it triggers a rehash:

1
if (!cleanSomeSlots(i, sz) && sz >= threshold)
2
    rehash();

Next, the implementation of rehash() is as follows:

1
private void rehash() {
2
    expungeStaleEntries();
3

4
    if (size >= threshold - threshold / 4)
5
        resize();
6
}
7

8
private void expungeStaleEntries() {
9
    Entry[] tab = table;
10
    int len = tab.length;
11
    for (int j = 0; j < len; j++) {
12
        Entry e = tab[j];
13
        if (e != null && e.get() == null)
14
            expungeStaleEntry(j);
15
    }
16
}

1. Perform probing cleanup across the table from the start.
2. After cleanup, there may be entries with null keys; this is removed by expungeStaleEntries().
3. Then, based on the condition size >= threshold - threshold / 4 (i.e., size >= 3/4 of threshold), decide whether to expand.

When asked about the expansion mechanism, it’s important to mention these two steps.

Next, the actual resize() method (for demonstration, consider an example where oldTab.len = 8):

The new table size is oldLen * 2.

1. Traverse the old hash table, recompute hash positions, and place entries into the new table.
2. If a hash conflict occurs, pick the nearest slot whose Entry is null.
3. After traversal, all entries from the old table have been moved into the new one.
4. Recompute the next expansion threshold for the new table.

Code:

1
private void resize() {
2
    Entry[] oldTab = table;
3
    int oldLen = oldTab.length;
4
    int newLen = oldLen * 2;
5
    Entry[] newTab = new Entry[newLen];
6
    int count = 0;
7

8
    for (int j = 0; j < oldLen; ++j) {
9
        Entry e = oldTab[j];
10
        if (e != null) {
11
            ThreadLocal<?> k = e.get();
12
            if (k == null) {
13
                e.value = null;
14
            } else {
15
                int h = k.threadLocalHashCode & (newLen - 1);
16
                while (newTab[h] != null)
17
                    h = nextIndex(h, newLen);
18
                newTab[h] = e;
19
                count++;
20
            }
21
        }
22
    }
23

24
    setThreshold(newLen);
25
    size = count;
26
    table = newTab;
27
}

Diagram of ThreadLocalMap.get()#

1. Compute the slot from the key; if the Entry.key in that slot matches the searched key, return it:

   

2. If the Entry.key in the slot does not match the searched key:

   

We take get(ThreadLocal1) as an example. After hashing, the correct slot would be 4, but index 4 already has data whose key is not ThreadLocal1, so we need to continue iterating.

When we reach index 5, the Entry.key is null. This triggers a probing cleanup operation via expungeStaleEntry(). After cleanup, data at index 5 and 8 are cleared, and data at indices 6 and 7 move forward. After moving forward, we resume from index 5 and continue to index 6, where we find the entry whose key matches, as shown:

1
private Entry getEntry(ThreadLocal<?> key) {
2
    int i = key.threadLocalHashCode & (table.length - 1);
3
    Entry e = table[i];
4
    if (e != null && e.get() == key)
5
        return e;
6
    else
7
        return getEntryAfterMiss(key, i, e);
8
}
9

10
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
11
    Entry[] tab = table;
12
    int len = tab.length;
13

14
    while (e != null) {
15
        ThreadLocal<?> k = e.get();
16
        if (k == key)
17
            return e;
18
        if (k == null)
19
            expungeStaleEntry(i);
20
        else
21
            i = nextIndex(i, len);
22
        e = tab[i];
23
    }
24
    return null;
25
}

Use cases for ThreadLocal#

In our project, we use ELK+Logstash for logging, and Kibana for viewing and searching.

All services are typically exposed in a distributed system; cross-service calls can be linked with a traceId. But how is the traceId passed across different projects?

We use org.slf4j.MDC to implement this, which internally relies on ThreadLocal. The implementation is as follows:

When a request hits Service A, Service A generates a string traceId similar to a UUID and places it in the current thread’s ThreadLocal. When calling Service B, the traceId is written into the request’s headers. Service B, on receiving the request, first checks if the header contains traceId, and if present, writes it into its own thread’s ThreadLocal.

requestId is the cross-system trace identifier; inter-service calls use it to locate the corresponding path. There are also other scenarios:

For these scenarios, there are corresponding solutions, as shown below.

Feign remote invocation solution#

Service sending request:

1
@Component
2
@Slf4j
3
public class FeignInvokeInterceptor implements RequestInterceptor {
4

5
    @Override
6
    public void apply(RequestTemplate template) {
7
        String requestId = MDC.get("requestId");
8
        if (StringUtils.isNotBlank(requestId)) {
9
            template.header("requestId", requestId);
10
        }
11
    }
12
}

Service receiving request:

1
@Slf4j
2
@Component
3
public class LogInterceptor extends HandlerInterceptorAdapter {
4

5
    @Override
6
    public void afterCompletion(HttpServletRequest arg0, HttpServletResponse arg1, Object arg2, Exception arg3) {
7
        MDC.remove("requestId");
8
    }
9

10
    @Override
11
    public void postHandle(HttpServletRequest arg0, HttpServletResponse arg1, Object arg2, ModelAndView arg3) {
12
    }
13

14
    @Override
15
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {
16

17
        String requestId = request.getHeader(BaseConstant.REQUEST_ID_KEY);
18
        if (StringUtils.isBlank(requestId)) {
19
            requestId = UUID.randomUUID().toString().replace("-", "");
20
        }
21
        MDC.put("requestId", requestId);
22
        return true;
23
    }
24
}

Thread pool asynchronous invocation, passing requestId#

Because MDC is based on ThreadLocal, in asynchronous operations, child threads cannot access the parent thread’s ThreadLocal data. You can customize the thread pool executor and modify its run() method:

1
public class MyThreadPoolTaskExecutor extends ThreadPoolTaskExecutor {
2

3
    @Override
4
    public void execute(Runnable runnable) {
5
        Map<String, String> context = MDC.getCopyOfContextMap();
6
        super.execute(() -> run(runnable, context));
7
    }
8

9
    @Override
10
    private void run(Runnable runnable, Map<String, String> context) {
11
        if (context != null) {
12
            MDC.setContextMap(context);
13
        }
14
        try {
15
            runnable.run();
16
        } finally {
17
            MDC.remove();
18
        }
19
    }
20
}

Use MQ to send messages to a third-party system#

In the MQ message body, add a custom property requestId. The receiver consumes the message and can parse the requestId for use.