go-chi / go-chi/httprate

Reduce dependencies through pluggable hashing

Open
#57 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
476
Forks
25
PR merge metrics
No merged PRs in 30d

Description

I'd like httprate to explore reducing dependencies, preferably to zero. While the current dependencies are very small/lightweight (and one is effectively an extension of stdlib), zero dependencies are still preferred, especially as supply chain attacks continue to grow in complexity and spread.

The 2 primary dependencies right now:

- `golang.org/x/sync` -- just used in tests right now (errgroup in particular), and quite easy to do right now without errgroup itself, especially since it's inside of tests. This should be a simple thing to remove, and I can open a PR to do that, if its OK.
- `github.com/zeebo/xxh3` -- used for key hashing, a particularly popular choice for something like a rate limiter.

I propose replacing **xxh3** with an implementation of FNV-1a, and potentially a `Option` parameter (or similar) that allows customizing it, if there is a specific desire (more reasoning below).

I've tested 3 variants:

- `github.com/zeebo/xxh3`
- pros: fast, relatively consistent timing growth.
- cons: extra dependency.
- `hash/fnv.New64a`
- pros: stdlib, don't have to maintain anything.
- cons: longer ns/op as the key length grows. stdlib implementation requires allocations/op. performance isn't good as-is.
- custom implementation of `hash/fnv.New64a`
- pros:
- **2-5x faster** than xxh3 for what I suspect is most-common length (IPv4/IPv6 addresses).
- **~5-10% slower** for likely-worst-case (ip + endpoint, ip + request ID, ip + uuid).
- all stdlib, ~13 LOC.
- cons:
- longer ns/op as the key length grows, but nowhere near as bad as stdlib. **~2-3x worse than xxh3 around 70 chars** (but still totally reasonable for almost any application).
- may be a "good enough" non-dependency implementation, but if we provide an `Option` to allow customizing the hash function, it still allows people to reach for something more performant.

Implementation of each:

```go
// LimitCounterKeyXXH3 hashes key with XXH3, matching httprate's local counter keying.
func LimitCounterKeyXXH3(key string) uint64 {
h := xxh3.New()
_, _ = h.WriteString(key)
return h.Sum64()
}

// LimitCounterKeyFNV64aStdlib hashes key with FNV-1a 64-bit via [hash/fnv.New64a].
func LimitCounterKeyFNV64aStdlib(key string) uint64 {
h := fnv.New64a()
_, _ = io.WriteString(h, key)
return h.Sum64()
}

// Ref: https://cs.opensource.google/go/go/+/refs/tags/go1.26.1:src/hash/fnv/fnv.go;l=31-40,130-138
const (
offset64 uint64 = 14695981039346656037
prime64 uint64 = 1099511628211
)

// LimitCounterKeyFNV64aInline hashes key with FNV-1a 64-bit using the same algorithm as
// [hash/fnv] digest64, without allocating a [hash.Hash64] each call.
func LimitCounterKeyFNV64aInline(key string) uint64 {
h := offset64
for i := 0; i < len(key); i++ {
h ^= uint64(key[i])
h *= prime64
}
return h
}
```

Benchmarks, comparing each solution above, over 5 iterations:

```
goos: linux
goarch: amd64
pkg: github.com/go-chi/httprate
cpu: AMD Ryzen 9 9900X3D 12-Core Processor
│ bench_results.txt │
│ sec/op │
LimitCounterKey_XXH3/1-12 11.17n ± ∞ ¹
LimitCounterKey_XXH3/10-12 14.39n ± ∞ ¹
LimitCounterKey_XXH3/25-12 14.89n ± ∞ ¹
LimitCounterKey_XXH3/50-12 15.36n ± ∞ ¹
LimitCounterKey_XXH3/100-12 16.97n ± ∞ ¹
LimitCounterKey_XXH3/200-12 18.06n ± ∞ ¹
LimitCounterKey_FNV64aStdlib/1-12 15.67n ± ∞ ¹
LimitCounterKey_FNV64aStdlib/10-12 19.40n ± ∞ ¹
LimitCounterKey_FNV64aStdlib/25-12 30.80n ± ∞ ¹
LimitCounterKey_FNV64aStdlib/50-12 53.02n ± ∞ ¹
LimitCounterKey_FNV64aStdlib/100-12 96.63n ± ∞ ¹
LimitCounterKey_FNV64aStdlib/200-12 172.1n ± ∞ ¹
LimitCounterKey_FNV64aInline/1-12 0.5086n ± ∞ ¹
LimitCounterKey_FNV64aInline/10-12 2.500n ± ∞ ¹
LimitCounterKey_FNV64aInline/25-12 8.005n ± ∞ ¹
LimitCounterKey_FNV64aInline/50-12 22.22n ± ∞ ¹
LimitCounterKey_FNV64aInline/100-12 46.85n ± ∞ ¹
LimitCounterKey_FNV64aInline/200-12 115.4n ± ∞ ¹
geomean 19.09n

│ bench_results.txt │
│ B/op │
LimitCounterKey_XXH3/1-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/10-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/25-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/50-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/100-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/200-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/1-12 16.00 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/10-12 24.00 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/25-12 40.00 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/50-12 72.00 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/100-12 120.0 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/200-12 216.0 ± ∞ ¹
LimitCounterKey_FNV64aInline/1-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/10-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/25-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/50-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/100-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/200-12 0.000 ± ∞ ¹

│ bench_results.txt │
│ allocs/op │
LimitCounterKey_XXH3/1-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/10-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/25-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/50-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/100-12 0.000 ± ∞ ¹
LimitCounterKey_XXH3/200-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/1-12 2.000 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/10-12 2.000 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/25-12 2.000 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/50-12 2.000 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/100-12 2.000 ± ∞ ¹
LimitCounterKey_FNV64aStdlib/200-12 2.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/1-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/10-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/25-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/50-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/100-12 0.000 ± ∞ ¹
LimitCounterKey_FNV64aInline/200-12 0.000 ± ∞ ¹
```

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.