diff options
author | Marc Pervaz Boocha <marcpervaz@qburst.com> | 2025-02-21 18:24:35 +0530 |
---|---|---|
committer | Marc Pervaz Boocha <marcpervaz@qburst.com> | 2025-02-21 18:24:35 +0530 |
commit | a470aa89cbdabba813636b8a29be8ae3836c03a0 (patch) | |
tree | 2551bebaff980cc93bf8fcf60dd8ff50bd7efc48 /store.go | |
parent | Add Tests and benchmarks (diff) | |
download | cache-a470aa89cbdabba813636b8a29be8ae3836c03a0.tar cache-a470aa89cbdabba813636b8a29be8ae3836c03a0.tar.gz cache-a470aa89cbdabba813636b8a29be8ae3836c03a0.tar.bz2 cache-a470aa89cbdabba813636b8a29be8ae3836c03a0.tar.lz cache-a470aa89cbdabba813636b8a29be8ae3836c03a0.tar.xz cache-a470aa89cbdabba813636b8a29be8ae3836c03a0.tar.zst cache-a470aa89cbdabba813636b8a29be8ae3836c03a0.zip |
Added LTR Eviction
Diffstat (limited to 'store.go')
-rw-r--r-- | store.go | 235 |
1 files changed, 235 insertions, 0 deletions
diff --git a/store.go b/store.go new file mode 100644 index 0000000..f4ba952 --- /dev/null +++ b/store.go @@ -0,0 +1,235 @@ +package cache + +import ( + "bytes" + "sync" + "time" + + "github.com/marcthe12/cache/internal/pausedtimer" +) + +const initialBucketSize uint64 = 8 + +type node struct { + Hash uint64 + Expiration time.Time + Access uint64 + Key []byte + Value []byte + HashNext *node + HashPrev *node + EvictNext *node + EvictPrev *node +} + +func (n *node) IsValid() bool { + return n.Expiration.IsZero() || n.Expiration.After(time.Now()) +} + +func (n *node) TTL() time.Duration { + if n.Expiration.IsZero() { + return 0 + } else { + return time.Until(n.Expiration) + } +} + +type store struct { + Bucket []node + Length uint64 + Cost uint64 + Evict node + MaxCost uint64 + SnapshotTicker *pausedtimer.PauseTimer + CleanupTicker *pausedtimer.PauseTimer + Policy evictionPolicy + mu sync.Mutex +} + +func (s *store) Init() { + s.Clear() + s.Policy.evict = &s.Evict + s.SnapshotTicker = pausedtimer.NewStopped(0) + s.CleanupTicker = pausedtimer.NewStopped(10 * time.Second) + s.Policy.SetPolicy(PolicyNone) +} + +func (s *store) Clear() { + s.mu.Lock() + defer s.mu.Unlock() + + s.Bucket = make([]node, initialBucketSize) + s.Length = 0 + s.Cost = 0 + + s.Evict.EvictNext = &s.Evict + s.Evict.EvictPrev = &s.Evict +} + +func lookup(s *store, key []byte) (uint64, uint64) { + hash := hash(key) + return hash % uint64(len(s.Bucket)), hash +} + +func lazyInitBucket(n *node) { + if n.HashNext == nil { + n.HashNext = n + n.HashPrev = n + } +} + +func (s *store) lookup(key []byte) (*node, uint64, uint64) { + idx, hash := lookup(s, key) + + bucket := &s.Bucket[idx] + + lazyInitBucket(bucket) + + for v := bucket.HashNext; v != bucket; v = v.HashNext { + if bytes.Equal(key, v.Key) { + return v, idx, hash + } + } + + return nil, idx, hash +} + +func (s *store) get(key []byte) ([]byte, time.Duration, bool) { + v, _, _ := s.lookup(key) + if v != nil { + if !v.IsValid() { + deleteNode(s, v) + return nil, 0, false + } + s.Policy.OnAccess(v) + return v.Value, v.TTL(), true + } + + return nil, 0, false +} + +func (s *store) Get(key []byte) ([]byte, time.Duration, bool) { + s.mu.Lock() + defer s.mu.Unlock() + + return s.get(key) +} + +func resize(s *store) { + bucket := make([]node, 2*len(s.Bucket)) + + for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext { + if !v.IsValid() { + deleteNode(s, v) + continue + } + idx := v.Hash % uint64(len(bucket)) + + n := &bucket[idx] + lazyInitBucket(n) + + v.HashPrev = n + v.HashNext = v.HashPrev.HashNext + v.HashNext.HashPrev = v + v.HashPrev.HashNext = v + } + + s.Bucket = bucket +} + +func cleanup(s *store) { + for v := s.Evict.EvictNext; v != &s.Evict; v = v.EvictNext { + if !v.IsValid() { + deleteNode(s, v) + } + } +} + +func evict(s *store) bool { + for s.MaxCost != 0 && s.MaxCost < s.Cost { + n := s.Policy.Evict() + if n == nil { + break + } + deleteNode(s, n) + } + return true +} + +func (s *store) set(key []byte, value []byte, ttl time.Duration) { + v, idx, hash := s.lookup(key) + if v != nil { + s.Cost = s.Cost + uint64(len(value)) - uint64(len(v.Value)) + v.Value = value + v.Expiration = time.Now().Add(ttl) + s.Policy.OnUpdate(v) + } + + bucket := &s.Bucket[idx] + if float64(s.Length)/float64(len(s.Bucket)) > 0.75 { + resize(s) + //resize may invidate pointer to bucket + _, idx, _ := s.lookup(key) + bucket = &s.Bucket[idx] + lazyInitBucket(bucket) + } + + node := &node{ + Hash: hash, + Key: key, + Value: value, + } + + if ttl != 0 { + node.Expiration = time.Now().Add(ttl) + } + + node.HashPrev = bucket + node.HashNext = node.HashPrev.HashNext + node.HashNext.HashPrev = node + node.HashPrev.HashNext = node + + s.Policy.OnInsert(node) + + s.Cost = s.Cost + uint64(len(key)) + uint64(len(value)) + s.Length = s.Length + 1 +} + +func (s *store) Set(key []byte, value []byte, ttl time.Duration) { + s.mu.Lock() + defer s.mu.Unlock() + + s.set(key, value, ttl) +} + +func deleteNode(s *store, v *node) { + v.HashNext.HashPrev = v.HashPrev + v.HashPrev.HashNext = v.HashNext + v.HashNext = nil + v.HashPrev = nil + + v.EvictNext.EvictPrev = v.EvictPrev + v.EvictPrev.EvictNext = v.EvictNext + v.EvictNext = nil + v.EvictPrev = nil + + s.Cost = s.Cost - (uint64(len(v.Key)) + uint64(len(v.Value))) + s.Length = s.Length - 1 +} + +func (s *store) delete(key []byte) bool { + v, _, _ := s.lookup(key) + if v != nil { + deleteNode(s, v) + return true + } + + return false +} + +func (s *store) Delete(key []byte) bool { + s.mu.Lock() + defer s.mu.Unlock() + + return s.delete(key) +} |