expiring_test.go

Documentation: k8s.io/apimachinery/pkg/util/cache

     1  /*
     2  Copyright 2019 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package cache
    18  
    19  import (
    20  	"context"
    21  	"math/rand"
    22  	"sync"
    23  	"testing"
    24  	"time"
    25  
    26  	"github.com/google/uuid"
    27  
    28  	testingclock "k8s.io/utils/clock/testing"
    29  )
    30  
    31  func TestExpiringCache(t *testing.T) {
    32  	cache := NewExpiring()
    33  
    34  	if result, ok := cache.Get("foo"); ok || result != nil {
    35  		t.Errorf("Expected null, false, got %#v, %v", result, ok)
    36  	}
    37  
    38  	record1 := "bob"
    39  	record2 := "alice"
    40  
    41  	// when empty, record is stored
    42  	cache.Set("foo", record1, time.Hour)
    43  	if result, ok := cache.Get("foo"); !ok || result != record1 {
    44  		t.Errorf("Expected %#v, true, got %#v, %v", record1, result, ok)
    45  	}
    46  
    47  	// newer record overrides
    48  	cache.Set("foo", record2, time.Hour)
    49  	if result, ok := cache.Get("foo"); !ok || result != record2 {
    50  		t.Errorf("Expected %#v, true, got %#v, %v", record2, result, ok)
    51  	}
    52  
    53  	// delete the current value
    54  	cache.Delete("foo")
    55  	if result, ok := cache.Get("foo"); ok || result != nil {
    56  		t.Errorf("Expected null, false, got %#v, %v", result, ok)
    57  	}
    58  }
    59  
    60  func TestExpiration(t *testing.T) {
    61  	fc := &testingclock.FakeClock{}
    62  	c := NewExpiringWithClock(fc)
    63  
    64  	c.Set("a", "a", time.Second)
    65  
    66  	fc.Step(500 * time.Millisecond)
    67  	if _, ok := c.Get("a"); !ok {
    68  		t.Fatalf("we should have found a key")
    69  	}
    70  
    71  	fc.Step(time.Second)
    72  	if _, ok := c.Get("a"); ok {
    73  		t.Fatalf("we should not have found a key")
    74  	}
    75  
    76  	c.Set("a", "a", time.Second)
    77  
    78  	fc.Step(500 * time.Millisecond)
    79  	if _, ok := c.Get("a"); !ok {
    80  		t.Fatalf("we should have found a key")
    81  	}
    82  
    83  	// reset should restart the ttl
    84  	c.Set("a", "a", time.Second)
    85  
    86  	fc.Step(750 * time.Millisecond)
    87  	if _, ok := c.Get("a"); !ok {
    88  		t.Fatalf("we should have found a key")
    89  	}
    90  
    91  	// Simulate a race between a reset and cleanup. Assert that del doesn't
    92  	// remove the key.
    93  	c.Set("a", "a", time.Second)
    94  
    95  	e := c.cache["a"]
    96  	e.generation++
    97  	e.expiry = e.expiry.Add(1 * time.Second)
    98  	c.cache["a"] = e
    99  
   100  	fc.Step(1 * time.Second)
   101  	if _, ok := c.Get("a"); !ok {
   102  		t.Fatalf("we should have found a key")
   103  	}
   104  
   105  	// Check getting an expired key with and without AllowExpiredGet
   106  	c.Set("b", "b", time.Second)
   107  	fc.Step(2 * time.Second)
   108  	if _, ok := c.Get("b"); ok {
   109  		t.Fatalf("we should not have found b key")
   110  	}
   111  	if count := c.Len(); count != 2 { // b is still in the cache
   112  		t.Errorf("expected two items got: %d", count)
   113  	}
   114  	c.AllowExpiredGet = true
   115  	if _, ok := c.Get("b"); !ok {
   116  		t.Fatalf("we should have found b key")
   117  	}
   118  	if count := c.Len(); count != 2 { // b is still in the cache
   119  		t.Errorf("expected two items got: %d", count)
   120  	}
   121  	c.Set("c", "c", time.Second)      // set some unrelated key to run gc
   122  	if count := c.Len(); count != 2 { // only a and c in the cache now
   123  		t.Errorf("expected two items got: %d", count)
   124  	}
   125  	if _, ok := c.Get("b"); ok {
   126  		t.Fatalf("we should not have found b key")
   127  	}
   128  	if _, ok := c.Get("a"); !ok {
   129  		t.Fatalf("we should have found a key")
   130  	}
   131  	if _, ok := c.Get("c"); !ok {
   132  		t.Fatalf("we should have found c key")
   133  	}
   134  }
   135  
   136  func TestGarbageCollection(t *testing.T) {
   137  	fc := &testingclock.FakeClock{}
   138  
   139  	type entry struct {
   140  		key, val string
   141  		ttl      time.Duration
   142  	}
   143  
   144  	tests := []struct {
   145  		name string
   146  		now  time.Time
   147  		set  []entry
   148  		want map[string]string
   149  	}{
   150  		{
   151  			name: "two entries just set",
   152  			now:  fc.Now().Add(0 * time.Second),
   153  			set: []entry{
   154  				{"a", "aa", 1 * time.Second},
   155  				{"b", "bb", 2 * time.Second},
   156  			},
   157  			want: map[string]string{
   158  				"a": "aa",
   159  				"b": "bb",
   160  			},
   161  		},
   162  		{
   163  			name: "first entry expired now",
   164  			now:  fc.Now().Add(1 * time.Second),
   165  			set: []entry{
   166  				{"a", "aa", 1 * time.Second},
   167  				{"b", "bb", 2 * time.Second},
   168  			},
   169  			want: map[string]string{
   170  				"b": "bb",
   171  			},
   172  		},
   173  		{
   174  			name: "first entry expired half a second ago",
   175  			now:  fc.Now().Add(1500 * time.Millisecond),
   176  			set: []entry{
   177  				{"a", "aa", 1 * time.Second},
   178  				{"b", "bb", 2 * time.Second},
   179  			},
   180  			want: map[string]string{
   181  				"b": "bb",
   182  			},
   183  		},
   184  		{
   185  			name: "three entries weird order",
   186  			now:  fc.Now().Add(1 * time.Second),
   187  			set: []entry{
   188  				{"c", "cc", 3 * time.Second},
   189  				{"a", "aa", 1 * time.Second},
   190  				{"b", "bb", 2 * time.Second},
   191  			},
   192  			want: map[string]string{
   193  				"b": "bb",
   194  				"c": "cc",
   195  			},
   196  		},
   197  		{
   198  			name: "expire multiple entries in one cycle",
   199  			now:  fc.Now().Add(2500 * time.Millisecond),
   200  			set: []entry{
   201  				{"a", "aa", 1 * time.Second},
   202  				{"b", "bb", 2 * time.Second},
   203  				{"c", "cc", 3 * time.Second},
   204  			},
   205  			want: map[string]string{
   206  				"c": "cc",
   207  			},
   208  		},
   209  	}
   210  
   211  	for _, test := range tests {
   212  		t.Run(test.name, func(t *testing.T) {
   213  			c := NewExpiringWithClock(fc)
   214  			for _, e := range test.set {
   215  				c.Set(e.key, e.val, e.ttl)
   216  			}
   217  
   218  			c.gc(test.now)
   219  
   220  			for k, want := range test.want {
   221  				got, ok := c.Get(k)
   222  				if !ok {
   223  					t.Errorf("expected cache to have entry for key=%q but found none", k)
   224  					continue
   225  				}
   226  				if got != want {
   227  					t.Errorf("unexpected value for key=%q: got=%q, want=%q", k, got, want)
   228  				}
   229  			}
   230  			if got, want := c.Len(), len(test.want); got != want {
   231  				t.Errorf("unexpected cache size: got=%d, want=%d", got, want)
   232  			}
   233  		})
   234  	}
   235  }
   236  
   237  func BenchmarkExpiringCacheContention(b *testing.B) {
   238  	b.Run("evict_probablility=100%", func(b *testing.B) {
   239  		benchmarkExpiringCacheContention(b, 1)
   240  	})
   241  	b.Run("evict_probablility=10%", func(b *testing.B) {
   242  		benchmarkExpiringCacheContention(b, 0.1)
   243  	})
   244  	b.Run("evict_probablility=1%", func(b *testing.B) {
   245  		benchmarkExpiringCacheContention(b, 0.01)
   246  	})
   247  }
   248  
   249  func benchmarkExpiringCacheContention(b *testing.B, prob float64) {
   250  	const numKeys = 1 << 16
   251  	cache := NewExpiring()
   252  
   253  	keys := []string{}
   254  	for i := 0; i < numKeys; i++ {
   255  		key := uuid.New().String()
   256  		keys = append(keys, key)
   257  	}
   258  
   259  	b.ResetTimer()
   260  
   261  	b.SetParallelism(256)
   262  	b.RunParallel(func(pb *testing.PB) {
   263  		rand := rand.New(rand.NewSource(rand.Int63()))
   264  		for pb.Next() {
   265  			i := rand.Int31()
   266  			key := keys[i%numKeys]
   267  			_, ok := cache.Get(key)
   268  			if ok {
   269  				// compare lower bits of sampled i to decide whether we should evict.
   270  				if rand.Float64() < prob {
   271  					cache.Delete(key)
   272  				}
   273  			} else {
   274  				cache.Set(key, struct{}{}, 50*time.Millisecond)
   275  			}
   276  		}
   277  	})
   278  }
   279  
   280  func TestStressExpiringCache(t *testing.T) {
   281  	ctx, cancel := context.WithTimeout(context.Background(), 5*time.Second)
   282  	defer cancel()
   283  
   284  	const numKeys = 1 << 16
   285  	cache := NewExpiring()
   286  
   287  	keys := []string{}
   288  	for i := 0; i < numKeys; i++ {
   289  		key := uuid.New().String()
   290  		keys = append(keys, key)
   291  	}
   292  
   293  	var wg sync.WaitGroup
   294  	for i := 0; i < 256; i++ {
   295  		wg.Add(1)
   296  		go func() {
   297  			defer wg.Done()
   298  			rand := rand.New(rand.NewSource(rand.Int63()))
   299  			for {
   300  				select {
   301  				case <-ctx.Done():
   302  					return
   303  				default:
   304  				}
   305  				key := keys[rand.Intn(numKeys)]
   306  				if _, ok := cache.Get(key); !ok {
   307  					cache.Set(key, struct{}{}, 50*time.Millisecond)
   308  				}
   309  			}
   310  		}()
   311  	}
   312  
   313  	wg.Wait()
   314  
   315  	// trigger a GC with a set and check the cache size.
   316  	time.Sleep(60 * time.Millisecond)
   317  	cache.Set("trigger", "gc", time.Second)
   318  	if cache.Len() != 1 {
   319  		t.Errorf("unexpected cache size: got=%d, want=1", cache.Len())
   320  	}
   321  }
   322
View as plain text