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.
Contents
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:
- If it’s a matching bracket, simply drop both.
- 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 nameRedisModule_OnLoad
.The signature of the
RedisModule_OnLoad
should beint 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. Returningfalse
as a guard here results in module registration failure upper in the stack, inRedisModule_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). CallingRedisModule_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 foralloc<ULongVar>
, but that value is not used, it is only needed for theRedisModule_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 withtry
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 aStableRef
so that Kotlin/Native runtime will maintain a stable address for it.dispose
must be called on thatStableRef
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
!
Top comments (0)