groupcache_test.go

Documentation: github.com/golang/groupcache

     1  /*
     2  Copyright 2012 Google Inc.
     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  // Tests for groupcache.
    18  
    19  package groupcache
    20  
    21  import (
    22  	"context"
    23  	"errors"
    24  	"fmt"
    25  	"hash/crc32"
    26  	"math/rand"
    27  	"reflect"
    28  	"sync"
    29  	"testing"
    30  	"time"
    31  	"unsafe"
    32  
    33  	"github.com/golang/protobuf/proto"
    34  
    35  	pb "github.com/golang/groupcache/groupcachepb"
    36  	testpb "github.com/golang/groupcache/testpb"
    37  )
    38  
    39  var (
    40  	once                    sync.Once
    41  	stringGroup, protoGroup Getter
    42  
    43  	stringc = make(chan string)
    44  
    45  	dummyCtx = context.TODO()
    46  
    47  	// cacheFills is the number of times stringGroup or
    48  	// protoGroup's Getter have been called. Read using the
    49  	// cacheFills function.
    50  	cacheFills AtomicInt
    51  )
    52  
    53  const (
    54  	stringGroupName = "string-group"
    55  	protoGroupName  = "proto-group"
    56  	testMessageType = "google3/net/groupcache/go/test_proto.TestMessage"
    57  	fromChan        = "from-chan"
    58  	cacheSize       = 1 << 20
    59  )
    60  
    61  func testSetup() {
    62  	stringGroup = NewGroup(stringGroupName, cacheSize, GetterFunc(func(_ context.Context, key string, dest Sink) error {
    63  		if key == fromChan {
    64  			key = <-stringc
    65  		}
    66  		cacheFills.Add(1)
    67  		return dest.SetString("ECHO:" + key)
    68  	}))
    69  
    70  	protoGroup = NewGroup(protoGroupName, cacheSize, GetterFunc(func(_ context.Context, key string, dest Sink) error {
    71  		if key == fromChan {
    72  			key = <-stringc
    73  		}
    74  		cacheFills.Add(1)
    75  		return dest.SetProto(&testpb.TestMessage{
    76  			Name: proto.String("ECHO:" + key),
    77  			City: proto.String("SOME-CITY"),
    78  		})
    79  	}))
    80  }
    81  
    82  // TestGetDupSuppressString tests that a Getter's Get method is only called once with two
    83  // outstanding callers.  This is the string variant.
    84  func TestGetDupSuppressString(t *testing.T) {
    85  	once.Do(testSetup)
    86  	// Start two getters. The first should block (waiting reading
    87  	// from stringc) and the second should latch on to the first
    88  	// one.
    89  	resc := make(chan string, 2)
    90  	for i := 0; i < 2; i++ {
    91  		go func() {
    92  			var s string
    93  			if err := stringGroup.Get(dummyCtx, fromChan, StringSink(&s)); err != nil {
    94  				resc <- "ERROR:" + err.Error()
    95  				return
    96  			}
    97  			resc <- s
    98  		}()
    99  	}
   100  
   101  	// Wait a bit so both goroutines get merged together via
   102  	// singleflight.
   103  	// TODO(bradfitz): decide whether there are any non-offensive
   104  	// debug/test hooks that could be added to singleflight to
   105  	// make a sleep here unnecessary.
   106  	time.Sleep(250 * time.Millisecond)
   107  
   108  	// Unblock the first getter, which should unblock the second
   109  	// as well.
   110  	stringc <- "foo"
   111  
   112  	for i := 0; i < 2; i++ {
   113  		select {
   114  		case v := <-resc:
   115  			if v != "ECHO:foo" {
   116  				t.Errorf("got %q; want %q", v, "ECHO:foo")
   117  			}
   118  		case <-time.After(5 * time.Second):
   119  			t.Errorf("timeout waiting on getter #%d of 2", i+1)
   120  		}
   121  	}
   122  }
   123  
   124  // TestGetDupSuppressProto tests that a Getter's Get method is only called once with two
   125  // outstanding callers.  This is the proto variant.
   126  func TestGetDupSuppressProto(t *testing.T) {
   127  	once.Do(testSetup)
   128  	// Start two getters. The first should block (waiting reading
   129  	// from stringc) and the second should latch on to the first
   130  	// one.
   131  	resc := make(chan *testpb.TestMessage, 2)
   132  	for i := 0; i < 2; i++ {
   133  		go func() {
   134  			tm := new(testpb.TestMessage)
   135  			if err := protoGroup.Get(dummyCtx, fromChan, ProtoSink(tm)); err != nil {
   136  				tm.Name = proto.String("ERROR:" + err.Error())
   137  			}
   138  			resc <- tm
   139  		}()
   140  	}
   141  
   142  	// Wait a bit so both goroutines get merged together via
   143  	// singleflight.
   144  	// TODO(bradfitz): decide whether there are any non-offensive
   145  	// debug/test hooks that could be added to singleflight to
   146  	// make a sleep here unnecessary.
   147  	time.Sleep(250 * time.Millisecond)
   148  
   149  	// Unblock the first getter, which should unblock the second
   150  	// as well.
   151  	stringc <- "Fluffy"
   152  	want := &testpb.TestMessage{
   153  		Name: proto.String("ECHO:Fluffy"),
   154  		City: proto.String("SOME-CITY"),
   155  	}
   156  	for i := 0; i < 2; i++ {
   157  		select {
   158  		case v := <-resc:
   159  			if !reflect.DeepEqual(v, want) {
   160  				t.Errorf(" Got: %v\nWant: %v", proto.CompactTextString(v), proto.CompactTextString(want))
   161  			}
   162  		case <-time.After(5 * time.Second):
   163  			t.Errorf("timeout waiting on getter #%d of 2", i+1)
   164  		}
   165  	}
   166  }
   167  
   168  func countFills(f func()) int64 {
   169  	fills0 := cacheFills.Get()
   170  	f()
   171  	return cacheFills.Get() - fills0
   172  }
   173  
   174  func TestCaching(t *testing.T) {
   175  	once.Do(testSetup)
   176  	fills := countFills(func() {
   177  		for i := 0; i < 10; i++ {
   178  			var s string
   179  			if err := stringGroup.Get(dummyCtx, "TestCaching-key", StringSink(&s)); err != nil {
   180  				t.Fatal(err)
   181  			}
   182  		}
   183  	})
   184  	if fills != 1 {
   185  		t.Errorf("expected 1 cache fill; got %d", fills)
   186  	}
   187  }
   188  
   189  func TestCacheEviction(t *testing.T) {
   190  	once.Do(testSetup)
   191  	testKey := "TestCacheEviction-key"
   192  	getTestKey := func() {
   193  		var res string
   194  		for i := 0; i < 10; i++ {
   195  			if err := stringGroup.Get(dummyCtx, testKey, StringSink(&res)); err != nil {
   196  				t.Fatal(err)
   197  			}
   198  		}
   199  	}
   200  	fills := countFills(getTestKey)
   201  	if fills != 1 {
   202  		t.Fatalf("expected 1 cache fill; got %d", fills)
   203  	}
   204  
   205  	g := stringGroup.(*Group)
   206  	evict0 := g.mainCache.nevict
   207  
   208  	// Trash the cache with other keys.
   209  	var bytesFlooded int64
   210  	// cacheSize/len(testKey) is approximate
   211  	for bytesFlooded < cacheSize+1024 {
   212  		var res string
   213  		key := fmt.Sprintf("dummy-key-%d", bytesFlooded)
   214  		stringGroup.Get(dummyCtx, key, StringSink(&res))
   215  		bytesFlooded += int64(len(key) + len(res))
   216  	}
   217  	evicts := g.mainCache.nevict - evict0
   218  	if evicts <= 0 {
   219  		t.Errorf("evicts = %v; want more than 0", evicts)
   220  	}
   221  
   222  	// Test that the key is gone.
   223  	fills = countFills(getTestKey)
   224  	if fills != 1 {
   225  		t.Fatalf("expected 1 cache fill after cache trashing; got %d", fills)
   226  	}
   227  }
   228  
   229  type fakePeer struct {
   230  	hits int
   231  	fail bool
   232  }
   233  
   234  func (p *fakePeer) Get(_ context.Context, in *pb.GetRequest, out *pb.GetResponse) error {
   235  	p.hits++
   236  	if p.fail {
   237  		return errors.New("simulated error from peer")
   238  	}
   239  	out.Value = []byte("got:" + in.GetKey())
   240  	return nil
   241  }
   242  
   243  type fakePeers []ProtoGetter
   244  
   245  func (p fakePeers) PickPeer(key string) (peer ProtoGetter, ok bool) {
   246  	if len(p) == 0 {
   247  		return
   248  	}
   249  	n := crc32.Checksum([]byte(key), crc32.IEEETable) % uint32(len(p))
   250  	return p[n], p[n] != nil
   251  }
   252  
   253  // TestPeers tests that peers (virtual, in-process) are hit, and how much.
   254  func TestPeers(t *testing.T) {
   255  	once.Do(testSetup)
   256  	rand.Seed(123)
   257  	peer0 := &fakePeer{}
   258  	peer1 := &fakePeer{}
   259  	peer2 := &fakePeer{}
   260  	peerList := fakePeers([]ProtoGetter{peer0, peer1, peer2, nil})
   261  	const cacheSize = 0 // disabled
   262  	localHits := 0
   263  	getter := func(_ context.Context, key string, dest Sink) error {
   264  		localHits++
   265  		return dest.SetString("got:" + key)
   266  	}
   267  	testGroup := newGroup("TestPeers-group", cacheSize, GetterFunc(getter), peerList)
   268  	run := func(name string, n int, wantSummary string) {
   269  		// Reset counters
   270  		localHits = 0
   271  		for _, p := range []*fakePeer{peer0, peer1, peer2} {
   272  			p.hits = 0
   273  		}
   274  
   275  		for i := 0; i < n; i++ {
   276  			key := fmt.Sprintf("key-%d", i)
   277  			want := "got:" + key
   278  			var got string
   279  			err := testGroup.Get(dummyCtx, key, StringSink(&got))
   280  			if err != nil {
   281  				t.Errorf("%s: error on key %q: %v", name, key, err)
   282  				continue
   283  			}
   284  			if got != want {
   285  				t.Errorf("%s: for key %q, got %q; want %q", name, key, got, want)
   286  			}
   287  		}
   288  		summary := func() string {
   289  			return fmt.Sprintf("localHits = %d, peers = %d %d %d", localHits, peer0.hits, peer1.hits, peer2.hits)
   290  		}
   291  		if got := summary(); got != wantSummary {
   292  			t.Errorf("%s: got %q; want %q", name, got, wantSummary)
   293  		}
   294  	}
   295  	resetCacheSize := func(maxBytes int64) {
   296  		g := testGroup
   297  		g.cacheBytes = maxBytes
   298  		g.mainCache = cache{}
   299  		g.hotCache = cache{}
   300  	}
   301  
   302  	// Base case; peers all up, with no problems.
   303  	resetCacheSize(1 << 20)
   304  	run("base", 200, "localHits = 49, peers = 51 49 51")
   305  
   306  	// Verify cache was hit.  All localHits are gone, and some of
   307  	// the peer hits (the ones randomly selected to be maybe hot)
   308  	run("cached_base", 200, "localHits = 0, peers = 49 47 48")
   309  	resetCacheSize(0)
   310  
   311  	// With one of the peers being down.
   312  	// TODO(bradfitz): on a peer number being unavailable, the
   313  	// consistent hashing should maybe keep trying others to
   314  	// spread the load out. Currently it fails back to local
   315  	// execution if the first consistent-hash slot is unavailable.
   316  	peerList[0] = nil
   317  	run("one_peer_down", 200, "localHits = 100, peers = 0 49 51")
   318  
   319  	// Failing peer
   320  	peerList[0] = peer0
   321  	peer0.fail = true
   322  	run("peer0_failing", 200, "localHits = 100, peers = 51 49 51")
   323  }
   324  
   325  func TestTruncatingByteSliceTarget(t *testing.T) {
   326  	var buf [100]byte
   327  	s := buf[:]
   328  	if err := stringGroup.Get(dummyCtx, "short", TruncatingByteSliceSink(&s)); err != nil {
   329  		t.Fatal(err)
   330  	}
   331  	if want := "ECHO:short"; string(s) != want {
   332  		t.Errorf("short key got %q; want %q", s, want)
   333  	}
   334  
   335  	s = buf[:6]
   336  	if err := stringGroup.Get(dummyCtx, "truncated", TruncatingByteSliceSink(&s)); err != nil {
   337  		t.Fatal(err)
   338  	}
   339  	if want := "ECHO:t"; string(s) != want {
   340  		t.Errorf("truncated key got %q; want %q", s, want)
   341  	}
   342  }
   343  
   344  func TestAllocatingByteSliceTarget(t *testing.T) {
   345  	var dst []byte
   346  	sink := AllocatingByteSliceSink(&dst)
   347  
   348  	inBytes := []byte("some bytes")
   349  	sink.SetBytes(inBytes)
   350  	if want := "some bytes"; string(dst) != want {
   351  		t.Errorf("SetBytes resulted in %q; want %q", dst, want)
   352  	}
   353  	v, err := sink.view()
   354  	if err != nil {
   355  		t.Fatalf("view after SetBytes failed: %v", err)
   356  	}
   357  	if &inBytes[0] == &dst[0] {
   358  		t.Error("inBytes and dst share memory")
   359  	}
   360  	if &inBytes[0] == &v.b[0] {
   361  		t.Error("inBytes and view share memory")
   362  	}
   363  	if &dst[0] == &v.b[0] {
   364  		t.Error("dst and view share memory")
   365  	}
   366  }
   367  
   368  // orderedFlightGroup allows the caller to force the schedule of when
   369  // orig.Do will be called.  This is useful to serialize calls such
   370  // that singleflight cannot dedup them.
   371  type orderedFlightGroup struct {
   372  	mu     sync.Mutex
   373  	stage1 chan bool
   374  	stage2 chan bool
   375  	orig   flightGroup
   376  }
   377  
   378  func (g *orderedFlightGroup) Do(key string, fn func() (interface{}, error)) (interface{}, error) {
   379  	<-g.stage1
   380  	<-g.stage2
   381  	g.mu.Lock()
   382  	defer g.mu.Unlock()
   383  	return g.orig.Do(key, fn)
   384  }
   385  
   386  // TestNoDedup tests invariants on the cache size when singleflight is
   387  // unable to dedup calls.
   388  func TestNoDedup(t *testing.T) {
   389  	const testkey = "testkey"
   390  	const testval = "testval"
   391  	g := newGroup("testgroup", 1024, GetterFunc(func(_ context.Context, key string, dest Sink) error {
   392  		return dest.SetString(testval)
   393  	}), nil)
   394  
   395  	orderedGroup := &orderedFlightGroup{
   396  		stage1: make(chan bool),
   397  		stage2: make(chan bool),
   398  		orig:   g.loadGroup,
   399  	}
   400  	// Replace loadGroup with our wrapper so we can control when
   401  	// loadGroup.Do is entered for each concurrent request.
   402  	g.loadGroup = orderedGroup
   403  
   404  	// Issue two idential requests concurrently.  Since the cache is
   405  	// empty, it will miss.  Both will enter load(), but we will only
   406  	// allow one at a time to enter singleflight.Do, so the callback
   407  	// function will be called twice.
   408  	resc := make(chan string, 2)
   409  	for i := 0; i < 2; i++ {
   410  		go func() {
   411  			var s string
   412  			if err := g.Get(dummyCtx, testkey, StringSink(&s)); err != nil {
   413  				resc <- "ERROR:" + err.Error()
   414  				return
   415  			}
   416  			resc <- s
   417  		}()
   418  	}
   419  
   420  	// Ensure both goroutines have entered the Do routine.  This implies
   421  	// both concurrent requests have checked the cache, found it empty,
   422  	// and called load().
   423  	orderedGroup.stage1 <- true
   424  	orderedGroup.stage1 <- true
   425  	orderedGroup.stage2 <- true
   426  	orderedGroup.stage2 <- true
   427  
   428  	for i := 0; i < 2; i++ {
   429  		if s := <-resc; s != testval {
   430  			t.Errorf("result is %s want %s", s, testval)
   431  		}
   432  	}
   433  
   434  	const wantItems = 1
   435  	if g.mainCache.items() != wantItems {
   436  		t.Errorf("mainCache has %d items, want %d", g.mainCache.items(), wantItems)
   437  	}
   438  
   439  	// If the singleflight callback doesn't double-check the cache again
   440  	// upon entry, we would increment nbytes twice but the entry would
   441  	// only be in the cache once.
   442  	const wantBytes = int64(len(testkey) + len(testval))
   443  	if g.mainCache.nbytes != wantBytes {
   444  		t.Errorf("cache has %d bytes, want %d", g.mainCache.nbytes, wantBytes)
   445  	}
   446  }
   447  
   448  func TestGroupStatsAlignment(t *testing.T) {
   449  	var g Group
   450  	off := unsafe.Offsetof(g.Stats)
   451  	if off%8 != 0 {
   452  		t.Fatal("Stats structure is not 8-byte aligned.")
   453  	}
   454  }
   455  
   456  // TODO(bradfitz): port the Google-internal full integration test into here,
   457  // using HTTP requests instead of our RPC system.
   458
View as plain text