Реализовать потокобезопасный in-memory rate limiter используя алгоритм Sliding Window или Token Bucket. Интерфейс: type RateLimiter interface { Allow(key string) bool } Требования: - Ограничение: N запросов за T секунд на один key - Потокобезопасная реализация - Без сторонних библиотек - Минимизировать блокировки - Рассказать: - возможные race conditions - влияние GC - поведение при большом количестве ключей Входные параметры: NewRateLimiter(limit int, window time.Duration)

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.
- Можно оптимизировать, используя кольцевые буферы или пул объектов.

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

---

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