Source file src/github.com/hashicorp/golang-lru/v2/expirable/expirable_lru_test.go

Documentation: github.com/hashicorp/golang-lru/v2/expirable

     1  // Copyright (c) HashiCorp, Inc.
     2  // SPDX-License-Identifier: MPL-2.0
     3  
     4  package expirable
     5  
     6  import (
     7  	"crypto/rand"
     8  	"fmt"
     9  	"math"
    10  	"math/big"
    11  	"reflect"
    12  	"sync"
    13  	"testing"
    14  	"time"
    15  
    16  	"github.com/hashicorp/golang-lru/v2/simplelru"
    17  )
    18  
    19  func BenchmarkLRU_Rand_NoExpire(b *testing.B) {
    20  	l := NewLRU[int64, int64](8192, nil, 0)
    21  
    22  	trace := make([]int64, b.N*2)
    23  	for i := 0; i < b.N*2; i++ {
    24  		trace[i] = getRand(b) % 32768
    25  	}
    26  
    27  	b.ResetTimer()
    28  
    29  	var hit, miss int
    30  	for i := 0; i < 2*b.N; i++ {
    31  		if i%2 == 0 {
    32  			l.Add(trace[i], trace[i])
    33  		} else {
    34  			if _, ok := l.Get(trace[i]); ok {
    35  				hit++
    36  			} else {
    37  				miss++
    38  			}
    39  		}
    40  	}
    41  	b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
    42  }
    43  
    44  func BenchmarkLRU_Freq_NoExpire(b *testing.B) {
    45  	l := NewLRU[int64, int64](8192, nil, 0)
    46  
    47  	trace := make([]int64, b.N*2)
    48  	for i := 0; i < b.N*2; i++ {
    49  		if i%2 == 0 {
    50  			trace[i] = getRand(b) % 16384
    51  		} else {
    52  			trace[i] = getRand(b) % 32768
    53  		}
    54  	}
    55  
    56  	b.ResetTimer()
    57  
    58  	for i := 0; i < b.N; i++ {
    59  		l.Add(trace[i], trace[i])
    60  	}
    61  	var hit, miss int
    62  	for i := 0; i < b.N; i++ {
    63  		if _, ok := l.Get(trace[i]); ok {
    64  			hit++
    65  		} else {
    66  			miss++
    67  		}
    68  	}
    69  	b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
    70  }
    71  
    72  func BenchmarkLRU_Rand_WithExpire(b *testing.B) {
    73  	l := NewLRU[int64, int64](8192, nil, time.Millisecond*10)
    74  
    75  	trace := make([]int64, b.N*2)
    76  	for i := 0; i < b.N*2; i++ {
    77  		trace[i] = getRand(b) % 32768
    78  	}
    79  
    80  	b.ResetTimer()
    81  
    82  	var hit, miss int
    83  	for i := 0; i < 2*b.N; i++ {
    84  		if i%2 == 0 {
    85  			l.Add(trace[i], trace[i])
    86  		} else {
    87  			if _, ok := l.Get(trace[i]); ok {
    88  				hit++
    89  			} else {
    90  				miss++
    91  			}
    92  		}
    93  	}
    94  	b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
    95  }
    96  
    97  func BenchmarkLRU_Freq_WithExpire(b *testing.B) {
    98  	l := NewLRU[int64, int64](8192, nil, time.Millisecond*10)
    99  
   100  	trace := make([]int64, b.N*2)
   101  	for i := 0; i < b.N*2; i++ {
   102  		if i%2 == 0 {
   103  			trace[i] = getRand(b) % 16384
   104  		} else {
   105  			trace[i] = getRand(b) % 32768
   106  		}
   107  	}
   108  
   109  	b.ResetTimer()
   110  
   111  	for i := 0; i < b.N; i++ {
   112  		l.Add(trace[i], trace[i])
   113  	}
   114  	var hit, miss int
   115  	for i := 0; i < b.N; i++ {
   116  		if _, ok := l.Get(trace[i]); ok {
   117  			hit++
   118  		} else {
   119  			miss++
   120  		}
   121  	}
   122  	b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(hit+miss))
   123  }
   124  
   125  func TestLRUInterface(_ *testing.T) {
   126  	var _ simplelru.LRUCache[int, int] = &LRU[int, int]{}
   127  }
   128  
   129  func TestLRUNoPurge(t *testing.T) {
   130  	lc := NewLRU[string, string](10, nil, 0)
   131  
   132  	lc.Add("key1", "val1")
   133  	if lc.Len() != 1 {
   134  		t.Fatalf("length differs from expected")
   135  	}
   136  
   137  	v, ok := lc.Peek("key1")
   138  	if v != "val1" {
   139  		t.Fatalf("value differs from expected")
   140  	}
   141  	if !ok {
   142  		t.Fatalf("should be true")
   143  	}
   144  
   145  	if !lc.Contains("key1") {
   146  		t.Fatalf("should contain key1")
   147  	}
   148  	if lc.Contains("key2") {
   149  		t.Fatalf("should not contain key2")
   150  	}
   151  
   152  	v, ok = lc.Peek("key2")
   153  	if v != "" {
   154  		t.Fatalf("should be empty")
   155  	}
   156  	if ok {
   157  		t.Fatalf("should be false")
   158  	}
   159  
   160  	if !reflect.DeepEqual(lc.Keys(), []string{"key1"}) {
   161  		t.Fatalf("value differs from expected")
   162  	}
   163  
   164  	if lc.Resize(0) != 0 {
   165  		t.Fatalf("evicted count differs from expected")
   166  	}
   167  	if lc.Resize(2) != 0 {
   168  		t.Fatalf("evicted count differs from expected")
   169  	}
   170  	lc.Add("key2", "val2")
   171  	if lc.Resize(1) != 1 {
   172  		t.Fatalf("evicted count differs from expected")
   173  	}
   174  }
   175  
   176  func TestLRUEdgeCases(t *testing.T) {
   177  	lc := NewLRU[string, *string](2, nil, 0)
   178  
   179  	// Adding a nil value
   180  	lc.Add("key1", nil)
   181  
   182  	value, exists := lc.Get("key1")
   183  	if value != nil || !exists {
   184  		t.Fatalf("unexpected value or existence flag for key1: value=%v, exists=%v", value, exists)
   185  	}
   186  
   187  	// Adding an entry with the same key but different value
   188  	newVal := "val1"
   189  	lc.Add("key1", &newVal)
   190  
   191  	value, exists = lc.Get("key1")
   192  	if value != &newVal || !exists {
   193  		t.Fatalf("unexpected value or existence flag for key1: value=%v, exists=%v", value, exists)
   194  	}
   195  }
   196  
   197  func TestLRU_Values(t *testing.T) {
   198  	lc := NewLRU[string, string](3, nil, 0)
   199  
   200  	lc.Add("key1", "val1")
   201  	lc.Add("key2", "val2")
   202  	lc.Add("key3", "val3")
   203  
   204  	values := lc.Values()
   205  	if !reflect.DeepEqual(values, []string{"val1", "val2", "val3"}) {
   206  		t.Fatalf("values differs from expected")
   207  	}
   208  }
   209  
   210  // func TestExpirableMultipleClose(_ *testing.T) {
   211  //	lc := NewLRU[string, string](10, nil, 0)
   212  //	lc.Close()
   213  //	// should not panic
   214  //	lc.Close()
   215  // }
   216  
   217  func TestLRUWithPurge(t *testing.T) {
   218  	var evicted []string
   219  	lc := NewLRU(10, func(key string, value string) { evicted = append(evicted, key, value) }, 150*time.Millisecond)
   220  
   221  	k, v, ok := lc.GetOldest()
   222  	if k != "" {
   223  		t.Fatalf("should be empty")
   224  	}
   225  	if v != "" {
   226  		t.Fatalf("should be empty")
   227  	}
   228  	if ok {
   229  		t.Fatalf("should be false")
   230  	}
   231  
   232  	lc.Add("key1", "val1")
   233  
   234  	time.Sleep(100 * time.Millisecond) // not enough to expire
   235  	if lc.Len() != 1 {
   236  		t.Fatalf("length differs from expected")
   237  	}
   238  
   239  	v, ok = lc.Get("key1")
   240  	if v != "val1" {
   241  		t.Fatalf("value differs from expected")
   242  	}
   243  	if !ok {
   244  		t.Fatalf("should be true")
   245  	}
   246  
   247  	time.Sleep(200 * time.Millisecond) // expire
   248  	v, ok = lc.Get("key1")
   249  	if ok {
   250  		t.Fatalf("should be false")
   251  	}
   252  	if v != "" {
   253  		t.Fatalf("should be nil")
   254  	}
   255  
   256  	if lc.Len() != 0 {
   257  		t.Fatalf("length differs from expected")
   258  	}
   259  	if !reflect.DeepEqual(evicted, []string{"key1", "val1"}) {
   260  		t.Fatalf("value differs from expected")
   261  	}
   262  
   263  	// add new entry
   264  	lc.Add("key2", "val2")
   265  	if lc.Len() != 1 {
   266  		t.Fatalf("length differs from expected")
   267  	}
   268  
   269  	k, v, ok = lc.GetOldest()
   270  	if k != "key2" {
   271  		t.Fatalf("value differs from expected")
   272  	}
   273  	if v != "val2" {
   274  		t.Fatalf("value differs from expected")
   275  	}
   276  	if !ok {
   277  		t.Fatalf("should be true")
   278  	}
   279  
   280  	// DeleteExpired, nothing deleted
   281  	lc.deleteExpired()
   282  	if lc.Len() != 1 {
   283  		t.Fatalf("length differs from expected")
   284  	}
   285  	if !reflect.DeepEqual(evicted, []string{"key1", "val1"}) {
   286  		t.Fatalf("value differs from expected")
   287  	}
   288  
   289  	// Purge, cache should be clean
   290  	lc.Purge()
   291  	if lc.Len() != 0 {
   292  		t.Fatalf("length differs from expected")
   293  	}
   294  	if !reflect.DeepEqual(evicted, []string{"key1", "val1", "key2", "val2"}) {
   295  		t.Fatalf("value differs from expected")
   296  	}
   297  }
   298  
   299  func TestLRUWithPurgeEnforcedBySize(t *testing.T) {
   300  	lc := NewLRU[string, string](10, nil, time.Hour)
   301  
   302  	for i := 0; i < 100; i++ {
   303  		i := i
   304  		lc.Add(fmt.Sprintf("key%d", i), fmt.Sprintf("val%d", i))
   305  		v, ok := lc.Get(fmt.Sprintf("key%d", i))
   306  		if v != fmt.Sprintf("val%d", i) {
   307  			t.Fatalf("value differs from expected")
   308  		}
   309  		if !ok {
   310  			t.Fatalf("should be true")
   311  		}
   312  		if lc.Len() > 20 {
   313  			t.Fatalf("length should be less than 20")
   314  		}
   315  	}
   316  
   317  	if lc.Len() != 10 {
   318  		t.Fatalf("length differs from expected")
   319  	}
   320  }
   321  
   322  func TestLRUConcurrency(t *testing.T) {
   323  	lc := NewLRU[string, string](0, nil, 0)
   324  	wg := sync.WaitGroup{}
   325  	wg.Add(1000)
   326  	for i := 0; i < 1000; i++ {
   327  		go func(i int) {
   328  			lc.Add(fmt.Sprintf("key-%d", i/10), fmt.Sprintf("val-%d", i/10))
   329  			wg.Done()
   330  		}(i)
   331  	}
   332  	wg.Wait()
   333  	if lc.Len() != 100 {
   334  		t.Fatalf("length differs from expected")
   335  	}
   336  }
   337  
   338  func TestLRUInvalidateAndEvict(t *testing.T) {
   339  	var evicted int
   340  	lc := NewLRU(-1, func(_, _ string) { evicted++ }, 0)
   341  
   342  	lc.Add("key1", "val1")
   343  	lc.Add("key2", "val2")
   344  
   345  	val, ok := lc.Get("key1")
   346  	if !ok {
   347  		t.Fatalf("should be true")
   348  	}
   349  	if val != "val1" {
   350  		t.Fatalf("value differs from expected")
   351  	}
   352  	if evicted != 0 {
   353  		t.Fatalf("value differs from expected")
   354  	}
   355  
   356  	lc.Remove("key1")
   357  	if evicted != 1 {
   358  		t.Fatalf("value differs from expected")
   359  	}
   360  	val, ok = lc.Get("key1")
   361  	if val != "" {
   362  		t.Fatalf("should be empty")
   363  	}
   364  	if ok {
   365  		t.Fatalf("should be false")
   366  	}
   367  }
   368  
   369  func TestLoadingExpired(t *testing.T) {
   370  	lc := NewLRU[string, string](0, nil, time.Millisecond*5)
   371  
   372  	lc.Add("key1", "val1")
   373  	if lc.Len() != 1 {
   374  		t.Fatalf("length differs from expected")
   375  	}
   376  
   377  	v, ok := lc.Peek("key1")
   378  	if v != "val1" {
   379  		t.Fatalf("value differs from expected")
   380  	}
   381  	if !ok {
   382  		t.Fatalf("should be true")
   383  	}
   384  
   385  	v, ok = lc.Get("key1")
   386  	if v != "val1" {
   387  		t.Fatalf("value differs from expected")
   388  	}
   389  	if !ok {
   390  		t.Fatalf("should be true")
   391  	}
   392  
   393  	for {
   394  		result, ok := lc.Get("key1")
   395  		if ok && result == "" {
   396  			t.Fatalf("ok should return a result")
   397  		}
   398  		if !ok {
   399  			break
   400  		}
   401  	}
   402  
   403  	time.Sleep(time.Millisecond * 100) // wait for expiration reaper
   404  	if lc.Len() != 0 {
   405  		t.Fatalf("length differs from expected")
   406  	}
   407  
   408  	v, ok = lc.Peek("key1")
   409  	if v != "" {
   410  		t.Fatalf("should be empty")
   411  	}
   412  	if ok {
   413  		t.Fatalf("should be false")
   414  	}
   415  
   416  	v, ok = lc.Get("key1")
   417  	if v != "" {
   418  		t.Fatalf("should be empty")
   419  	}
   420  	if ok {
   421  		t.Fatalf("should be false")
   422  	}
   423  }
   424  
   425  func TestLRURemoveOldest(t *testing.T) {
   426  	lc := NewLRU[string, string](2, nil, 0)
   427  
   428  	k, v, ok := lc.RemoveOldest()
   429  	if k != "" {
   430  		t.Fatalf("should be empty")
   431  	}
   432  	if v != "" {
   433  		t.Fatalf("should be empty")
   434  	}
   435  	if ok {
   436  		t.Fatalf("should be false")
   437  	}
   438  
   439  	ok = lc.Remove("non_existent")
   440  	if ok {
   441  		t.Fatalf("should be false")
   442  	}
   443  
   444  	lc.Add("key1", "val1")
   445  	if lc.Len() != 1 {
   446  		t.Fatalf("length differs from expected")
   447  	}
   448  
   449  	v, ok = lc.Get("key1")
   450  	if !ok {
   451  		t.Fatalf("should be true")
   452  	}
   453  	if v != "val1" {
   454  		t.Fatalf("value differs from expected")
   455  	}
   456  
   457  	if !reflect.DeepEqual(lc.Keys(), []string{"key1"}) {
   458  		t.Fatalf("value differs from expected")
   459  	}
   460  	if lc.Len() != 1 {
   461  		t.Fatalf("length differs from expected")
   462  	}
   463  
   464  	lc.Add("key2", "val2")
   465  	if !reflect.DeepEqual(lc.Keys(), []string{"key1", "key2"}) {
   466  		t.Fatalf("value differs from expected")
   467  	}
   468  	if lc.Len() != 2 {
   469  		t.Fatalf("length differs from expected")
   470  	}
   471  
   472  	k, v, ok = lc.RemoveOldest()
   473  	if k != "key1" {
   474  		t.Fatalf("value differs from expected")
   475  	}
   476  	if v != "val1" {
   477  		t.Fatalf("value differs from expected")
   478  	}
   479  	if !ok {
   480  		t.Fatalf("should be true")
   481  	}
   482  
   483  	if !reflect.DeepEqual(lc.Keys(), []string{"key2"}) {
   484  		t.Fatalf("value differs from expected")
   485  	}
   486  	if lc.Len() != 1 {
   487  		t.Fatalf("length differs from expected")
   488  	}
   489  }
   490  
   491  func ExampleLRU() {
   492  	// make cache with 10ms TTL and 5 max keys
   493  	cache := NewLRU[string, string](5, nil, time.Millisecond*10)
   494  
   495  	// set value under key1.
   496  	cache.Add("key1", "val1")
   497  
   498  	// get value under key1
   499  	r, ok := cache.Get("key1")
   500  
   501  	// check for OK value
   502  	if ok {
   503  		fmt.Printf("value before expiration is found: %v, value: %q\n", ok, r)
   504  	}
   505  
   506  	// wait for cache to expire
   507  	time.Sleep(time.Millisecond * 100)
   508  
   509  	// get value under key1 after key expiration
   510  	r, ok = cache.Get("key1")
   511  	fmt.Printf("value after expiration is found: %v, value: %q\n", ok, r)
   512  
   513  	// set value under key2, would evict old entry because it is already expired.
   514  	cache.Add("key2", "val2")
   515  
   516  	fmt.Printf("Cache len: %d\n", cache.Len())
   517  	// Output:
   518  	// value before expiration is found: true, value: "val1"
   519  	// value after expiration is found: false, value: ""
   520  	// Cache len: 1
   521  }
   522  
   523  func getRand(tb testing.TB) int64 {
   524  	out, err := rand.Int(rand.Reader, big.NewInt(math.MaxInt64))
   525  	if err != nil {
   526  		tb.Fatal(err)
   527  	}
   528  	return out.Int64()
   529  }
   530  
   531  func (c *LRU[K, V]) wantKeys(t *testing.T, want []K) {
   532  	t.Helper()
   533  	got := c.Keys()
   534  	if !reflect.DeepEqual(got, want) {
   535  		t.Errorf("wrong keys got: %v, want: %v ", got, want)
   536  	}
   537  }
   538  
   539  func TestCache_EvictionSameKey(t *testing.T) {
   540  	var evictedKeys []int
   541  
   542  	cache := NewLRU[int, struct{}](
   543  		2,
   544  		func(key int, _ struct{}) {
   545  			evictedKeys = append(evictedKeys, key)
   546  		},
   547  		0)
   548  
   549  	if evicted := cache.Add(1, struct{}{}); evicted {
   550  		t.Error("First 1: got unexpected eviction")
   551  	}
   552  	cache.wantKeys(t, []int{1})
   553  
   554  	if evicted := cache.Add(2, struct{}{}); evicted {
   555  		t.Error("2: got unexpected eviction")
   556  	}
   557  	cache.wantKeys(t, []int{1, 2})
   558  
   559  	if evicted := cache.Add(1, struct{}{}); evicted {
   560  		t.Error("Second 1: got unexpected eviction")
   561  	}
   562  	cache.wantKeys(t, []int{2, 1})
   563  
   564  	if evicted := cache.Add(3, struct{}{}); !evicted {
   565  		t.Error("3: did not get expected eviction")
   566  	}
   567  	cache.wantKeys(t, []int{1, 3})
   568  
   569  	want := []int{2}
   570  	if !reflect.DeepEqual(evictedKeys, want) {
   571  		t.Errorf("evictedKeys got: %v want: %v", evictedKeys, want)
   572  	}
   573  }
   574  

View as plain text