GoCache: LRU Cache Implementation in Go
Tags: posts, go
Published: 2020-04-04 15:00:31

---
title: GoCache: LRU Cache Implementation in Go
published: true
date: 2020-03-31 13:35:44 UTC
tags: Posts,Golang
canonical_url: http://blog.adnansiddiqi.me/gocache-lru-cache-implementation-in-go/
---

I got to know about Golang a year back and did write some [toy programs](http://blog.adnansiddiqi.me/tag/golang) in it while learning but then I gave up as I was not really enjoying despite liking Go language. It is very much like Python but with better performance because it’s compiled.

Recently I against wished to do something in Go. This time I did not want to go back to practice topic by topic. I rather thought to do some _project_ and will learn whatever the stuff I need to get the thing done.

I have used [Memcached](https://memcached.org/) in the past in PHP and really liked it so I thought to come up with a cache mechanism in Go. Upon learning I found out that Memcached has used the [LRU](https://en.wikipedia.org/wiki/Cache_replacement_policies) cache technique. I had a couple of challenges:

- Learning Go to do my stuff. Especially about structs, pointers, and maps.
- Understanding LRU implementation.

It was not easy, but I pushed anyway to progress. I found a few implementations in Python and Java. I did not want to see any Go implementation as it could kill the entire purpose. After a month or so I was able to come up with an implementation consist of a couple of files.

```
/\*- Set: Add the item both in queue and HashMap. If they capacity is full, it removes the least recently usedelement- Get: Returns the item requested via Key. On querying the item it comes to forward of the queue\*/package mainimport ("container/list""errors""fmt")var queue = list.New()var m = make(map[string]string)/\*Cache struct\*/type Cache struct {capacity int}/\*CacheItem Struct\*/type CacheItem struct {Name stringValue string}// Move the list item to frontfunc moveListElement(k string) {for e := queue.Front(); e != nil; e = e.Next() {if e.Value.(CacheItem).Name == k {queue.MoveToFront(e)break}}}func (cache \*Cache) print() {fmt.Println("Printing Queue Items")// Iterate through list and print its contents.for e := queue.Front(); e != nil; e = e.Next() {fmt.Println(e.Value.(CacheItem).Name)}}func (cache \*Cache) set(key string, val string) string {//Search the key in map\_, found := m[key]if !found {//Check the capacityif len(m) == cache.capacity { // Time to evict// Get the least use item from the queuee := queue.Back()queue.Remove(e) // DequeuekeyName := e.Value.(CacheItem).Name// Delete from the mapdelete(m, keyName)} else {//There is still some roomitem := CacheItem{Name: key, Value: val}queue.PushFront(item)m[key] = val}}return "1"}func (cache \*Cache) get(k string) (string, error) {//Search the key in mapv, found := m[k]if found {v := m[k]//fmt.Println(v)moveListElement(v)return v, nil}v = "-1"return v, errors.New("Key not found")}
```

and…

```
package mainimport ("bufio""flag""fmt""net""regexp""strings")/\*This function will process the command and execute relevant LRU methods\*/func processCommand(c string, gc Cache) string {var result stringvar er errorvar pattern = ""if strings.Index(strings.ToLower(c), "get") > -1 {pattern = `(?i)GET\s+(\w+)`} else if strings.Index(strings.ToLower(c), "set") > -1 {pattern = `(?i)SET\s(\w+)\s(\w+)`}// TODO: Based on results call Cache Methodsvar re = regexp.MustCompile(pattern)matches := re.FindAllStringSubmatch(c, -1)if len(matches) > 0 {// For GET commandif len(matches[0]) == 2 {key := matches[0][1]result, er = gc.get(key)if er != nil {result = er.Error()}} else if len(matches[0]) == 3 {key := matches[0][1]val := matches[0][2]result = gc.set(key, val)//gc.print()}}return result}func validateCommand(cmd string) bool {var msg bool//Split the command to make sure it is not more than 2 or 3cmdArray := strings.Split(cmd, " ")if len(cmdArray) > 3 {msg = false} else if (len(cmdArray) == 2) && (strings.TrimSpace(strings.ToLower(cmdArray[0])) != "get") {msg = false} else if len(cmdArray) == 3 && strings.ToLower(cmdArray[0]) != "set" {msg = false} else if len(cmdArray) == 3 && strings.ToLower(cmdArray[0]) == "set" {msg = true} else if len(cmdArray) == 2 && strings.ToLower(cmdArray[0]) == "get" {msg = true}return msg}func handleConnection(c net.Conn, gc Cache) {fmt.Printf("Serving %s\n", c.RemoteAddr().String())for {netData, err := bufio.NewReader(c).ReadString('\n')if err != nil {fmt.Println(err)return}temp := strings.TrimSpace(string(netData))if validateCommand(temp) {outcome := processCommand(temp, gc)c.Write([]byte(string(outcome + "\n")))} else {c.Write([]byte(string("Invalid Command\n")))}//fmt.Println(z)if temp == "\\q" {break}}c.Close()}func main() {portArg := flag.String("port", "9000", "GoCached Server Port")capacityArg := flag.Int("capacity", 5, "Capacity of the cache")flag.Parse()PORT := ":" + \*portArgfmt.Printf("Launching server at port %s with the capacity %d \n", \*portArg, \*capacityArg)//os.Exit(0)var gCache = Cache{\*capacityArg}// listen on all interfacesconnection, err := net.Listen("tcp4", PORT)if err != nil {fmt.Println(err)return}defer connection.Close()for {c, err := connection.Accept()if err != nil {fmt.Println(err)return}go handleConnection(c, gCache)}}
```

`lru.go` consist of main implementation while `gocached.go` calls the stuff from `lru.go` along with initialization a socket server.

The code is pushed on [Github](https://github.com/kadnan/GoCache). Some kind guy did a code review and came up with his own professional implementation which I merged in `master`.(The beautify of Opensource) therefore I dumped the original crappy code here. You are free to fork and play/improve it.

I am still a newbie but definitely, a great journey to learn something new, especially when we all are[locked down](http://lockdown).