понедельник, октября 20, 2014

Введение в ограничение числа запросов с Redis [часть 1]

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

Эта статья предполагает, что у вас есть некоторый опыт работы с Python и Redis и, в меньшей степени Lua, но и тем, у кого такого опыта нет тоже будет интересно.

Зачем ограничивать число запросов?

Например, Twitter ограничивает количество запросов к своему API, а Reddit и StackOverflow используют ограничения на количество сообщений и комментариев. Кто-то ограничивает количество запросов, чтобы оптимизировать утилизацию ресурсов, кто-то борется со спамерами. Иными словами, в современном интернете, ограничение числа запросов к платформе ставит своей целью ограничить влияние, которое может оказать пользователь. Независимо от причины, давайте исходить из того, что мы должны подсчитывать некоторые действия пользователя и предотвращать их, если пользователь достиг или превысил какой-то предел. Давайте начнем с ограничения количества запросов к некоторому API, в максимум 240 запросов в час на одного пользователя.

Мы знаем, что нам нужно подсчитывать действия и ограничивать пользователя, так что нам потребуется немного вспомогательного кода. Во-первых, мы должны иметь функцию, которая дает нам один или несколько идентификаторов для пользователя, выполняющего действие. Иногда это просто IP пользователя, иногда его идентификатор. Я предпочитаю использовать оба, если это возможно. По крайней мере IP, если пользователь не авторизован. Ниже функция, получающая IP и идентификатор пользователя, используя Flask плагин Flask-Login.
from flask import g, request

def get_identifiers():
    ret = ['ip:' + request.remote_addr]
    if g.user.is_authenticated():
        ret.append('user:%s'%g.user.get_id())
    return ret

Просто используйте счётчики

Теперь у нас есть функция, возвращающая идентификаторы пользователя и мы можем начать считать наши действия. Один из самых простых способов, доступных в Redis - вычислять ключ для диапазона времени и увеличивать в нём счётчик всякий раз, как происходит интересующее нас действие. Если число в счётчике превысило нужное нам значение, мы не позволим выполнить действие. Вот функция, которая использует автоматически потухающие ключи с диапазоном (и временем жизни) в 1 час:
import time

def over_limit(conn, duration=3600, limit=240):
    bucket = ':%i:%i'%(duration, time.time() // duration)
    for id in get_identifiers():
        key = id + bucket

        count = conn.incr(key)
        conn.expire(key, duration)
        if count > limit:
            return True

    return False
Эта достаточно простая функция. Для каждого идентификатора мы увеличиваем соответствующий ключ в Redis и выставляем ему время жизни в 1 час. Если значение счетчика превысило лимит вы вернём True. В противном случае вернём False.

Вот и всё. Ну или почти. Это позволяет нам решить нашу задачу - ограничить количество запросов до 240 в час для каждого пользователя. Реальность однако такова, что пользователи быстро заметят, что лимит сбрасывается в начале каждого часа. И ничто им не помешает сделать свои 240 запросов в течении пары секунд сразу в начале часа. Наша работа пойдёт в таком случае на смарку.

Используем различные диапазоны

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

Предположим мы решили, что 10 запросов в секунду, 120 запросов в минуту и 240 запросов в час достаточно для наших пользователей, и позволит нам лучше распределять запросы с течением времени.

Чтобы это сделать, мы можем просто использовать нашу функцию over_limit ():
def over_limit_multi(conn, limits=[(1, 10), (60, 120), (3600, 240)]):
    for duration, limit in limits:
        if over_limit(conn, duration, limit):
            return True
    return False
Это будет работать так как мы ожидали. Однако каждый из 3-х вызовов over_limit() может выполнить две команды Redis - одну для обновления счетчика и вторую для установки времени жизни для ключа. Мы выполним их для IP и идентификатора пользователя. В итоге может потребовать до 12 запросов в Redis чтобы просто сказать, что один человек превысил лимит по одной операции. Самый простой метод минимизировать число запросов к Redis - это использовать `pipelining` (конвейерные запросы). Такие запросы также называют в Redis транзакционными. В контексте Redis это означает, что вы пошлете много команд одним запросом.

Нам повезло, что наша функция over_limit() написана так, что можно легко заменить вызов INCR и EXPIRE на один запрос с MULTI. Это изменение позволит нам уменьшить число запросов к Redis с 12 до 6, когда мы используем её вместе с over_limit_multi().
def over_limit(conn, duration=3600, limit=240):
    pipe = conn.pipeline(transaction=True)
    bucket = ':%i:%i'%(duration, time.time() // duration)
    for id in get_identifiers():
        key = id + bucket

        pipe.incr(key)
        pipe.expire(key, duration)
        if pipe.execute()[0] > limit:
            return True

    return False
Сокращение количества обращений к Redis вдвое это здорово, но мы всё ещё делаем 6 запросов просто чтобы понять, может ли пользователь сделать вызов к API. Можно написать другой вариант over_limit_multi(), который делает все операции сразу и проверяет ограничения после, но очевидно, что реализация будет иметь несколько ошибок. У нас получится ограничить пользователей и позволить им делать не более 240 запросов в час, правда, в худшем случае, это будет всего 10 запросов в час. Да, ошибку можно исправить, сделав ещё один запрос к Redis, а можно просто перенести всю логику в Redis!

Считаем правильно

Вместо того, чтобы исправлять нашу предыдущую реализацию давайте давайте перенесём её в LUA скрипт, который мы выполним внутри Redis. В этом скрипте мы будем делать тоже самое, что делали выше - пройдемся по списку ограничений, для каждого идентификатора увеличим счетчик, обновим время жизни и проверим не превысил ли счетчик лимит.
import json

def over_limit_multi_lua(conn, limits=[(1, 10), (60, 125), (3600, 250)]):
    if not hasattr(conn, 'over_limit_multi_lua'):
        conn.over_limit_multi_lua = conn.register_script(over_limit_multi_lua_)

    return conn.over_limit_multi_lua(
        keys=get_identifiers(), args=[json.dumps(limits), time.time()])

over_limit_multi_lua_ = '''
local limits = cjson.decode(ARGV[1])
local now = tonumber(ARGV[2])
for i, limit in ipairs(limits) do
    local duration = limit[1]

    local bucket = ':' .. duration .. ':' .. math.floor(now / duration)
    for j, id in ipairs(KEYS) do
        local key = id .. bucket

        local count = redis.call('INCR', key)
        redis.call('EXPIRE', key, duration)
        if tonumber(count) > limit[2] then
            return 1
        end
    end
end
return 0
'''
Посмотрите на кусок кода сразу после 'local bucket'. Видите, что наш Lua скрипт выглядит как наше предыдущее решение и выполняет те же операции как и оригинальная over_limit()?

Заключение

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

Собственно, любой из вариантов наших ограничителей может пригодится в разных приложениях. 

Оригинал статьи на английском языке http://www.binpress.com/tutorial/introduction-to-rate-limiting-with-redis/155?utm_source=redisweekly&utm_medium=email


Отправить комментарий