LRU и FIFO кэши в Scala без лишних зависимостей

9 февраля 2015

Редкое серьезное приложение в наши дни обходится без кэширования чего-либо. Какой-нибудь LRU кэш элементарно реализуется, например, при помощи хэш-таблиц и двусвязных списков. Но не факт, что ваше решение будет отличаться особой эффективностью, поэтому лучше воспользоваться готовой реализацией. Часто в качестве такой реализации рекомендуют Guava или LruMap из twitter-util. Но у этих решений есть свои минусы, в частности, стэк Twitter’а традиционно привязывает вас к Scala 2.10, а Guava просто страшна.

К счастью, в Scala можно легко завести простенький кэшик, не протаскивая в проект лишних зависимостей. В мире Java широко известен прием с оверайдом метода removeEldestEntry класса LinkedHashMap, позволяющий получить LRU кэш. Прием этот не слишком элегантен, но все равно не так страшен, как Guava. В переводе на Scala он выглядит так:

import java.util.{Map, LinkedHashMap}

def makeCache[K,V](capacity: Int): Map[K, V] = {
  new LinkedHashMap[K, V](capacity, 0.7F, true) {
    private val cacheCapacity = capacity

    override def removeEldestEntry(entry: Map.Entry[K, V]): Boolean = {
      this.size() > this.cacheCapacity
    }
  }
}

Пример использования:

scala> case class Dog(name: String)
defined class Dog

scala> val cache = makeCache[String, Dog](3)
cache: java.util.Map[String,Dog] = {}

scala> for(i <- 1 to 10) { cache.put(i.toString, Dog(i.toString)) }

scala> cache
res1: java.util.Map[String,Dog] = {8=Dog(8), 9=Dog(9), 10=Dog(10)}

scala> Option(cache.get("8"))
res2: Option[Dog] = Some(Dog(8))

scala> cache
res3: java.util.Map[String,Dog] = {9=Dog(9), 10=Dog(10), 8=Dog(8)}

scala> Option(cache.get("ololo"))
res4: Option[Dog] = None

Обратите внимание, что cache.get оборачивается в Option, поскольку это джавный LinkedHashMap и метод get может возвращать null. Но для примитивных типов (Int и подобные), возвращается значение по умолчанию:

scala> val cache = makeCache[String, Int](3)
cache: java.util.Map[String,Int] = {}

scala> cache.get("test")
res5: Int = 0

scala> val cache = makeCache[String, Boolean](3)
cache: java.util.Map[String,Boolean] = {}

scala> cache.get("test")
res6: Boolean = false

Поэтому вам может захотеться использовать метод containsKey:

scala> cache.containsKey("test")
res7: Boolean = false

Следует также принять во внимание, что если с вашим кэшом может работать больше одного потока одновременно, хождение в него нужно оборачивать в synchonized:

scala> cache.synchronized { cache.get("test") }
res8: Boolean = false

Теперь рассмотрим второй способ.

В Scala тоже есть LinkedHashMap, но у него нет аргумента accessOrder, как в джавном LinkedHashMap, в результате чего с его помощью можно получить только FIFO кэш:

import scala.collection._

val cacheCapacity = 10000
val cacheMutex = new Object()
var cache = mutable.LinkedHashMap[String, Long]()
  
// запись в кэш
cacheMutex.synchronized {
  cache.put("key", 100500)
  cache = cache.drop(cache.size - cacheCapacity)
}
  
// чтение из кэша
cacheMutex.synchronized { cache.get("key") }

Здесь метод get возвращает Option. Подчищается кэш «вручную» при помощи метода drop. Причем этот метод возвращает новый LinkedHashMap, поэтому для синхронизации доступа к кэшу требуется отдельный объект cacheMutex. Следует также принять во внимание, что из соображений эффективности вам может захотеться делать drop не на каждую запись в кэш:

// запись в кэш
cacheMutex.synchronized {
  cache.put("key", 100500)
  if(cache.size > cacheCapacity) {
    cache = cache.drop(cache.size - (cacheCapacity.toDouble*0.7).toInt)
  }
}

И вообще, возможно, делать это в отдельном потоке.

Само собой разумеется, есть много других способов создать кэш в Scala, но эти два кажутся мне самыми простыми. Конечно же, в реальных приложениях все намного интереснее, поскольку кэши не должны разъезжаться с реальными данными или с кэшами на других нодах, кэш может понадобиться разбить на несколько, чтобы он не становился бутылочным горлышком, и так далее.

Ссылки по теме:

А как вы делаете кэши?