Administrator
发布于 2019-01-11 / 3035 阅读
18

ConcurrentHashMap 为什么比 synchronizedMap 快

压测报告里,那根最扎眼的柱子

一月初做订单履约服务的性能优化,主管让我把瓶颈点列一遍。用 JMH 跑了几个核心组件的基准测试,结果里最刺眼的是本地缓存这一项:同样 8 线程、读写比 9:1,Collections.synchronizedMap(new HashMap<>()) 的吞吐是 2.1M ops/s,换成 ConcurrentHashMap 是 13.6M ops/s,差了 6.5 倍。

我当然知道 CHM 更快,但 6.5 倍这个数字超出了我的预期。如果只是"锁粒度更细",在有竞争的情况下应该是 3 到 4 倍才对。于是去翻了源码,发现我一直以来的理解有个错误:我把 JDK 8 的 CHM 还按 JDK 7 的分段锁在想。

先复现:把读写拆开测

写了三组对照,JMH 配置是 4 核机器(8 逻辑核)、8 线程、预热 3 轮、测量 5 轮、每轮 10 秒。Map 里预置 10000 个键值对。

@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@State(Scope.Benchmark)
@Warmup(iterations = 3, time = 10)
@Measurement(iterations = 5, time = 10)
@Threads(8)
public class MapBenchMark {

    private Map<Integer, Integer> syncMap;
    private Map<Integer, Integer> chm;

    @Setup
    public void setup() {
        syncMap = Collections.synchronizedMap(new HashMap<>());
        chm = new ConcurrentHashMap<>();
        for (int i = 0; i < 10000; i++) {
            syncMap.put(i, i);
            chm.put(i, i);
        }
    }

    @Benchmark
    public Integer syncMapGet() {
        return syncMap.get(ThreadLocalRandom.current().nextInt(10000));
    }

    @Benchmark
    public Integer chmGet() {
        return chm.get(ThreadLocalRandom.current().nextInt(10000));
    }
}

纯读场景的结果:

场景1 线程4 线程8 线程16 线程
synchronizedMap.get38.2M ops/s6.1M3.4M3.1M
ConcurrentHashMap.get41.5M ops/s158M302M298M

这个表解释了我的疑问。单线程下两者几乎一样(38.2 vs 41.5,synchronized 的偏向锁开销很小),但 4 线程时 CHM 是它的 26 倍,8 线程是 89 倍。差距不是来自"锁更细",而是来自"读根本不加锁",所以能随着线程数线性扩展,而 synchronizedMap 的读是互斥的,线程越多抢得越厉害,吞吐反而往下掉。

读操作为什么能做到无锁

看 JDK 8 的 get

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)                       // 负数 hash 代表特殊节点
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

整段没有任何同步动作,靠三样东西保证正确性:

  • table 被声明为 volatile,扩容后新数组能被立刻看到
  • Node.valNode.next 都是 volatile,保证了 happens-before:写线程在 synchronized 块里改完 val,读线程立刻可见
  • tabAt 用的是 Unsafe.getObjectVolatile,拿到的是那一瞬间数组槽位里的真实引用,不会读到半成品
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

读线程遇到正在扩容的桶(eh < 0 表示 ForwardingNode)时会走 e.find() 去新数组里查,这个设计让扩容期间的读也不用停。

写操作:JDK 7 的分段锁已经被推翻了

我以前理解的 CHM 是"默认 16 个 Segment,每个 Segment 一把 ReentrantLock,并发度 16"。那是 JDK 7。JDK 8 里 Segment 这个类还在,但只用于序列化兼容,实际数据结构回到了"数组 + 链表/红黑树",锁的对象变成了桶里的头节点

我把 JDK 7 的 Segment 定义和 JDK 8 的 putVal 放在一起看,差别一目了然:

// JDK 7
static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile HashEntry<K,V>[] table;
    transient int count;
}

// JDK 8 的 putVal(节选,省略红黑树分支)
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();                                   // CAS 初始化
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                    // 空桶:一次 CAS 搞定,完全不加锁
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);                          // 帮忙迁移
        else {
            V oldVal = null;
            synchronized (f) {                                   // 锁的粒度是单个桶
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent) e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    // 省略树节点分支
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null) return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

三个关键变化:

  • 锁粒度从 16 降到"桶数量"。默认初始容量 16,但扩容后桶数是几千,冲突概率被摊薄到可以忽略。在命中不同桶的情况下,写操作连锁都碰不到。
  • 空桶插入走 CAS,不进 synchronizedcasTabAt 失败就自旋重试,没有线程挂起和唤醒的开销。
  • 从 ReentrantLock 换成 synchronized。这点我一开始很困惑,后来想明白了:ReentrantLock 在 JDK 6 之后和 synchronized 性能已经接近,而 synchronized 有 JVM 层面的锁粗化、锁消除优化,代码也简洁。而且这里锁的是桶头节点,竞争极小,偏向锁几乎不用升级。

顺带说明初始化和计数的做法

initTable() 用了一个 sizeCtl 变量做状态机,值为 -1 表示正在初始化,其他线程检测到就 Thread.yield() 让出:

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield();                    // 让出 CPU,不阻塞
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);        // 0.75 * n
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

size() 不是免费的,这是我踩到的第二个坑

上面说 CHM 读无锁,但 size() 是个例外。它不像 HashMap 那样维护一个 int 字段,因为这会让每次 put 都去竞争同一个计数器,把无锁的优势全毁掉。JDK 8 用的是 baseCount + CounterCell[] 的分段计数(思路借鉴 LongAdder):

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

我们有个监控任务每秒调一次 cache.size() 上报,map 里有 200 万条数据、8 个 CounterCell。测下来单次 size() 要遍历一遍 CounterCell 数组,平均 1.8 微秒,看着不多,但它是个"遍历"操作,并发写多的时候 CounterCell 数组会扩容,遍历长度会变。

更麻烦的是语义:size() 返回的是遍历过程中的瞬时累加值,在并发写入时它可能不是一个真实存在过的数量。如果需要精确的 int 值并且能接受上限,官方建议用 mappingCount()(返回 long,不会在超过 Integer.MAX_VALUE 时被截断成 MAX_VALUE)。我们的监控改成了:

gauge.set(chm.mappingCount());   // 语义更准确,且明确返回 long

另外,判断 Map 是否为空一律用 isEmpty() 而不是 size() == 0,前者只要 sumCount() <= 0,实现上有短路。

回到压测:改完之后

把履约服务里的三处 synchronizedMap 换成 ConcurrentHashMap 之后,重新跑了一遍全链路压测(300 并发,10 分钟):

指标改之前改之后
平均 TPS1,8403,270
P99 响应时间286ms141ms
CPU 使用率62%48%

TPS 涨了 78%,比 JMH 里看到的 6.5 倍低很多,因为这个瓶颈只占全链路的一部分。CPU 反而降了,这一点很值得记:锁竞争时线程会自旋或者挂起,自旋烧 CPU,挂起唤醒消耗上下文切换,都是纯浪费。锁竞争打下去之后,有效工作占比上来了。

小结

这次翻源码纠正了我两个认知。

  • JDK 8 的 CHM 已经不是分段锁了,是"数组 + 链表/红黑树 + 桶头节点 synchronized + 空桶 CAS"。拿 JDK 7 的知识回答 JDK 8 的问题,在面试和方案评审里都会露馅。
  • 它的性能优势主要不在"写更快",而在"读完全无锁"。判断一个并发容器好不好,先看它的读路径,因为绝大多数场景读远多于写。

最后一点提醒:CHM 只保证容器自身操作的线程安全,不保证你用它的那段业务逻辑安全。我见过有人写出这种代码还觉得没问题:

// 错的:两步操作之间没有原子性
if (!map.containsKey(key)) {
    map.put(key, loadFromDb(key));      // 可能被另一个线程插进来,loadFromDb 跑两次
}

这种情况该用 putIfAbsentcomputeIfAbsent。不过 computeIfAbsent 的映射函数里不能再改同一个 map,会死锁,这个我下次写。

参考