Привет, Хабр!

Сегодня мы предлагаем вашему вниманию перевод сложной статьи о реализации распределенных блокировок средствами Redis и предлагаем поговорить о перспективности Redis как темы. Анализ рассматриваемого алгоритма Redlock от Мартина Клеппмана, автора книги "Высоконагруженные приложения", приведен здесь.


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

Существует ряд библиотек и постов, описывающих, как реализовать DLM (менеджер распределенных блокировок) при помощи Redis, но в каждой библиотеке используется собственный подход, и предоставляемые при этом гарантии довольно слабые по сравнению с тем, что достижимо при помощи чуть более сложного проектирования.

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

Реализации

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

• Redlock-rb (реализация для Ruby). Также существует форк Redlock-rb, добавляющий пакет (gem) для удобства распределения, и не только для этого.
• Redlock-py (реализация для Python).
• Aioredlock (реализация для Asyncio Python).
• Redlock-php (реализация для PHP).
• PHPRedisMutex (еще одна реализация для PHP)
• cheprasov/php-redis-lock (PHP-библиотека для блокировок)
• Redsync (реализация для Go).
• Redisson (реализация для Java).
• Redis::DistLock (реализация для Perl).
• Redlock-cpp (реализация для C++).
• Redlock-cs (реализация для C#/.NET).
• RedLock.net (реализация для C#/.NET). С поддержкой расширений async и lock.
• ScarletLock (реализация для C# .NET с конфигурируемым хранилищем данных)
• Redlock4Net (реализация для C# .NET)
• node-redlock (реализация для NodeJS). Включает поддержку продления блокировок.

Гарантии безопасности и доступности

Мы собираемся смоделировать наш проект всего с тремя свойствами, которые, на наш взгляд, дают минимальные гарантии, необходимые для эффективного использования распределенных блокировок.

1. Свойство безопасности: Взаимное исключение. В любой момент времени лишь один клиент может удерживать блокировку.
2. Свойство доступности A: Отсутствие взаимных блокировок. В конечном итоге всегда можно получить блокировку, даже если клиент, заблокировавший ресурс, откажет или попадет в другой сегмент диска.
3. Свойство доступности B: Отказоустойчивость. Пока большинство узлов Redis работает, клиенты способны приобретать и высвобождать блокировки.

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

Простейший способ блокировать ресурс при помощи Redis – создать ключ в инстансе. Обычно ключ создается с ограниченным временем жизни, это достигается при помощи предусмотренной в Redis возможности expires, поэтому рано или поздно этот ключ высвобождается (свойство 2 в нашем списке). Когда клиенту необходимо высвободить ресурс, он удаляет ключ.

На первый взгляд это решение вполне работает, но есть проблема: в нашей архитектуре возникает единая точка отказа. Что случится, если откажет ведущий инстанс Redis? Давайте тогда добавим ведомый! И будем им пользоваться, если ведущий недоступен. К сожалению, такой вариант нежизнеспособен. Сделав так, мы не сможем правильно реализовать свойство взаимного исключения, нужное нам для обеспечения безопасности, ведь репликация в Redis асинхронна.

Очевидно, что в такой модели возникает состояние гонки:

1. Клиент A приобретает блокировку на ведущем.
2. Ведущий отказывает до того, как запись в ключ будет передана ведомому.
3. Ведомый повышается до ведущего.
4. Клиент B приобретает блокировку того же ресурса, который уже заблокирован A. НАРУШЕНИЕ БЕЗОПАСНОСТИ!

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

Правильная реализация с единственным инстансом

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

Чтобы приобрести блокировку, поступим так:

SET resource_name my_random_value NX PX 30000

Эта команда устанавливает ключ, только если он еще не существует (опция NX), со сроком действия 30000 миллисекунд (опция PX). Для ключа задается значение “myrandomvalue”. Это значение должно быть уникальным в пределах всех клиентов и всех запросов на блокировку.
В принципе, случайное значение используется для безопасного высвобождения блокировки, при помощи скрипта, сообщающего Redis: удаляй ключ, только если он существует, и значение, сохраненное в нем – именно то, что и ожидалось. Это достигается при помощи следующего скрипта на Lua:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

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

Какова должна быть эта случайная строка? Полагаю, это должно быть 20 байт из /dev/urandom, но можно найти и менее затратные способы сделать строку достаточно уникальной для тех целей, что перед вами стоят. Например, будет нормально посеять RC4 с /dev/urandom, а потом сгенерировать на его основе псевдослучайный поток. Более простое решение связано с комбинацией времени unix в микросекундном разрешении плюс ID клиента; оно не столь безопасно, но, пожалуй, соответствует уровню задач в большинстве контекстов.

Время, которое мы используем в качестве показателя времени жизни ключа, называется «время действия блокировки». Это значение – одновременно срок, по истечении которого блокировка автоматически высвободится, и время, которое есть у клиента на выполнение операции прежде, чем другой клиент сможет, в свою очередь, заблокировать этот ресурс, без фактического нарушения гарантий взаимоисключения. Такая гарантия ограничена лишь определенным окном времени, которое начинается с момента приобретения блокировки.

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

Алгоритм Redlock

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

Чтобы приобрести блокировку, клиент выполняет следующие операции:

1. Получает текущее время в миллисекундах.
2. Последовательно пытается получить блокировку на все N инстансов, используя во всех случаях одно и то же имя ключа и случайные значения. На этапе 2, устанавливая блокировку для каждого инстанса, клиент, чтобы получить ее, использует задержку, которая достаточно коротка по сравнению с тем временем, по истечении которого блокировка автоматически снимается. Например, если длительность блокировки составляет 10 секунд, то задержка может быть в диапазоне ~ 5-50 миллисекунд. Таким образом исключается ситуация, в которой клиент мог бы долго оставаться заблокирован, пытаясь достучаться до отказавшего узла Redis: если инстанс недоступен, то мы как можно скорее пытаемся соединиться с другим инстансом.
3. Чтобы взять блокировку, клиент вычисляет, сколько времени истекло; для этого он вычитает из актуального значения времени ту метку времени, которая была получена в шаге 1. Тогда и только тогда, когда клиент смог получить блокировку на большинстве инстансов (как минимум 3), и общее время, понадобившееся на то, чтобы получить блокировку, меньше времени действия блокировки, считается, что получение блокировки состоялось.
4. Если блокировка была получена, то за срок ее действия принимается исходное значение длительности блокировки минус истекшее время, вычисленное в шаге 3.
5. Если клиенту по какой-то причине не удалось получить блокировку (либо он не смог заблокировать N/2+1 инстансов, либо время действия блокировки оказалось отрицательным), то он попытается разблокировать все инстансы (даже те, что, как считалось, он не мог заблокировать).

Является ли алгоритм асинхронным?

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

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

Подробнее о подобных системах, требующих согласования разбежки по времени, рассказывает следующая интересная статья: Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

Повторная попытка при отказе

Когда клиенту не удалось получить блокировку, он должен попытаться снова это сделать, выдержав случайную задержку; это делается с целью рассинхронизировать множество клиентов, одновременно пытающихся приобрести блокировку одного и того же ресурса (что может привести к ситуации «разделенного мозга», в которой победителей не бывает). Кроме того, чем быстрее клиент пытается приобрести блокировку большинства инстансов Redis, тем уже окно, в которое может возникнуть ситуация разделенного мозга (и тем меньше необходимость в повторных попытках). Поэтому в идеале клиент должен попытаться одновременно послать команды SET к N инстансов при помощи мультиплексирования.

Здесь стоит подчеркнуть, насколько важно, чтобы клиенты, которые не смогли приобрести большинство блокировок, высвободили (частично) приобретенные блокировки, чтобы не приходилось ждать истечения срока действия ключа, прежде, чем блокировка над ресурсом снова сможет быть приобретена (правда, если случается фрагментация сети, и клиент теряет связь с инстансами Redis, то приходится заплатить штраф за нарушение доступности, пока ожидается истечение срока действия ключа).

Высвобождение блокировки

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

Соображения по поводу безопасности

Безопасен ли алгоритм? Давайте попробуем представить, что происходит в различных сценариях.

Для начала давайте предположим, что клиент смог получить блокировку над большинством инстансов. Каждый из инстансов будет содержать ключ с одним и тем же временем жизни у всех. Однако, каждый из этих ключей устанавливался в свой момент, поэтому и срок действия у них истечет в разное время. Но, если первый ключ был установлен в момент не хуже T1 (время, которое мы выбираем перед контактом с первым сервером), а последний ключ был установлен в момент не хуже T2 (время, в которое был получен отклик от последнего сервера), то мы уверены, что первый ключ во множестве, у которого истечет срок действия, просуществует как минимум MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT. Все остальные ключи истекут позже, поэтому мы можем быть уверены, что все ключи будут одновременно действительны в течение как минимум этого времени.

В течение времени, когда большинство ключей остаются действительны, другой клиент не сможет приобрести блокировку, так как N/2+1 SET NX операций не могут закончиться успехом, если уже существует N/2+1 ключей. Поэтому, если блокировка была приобретена, то повторно приобрести ее в тот же момент невозможно (это нарушало бы свойство взаимного исключения).
Правда, мы хотим убедиться, что множество клиентов, одновременно пытающихся приобрести блокировку, не смогут одновременно в этом преуспеть.

Если клиент заблокировал большинство инстансов, затратив на это время около или более, чем максимальное время длительности блокировки, то сочтет блокировку недействительной и разблокирует инстансы. Поэтому нам приходится учесть лишь тот случай, в котором клиенту удалось заблокировать большинство инстансов за время, меньшее, чем срок действия. В данном случае, что касается вышеизложенного аргумента, за время MIN_VALIDITY ни один клиент не должен быть в состоянии повторно получить блокировку. Поэтому множество клиентов смогут заблокировать N/2+1 экземпляров за одно и то же время (которое заканчивается в момент завершения этапа 2), только когда время для блокировки большинства было больше, чем время TTL, что превращает блокировку в недействительную.

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

Соображения по поводу доступности

Доступность системы зависит от трех основных характеристик:

1. Автоматическое снятие блокировки (поскольку срок действия ключей истекает): в конечном итоге ключи будут доступны снова, чтобы использоваться для блокировок.
2. Тот факт, что клиенты обычно помогают друг другу, удаляя блокировки, когда нужная блокировка не была приобретена, либо была приобретена, а работа завершилась; поэтому вполне вероятно, что нам не придется дожидаться истечения ключей, чтобы повторно приобрести блокировку.
3. Тот факт, что, когда клиенту необходимо повторно попытаться получить блокировку, он выжидает в течение сравнительно дольшего времени, чем период, требующийся для приобретения большинства блокировок. Так снижается вероятность возникновения ситуации разделенного мозга при конкуренции за ресурсы.

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

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

Производительность, восстановление после отказа и fsync

Многие используют Redis, поскольку требуется обеспечить высокую производительность сервера блокировок, на уровне задержек, необходимых для приобретения и высвобождения блокировок, а также количества операций такого приобретения/высвобождения, которые удается выполнить в секунду. Для соответствия этому требованию существует стратегия коммуникации с N серверов Redis, чтобы снизить задержку. Это стратегия мультиплексирования (или же «мультиплексирование бедняка», при котором сокет ставится в неблокирующий режим, отправляет все команды, а считывает команды позднее, предполагая, что время оборота между клиентом и каждым из инстансов является схожим).

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

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

Если включить опережающее сохранение данных (AOF), ситуация немного улучшится. Например, можно повысить сервер, отправив команду SHUTDOWN и перезапустив его. Поскольку операции истечения в Redis семантически реализованы таким образом, что время продолжает течь, также когда сервер выключен, со всеми нашими требованиями все нормально. Нормально до тех пор, пока обеспечивается штатное отключение. А что делать при перебоях с питанием? Если Redis сконфигурирован по умолчанию, с синхронизацией fsync на диске каждую секунду, то возможно, что после перезапуска мы не досчитаемся нашего ключа. Теоретически, если мы хотим гарантировать безопасность блокировок при любом перезапуске инстанса, то должны включить fsync=always в настройках долговременного сохранения данных. Это полностью убьет производительность, до уровня таких CP-систем, которые традиционно применяются для безопасной реализации распределенных блокировок.

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

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

Используя отложенные перезапуски, в принципе возможно достичь безопасности и при отсутствии какой-либо долговременной сохраняемости в Redis. Отметим, правда, что это может вылиться в штраф за нарушение доступности. Например, при отказе большинства инстансов, система станет глобально недоступна на время TTL (и ни один ресурс заблокировать в это время будет нельзя).

Повышаем доступность алгоритма: продлеваем блокировку

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

Клиент должен считать блокировку повторно приобретенной лишь в случае, когда ему удалось заблокировать большинство инстансов в течение времени действия.

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