LRUCache en Scala ?

Question

Je sais que la goyave a une excellente bibliothèque de mise en cache mais je cherche quelque chose de plus convivial pour Scala/fonctionnel où je peux faire des choses comme cache.getOrElse(query, { /* expensive operation */}) . J'ai également consulté Mémo de Scalaz mais qui n'a pas d'expiration lru.

Answer 1

Les gens de Spray ont une la cache par pulvérisation qui utilise les Futures. Il existe une version LRU simple et une version qui vous permet de spécifier une durée de vie explicite, après laquelle les entrées sont automatiquement expirées.

L'utilisation des Futures permet évidemment d'écrire un code qui ne se bloque pas. Mais ce qui est vraiment génial, c'est que cela résout en prime le problème des "troupeaux de tonnerre". Supposons, par exemple, qu'un grand nombre de requêtes arrivent en même temps pour la même entrée qui n'est pas dans le cache. Dans une implémentation naïve du cache, une centaine de threads pourraient manquer cette entrée dans le cache et s'exécuter pour générer les mêmes données pour cette entrée du cache, mais bien sûr, 99 % de cela n'est que de l'effort gaspillé. Ce que vous voulez vraiment, c'est qu'un seul thread génère les données et que les 100 demandeurs voient le résultat. Cela se produit tout naturellement si votre cache contient des Futures : le premier demandeur installe immédiatement un Future dans le cache, de sorte que seul le premier demandeur manque à l'appel. Les 100 demandeurs obtiennent ce Future pour le résultat généré.

Answer 2

Solution LRUCache basée sur Java LinkedHashMap et exposée comme Scala mutable.Map

import java.util.Collections.synchronizedMap

import scala.collection.JavaConversions._
import scala.collection.mutable

class LRUCache[K, V](maxEntries: Int)
  extends java.util.LinkedHashMap[K, V](100, .75f, true) {

  override def removeEldestEntry(eldest: java.util.Map.Entry[K, V]): Boolean 
     = size > maxEntries

}

object LRUCache {
  def apply[K, V](maxEntries: Int): mutable.Map[K, V] 
    = synchronizedMap(new LRUCache[K, V](maxEntries))
}

Lorsque la taille de la carte > maxEntries, la dernière entrée utilisée est supprimée.

Le paramètre 3rd du constructeur de LinkedHashMap doit être fixé à true pour la stratégie LRU. LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

Exemple d'utilisation :

val cache = LRUCache[String, Int](1000)
val key = "key1"
val value = 111

cache.get(key) shouldBe None
cache += key -> value
cache.get(key) shouldBe Some(value)
cache(key) shouldBe value