In the course of developing our database we have come across surprising multithreaded behavior in Scala’s ConcurrentMap trait. Java and Scala provide a ConcurrentMap interface and trait, respectively. Both trait and interface define a number of atomic, or transactional, operations that help developers deal with concurrent modification of the map. The difference between the Scala trait and the Java interface is that the Scala trait inherits a number of operations that are not atomic.
In particular, Scala’s ConcurrentMap trait does not provide an atomic implementation of getOrElseUpdate. getOrElseUpdate lazily evaluates its second argument, allowing the user to forgo evaluation if the key already exists in the map. In a multithreaded environment, however, a highly contended map key is likely to cause multiple evaluations of the value. This is problematic behavior if the evaluation is resource intensive or has some side effects which should only occur once per key.
Your challenge is to provide an atomic implementation of getOrElseUpdate. It must guarantee that the value for any particular key will only get evaluated once, regardless of how many threads are contending for the same key. We have provided a github repo with a spec for the correct behavior of a ConcurrentMap. Fork this repo, provide a ConcurrentMap implementation that passes the spec, and send a repo link to challenge@boundary.com with the subject line “AtomicMap Challenge”. We will be publishing a breakdown and benchmark of the best implementations along with our own. Happy hacking!