1package backoff
  2
  3import (
  4	"container/list"
  5	"errors"
  6	"sync"
  7	"time"
  8)
  9
 10const (
 11	Threshold = 5
 12	Base      = time.Second
 13	Cap       = 15 * time.Minute
 14	Entries   = 10000
 15)
 16
 17var errNoEntries = errors.New("backoff: a table needs at least one entry")
 18
 19type entry struct {
 20	key      string
 21	failures int
 22	until    time.Time
 23	in       *list.List
 24}
 25
 26type Backoff struct {
 27	mu       sync.Mutex
 28	now      func() time.Time
 29	max      int
 30	entries  map[string]*list.Element
 31	counting *list.List
 32	reached  *list.List
 33	evicted  uint64
 34}
 35
 36func New(now func() time.Time, max int) *Backoff {
 37	if max < 1 {
 38		panic(errNoEntries)
 39	}
 40	return &Backoff{now: now, max: max, entries: map[string]*list.Element{}, counting: list.New(), reached: list.New()}
 41}
 42
 43func (b *Backoff) Locked(key string) bool {
 44	b.mu.Lock()
 45	defer b.mu.Unlock()
 46	el, ok := b.entries[key]
 47	if !ok {
 48		return false
 49	}
 50	e := el.Value.(*entry)
 51	e.in.MoveToFront(el)
 52	return b.now().Before(e.until)
 53}
 54
 55func (b *Backoff) Fail(key string) {
 56	b.mu.Lock()
 57	defer b.mu.Unlock()
 58	el, ok := b.entries[key]
 59	if !ok {
 60		for len(b.entries) >= b.max {
 61			b.evict()
 62		}
 63		el = b.counting.PushFront(&entry{key: key, in: b.counting})
 64		b.entries[key] = el
 65	}
 66	e := el.Value.(*entry)
 67	e.in.MoveToFront(el)
 68	e.failures++
 69	if e.failures < Threshold {
 70		return
 71	}
 72	if e.in == b.counting {
 73		b.counting.Remove(el)
 74		e.in = b.reached
 75		b.entries[key] = b.reached.PushFront(e)
 76	}
 77	window := Cap
 78	if shift := e.failures - Threshold; shift < 20 {
 79		if w := Base << shift; w < Cap {
 80			window = w
 81		}
 82	}
 83	e.until = b.now().Add(window)
 84}
 85
 86func (b *Backoff) evict() {
 87	victim := b.counting.Back()
 88	if victim == nil {
 89		victim = b.reached.Back()
 90	}
 91	e := victim.Value.(*entry)
 92	e.in.Remove(victim)
 93	delete(b.entries, e.key)
 94	b.evicted++
 95}
 96
 97func (b *Backoff) Reset(key string) {
 98	b.mu.Lock()
 99	defer b.mu.Unlock()
100	if el, ok := b.entries[key]; ok {
101		el.Value.(*entry).in.Remove(el)
102		delete(b.entries, key)
103	}
104}
105
106func (b *Backoff) Len() int {
107	b.mu.Lock()
108	defer b.mu.Unlock()
109	return len(b.entries)
110}