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.
lru.go
/*
— Set: Add the item both in queue and HashMap. If they capacity is full, it removes the least recently used
element- 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 string
Value string
}// Move the list item to front
func 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 capacity
if len(m) == cache.capacity { // Time to evict
// Get the least use item from the queue
e := queue.Back()
queue.Remove(e) // Dequeue
keyName := e.Value.(CacheItem).Name
// Delete from the map
delete(m, keyName)
} else {
//There is still some room
item := 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 map
v, 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 gocached.go
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 string
var er error
var 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 command
if 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 3
cmdArray := 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 := “:” + *portArg
fmt.Printf(“Launching server at port %s with the capacity %d \n”, *portArg, *capacityArg)
//os.Exit(0)
var gCache = Cache{*capacityArg}// listen on all interfaces
connection, 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 the main implementation while gocached.go calls the stuff from lru.go along with initialization of 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 are locked down.
Originally published at http://blog.adnansiddiqi.me on March 31, 2020.
