Dijkstra's algorithm by Redis and Lua (1 of 2)

Redis provides several kind of data structures and many functions to manipulate those data. But sometimes additional function is required for satisfying some demand.

The power of Lua

For example, you may need to delete a string only when the string is equal to a specified one but there is no such function. Although this is easy to implement by checking the equality of GET-ed string in client-side program and executing DEL command if necessary, it is difficult to make sure that this operation is atomic and you also have to implement a remote locking mechanism. Fortunately, this problem is easily solve because Redis has a great flexibility to extend its function by built-in Lua interpreter. EVAL and EVALSHA commands evaluate a Lua script atomically and you can execute Redis commands inside Lua script.

Above function is implemented like this:

-- deleq.lua
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('DEL', KEYS[1])
else
  return nil
end

Here is an example to delete mykey if its value is equal to “Redis”.

% redis-cli SET mykey Redis
OK

% redis-cli EVAL "$(cat deleq.lua)" 1 mykey Redis
(integer) 1  # deleted !!

% redis-cli SET mykey redis
OK

% redis-cli EVAL "$(cat deleq.lua)" 1 mykey Redis
(nil)  # not deleted

The detail of Lua script and meanings of arguments for EVAL are not explained in this post. There are already some good articles for learning: Lua: A Guide for Redis Users is a very good tutorial and document of EVAL provides a wealth of content.

Constructing a directed graph with weighted edges

As above, Redis becomes a computational environment rather than data store with the help of Lua. Although there are some restrictions on running Lua script in Redis, there still be a wide range of application.

As an example, I wil try to implement the Dijkstra’s shortest path algorithm. Before implementing the algorithm I need a data structure to represent a directed graph with weighted edges. In some usual programming languages, such a graph can be implemented as a list of lists. We can do similar by having a bunch of Redis’s lists but I would like to put everything into a single object. So I pack a node pair into an integer value and associate a weight between the nodes to it. Suppose that nodes of graph are indexed from 0 to n-1, a edge from node i to node j can be represnted by i*n + j. Then, a Lua script to register weighted graphs edges can be implemented like this:

-- add_edge.lua
local function set_weight(key, n, i, j, w)
  redis.call('HSET', key, n*i + j, w)
end

local n = ARGV[1]
local argc = table.getn(ARGV)

for i = 2, argc, 3 do
  set_weight(KEYS[1], n, ARGV[i], ARGV[i+1], ARGV[i+2])
end

This script takes a Redis key for storing information of edges, number of nodes and some edge triples in which each consists of source node index, destination node index and weight of the edge.

For instance, above graph can be stored by following command.

% redis-cli EVAL "$(cat add_edge.lua)" 1 graph \
        5 0 1 2 0 2 3 1 3 4 1 4 5 2 3 1 2 4 3 3 4 1

% redis-cli HGETALL graph
1) "1"
2) "2"
3) "2"
4) "3"
5) "8"
6) "4"
7) "9"
8) "5"
9) "13"
10) "1"
11) "14"
12) "3"
13) "19"
14) "1"

In the next post, I will implement the Dijkstra’s algorithm over this graph data structure!