Невозможно спроектировать распределённую систему, которая при разделении (partition) будет одновременно поддерживать целостность (consistency) и доступность (availability)

Зачем переходить к распределённой системе:

• Распределение нагрузки

• Увеличение производительности

• Отказоустойчивость

• Использование общего ресурса

• Обслуживание географически распределенных пользователей (replica placement)

При построении РС необходимо обеспечить:

• Прозрачность - способность системы скрывать свою распределённую природу

• Открытость – лёгкость подключения новых компонент

• Масштабируемость – способность системы адаптироваться к росту нагрузки,

расширению области покрытия и усложнению административной структуры

• Целостность данных – в идеале, клиенты, подключаясь к разным узлам системы, должны получать одну и те же информацию

Задержка (латентность)

Период между инициированием чего-либо и возникновением реакции.

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

В распределенной системе существует минимальная задержка, которую невозможно преодолеть:

скорость света ограничивает скорость распространения информации,

аппаратные компоненты имеют минимальные задержки на каждой операции

Пример: время пинга до разных стран (https://www.netmeter.eu/ping-test/)

• Копенгаген, Дания: 60 мс

• Дубай, ОАЭ: 170 мс

• Лос Анджелес, США: 203 мс

• Рио-Де-Жанейро, Бразилия: 240 мс

• Токио, Япония: 260 мс

• Сидней, Австралия: 335 мс

Рост количества узлов

• увеличение вероятности сбоя в системе (снижает доступность и увеличивает

административные расходы)

• увеличение потребности в обмене данными между узлами (снижение

производительности по мере увеличения масштаба)

• разные топологии – разное влияние увеличения количества узлов

�Топология «звезда»:

��

​

​

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

​

​

Топология «дерево»:

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

Время в распределённых системах

Время необходимо:

• установление очерёдности событий

• для выяснения причинно-следственных связей

При работе на кластере или в сети в рамках одного ЦОД можем использовать физические часы

для синхронизации. Но при работе с системами большого масштаба (система занимает несколько ЦОД, части системы могут находиться на разных континентах) пользоваться физическим временем нельзя.

Замедление/ускорение часов (clock drift) – приводит к расхождению часов (clock skew):

Варианты решения

• Атомные часы

• Часы GPS

• Периодическая синхронизация с внешним сервером времени

• Периодическая синхронизация между узлами РС (устанавливаем некое усреднённое

время на всех узлах) — алгоритм Беркли, алгоритм Кристиана и др.

Все эти методы имеют недостатки. Таким образом, считается, что в больших распределённых

системах нет глобальных физических часов.

Глобальная информация

Это информация о текущем состоянии системы.

Сколько узлов в настоящее время в системе? Где находится нужный нам узел? Где находятся

нужные нам данные?

В системах большого масштаба

• Отсутствие глобальной информации у узлов

• Принятие решений на основе локальной информации

Итак, в распределённой системе

• Нет глобальных часов

• Нет общей памяти

• Нет глобальной информации о состоянии системы у узлов

• Узлы должны принимать решения на основе локальной информации (информации

о состоянии других узлов, которая может быть устаревшей)

Для решения многих классических проблем (взаимное исключение, например) нужно искать

новые алгоритмические решения.

Взаимное исключение (mutual exclusion): несколько процессов хотят работать с одним и тем же

ресурсом (разделяемый ресурс); необходимо организовать такой режим работы с разделяемым

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

На локальной машине (в локальной ОС) эта задача решается с помощью семафоров (некоторая

общая переменная-счётчик). На основании значения семафора процесс входит или не входит в

критическую секцию (область программы, в которой осуществляется работа с разделяемым

ресурсом).

В случае РС у нас нет общих переменных, только посылка сообщений. Следовательно,

нужны новые алгоритмы. Возникает отдельная область – распределённые

алгоритмы (не путать с параллельными алгоритмами)

Расширение теоремы CAP - теорема PACELC (Абади): in the case of Partitioning, one must choose between

Availability and Consistency, Else (in the case of normal system operation) one must choose between

Latency and Consistency.