empty.go

/*
Welcome to April's Go Problem of the Month!

This month's challenge will take you through simulations of slowly degrading services (inspired by a
well-known identity provider whose name rhymes with "Oogle").

Our services return a number, and our challenge is to fetch 500 numbers from the service and sum the
results as quickly as possible.

You'll fill out implementations of the three functions, handling increasingly degraded services as
you get further.

You can run the tests and benchmarks with the command:

	go test -bench . -v empty.go external.go main_test.go

Note that the benchmarks won't run until all implementations are correct.

You can download all of these files by running:

	git clone https://gist.github.com/azylman/077c0121f70aaaa32b3a82ce3610c44d.git
*/
package main

import "errors"

var (
	ErrRateLimit    = errors.New("too many in-flight requests")
	ErrIntermittent = errors.New("status code 500")
)

// At first, the service performs relatively well: it's not as fast as we would like, but has 100%
// uptime.
// Your challenge is to sum the results from 500 successful calls to fetchNumber.
func SumSlowNumbers(fetchNumber func() (int, error)) int {
	return 0
}

// Later, the service starts to degrade. To deal with increasing load, the service maintainers put a
// rate limit on the service, and if you make too many concurrent requests it returns ErrRateLimit.
// Your challenge is to sum the results from 500 successful calls to fetchNumber.
func SumRateLimitedNumbers(fetchNumber func() (int, error)) int {
	return 0
}

// Eventually, the service degrades even more. Now, in addition to the rate limiting, it sometimes
// intermittently errors (represented by ErrIntermittent). Other times, it doesn't even return at
// all, and just hangs forver.
// Your challenge is to sum the results from 500 successful calls to fetchNumber.
func SumUnreliableNumbers(fetchNumber func() (int, error)) int {
	return 0
}

external.go

/*
This contains the implementations of SlowNumber, RateLimitedNumber, and UnreliableNumber.
You shouldn't need to know the implementations of these, and please don't base your solution on the
implementation.

We will change the implementations when we test people's solutions.
*/

package main

import (
	"math/rand"
	"sync/atomic"
	"time"
)

func init() {
	// Provide the same seed every time so that we're deterministic across runs
	rand.Seed(353868019)
}

// slowNumber returns a number after some delay.
func slowNumber() (int, error) {
	return slowlyReturn(3209624)
}

// rateLimitedNumber returns a number after some delay, and returns ErrRateLimit if you're calling
// it too quickly.
func rateLimitedNumber() (int, error) {
	return rateLimitedReturn(3588494)
}

// unreliableNumber returns a number... sometimes. Other times it might return ErrRateLimit. Or it
// might return ErrIntermittent, representing some intermittent error from the backend. Or it might
// not return at all.
func unreliableNumber() (int, error) {
	rnd := rand.Float64()
	if rnd < .99 {
		// 90% of the time we mess up, we want to return an error, and 10% of the time we want to
		// hang forever, simulated by sleeping for an hour.
		if rnd < .90 {
			return 0, ErrIntermittent
		} else {
			time.Sleep(time.Hour)
		}
	}
	return rateLimitedReturn(3969827)
}

func slowlyReturn(f int) (int, error) {
	time.Sleep(10 * time.Millisecond)
	return f, nil
}

var rateLimitedReturn = func() func(f int) (int, error) {
	inFlight := int64(0)
	return func(f int) (int, error) {
		// Add a bit of randomness to the rate limiting by adding a random offset
		offset := int64(rand.Intn(6))
		if atomic.LoadInt64(&inFlight)+offset > 10 {
			// If too many requests are in flight, return rate limit error
			return 0, ErrRateLimit
		}

		atomic.AddInt64(&inFlight, 1)
		n, _ := slowlyReturn(f)
		atomic.AddInt64(&inFlight, -1)

		return n, nil
	}
}()

main_test.go

/*
No cheating! People that just return the number get no credit :)
*/

package main

import "testing"

func TestSumSlowNumbers(t *testing.T) {
	n := SumSlowNumbers(slowNumber)
	expected := 1604812000
	if n != expected {
		t.Errorf("received %d instead of %d", n, expected)
	}
}
func TestSumRateLimitedNumbers(t *testing.T) {
	n := SumRateLimitedNumbers(rateLimitedNumber)
	expected := 1794247000
	if n != expected {
		t.Errorf("received %d instead of %d", n, expected)
	}
}
func TestSumUnreliableNumbers(t *testing.T) {
	n := SumUnreliableNumbers(unreliableNumber)
	expected := 1984913500
	if n != expected {
		t.Errorf("received %d instead of %d", n, expected)
	}
}

func BenchmarkSumSlowNumbers(b *testing.B) {
	for i := 0; i < b.N; i++ {
		SumSlowNumbers(slowNumber)
	}
}

func BenchmarkSumRateLimitedNumbers(b *testing.B) {
	for i := 0; i < b.N; i++ {
		SumRateLimitedNumbers(rateLimitedNumber)
	}
}

func BenchmarkSumUnreliableNumbers(b *testing.B) {
	for i := 0; i < b.N; i++ {
		SumUnreliableNumbers(unreliableNumber)
	}
}