Categories: Функциональное программирование

scala-cache/

Редкое серьезное приложение в наши дни обходится без кэширования чего-либо. Какой-нибудь 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, но эти два кажутся мне самыми простыми. Конечно же, в реальных приложениях все намного интереснее, поскольку кэши не должны разъезжаться с реальными данными или с кэшами на других нодах, кэш может понадобиться разбить на несколько, чтобы он не становился бутылочным горлышком, и так далее.

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

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

admin