As an exercise, I was trying to implement a memoization of single parameter functions with a bounded cache size; a very simple approach with a First In First Out strategy but with a good concurrent behaviour. It's probably not perfect, let me know what you think of it.

Memoizer.md

#Bounded Memoizer

As an exercise, I was trying to implement a memoization of single parameter functions with a bounded cache size; a very simple approach with a First In First Out strategy. It's probably not perfect, let me know what you think of it.

The specs are that the memoizer should be concurrent and kick out the "oldest" computation. For instance, with a maximum size of 2 slots in the cache:

  foo(0) //computes and cache the result for 0
  foo(1) //computes and cache the result for 1
  foo(0) // returns the cached result
  foo(2) // computes and cache the result for 2 and kicks out the result for 0)
  foo(1) // still from cache
  foo(2) // from cache
  foo(0) // recompute and cache and kicks out the result for 1 

#Bounded size Map

The memoizer is backed by a sized map. The point was to have a map that is good with concurency (can be used by multiple threads) and still has a good throughput.

This is a very basic implementation of a bounded map-like object that uses AtomicReference to implement a Compare-And-Set (CAS) approach for a lock-free implementation.

We use a LinkedHashMap to keep track of the order of insertion in the Map.

According to the doc:

"The iterator and all traversal methods of this class visit elements in the order they were inserted."

When the LinkedHashMap runs over the specified size, we just drop the first element to get back under the bound.

However, as we need to allow concurrent access, we need some way to synchronize the read/write on the map. Instead of using synchronize or a read/write lock, we prefer the Compare-and-Set approach as it usually has a better throughput.

We keep an atomic reference to the "latest" version of the map, which can be changed atomically. While LinkedHashMap is a mutable class, we use it as an immutable map as we create clones before performing the operations (to simplify the CAS operations).

Reads are straightforward as we just read straight out of the kept reference, there might be misses as another thread might be trying to update the reference for the value we want to read but we won't see it.

Writes are not locking, but if there is a lot of contention, they might wait an indefinite amount of time to succeed. An optional approximative maximum duration to wait for can be specified.

A write works in the following manner:

• we create a copy of the current map contained in the AtomicReference and add the new item to it
• if the size of the copy+new element is over the bound, we drop the first element of the map
• we try to replace the pointer in the AtomicReference to the new map with a CAS operation, if the AtomicReference doesn't point to the same map as the one we copied in the first step, we have to start again

This is a simple approach that guarantees no locks and has a good throughput, it should also scale linearly.

##Issues

However, because we have to create a copy of the map at every CAS operation, if the size of the map is big, it might be expensive, in particular if there is a lot of contention and the CAS operation has to be repeated.

To avoid spending too much time in setting the cache, we can specify an optional maximum wait for the write to happen. When we are using this as a cache there is no point in spending more time waiting than it would take to compute the value.

##Alternative solution

A more efficient approach might use a Map backed by a Concurrent Trie, where the write operations are not waiting on the whole Map but only on specific nodes of the trie. The set operation will be less prone to contention and copies will be cheaper. Scala provides a lock-free concurrent Trie Map that could be used for backing the cache. However as it's not fully integrated with an ordered list to keep track of the insertion order, the implementation would be more involved.

Memoizer.scala

import scala.concurrent.duration.FiniteDuration

/**
 * A map-like object (with only the most basic functions implemented) that is thread safe but doesn't is not locking. 
 * The size of the map is limited to a maximum bound and the "oldest" entries are thrown out.
 */
class LockFreeBoundedCache[K, E](maxSize: Int) {

  import java.util.concurrent.atomic.AtomicReference
  import scala.collection.mutable.LinkedHashMap
  import scala.annotation.tailrec

  //the AtomicReference that is keeping track of the LinkedHashMap pointer
  private val cache: AtomicReference[LinkedHashMap[K, E]] = new AtomicReference(new LinkedHashMap())

  /**
   * get the stored value for a particular key. Returns None if the key is not in the map.
   */
  def get(key: K): Option[E] = cache.get.get(key) //basic debug: .map { k => println(s"from cache $key"); k }

  /**
   * put a new element in the map and make sure we do not run over the bound. This operation might take an indefinite amount of time if there
   * is a large amount of contention. 
   * To avoid waiting indefinitely on the put, you can specify a maximum duration to wait for and fail the put if we had to wait too much.
   * Returns true if the put was successful, false if we were not able to put the new value within the given time.
   */
  def put(key: K, elt: E, maxWait: Option[FiniteDuration] = None): Boolean = {
    //start counting until the maxWait
    val deadline = maxWait.map(_.fromNow)
    
    //a tail recursive "while" loop that will only finish when a successful CAS is operated on the Reference.
    @tailrec
    def cas(): Boolean = {
      //get the reference to the current map (these might be changed later by another thread)
      val oldMap = cache.get
      //create a new updated map
      val newMap = {
        //1- clone and add the new element
        val clone = oldMap.clone += key -> elt
        //2- check that we are within the bound
        if (clone.size > maxSize) clone.drop(clone.size - maxSize)
        else clone
      }
      //try to CAS the AtomicReference. If we fail, try again
      if (!cache.compareAndSet(oldMap, newMap)) deadline match {
        //except if we are past the deadline
        case Some(d) if d.isOverdue => false
        case _ => cas()
        //equivalent to (but covering all cases):
        //case None => cas()
        //case Some(d) if d.hasTimeLeft => cas()
      } else {
        true
      }
    }
    cas()
  }

  /**
   * try to get the key, if it's not in the map yet, put the value in it. (useful for a cache use)
   */
  def getOrElse(key: K, maxWait: Option[FiniteDuration] = None)(elt: => E): E = {
    get(key).getOrElse {
      val newElt = elt
      put(key, newElt, maxWait)
      newElt
    }
  }

}

object Memoizer {

  /**
   * wrap the function within a bounded cache. 
   * We have to specify the maximum size of the cache, and optionally a maximum time to wait for access to the cache.
   * It's a good idea to specify a maxWait. If the cache is too busy, we do not want to wait indefinitely for our computed value, it's better to
   * recompute it.
   */
  def boundedMemoize[I, O](bound: Int, maxWait: Option[FiniteDuration] = None)(f: I => O): I => O = {
    // use the lock free map for the cache. One per wrapped function
    val cache = new LockFreeBoundedCache[I, O](bound)
    //return a new function that uses the cache instead of doing the straight computation
    ((in: I) =>
      cache.getOrElse(in, maxWait) {
        f(in)
      })
  }
}