Those of you who have some experience with Redis may know that it is not just a simple cache or a plain key-value store, but actually a data structures server, supporting different kinds of values. Out of the box it supports binary-safe strings, sets, lists, hashes, bit arrays, streams and HyperLogLogs. Redis also provides a simple C API for custom data structures, called native types. Some of the popular community-supported native types are Bloom filters, graphs, JSON objects, and tensors.

Let’s use Kotlin/Native to implement a simple data structure for parentheses expression validation just because we can. But first, I want to say thanks to Artyom Degtyarev from JetBrains, who helped a lot with Kotlin/Native in Kotlin Slack.

Redis 101

The best way to start with Redis, is, probably, The Little Redis Book by Karl Seguin. It is absolutely free and takes about an hour to read (Karl mentioned in his blog that the book was written in only two days).

But the bare minimum required to understand the rest of the article is that the idea of Redis is storing different data structures and providing access to them by key:

After grasping the basics consult with the list of Redis commands for the details.

Redis persistence

Redis persistence is an advanced topic and not every regular Redis user needs to dig in it. But as an author of a native type you need to understand it, as every native type needs to support the persistence.

Basically, Redis provides two persistence modes: RDB and AOF. RDB (AKA snapshotting) stands for Redis Database Backup and AOF stands for Append Only File.

Snapshotting is the simplest persistence mode. It produces a point-in-time snapshot of the whole Redist dataset. Snapshots can be taken with SAVE or BGSAVE commands, or configured to be taken periodically or after some predefined number of changes, whatever occurs first. Snapshots produce a binary file called dump.rdb in Redis’s data directory.

AOF is more cunning: every time a change is performed, that operation is logged into the append-only file appendonly.aof in the data directory. Operations are logged in the same format used by Redis, so the AOF can be just “replayed” to reconstruct the whole dataset. The problem is that the AOF grows as changes are performed. So Redis supports an interesting feature: it is able to rebuild the AOF in the background without downtime upon the execution of the BGREWRITEAOF command or periodically. As a result of AOF rewriting it will contain the shortest sequence of commands needed to rebuild the current dataset in memory.

More details about Redis persistence can be found in Salvatore Sanfilippo’s (the author of Redis) article: Redis persistence demystified.

Redis modules

Redis modules make it possible to extend Redis functionality by implementing new functions and data structures. Redis modules are dynamic libraries (.so files), that can be loaded into Redis at startup or using the MODULE LOAD command without downtime. Redis exports its API for the module authors in the form of a single C header file called redismodule.h.

Kotlin/Native Redis module

Kotlin/Native allows developers to produce, among other deliveries, dynamic libraries. So, let’s practice a little bit and create a module providing a native type for parentheses expression validation.

Parentheses expression validation problem

The valid parentheses problem involves checking that:

Every opening parenthesis has a corresponding closing parenthesis.
Every opening parenthesis should come before the corresponding closing parenthesis.

The classic approach to this problem is using a stack:

Declare an empty stack.
Traverse the expression from left to right.
Push every opening parenthesis on the top of the stack.
For every closing bracket, check the topmost stack element:
1. If it’s a matching bracket, simply drop both.
2. If it’s not a matching bracket, push the closing bracket on the top of the stack.
If the expression is valid, then the stack will be empty once the input string finishes.

One way to implement a stack is a singly linked list. Singly linked lists contain nodes that have a data field and a pointer to the next node in line of nodes. The last node will point to nothing, thereby marking the end of the list:

Let’s finally write some code. Here is a Kotlin class for the single stack node for the parenthesis expression validation problem:

class Bracket(val prev: Bracket?, val symbol: Char)

And a class for the whole expression:

class Brackets {
    private var head: Bracket? = null

    fun push(symbol: Char) {
      …
    }

    val valid: Boolean
        get() = …

    override fun toString(): String {
      …
    }
}

push and valid members will make up our stack and toString will be used to print the whole stack and for persistence.

push drops topmost stack element and the incoming bracket if they match and adds a new node if they don’t match. For the sake of simplicity, there are no other checks and validations:

fun push(symbol: Char) {
    head = if (
            ((symbol == ')') && (head?.symbol == '(')) ||
            ((symbol == ']') && (head?.symbol == '[')) ||
            ((symbol == '}') && (head?.symbol == '{'))
    ) {
        head?.prev
    } else {
        Bracket(head, symbol)
    }
}

valid is as simple as checking if the head is null:

val valid: Boolean
    get() = (head == null)

toString uses a recursion to construct a string representation of the stack:

override fun toString(): String {
    fun visit(b: Bracket, buf: String): String {
        return if (b.prev != null) {
            visit(b.prev, b.symbol + buf)
        } else {
            b.symbol + buf
        }
    }

    return this.head?.let {
        visit(it, "")
    } ?: ""
}

The implementation is neither perfect nor safe, but it’s just an example. There is a test for the Brackets class on my GitLab, take a look. Also, note that we used only pure Kotlin code here (for both the domain logic and the tests), without any platform-specific dependencies. This code could be shared across JVM, JS and Native targets if needed, and that’s a cool feature of Kotlin Multiplatform!

C Interop

Before being able to interact with Redis via bindings to its C API, we need to configure a C interop with its redismodule.h. As the whole Redis API is defined in that single header, let’s just copy it from their GitHub to the src/nativeInterop/cinterop/redismodule.h. Next step is to define a src/nativeInterop/cinterop/redismodule.def file describing what things to include into the binding:

headers = redismodule.h

---

# Custom declarations

Here we simply want to create bindings for the contents of redismodule.h plus a few custom declarations.

Kotlin Multiplatform Gradle plugin will do the rest:

kotlin {
    linuxX64 {
        val main by compilations.getting {
            val redismodule by cinterops.creating {
                includeDirs("src/nativeInterop/cinterop")
            }
        }

        binaries {
            sharedLib("brackets_kn")
        }
    }
}

Custom declarations

Redis relies heavily on macros in redismodule.h: all the API functions are exported using a macro REDISMODULE_API_FUNC. This results in functions like RedisModule_CreateCommand, used to provide a callback for custom command, to be seen by Kotlin/Native as a nullable global variable:

var RedisModule_CreateCommand: CPointer<CFunction<(CPointer<RedisModuleCtx>?, CPointer<ByteVar>?, RedisModuleCmdFunc?, CPointer<ByteVar>?, Int, Int, Int) -> Int>>?
    get() = …
    set(value) { … }

It forces an awkward bang-bang syntaxt at call sites:

(RedisModule_CreateCommand!!)(ctx, …)

To mitigate that, one can add a wrapper declaration in a .def file:

static inline int RedisModuleWrapper_CreateCommand(RedisModuleCtx *ctx, const char *name, RedisModuleCmdFunc cmdfunc, const char *strflags, int firstkey, int lastkey, int keystep) {
    return RedisModule_CreateCommand(ctx, name, cmdfunc, strflags, firstkey, lastkey, keystep);
}

Another usecase I found useful is C functions with variadic arguments, like RedisModule_EmitAOF. Kotlin/Native sees it as:

var RedisModule_EmitAOF: COpaquePointer?
    get() = …
    set(value) { … }

And that’s completely unusable! I had to create a custom wrapper specifically for my usecase:

static inline void Brackets_EmitAOF(RedisModuleIO *io, const RedisModuleString *key, char *bracket) {
    return RedisModule_EmitAOF(io, "BRACKETS.KN.PUSH", "sc", key, bracket);
}

RedisModuleWrapper_CreateCommand and Brackets_EmitAOF will be seen by Kotlin/Native as a regular functions.

Module initialization

Now, having the domain objects defined and the C interop configured the next thing to do is to actually create a Redis module. Every Redis module needs to expose a RedisModule_OnLoad function. Redis will call it upon loading the module, this is the place where you tell the Redis what your module is. Let’s define it:

@CName("RedisModule_OnLoad") // (1)
fun RedisModule_OnLoad(
        ctx: CPointer<RedisModuleCtx>?,
        argv: CPointer<CPointerVar<RedisModuleString>>?,
        argc: Int // (2)
): Int {
    // (3)
    if (!initRedisModule(ctx)) {
        return REDISMODULE_ERR
    }

    // (4)
    if (!registerVersionFunction(ctx)) {
        return REDISMODULE_ERR
    }

    // (5)
    if (!registerBracketsType(ctx)) {
        return REDISMODULE_ERR
    }

    // (6)
    return REDISMODULE_OK
}

@CName is used to prevent name mangling and export the function under the exact name RedisModule_OnLoad.
The signature of the RedisModule_OnLoad should be int RedisModule_OnLoad(RedisModuleCtx *, RedisModuleString **, int). This is a Kotlin/Native equivalent.
Init the module.
Export a function that will respond with the module’s version. It’s an optional step, just to show how to define custom commands.
Export a native type. Details are described in a separate section.
If everything is ok, return REDISMODULE_OK.

initRedisModule is a wrapper around RedisModule_Init, provided by Redis. Its parameters include module context, module name, module version, and target Redis API version. We’ll use "brackets.kn" as a module name and integer "1" as a module version, defined in a global constant BRACKETS_KN_VERSION. REDISMODULE_APIVER_1 is provided by Redis in redismodule.h.

private fun initRedisModule(ctx: CPointer<RedisModuleCtx>?) =
        RedisModule_Init(ctx, "brackets.kn", BRACKETS_KN_VERSION, REDISMODULE_APIVER_1) != REDISMODULE_ERR

Exporting a version function is straightfowrard as well, the only interesting part is aquiring a pointer to a Kotlin function to pass as a callback to the RedisModuleWrapper_CreateCommand (which is a wrapper around RedisModule_CreateCommand) via staticCFunction:

fun bracketsKnVersion(ctx: CPointer<RedisModuleCtx>?, argv: CPointer<CPointerVar<RedisModuleString>>?, argc: Int): Int {
    println("bracketsKnVersion")
    (RedisModule_ReplyWithLongLong!!)(ctx, BRACKETS_KN_VERSION.toLong())
    return REDISMODULE_OK
}

private fun registerVersionFunction(ctx: CPointer<RedisModuleCtx>?) =
        RedisModuleWrapper_CreateCommand(ctx, "brackets.kn.version", staticCFunction(::bracketsKnVersion), "", 0, 0, 0) != REDISMODULE_ERR

Exporting a native type

Finally, we approached native types!

A module exporting a native type is composed of the following parts:

The implementation of some kind of new data structure and commands operating on the new data structure. We’ve done the Redis-agnostic part in the Brackets class.
A set of callbacks that handle: RDB saving, RDB loading, AOF rewriting, releasing of a value associated with a key and some other, optional, events.
A 9 character name that is unique to each module native data type.
An encoding version used to persist into RDB files a module-specific data version so that a module will be able to load older representations from RDB files.

A very easy to understand but complete example of native type implementation is available inside the Redis distribution in the /modules/hellotype.c file. Actually, our stack is the same singly linked list as in this file.

To register a new native type into the Redis core, the module needs to declare a global variable that will hold a reference to the data type. The API to register the data type will return a data type reference that will be stored in the global variable. That global variable will be used later to check the types of the values in commands operating on that native data type.

lateinit var KNBracketType: CPointer<RedisModuleType>

fun registerBracketsType(ctx: CPointer<RedisModuleCtx>?): Boolean {
    // (1)
    KNBracketType = RedisModuleWrapper_CreateDataType(
            ctx,
            "KNBRACKET", // (2)
            BRACKETS_KN_VERSION, // (3)
            cValue { // (4)
                version = BRACKETS_KN_VERSION.toULong()
                rdb_load = staticCFunction(::bracketsRdbLoad)
                rdb_save = staticCFunction(::bracketsRdbSave)
                aof_rewrite = staticCFunction(::bracketsAofRewrite)
                free = staticCFunction(::bracketsFree)
            }
    ) ?: return false

    // Registering native type commands

    return true
}

Calling the RedisModule_CreateDataType function via a wrapper to register a native type. Returning false as a guard here results in module registration failure upper in the stack, in RedisModule_OnLoad.
A 9 character name for our native type.
Encoding version. We’ll simply use BRACKETS_KN_VERSION, our module’s version, everywhere.
A pointer to a RedisModuleTypeMethods structure that should be populated with the methods callbacks and structure version. staticCFunction is again our friend.

Now, let’s expose Bracket's operations.

Domain-specific commands

We’ll need three main operations for our data type:

Pushing bracket to the expression
Checking if the expression is valid
Printing the current expression

That operations correspond to the members of Brackets type above, but they need to be wrapped into Redis commands:

fun registerBracketsType(ctx: CPointer<RedisModuleCtx>?): Boolean {
    // Registering a native type

    if (RedisModuleWrapper_CreateCommand(ctx, "brackets.kn.push", staticCFunction(::bracketsKnPush), "write deny-oom", 1, 1, 1) == REDISMODULE_ERR) {
        return false
    }

    if (RedisModuleWrapper_CreateCommand(ctx, "brackets.kn.print", staticCFunction(::bracketsKnPrint), "readonly", 1, 1, 1) == REDISMODULE_ERR) {
        return false
    }

    if (RedisModuleWrapper_CreateCommand(ctx, "brackets.kn.valid", staticCFunction(::bracketsKnValid), "readonly", 1, 1, 1) == REDISMODULE_ERR) {
        return false
    }

    return true
}

Here, we marked brackets.kn.push command as a one that changes the dataset (write flag). deny-oom means that the command may use additional memory and should be denied during out of memory conditions.

brackets.kn.print and brackets.kn.valid commands are read-only.

All the commands expect a single argument, and that argument is a key of the value in the dataset. That’s what those cryptic 1, 1, 1 arguments mean.

Let’s look at the bracketsKnPush, the most complex function:

fun bracketsKnPush(ctx: CPointer<RedisModuleCtx>?, argv: CPointer<CPointerVar<RedisModuleString>>?, argc: Int): Int {
    println("bracketsKnPush")

    // (1)
    if (argc != 3) {
        return (RedisModule_WrongArity!!)(ctx)
    }

    // (2)
    if (argv == null) {
        memScoped {
            return (RedisModule_ReplyWithError!!)(ctx, "argv is null".cstr.ptr)
        }
    }

    // (3)
    val bracket = memScoped {
        (RedisModule_StringPtrLen!!)(argv[2], alloc<ULongVar>().ptr)?.toKString()?.get(0) ?: ' '
    }

    // (4)
    if (bracket !in listOf('(', ')', '{', '}', '[', ']')) {
        memScoped {
            return (RedisModule_ReplyWithError!!)(ctx, "Please, push only one of the `(`, `)`, `{`, `}`, `[`, `]` symbols".cstr.ptr)
        }
    }

    // (5)
    val key = (RedisModule_OpenKey!!)(ctx, argv[1], REDISMODULE_READ or REDISMODULE_WRITE)?.reinterpret<cnames.structs.RedisModuleKey>()

    // (6)
    val type = (RedisModule_KeyType!!)(key)

    // (7)
    if ((type != REDISMODULE_KEYTYPE_EMPTY) && ((RedisModule_ModuleTypeGetType!!)(key) != KNBracketType)) {
        memScoped {
            return (RedisModule_ReplyWithError!!)(ctx, REDISMODULE_ERRORMSG_WRONGTYPE.cstr.ptr)
        }
    }

    if (type == REDISMODULE_KEYTYPE_EMPTY) {
        // (8)
        val obj = Brackets()

        obj.push(bracket)

        (RedisModule_ModuleTypeSetValue!!)(key, KNBracketType, StableRef.create(obj).asCPointer())
    } else {
        // (9)
        (RedisModule_ModuleTypeGetValue!!)(key)?.asStableRef<Brackets>()?.let { ref ->
            ref.get().push(bracket)
        }
    }

    // (10)
    memScoped {
        (RedisModule_ReplyWithSimpleString!!)(ctx, "OK".cstr.ptr)
    }

    (RedisModule_CloseKey!!)(key) // (11)
    (RedisModule_ReplicateVerbatim!!)(ctx) // (12)

    return REDISMODULE_OK
}

Check the number of arguments. brackets.kn.push is called with two arguments — a key and a bracket, so the total number of arguments will be three (the first one will be the command itself). Calling RedisModule_WrongArity here will result in an error telling the user about the wrong number of arguments.
This actually should not happen, but…
Extracting the bracket character from the third argument (argv[2]). memScoped is needed for alloc<ULongVar>, but that value is not used, it is only needed for the RedisModule_StringPtrLen call.
Validating the input. Only brackets are allowed.
Opening the key for writing so that it is possible to call other APIs with the key handle as an argument to perform operations on the key. Don’t forget to call RedisModule_CloseKey. Yeah, better wrap that with try one day…
Querying the key type. If there is no value associated with that key, REDISMODULE_KEYTYPE_EMPTY will be returned.
Fail with REDISMODULE_ERRORMSG_WRONGTYPE message if there is a value associated with that key and it is not empty or of our type.
Create a new Brackets value, push the bracket into it, and store the value in the dataset. The value is wrapped in a StableRef so that Kotlin/Native runtime will maintain a stable address for it. dispose must be called on that StableRef instance when it’s not needed anymore allowing Kotlin/Native’s GC to collect the object.
For the existing values, just call the push.
Replying with "OK".
Closing the key.
Replicating the command to slaves and AOF. Yes, you get the AOF persistence almost for free!

bracketsKnPrint and bracketsKnValid are similar to the bracketsKnPush: they open the key, check the type and call .toString() or .valid on the Brackets value. I won’t provide the code here, as this article became really big.

Now, let’s take a look at the utility functions bracketsRdbLoad, bracketsRdbSave, bracketsAofRewrite and bracketsFree. They have nothing to do with our problem, but they are required by Redis.

Utility functions

bracketsRdbLoad and bracketsRdbSave callbacks are required by Redis to support RDB persistence. Developers are free to use any kind of encoding for their types. The only limit is imagination and the set of available API functions:

Let’s use RedisModule_SaveStringBuffer / RedisModule_LoadStringBuffer to persist our stack as a simple string. Redis will call bracketsRdbSave with a pointer to the RedisModuleIO structure, used for RBD operations, and a pointer to the memory location with our data. As you saw in the previous section the values will be stored using Kotlin/Native’s StableRef, a class used to provide a way to create a stable handle to any Kotlin object. So, in bracketsRdbSave we cast the value to StableRef<Brackets>, then, if it’s not empty, convert it to a string using Brackets#toString function, and save it. memScoped is needed to obtain a short-lived pointer to the null-terminated string to pass to the RedisModule_SaveStringBuffer. Note that this may be unsafe if RedisModule_SaveStringBuffer store that pointer for later use, but it seems to use it immediately, so we’re good.

fun bracketsRdbSave(rdb: CPointer<RedisModuleIO>?, value: COpaquePointer?) {
    println("bracketsRdbSave")

    value?.asStableRef<Brackets>()?.get()?.let {
        memScoped {
            val str = it.toString().cstr

            (RedisModule_SaveStringBuffer!!)(rdb, str.ptr, str.size.toULong())
        }
    }
}

In bracketsRdbLoad we’ll do the opposite: read the null-terminated string from the RDB file and recreate Brackets by pushing the brackets one by one. The result is wrapped into a StableRef and the pointer returned.

fun bracketsRdbLoad(rdb: CPointer<RedisModuleIO>?, encver: Int): COpaquePointer? {
    println("bracketsRdbLoad")

    if (encver != BRACKETS_KN_VERSION) {
        println("Cannot load version $encver")

        return null
    }

    val value = memScoped {
        val value = (RedisModule_LoadStringBuffer!!)(rdb, alloc<ULongVar>().ptr)

        value?.toKString() ?: ""
    }

    val obj = Brackets()

    value.forEach {
        obj.push(it)
    }

    return StableRef.create(obj).asCPointer()
}

In bracketsAofRewrite all we need to do is to emit a sequence of pushes. Here I use a Brackets_EmitAOF function, a wrapper around the RedisModule_EmitAOF.

fun bracketsAofRewrite(aof: CPointer<RedisModuleIO>?, key: CPointer<RedisModuleString>?, value: COpaquePointer?) {
    println("bracketsAofRewrite")

    value?.asStableRef<Brackets>()?.get()?.let {
        it.toString().forEach { bracket ->
            Brackets_EmitAOF(aof, key, "$bracket".cstr)
        }
    }
}

This function called for a Brackets value storing ({[ symbols under the key key, will basically emit a sequence of command like:

BRACKETS.KN.PUSH key (
BRACKETS.KN.PUSH key {
BRACKETS.KN.PUSH key [

Obviously, by replaying this sequence, the original Brackets value can be recreated.

bracketsFree simply disposes a StableRef that we created via brackets.kn.push command or in bracketsRdbLoad. Kotlin/Native’s GC then will be able to recycle that object.

fun bracketsFree(value: COpaquePointer?) {
    println("bracketsFree")

    value?.asStableRef<Brackets>()?.dispose()
}

Testing

You’ve already seen a few links to the source code for this article, but to be clear: madhead-playgrounds/redis on GitLab or madhead/kn-redis if you prefer GitHub. Clone or fork, or just give it a star. If you want to get your hands dirty, follow the instructions in the README, you’ll need Docker Compose. I’ve tried to configure things so that you only need to build the code and start the container, the modules will be loaded automagically.

Let’s tail the logs of the Redis container in a separate console and see what happens upon the execution of some commands:

Let’s also check the AOF:

Seems good. The dataset is recreated correctly after the restart with both RDB and AOF.

Congratulations, we’ve done! Thank you for reading to the end of the article, I hope you found it informative.

Have fun!

Blog

Redis module in Kotlin/Native

madhead

Contents