Senior

Implementujte thread-safe in-memory rate limiter pomocou algoritmu Sliding Window alebo Token Bucket. Rozhranie: type RateLimiter interface { Allow(key string) bool } Požiadavky: - Obmedzenie: N požiadaviek za T sekúnd na jeden kľúč - Vlákno-bezpečná implementácia - Bez externých knižníc - Minimalizovať zámky - Vysvetlite: - možné race conditions - vplyv na GC - správanie pri veľkom počte kľúčov Vstupné parametre: NewRateLimiter(limit int, window time.Duration)

sobes.tech AI

Odpoveď od AI

go package ratelimiter

import ( "sync" "time" )

// RateLimiter ограничивает количество запросов по ключу // с использованием алгоритма Sliding Window. type RateLimiter interface { Allow(key string) bool }

// slidingWindowLimiter реализует RateLimiter // потокобезопасно, минимизируя блокировки. type slidingWindowLimiter struct { limit int window time.Duration mu sync.RWMutex // для каждого ключа храним срез меток времени запросов requests map[string][]time.Time }

func NewRateLimiter(limit int, window time.Duration) RateLimiter { return &slidingWindowLimiter{ limit: limit, window: window, requests: make(map[string][]time.Time), } }

func (rl *slidingWindowLimiter) Allow(key string) bool { now := time.Now() windowStart := now.Add(-rl.window)

rl.mu.Lock()
defer rl.mu.Unlock()

times := rl.requests[key]

// Удаляем устаревшие метки
i := 0
for ; i < len(times); i++ {
	if times[i].After(windowStart) {
		break
	}
}
times = times[i:]

if len(times) >= rl.limit {
	// Превышен лимит
	rl.requests[key] = times
	return false
}

// Добавляем текущий запрос
times = append(times, now)
rl.requests[key] = times
return true

}


### Объяснение
- Используется алгоритм Sliding Window: храним временные метки запросов за окно времени.
- Для каждого ключа — срез временных меток.
- При вызове Allow удаляем устаревшие метки, проверяем лимит, добавляем новую.
- Для потокобезопасности используется `sync.RWMutex`.

### Возможные race conditions
- Без блокировок возможна гонка при одновременном чтении и записи среза меток.
- Использование мьютекса предотвращает гонки.

### Влияние GC
- При большом количестве ключей и частых запросах срезы меток постоянно создаются и обрезаются, что может создавать нагрузку на GC.
- Можно оптимизировать, используя кольцевые буферы или пул объектов.

### Поведение при большом количестве ключей
- Память растёт пропорционально количеству активных ключей.
- Неиспользуемые ключи остаются в карте, что может привести к утечке памяти.
- Для решения можно реализовать периодическую очистку старых ключей.

---

Для минимизации блокировок можно использовать шардирование по ключам с несколькими мьютексами, но это усложнит реализацию.

Predchádzajúce Ďalej