GoCache: LRU Cache Implementation in Go

I got to know about Golang a year back and did write some toy programs 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 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 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. 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 arelocked down.