sched-latency-sim.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

// P is a latency variable that has emits a configured duration 99% of the time,
// another duration 0.9% of time, and yet another 0.1% of the time. It can be
// used to simulate the effects of some given thing with a given latency
// profile (p99, p99.9).
type P struct {
	p0, p99, p999 time.Duration
}

func (p *P) duration() time.Duration {
	r := rand.Float32()
	if r < 0.99 {
		return p.p0
	}
	if r < 0.999 {
		return p.p99
	}
	return p.p999
}

// serial takes in a list of latency variables, sums them, and returns the
// probability that their sum exceeds the given limit. It can be used to
// simulate the latency effects of going through a sequence of steps (rpc
// servers, goroutines, etc., each with some latency profile).
func serial(limit time.Duration, ps ...P) float64 {
	samples := 10000
	durations := make([]time.Duration, samples, samples)
	for i := 0; i < samples; i++ {
		for _, p := range ps {
			durations[i] = time.Duration(
				durations[i].Nanoseconds() + p.duration().Nanoseconds(),
			)
		}
	}
	sort.Slice(durations, func(i, j int) bool {
		return durations[i].Nanoseconds() < durations[j].Nanoseconds()
	})
	i := sort.Search(len(durations), func(i int) bool {
		return durations[i].Nanoseconds() >= limit.Nanoseconds()
	})
	return float64(i) / float64(samples)
}

// serialp takes in a list of latency variables, sums them, and returns the
// value at the given percentile.
func serialp(pX float64, ps ...P) time.Duration {
	iters := 10000
	idx := int(pX * float64(iters))
	if idx < 0 || idx >= iters {
		panic("idx out of bounds")
	}
	durations := make([]time.Duration, iters, iters)
	for i := 0; i < iters; i++ {
		for _, p := range ps {
			durations[i] = time.Duration(
				durations[i].Nanoseconds() + p.duration().Nanoseconds(),
			)
		}
	}
	sort.Slice(durations, func(i, j int) bool {
		return durations[i].Nanoseconds() < durations[j].Nanoseconds()
	})
	return durations[idx]
}

// parallel takes in a list of latency variables and returns the probability
// that the max exceeds the given limit. It can be used to simulate the latency
// effects of going through a set of steps in parallel (rpc servers, goroutines,
// etc., each with some latency profile).
func parallel(limit time.Duration, ps ...P) float64 {
	samples := 10000
	durations := make([]time.Duration, samples, samples)
	for i := 0; i < samples; i++ {
		for _, p := range ps {
			durations[i] = max(durations[i], p.duration())
		}
	}
	sort.Slice(durations, func(i, j int) bool {
		return durations[i].Nanoseconds() < durations[j].Nanoseconds()
	})
	i := sort.Search(len(durations), func(i int) bool {
		return durations[i].Nanoseconds() >= limit.Nanoseconds()
	})
	return float64(i) / float64(samples)
}

// parallelp takes in a list of latency variables, takes their max, and returns
// the value at the given percentile.
func parallelp(pX float64, ps ...P) time.Duration {
	iters := 10000
	idx := int(pX * float64(iters))
	if idx < 0 || idx >= iters {
		panic("idx out of bounds")
	}
	durations := make([]time.Duration, iters, iters)
	for i := 0; i < iters; i++ {
		for _, p := range ps {
			durations[i] = max(durations[i], p.duration())
		}
	}
	sort.Slice(durations, func(i, j int) bool {
		return durations[i].Nanoseconds() < durations[j].Nanoseconds()
	})
	return durations[idx]
}

func main() {
	rand.Seed(time.Now().UnixNano())

	// Create a variable that with a p99=1s, p99.9=1m, and lower percentile
	// values of 1ms.
	p := P{
		p0:   1 * time.Millisecond,
		p99:  1 * time.Second,
		p999: 1 * time.Minute,
	}

	target := p.p99
	for i := 0; i < 10; i++ {
		var ps []P
		for j := 0; j < 100; j++ {
			ps = append(ps, p)
		}

		fmt.Printf("parallel-p%0.2f=%-4s parallel-p99=%-4s serial-p%0.2f=%-4s serial-p99=%-8s (vars=%d)\n",
			parallel(target, ps...), target,
			parallelp(0.99, ps...),
			serial(target, ps...), target,
			serialp(0.99, ps...),
			len(ps),
		)
	}

	// The output is something like the following, showing that higher
	// percentiles of the random variables shows up in lower percentiles when
	// exposed to it in serial or parallel fashion. Also the p99 of the
	// serial/parallel forms are exposed a much higher percentile of the random
	// variable.
	//
	//  parallel-p0.90=1s   parallel-p99=1s   serial-p0.91=1s   serial-p99=2.008s   (vars=10)
	//  parallel-p0.91=1s   parallel-p99=1m0s serial-p0.91=1s   serial-p99=1m0.009s (vars=10)
	//  parallel-p0.91=1s   parallel-p99=1s   serial-p0.90=1s   serial-p99=2.008s   (vars=10)
	//  parallel-p0.91=1s   parallel-p99=1s   serial-p0.90=1s   serial-p99=3.007s   (vars=10)
	//  parallel-p0.90=1s   parallel-p99=1s   serial-p0.90=1s   serial-p99=1m0.009s (vars=10)
	//  parallel-p0.90=1s   parallel-p99=1s   serial-p0.91=1s   serial-p99=1m0.009s (vars=10)
	//  parallel-p0.90=1s   parallel-p99=1s   serial-p0.91=1s   serial-p99=2.008s   (vars=10)
	//  parallel-p0.91=1s   parallel-p99=1s   serial-p0.90=1s   serial-p99=2.008s   (vars=10)
	//  parallel-p0.91=1s   parallel-p99=1s   serial-p0.91=1s   serial-p99=3.007s   (vars=10)
	//  parallel-p0.90=1s   parallel-p99=1s   serial-p0.90=1s   serial-p99=1m0.009s (vars=10)
}

func max(a, b time.Duration) time.Duration {
	if a.Nanoseconds() > b.Nanoseconds() {
		return a
	}
	return b
}