stress_test.go

Documentation: github.com/dgraph-io/ristretto

     1  package ristretto
     2  
     3  import (
     4  	"container/heap"
     5  	"fmt"
     6  	"math/rand"
     7  	"runtime"
     8  	"sync"
     9  	"testing"
    10  	"time"
    11  
    12  	"github.com/dgraph-io/ristretto/sim"
    13  	"github.com/stretchr/testify/require"
    14  )
    15  
    16  func TestStressSetGet(t *testing.T) {
    17  	c, err := NewCache(&Config{
    18  		NumCounters: 1000,
    19  		MaxCost:     100,
    20  		BufferItems: 64,
    21  		Metrics:     true,
    22  	})
    23  	require.NoError(t, err)
    24  
    25  	for i := 0; i < 100; i++ {
    26  		c.Set(i, i, 1)
    27  	}
    28  	time.Sleep(wait)
    29  	wg := &sync.WaitGroup{}
    30  	for i := 0; i < runtime.GOMAXPROCS(0); i++ {
    31  		wg.Add(1)
    32  		go func() {
    33  			r := rand.New(rand.NewSource(time.Now().UnixNano()))
    34  			for a := 0; a < 1000; a++ {
    35  				k := r.Int() % 10
    36  				if val, ok := c.Get(k); val == nil || !ok {
    37  					err = fmt.Errorf("expected %d but got nil", k)
    38  					break
    39  				} else if val != nil && val.(int) != k {
    40  					err = fmt.Errorf("expected %d but got %d", k, val.(int))
    41  					break
    42  				}
    43  			}
    44  			wg.Done()
    45  		}()
    46  	}
    47  	wg.Wait()
    48  	require.NoError(t, err)
    49  	require.Equal(t, 1.0, c.Metrics.Ratio())
    50  }
    51  
    52  func TestStressHitRatio(t *testing.T) {
    53  	key := sim.NewZipfian(1.0001, 1, 1000)
    54  	c, err := NewCache(&Config{
    55  		NumCounters: 1000,
    56  		MaxCost:     100,
    57  		BufferItems: 64,
    58  		Metrics:     true,
    59  	})
    60  	require.NoError(t, err)
    61  
    62  	o := NewClairvoyant(100)
    63  	for i := 0; i < 10000; i++ {
    64  		k, err := key()
    65  		require.NoError(t, err)
    66  
    67  		if _, ok := o.Get(k); !ok {
    68  			o.Set(k, k, 1)
    69  		}
    70  		if _, ok := c.Get(k); !ok {
    71  			c.Set(k, k, 1)
    72  		}
    73  	}
    74  	t.Logf("actual: %.2f, optimal: %.2f", c.Metrics.Ratio(), o.Metrics().Ratio())
    75  }
    76  
    77  // Clairvoyant is a mock cache providing us with optimal hit ratios to compare
    78  // with Ristretto's. It looks ahead and evicts the absolute least valuable item,
    79  // which we try to approximate in a real cache.
    80  type Clairvoyant struct {
    81  	capacity uint64
    82  	hits     map[uint64]uint64
    83  	access   []uint64
    84  }
    85  
    86  func NewClairvoyant(capacity uint64) *Clairvoyant {
    87  	return &Clairvoyant{
    88  		capacity: capacity,
    89  		hits:     make(map[uint64]uint64),
    90  		access:   make([]uint64, 0),
    91  	}
    92  }
    93  
    94  // Get just records the cache access so that we can later take this event into
    95  // consideration when calculating the absolute least valuable item to evict.
    96  func (c *Clairvoyant) Get(key interface{}) (interface{}, bool) {
    97  	c.hits[key.(uint64)]++
    98  	c.access = append(c.access, key.(uint64))
    99  	return nil, false
   100  }
   101  
   102  // Set isn't important because it is only called after a Get (in the case of our
   103  // hit ratio benchmarks, at least).
   104  func (c *Clairvoyant) Set(key, value interface{}, cost int64) bool {
   105  	return false
   106  }
   107  
   108  func (c *Clairvoyant) Metrics() *Metrics {
   109  	stat := newMetrics()
   110  	look := make(map[uint64]struct{}, c.capacity)
   111  	data := &clairvoyantHeap{}
   112  	heap.Init(data)
   113  	for _, key := range c.access {
   114  		if _, has := look[key]; has {
   115  			stat.add(hit, 0, 1)
   116  			continue
   117  		}
   118  		if uint64(data.Len()) >= c.capacity {
   119  			victim := heap.Pop(data)
   120  			delete(look, victim.(*clairvoyantItem).key)
   121  		}
   122  		stat.add(miss, 0, 1)
   123  		look[key] = struct{}{}
   124  		heap.Push(data, &clairvoyantItem{key, c.hits[key]})
   125  	}
   126  	return stat
   127  }
   128  
   129  type clairvoyantItem struct {
   130  	key  uint64
   131  	hits uint64
   132  }
   133  
   134  type clairvoyantHeap []*clairvoyantItem
   135  
   136  func (h clairvoyantHeap) Len() int           { return len(h) }
   137  func (h clairvoyantHeap) Less(i, j int) bool { return h[i].hits < h[j].hits }
   138  func (h clairvoyantHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
   139  
   140  func (h *clairvoyantHeap) Push(x interface{}) {
   141  	*h = append(*h, x.(*clairvoyantItem))
   142  }
   143  
   144  func (h *clairvoyantHeap) Pop() interface{} {
   145  	old := *h
   146  	n := len(old)
   147  	x := old[n-1]
   148  	*h = old[0 : n-1]
   149  	return x
   150  }
   151
View as plain text