Алгоритм выбора лидера в распределенных системах

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

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

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

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

Существует много способов выбрать лидера: алгоритмы типа Paxos, программное обеспечение типа Apache ZooKeeper, настройка программного обеспечения, а также аренды. Аренды – это самый распространенный механизм выбора лидера в Amazon. Аренды относительно просты для понимания и реализации, а также предлагают встроенную отказоустойчивость. Аренды работают за счет единой базы данных, где расположен действующий лидер. По условиям аренды лидер посылает периодический тактовый импульс, демонстрируя что он продолжает быть лидером. В случае если текущий лидер некоторое время не посылает тактовый импульс, другой кандидат попробует занять его место.

В распределенных системах мы стараемся не зависеть от времени, даже при наличии в веб-сервисе Amazon Elastic Compute Cloud (Amazon EC2) такой возможности как отличная синхронизация времени. Сложно обеспечить достаточную синхронизацию счетчиков в кластере, чтобы полагаться на нее для выполнения распределенных операций заказа или координации. В Amazon время в распределенных системах указывается только для удобства потребителей. Аренды зависят от времени. В данном случае имеется в виду только локально затраченное время – продолжительность, а не время на часах, которое синхронизировано и требует согласования многочисленных серверов.

Исходный код библиотеки DynamoDB Lock Client содержит примеры и дополнительные сведения, связанные с выбором лидера. Однако, как выяснилось, несмотря на кажущуюся простоту использования аренды и блокировок с точки зрения теории, на практике корректная реализация требует мастерства. Необходимо понимать как сервер определяет локальную продолжительность времени. Например, если в какой-то момент сервер или библиотека, определяющие время, решат, что время перескочило назад, это сломает предположения о продолжительности времени, встроенные в аренды. На продолжительности не влияют проблемы синхронизации глобального счетчика, из-за которой серверы перестают согласовывать текущие время: от провала в несколько секунд до смещения локального счетчика во времени из-за устойчиво высокой нагрузки процессора.

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

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

Шаблон выбора лидера часто развертывается в системах Amazon. Ниже приведены соответствующие примеры.

• Почти все системы, использующие системы управления реляционными базами данных (RDBMS), полагаются на алгоритм выбора лидера, чтобы избрать лидера среди баз данных для обработки всех операций записи, а иногда и считывания. В таких системах процесс выбора может быть автоматизированным, хотя он часто выполняется оператором вручную.
• Amazon EBS распределяет операции чтения и записи для тома на множестве серверов хранения. Для обеспечения согласованности сервис использует выбор лидера, чтобы определить основные узлы для каждой области тома, которые задают порядок операций чтения и записи. В случае отказа основного узла версии follower берут на себя задачи лидера, используя тот же механизм выбора лидера. В сервисе Amazon EBS возможность выбора лидера обеспечивает согласованность и одновременно улучшает производительность, при этом удается избежать координации в плоскости передачи данных. По той же причине DynamoDB, Amazon Quantum Ledger Database (Amazon QLDB), а также Amazon Kinesis (Kinesis) используют аналогичные подходы.
• Библиотека Kinesis Client Library (KCL) использует механизм аренды, чтобы обеспечить обработку каждого сегмента Kinesis одним владельцем. Таким образом легче проводить расширенную обработку потоков Kinesis.

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

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

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

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

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

• Регулярно проверяйте оставшееся время аренды (или статус блокировки в общем), особенно перед началом любой операции с возможными побочными эффектами, выходящими за рамки лидера.
• Учитывайте, что медленные сетевые подключения, перерывы в работе, повторные попытки, а также паузы для сбора мусора могут привести к тому, что срок аренды истечет раньше, чем предусмотрено в коде.
• Избегайте отправки тактовых импульсов арендам в фоновом потоке. Могут возникать проблемы с правильностью кода, если поток не может прервать код, когда истечет срок аренды или умрет поток с тактовым импульсом. Проблемы с доступностью могут возникать, когда рабочий поток умирает или останавливается, а поток с тактовым импульсом привязан к аренде.
• Пользуйтесь надежными метриками, показывающими, какой объем работы может выполнить лидер по сравнению с текущим объемом. Чаще проверяйте эти метрики и заранее предусмотрите планы по масштабированию, не дожидаясь, пока иссякнут ресурсы.
• Упростите поиск узла, который является лидером в данный момент, и узла, который был лидером в любой заданный момент времени. Ведите журнал аудита изменений лидера.
• Моделируйте и формально проверяйте правильность распределенных алгоритмов с помощью таких инструментов, как TLA+. Это средство улавливает скрытые малозаметные и редкие ошибки, которые могут попасть в код, когда приложение слишком полагается на гарантии протокола выбора лидера.

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

Системы Amazon часто пользуются алгоритмом выбора лидера, чтобы обеспечить наличие встроенной отказоустойчивости. Когда системы используют выбор лидера, чтобы убедиться, что хотя бы один сервер обрабатывает задачу, они используют отдельные механизмы для поддержания правильности из-за наличия множества параллельных лидеров. Например, системы используют основную базу данных, чтобы отслеживать и предотвращать вмешательство лидеров в работу друг друга, когда два из них считают, что аренда у них. Уделяя меньше внимания предположениям о гарантиях, которые предоставляет реализация аренды, мы заботимся о правильности работы этих систем, часто моделируя ситуации с помощью таких технологий, как TLA+.

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

Ознакомьтесь с более детальными сведениями о работе аренды:

• Как сделать распределенную блокировку
• Burrows, The Chubby lock service for loosely-coupled distributed systems
• Gray and Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency