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)

还有其他几个类似上面的线程在调用 get 时被阻塞，但等待时间最长的是 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 会进入一个循环来查找键的值而不是 returns。

Answer 1

TL;DR

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

对于对发生的事情感到好奇的人

Would there be any reason for why HashBiMap.get would go into a loop to find the value for a key and never returns.

这是一个关于多线程如何创建 "unexpected" 结果的有趣示例。
让我们看一下 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来了，完成了Step 2，B.nextInKToVBucket = A。假设在执行Step 3之前，A的Thread正在执行rehashIfNecessary，不幸的是需要rehash。

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
    }
    ...
  }
}

当第 4 步完成时，hashTableKToV 被清除。不幸的是此时B的Thread执行了step 3，hashTableKToV[keyBucket] = B。A的thread继续step 5，再次插入A，在step 2之后A.nextInKToVBucket = A，导致a循环引用。因此 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();
    }
}

HashBiMap 被阻止

HashBiMap get getting blocked

java

guava

TL;DR

对于对发生的事情感到好奇的人