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

volatile ImmutableMapの使用法をwithに置き換えてfinal ConcurrentHashMapすべてのブロックを削除するとsynchronized、競合する同時ミューテーターが互いに無効になる可能性はありますか? たとえば、 の 2 つの同時呼び出しがremove競合状態につながり、最初の の結果が完全に無効になることを想像できremoveます。

私が見ることができる唯一の改善点は、使用してfinal ConcurrentHashMap そのままsynchronizedにしておくことで、少なくともデータの不要なコピーを回避できることです。

それは理にかなっていますか? それとも、ここで何かを見落としているのでしょうか? このソリューションの他の代替案を提案できる人はいますか?

4

2 に答える 2

5

この置換を行った場合でも、指定された Iterator を一度に使用するスレッドは 1 つだけになります。この警告は、2 つのスレッドが同じ Iterator インスタンスを使用してはならないことを意味します。2 つのスレッドが同時に反復できないわけではありません。

問題は、ConcurrentMap の単一のアトミック操作で削除操作を実行できないため、並行スレッドに中間状態のマップを表示させる可能性があることです。一方の値は削除されましたが、もう一方の値は削除されていません。

書き込みパフォーマンスは問題ではないとおっしゃっていますが、書き込みのたびにマップのコピーを回避するためにできることは、変更可能な ConcurrentMap を保護する ReadWriteLock を使用することです。すべての読み取りは引き続き並行処理されますが、マップへの書き込みにより、他のすべてのスレッドがマップにアクセスできなくなります。また、変更のたびに新しいコピーを作成する必要はありません。

于 2012-01-19T23:01:26.527 に答える
2

ConcurrentHashMap複数の反復子/複数のスレッドを同時に変更しても問題ありません。iterator の単一のインスタンスを複数のスレッドに渡して同時に使用することは想定されていないというだけです。

したがって、使用するConcurrentHashMap場合はそこに残す必要はありませんsynchronized。JB Nizet が指摘しているように、これと現在の実装の違いは、中間状態の可視性です。それを気にしない場合はConcurrentHashMap、実装が最も単純で、読み取りまたは書き込みのパフォーマンスを心配する必要がないため、使用することをお勧めします。

于 2012-01-19T23:05:03.497 に答える