Реализация общих регистров в асинхронных системах передачи сообщений
Ключевые слова и синонимы
Симуляция (Simulation); эмуляция (Emulation)
Постановка задачи
Распределенная система состоит из набора из [math]\displaystyle{ n }[/math] процессов, которые взаимодействуют друг с другом. Были хорошо изучены два способа межпроцессного взаимодействия. Системы с передачей сообщений моделируют компьютерные сети, в которых каждый процесс может посылать информацию по каналам сообщений другим процессам. В системах с общей памятью процессы общаются менее непосредственным образом, получая доступ к информации в структурах совместно используемых данных. Распределенные алгоритмы часто оказывается проще проектировать для систем с общей памятью из-за их сходства с архитектурами однопроцессных систем. Однако многие реальные распределенные системы строятся как системы с передачей сообщений. Таким образом, ключевой проблемой распределенных вычислений является реализация общей памяти в системах с передачей сообщений. Такие реализации также называют симуляциями или эмуляциями общей памяти.
Наиболее фундаментальным типом структуры совместно используемых данных для реализации является регистр (чтения-записи), который хранит значение, взятое из некоторой области [math]\displaystyle{ D }[/math]. Изначально ему присваивается значение из [math]\displaystyle{ D }[/math], а доступ к нему можно получить с помощью двух видов операций – чтения (read) и записи (write((v)), где [math]\displaystyle{ v \in D }[/math]. Регистр может быть либо однорайтерным, то есть записывать в него может только один процесс, либо мультирайтерным, то есть любой процесс может записывать в него. Аналогично, он может быть одноридерным или мультиридерным. Аттия и Уэлч [4] представили обзор способов построения мультиридерных и мультирайтерных регистров из однорайтерных и одноридерных.
Если операции чтения и записи выполняются по одной за раз, они производят следующие эффекты: операция [math]\displaystyle{ read }[/math] возвращает значение, хранящееся в регистре, вызывающему процессу, а операция [math]\displaystyle{ write(v) }[/math] изменяет значение, хранящееся в регистре, на [math]\displaystyle{ v }[/math] и возвращает подтверждение, указывающее на завершение операции. Когда множество процессов выполняет операции параллельно, существует несколько способов определить поведение регистра [14]. Однорайтерный регистр является регулярным, если при каждом чтении возвращается либо аргумент операции записи, завершившейся в последний раз перед началом чтения, либо аргумент некоторой операции записи, выполняющейся параллельно с операцией чтения. (Если не имеется операции записи, которая завершается до начала операции чтения, операция чтения может вернуть либо изначальное значение регистра, либо значение параллельной операции записи). Регистр является атомарным (см. Линеаризуемость), если каждая операция выполняется как бы мгновенно. Точнее говоря, для любого параллельного выполнения существует полный порядок операций, такой, что каждая операция чтение возвращает значение, записанное последней операцией записи, которая предшествует ему в порядке (или изначальное значение регистра, если таковой операции записи не было). Более того, этот полный порядок должен соответствовать временному порядку операций: если одна операция завершается раньше, чем начинается другая, то первая должна предшествовать второй в полном порядке. Атомарность является более жестким условием, чем регулярность, но можно реализовать атомарные регистры на основе регулярных с некоторым увеличением сложности [12].
В данной статье описывается задача реализации регистров в асинхронной системе с передачей сообщений, в которой процессы могут испытывать сбои типа аварийного завершения. Каждый процесс может отправить сообщение, содержащее конечную строку, любому другому процессу. Чтобы сделать описание алгоритмов более единообразным, часто предполагается, что процессы могут также посылать сообщения сами себе. Все сообщения в конечном итоге доставляются. В описанных ниже алгоритмах отправители ждут подтверждения [доставки] каждого сообщения перед отправкой следующего, поэтому нет необходимости предполагать, что каналы передачи сообщений работают по принципу «первый пришел – первый ушел». Система полностью асинхронна: нет никаких ограничений на время, необходимое для доставки сообщения получателю или для выполнения процессом шага локальных вычислений. Процесс, выходящий из строя путем отказа, прекращает выполнение своего кода, но другие процессы не могут отличить процесс, претерпевший аварийное завершение, от процесса, работающего очень медленно. (Также изучались отказы каналов передачи сообщений [3] и более злонамеренные виды отказов процессов [15]).
Реализация t-устойчивого регистра предоставляет программы для выполнения процессами для симуляции операций чтения и записи. Эти программы могут включать любые стандартные управляющие структуры и обращения к локальной памяти процесса, а также инструкции для отправки сообщения другому процессу и для чтения буфера процесса, в котором хранятся входящие сообщения. В реализации также должно быть указано, как инициализируются локальные переменные процессов, отражая любое начальное значение реализованного регистра. В случае однорайтерного регистра только один процесс может выполнять программу записи. Процесс может многократно вызывать программы чтения и записи, но он должен дождаться завершения одного вызова, прежде чем начинать следующий. При любом таком выполнении, когда аварийно завершаются не более [math]\displaystyle{ t }[/math] процессов, каждый из вызовов процессом программы чтения или записи должен в конце концов завершиться. Каждая операция чтения возвращает результат из множества [math]\displaystyle{ D }[/math], и эти результаты должны удовлетворять свойству регулярности или атомарности.
Релевантными мерами сложности алгоритмов являются количество сообщений, передаваемых по системе для выполнения операции, количество бит на сообщение и объем локальной памяти, требуемый каждому процессу. Одной из мер временной сложности является время, необходимое для выполнения операции, при оптимистичном предположении, что время доставки сообщений ограничено [math]\displaystyle{ \Delta }[/math], а локальные вычисления происходят мгновенно (хотя алгоритмы должны корректно работать и без этих предположений).
Основные результаты
Реализация регулярного регистра
Одной из основных идей для реализации общих регистров в системах с передачей сообщений является построение, реализующее регулярный однорайтерный и мультиридерный регистр. Оно было предложено Аттией, Бар-Ноем и Долевом [3] и более явно сформулировано Аттией в работе [2]. Операция [math]\displaystyle{ write(v) }[/math] посылает значение [math]\displaystyle{ v }[/math] всем процессам и ждет, пока большинство процессов ([math]\displaystyle{ \lfloor \frac{n}{2} + 1 \rfloor }[/math], включая сам записывающий процесс) не вернут подтверждение. Читающий процесс посылает запрос всем процессам на получение их последних значений. Получив ответы от большинства процессов, он выбирает из них самое последнее записанное значение. Если запись завершается до начала чтения, то хотя бы один процесс, ответивший читающему процессу, получил значение операции записи до того, как отправил свой ответ. Это происходит потому, что любые два множества, содержащие большинство процессов, должны пересекаться. Время, необходимое для выполнения операций, когда время доставки ограничено, составляет [math]\displaystyle{ 2 \Delta }[/math].
Этот алгоритм требует, чтобы читающий процесс определил, какое из полученных им значений является самым последним. Он делает это с помощью временных меток, прикрепленных к значениям. Если записывающий процесс использует в качестве временных меток возрастающие целые числа, то по мере выполнения алгоритма сообщения будут расти без ограничений. Использование схемы ограниченных временных меток, предложенной Израэли и Ли [13], приводит к следующей теореме.
Теорема 1 (Аттия [2]). Существует [math]\displaystyle{ \lceil \frac{n - 2}{2} \rceil }[/math]-устойчивая реализация регулярного однорайтерного мультиридерного регистра в системе с передачей сообщений из [math]\displaystyle{ n }[/math] процессов. Реализация использует [math]\displaystyle{ \Theta(n) }[/math] сообщений на операцию, [math]\displaystyle{ \Theta(n^3) }[/math] бит на сообщение. Записывающий процесс использует [math]\displaystyle{ \Theta(n^4) }[/math] бит локальной памяти, каждый читающий процесс – [math]\displaystyle{ \Theta(n^3) }[/math] бит.
Теорема 1 является оптимальной с точки зрения отказоустойчивости. Если [math]\displaystyle{ \lceil \frac{n}{2} \rceil }[/math] процессов могут завершиться аварийно, то сеть можно разбить на две половины величиной [math]\displaystyle{ \lfloor \frac{n}{2} \rfloor }[/math], с задержкой сообщений между двумя половинами на неопределенное время. Операция записи должна завершиться до того, как любое свидетельство о записи будет передано во вторую половину сети, не содержащую записывающий процесс, тогда операция чтения, выполняемая процессом в этой половине, не сможет вернуть актуальное значение. При [math]\displaystyle{ t \ge \lceil \frac{n}{2} \rceil }[/math] регистры могут быть реализованы в системе с передачей сообщений только в том случае, если в системе присутствует некоторая степень синхронности. Точный объем необходимой синхронности исследовали Дельпор-Галле и коллеги [6].
Результат теоремы 1 отличается от оптимального количества сообщений на операцию не более чем на константный коэффициент. Свидетельство о каждой операции записи должно быть передано по меньшей мере [math]\displaystyle{ \lceil \frac{n}{2} \rceil - 1 }[/math] процессам, что требует [math]\displaystyle{ \Omega(n) }[/math] сообщений; в противном случае это свидетельство может быть уничтожено в результате сбоя. Операция записи должна завершиться, даже если только [math]\displaystyle{ \lfloor \frac{n}{2} \rfloor + 1 }[/math] процессов (включая записывающий) получили информацию о записанном значении, поскольку остальные процессы могли претерпеть сбой. Таким образом, читающий процесс должен получить информацию по крайней мере от [math]\displaystyle{ \lceil \frac{n}{2} \rceil }[/math] процессов (включая себя), чтобы быть уверенным, что он «знает» о последней операции записи.
t-устойчивую реализацию, при [math]\displaystyle{ t \lt \lceil \frac{n}{2} \rceil }[/math], которая использует [math]\displaystyle{ \Theta(t) }[/math] сообщений на операцию, можно получить с помощью следующей адаптации. Множество из [math]\displaystyle{ 2t + 1 }[/math] процессов предварительно выбирается в качестве серверов хранения данных. Операции записи отправляют информацию серверам и ожидают [math]\displaystyle{ t + 1 }[/math] подтверждений. Операции чтения ожидают ответов от [math]\displaystyle{ t + 1 }[/math] серверов и выбирают тот из них, который имеет самую свежую временную метку.
Реализация атомарного регистра
Аттия, Бар-Ной и Долев [3] представили построение атомарного регистра, в котором операции записи передают возвращаемое ими значение всем процессам и ждут подтверждения от большинства. Это делается для того, чтобы операция чтения не возвращала более старое значение, чем предшествующая ей другая операция чтения. Применяя неограниченные целочисленные временные метки, этот алгоритм использует [math]\displaystyle{ \Theta(n) }[/math] сообщений на операцию. Время, необходимое для одной операции в условиях ограниченного времени доставки, составляет [math]\displaystyle{ 2 \Delta }[/math] для записи и [math]\displaystyle{ 4 \Delta }[/math] для чтения. Однако предложенная авторами техника ограничения временных меток увеличивает количество сообщений на операцию до [math]\displaystyle{ \Theta(n^2) }[/math] (и время на операцию до [math]\displaystyle{ 12 \Delta }[/math]). Более эффективная реализация атомарных регистров с ограниченным размером сообщений приведена в работе Аттии [2]. Она использует регулярные регистры из теоремы 1 для реализации атомарных регистров с помощью конструкции «рукопожатия» Халдара и Видьясанкара [12], что приводит к следующему результату.
Теорема 2 (Аттия [2]). Существует [math]\displaystyle{ \lceil \frac{n - 2}{2} \rceil }[/math]-устойчивая реализация атомарного однорайтерного мультиридерного регистра в системе с передачей сообщений из [math]\displaystyle{ n }[/math] процессов. Реализация использует [math]\displaystyle{ \Theta(n) }[/math] сообщений на операцию, [math]\displaystyle{ \Theta(n^3) }[/math] бит на сообщение. Записывающий процесс использует [math]\displaystyle{ \Theta(n^5) }[/math] бит локальной памяти, каждый читающий процесс – [math]\displaystyle{ \Theta(n^4) }[/math] бит.
Поскольку атомарные регистры регулярны, этот алгоритм является оптимальным с точки зрения отказоустойчивости и отличается от оптимального на константный коэффициент с точки зрения количества сообщений. Время выполнения одной операции в условиях ограниченного времени доставки составляет не более [math]\displaystyle{ 14 \Delta }[/math] для записи и [math]\displaystyle{ 18 \Delta }[/math] – для чтения.
Применение
Любой распределенный алгоритм, использующий общие регистры, может быть адаптирован для работы в системе с передачей сообщений с помощью описанных выше реализаций. Этот подход позволил получить новые или улучшенные решения по передаче сообщений для ряда задач, включая рандомизированный консенсус [1], мультирайтерные регистры [4] и объекты типа «моментальный снимок». Обратная симуляция также возможна, для чего можно использовать простую реализацию каналов передачи сообщений с помощью однорайтерных одноридерных регистров. Таким образом, две асинхронные модели эквивалентны с точки зрения набора задач, которые они могут решить, предполагая, что аварийно завершается только меньшая часть процессов. Однако использование симуляций сопряжено с определенным увеличением сложности.
Если алгоритм с общей памятью реализован в системе с передачей сообщений с помощью описанных здесь подходов, процессы должны продолжать работать даже при завершении алгоритма, чтобы помочь другим процессам выполнить свои операции чтения и записи. Этого нельзя избежать: если каждый процесс должен прекратить выполнение шагов, когда его алгоритм завершает работу, возникают некоторые проблемы, решаемые с помощью общих регистров и нерешаемые в модели передачи сообщений [5].
Использование большинства процессов для «подтверждения» каждой операции чтения и записи является примером системы кворума, первоначально представленной Гиффордом [10] для реплицированных данных. В общем случае система кворумов – это совокупность множеств процессов, называемых кворумами, такая, что каждые два кворума пересекаются. Системы кворумов также могут быть разработаны для реализации общих регистров в других моделях систем с передачей сообщений, включая динамические сети и системы со злонамеренными видами отказов. Примеры см. в работах [7, 9, 11, 15].
Открытые вопросы
Хотя описанные здесь алгоритмы оптимальны с точки зрения отказоустойчивости и сложности сообщений, неизвестно, является ли оптимальным количество бит, используемых в сообщениях, и локальной памяти. Точное время, требуемое для выполнения операций чтения и записи, когда сообщения доставляются за время [math]\displaystyle{ \Delta }[/math], также является предметом постоянного исследования. (См., например, [8]). Как упоминалось выше, симуляция общих регистров может быть использована для реализации алгоритмов с общей памятью в системах с передачей сообщений. Однако, поскольку симуляция влечет значительные накладные расходы, возможно, что некоторые из этих задач могут быть более эффективно решены с помощью алгоритмов, разработанных специально для систем с передачей сообщений.
См. также
Литература
1. Aspnes, J.: Randomized protocols for asynchronous consensus. Distrib.Comput. 16(2-3), 165-175 (2003)
2. Attiya, H.: Efficient and robust sharing of memory in message-passing systems. J. Algorithms 34(1), 109-127 (2000)
3. Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J.ACM 42(1), 124-142 (1995)
4. Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley-Interscience, Hoboken (2004)
5. Chor, B., Moscovici, L.: Solvability in asynchronous environments. In: Proc. 30th Symposium on Foundations of Computer Science, pp. 422-427 (1989)
6. Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Hadzilacos, V., Kouznetsov, P., Toueg, S.: The weakest failure detectors to solve certain fundamental problems in distributed computing. In: Proc. 23rd ACM Symposium on Principles of Distributed Computing, pp. 338-346. St. John's, Newfoundland, 25-28 July 2004
7. Dolev, S., Gilbert, S., Lynch, N.A., Shvartsman, A.A., Welch, J.L.: GeoQuorums: Implementing atomic memory in mobile ad hoc networks. Distrib. Comput. 18(2), 125-155 (2005)
8. Dutta, P., Guerraoui, R., Levy, R.R., Chakraborty, A.: How fast can a distributed atomic read be? In: Proc. 23rd ACM Symposium on Principles of Distributed Computing, pp. 236-245. St. John's, Newfoundland, 25-28 July 2004
9. Englert, B., Shvartsman, A.A.: Graceful quorum reconfiguration in a robust emulation of shared memory. In: Proc. 20th IEEE International Conference on Distributed Computing Systems, pp. 454^63. Taipei, 10-13 April 2000
10. Gifford, D.K.: Weighted voting for replicated data. In: Proc. 7th ACM Symposium on Operating Systems Principles, pp. 150-162. Pacific Grove, 10-12 December 1979
11. Gilbert, S., Lynch, N., Shvartsman,A.: Rambo II: rapidly reconfigurable atomic memory for dynamic networks. In: Proc. International Conference on Dependable Systems and Networks, pp. 259-268. San Francisco, 22-25 June 2003
12. Haldar, S., Vidyasankar, K.: Constructing 1-writer multireader multivalued atomic variables from regular variables. J. ACM 42(1),186-203(1995)
13. Israeli, A., Li, M.: Bounded time-stamps. Distrib. Comput. 6(4), 205-209(1993)
14. Lamport, L.: On interprocess communication, Part II: Algorithms. Distrib.Comput. 1(2), 86-101 (1986)
15. Malkhi, D., Reiter, M.: Byzantine quorum systems. Distrib. Comput. 11(4), 203-213 (1998)