LRU Cache implementation with concurrent cleaning based on ttl

lru_cache_main.go

package main

import (
	"context"
	"encoding/json"
	"fmt"
	"log"
	"math"
	"math/rand"
	"sync"
	"time"
)

type item struct {
	Key    string
	Val    string
	UsedAt time.Time
}

type LruCache struct {
	mu     sync.Mutex
	ctx    context.Context
	cancel context.CancelFunc

	cap           int
	items         []*item
	cleanInterval time.Duration
}

func NewLRUCache(n int, interval time.Duration) *LruCache {
	ctx, cancel := context.WithCancel(context.Background())
	c := &LruCache{
		cap:           n,
		items:         []*item{},
		ctx:           ctx,
		cancel:        cancel,
		cleanInterval: interval,
	}
	go clean(c)
	return c
}

const cleanDuration = 1 * time.Second

func clean(c *LruCache) {
	ontick := func(tick time.Time) {
		c.mu.Lock()
		defer c.mu.Unlock()
		if time.Since(tick) >= 999*time.Millisecond {
			log.Println("could not aquire the lock in around a second")
			return
		}

		n := len(c.items)
		size := 1000
		cparts := int(math.Ceil(float64(n) / float64(size)))
		newCacheItems := make([][]*item, cparts)
		var j int
		var wg sync.WaitGroup
		for i := 0; i < n; i += size {
			j += size
			if j > n {
				j = n
			}
			wg.Add(1)
			go func(x, y int) {
				defer wg.Done()
				var cpart []*item
				copy(cpart, c.items[x:y])
				for i := 0; i < len(cpart); i++ {
					e := cpart[i]
					at := i
					if time.Since(e.UsedAt) >= c.cleanInterval {
						cpart = append(cpart[:at], cpart[at+1:]...)
					}
				}
				newCacheItems[int(math.Ceil(float64(x)/float64(size)))] = cpart
			}(i, j)
		}
		wg.Wait()
		var output []*item
		for _, v := range newCacheItems {
			output = append(output, v...)
		}
		c.items = output
	}

	ticker := time.NewTicker(cleanDuration)
	for {
		select {
		case tick := <-ticker.C:
			go ontick(tick)
		case <-c.ctx.Done():
			return
		}
	}
}

func (c *LruCache) PauseCleaning() {
	c.cancel()
}

func (c *LruCache) ResumeCleaning() {
	if c.ctx.Err() == nil {
		return
	}
	ctx, cancel := context.WithCancel(context.Background())
	c.ctx = ctx
	c.cancel = cancel

	go clean(c)
}

func (c *LruCache) String() string {
	buf, _ := json.Marshal(c.items)
	return string(buf)
}

func (c *LruCache) Get(key string) string {
	var j int
	n := len(c.items)
	size := 1000
	slices := int(math.Ceil(float64(n) / float64(size)))
	result := make(chan *item, slices)
	for i := 0; i < n; i += size {
		j += size
		if j > n {
			j = n
		}
		go func(x, y int) {
			cpart := c.items[x:y]
			for i := 0; i < len(cpart); i++ {
				at := i
				e := c.items[at]
				if e.Key == key {
					func() {
						c.mu.Lock()
						defer c.mu.Unlock()

						c.items = append(c.items[:at], c.items[at+1:]...)
						e.UsedAt = time.Now()
						c.items = append(c.items, e)
						result <- e
					}()
					return
				}
			}
			result <- nil
		}(i, j)
	}

	for i := 0; i < slices; i++ {
		v := <-result
		if v != nil {
			return v.Val
		}
	}
	return "-1"
}

func (c *LruCache) Put(key, val string) {
	c.mu.Lock()
	defer c.mu.Unlock()

	exits := func(key string) (int, bool) {
		size := 1000
		n := len(c.items)
		slices := int(math.Ceil(float64(n) / float64(size)))
		result := make(chan *int, slices)
		var j int
		for i := 0; i < n; i += size {
			j += size
			if j > n {
				j = n
			}
			go func(x, y int) {
				cpart := c.items[x:y]
				for i := 0; i < len(cpart); i++ {
					at := i
					e := c.items[at]
					if e.Key == key {
						result <- &i
						return
					}
				}
				result <- nil
			}(i, j)
		}
		for i := 0; i < slices; i++ {
			v := <-result
			if v != nil {
				return *v, true
			}
		}
		return 0, false
	}

	at, e := exits(key)
	if e {
		item := c.items[at]
		item.UsedAt = time.Now()
		c.items = append(c.items[:at], c.items[at+1:]...)
		c.items = append(c.items, item)
	} else {
		item := &item{
			key,
			val,
			time.Now(),
		}
		if len(c.items) == c.cap {
			c.items = append(c.items[1:], item)
		} else {
			c.items = append(c.items, item)
		}
	}
}

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func randSeq(n int) string {
	b := make([]rune, n)
	for i := range b {
		b[i] = letters[rand.Intn(len(letters))]
	}
	return string(b)
}

func main() {
	cache := NewLRUCache(1000000, 10*time.Second)
	cache.Put("foo", "bar")
	cache.Put("john", "doe")
	cache.Put("john1", "doe")
	cache.Put("john2", "doe")
	cache.Put("john3", "doe")
	cache.Put("john4", "doe")
	cache.Put("john5", "doe")

	fmt.Println(cache.Get("foo"))
	rand.Seed(time.Now().UnixNano())
	for i := 0; i < 999990; i++ {
		k := randSeq(5)
		v := randSeq(5)
		cache.Put(k, v)
	}

	cache.Put("test", "123")
	fmt.Println(cache.Get("john")) // -1

	cache.Put("city", "Blore")
	fmt.Println(cache.Get("foo")) // -1

	time.Sleep(12 * time.Second)
	fmt.Println(cache)
	fmt.Println(cache.Get("test")) // -1
	fmt.Println(cache.Get("city")) // -1
}