Awesome
Cache-Lite - An extremely light-weight cache framework for Kotlin
The Cache-Lite is an extremely light-weight cache framework implemented in Kotlin, it is for study case.
You can check out the source code to learn how caching works and learn how to implement a simple cache framework by yourself.
Usage
Although this is a simple project for study case, it's well tested and you can still use it in your project if you found it fits your use case.
<dependency>
<groupId>io.github.kezhenxu94</groupId>
<artifactId>cache-lite</artifactId>
<version>${cache-lite.version}</version>
</dependency>
Background
Caching is a critical technology in many high performance scalable applications. There are many choices in caching framework, including Ehcache, Memcache, cache2k etc. But today we are going to build one on our own, to learn what cache really does. Let's get started.
Naive Version
A cache is typically a key-value store, and in Kotlin/Java there is exactly a class representing this kind of data structure: Map
. There are chances that we have already leveraged this class to do some caching tasks. So the very first thought to build a caching framework is simply using the class java.util.Map
.
val cache = HashMap<Any, Any>()
cache["key"] = "Frequently used value taken from database"
val v = cache["key"]
println(v)
cache.remove("key")
Quite simple, isn't it? But according to the programming principle, "Program to Interface, not Implementation", we should not couple our caching framework to the specific implementation, which is java.util.Map
here. You may argue that java.util.Map
is an interface, not an implementation. True, but not applicable here. Here we are talking about a caching system, which means that, for end users, caching is an interface and java.util.Map
is an implementation that they don't care. We have to define an interface that only describes what a cache does.
Defining Cache
Interface
There are some basic operations on a cache, you may want to put
a value into it, get
a value by key
from it, remove
a value by key
from it, clear
it and know what's the size
of it. After saying the sentence, our interface Cache
is almost done.
interface Cache {
val size: Int
operator fun set(key: Any, value: Any)
operator fun get(key: Any): Any?
fun remove(key: Any): Any?
fun clear()
}
Here is one thing different from what we just said, the method set
. The reason why we name it set
is that we want to use operator []
to put a value by key into the cache. By using operator function set
, we are able to put a value into cache like this: cache["key"] = "value"
, instead of cache.put("key", "value")
.
Cache Forever
One of the challenges in designing a caching framework is to deal with the expiration of the cached items. But for simplicity, we are ignoring this now and build our first cache that caches items forever until we remove it manually.
It is true that we should program to interface not implementation, but when we are implementing an interface, we could leverage some other implementations, here we will use java.util.Map
to implement our first cache, PerpetualCache
:
class PerpetualCache : Cache {
private val cache = HashMap<Any, Any>()
override val size: Int
get() = cache.size
override fun set(key: Any, value: Any) {
this.cache[key] = value
}
override fun remove(key: Any) = this.cache.remove(key)
override fun get(key: Any) = this.cache[key]
override fun clear() = this.cache.clear()
}
All of the methods are delegated to cache
, it is fine because cache
is private
so that we can change our implementation without effecting our end users. Now that we have our own cache interface Cache
and one of implementations of it, PerpetualCache
, we want to add more functionalities.
LRU Cache
By now our cache will keep all the entries until we remove them manually, it can be very memory-intensive. In many caching scenarios, we assume that the entries we recently used will be used again soon, if that is true (mostly it is), we can keep only a certain number of entries that are recently used and remove others, this kind of flush strategy is called Least Recently Used.
Since we already have PerpetualCache
and we want to add responsibilities to this class, the Decorator Pattern is the best choice here.
class LRUCache(private val delegate: Cache, private val minimalSize: Int = DEFAULT_SIZE) : Cache by delegate {
private val keyMap = object : LinkedHashMap<Any, Any>(minimalSize, .75f, true) {
override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Any, Any>): Boolean {
val tooManyCachedItems = size > minimalSize
if (tooManyCachedItems) eldestKeyToRemove = eldest.key
return tooManyCachedItems
}
}
private var eldestKeyToRemove: Any? = null
override fun set(key: Any, value: Any) {
delegate[key] = value
cycleKeyMap(key)
}
override fun get(key: Any): Any? {
keyMap[key]
return delegate[key]
}
override fun clear() {
keyMap.clear()
delegate.clear()
}
private fun cycleKeyMap(key: Any) {
keyMap[key] = PRESENT
eldestKeyToRemove?.let { delegate.remove(it) }
eldestKeyToRemove = null
}
companion object {
private const val DEFAULT_SIZE = 100
private const val PRESENT = true
}
}
We only keep minimalSize
entries at most. Here we leverage the class java.util.LinkedHashMap
to trace the usage of entries, and eldestKeyToRemove
is the one to be removed, which is the eldest entry ordered by used frequency. Method cycleKeyMap
is responsible for removing entries that are too old and less used. Simple and straightforward.
Expirable Cache
As we said above, expiration is critical in caching framework because it prevent our cache from growing infinitely. With the experience of LRUCache
implementation, we know how and when to remove entries, it's time to implement an expirable cache.
class ExpirableCache(private val delegate: Cache,
private val flushInterval: Long = TimeUnit.MINUTES.toMillis(1)) : Cache by delegate {
private var lastFlushTime = System.nanoTime()
override val size: Int
get() {
recycle()
return delegate.size
}
override fun remove(key: Any): Any? {
recycle()
return delegate.remove(key)
}
override fun get(key: Any): Any? {
recycle()
return delegate[key]
}
private fun recycle() {
val shouldRecycle = System.nanoTime() - lastFlushTime >= TimeUnit.MILLISECONDS.toNanos(flushInterval)
if (!shouldRecycle) return
delegate.clear()
}
}
To make it simple, by saying expirable, we means that the cache is expirable, not a single entry in the cache is expirable. However, after knowing how the entire cache is expired, it's easy to implement a cache where entries are expired respectively.
We are given a flushInterval
, and we will clear the cache every flushInterval
milliseconds. It's typically a scheduled task, we can use a background thread to do the task, but again, to make it simple, we just recycle
before every operation in our cache.
Other Implementations
Besides the three implementations we discussed above, here are several implementations such as FIFOCache
, SoftCache
and WeakCache
, implemented with First-in-first-out algorithm, Soft Reference, and Weak Reference respectively.
None-typed Cache
To make a cache more flexible, in terms of values it can store, Cache type can be used which is just a type-alias
typealias Cache = GenericCache<Any, Any>
You can check out the source code here in GitHub.