Multi-threading in Scala -- dealing only with immutability

Question

I have the code of Scala

class MyClass {
  private val myData: Map[String, MyClass2] = new HashMap[String, MyClass2]()

  def someMethod = {
      synchronized(myData) {
        val id = getSomeId
        if (myData.containsKey(id)) myData = myData.remove(id)
        else Log.d("123", "Not found!")
      }
  }

  def getSomeId = //....
}

I wonder, is it possible to remain this code thread-safe without using synchronized and without involving some other libraries such Akka or any other libraries (classes) even built-in in Java or Scala?

Ideally, I'd like to make thread-safe only by using the conception of immutability (final in Java, if you will).

UPDATE:

class MyClass(myData: Map[String, MyClass2] = new HashMap[String, MyClass2]()) {

  def someMethod = {
      synchronized(myData) {
        val id = getSomeId
        if (myData.containsKey(id)) new MyClass(myData.remove(id))
        else {
           Log.d("123", "Not found!")
           this
         }
      }
  }

  def getSomeId = //....
}

Answer 1

You can solve the problem with immutability only if you make MyClass immutable too (and let it use only immutable data structures as well). The reason is simple: If MyClass is mutable, then you have to synchronize modifications by concurrent threads.

This requires a different design - every operation that causes an instance of MyClass to "change" will instead return a (possibly) modified instance.

import collection.immutable._

class MyClass2 {
  // ...
}

// We can make the default constructor private, if we want to manage the
// map ourselves instead of allowing users to pass arbitrary maps
// (depends on your use case):
class MyClass private (val myData: Map[String,MyClass2]) {
  // A public constructor:
  def this() = this(new HashMap[String,MyClass2]())

  def someMethod(id: String): MyClass = {
    if (myData.contains(id))
      new MyClass(myData - id) // create a new, updated instance
    else {
      println("Not found: " + id)
      this // no modification, we can return the current
            // unmodified instance
    }
  }

  // other methods for adding something to the map
  // ...
}

Answer 2

If you use a TrieMap from scala 2.10, which is a lock free and concurrent map implementation, you can avoid synchronizing:

import scala.collection.concurrent.TrieMap

class MyClass2

class MyClass {
    private val myData = TrieMap[String, MyClass2]()
    def someMethod = myData -= getSomeId
    def getSomeId = "id"
}

Answer 3

I would recommend using a library, because getting concurrency right on your own is hard. You could for example use a concurrent map like TrieMap. See the answer above.

But let's assume that you want to do this manually for educational purposes. The first step to make the above thread-safe would be to use an immutable collection. So instead of

private val myData: Map[String, MyClass2] = new HashMap[String, MyClass2]()

you would use

private var myData = Map.empty[String, MyClass2] 

(Even though there is a var here, this has less mutable state than the version above. In this case the only mutable thing is a single reference, whereas in the example above the entire collection is mutable)

Now you have to deal with the var. You have to make sure that an update to the var on one thread is "seen" on all other threads. So you have to mark the field as @volatile. That would be enough if you have a publish/subscribe scenario where writes are only done from one thread. But assuming that you want to both read and write from different threads, you will need to use synchronized for all write accesses.

Clearly, this is enough complexity to warrant introducing a little helper class:

final class SyncronizedRef[T](initial:T) {
  @volatile private var current = initial

  def get:T = current

  def update(f:T=>T) {
    this synchronized {
      current = f(current)
    }
  }
}

With this little helper, the code from above can be implemented like this:

class MyClass {
  val state = new SyncronizedRef(Map.empty[String, MyClass2])

  def someMethod = {
    state.update(myData =>
      val id = getSomeId
      if (myData.containsKey(id)) 
        myData - id
      else { 
        Log.d("123", "Not found!")
        myData
      }
  }

  def getSomeId = //....
}

This would be thread-safe as far as the map is concerned. However, whether the whole thing is threadsafe depends on whatever happens in getSomeID.

In general, this way of dealing with concurrency will work as long as the thing passed to update is a pure function that just transforms the data without having any side effects. If your state is more complex than a single map, it can be quite challenging to write your updates in a purely functional style.

There are still low level multithreading primitives in the SynchronizedRef, but the logic of your program is completely free of them. You just describe how the state of your program changes in response to external input by composing pure functions.

In any case, the best solution for this particular example is just to use an existing concurrent map implementation.

Answer 4

Whenever you share mutable state, you need a concurrency mechanism. As Rüdiger points out, the best is to identify which kind of concurrency scenario you have, and then use an existing tool that best addresses that scenario:

• plain old Java synchronized locks
• atomic compare-and-swap
• software transactional memory (e.g. Scala-STM)
• message-passing / actors

Or of course, you could use cooperative multitasking (run concurrent processes on a single shared thread), if you don't need highest possible performance.

If the state of your class is overseeable, you can make that class completely immutable, e.g.:

case class MyClass2()

case class MyClass(myData: Map[String, MyClass2] = Map.empty) {
  def someMethod = {
    val id = getSomeId
    if (myData.contains(id)) copy(myData = myData - id)
    else throw new IllegalArgumentException(s"Key $id not found")
  }

  def getSomeId = "foo" // ...
}

An instance of MyClass is only mutated by copying the data to a new instance, so multiple threads can safely refer to the same instance. But on the other hand, if two threads A and B start off with the same instance foo1, and either of them mutates it and wants that mutation to be seen by the other thread, then you need to share that mutated state again in some form (use an STM ref cell, send a message via an actor, store it in a synchronized variable etc.)

val foo1 = MyClass(Map("foo" -> MyClass2()))
val foo2 = foo1.someMethod  // foo1 is untouched