Проблемы с облаком: синхронизация

  • 10 мин

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

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

Помимо взаимного исключения, механизмы синхронизации должны предоставлять распределенным программам и другие преимущества. Для начала: если одна задача пытается получить доступ к важному разделу, то в конечном счете она должна завершиться успешно. Если две задачи одновременно пытаются получить доступ к важному разделу, то только одна из них должна завершиться успехом. Однако не всегда все идет так, как ожидалось. Например, если задача $A$ по получению lock1 завершается успешно и в то же время задача $B$ по получению lock2 также завершается успешно, то если задача $A$ пытается получить lock2, а задача $B$ пытается получить lock1, возникнет то, что называется взаимоблокировкой. Недопущение таких тупиковых ситуаций является значительной проблемой при разработке распределенных программ, особенно при вертикальном увеличении масштаба количества задач, поэтому любой механизм взаимного исключения должен обеспечивать отсутствие взаимоблокировок.

Основываясь на примере задач $A$ и $B$, предположим, что у нас есть более широкий набор задач: $\lbrace A, B, C, \cdots, Z \rbrace$. Чтобы обеспечить взаимное исключение, задача $A$ может ожидать выполнения задачи $B$, если $B$ содержит блокировку, необходимую $A$. Взамен задача $B$ может ожидать выполнения задачи $C$, если $C$ содержит блокировку, необходимую задаче $B$. Последовательность ожидания может выполняться вплоть до задачи $Z$. В частности, задача $C$ может ожидать выполнения задачи $D$, а задача $D$ — выполнения задачи $E$, и так может продолжаться до задачи $Y$, которая также может ожидать выполнения задачи $Z$. Такая цепочка ожидания обычно называется транзитивным замыканием. Когда происходит транзитивное замыкание, говорят, что возникает циклическое ожидание. Обычно эта ситуация влечет за собой жесткие взаимоблокировки, которые могут привести к сбою всей распределенной программы или системы. И, наконец, следует отметить, что ожидание лежит в основе любого механизма взаимного исключения. Его не может запретить ни один продвинутый протокол взаимного исключения2. В обычных сценариях задача находится в режиме ожидания в течение ограниченного (разумного) времени. Но что делать, если задача, содержащая блокировку или токен, завершается сбоем? Здесь мы переходим еще к одной серьезной задаче для распределенных программ, а именно, к отказоустойчивости.

Знаете ли вы?

Взаимное исключение в распределенных системах можно разделить на два основных класса: на основе токенов и на основе разрешений.

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

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

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

Централизованные алгоритмы просты в реализации, устойчивы к зависаниям и являются непредвзятыми. Разрешения могут быть предоставлены в том порядке, в котором запрашиваются, и выданы на указанное выделенное время, что гарантирует, что каждая задача получит возможность выполнить запросы. Тем не менее работа централизованных алгоритмов связана с серьезными проблемами. Во-первых, координатор является единой точкой отказа (SPOF). То есть в случае сбоя координатора вся система выйдет из строя. Во-вторых, координатор может стать узким местом производительности, особенно при вертикальном увеличении масштаба количества узлов и пользователей.

Чтобы устранить эти два основных недостатка централизованных алгоритмов, децентрализованные алгоритмы предлагают разделение центрального координатора на несколько координаторов1. Впоследствии для того, чтобы задача получила разрешение (на запись), ей требуется большинство голосов от координаторов (см. урок 4 в этом модуле, где приводятся вводные сведения о механизмах голосования). Очевидно, что получение этих разрешений делает распределенную программу менее уязвимой для SPOF. Точнее, распределенная программа с децентрализованным и взаимоисключающим алгоритмом может допускать $K$ из $2K + 1$ сбоев координатора1. Кроме того, децентрализованные алгоритмы устраняют проблемы производительности, возникающие в централизованных алгоритмах. Децентрализованные алгоритмы более сложны в реализации и обслуживании, чем централизованные. Как правило, сложность реализации и обслуживания может затруднить масштабируемость, особенно при значительном увеличении числа управляющих сообщений.


Ссылки

  1. A. S. Tanenbaum and M. V. Steen (October 12, 2006). Distributed Systems: Principles and Paradigms Prentice Hall, Second Edition
  2. M. Herlihy and N. Shavit (March 14, 2008). The Art of Multiprocessor Programming Morgan Kaufmann, First Edition

Проверьте свои знания

1.

Возьмем следующую функцию:

transaction (Account source, Account destination, double amount)
{
  Acquire lock on source;
  Acquire lock on destination;
  withdraw(from, amount);
  deposit(to, amount);
  Release lock on destination;
  Release lock on source;
}

Предположим, что изначально на счетах А и Б лежит в общей сложности 100 долларов США, и следующие операции выполняются одновременно, поэтому обе операции одновременно получают блокировку на исходном счете (как указано в строке 3 в функции транзакции):

1 Transaction(A,B,50); and Transaction(B,A,10);

Каков будет результат?