不可变映射的无锁原子更新

Question

给定一个 Java俚语/Vavr immutable map，以及一个更新该映射的函数：

private Map<Foo, Bar> myMap = HashMap.empty();

public void setBar(Foo foo, Bar bar) {
  myMap = myMap.put(foo, bar);
}

我如何确保针对不同的 Foo 键对 setBar() 的两次并发调用都会记录它们的更新？

// thread A
setBar(fooA, barA)

// thread B
setBar(fooB, barB)

似乎存在这样的调用交错的风险：

线程 A 获得 {}
线程 B 获得 {}
线程 B 计算 {} + fooB -> barB = {(fooB -> barB)}
线程 B 将 myMap 设置为 {(fooB -> barB)}
线程 A 计算 {} + fooA -> barA = {(fooA -> barA)}
线程 A 将 myMap 设置为 {(fooA -> barA)}
线程 B 的更新丢失

使用 AtomicReference，我或多或少地基于 Java Concurrency in Practice 的“非阻塞算法”部分中的 ConcurrentStack 方法提出了以下方法。

private AtomicReference<Map<Foo, Bar>> myMap = 
  new AtomicReference<>(HashMap.empty());

public void setBar(Foo foo, Bar bar) {
  Map<Foo, Bar> myMap0;
  Map<Foo, Bar> myMap1;
  do {
    myMap0 = myMap.get();
    myMap1 = myMap0.put(foo, bar);
  } while (!myMap.compareAndSet(myMap0, myMap1));
}

这是正确的吗？如果是这样，它是不是像我可能得到的那样好，或者是否有更简单的东西（例如一些 Java 8 AtomicReference API 我错过了实现这个模式)?

Answer 1

在这种情况下使用 AtomicReference 比较好。可以使用快捷方式

public void setBar(Foo foo, Bar bar) {
    myMap.updateAndGet(map -> map.put(foo, bar)));
}

相反。参见javadoc for AtomicReference.updateAndGet。默认 java 实现与 Java 8.

中的完全相同

不可变映射的无锁原子更新

Lock-free atomic update to immutable Map

java

immutability

atomic

vavr