diff options
| -rw-r--r-- | conn.go | 39 | ||||
| -rw-r--r-- | evict.go | 147 | ||||
| -rw-r--r-- | evict_test.go | 213 | ||||
| -rw-r--r-- | go.mod | 7 | ||||
| -rw-r--r-- | go.sum | 43 | ||||
| -rw-r--r-- | internal/pausedtimer/timer.go | 54 | ||||
| -rw-r--r-- | internal/pausedtimer/timer_test.go (renamed from utils_test.go) | 12 | ||||
| -rw-r--r-- | store.go (renamed from map.go) | 28 | ||||
| -rw-r--r-- | store_test.go (renamed from map_test.go) | 45 | ||||
| -rw-r--r-- | utils.go | 50 |
10 files changed, 432 insertions, 206 deletions
@@ -7,16 +7,15 @@ import ( "sync" "time" - "github.com/vmihailenco/msgpack" + "github.com/rogpeppe/go-internal/lockedfile" + "github.com/vmihailenco/msgpack/v5" ) type db struct { - File io.WriteSeeker - Store store - SnapshotTicker *pauseTimer - CleanupTicker *pauseTimer - Stop chan struct{} - wg sync.WaitGroup + File io.WriteSeeker + Store store + Stop chan struct{} + wg sync.WaitGroup } type Option func(*db) error @@ -26,7 +25,7 @@ func openFile(filename string, options ...Option) (*db, error) { if err != nil { return nil, err } - file, err := os.OpenFile(filename, os.O_RDWR|os.O_CREATE, 0666) + file, err := lockedfile.OpenFile(filename, os.O_RDWR|os.O_CREATE, 0666) if err != nil { return nil, err } @@ -49,10 +48,7 @@ func openFile(filename string, options ...Option) (*db, error) { } func openMem(options ...Option) (*db, error) { - ret := &db{ - SnapshotTicker: newPauseTimerStopped(0), - CleanupTicker: newPauseTimerStopped(10 * time.Second), - } + ret := &db{} ret.Store.Init() ret.SetConfig(options...) return ret, nil @@ -65,6 +61,9 @@ func (d *db) Start() { } func (d *db) SetConfig(options ...Option) error { + d.Store.mu.Lock() + defer d.Store.mu.Unlock() + for _, opt := range options { if err := opt(d); err != nil { return err @@ -88,14 +87,14 @@ func WithMaxCost(maxCost uint64) Option { func SetSnapshotTime(t time.Duration) Option { return func(d *db) error { - d.SnapshotTicker.Reset(t) + d.Store.SnapshotTicker.Reset(t) return nil } } func SetCleanupTime(t time.Duration) Option { return func(d *db) error { - d.CleanupTicker.Reset(t) + d.Store.CleanupTicker.Reset(t) return nil } } @@ -103,19 +102,19 @@ func SetCleanupTime(t time.Duration) Option { func (d *db) backgroundWorker() { defer d.wg.Done() - d.SnapshotTicker.Resume() - defer d.SnapshotTicker.Stop() + d.Store.SnapshotTicker.Resume() + defer d.Store.SnapshotTicker.Stop() - d.CleanupTicker.Resume() - defer d.CleanupTicker.Stop() + d.Store.CleanupTicker.Resume() + defer d.Store.CleanupTicker.Stop() for { select { case <-d.Stop: return - case <-d.SnapshotTicker.C: + case <-d.Store.SnapshotTicker.C: d.Flush() - case <-d.CleanupTicker.C: + case <-d.Store.CleanupTicker.C: cleanup(&d.Store) evict(&d.Store) } @@ -1,6 +1,8 @@ package cache -import "errors" +import ( + "errors" +) // EvictionPolicyType defines the type of eviction policy. type EvictionPolicyType int @@ -16,6 +18,7 @@ const ( // evictionStrategies interface defines the methods for eviction strategies. type evictionStrategies interface { OnInsert(n *node) + OnUpdate(n *node) OnAccess(n *node) Evict() *node } @@ -27,14 +30,21 @@ type evictionPolicy struct { evict *node } +func pushEvict(node *node, sentinnel *node) { + node.EvictPrev = sentinnel + node.EvictNext = node.EvictPrev.EvictNext + node.EvictNext.EvictPrev = node + node.EvictPrev.EvictNext = node +} + // SetPolicy sets the eviction policy based on the given type. func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error { store := map[EvictionPolicyType]func() evictionStrategies{ PolicyNone: func() evictionStrategies { - return nonePolicy{evict: e.evict} + return fifoPolicy{evict: e.evict, shouldEvict: false} }, PolicyFIFO: func() evictionStrategies { - return fifoPolicy{evict: e.evict} + return fifoPolicy{evict: e.evict, shouldEvict: true} }, PolicyLRU: func() evictionStrategies { return lruPolicy{evict: e.evict} @@ -42,6 +52,9 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error { PolicyLFU: func() evictionStrategies { return lfuPolicy{evict: e.evict} }, + PolicyLTR: func() evictionStrategies { + return ltrPolicy{evict: e.evict} + }, } factory, ok := store[y] if !ok { @@ -51,48 +64,28 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error { return nil } -// nonePolicy struct represents the no eviction policy. -type nonePolicy struct { - evict *node -} - -// OnInsert adds a node to the eviction list. -func (s nonePolicy) OnInsert(node *node) { - node.EvictPrev = s.evict - node.EvictNext = node.EvictPrev.EvictNext - node.EvictNext.EvictPrev = node - node.EvictPrev.EvictNext = node -} - -// OnAccess is a no-op for nonePolicy. -func (nonePolicy) OnAccess(n *node) { -} - -// Evict returns nil for nonePolicy. -func (nonePolicy) Evict() *node { - return nil -} - // fifoPolicy struct represents the First-In-First-Out eviction policy. type fifoPolicy struct { - evict *node + evict *node + shouldEvict bool } // OnInsert adds a node to the eviction list. func (s fifoPolicy) OnInsert(node *node) { - node.EvictPrev = s.evict - node.EvictNext = node.EvictPrev.EvictNext - node.EvictNext.EvictPrev = node - node.EvictPrev.EvictNext = node + pushEvict(node, s.evict) } // OnAccess is a no-op for fifoPolicy. func (fifoPolicy) OnAccess(n *node) { } +// OnUpdate is a no-op for fifoPolicy. +func (fifoPolicy) OnUpdate(n *node) { +} + // Evict returns the oldest node for fifoPolicy. func (s fifoPolicy) Evict() *node { - if s.evict.EvictPrev != s.evict { + if s.shouldEvict && s.evict.EvictPrev != s.evict { return s.evict.EvictPrev } else { return nil @@ -106,21 +99,18 @@ type lruPolicy struct { // OnInsert adds a node to the eviction list. func (s lruPolicy) OnInsert(node *node) { - node.EvictPrev = s.evict - node.EvictNext = node.EvictPrev.EvictNext - node.EvictNext.EvictPrev = node - node.EvictPrev.EvictNext = node + pushEvict(node, s.evict) +} + +func (s lruPolicy) OnUpdate(node *node) { + s.OnAccess(node) } // OnAccess moves the accessed node to the front of the eviction list. func (s lruPolicy) OnAccess(node *node) { node.EvictNext.EvictPrev = node.EvictPrev node.EvictPrev.EvictNext = node.EvictNext - - node.EvictPrev = s.evict - node.EvictNext = node.EvictPrev.EvictNext - node.EvictNext.EvictPrev = node - node.EvictPrev.EvictNext = node + s.OnInsert(node) } // Evict returns the least recently used node for lruPolicy. @@ -139,11 +129,12 @@ type lfuPolicy struct { // OnInsert adds a node to the eviction list and initializes its access count. func (s lfuPolicy) OnInsert(node *node) { - node.EvictPrev = s.evict - node.EvictNext = node.EvictPrev.EvictNext - node.EvictNext.EvictPrev = node - node.EvictPrev.EvictNext = node - node.Access = 0 + pushEvict(node, s.evict) +} + +// OnUpdate increments the access count of the node and reorders the list. +func (s lfuPolicy) OnUpdate(node *node) { + s.OnAccess(node) } // OnAccess increments the access count of the node and reorders the list. @@ -179,3 +170,69 @@ func (s lfuPolicy) Evict() *node { return nil } } + +// ltrPolicy struct represents the Least Remaining Time eviction policy. +type ltrPolicy struct { + evict *node + evictZero bool +} + +// OnInsert adds a node to the eviction list based on its TTL (Time To Live). +// It places the node in the correct position in the list based on TTL. +func (s ltrPolicy) OnInsert(node *node) { + pushEvict(node, s.evict) + + s.OnUpdate(node) +} + +// OnAccess is a no-op for ltrPolicy. +// It does not perform any action when a node is accessed. +func (s ltrPolicy) OnAccess(node *node) { +} + +// OnUpdate updates the position of the node in the eviction list based on its TTL. +// It reorders the list to maintain the correct order based on TTL. +func (s ltrPolicy) OnUpdate(node *node) { + if node.TTL() == 0 { + return + } + for v := node.EvictPrev; v.EvictPrev != s.evict; v = v.EvictPrev { + if v.TTL() == 0 { + continue + } + if v.TTL() < node.TTL() { + node.EvictNext.EvictPrev = node.EvictPrev + node.EvictPrev.EvictNext = node.EvictNext + + node.EvictPrev = v + node.EvictNext = node.EvictPrev.EvictNext + node.EvictNext.EvictPrev = node + node.EvictPrev.EvictNext = node + return + } + } + for v := node.EvictNext; v.EvictNext != s.evict; v = v.EvictNext { + if v.TTL() == 0 { + continue + } + if v.TTL() > node.TTL() { + node.EvictNext.EvictPrev = node.EvictPrev + node.EvictPrev.EvictNext = node.EvictNext + + node.EvictPrev = v + node.EvictNext = node.EvictPrev.EvictNext + node.EvictNext.EvictPrev = node + node.EvictPrev.EvictNext = node + return + } + } +} + +// Evict returns the node with the least remaining time to live for ltrPolicy. +// It returns the node at the end of the eviction list. +func (s ltrPolicy) Evict() *node { + if s.evict.EvictPrev != s.evict && (s.evict.EvictPrev.TTL() != 0 || s.evictZero) { + return s.evict.EvictPrev + } + return nil +} diff --git a/evict_test.go b/evict_test.go index 3503be4..ba73c24 100644 --- a/evict_test.go +++ b/evict_test.go @@ -2,6 +2,7 @@ package cache import ( "testing" + "time" "github.com/stretchr/testify/assert" ) @@ -29,44 +30,13 @@ func getListOrder(t testing.TB, evict *node) []*node { return order } -func TestNonePolicy(t *testing.T) { - t.Parallel() - - t.Run("OnInsert", func(t *testing.T) { - t.Parallel() - - policy := nonePolicy{evict: createSentinel(t)} - - n0 := &node{Key: []byte("0")} - n1 := &node{Key: []byte("1")} - - policy.OnInsert(n0) - policy.OnInsert(n1) - - order := getListOrder(t, policy.evict) - assert.Len(t, order, 2) - assert.Contains(t, order, n0) - assert.Contains(t, order, n1) - }) - - t.Run("Evict", func(t *testing.T) { - t.Parallel() - - policy := nonePolicy{evict: createSentinel(t)} - - policy.OnInsert(&node{}) - - assert.Nil(t, policy.Evict()) - }) -} - func TestFIFOPolicy(t *testing.T) { t.Parallel() t.Run("OnInsert", func(t *testing.T) { t.Parallel() - policy := fifoPolicy{evict: createSentinel(t)} + policy := fifoPolicy{evict: createSentinel(t), shouldEvict: true} n0 := &node{Key: []byte("0")} n1 := &node{Key: []byte("1")} @@ -86,7 +56,7 @@ func TestFIFOPolicy(t *testing.T) { t.Run("Evict", func(t *testing.T) { t.Parallel() - policy := fifoPolicy{evict: createSentinel(t)} + policy := fifoPolicy{evict: createSentinel(t), shouldEvict: true} n0 := &node{Key: []byte("0")} n1 := &node{Key: []byte("1")} @@ -97,6 +67,17 @@ func TestFIFOPolicy(t *testing.T) { evictedNode := policy.Evict() assert.Same(t, n0, evictedNode) }) + + t.Run("Evict noEvict", func(t *testing.T) { + t.Parallel() + + policy := fifoPolicy{evict: createSentinel(t), shouldEvict: false} + + policy.OnInsert(&node{}) + + assert.Nil(t, policy.Evict()) + }) + t.Run("Empty List", func(t *testing.T) { t.Parallel() @@ -269,7 +250,7 @@ func TestLFUPolicy(t *testing.T) { policy := lfuPolicy{evict: createSentinel(t)} - n0 := &node{Key: []byte("1")} + n0 := &node{Key: []byte("0")} n1 := &node{Key: []byte("1")} |