Несколько недель назад в Figma мы впервые испытали спам-атаку. Это доказало ценность ограничителя скорости в Figma и, наконец, положило конец давней шутке о том, что я напрасно построил его.

Во время атаки спамеры рассылали незапрашиваемые приглашения на документы на множество адресов электронной почты. Если бы мы не обнаружили атаку, мы могли столкнуться с огромным ростом наших затрат на доставку и падением репутации отправителя электронной почты. К счастью, мы узнали об атаке на раннем этапе и избежали этого результата, потому что наш ограничитель скорости обнаружил поток запросов от спамеров.

Наша система ограничения скорости является доморощенной, и я хотел бы объяснить ее структуру, если она будет полезна другим. Он сочетает в себе несколько стандартных методов управления скоростью, с которой люди отправляют запросы на ваш сервер, и является относительно точным, простым и компактным. Если вы компания, разрабатывающая веб-приложения в масштабе потребителя, наш ограничитель скорости не позволит пользователям повредить доступность вашего веб-сайта из-за большого количества запросов. Как мы обнаружили, он также отлично подходит для предотвращения спам-атак.

Для тех, кто не знаком, ограничитель скорости ограничивает количество запросов, которые отправитель - это может быть пользователь или IP-адрес - может отправить за определенный промежуток времени (например, 25 запросов в минуту). В случае с Figma также необходимо:

  • хранить данные извне, чтобы несколько компьютеров, на которых запущено наше веб-приложение, могли их совместно использовать
  • существенно не замедляют веб-запросы
  • эффективно удалять устаревшие данные
  • точно ограничить чрезмерное использование нашего веб-приложения
  • используйте как можно меньше памяти

Первые три требования выполнить было несложно. В Figma мы используем два внешних хранилища данных - Redis и PostgreSQL - и Redis был лучшим местом для сохранения данных отслеживания. Redis - это хранилище данных в памяти, которое обеспечивает чрезвычайно быстрое чтение и запись по сравнению с PostgreSQL, реляционной базой данных на диске. Более того, просто указать, когда Redis должен удалять просроченные данные.

Найти способ удовлетворить последние два требования - точно контролировать веб-трафик и минимизировать использование памяти - было более сложной задачей. Вот существующие реализации ограничителя скорости, которые я рассмотрел:

  • Ведро токенов
  • Фиксированные оконные счетчики
  • Журнал сдвижного окна

Давайте посмотрим, как работает каждый из них, и сравним их с точки зрения точности и использования памяти. Это даст нам некоторый контекст для окончательного подхода, который мы использовали для создания ограничителя скорости, который избавил нас от спамеров.

Ведро токенов

Простой поиск в Google по запросу алгоритм ограничения скорости указывает нам на классический алгоритм token bucket (или дырявый bucket как алгоритм счетчика). Для каждого уникального пользователя мы будем записывать временную метку Unix последнего запроса и количество доступных токенов в хэш Redis. Мы бы сохранили эти два значения в хэше, а не как два отдельных ключа Redis для эффективности памяти. Пример хеша будет выглядеть так:

Всякий раз, когда от пользователя поступает новый запрос, ограничитель скорости должен будет выполнить ряд действий для отслеживания использования. Он получит хэш из Redis и пополнит доступные токены в зависимости от выбранной скорости пополнения и времени последнего запроса пользователя. Затем он обновит хэш с отметкой времени текущего запроса и новым количеством доступных токенов. Когда количество доступных токенов падает до нуля, ограничитель скорости знает, что пользователь превысил лимит.

Несмотря на элегантность алгоритма token bucket и крошечный объем памяти, его операции Redis не атомарны. В распределенной среде поведение «чтение и затем запись» создает состояние гонки, что означает, что ограничитель скорости иногда может быть слишком мягким.

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

Наша реализация token bucket могла бы достичь атомарности, если бы каждый процесс извлекал блокировку Redis на время своих операций Redis. Это, однако, произойдет за счет замедления одновременных запросов от одного и того же пользователя и внесения еще одного уровня сложности. В качестве альтернативы, мы могли бы сделать операции Redis ведра токенов атомарными с помощью сценариев Lua. Однако для простоты я решил избежать ненужных сложностей, связанных с добавлением другого языка в нашу кодовую базу.

Фиксированные оконные счетчики

В качестве второго подхода я рассмотрел фиксированные оконные счетчики. Это простой, эффективный с точки зрения памяти алгоритм, который записывает количество запросов от отправителя, происходящих за временной интервал ограничения скорости. В отличие от алгоритма token bucket, в этом подходе операции Redis атомарны. Каждый запрос будет увеличивать ключ Redis, который включает временную метку запроса. Данный ключ Redis может выглядеть так:

При увеличении счетчика запросов для данной отметки времени мы сравниваем ее значение с нашим пределом скорости, чтобы решить, отклонять ли запрос. Мы также сказали бы Redis, чтобы срок действия ключа истекал по истечении текущей минуты, чтобы гарантировать, что устаревшие счетчики не останутся навсегда.

Хотя подход с фиксированным окном предлагает простую ментальную модель, иногда он может пропускать вдвое больше разрешенных запросов в минуту. Например, если наш предел скорости составлял 5 запросов в минуту, а пользователь сделал 5 запросов в 11:00:59, они могли бы сделать еще 5 запросов в 11:01:00, потому что новый счетчик начинается в начале каждой минуты. Несмотря на ограничение скорости в 5 запросов в минуту, теперь мы разрешили 10 запросов менее чем за минуту!

Мы могли бы избежать этой проблемы, добавив еще один предел скорости с меньшим порогом и более коротким окном принудительного исполнения - например, 2 запроса в секунду в дополнение к 5 запросам в минуту, но это приведет к чрезмерному усложнению ограничения скорости. Возможно, это также наложило бы слишком строгое ограничение на то, как часто пользователь может делать запросы.

Журнал сдвижного окна

Последняя реализация ограничителя скорости, которую я считал оптимизированной для точности, просто сохраняет временную метку для каждого запроса. Как описывает Питер Хейс, мы могли эффективно отслеживать все запросы пользователей в едином отсортированном наборе.

Когда веб-приложение обрабатывает запрос, оно вставляет новый член в отсортированный набор со значением сортировки микросекундной временной метки Unix. Это позволит нам эффективно удалить все элементы набора с устаревшими метками времени и впоследствии подсчитать размер набора. Тогда размер отсортированного набора будет равен количеству запросов в самом последнем скользящем временном окне.

И этот алгоритм, и подход со счетчиками с фиксированным окном используют атомарную последовательность операций Redis «запись и затем чтение», но первый дает заметный побочный эффект. А именно, ограничитель скорости продолжает подсчитывать запросы даже после того, как пользователь превышает ограничение скорости. Мне было комфортно с таким поведением, поскольку оно просто продлит бан для злоумышленника, вместо того, чтобы пропускать его запросы, как только пройдет промежуток времени.

Хотя точность подхода журнала со скользящим окном может быть полезна для API разработчика, он оставляет довольно большой объем памяти, поскольку сохраняет значение для каждого запроса. Это было не идеально для Figma. Единое ограничение скорости в 500 запросов в день на пользователя на веб-сайте с 10 000 активных пользователей в день может гипотетически означать хранение 5 000 000 значений в Redis. Если бы каждое сохраненное значение метки времени в Redis было даже 4-байтовым целым числом, это заняло бы ~ 20 МБ (4 байта на метку времени * 10 000 пользователей * 500 запросов на пользователя = 20 000 000 байт).

Счетчики раздвижных окон

В конечном счете, последние два подхода к ограничению скорости - счетчики с фиксированным окном и журнал с скользящим окном - вдохновили алгоритм, который останавливал спамеров. Мы подсчитываем запросы от каждого отправителя, используя несколько фиксированных временных окон, составляющих 1/60 от временного окна нашего ограничения скорости.

Например, если у нас есть почасовая ставка, мы увеличиваем счетчики, специфичные для текущей минутной метки времени Unix, и вычисляем сумму всех счетчиков за последний час, когда получаем новый запрос. Чтобы уменьшить объем памяти, мы храним счетчики в хэше Redis - они предлагают чрезвычайно эффективное хранилище, когда у них меньше 100 ключей. Когда каждый запрос увеличивает счетчик в хэше, он также устанавливает срок действия хэша на час позже. В случае, если пользователь делает запросы каждую минуту, хэш пользователя может вырасти из-за удержания счетчиков для прошлых временных меток. Мы предотвращаем это, регулярно удаляя эти счетчики, когда их много.

Давайте сравним использование памяти этим алгоритмом с нашим расчетом из алгоритма журнала скользящего окна. Если у нас есть ограничение скорости 500 запросов в день на пользователя на веб-сайте с 10 000 активных пользователей, нам потребуется хранить в Redis не более 600 000 значений. Таким образом, объем памяти составляет ~ 2,4 МБ (4 байта на счетчик * 60 счетчиков * 10 000 пользователей = 2 400 000 байтов). Это немного более масштабируемо.

Практические соображения

Используя счетчики с фиксированным окном с соотношением 1:60 между временным окном счетчика и временным окном применения ограничения скорости, наш ограничитель скорости работал с точностью до секунды и значительно сокращал использование памяти. Однако на практике большое временное окно принудительного исполнения - например, один час - немного снижена точность ограничителя скорости. Лучше всего это проиллюстрировать на примере: для почасового ограничения скорости, когда ограничитель скорости проверяет использование в 11:00:35, он игнорирует запросы, которые произошли между 10:00:00 и 10:00:59.

Эта небольшая степень изменчивой снисходительности - до 59 секунд - может быть приемлемой в зависимости от вашего варианта использования. В нашей ситуации, однако, мы предпочли, чтобы наш ограничитель скорости иногда был немного жестче, а не мягче, поэтому я вычислял сумму всех счетчиков за последний час и одну минуту, когда текущая временная метка не делится на 60. Переменная Ограничения могут даже быть полезны для предотвращения написания программных сценариев на сайте.

Наконец, нам пришлось задуматься о том, как реагировать на пользователей, которые превысили лимит скорости. Традиционно веб-приложения отвечают на запросы от пользователей, которые превышают ограничение скорости, с кодом ответа HTTP 429. Наш ограничитель скорости изначально делал то же самое. Но в случае спам-атаки Figma наши злоумышленники увидели, что код ответа изменился с 200 на 429, и просто создали новые учетные записи, чтобы обойти ограничение скорости для своих заблокированных учетных записей. В ответ мы реализовали теневой запрет: на первый взгляд злоумышленники продолжали получать ответный HTTP-код 200, но за кулисами мы просто перестали отправлять приглашения в документы после того, как они превысили лимит скорости.

Хотя спам-атака на данный момент закончена, новые типы инцидентов могут и будут происходить в будущем, и мы продолжим настраивать наш ограничитель скорости по мере необходимости.

Нравится решать такие сложные инженерные задачи? Figma создает инструмент для совместного проектирования на основе браузера, и мы нанимаем! Если вам нравится эта история, подпишитесь здесь, чтобы получать обновления, когда мы публикуем новые редакционные материалы.