Making Timed Maps in Go

Making an efficient, concurrency-safe maps with TTL in Golang

Many of today’s web apps requires some sort of a super fast data storage mechanisms for achieveing various types of features regarding Authentication, Authorization, Rate-limitting and Caching, just to name a few.

Solutions such as Redis, Aerospike …etc are great, but these solutions may come with an overhead in case that your usecase doesn’t really requires that much of the features they introduce when you really just want something that is simple and gets the job done.. So, let’s build our own !

Our solution is a simple map[string]interface{} with a wrapper to implement the features we want

    type TimedMap struct {
        m map[string]interface{}
    }

As you might have heard earlier, maps in Go are not concurrency-safe, that is if multiple goroutines try to access a map (Read/Write), this will produce what is known as a data race error

Maps are not safe for concurrent use: it’s not defined what happens when you read and write to them simultaneously. If you need to read from and write to a map from concurrently executing goroutines, the accesses must be mediated by some kind of synchronization mechanism. (https://blog.golang.org/go-maps-in-action)

Now this can be solved in many ways, the simplest is to use Mutex.

A Mutex is a mutual exclusion lock. The zero value for a Mutex is an unlocked mutex. (…) If the lock is already in use, the calling goroutine blocks until the mutex is available. (https://golang.org/pkg/sync/#Mutex)

Using mutexes in Go is actually very easy, let’s add a mutex to our TimedMap struct for now to use it later.

    type TimedMap struct {
        m map[string]interface{}
        mu *sync.Mutex
    }

We want to make the values in our map temporary with a TTL, this means we need to attach an expiration date with every Key-Value.

Though this can be implemented in various ways, but I’ll try to keep it as simple as possible. Instead of using interface{} type for the map values, I’ll use the following simple struct:

    type element struct {
        Value interface{}
        ExpiresAt int64
    }

type element struct will hold the actual value we want to store and an expiration date represented in a Unix-timestamp just for the sake of simplicity.

    type TimedMap struct {
        m map[string]*element
        mu *sync.Mutex
    }

Now for every key we’ll have a corrosponding Value/Expiration pair.

Let’s implement a method for setting date to our TimedMap

    func (tm *TimedMap) SetTemporary(key string, value interface{}, expirationDate time.Time) {

        // locking the mutex before writing the date
        tm.mu.Lock()

        // setting the new value
        tm.m[key] = &element {
            Value: value,
            ExpiresAt: expirationDate.Unix(),
        }

        // don't forget to unlock the mutex
        tm.mu.Unlock()
    }

and a method for retrieving a value from the map and a bool which indicates whether the value actually exists or not.

    func (tm *TimedMap) Get(key) (interface{}, bool) {
        tm.mu.RLock()
        e := tm.m[key]
        tm.mu.RUnlock()

        if v == nil {
            return nil, false
        }

        return e.Value, true
    }

notice that in Get method I’ve used mu.RLock() and mu.RUnlock(), which are mutex locking and unlocking mechanisms made to be used for synchronizing readers goroutines of our map. Read more on Mutexes.

So far everything is fairly simple. We need to make our Timed Map automatically CLEAN expired values, for this let’s use time.Ticker and a new goroutine, time.Ticker sends a value over channel every X unit of time of our choice. So when ever the Ticker “ticks” it will trigger a cleaning operation which is simply iterating over our map and comparing each value, if it’s expired, we delete it, if not, leave it as it is.

A Ticker holds a channel that delivers `ticks’ of a clock at intervals. (https://golang.org/pkg/time/#Ticker ).

first let’s modify TimedMap struct to add a ticker, and a channel to help us STOP the ticker if needed:

    type TimedMap struct {
        m map[string]*element
        mu *sync.Mutex

        cleaningTicker *time.Ticker
        cleaningTickerStop chan bool
    }

Next, let’s implement the cleaning procedure:

    func (tm *TimedMap) clean() {
        // current time in unix-timestamp
        now := time.Now().Unix()

        // lock the map for writting (deleting expired values)
        tm.mu.Lock()

        // iterating over the map
        for key, el := range tm.m {
            if now >= el.ExpiresAt { 
                delete(tm.m, key)
            }
        }

        // releasing the lock
        tm.mu.Unlock()
    }

now let’s implement a method for starting the cleaner:

    func (tm *TimedMap) StartCleaner() {

        // spawn a new goroutine
        go func() {
            for {
                select {
                    case <- tm.cleanerTicker.C: // a new tick
                    tm.clean()
                    case <- tm.cleaningTickerStop: // stopping the cleaner
                    break
                }
            }
        }()
    }

We’ve implemented a very simple Timed Map which is concurrency-safe and has a cleaner for cleaning expired values & methods for setting and getting values, now let’s implement the initilizing function:

    func NewTimedMap(cleaningInterval time.Duration) *TimedMap {
        t := &TimedMap{
            m: map[string]*elemet{}, // an empty map
            mu: &sync.RWMutex{}, // a mutex
            cleaningTicker: time.NewTicker(cleaningInterval), // a ticker
            cleaningTickerStop: make(chan bool), // channel for stopping the ticker
        }

        // starting the cleaner
        t.StartCleaning()

        return t
    }

By now everything is done and as simple as possible, I’ve a created a package for this lesson, please note that the package has some added features & API, but really it all breaks down to the above code blocks, please check it for Usage instructions, PRs are welcome !

Package: firasdarwish/temap
go  temap  backend 

comments powered by Disqus