cachemap

---

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 Kotlin's read-only Map<K, V> interface and provides familiar mutation operations, so it can be used like a normal map for individual reads and writes.

The exception is the entries, keys, and values properties. On a normal map, these return live views backed by the map's internal storage. CacheMap cannot safely allow those views to escape the protected read in which they were obtained, because the backing map may subsequently be mutated. These properties therefore throw UnsupportedOperationException.

Instead, we provide the following replacement functions forEach, forEachKey, or forEachValue.

CacheMap is ultimately a thin wrapper around the left-right concurrency primitive.

Setup

dependencies {
    implementation("io.github.charlietap:cachemap:0.3.0")
    // Or
    implementation("io.github.charlietap:cachemap-suspend:0.3.0")
}

Usage

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)

Coroutines

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
// }

leftright

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;

Loading

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.

Setup

dependencies {
    implementation("io.github.charlietap:leftright:0.3.0")
    // Or
    implementation("io.github.charlietap:leftright-suspend:0.3.0")
}

Usage

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)

Coroutines

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")
    }
}

Additional Reading

• Making my concurrent algo 6000% better

License

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.

• For details on the MIT license, please see the LICENSE-MIT file.
• For details on the Apache 2.0 license, please see the LICENSE-APACHE file.