Implements a single-writer concurrent hashmap allowing lock-free, wait-free reads. Supports coroutines, ensuring non-blocking operations, and uses left-right concurrency for efficient data management.
CacheMap is single writer concurrent hashmap implementation.
Reads from the hashmap can proceed concurrently to writes from any thread with zero coordination necessary... No locks and no waits
CacheMap implements Map<K,V> so can be used in place of existing map instances.
CacheMap implements all of MutableMap<K,V> with the exception of val entries: Set<Map.MutableEntry<K, V>>
as exposing MutableEntry's would allow mutation without the necessary write coordination.
CacheMap is ultimately a thin wrapper around the left-right concurrency primitive.
dependencies {
implementation("io.github.charlietap:cachemap:0.2.4")
// Or
implementation("io.github.charlietap:cachemap-suspend:0.2.4")
}
Instance creation follows the typical Kotlin convention
val cachemap = cacheMapOf()
For sizing the initial capacity you can use
val cachemap = cacheMapOf(9000)
And for pre-population a varargs constructor exists
val cachemap = cacheMapOf(key to value,...)
Use cachemap like any MutableMap in Kotlin
cachemap[key] = value
// or
cachemap.put(key, value)
For reasons documented in leftright cachemap may block or yield within methods that mutate the map. If you would prefer to not block the underlying thread you can use the suspending variant of cachemap:
val cachemap = suspendCacheMapOf()
Use cachemap like any MutableMap in Kotlin
scope.launch {
cachemap.put(key, value)
}
// Unfortunately operator functions cannot suspend so this is not possible
// scope.launch {
// cachemap[key] = value
// }
left-right is a concurrency primitive which allows lock-free/wait-free reads of any mutable datastructure.
Conceptually left-right can be understood as a concurrency primitive that maintains two copies of a datastructure with a pointer (switch) directing traffic for reads and writes in separate directions.
graph TD;
Switch--reads-->Left;
Switch--writes-->Right;
If you're interested in learning more about the intricacies of the algorithm I would recommend an incredible video from John Gjengset which details his creation of an eventually-consistent implementation of a left-right. My implementation borrows the same epoch counter algorithm for waiting on departing readers with a deviation to avoid the global epoch array lock by imposing a max parallelism invariant and leveraging ThreadLocal state.
You can also find what I believe to be the first paper on the primitive here.
dependencies {
implementation("io.github.charlietap:leftright:0.2.4")
// Or
implementation("io.github.charlietap:leftright-suspend:0.2.4")
}
LeftRight is generic over any given datastructure and can be constructed like so
val leftright = LeftRight<T>(::constructorForT)
// For example
val leftRightSet = LeftRight<MutableSet<String>>(::mutableSetOf)
Whilst reads avoid locks and waits, writes are not so lucky. A write is capable of both blocking on a mutex and yielding back to the scheduler if readers take too long to depart. Rather than blocking valuable thread resources you can yield back to the coroutines runtime using with the suspend variant:
val leftright = SuspendLeftRight<T>(::constructorForT)
// For example
val leftRightSet = SuspendLeftRight<MutableSet<String>>(::mutableSetOf)
// mutate is now suspending
scope.launch {
leftRightSet.mutate {
it.add("Hello worlds")
}
}
This project is dual-licensed under both the MIT and Apache 2.0 licenses. You can choose which one you want to use the software under.
Surfaced from shared tags and platforms — no rankings paid for.