5

我需要编写一个缓存的特定实现，它具有唯一键但可以包含重复值，例如：

 "/path/to/one" -> 1
 "/path/to/two" -> 2
 "/path/to/vienas" -> 1
 "/path/to/du" -> 2

该类需要提供非阻塞读取/键查找，但也具有典型的创建/更新/删除突变器。例如，删除值2应该导致

"/path/to/one" -> 1
"/path/to/vienas" -> 1

到目前为止，此缓存的读取将超过写入，因此写入性能不是问题 - 只要并发写入不会在彼此之上运行。条目的总数很可能会少于 1000，因此偶尔迭代值仍然是可以承受的。

所以我写了这样的东西（伪代码）：

//
// tl;dr all writes are synchronized on a single lock and each
// resets the reference to the volatile immutable map after finishing
//
class CopyOnWriteCache {
   private volatile Map<K, V> readOnlyMap = ImmutableMap.of();

   private final Object writeLock = new Object();

   public void add(CacheEntry entry) {
      synchronized (writeLock) {
         readOnlyMap = new ImmutableMap.Builder<K, V>()
            .addAll(readOnlyMap)
            .add(entry.key, entry.value)
            .build();
      }
   }

   public void remove(CacheEntry entry) {
      synchronized (writeLock) {
         Map<K, V> filtered = Maps.filterValues(readOnlyMap, somePredicate(entry));
         readOnlyMap = ImmutableMap.copyOf(filtered);
      }
   }

   public void update(CacheEntry entry) {
      synchronized (writeLock) {
         Map<K, V> filtered = Maps.filterValues(readOnlyMap, somePredicate(entry));
         readOnlyMap = new ImmutableMap.Builder<K, V>()
             .addAll(filtered)
             .add(entry.key, entry.value)
             .build();
      }
   }

   public SomeValue lookup(K key) {
      return readOnlyMap.get(key);
   }
}

写完上面的内容后，我意识到ConcurrentHashMap它还提供了非阻塞读取，这将使我的所有努力都变得毫无意义，但是它的 Javadoc 中有一个声明引起了人们的注意：

iterators are designed to be used by only one thread at a time

因此，如果我替换 with 的使用volatile ImmutableMap并final ConcurrentHashMap删除所有synchronized块，竞争的并发突变器是否有可能相互失效？例如，我可以想象两个并发调用如何remove导致竞争条件，使第一个的结果完全无效remove。

我能看到的唯一改进是，通过使用final ConcurrentHashMap 和保持synchronized原样，我至少可以避免不必要的数据复制。

这有意义吗 - 或者我在这里忽略了一些东西？任何人都可以为此解决方案提出其他替代方案吗？

4

2 回答 2

5

如果您进行了此替换，您仍然只有一个线程同时使用给定的迭代器。该警告意味着两个线程不应使用相同的 Iterator 实例。并不是说两个线程不能同时迭代。

您将遇到的问题是，由于无法在 ConcurrentMap 的单个原子操作中完成删除操作，因此您可以让并发线程查看处于中间状态的映射：一个值已被删除，但另一个未删除。

我不确定这会更快，因为您说写入性能不是问题，但是您可以做些什么来避免在每次写入时复制映射，就是使用 ReadWriteLock 保护可变的 ConcurrentMap。所有读取仍然是并发的，但是对映射的写入会阻止所有其他线程访问映射。而且您不必在每次修改时都创建一个新副本。

于 2012-01-19T23:01:26.527 回答
2

ConcurrentHashMap可以同时通过多个迭代器/多个线程进行变异。只是您不应该将迭代器的单个实例交给多个线程并同时使用它。

So, if you use ConcurrentHashMap you don't need to leave synchronized in there. As JB Nizet notes, difference between this and your current implementation is the visibility of the intermediate state. If you don't care about that, using ConcurrentHashMap would be my preferred choice as the implementation is most simple and you won't have to worry about read or write performance.

于 2012-01-19T23:05:03.497 回答