HashBiMap被屏蔽

Question

我们在我们的应用程序中使用HashBiMap，我们是这样创建的。

HashBiMap<String, String> map = HashBiMap.create();

我们有guava-26.0-jre版本的guava。

最近发现我们的应用程序被挂起，无法处理任何其他请求。我做了一个线程转储，发现有这样的情况

Thread.State: RUNNABLE
native=false, suspended=false, blockCount=1, waitCount=4, cpu=9h, 12m, 45s, 434ms, user=9h, 10m, 59s, 990ms
    com.google.common.collect.HashBiMap.seekByKey(HashBiMap.java:223)
    com.google.common.collect.HashBiMap.get(HashBiMap.java:254)

Thread.State: RUNNABLE
native=false, suspended=false, blockCount=1, waitCount=6, cpu=9h, 11m, 49s, 453ms, user=9h, 10m, 3s, 760ms
    com.google.common.collect.HashBiMap.seekByKey(HashBiMap.java:223)
    com.google.common.collect.HashBiMap.get(HashBiMap.java:254)

Thread.State: RUNNABLE
native=false, suspended=false, blockCount=274, waitCount=6615, cpu=22h, 31m, 29s, 966ms, user=22h, 27m, 30s, 540ms
    com.google.common.collect.HashBiMap.seekByKey(HashBiMap.java:223)
    com.google.common.collect.HashBiMap.get(HashBiMap.java:254)

Thread.State: RUNNABLE
native=false, suspended=false, blockCount=91, waitCount=2443, cpu=22h, 29m, 51s, 541ms, user=22h, 25m, 54s, 140ms
    com.google.common.collect.HashBiMap.seekByKey(HashBiMap.java:223)
    com.google.common.collect.HashBiMap.get(HashBiMap.java:254)

像上面这样的线程还有好几条，在呼叫获取时被屏蔽了，但等待时间最长的是这个，cpu=22h，31m，29s，966ms。

Thread.State: RUNNABLE
native=false, suspended=false, blockCount=3, waitCount=32, cpu=5h, 46m, 7s, 733ms, user=5h, 45m, 500ms
    com.google.common.collect.HashBiMap.seekByValue(HashBiMap.java:234)
    com.google.common.collect.HashBiMap.put(HashBiMap.java:274)
    com.google.common.collect.HashBiMap.forcePut(HashBiMap.java:301)

只有一个线程像上面一样在等待forcePut。

有什么原因导致HashBiMap.get会进入一个循环来寻找一个键的值，并且永远不会返回。

Answer 1

TL;DR

正如建议的 Xaerxess使用 地图#synchronizedBiMap 以防地图被多个线程访问。你永远不知道当有多个线程的时候会发生什么。

如果有人对发生的事情感到好奇，请看以下内容

为什么HashBiMap.get会进入一个循环来寻找一个键的值，并且永远不会返回。

---

这是一个有趣的例子，说明多线程如何产生 "意外 "的结果。让我们来看看这一行 HashBiMap.java:223 的方法 seekByKey

private BiEntry<K, V> seekByKey(@Nullable Object key, int keyHash) {
  for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask];
      entry != null;
      entry = entry.nextInKToVBucket) {
    if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) {
      return entry;
    }
  }
  return null;
}

而第223行是

      entry = entry.nextInKToVBucket) {

这条线的阻塞意味着有一个无限的循环，这是由于循环引用的 entry 和 entry.nextInKToVBucket.

其中一种可能的情况是： 在 put 方法。

private V put(@Nullable K key, @Nullable V value, boolean force) {
  ...

  BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash);
  if (oldEntryForKey != null) {
    ...
  } else {
    insert(newEntry, null);
    rehashIfNecessary();
    return null;
  }
}

假设不幸的是，在两个线程中同时出现了两个相同键和值的调用，创建了两个新的条目A和B。insert 方法。

private void insert(BiEntry<K, V> entry, @Nullable BiEntry<K, V> oldEntryForKey) {
  int keyBucket = entry.keyHash & mask; // 1
  entry.nextInKToVBucket = hashTableKToV[keyBucket]; // Step 2
  hashTableKToV[keyBucket] = entry; // 3
  ...
}

假设A先完成。hashTableKToV[keyBucket] = A, A.nextInKToVBucket = null.当B来时，并完成步骤2。B.nextInKToVBucket = 假设在执行步骤3之前，A的线程正在执行 rehashIfNecessary，可惜需要重来。

private void rehashIfNecessary() {
  BiEntry<K, V>[] oldKToV = hashTableKToV;
  if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
    int newTableSize = oldKToV.length * 2;

    this.hashTableKToV = createTable(newTableSize);  // Step 4
    ...

    for (BiEntry<K, V> entry = firstInKeyInsertionOrder; 
        entry != null;
        entry = entry.nextInKeyInsertionOrder) {
      insert(entry, entry); // step 5
    }
    ...
  }
}

当第四步完成后。hashTableKToV 被清除了。不幸的是，B线程在此刻执行了第3步，并且...。hashTableKToV[keyBucket] = A的线程继续进行第5步，再次插入A，并且 A.nextInKToVBucket =A后的步骤2，造成循环参考。因此无限循环中 seekByKey.

下面是一个如何重现上述情况的例子（不是100%，可能需要尝试几次）。

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;

public class HashBiMapConcurrentTest {
    public static void main(String[] args) throws InterruptedException {
        BiMap<String, String> biMap = HashBiMap.create();
        ExecutorService executors = Executors.newFixedThreadPool(4);
        Collection<Callable<Integer>> tasks = new ArrayList<>();
        Callable<Integer> task = () -> {
            for (int i = 0; i < 1000; i++) {
                biMap.put("A" + i, "B" + i);
                biMap.get("A" + i);
            }
            System.out.println("Done");
            return 0;
        };
        tasks.add(task);
        tasks.add(task);
        List<Future<Integer>> futures = executors.invokeAll(tasks);
        for (Future<Integer> future : futures) {
            while (!future.isDone()) {
                Thread.sleep(10);
            }
        }
        executors.shutdown();
    }
}