1. Design patterns

1.1. Timeline

1.1.1. Introduction

A way to store a chronological sequence of events with a limited number of entries, so that adding a new element is a constant time operation, and fetching the latest items is also very fast. Old elements are discarded as new elements arrive. Removing elements is possible but more costly if they are not positioned towards the start or the end of the list of events.

1.1.2. Applications

The timeline pattern is widely applicable but one of the most representative applications are probably status messages in social networks. The following is a list of possible applications of this pattern:

It is possible to use this pattern for logging. For instance in order to save the list of the latest pages visited by every user to analyze the user behaviours on the site.
An hypothetical implementation of Twitter may represent the user timeline using this pattern: every time an user tweets, the timeline of all the users following this user will be populated with the identifier of the new tweet (or with the tweet itself).
In a scientific application this pattern can be used to collect data from a sensor, retaining only the latest N samples, and discarding all the older entries.

In general every time we want to store a chronologically sorted sequence of events (from newer to older events), with a max number of elements limit, and we are usually interested in accessing the newer items in very short time, this pattern is a good fit.

1.1.3. Implementation

This pattern uses the Redis list type. The base implementation of this patterns uses LPUSH and LTRIM in order to store a new item in the timeline, and LRANGE in order to retrieve the latest N events from the timeline.

The LPUSH+LTRIM combination is used in order to insert the new element (LPUSH) while cutting the list at the specified size (LTRIM).

Example 1: Inserting a new event in the timeline, with max length of 100 events.

redis> LPUSH timeline newevent
(integer) 1
redis> LTRIM timeline 0 99
OK

Accessing elements is simply performed using LRANGE. Since elements are added using LPUSH newer elements are near the head of the list, so to fetch the latest newer elements, in reverse chronological order, we ned to issue the LRANGE timeline 0 9 command.

1.1.4. Variants

Depending on the application it is possible to either push the event data itself or just an integer referencing the event. For instance it is possible to use an hash to represent the event using a key named event:1234 and then pushing 1234 in the timeline.

The normalized representation is to prefer every time the event is duplicated among many timelines (or among different Redis values) or when the event is not immutable and needs to be modified.

An interesting and very used variant of this pattern does not send the LTRIM command every time an LPUSH is sent, but only when a given limit is reached. For instance if we are interested in 500 elements, we trim the list only when we reach 510 elements (the LPUSH command returns the number of elements inside the list, so no additional operation is needed to detect this condition). This variant allows to send just 10% of the LTRIM commands otherwise needed, with a minimal memory overhead.

It is worth noting that this pattern is also used for caching also.

Removing items

When normalization is used, storing just the ID of the event in the timeline, removed items can be handled simply deleting the key of the event, without altering the timeline itself (eventually this stale reference will be discareded as new entires arrive). The missing event will be handled at application level.

An alternative is to use the LREM command. However this command is executed in linear time: for small lists this is not an issue. For larger ones it is better to make sure that the element to remove is near the head of the list. Fortunately in most applicaitons the users tend to remove the newest elements, and rarely the oldest ones.

1.1.5. Example

class Timeline
    def initialize(redis,lowlevel,highlevel)
        @r = redis
        @lowlevel = lowlevel
        @highlevel = highlevel
    end

    def insert(list,event)
        count = @r.lpush(list,event)
        @r.ltrim(list,0,@lowlevel-1) if count >= @highlevel
    end

    def remove(list,event)
        @r.lrem(list,1,event)
    end

    def fetch(list,count=10,start=0)
        @r.lrange(list,start,start+count-1)
    end
end

# Usage
timeline = Timeline.new(Redis.new,100,110)
timeline.insert("foo")
timeline.insert("bar")
timeline.fetch(list)