Ограничитель скорости без блокировки ⇐ Python

[Anonymous]

Я работаю над многопоточным сервисом Python, которому необходимо ограничить скорость запросов на очень популярном пути кода. Моя текущая реализация использует дек, защищенный потоком.Lock, для хранения временных меток запроса и удаления записей старше временного окна. Хотя это работает правильно, профилирование показывает, что конфликт блокировок становится узким местом при высоком уровне параллелизма.
Я уже рассматривал или пробовал:

• Счетчики с фиксированным окном (слишком нестабильные на границах окон)
• Подходы в стиле сегмента токенов (обычно полагаются на блокировки или фоновые потоки пополнения)
• Сторонние библиотеки (не вариант в моей среде)

Поэтому я пытаюсь понять, возможен ли подход без блокировки в чистом Python, полагаясь на монотонное время и модель выполнения CPython.
Ниже: упрощенная версия моей текущей реализации на основе блокировки:

Код: Выделить всё

import time
import threading
from collections import deque

class RateLimiter:
def __init__(self, max_requests: int, window_ms: int):
self.max_requests = max_requests
self.window_ns = window_ms * 1_000_000
self.timestamps = deque()
self.lock = threading.Lock()

def allow(self) -> bool:
now = time.monotonic_ns()
cutoff = now - self.window_ns

with self.lock:
while self.timestamps and self.timestamps[0] < cutoff:
self.timestamps.popleft()

if len(self.timestamps) >= self.max_requests:
return False

self.timestamps.append(now)
return True

Эта реализация функционально правильна, но при высоком уровне параллелизма блокировка становится узким местом, так как каждый вызов методаallow() должен ее захватывать.
Вместо этого мне нужен ограничитель скорости скользящего окна с тем же поведением, но:

• Без блокировок (

  Код: Выделить всё

  threading.Lock

  , RLock и т. д.)
• Безопасно при одновременном доступе многих потоков
• Ограниченное использование памяти

Целевой интерфейс останется:

Код: Выделить всё

class RateLimiter:
def __init__(self, max_requests: int, window_ms: int):
...

def allow(self) -> bool:
...

Мои основные вопросы:

• Действительно ли в CPython достижим ограничитель скорости скользящего окна без блокировки?
• Какие гарантии (если таковые имеются) предоставляет CPython, чтобы сделать это безопасным?
• Какие компромиссы или крайние случаи мне следует использовать? знаете о сравнении с решением на основе блокировки?

Подробнее здесь: https://stackoverflow.com/questions/798 ... te-limiter