memory.go

// Copyright 2016, Google Inc. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package throttler

import (
	"fmt"
	"sort"
	"time"
)

// memory tracks "good" and "bad" throttler rates where good rates are below
// the system capacity and bad are above it.
//
// It is based on the fact that the MySQL performance degrades with an
// increasing number of rows. Therefore, the implementation stores only one
// bad rate which will get lower over time and turn known good rates into
// bad ones.
//
// To protect against temporary performance degradations, a stable bad rate,
// which hasn't changed for a certain time, "ages out" and will be increased
// again. This ensures that rates above past bad rates will be tested again in
// the future.
//
// To simplify tracking all possible rates, they are slotted into buckets
// e.g. of the size 5.
type memory struct {
	bucketSize int

	good             []int64
	bad              int64
	nextBadRateAging time.Time

	ageBadRateAfter time.Duration
	badRateIncrease float64
}

func newMemory(bucketSize int, ageBadRateAfter time.Duration, badRateIncrease float64) *memory {
	if bucketSize == 0 {
		bucketSize = 1
	}
	return &memory{
		bucketSize:      bucketSize,
		good:            make([]int64, 0),
		ageBadRateAfter: ageBadRateAfter,
		badRateIncrease: badRateIncrease,
	}
}

func (m *memory) updateAgingConfiguration(ageBadRateAfter time.Duration, badRateIncrease float64) {
	if !m.nextBadRateAging.IsZero() {
		// Adjust the current age timer immediately.
		m.nextBadRateAging = m.nextBadRateAging.Add(ageBadRateAfter).Add(-m.ageBadRateAfter)
	}
	m.ageBadRateAfter = ageBadRateAfter
	m.badRateIncrease = badRateIncrease
}

// int64Slice is used to sort int64 slices.
type int64Slice []int64

func (a int64Slice) Len() int           { return len(a) }
func (a int64Slice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a int64Slice) Less(i, j int) bool { return a[i] < a[j] }

func searchInt64s(a []int64, x int64) int {
	return sort.Search(len(a), func(i int) bool { return a[i] >= x })
}

func (m *memory) markGood(rate int64) error {
	rate = m.roundDown(rate)

	if lowestBad := m.lowestBad(); lowestBad != 0 && rate > lowestBad {
		return fmt.Errorf("ignoring higher good rate of %v because we assume that the known maximum capacity (currently at %v) can only degrade", rate, lowestBad)
	}

	// Skip rates which already exist.
	i := searchInt64s(m.good, rate)
	if i < len(m.good) && m.good[i] == rate {
		return nil
	}

	m.good = append(m.good, rate)
	sort.Sort(int64Slice(m.good))
	return nil
}

func (m *memory) markBad(rate int64, now time.Time) error {
	// Bad rates are rounded up instead of down to not be too extreme on the
	// reduction and account for some margin of error.
	rate = m.roundUp(rate)

	// Ignore higher bad rates than the current one.
	if m.bad != 0 && rate >= m.bad {
		return nil
	}

	// Ignore bad rates which are too drastic. This prevents that temporary
	// hiccups e.g. during a reparent, are stored in the memory.
	// TODO(mberlin): Remove this once we let bad values expire over time.
	highestGood := m.highestGood()
	if rate < highestGood {
		decrease := float64(highestGood) - float64(rate)
		degradation := decrease / float64(highestGood)
		if degradation > 0.1 {
			return fmt.Errorf("ignoring lower bad rate of %v because such a high degradation (%.1f%%) is unlikely (current highest good: %v)", rate, degradation*100, highestGood)
		}
	}

	// Delete all good values which turned bad.
	goodLength := len(m.good)
	for i := goodLength - 1; i >= 0; i-- {
		goodRate := m.good[i]
		if goodRate >= rate {
			goodLength = i
		} else {
			break
		}
	}
	m.good = m.good[:goodLength]

	m.bad = rate
	m.touchBadRateAge(now)
	return nil
}

// touchBadRateAge records that the bad rate was changed and the aging should be
// further delayed.
func (m *memory) touchBadRateAge(now time.Time) {
	m.nextBadRateAging = now.Add(m.ageBadRateAfter)
}

func (m *memory) ageBadRate(now time.Time) {
	if m.badRateIncrease == 0 {
		return
	}
	if m.bad == 0 {
		return
	}
	if m.nextBadRateAging.IsZero() {
		return
	}
	if now.Before(m.nextBadRateAging) {
		return
	}

	newBad := float64(m.bad) * (1 + m.badRateIncrease)
	if int64(newBad) == m.bad {
		// Increase had no effect. Increase it at least by the granularity.
		newBad += memoryGranularity
	}
	m.bad = int64(newBad)
	m.touchBadRateAge(now)
}

func (m *memory) highestGood() int64 {
	if len(m.good) == 0 {
		return 0
	}

	return m.good[len(m.good)-1]
}

func (m *memory) lowestBad() int64 {
	return m.bad
}

func (m *memory) roundDown(rate int64) int64 {
	return rate / int64(m.bucketSize) * int64(m.bucketSize)
}

func (m *memory) roundUp(rate int64) int64 {
	ceil := rate / int64(m.bucketSize) * int64(m.bucketSize)
	if rate%int64(m.bucketSize) != 0 {
		ceil += int64(m.bucketSize)
	}
	return ceil
}