tamarlabs/rede

A Redis dehydrator module

ReDe - The Element Dehydration Module

🚀TL;DR - A Dehydrator is a timer data structure capable of handling millions of cuncurrent timers, and their corresponding payload, see what commands this module provides HERE

ReDe /'redɪ/ n. a Redis Module for simple data dehydration using the Lawn algorithm. This is a pretty straightforward implementation of the dehydration system depicted in the article "Fast Data". The Goal of this module is to solve the Contextual Completeness and Emergent Relevancy problems by adding the ability to postpone incoming elements to a later time in which we will have a complete information for these elements. Effectively acting as a snooze button to any element.

You can read further on the algorithm behind this module here. or read the actual article here

Common Use Cases

• Stream Coordination - Make data from one stream wait for the corresponding data from another (preferebly using sliding-window style timing).
• Event Rate Limitation - Delay any event beyond current max throughput to the next available time slot, while preserving order.
• Self Cleaning Claims-Check - Store data for a well known period, without the need to search for it when it is expired or clear it from the data-store yourself, minimizing load on transportation and manipulation nodes of your pipeline architecture.
• Task Timer - Postpone actions and their respective payloads to a specific point in time.

The module works by adding a new type to Redis -DehydratorType. It will be ceated automatically when you call a push command on it, and it can be deleted using the DEL command like any other key.

From the article:

Dehydrators are simplistic time machines. They transport data elements that arrived prematurely in terms of their context right to the future where they might be needed, without loading the system while waiting. This concept is achieved by attaching a time-indexed data store to a clock, storing elements as they arrive to the dehydrator and re-introducing them as inputs to the system once a predetermined time period has passed.

This repo includes:

1. Dehydration module source code

module.c - Build it, read it, love it, extend it (PRs are welcome)!

2. usage example files and load tests

In this repository there are two python files that exemplify the usage of the module:

• helloworld.py - very simple usage example of all the functions exposed by the module
• test.py - run internal as well as external functional tests, load test and print it all to stdout.

3. Redis PubSub utility script

pubsub.py - A workaround for the lack of redis background tasks for providing PUB/SUB functionality

4. Redis Benchmark

The modified redis-benchmark code used to measure some of the module's performance.

5. klib khash

A set of macros to create the hash maps used to implement the dehydrator type.

6. LibRMUtil

From Redis Modules SDK README:

A small library of utility functions and macros for module developers, including:

• Easier argument parsing for your commands.
• Testing utilities that allow you to wrap your module's tests as a redis command.
• RedisModuleString utility functions (formatting, comparison, etc)
• The entire sds string library, lifted from Redis itself.
• A generic scalable Vector library. Not redis specific but we found it useful.
• A few other helpful macros and functions.
• alloc.h, an include file that allows modules implementing data types to implicitly replace the malloc() function family with the Redis special allocation wrappers.

It can be found under the rmutil folder, and compiles into a static library you link your module against.

Usage

The dehydrator is an effective 'snooze button' for events, you push an event into it along with an id (for future referance) and in how many seconds you want it back, and poll whenever you want the elements back. only expired elements would pop out.

The module include 9 commands:

• REDE.PUSH - Insert an element. The command takes an id for the element, the element itself and dehydration time in milliseconds.
• REDE.GIDPUSH - Insert an element. The command generates an id for the element, but still needs the element itself and dehydration time in milliseconds.
• REDE.PULL - Remove the element with the appropriate ID whether it is expired or not.
• REDE.POLL - Pull and return all the expired elements.
• REDE.XPOLL - Return the IDs of all the expired elements, without pulling.
• REDE.LOOK - Search the dehydrator for an element with the given ID and if found return it's payload (without pulling).
• REDE.XACK - Pull and return all the expired elements from within the given set of IDs.
• REDE.TTN - Return the minimal time between now and the next expiration (aka. time to next).
• REDE.UPDATE - Set the element represented by a given id, the current element will be returned, and the new element will inherit the current expiration.

it also includes a test command:

• REDE.TEST - a set of unit tests of the above commands. NOTE! This command is running in fixed time (~15 seconds) as it uses sleep (dios mio, No! ✞✞✞).

see more about the commands in Commands.md

Quick Start Guide

Here's what you need to do to build this module:

0. Build Redis in a build supporting modules.
1. Build the module: make or download the .so file from the latest release
2. Run Redis loading the module: /path/to/redis-server --loadmodule path/to/module.so

Now run redis-cli and try the commands:

127.0.0.1:9979> REDE.PUSH some_dehy 15000 world id1
OK
127.0.0.1:9979> REDE.PUSH some_dehy 1000 hello id2
OK
127.0.0.1:9979> REDE.PUSH some_dehy 2000 goodbye id3
OK
127.0.0.1:9979> REDE.PULL some_dehy id3
"goodbye"
127.0.0.1:9979> REDE.POLL some_dehy
1) "hello"
127.0.0.1:9979> REDE.POLL some_dehy
(empty list or set)
127.0.0.1:6379> REDE.LOOK some_dehy id2
(nil)
127.0.0.1:6379> REDE.LOOK some_dehy id1
"world"
127.0.0.1:6379> REDE.PULL some_dehy id2
(nil)
127.0.0.1:6379> REDE.TTN some_dehy
8000

This (empty list or set) reply from REDE.POLL means that the there are no more items to pull right now, so we'll have to wait until enough time passes for our next element to expire. using REDE.TTN we can see this will be in 8 seconds (in this example we waited a bit between commands). Once 8 seconds will pass we can run:

127.0.0.1:9979> REDE.POLL some_dehy
1) "world"
127.0.0.1:9979> REDE.TEST
PASS
(15.00s)
127.0.0.1:9979> DEL some_dehy
OK

Enjoy!

Known Issues

• TTN test is somewhat unstable on small or heavliy loaded machines.

Future work

• add some sort of pub/sub mechanism to POLL - waiting for some sort of "reactor" pattern or background tasks in redis (maybe this should be a module).. right now this functionality can be achieved by using this python script, there is currently also a task to add a blocking command that duplicates the behavior of the script.
• Additional / more thorough / automatic tests

About This Module

This module is based off a python version of the same concepts designed by Adam Lev-Libfeld and developed in Tamar Labs by Adam Lev-Libfeld and Alexander Margolin in mid 2015.

The Redis module was created by Adam Lev-Libfeld during the RedisModulesHackathon in late 2016, and is maintained by him solely.

rede's Issues

use blocking API to create Pub/Sub commands

Add some sort of pub/sub mechanism to wrap POLL - waiting for some sort of "reactor" pattern or background tasks in Redis (maybe this should be a module).. right now this functionality can be w achieved by using this python script, the task is to add a blocking command named WATCH that duplicates the behaviour of the script.

Suggested syntax:

> REDE.WATCH <dehydrator_name> <channel/stream> [Hz]

where [Hz] is an optional parameter that would define the frequency in which to POLL the dehydrator <dehydrator_name> and publishes them on channel <channel> or streamed on stream <stream>

Memory leak with GIDPUSH

ReDe/src/module.c

Line 80 in 811add5

srandom((unsigned) time(0));

There seems to be a memory leak when using GIDPUSH with Redis 5.0.1 and jemalloc-5.1.0.

We are implementing a timer-based game in which we need to submit entries to a dehydrator which expire in 15 minutes and after expiration, the same number of entries need to be submitted for the next round. When we submit about 20 entries at a time, Redis memory spikes by 35 Mb. This happens every 15 minutes and eventually, Redis goes OOM.

The memory spike was not found when we replaced GIDPUSH with PUSH by generating our own id, hence submitting this issue.

Few SOF links :
https://stackoverflow.com/questions/322938/recommended-way-to-initialize-srand

Abhishek

improve resolution to work in milliseconds

http://stackoverflow.com/questions/3756323/getting-the-current-time-in-milliseconds

Support for reliable messages with streams

I want to process delayed messages with fault tolerance garanties.
POLL command can't do that - it removes message after getting it.
And there is no command to get expired messages without removing them, to remove it later manually.

In redis 5 there is Streams - they can be used for this purpose, they have XACK command.
Message can be getted from REDE and moved to stream.

I can do this with some lua script in transaction. But it is not userfriendly.
Is it possible to add command like "REDE.XPOLL dehydrator_name stream_name", that can do this?

merge similar code in PUSH and GIDPUSH to helper function

make sure there are no memory leaks

add command bindings for the new function implementations

auto create ids if they are not supplied by user

http://stackoverflow.com/questions/7399069/how-to-generate-a-guid-in-c

Separate tests from module.c

the module.c file is a mess! help by extracting all test-related code to a separate file.

update README

to match new API

improve quality of random id generation

by using /dev/urand or something

test for persistence

that is, loading from and to disc

create a print dehy function

currntly it dumps the data on the server side, preferebly we would like it to print on the client side, if possible