LRU и FIFO кэши в Scala без лишних зависимостей
9 февраля 2015
Редкое серьезное приложение в наши дни обходится без кэширования чего-либо. Какой-нибудь LRU кэш элементарно реализуется, например, при помощи хэш-таблиц и двусвязных списков. Но не факт, что ваше решение будет отличаться особой эффективностью, поэтому лучше воспользоваться готовой реализацией. Часто в качестве такой реализации рекомендуют Guava или LruMap из twitter-util. Но у этих решений есть свои минусы, в частности, стэк Twitter’а традиционно привязывает вас к Scala 2.10, а Guava просто страшна.
К счастью, в Scala можно легко завести простенький кэшик, не протаскивая в проект лишних зависимостей. В мире Java широко известен прием с оверайдом метода removeEldestEntry класса LinkedHashMap, позволяющий получить LRU кэш. Прием этот не слишком элегантен, но все равно не так страшен, как Guava. В переводе на Scala он выглядит так:
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
}
}
}
Пример использования:
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 и подобные), возвращается значение по умолчанию:
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:
res7: Boolean = false
Следует также принять во внимание, что если с вашим кэшом может работать больше одного потока одновременно, хождение в него нужно оборачивать в synchonized:
res8: Boolean = false
Теперь рассмотрим второй способ.
В Scala тоже есть LinkedHashMap, но у него нет аргумента accessOrder, как в джавном LinkedHashMap, в результате чего с его помощью можно получить только FIFO кэш:
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, но эти два кажутся мне самыми простыми. Конечно же, в реальных приложениях все намного интереснее, поскольку кэши не должны разъезжаться с реальными данными или с кэшами на других нодах, кэш может понадобиться разбить на несколько, чтобы он не становился бутылочным горлышком, и так далее.
Ссылки по теме:
- https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html;
- http://www.scala-lang.org/api/current/index.html#…LinkedHashMap;
- http://code4reference.com/2014/06/lru-implementation-linkedhashmap/;
А как вы делаете кэши?
Метки: Scala, Оптимизация, Функциональное программирование.
Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.