Diseño de un limitador de velocidad

Aquí están mis notas sobre el diseño de un limitador de velocidad.

¿Qué es un limitador de velocidad?

• En las redes informáticas, la limitación de velocidad se utiliza para controlar la velocidad de las solicitudes enviadas o recibidas por un controlador de interfaz de red .
• En el lado HTTP, limita la cantidad de solicitudes de clientes que se pueden enviar durante un período específico.

• Los usuarios pueden crear 1 ticket cada 5 minutos
• Los usuarios pueden crear 2 cuentas por día con la misma dirección IP
• Los usuarios pueden intentar 5 intentos fallidos de inicio de sesión por hora con la misma dirección IP en un día

• Un limitador de velocidad evita los ataques DoS
• Detener el abuso del sistema
• Reduce el costo
• Evita la sobrecarga de servidores. También reduce la carga del servidor
• Mejore la experiencia del usuario con menos tráfico

• El limitador de velocidad no debería ralentizar el tiempo de respuesta HTTP de su sistema.
• Usa menos memoria
• Muestre excepciones a los usuarios cuando sus solicitudes estén bloqueadas debido a la limitación de velocidad.
• Su limitador de velocidad no debe afectar a todo el sistema. Por ejemplo, si su servidor de caché deja de funcionar, su sistema debe estar disponible.

• Hay diferentes formas de implementar un limitador de velocidad. Estos son; Implementación del lado del cliente, implementación del lado del servidor y una forma alternativa de usar una puerta de enlace API de terceros.
• En general, el lado del cliente es un lugar poco confiable para hacer cumplir la limitación de velocidad
• Una implementación del lado del servidor tiene algunas ventajas internas porque puede modificar la lógica en su extremo.
• El uso de una puerta de enlace API de terceros es útil a veces porque lleva tiempo implementarlo.

1- Cubo de fichas

• Dos parámetros principales; Tamaño del balde y tasa de recarga.
• Tamaño del cubo: número máximo de tokens permitidos
• Tasa de recarga: número de fichas puestas en el cubo en cualquier intervalo como cada segundo
• Suponiendo que tenemos un cubo, la capacidad se define como la cantidad de tokens que puede contener. Siempre que un consumidor desee acceder a un punto final de API, debe obtener un token del depósito. El token se elimina del depósito si está disponible y acepta la solicitud. Si el token no está disponible, el servidor rechaza la solicitud.
• En cada intervalo fijo, necesitamos recargar.
• Si necesitamos acelerar las solicitudes HTTP en función de las direcciones IP, cada dirección IP requiere un depósito.
• Puede causar condiciones de carrera en un entorno distribuido (Desventaja)

2- Cubo con fugas

• Cuando llega una solicitud HTTP, el sistema verifica la cola. Si la cola no está llena, la solicitud se agrega a la cola. De lo contrario, la solicitud se bloquea.
• Las solicitudes HTTP se extraen de la cola y se procesan a intervalos regulares.
• El procesamiento del primer elemento de la cola se produce a intervalos regulares o primero en entrar, primero en salir (FIFO)

• Divide la línea de tiempo en ventanas de tiempo de tamaño fijo
• Cada solicitud incrementa el contador.
• La ventana de tiempo se considera desde el inicio de la unidad de tiempo hasta el final de la unidad de tiempo.
• Complejidad espacial: O(1) — Almacenar el conteo de ventana actual Complejidad temporal: O(1) — Obtener y operación de incremento atómico simple

• El mayor problema con esto es que los consumidores pueden encontrar el tiempo de reinicio y maximizar la solicitud en un período de tiempo pequeño que pueden bombardear.

• el algoritmo de ventana fija tiene un problema como escribí. Permite que pasen más solicitudes en los bordes de una ventana. Un registro de ventana deslizante está resolviendo este problema.
• mantiene el tiempo de las solicitudes ordenado en un Conjunto o una Tabla (Ej: Redis)
• Cada minuto buscamos solicitudes más antiguas y las filtramos. Luego calcule la disponibilidad. Si la solicitud excede la tasa de umbral, entonces se retiene, de lo contrario, se atiende.
• Consume mucha memoria.
• Es costoso almacenar una cantidad ilimitada de registros para cada solicitud.
• Complejidad del espacio: O (Solicitudes máximas vistas en una ventana de tiempo) : almacena todas las marcas de tiempo de las solicitudes en una ventana de tiempo.
• Complejidad de tiempo: O (Solicitudes máximas vistas en un tiempo de ventana) : eliminación de un subconjunto de marcas de tiempo

1. Cuente el número total de elementos en el conjunto ordenado. Rechace la solicitud si este conteo es mayor que nuestro límite de regulación de "3".
2. Inserte la hora actual en el conjunto ordenado y acepte la solicitud.

• combina el bajo costo de procesamiento del algoritmo de ventana fija y las condiciones de contorno mejoradas del registro deslizante.
• Complejidad espacial: O (número de cubos)
• Complejidad de tiempo: O (1) : obtenga el cubo reciente, incremente y verifique con la suma total de cubos (se puede almacenar en una variable totalCount).
• Para obtener detalles sobre la implementación, puede seguir este artículo.
• Otro artículo para una mejor comprensión.

1. Retire todos los contadores que tengan más de 1 minuto.
2. incrementa el contador si la solicitud viene en el depósito actual.
3. Solicitud bloqueada si el cubo actual ya superó el límite de garganta.

Referencias

• https://www.quinbay.com/blog/rate-limiter-implementation-token-bucket-algorithm
• https://betterprogramming.pub/4-rate-limit-algorithms-every-developer-should-know-7472cb482f48
• https://codeminion.hashnode.dev/rate-limiting-algorithms
• https://goalgorithm.wordpress.com/2019/06/08/designing-an-api-rate-limiter/