Java中的线程安全Map

Question

我理解多线程和同步的概念，但对于编写线程安全的代码还不熟悉。我现在有以下代码片段：

synchronized(compiledStylesheets) {
    if(compiledStylesheets.containsKey(xslt)) {
        exec = compiledStylesheets.get(xslt);
    } else {
        exec = compile(s, imports);
        compiledStylesheets.put(xslt, exec);
    }
}

compiledStylesheets 是一个私有、终态的 HashMap。我有几个问题。

compile() 方法返回需要几百毫秒，这看起来很长，但我没有看到其他的替代方案。此外，在 synchronized 块中使用 Collections.synchronizedMap 是不必要的，对吗？除了初始化/实例化之外，这是唯一使用该对象的代码。

另外，我知道存在一种 ConcurrentHashMap，但我不知道是否有点大材小用。在这种情况下，putIfAbsent() 方法将无法使用，因为它不能跳过 compile() 方法调用。我也不知道它是否会解决“在 containsKey() 之后但在 put() 之前被修改”的问题，或者在这种情况下是否真的是一个问题。

编辑：拼写错误

- Derek

---

使用exec语句将键添加到队列中，然后定期执行队列中的某些进程怎么样？这样可以保证“安全”，并且不会多次添加相同的键。 - Marshall Tigerus

什么是XSLT？你可以锁定它。你可以使用“键锁定”缓存方法。或者使用ConcurrentHashMap。 - Boris the Spider

@MarshallTigerus 我认为操作者需要从该方法中return exec。 - assylias

对于这种任务，我强烈推荐使用Guava缓存支持。 - erickson

@assylias - 这不是你非常好的多例模式的变体吗？ - OldCurmudgeon

Answer 1

对于这种任务，我强烈推荐使用Guava缓存支持。如果您无法使用该库，则可以使用Multiton的紧凑实现。在此实现中，FutureTask的使用是从assylias通过OldCurmudgeon的提示得来的。

public abstract class Cache<K, V>
{

  private final ConcurrentMap<K, Future<V>> cache = new ConcurrentHashMap<>();

  public final V get(K key)
    throws InterruptedException, ExecutionException
  {
    Future<V> ref = cache.get(key);
    if (ref == null) {
      FutureTask<V> task = new FutureTask<>(new Factory(key));
      ref = cache.putIfAbsent(key, task);
      if (ref == null) {
        task.run();
        ref = task;
      }
    }
    return ref.get();
  }

  protected abstract V create(K key)
    throws Exception;

  private final class Factory
    implements Callable<V>
  {

    private final K key;

    Factory(K key)
    {
      this.key = key;
    }

    @Override
    public V call()
      throws Exception
    {
      return create(key);
    }

  }

}

- erickson

Answer 2

我认为你正在寻找一个多例模式。

这里有一个非常好的Java实现链接, @assylas在一段时间前发布过。

- OldCurmudgeon

---

链接的答案在使用ConcurrentHashMap时有两种不同的方式，具体取决于是否使用JDK8。这两种方式都非常干净、高效且无竞争条件。 - Peter G

是的，这是我想出来的解决方案，但我使用的是CountDownLatch而不是FutureTask。像这样做是正确的方法。 - erickson

@erickson - 我喜欢 FutureTask 的优雅。 - OldCurmudgeon

是的，FutureTask 很好，我只是忘记它们可以满足我的需求了。 - erickson

Answer 3

您可以冒着偶尔发生的竞态条件下双重编译样式表的风险来放松锁定。

Object y;

// lock here if needed
y = map.get(x);
if(y == null) {
    y = compileNewY();

    // lock here if needed
    map.put(x, y); // this may happen twice, if put is t.s. one will be ignored
    y = map.get(x); // essential because other thread's y may have been put
}

这需要get和put是原子的，这在ConcurrentHashMap中是正确的，您可以通过在类中包装单个调用get和put来实现。 （正如我试图用“如果需要，请在此处锁定”注释来解释的那样-重点是您只需要包装单个调用，而不是有一个大锁）。

即使对于ConcurrentHashMap（和putIfAbsent），这仍然是一种标准的线程安全模式，以最小化编译两次的成本。它仍然需要接受有时需要编译两次，但即使昂贵也应该没问题。

顺便说一下，您可以解决该问题。通常上述模式不与像compileNewY这样的重型函数一起使用，而是与轻量级构造函数new Y()一起使用。例如：

class PrecompiledY {
    public volatile Y y;
    private final AtomicBoolean compiled = new AtomicBoolean(false);
    public void compile() {
        if(!compiled.getAndSet(true)) {
            y = compile();
        }
    }
}
// ...
ConcurrentMap<X, PrecompiledY> myMap; // alternatively use proper locking

py = map.get(x);
if(py == null) {
    py = new PrecompiledY(); // much cheaper than compiling

    map.put(x, y); // this may happen twice, if put is t.s. one will be ignored
    y = map.get(x); // essential because other thread's y may have been put
    y.compile(); // object that didn't get inserted never gets compiled
}

还有：

另外，我知道存在ConcurrentHashMap，但我不知道那是否过度。

考虑到你的代码需要大量锁定，使用ConcurrentHashMap几乎肯定会更快，所以这并不过度。（而且更可能是无漏洞的。并发漏洞非常棘手。）

- djechlin

---

我无法理解其中的某些部分。您能否请澄清“如果需要，在此处锁定”注释？何时需要锁定？此外，这段代码是否不允许多个线程编译？那不是浪费资源吗？ - Miserable Variable

只要 get 和 put 是线程安全的，这个算法就是线程安全的。它不需要在访问 map 时进行任何锁定。 - djechlin

@MiserableVariable，请看我的编辑，了解如何解决编译浪费的问题。 - djechlin

如果地图不是“ConcurrentMap”（或以类似方式使用内存屏障的东西），那么这将会出问题。 - erickson

@erickson，我在回答和评论中解释得不好，算法只假设put和get是原子操作，这可以通过将它们包装在锁中或使用常见的ConcurrentMap实现来实现。还有其他问题吗？ - djechlin

我在谈论第二个例子。它没有解释 map 必须是 ConcurrentMap。 - erickson

Answer 4

请查看 Erickson 在下面的 评论。使用带有哈希映射的双重检查锁定并不明智。

编译方法可能需要几百毫秒才能返回。这似乎是一个很长的时间来锁定对象，但我没有看到其他选择。

您可以使用双重检查锁定，并注意在 get 之前不需要任何锁定，因为您从未从映射中删除任何内容。

if(compiledStylesheets.containsKey(xslt)) {
    exec = compiledStylesheets.get(xslt);
} else {
    synchronized(compiledStylesheets) {
        if(compiledStylesheets.containsKey(xslt)) {
            // another thread might have created it while
            // this thread was waiting for lock
            exec = compiledStylesheets.get(xslt);
        } else {
            exec = compile(s, imports);
            compiledStylesheets.put(xslt, exec);
        }
    }
}

}

另外，在同步块中使用Collections.synchronizedMap是不必要的，对吗？

正确。

除了初始化/实例化之外，这是唯一访问该对象的代码。

- Miserable Variable

---

我曾犹豫是否要两次调用containsKey，但我想在HashMap上它应该非常快... - Derek

这很糟糕。你不能将线程安全的双重检查锁定习惯用法扩展到HashMap上。简单地在可能异步修改的HashMap上调用get（）可能会在重新散列时造成非原子性或顺序不当的可见修改引起错误。 - erickson

最好调用两次而不是锁定它；这是一个很少写入但经常读取的场景。 - Miserable Variable

@erickson 我之前没有考虑过重新散列。现在我又在想双重检查锁定的价值，因为我自己主要用它来管理这些映射。你知道未加锁的 get 是否会抛出异常或返回错误结果吗？由于第二个 get 是有保护的，所以我想知道是否安全（即使很丑陋）忽略第一次调用中的错误。 - Miserable Variable

不加保护的 get() 是否会抛出异常取决于具体实现，而导致问题的条件也随着年代的变迁而有所不同。在某些版本中，曾经报告过可能会发生无限循环，因此您甚至无法忽略异常。Java 内存模型提供了更好的解决方案，既高效又保证正确性。 - erickson

Answer 5

首先，按照您发布的代码，它是没有竞态条件的，因为containsKey()方法的结果在compile()方法执行期间不会改变。

Collections.synchronizedMap()在您的情况下是无用的，因为它将所有映射方法包装成一个使用this作为互斥体或另一个由您提供的对象（对于两个参数版本）的synchronized块。

我认为使用ConcurrentHashMap也不是一个选项，因为它基于键hashCode()的结果分带锁；它的并发迭代器在这里也是无用的。

如果您真的想要在synchronized块之外调用compile()，则可以在检查containsKey()之前预计算它。这可能会降低整体性能，但可能比在synchronized块中调用更好。为了做出决策，我个人会考虑“未命中”关键字发生的频率，因此，哪个选项更合适-保持锁定时间更长还是总是计算您的内容。

- Alexey Malev