在Scala中包装不可变集合和维护线程安全？ [英] Wrapping an immutable collection and maintaining thread-safety in Scala?

问题描述

我是新的并发问题，所以没有我。我想创建一个线程安全的容器，使用Scala Map作为后备存储。不是将用户暴露给底层Map，我宁愿只公开其方法的子集。

示例可能如下所示：

  MyContainer [A] {
 
 def add（thing：A）：Unit = {
 backingStore = backingStore +（thing.uuid  - > thing）
} 
 
 def filter（p：A => Boolean）：Option [Iterable [A]] = {
 val filteredThings = backingStore.values.filter（p）
 if（filteredThings.isEmpty）没有其他一些（filteredThings）
} 
 
 def remove（uuid：UUID）：Option [A] = backingStore.get（uuid）match {
 case optionalThing @ Some ）=> 
 backingStore = backingStore  -  uuid; optionalThing 
 case无=>无
} 
 
 @ volatile private [this] var backingStore = immutable.HashMap.empty [UUID，A] 
 
} 
  

...我怀疑即使底层的后备存储是不可变的，它的引用 volatile ，容器不是线程安全的。

假设我有两个独立的线程，可以访问上述容器的一个实例。线程1过滤基础集合并获得一些结果;同时线程2删除一个项目。线程1的结果可能包含对线程2删除的项目的引用？可能还有其他问题。

我是否纠正上述实现不是线程安全？使用Scala使上述线程安全的最常用的方法是什么？

编辑：我希望尽可能避免屏蔽和同步。如果必须使用阻塞/同步，那么是否需要volatile参考？不可变的集合的要点是什么？

解决方案

您使用的是写时复制的方法，所以您的并发读写的问题是它们不是严格排序的，但这不是一个问题：这只是一个时序问题，如果A正在写，而B正在读，则不能保证A是否将看到B的编辑。 / p>

你真正的问题是当你同时写C和D：然后他们可以读取相同的开始地图，更新自己的副本，然后只写自己的编辑。

考虑一个包含（A，B）的起始映射，线程C和D分别添加条目'C'和'D' ，而线程E和F读取映射;所有这一切同时发生。一个可能的例子是：

C读取地图（A，B）

D读取地图（A，B）

C写map（A，B，C）

E读取映射（A，B，C）

D写映射（A，B，D）

F读取地图（A，B，D）

C条目出现了trnasiently，然后永远丢失。

可靠地对写操作进行排序的唯一方法是确保不会同时输入。要么使用同步锁定nforce单个条目写入块或确保它通过使用单个Akka actor进行序列化以执行更新。

如果您需要，还需要同步读取关于读取与写入的顺序，但是如果你有多个线程访问这个，这不太可能是一个真正的问题。

I am new to concurrency issues so bare with me. I want to create a thread-safe container that uses a Scala Map as a backing store. Rather than expose the user to the underlying Map, I would rather only expose a subset of its methods.

Example might look something like the following...

class MyContainer[A] {

  def add(thing: A): Unit = {
    backingStore = backingStore + (thing.uuid -> thing)
  }

  def filter(p: A => Boolean): Option[Iterable[A]] = {
    val filteredThings = backingStore.values.filter(p)
    if (filteredThings.isEmpty) None else Some(filteredThings)
  }

  def remove(uuid: UUID): Option[A] = backingStore.get(uuid) match {
    case optionalThing @ Some(thing) =>
      backingStore = backingStore - uuid; optionalThing
    case None => None
  }

  @ volatile private[this] var backingStore = immutable.HashMap.empty[UUID, A]

}

...I suspect that even though the underlying backing store is immutable and its reference is volatile, the container is not thread-safe.

Suppose that I have two separate threads running with access to an instance of the above container. Thread 1 filters the underlying collection and gets some results; at the same time Thread 2 removes an item. The results that thread one has might contain a reference to the item that Thread 2 removed? There might be other problems.

Am I correct that the above implementation is not thread-safe? What would be the most idiomatic way to make the above thread-safe using Scala?

Edit: I would prefer to avoid blocking and synchronization if possible. If blocking/synchronization must be used then is the volatile reference needed? And what would be the point of the immutable collection? Couldn't I just as well use a mutable collection?

解决方案

You are using a copy-on-write approach, so your problem of a concurrent read and write is that they are not strictly ordered, but that's not really a problem: it's simply a timing issue in that if A is writing while B is reading there is no guarantee about whether A will see B's edits.

Your real problem is when you have C and D writing simultaneously: then they can both read the same starting map, update their own copies and then write only their own edits. Whoever writes first will have their changes overwritten.

Consider a starting map containing (A,B), and threads C and D adding entries 'C' and 'D' trespectively, while threads E anf F read the map; all this happenning concurrently. One possible reuslt is:

C reads map (A,B)
D reads map (A,B)
C writes map (A,B,C)
E reads map (A,B,C)
D writes map (A, B, D)
F reads map (A, B, D)

The 'C' entry appeared trnasiently and was then lost forever.

The only way to reliably sequence the writes is to ensure it is never entered concurrently. Either with a synchronize locke nforce single entry the write block or ensure it is serialised by using a single Akka actor to perform updates.

You need to synchronize reads also if you care about ordering of reads vs writes, but if you have multiple threads accessing this, that's unlikely to be a real concern.

这篇关于在Scala中包装不可变集合和维护线程安全？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！