Cloning Memcached with Go

My first program in Go was Conway's Game of Life. This time I made an in-memory HTTP caching server.

I use caching pretty often but I had never coded up a Least Frequently Used (LRU) cache by hand before. Neither had I used Go's net/http or container/list packages. Both packages are elegant with great documentation and readable sourcecode the latter being one of my favorite things about Go.

With my first program, I threw everything in a file called main.go and called it a day. This time I used packages.

• api an HTTP server which responds to GET requests like /set?key=name&value=Andrew&expire=1571577784.
• cache an LRU cache that allows an expire time and a max number of keys.

Caching

As an LRU cache fills up and needs to forget an item it will choose the one that was last accessed the longest time ago. It also allows lookups in constant time. To build mine, I mapped strings to doubly linked list elements.

// Store contains an LRU Cachetype Store struct {    Mutex *sync.Mutex    store map[string]*list.Element    ll    *list.List    max   int // Zero for unlimited}

Each list element is a Node with the following fields.

// Node maps a value to a keytype Node struct {    value   string    expire  int  // Unix time    deleted bool // Whether this should be cleaned up}

The Mutex field of the Store is capitalized so it can be exported. I wrote the cache to be generic and some clients might not require a mutual exclusion object. In my case, it is required because while maps are okay with concurrent readers they should not have concurrent writers. The default behavior of net/http is to spawn a goroutine for every request.

I have a different route for every method and to avoid duplicate code I used middleware. It takes a handler function and makes sure that the global Store object is locked while the cache is manipulated. In larger applications, things like authentication and logging would go here too.

// Middlewarefunc handle(f func(http.ResponseWriter, *http.Request)) func(w http.ResponseWriter, r *http.Request) {    return func(w http.ResponseWriter, r *http.Request) {        s.Mutex.Lock()        defer s.Mutex.Unlock()        f(w, r)    }}

I've been reaching for defer in my other programming languages recently. It helps one better manage the lifetime of objects. It's explained in a Go blog post.

Defer statements allow us to think about closing each file right after opening it, guaranteeing that, regardless of the number of return statements in the function, the files will be closed.

The middleware is applied like this.

http.HandleFunc("/set", handle(Set))

Give key, get value

In Go, the HTTP protocol is a first-class citizen. Clients and servers are simple (and extensible). Writing the /get method for my server uses six lines.

// Get a key from the store// Status code: 200 if present, else 404// e.g. ?key=foofunc Get(w http.ResponseWriter, r *http.Request) {    value, exist := s.Get(r.URL.Query().Get("key"))    if !exist {        http.Error(w, "", 404)        return    }    w.Header().Set("content-type", "text/plain")    w.Write([]byte(value))}

The cache method that maps to this route is more complex. It looks for a key in the map and checks that it is valid (not expired or due for cleanup). It returns (string, bool) (the value or an empty string, true if the value was found). If a string is found, its Node is moved to the front of the list because it is now the most recently accessed.

If the key is expired or is due for deletion (to-be-deleted keys have their Node's fields set to zero values to save space) then it's passed to the delete method which will remove the key from the map and the Node will be passed to the garbage collector.

// Get a keyfunc (s *Store) Get(key string) (string, bool) {    current, exist := s.store[key]    if exist {        expire := int64(current.Value.(*Node).expire)        if current.Value.(*Node).deleted != true && (expire == 0 || expire > time.Now().Unix()) {            s.ll.MoveToFront(current)            return current.Value.(*Node).value, true        }        s.Delete(key) // Clean up item    }    return "", false}

Insert into cache

Putting something into the cache means either creating a new Node at the front of the list or updating the details of a pre-existing Node and moving it to the front of the list. If we are at the maximum number of keys then as we create, we flag our least frequently accessed Node for deletion.

The expire parameter is optional.

// Set a keyfunc (s *Store) Set(key string, value string, expire int) {    current, exist := s.store[key]    if exist != true {        s.store[key] = s.ll.PushFront(&Node{            value:  value,            expire: expire,        })        if s.max != 0 && s.ll.Len() > s.max {            toBeZeroed := s.ll.Remove(s.ll.Back()).(*Node)            toBeZeroed.value = ""            toBeZeroed.deleted = true        }        return    }    current.Value.(*Node).value = value    current.Value.(*Node).expire = expire    s.ll.MoveToFront(current)}

All other cache methods use Get and Set to avoid duplication of code.

When removing all keys from the cache we can lean on the garbage collector to do the hard stuff for us by removing all existing references to the objects.

// Flush all keysfunc (s *Store) Flush() {    s.store = make(map[string]*list.Element)    s.ll = list.New()}

The full list of methods is Set, Get, Delete, CheckAndSet, Increment, Decrement, Append, Prepend, Flush, and Stats.

This project took me two Sunday mornings and I continue to warm towards Go. It's not as terse as other languages but remains easy to read. It tends to lead to vertical code as opposed to horizontal code which also aids readability. It also brings all of the benefits of a static language without requiring a lot of boilerplate.

So far, I've had a great 'Google experience' alongside my Go programming. Looking up solutions normally leads to a sensible and well-explained answer. When I'm heading in the wrong direction, I normally find out after searching rather than running into problems further down the line. But perhaps this is because the language is quite new and there are less results for the incorrect version!

Check out the code on GitHub.

I post unique content to my weekly newsletter !

And tweet about tech @healeycodes.