Un enfoque alternativo para limitar la velocidad

Hace unas semanas en Figma, experimentamos nuestro primer ataque de spam. Esto demostró el valor del limitador de velocidad de Figma y finalmente puso fin al viejo chiste de que lo había construido en vano.

Durante el ataque, los spammers enviaron invitaciones no solicitadas para documentos a decenas de direcciones de correo electrónico. Si no hubiéramos descubierto el ataque, podríamos haber enfrentado un enorme aumento en nuestros costos de entrega y una disminución en nuestra reputación de remitente de correo electrónico. Afortunadamente, nos enteramos del ataque desde el principio y evitamos este resultado porque nuestro limitador de velocidad detectó la gran cantidad de solicitudes de los spammers.

Nuestro sistema de limitación de velocidad es de cosecha propia y me gustaría explicar su diseño en caso de que sea útil para otros. Combina algunas técnicas estándar para controlar la velocidad a la que las personas envían solicitudes a su servidor, y es relativamente preciso, simple y eficiente en cuanto al espacio. Si es una empresa que desarrolla aplicaciones web a escala del consumidor, nuestro limitador de tarifas puede evitar que los usuarios perjudiquen la disponibilidad de su sitio web con una serie de solicitudes. También descubrió que es excelente para detener los ataques de spam.

Para aquellos que no están familiarizados, un limitador de velocidad limita la cantidad de solicitudes que un remitente, esto podría ser un usuario o una dirección IP, puede emitir en un período de tiempo específico (por ejemplo, 25 solicitudes por minuto). En el caso de Figma, también necesitaba:

  • almacenar datos externamente para que las múltiples máquinas que ejecutan nuestra aplicación web puedan compartirlos
  • no ralentizar apreciablemente las solicitudes web
  • expulsar eficientemente datos obsoletos
  • limitar con precisión el uso excesivo de nuestra aplicación web
  • use la menor memoria posible

Los primeros tres requisitos fueron fáciles de cumplir. En Figma, utilizamos dos almacenes de datos externos: Redis y PostgreSQL, y Redis era la mejor ubicación para guardar los datos de seguimiento. Redis es un almacén de datos en memoria que ofrece lecturas y escrituras extremadamente rápidas en relación con PostgreSQL, una base de datos relacional en disco. Aún mejor, es simple especificar cuándo Redis debe eliminar los datos caducados.

Encontrar una manera de satisfacer los dos últimos requisitos (controlar con precisión el tráfico web y minimizar el uso de memoria) fue más difícil. Aquí están las implementaciones de limitador de velocidad existentes que consideré:

  • Cubo de fichas
  • Ventanas fijas
  • Registro de ventana deslizante

Veamos cómo funciona cada uno de ellos y compárelos en términos de precisión y uso de memoria. Esto nos dará un poco de contexto para el enfoque final que tomamos para construir el limitador de velocidad que nos libró de los spammers.

Cubo de fichas

Una simple búsqueda en Google de "algoritmo de límite de velocidad" nos señala el clásico algoritmo de depósito de tokens (o depósito con fugas como algoritmo de medidor). Para cada usuario único, registraríamos la marca de tiempo de Unix de su última solicitud y el recuento de tokens disponibles dentro de un hash en Redis. Almacenaríamos estos dos valores en un hash en lugar de dos claves Redis separadas para la eficiencia de la memoria. Un ejemplo de hash se vería así:

Al usuario 1 le quedan dos tokens en su cubo de tokens e hizo su última solicitud el jueves 30 de marzo de 2017 a las 10:00 GMT.

Cada vez que llega una nueva solicitud de un usuario, el limitador de velocidad tendría que hacer varias cosas para rastrear el uso. Recogería el hash de Redis y volvería a llenar los tokens disponibles en función de una tasa de recarga elegida y el momento de la última solicitud del usuario. Luego, actualizaría el hash con la marca de tiempo de la solicitud actual y el nuevo recuento de tokens disponibles. Cuando el recuento de tokens disponible cae a cero, el limitador de velocidad sabe que el usuario ha excedido el límite.

Si el depósito de tokens del Usuario 1 se vacía más rápido de lo que se rellena y no quedan tokens, el Usuario 1 ha excedido el límite de velocidad.

A pesar de la elegancia del algoritmo de depósito de fichas y la pequeña huella de memoria, sus operaciones de Redis no son atómicas. En un entorno distribuido, el comportamiento de "leer y luego escribir" crea una condición de carrera, lo que significa que el limitador de velocidad a veces puede ser demasiado indulgente.

Si solo queda un token y las operaciones de Redis de dos servidores se intercalan, ambas solicitudes se dejarán pasar.

Imagínese si solo hubiera un token disponible para un usuario y ese usuario emitiera múltiples solicitudes. Si dos procesos separados atendieron cada una de estas solicitudes y leyeron simultáneamente el recuento de tokens disponibles antes de que alguno de ellos lo actualizara, cada proceso pensaría que al usuario le queda un token y que no ha alcanzado el límite de velocidad.

Nuestra implementación del depósito de tokens podría alcanzar la atomicidad si cada proceso fuera a buscar un bloqueo de Redis durante la duración de sus operaciones de Redis. Sin embargo, esto se haría a expensas de ralentizar las solicitudes concurrentes del mismo usuario e introducir otra capa de complejidad. Alternativamente, podríamos hacer que las operaciones de Redis del cubo de tokens sean atómicas a través de secuencias de comandos Lua. Sin embargo, por simplicidad, decidí evitar las complicaciones innecesarias de agregar otro lenguaje a nuestra base de código.

Ventanas fijas

Como segundo enfoque, consideré los mostradores de ventanas fijas. Es un algoritmo simple y eficiente en la memoria que registra el número de solicitudes de un remitente que ocurren en el intervalo de tiempo del límite de velocidad. A diferencia del algoritmo de depósito de tokens, las operaciones de Redis de este enfoque son atómicas. Cada solicitud incrementaría una clave Redis que incluía la marca de tiempo de la solicitud. Una clave Redis dada podría verse así:

El usuario 1 realizó una solicitud entre las 10:00:00 a.m. GMT y las 10:00:59 GMT el jueves 30 de marzo de 2017.

Al incrementar el recuento de solicitudes para una marca de tiempo dada, comparamos su valor con nuestro límite de velocidad para decidir si rechazamos la solicitud. También le diríamos a Redis que expirara la clave cuando pasara el minuto actual para garantizar que los contadores obsoletos no se queden para siempre.

Cuando el valor de la última clave Redis excede el umbral de solicitud, el Usuario 1 ha excedido el límite de velocidad.

Aunque el enfoque de ventana fija ofrece un modelo mental directo, a veces puede dejar pasar el doble de solicitudes permitidas por minuto. Por ejemplo, si nuestro límite de velocidad fuera de 5 solicitudes por minuto y un usuario hiciera 5 solicitudes a las 11:00:59, podría hacer 5 solicitudes más a las 11:01:00 porque comienza un nuevo contador al comienzo de cada minuto. A pesar de un límite de 5 solicitudes por minuto, ¡ahora permitimos 10 solicitudes en menos de un minuto!

Si contamos las solicitudes en ventanas de minutos fijas, podríamos dejar pasar hasta el doble del número de solicitudes permitidas por minuto.

Podríamos evitar este problema agregando otro límite de velocidad con un umbral más pequeño y una ventana de cumplimiento más corta, p. Ej. 2 solicitudes por segundo además de 5 solicitudes por minuto, pero esto complicaría demasiado el límite de velocidad. Podría decirse que también impondría una restricción demasiado severa sobre la frecuencia con la que el usuario podría realizar solicitudes.

Registro de ventana deslizante

La implementación del limitador de velocidad final que consideré optimiza la precisión: solo almacena una marca de tiempo para cada solicitud. Como describe Peter Hayes, podríamos rastrear eficientemente todas las solicitudes de un usuario en un solo conjunto ordenado.

Las tres solicitudes del Usuario 1 el jueves 30 de marzo de 2017 a las 10:00:00, 10:00:54 y 10:01:38 GMT se ordenan por marca de tiempo de microsegundos de Unix.

Cuando la aplicación web procesa una solicitud, inserta un nuevo miembro en el conjunto ordenado con un valor de clasificación de la marca de tiempo de microsegundos de Unix. Esto nos permitiría eliminar de manera eficiente a todos los miembros del conjunto con marcas de tiempo desactualizadas y contar el tamaño del conjunto después. El tamaño del conjunto ordenado sería igual al número de solicitudes en la última ventana de tiempo deslizante.

Cuando el tamaño del conjunto ordenado del Usuario 1 excede el umbral de solicitud, el Usuario 1 ha excedido el límite de velocidad.

Tanto este algoritmo como el enfoque de los contadores de ventanas fijas comparten una secuencia de operación atómica de "escribir y luego leer" Redis, pero el primero produce un efecto secundario notable. A saber, el limitador de velocidad continúa contando solicitudes incluso después de que el usuario excede el límite de velocidad. Me sentí cómodo con este comportamiento, ya que solo extendería la prohibición de un usuario malintencionado en lugar de dejar pasar sus solicitudes tan pronto como haya pasado el tiempo.

Si bien la precisión del enfoque de registro de ventana deslizante puede ser útil para una API de desarrollador, deja una huella de memoria considerablemente grande porque almacena un valor para cada solicitud. Esto no era ideal para Figma. Un límite de tarifa única de 500 solicitudes por día por usuario en un sitio web con 10,000 usuarios activos por día podría significar hipotéticamente almacenar 5,000,000 de valores en Redis. Si cada valor de marca de tiempo almacenado en Redis fuera incluso un entero de 4 bytes, esto tomaría ~ 20 MB (4 bytes por marca de tiempo * 10,000 usuarios * 500 solicitudes / usuario = 20,000,000 bytes).

Ventanas correderas

Finalmente, los dos últimos enfoques de limitación de velocidad (contadores de ventanas fijas y registro de ventanas deslizantes) inspiraron el algoritmo que detuvo a los spammers. Contamos las solicitudes de cada remitente utilizando múltiples ventanas de tiempo fijo 1/60 del tamaño de la ventana de tiempo de nuestro límite de tarifa.

Por ejemplo, si tenemos un límite de tarifa por hora, incrementamos los contadores específicos de la marca de tiempo actual de Unix y calculamos la suma de todos los contadores en la última hora cuando recibimos una nueva solicitud. Para reducir nuestra huella de memoria, almacenamos nuestros contadores en un hash de Redis: ofrecen un almacenamiento extremadamente eficiente cuando tienen menos de 100 claves. Cuando cada solicitud incrementa un contador en el hash, también establece que el hash caduque una hora más tarde. En el caso de que un usuario haga solicitudes cada minuto, el hash del usuario puede crecer al retener los contadores para marcas de tiempo pasadas. Prevenimos esto eliminando regularmente estos contadores cuando hay un número considerable de ellos.

Cuando la suma de los contadores con marcas de tiempo en la última hora excede el umbral de solicitud, el Usuario 1 ha excedido el límite de velocidad.

Comparemos el uso de memoria de este algoritmo con nuestro cálculo del algoritmo de registro de ventana deslizante. Si tenemos un límite de 500 solicitudes diarias por usuario en un sitio web con 10,000 usuarios activos, a lo sumo necesitaríamos almacenar ~ 600,000 valores en Redis. Eso tiene una huella de memoria de ~ 2.4 MB (4 bytes por contador * 60 contadores * 10,000 usuarios = 2,400,000 bytes). Esto es un poco más escalable.

Consideraciones prácticas

Al usar contadores de ventana fijos con una relación de 1:60 entre la ventana de tiempo del contador y la ventana de tiempo de cumplimiento del límite de velocidad, nuestro limitador de velocidad fue preciso hasta el segundo y minimizó significativamente el uso de memoria. En la práctica, sin embargo, un gran intervalo de tiempo de aplicación, p. Ej. una hora: redujo ligeramente la precisión del limitador de velocidad. Esto se ilustra mejor a través de un ejemplo: para un límite de tarifa por hora, cuando el limitador de velocidad verifica el uso a las 11:00:35, ignora las solicitudes que ocurrieron entre las 10:00:00 y las 10:00:59.

Si contamos las solicitudes en ventanas de 60 minutos fijos y verificamos la cantidad de solicitudes cuando estamos dentro de una ventana de minutos fijos, podemos subestimar la cantidad total de solicitudes en la última hora. Arriba, el limitador de velocidad ignora las tres solicitudes que ocurrieron entre las 10:00:00 y las 10:00:59.

Este leve grado de clemencia variable (hasta 59 segundos) puede ser aceptable según su caso de uso. En nuestra situación, sin embargo, preferimos que nuestro limitador de velocidad sea a veces un poco más duro en lugar de levemente indulgente, por lo que calculé la suma de todos los contadores en la última hora y un minuto cada vez que la marca de tiempo actual no era divisible por 60. Variable la restricción podría incluso ser útil para desalentar las secuencias de comandos programáticas contra el sitio.

Finalmente, tuvimos que reflexionar sobre cómo responder a los usuarios que excedieron el límite de velocidad. Tradicionalmente, las aplicaciones web responden a las solicitudes de los usuarios que superan el límite de velocidad con un código de respuesta HTTP de 429. Nuestro limitador de velocidad inicialmente también lo hizo. Pero en el caso del ataque de spam de Figma, nuestros atacantes vieron cambiar el código de respuesta de 200 a 429 y simplemente crearon nuevas cuentas para eludir la limitación de velocidad en sus cuentas bloqueadas. En respuesta, implementamos una prohibición paralela: en la superficie, los atacantes continuaron recibiendo un código de respuesta HTTP 200, pero detrás de escena simplemente dejamos de enviar invitaciones de documentos después de que excedieron el límite de velocidad.

Mientras el ataque de spam ha terminado por ahora, nuevos tipos de incidentes pueden ocurrir y ocurrirán en el futuro y continuaremos ajustando nuestro limitador de velocidad según sea necesario.

¿Te gustaría abordar problemas de ingeniería difíciles como este? Figma está construyendo una herramienta de diseño colaborativo basada en navegador, ¡y estamos contratando! Si le gusta esta historia, suscríbase aquí para recibir actualizaciones cuando publiquemos nuevo contenido editorial.