Skip to content

Instantly share code, notes, and snippets.

@malisetti
Last active August 5, 2022 14:21
Show Gist options
  • Save malisetti/32f8b4dba4240521f2ee459f5cf12df2 to your computer and use it in GitHub Desktop.
Save malisetti/32f8b4dba4240521f2ee459f5cf12df2 to your computer and use it in GitHub Desktop.
LRU Cache implementation with concurrent cleaning based on ttl
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment