понедельник, октября 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


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

Безопасное выполнение пакетных(bulk) операций в Redis с помощью Lua скриптов

Если бы было одно золотое правило при работе с Redis на бою, это должно было быть
Никогда не используйте KEYS
Команда KEYS блокирует event-loop Redis сервера, пока команда не будет выполнена. То есть пока сервер сканирует всё пространство ключей, он не будет обрабатывать команды и подключения от новых клиентов.

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

250Mb не так много. Правда в нашем случае это порядка миллиона ключей в хранилище к концу дня. И явно имело смысл убрать лишнее, учитывая, что наш нормальный суточный "расход" был в районе 30-50Mb.

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

Очевидно, мы предпочли второй вариант.

Зная, что мы не должны использовать KEYS (я же говорил, что вы никогда не должны использовать KEYS?), моя первая попытка использовать команду SCAN, чтобы получить список ключей и выставить им TTL. Я начал со скрипта из этого топика на StackOverflow и немного изменил его, потому что результат бы не таким, как я ожидал.

Мой скрипт:
#!/bin/bash

if [ $# -ne 3 ]
then
  echo "Expire keys from Redis matching a pattern using SCAN & EXPIRE"
  echo "Usage: $0 <host> <port> <pattern>"
  exit 1
fi

cursor=-1
keys=""

while [ $cursor -ne 0 ]; do
  if [ $cursor -eq -1 ]
  then
    cursor=0
  fi

  reply=$(redis-cli -h $1 -p $2 SCAN $cursor MATCH $3)
  cursor=$(expr "$reply" : '\([0-9]*[0-9 ]\)')

  keys=$(echo $reply | awk '{for (i=2; i<NF; i++) print $i}')
  [ -z "$keys" ] && continue

  for key in $keys; do
    redis-cli -h $1 -p $2 EXPIRE $key 60
  done
done
SCAN возвращает курсор и список ключей. А может и не вернуться ключей вообще. Нужно вытащить ключи и курсор (строки 19-22) и для каждого ключа выполнить expire (строки 25-27).
Обрабатываем первый набор ключей и возвращаемся к началу цикла. Снова вызываем команду SCAN, на этот раз с помощью курсора, который был возвращен в предыдущий раз. Таким образом, Redis знает, где мы были и на чём закончили.

Redis возвращает курсор 0(ноль) , если она мы прошлись по всем ключам. И когда это произойдет мы выйдем из цикла.

Это немного медленно ...

Скрипт работал хорошо, правда со скоростью порядка 100 ключей в секунду. С очень небольшой базой данных, это может быть хорошим решением, но в нашем случае выходило порядка 3 часов. Я считал, что мы могли сделать лучше.

Redis поддерживаем Lua скрипты. Мы не использовали Lua раньше, но его синтаксис выглядит достаточно простым.

Чтобы вызвать скрипт вы просто передаёте его как аргумент в команду EVAL вместе с количеством ключей, самими ключами и любыми другими аргументами. Простой пример (из документации):
> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 key1 key2 first second
1) "key1"
2) "key2"
3) "first"
4) "second"
И если в myscript.lua лежит
return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}
Его можно вызвать вот так
redis-cli EVAL "$(cat ./myscript.lua)" 2 key1 key2 first second
(кавычки вокруг cat необходимы)

Так что я переписал Bash скрипт из моей первой попытки на вызов Lua скрипта:
#!/bin/bash

if [ $# -ne 3 ]
then
  echo "Expire keys from Redis matching a pattern using SCAN & EXPIRE"
  echo "Usage: $0 <host> <port> <pattern>"
  exit 1
fi

cursor=-1
keys=""

while [[ $cursor -ne 0 ]]; do
  if [[ $cursor -eq -1 ]]
  then
    cursor=0
  fi

  reply=$(redis-cli -h $1 -p $2 SCAN $cursor MATCH $3 COUNT 100)
  cursor=$(expr "$reply" : '\([0-9]*[0-9 ]\)')
  echo "Cursor: $cursor"

  keys=$(echo $reply | awk '{for (i=2; i<NF; i++) print $i}')
  [ -z "$keys" ] && continue

  keya=( $keys )
  count=$(echo ${#keya[@]})
  redis-cli -h $1 -p $2 EVAL "$(cat expire.lua)" $count $keys
done
(ссылка на github)

Нам потребуется немного дополнительной логики, т.к. мы должны знать количество ключей, которое мы планируем передать в команду EVAL. И SCAN не возвращает постоянное количество ключей. Т.е. нужно преобразовать ключи в массив, и подсчитать количество элементов. Я также выставил параметр COUNT в команде SCAN, чтобы увеличить количество ключей, которое нам должны вернуть за раз. По умолчанию значение COUNT равно 10 и это не имеет значения, когда вы вызываете Redis-CLI для каждого полученного ключа. Когда вы собираетесь вызывать EVAL на каждый SCAN, увеличение этого значения в 10 раз означает, что вы сократите количество вызовов в цикле так же в 10 раз.

Lua скрипт

Скрипт пробегает по всем переданным ключам и если TTL не -1 то выполняет для такого ключа EXPIRE. Можно просто выполнить EXPIRE для всех ключей, если вам не нужно заботиться о верном значении TTL.

Переданные ключи доступны в переменной KEYS, а аргументы в ARGS. В нашем случае нам ARGS не нужны и мы просто пробегаем по всем KEYS:
local modified={};

for i,k in ipairs(KEYS) do
    local ttl=redis.call('ttl', k);
    if ttl == -1 then
        redis.call('EXPIRE', k, 60)
        modified[#modified + 1] = k;
    end
end

return modified;
(ссылка на github)
Вызываем bash скрипт (убедитесь что lua скрипт в той же директории):
bash ./expire-lua.sh 127.0.0.1 6379 'flashMap_*'
Где flashMap_* - префикс по которому мы ищем ключи.

С помощью этого простого Lua скрипта, который работает на блоках ключей из SCAN, мы значительно сократили количество вызовов в Redis и смогли очистить пространство ключей гораздо быстрее, чем раньше (в данном случае порядка 3500 ключей в секунду). А на практике - вместо 3-х часов потребовалось меньше минуты.

Можно изменить "размер блока" (количество ключей обрабатываемых с каждым EVAL) изменив значение аргумента COUNT команды SCAN. Например выставить его в 500:
reply=$(redis-cli -h $1 -p $2 SCAN $cursor MATCH $3 COUNT 500)
Правда не факт, что первые несколько вызовов вернут вам столько данных, сколько вы ждёте. Я заметил, что со значением 100 redis требуется всего пара итераций, чтобы начать возвращать блоки большого размера.

Можно кое что усовершенствовать. Мы могли бы перенести почти всё в Lua скрипт и просто передать размер блока и TTL как параметры. Мне показалось это немного громоздким.

В заключении я хотел бы посоветовать не ставить большие значения для COUNT. Во-первых, вы можете столкнуться с ограничением на количества аргументов, которые можно передать в LUA за раз. Во-вторых, скрипты Lua в Redis - это атомарные операции и работа redis будет блокирована во время их работы. Т.е. стоит использовать только очень быстрые Lua скрипты. В моем случае, размер блока 100 показал отличную производительность c приемлемой  блокировкой.

Оригинал статьи на английском языке http://www.gumtree.com/devteam/2014-08-19-safely-running-bulk-operations-on-redis-with-lua-scripts.html