HashMap扩容导致的生产问题

HashMap的扩容问题作为Java八股文的重要考点之一，已经背得滚瓜烂熟，但还是在生产中踩了坑（总有一个坑的形状适合你）。这里再记录一下当时的复盘。

问题概述

2023.10.27，某国0点开始，业务投放量同比前一天出现明显下跌（约30%），当天下午通过报表数据发现了此问题，晚上20:00修复代码后数据恢复。

问题发现过程

• 11:00，下游业务触发限流，发现流量上涨了一倍多，但因临近大促以为是大促流量，直接调高了限流阈值，没有引起重视
• 16:20，算法同学发现业务投放量有明显下跌，开始排查问题，看到是从0点开始，业务投放量同比昨天下跌了30%左右。排查入口流量，发现流量平稳，并没有大促带来的流量，说明可能是代码问题，排查陷入僵局
• 19:00~20:00，找到问题原因，修复代码并发布

快速定位

问题的主要表现有：

• 业务投放量同比下跌30%
• 业务投放疲劳度拦截量同步增长1倍
• 下游流量增长1倍，但入口流量没有变化
• 业务内部拦截策略和流量没有变化

表面原因是业务投放疲劳度拦截增多导致投放量下跌，但业务内部拦截策略和流量没有变化。

注意到一个关键的时间点是0点，在这个时间点，业务的投放计划会发生变化。所谓“投放计划”是指运营配置指定的时间在APP上投放指定活动素材，0点是很多计划上线或者下线的时间点。业务投放量下降是从当天0点开始的，并且看发布记录期间没有代码的变化，那么一定是投放计划达到了某个临界点，或者满足了某种条件，才触发了bug，比如：数量、类型等。

此时我回忆起近期预发偶现的一个bug：有时候一次请求，会触发下游2次调用。这个2次和此次问题中下游流量增长2倍，是同一个逻辑。（QA同学常说，偶现的bug必然是某种条件下必现的bug，我一定能复现出来给你提bug的！哈哈。）

于是继续排查，把精力集中在调用下游接口上，搜索相关日志，果然发现了一个奇怪的现象：我们把下游调用的查询结果会缓存在LinkedHashMap结构的context变量里，但同一个key竟然产生了2个数据。

context={"k1":"v1", ...., "key": "result", "key": "result", ..., "kn":"vn"}

首先解释一下为什么使用LinkedHashMap结构的context。我们一次请求需要多次调用下游，为了满足时延要求，采用的并发处理。同时为了避免下游1:N的流量扩大，因此采用了一个线程安全数据结构来存储下游结果，一次调用，多次使用。如下图所示。

通常来说第一个想到的是ConcurrentHashMap，但为了日志打印能按照key进行顺序打印方便排查问题，采用了如下的结构：

public class DeliveryRequestContext {
	private final Map<String, Object> data;

	private DeliveryRequestContext() {
		this.data = Collections.synchronizedMap(new LinkedHashMap<>()); 
	}
}

利用LinkedHashMap保证打印时按照插入顺序打印，利用Collections.synchronizedMap进行一层线程安全的封装：

private static class SynchronizedMap<K,V> {
    final Object      mutex;        // Object on which to synchronize
    SynchronizedMap(Map<K,V> m) {
        this.m = Objects.requireNonNull(m);
        mutex = this;
    }

    public V get(Object key) {
        synchronized (mutex) {return m.get(key);}
    }

    public V put(K key, V value) {
        synchronized (mutex) {return m.put(key, value);}
    }

    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
    	synchronized (mutex) {return m.computeIfAbsent(key, mappingFunction);}
    }
    ……

首先来排除线程安全问题：

1. 怀疑是调用的bug。难道是调用了2次？但key如果是相同的，即使调用2次，也应该会覆盖。同时，这么明显的线程安全问题，在代码中肯定早就考虑过了：

   context.computeIfAbsent("key", k -> { 
   	return 调用下游的result();
   });

2. 怀疑是库的bug。虽然JDK8出了这么久还能发现库bug的可能性几乎和中彩票概率一样，但我们还是仔细分析了其中的线程安全代码，没有发现问题。

此时团队里富有经验的大佬看到了一个我从来没有想到的排查角度：这个key在日志打印中总是出现在第26位，难道是和扩容有关？ 排查自此，问题逐渐明朗。

问题根因和分析

一句话结论：当天投放计划因大促临近运营调整正好达到了特定数量触发代码bug，1次请求产生了2次下游调用，下游流量增长1倍，同时投放量因1天1次的疲劳度限制，拦截增加，业务投放量下降30%。

重复的key为什么固定出现在26位

context作为一个线程安全的公共存储，并发写入的情况下，key的位置不太可能固定，固定在26位肯定是有特殊条件。默认配置下，HashMap的第二次扩容时机是32✖0.75+1=25，合理怀疑在computeIfAbsent执行的回调方法中刚好触发了扩容，而在回调中扩容会导致不可预期的行为，比如key即使重复了也仍然执行插入，并放在扩容后的第26位上，类似这个bug的描述：https://bugs.java.com/bugdatabase/view_bug?bug_id=8071667

回到代码，问题表现为：

context.computeIfAbsent("key", k -> { 
	result = 调用下游的result();
	context.computeIfAbsent("abc", "def"); // 回调里面执行了插入
	context.computeIfAbsent("efg", "hij");
});

为什么computeIfAbsent中触发扩容，会导致key重复仍然执行插入

分析JDK8中的HashMap的computeIfAbsent代码：

public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
    ……

    // 临时变量保存tab
    Node<K,V>[] tab; 

    // 如果未达到扩容条件，就会执行第二个条件项：将当前table赋值给临时变量tab
    if (size > threshold || (tab = table) == null || (n = tab.length) == 0) 
    	// 如果达到扩容条件，就会执行扩容
        n = (tab = resize()).length;

    // 如果已经存在，返回旧值
    if ((first = tab[i = (n - 1) & hash]) != null) {
        ……
    }

    // 否则执行回调方法
    V v = mappingFunction.apply(key);


    if (v == null) {
        ……
    } else if (old != null) {
        ……
    }
    else if (t != null)
        ……
    else {
    	// 将新值插入临时变量tab，这里newNode会调用LinkedHashMap子类实现
        tab[i] = newNode(hash, key, v, first);
        ……
    }
    ++size;
    ……
    return v;
}

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    ……    
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    ……
    // 扩容后的table已经是一个新数组了
    return newTab;
}

那么流程也就是这样的：

• 执行外层computeIfAbsent0，未达到扩容条件，tab=tableA，此时触发回调方法
• 回调方法里继续执行computeIfAbsent1，未达到扩容条件，但插入后++size刚好达到了扩容条件
• 回调方法里继续执行computeIfAbsent2，达到扩容条件，触发resize，tableA被替换为tableB
• 回溯到外层computeIfAbsent0，此时tab仍然是tableA，数据被插入到旧数组tableA中

在外面看来，数据没有放进去，但size正常增加。这就导致第一个线程调用下游后并没有保存成功，第二个线程重复发起调用。

这个bug在JDK17的computeIfAbsent已经做了防御性编程：

// JDK 17
int mc = modCount;
V v = mappingFunction.apply(key);
// 如果发现apply回调方法中有修改，则直接报异常
if (mc != modCount) { throw new ConcurrentModificationException(); }

为什么日志打印时，仍然能打印扩容前数组中的元素

因为使用的是LinkedHashMap。LinkedHashMap是在HashMap基础上，用双向链表保留了插入顺序（或者访问顺序）。所以只要成功执行了newNode方法，都会被记录下来。而打印日志会迭代遍历这个双向链表，只要在双向链表上的Node，都会被打印出来。

所以重复key的Node虽然在日志中存在，在LinkedHashMap双向链表中存在，但是在HashMap最新的table中并不存在。

如果用ConcurrentHashMap，能避免这个问题吗？

也不行，JDK8的ConcurrentHashMap如果在computeIfAbsent中重复调用computeIfAbsent，会导致死循环卡死线程。在JDK8的方法注释中明确规定不要在回调里修改数据：

Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

当然，这个问题也在JDK17被防御性编程了：

// JDK 17
if (pred.next != null)
	throw new IllegalStateException("Recursive update");
if (f instanceof ReservationNode)
	throw new IllegalStateException("Recursive update");

为什么之前没有触发这个bug？

之前刚上线这个平台，投放计划很少，当然不会触发。因当天大促临近，运营修改了大量投放计划，投放计划发生了上下线导致context在调用这个下游时刚好达到24个元素。这个条件还是比较苛刻。在预发偶现，也正是因为近期迭代的功能增多，预发测试用的投放计划增多。

为什么会犯这种错误

印象里有这样一条开发经验：Map、List的computeIfAbsent、foreach等方法回调中，不要再次对元素进行修改，会产生非预期的行为。

但是实际开发中很难完全发现这样的问题，因为：

1. 工具类或者内部方法屏蔽了细节，但又做得不够完善。比如这次的真实场景是产品新需求：加入跟踪和点击埋点。因此在context里面写了computeIfAbsent方法，屏蔽掉LinkedHashMap数据结构的信息，因此也就看不出这个问题。

   context.computeIfAbsent("key", k -> { 
   	// ……
   	context.setTrackInfo("abc", "def");
   	context.setClickInfo("efg", "hij");
   });

2. 产品需求的间隔时间太长，忘记外层写了什么。通常方法体太长的时候，会新建方法来写，比如：

   context.computeIfAbsent("key", k -> dosomething(k) );
   
   public Object dosomething(String key) {
      // ……
   	context.setTrackInfo("abc", "def");
   	context.setClickInfo("efg", "hij");
   }

   当这样写的时候，你还记得外层嵌套了多少层、什么样的代码吗？只会关注dosomething内部的逻辑了吧？

解决方案

1. 止血方案：将LinkedHashMap的初始容量改为64，避免扩容，快速修复问题。
2. 临时方案：弃用默认的computeIfAbsent方法，所有的地方都改为自己实现的getOrLoadData，通过强锁来控制并发：

   public <V> V getOrLoadData(String key, Supplier<V> loader) {
   	synchronized (data) {
   		V v;
   		if ((v = (V) data.get(key)) == null) {
   			V newValue;
   			if ((newValue = loader.get()) != null) {
   				if ((v = (V) data.putIfAbsent(key, newValue)) == null) {
   					return newValue;
   				}
   			}
   		}
   		return v;
   	}
   }

3. 永久方案：升级JDK17，正好集团在推进升级JDK17。如果写出重复调用的业务代码，会被底层防御性编程的代码抛出异常。

暴露问题和优化Action

• 部分实时数据涨跌没有监控告警，没能在0点或者早上上班时发现问题，需要增加xxxxx监控告警
• 加强CR

总之，如果这样的技术问题逐渐积累，PD和运营就会认为你能力不行，从而对你失去信任。还是需要多积累生产经验避免踩坑。另外，即使看到了重复的key，也很难有排查思路，大佬能一眼看出26这个数字和扩容有关，真的很佩服。