浅谈ThreadLocal设计

初看ThreadLocal的源码的时候，觉得有几个地方比较晦涩，于是索性按照自己的想法来看：如果是我会怎么设计这个API。以这种方式再次阅读源代码，顿觉豁然开朗，此间记录所思所想所得。

设计初衷：希望在线程中定义一个全局可见的变量，如Spring中一个Request通常由一个线程处理，如果能把上下文放在当前Requst作用域内，只有当前处理Request的线程可见，这样会带来极大的方便。

初步想法：在线程中定义一个HashTable，用于存储当前线程的变量，用法如下：

Thread t = Thread.currentThread();
// 设置局部变量
t.map.put(k, value);
// ...
// 使用局部变量
t.map.get(k);

// 另一个线程中
new Thread(() -> {
   Thread t1 = Thread.currentThread();
    t1.map.put(k, value);
    // ...
    t1.map.get(k);
}).start();

第一个问题：key应该如何定义？换句话说，key担什么责？首先key用于查找变量。而且这个key必须是每个线程可见且被多个线程共用，只是对应的值各自不同而已，所以叫线程局部。不妨定义一个类来专门做这件事情，名为ThreadLocal。在上面代码中，map暴露在外，我们并不想这么做，我们应该把map封装起来，放在ThreadLocal去做，会很方便。于是ThreadLocal的责任归结为：

当做key，用于查找变量
当做代理，用于设置和查找变量

因此新的代码如下:

// 定义局部变量
ThreadLocal<String> local = new ThreadLocal<>();

// 线程1
local.set("hi");                     // 1
System.out.println(local.get());     // hi

// 线程2
new Thread(() -> {
    local.set("hello");
    System.out.println(local.get()); // hello
}).start();

// ThreadLocal简要代码
class ThreadLocal {
    void set(T value) {
        Thread t = Thread.currentThread();
        Map<K, T> map = t.threadLocalMap;
        map.put(this, value);  
    }
    
    T get() {
        Thread t = Thread.currentThread();
        Map<K, T> map = t.threadLocalMap;
        return map.get(this);
    }
}

我们看到通过ThreadLocal一层的封装，API变得很简洁，也比较容易理解了。

第二个问题：这样的设计效率如何？瓶颈在哪里？ThreadLocal里面既没有锁，也没有线程切换。唯一可能的性能瓶颈是map操作。ThreadLocal中的map是高度定制的。对HashTable而言首要的问题是选择寻址方法。线程局部变量不会太多，一般是显式指定的，也就是说一旦程序启动，key的数量不会变了，所以使用线性探测足矣。使用线性探测可能会出现primary clustering问题，这个问题如下图所示，随着元素的增多，可能会出现i个长度的位置都会被占满的情况，如果这时候再进来一个元素，那么i个元素后面那个空位置被占据的概率将是(i + 1)/n，因为总长是n，通过hash函数算出的index被认为是均匀的，由元素扎堆引发查询时间加大，而且会愈演愈烈。这不是我们想看到的。

|<--- 长度为n的数组 --->|
[xxxxxxxxxxxx---------]
|<--- i --->|

解决思路：元素的hash code在被2^x（即table长度）整除后，应尽可能均匀分布，以减少探测次数。下面是ThreadLocal的hash处理：

// key的hash code，每次ThreadLocal实例化，生成下一个hash code
private final int threadLocalHashCode = nextHashCode();

// 累加器
private static AtomicInteger nextHashCode =
        new AtomicInteger();

// hash code累加步长        
private static final int HASH_INCREMENT = 0x61c88647;

// 生成下一个hash code
private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

// 计算index
private static int index(int h, int len) {
    return h & (len - 1);
}

我们看到hash code是通过每次累加0x61c88647这个数得到的，这个数并不是质数，其实只要能使生成的index相对均匀即可，这里我对前10个index的均匀性做了简单研究：

List<Integer> list = new ArrayList<>();
int len = 16;
for (int i = 0; i < 10; i++) {
    int h = nextHashCode();
    int i = h & (len - 1);
    list.add(i);
}
list.sort(Integer::compareTo);
System.out.println(list);
// 输出：[0, 1, 3, 5, 7, 8, 10, 12, 14, 15]

我们看到这一组hash code生成的index非常均匀，前10个不会发生碰撞，很不错的设计了。读者可以将size设置成32，threshold设置成21（ThreadLocalMap的load factor是2/3)，进一步观察index的分布。

题外话：有时候ThreadLocal不被引用了，我们希望map中的元素Entry可以被回收，以节省空间和效率。所以不妨让Entry继承WeakReference，并且对ThreadLocal进行引用，当这个ThreadLocal没被应用且被GC回收的时候，就可以回收这个entry了。在put操作的时候，如果发现当前探测到的key是null，见下方代码片段中的3，那说明这个位置上原来的ThreadLocal被GC回收了，直接替换即可。(参考各类引用的区别)

private void set(ThreadLocal<?> key, Object value) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);

    for (Entry e = tab[i];
         e != null;                        
         e = tab[i = nextIndex(i, len)]) {
        ThreadLocal<?> k = e.get();

        if (k == key) {
            e.value = value;
            return;
        }

        if (k == null) {  // 3
            replaceStaleEntry(key, value, i);
            return;
        }
    }
    tab[i] = new Entry(key, value);
    int sz = ++size;
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

至此，整个分析结束。学到了什么呢？