Building a high performing last viewed list using Redis

We live in a day and age in which we can choose a data-store that matches the characteristics of our apps and (micro) services. Lately we've been looking into Redis as a high performing store for last viewed items. In this blog I'll look show how to create a POC with the redis-cli and then implement it using .NET Core. We'll be using the sorted set structure.

Screenshot of last viewed items at wehkamp.nl
The last viewed items are visible on the wehkamp.nl home-page. Our app uses this feature as well.

When you dive into the topic of last viewed you see some interesting properties that need to be supported:

  • We only need to store the 10 last viewed items.
  • The last visited item should be stored at the beginning of the list.
  • A product should only appear once in the list (at the right place).
  • Families share accounts and people use tabs, so reads and writes come in asynchronously.
  • There are many (!!) lists. Adding to and retrieval of the list should be as fast as possible as it cannot be cached.

Find a data structure that works

As an engineer I'm tempted to directly start programming a micro-service to see if I can make it work. But as the service is so tightly coupled to Redis, it is better to use the redis-cli first to see if we can create a flow that works. Once we've found that flow, we can turn it into a service.

Redis is so much more than just a key/value store. It has some interesting data-structures. Each structure comes with its own set of commands to manipulate the underlying data.

Redis data structures: string, linked lists, sets of strings, sorted sets of strings and hash tables.
One key to rule them all.

The data structure I'll be using is the sorted set. It works with a score that will influence the position (rank) of the item. The set is ordered from low to high, so the lowest scores are at the beginning of the list. I'll be using 0 - {time in ticks} as the score, so the last viewed products are at the beginning of the list.

ZADD: adding to the set

Let's do some testing! Just fire up Bash and make sure your Redis server is running: sudo service redis-server restart. (I'm using the Windows Subsystem for Linux to run Redis locally.)

Let's see what happens when we add some with scores. I've created an add.txt with the actual commands. I'll feed it to the redis-cli by doing: cat add.txt | redis-cli. This gives me some room to fiddle around till it works. The file looks like this:

del set:1
zadd set:1 -1555596360001 alpha
zadd set:1 -1555596360002 beta
zadd set:1 -1555596360003 gamma
zadd set:1 -1555596360004 alpha
zadd set:1 -1555596360005 delta
zadd set:1 -1555596360006 epsilon
zadd set:1 -1555596360007 alpha
zadd set:1 -1555596360008 zeta
zadd set:1 -1555596360009 eta
zadd set:1 -1555596360010 theta
zadd set:1 -1555596360011 iota
zadd set:1 -1555596360012 kappa
zadd set:1 -1555596360013 alpha
zadd set:1 -1555596360014 lambda
zadd set:1 -1555596360015 mu
zadd set:1 -1555596360016 alpha
zrange set:1 0 -1

Everything in Redis works with a key. I'll be using the id of the user together with the prefix set: as a key. First I'll remove the key, so I can run the tests multiple times. Then I'll add some data using zadd with the score. And finally I'll display they all the items in the set by doing a zrange.

Because each item has a lower score than the previous, it will be added to the beginning of the ordered set. I've created a visualization of how items are added. We're adding the aplha-item multiple times, so I highlighted it to make it easier to see how it "moves" through the list based on its score:

Items on the Redis sorted set visualized.
The lowest score is at the beginning of the list, so we need to make sure that a new item has a lower score than the rest.

Each unique name is only added once; just like we would expect from a set.

ZREMRANGEBYRANK

We don't want to store more than is necessary - as every Wehkamp user has a last viewed list, things add up quickly.

To keep things clean, we'll remove everything from rank 10 and up. Remember: the lowest rank is 0 = the lowest score = the most recent date, as we do 0 - ticks.

To remove things from the ordered set, we must use the zremrangebyrank command. We're starting at rank 10. As stop we'll use -1, which indicates the highest rank.

zremrangebyrank set:1 10 -1

If the list is less than 10 items, nothing will happen; there is no exception thrown, so it is safe to execute.

ZRANGE

If we want to view our items, we need to do:

zrange set:1 0 9

Let's visualize the combination of zadd, zremrangebyrank and zrange:

Redis sorted set - capped at 10
Here all ZADD commands are followed by a ZREMRANGEBYRANK, so the sorted set is max 10 items long. Items beta and gamma are removed from the list once it gets bigger than 10.

Implementation in .NET

Now we know what we want, we can implement it into a service. I'll be using the StackExchange Redis nuget package to talk to Redis. Let's first define an interface for storage abstraction:

public interface ILastViewedStore
{
    Task<bool> Add(int userId, string productId);

    Task<bool> Add(int userId, string[] productIds);

    Task<string[]> Get(int userId);

    Task<bool> Delete(int userId);
}

The string[] productIds is used to support a migration from our previous solution.

Setting up the basics

For the implementation of the store we'll use the IDatabase provided by the StackExchange Redis package. We will do the setup of the class on startup time by dependency injection.

public class LastViewedStoreRedis : ILastViewedStore
{
    private readonly int _size;
    private readonly IDatabase _database;

    public LastViewedStoreRedis(int size, IDatabase database)
    {
        _size = size;
        _database = database;
    }

    private static string ConstructKey(int userId)
    {
        return $"set:{userId}";
    }

    private long GetScore()
    {
        var time = DateTime.Now.Ticks - DateTime.UnixEpoch.Ticks;
        return 0 - time;
    }
}

The ConstructKey gives us a nice way to determine the key for the set. The GetScore will give use a time-based score. To make the value smaller we're subtracting Unix Epoch ticks.

We can use dependency injection to setup the store and inject it where needed:

services.AddTransient<ILastViewedStore>(x =>
{
    var connection = x.GetRequiredService<IConnectionMultiplexer>();
    var database = connection.GetDatabase();
    return new LastViewedStoreRedis(10, database);
});

Implementing add

On every add we need to do two things: add one or more items and remove anything that's out of range:

public Task<bool> Add(int userId, string productId)
{
    return Add(userId, new[] {productId});
}

public Task<bool> Add(int userId, string[] productIds)
{
    var key = ConstructKey(userId);
    var entries = Array.ConvertAll(productIds, p => 
        new SortedSetEntry(p, GetScore())
    );

    var trans = _database.CreateTransaction();
    trans.SortedSetAddAsync(key, entries);
    trans.SortedSetRemoveRangeByRankAsync(key, _size, -1);
    return trans.ExecuteAsync();
}

I'm using a transaction to make sure both the add and remove are done together. More on transactions can be found here.

Fire and forget?

There is a CommandFlags.FireAndForget flag that you could give to the operations, but it looks like this is something that is "invented" by the package (not by Redis) and should not be used in combination with async. For more information, check this StackOverflow discussion and this one.

Implementing get & delete

The rest of the implementation is trivial:

public Task<bool> Delete(int userId)
{
    var key = ConstructKey(userId);
    return _database.KeyDeleteAsync(key);
}

public async Task<string[]> Get(int userId)
{
    var key = ConstructKey(userId);
    var stop = _size - 1;
    var values = await _database.SortedSetRangeByRankAsync(key, 0, stop);

    return Array.ConvertAll(values, x => (string) x);
}

That's it

We can now use the ILastViewedStore in a controller and supply the API to the rest of the ecosystem. Because of Redis the performance improved significantly, we decreased the average response time of the Last Viewed Service with 78%.

Wehkamp Last Viewed List using Redis sorted set: done!
Well... back to other things.
expand_less