kacerrandClaude Fable 5
5e2d9400ac
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01GbnJj9ZqEx9nUvzkjdwfMq
75 lines
2.3 KiB
Go
75 lines
2.3 KiB
Go
// Exercise 03 — Token Bucket Rate Limiter
|
|
//
|
|
// ASSIGNMENT
|
|
// ----------
|
|
// Implement a token-bucket limiter:
|
|
//
|
|
// 1. NewLimiter(rate, burst): capacity `burst` tokens, refilled continuously
|
|
// at `rate` tokens/second. Bucket starts FULL.
|
|
// 2. Allow() consumes one token and returns true, or returns false if no
|
|
// token is available. Must be non-blocking and safe for concurrent use.
|
|
// 3. Refill must be LAZY — no background goroutine, no ticker. Compute the
|
|
// accrued tokens from elapsed time inside Allow().
|
|
// 4. Tokens never exceed `burst` (idle time must not build infinite credit).
|
|
//
|
|
// Run the tests: go test -race ./03-rate-limiter/
|
|
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"sync"
|
|
"time"
|
|
)
|
|
|
|
type Limiter struct {
|
|
|
|
// TODO: fields (mutex, current tokens, max, rate, last refill time)
|
|
mu sync.Mutex
|
|
tokens float64
|
|
max float64
|
|
rate float64
|
|
last time.Time
|
|
}
|
|
|
|
// NewLimiter returns a limiter allowing `rate` ops/sec with bursts up to `burst`.
|
|
// TODO: implement me.
|
|
func NewLimiter(rate float64, burst int) *Limiter {
|
|
return &Limiter{tokens: float64(burst), rate: rate, max: float64(burst), last: time.Now()}
|
|
}
|
|
|
|
// Allow reports whether one operation may proceed now.
|
|
// TODO: implement me.
|
|
func (l *Limiter) Allow() bool {
|
|
/*
|
|
1. Lock — refill + consume is a read-modify-write on two fields;
|
|
without the lock two goroutines can both see 1 token and both take it.
|
|
2. Lazy refill — tokens earned since the last call = elapsed * rate.
|
|
float64 so fractions (0.6 of a token) carry over instead of truncating to 0.
|
|
3. Cap at max — idle time must not build unlimited credit (burst is a ceiling).
|
|
4. Update last on EVERY call, granted or not — otherwise the same interval
|
|
is credited again on the next call.
|
|
5. If at least one whole token is available, take it and allow; else deny.
|
|
Non-blocking: never sleeps or waits.
|
|
*/
|
|
l.mu.Lock()
|
|
defer l.mu.Unlock()
|
|
l.tokens += l.rate * time.Since(l.last).Seconds()
|
|
if l.tokens > l.max {
|
|
l.tokens = l.max
|
|
}
|
|
l.last = time.Now()
|
|
if l.tokens >= 1 {
|
|
l.tokens--
|
|
return true
|
|
}
|
|
return false
|
|
}
|
|
|
|
func main() {
|
|
l := NewLimiter(5, 3) // 5/sec, burst 3
|
|
for i := 0; i < 10; i++ {
|
|
fmt.Printf("req %d: allowed=%v\n", i, l.Allow())
|
|
time.Sleep(100 * time.Millisecond)
|
|
}
|
|
}
|