cristalhq / hedgedhttp Goto Github PK

View Code? Open in Web Editor NEW

119.0 5.0 9.0 72 KB

Hedged HTTP client which helps to reduce tail latency at scale.

License: MIT License

Go 100.00%

go golang http http-client scale latency timeout

hedgedhttp's Introduction

hedgedhttp

Hedged HTTP client which helps to reduce tail latency at scale.

Rationale

See paper Tail at Scale by Jeffrey Dean, Luiz André Barroso. In short: the client first sends one request, but then sends an additional request after a timeout if the previous hasn't returned an answer in the expected time. The client cancels remaining requests once the first result is received.

Acknowledge

Thanks to Bohdan Storozhuk for the review and powerful hints.

Features

Simple API.
Easy to integrate.
Optimized for speed.
Clean and tested code.
Supports http.Client and http.RoundTripper.
Dependency-free.

Install

Go version 1.16+

go get github.com/cristalhq/hedgedhttp

Example

ctx := context.Background()
req, err := http.NewRequestWithContext(ctx, http.MethodGet, "https://google.com", http.NoBody)
if err != nil {
	panic(err)
}

timeout := 10 * time.Millisecond
upto := 7
client := &http.Client{Timeout: time.Second}
hedged, err := hedgedhttp.NewClient(timeout, upto, client)
if err != nil {
	panic(err)
}

// will take `upto` requests, with a `timeout` delay between them
resp, err := hedged.Do(req)
if err != nil {
	panic(err)
}
defer resp.Body.Close()

Also see examples: examples_test.go.

Documentation

See these docs.

License

MIT License.

hedgedhttp's People

Contributors

Stargazers

Watchers

Forkers

slavabobik joe-elliott 0xack13 storozhukbm ryancurrah dmitrybezik giedriuss dannykopping fangxlmr

hedgedhttp's Issues

Implement t-digest

My suggestion would be to approximate the 90th, 95th or whichever percentile using t-digest and then to send a second request if the duration exceeds that percentile. IMHO would be much better than having a static value.

If this sounds good to you then I could try implementing it.

Moving to go-distsys

I'm planning to move this repository to the https://github.com/go-distsys. So, Github should take care of all redirects.

Probably will happen next week, read as Sep 18-20.

Another option is to archive this repository and push it as a new in @go-distsys. Not sure what is better, any ideas?

Add Prometheus integration

What do we think about adding Prometheus integration to this library.

It seems hard to do outside of the library. Something I could contribute if needed.

Rate limit hedge requests

Hello there,

What do we think about adding a way to rate limits hedged requests ?

For example if we suddenly seems to hedge all request because the tail latency changed, we may actually worsen the problem.

I suggest we add a percentage parameter which tells how often we can hedge request based on actual requested throughput.

For example if the value is 10%, then we can only hedge 1 request out of 10. Default could be 100%, all request can be hedged.

What do you think ?

Don’t Panic, Return Err

I’m interested in using this lib but have concerns over the use of panic in it.

Just curious as to why it’s used?

If it was an oversight would you’d be open to a PR that returns an error instead?

Thank you.

Backoff parameter instead of simple time.Duration

// Backoff logic for hedged requests.
type Backoff interface {
	// Next returns a time to wait before next request and flag to stop.
	Next() (next time.Duration, stop bool)
}

Probably interface might be too heavy for this and just a func() (time.Duration, bool) should be enough. This is kinda relates to golang/go#47487 (CC: cristalhq/acmd#7) but 6 months to wait at least.

Determining the effectiveness of hedging

Hey @cristaloleg

Is there a way to determine how many hedged requests actually "won" vs the original request, with the stats?

Flaky test: TestHedgedResponseWins

I've packaged this library for Debian, as a dependency of other packages, and have noticed that there is a test that seems to be flaky across multiple builds/autopkgtests for the latest release (0.8.0):

=== RUN   TestHedgedResponseWins
    hedged_test.go:363: Unnexpected actualRoundTrips: 4
--- FAIL: TestHedgedResponseWins (0.60s)

(See https://buildd.debian.org/status/fetch.php?pkg=golang-github-cristalhq-hedgedhttp&arch=all&ver=0.8.0-1&stamp=1692386052&raw=0, https://ci.debian.net/data/autopkgtest/testing/ppc64el/g/golang-github-cristalhq-hedgedhttp/36961327/log.gz, https://ci.debian.net/data/autopkgtest/testing/i386/g/golang-github-cristalhq-hedgedhttp/36953254/log.gz)

Investigate Best Practices with HTTP2

hedgedhttp cancels the context of the request which appears to have some issues with HTTP2. I'm unsure if everything is working as intended or if modifications could be made to this library to improve interaction with HTTP2. To demonstrate the issue at hand (without using hedgedhttp):

	client := &http.Client{
		Transport: &http2.Transport{},
	}

	req, err := http.NewRequest("GET", "https://google.com", nil)
	if err != nil {
		panic(err)
	}

	ctx, cancel := context.WithCancel(context.Background())
	req = req.WithContext(ctx)
	resp, err := client.Do(req)
	if err != nil {
		panic(err)
	}

	cancel()

	buffer := make([]byte, 1000000)
	_, err = resp.Body.Read(buffer)
	if err != nil && err != io.EOF {
		panic(err)
	}

	fmt.Println(string(buffer))

This code panics with error "context canceled" most of the time and occasionally panics with "unexpected EOF" (but never completes successfully).

Buried deep in the code http2 is using a pipe. The Read method is checking it's local member p.err which contains one of the above errors and it is returned all the way back to calling code. This is being set through CloseWithError which is triggered by the cancel() call.

CloseWithError is initiated (through a few layers) here:
https://github.com/golang/net/blob/abc453219eb5/http2/transport.go#L2287
Perhaps the transport/http2 pipe is reused across multiple http2 requests which is why I'm intermittently seeing it with the GCS client?

hedgedhttp is triggering this same behavior when interacting with GCS using the official GCS client.

Should we auto detect http2 and not cancel? Should we make cancelling optional? Should we just not cancel at all?