medved

Мини-учебнег по распределенным системам/протоколам. Требования к распределенной системе

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

Я бы выделил три основных случая почему нам может понадобиться распределенная система: отказоустойчивость, производительность и распределенность в узком смысле. Под распределенностью в узком смысле, имеется в виду ситуация, когда нам по тем или иным соображениям надо разместить систему на разных устройствах в сети. Например, мы хотим обрабатывать клиентские запросы по стадиям/tiers: веп-сервер, апп-сервер, сервер БД. Это типовый паттерн организации распределенных вычислений, хотя, вообще говоря, группировка серваков/процессов по функциональности вовсе не есть обязательное условие. Но так может быть понятнее устройство, плюс требования к серверам у разных групп разные, плюс там настройки сети или там безопасность можно лучше регулировать (типа какие-нить серваки можно вынести в DMZ). Т.е. на практике это достаточно важное требование, что какие-то компоненты распределенной системы должны быть на физически разных компьютерах, и это не обязательно вызвано требованиями производительности и отказоустойчивы (хотя оно конечно может совмещаться). Поэтому я выделяю три вида требований, конечно же, они могут совмещаться. Рассмотрим их подробнее.
Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Модель распределенной системы

Перейдем все-таки к распределенным системам. Уточним сперва модель распределенной системы. Будем считать, что система состоит из набора нод/процессов, которые коммуницируют только передачей друг другу сообщений. Будем считать, что на каждой ноде работает ровно один процесс, т.е. будем игнорировать различие ноды и процесса(ов). Каждая нода может послать сообщение любой другой ноде (в том числе и себе). Также будем считать, что единственный источник недетерминизма в системе - это сеть. Т.е. результат обработки последовательности событий, определяется только последовательностью событий и исходным состоянием, и всегда одинаков. Т.е. можно восстановить систему после сбоя, восстановив консистентное состояние всех нод и подать на каждую ноду события в той же последовательности, что и до сбоя.

Недетерминизм же заключается в том, что сеть может доставлять сообщения в разном поряке от случая к случаю. Будем также считать, что содержимое сообщений не меняется. Также будем считать, что канал передачи сообщений между двумя нодами не теряет сообщений, не генерирует дубли и доставляет их в том, порядке, что их отправили (это несложно реализовать с помощью нумерации исходящих сообщений) - FIFO канал. При этом порядок доставки сообщений разным процессам (т.е. через разные peer-to-peer каналы) не определен.

Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Оптимизации компилятора и процессора

Итак у нас есть иерархия памяти: регистры процессора, несколько уровней кэшей, общая память одного компьютера - и, возможно, распределенная память в том или ином виде (условный memcached). Оно все нужно для оптимизации - доступ в локальную память сильно быстрее нежели уровнем ниже. Так что если мы будем все операции чтения и записи распространять по всей иерархии памяти, это будет очень медленно. Особенно в распределенном случае - другой компьютер может ведь и сдохнуть. А пока мы обнаружим что он слишком долго не отвечает... При этом основная часть кода все же однопоточная. Так что нужно обеспечить высокую производительность однопоточного кода, иначе теряется смысл во всей этой многопроцессорности и распределенности (впрочем это все равно актуально для отказоустойчивости).

Поэтому по умолчанию и компиляторы, и система исполнения да и процессор, полагают, что код исполняется в однопоточном режиме. Чтобы они считали по другому, им обычно нужно давать специальные указания. В однопоточном режиме же можно делать кучу всеразличных оптимизаций, которые нельзя делать в случае, когда другие потоки управления могут параллельно читать или писать в те участки памяти, которые читает и пишет программа. Соответственно, специальные указания процессору и компилятору позволяют сообщить, что те или иные участки памяти разделяются между процессорами, ну или те или иные куски программы лазают в память, в которую могут лазить другие потоки управления. Например, если мы захватили блокировку, то это одновременно неявное указание компилятору и процессору, что мы сейчас будем читать и писать разделяемые данные. Точно так же, освобождение блокировки - это "намек", что мы закончили работать с разделяемыми данными. Но могут быть и явные указания на разделяемые доступ к даннам - например volatile модификатор в Java.

Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Вычислительная модель

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

Начнем с программы и памяти. Программа - это набор инструкций. А память - хранилище данных, куда можно чего-то записать или прочитать. Инструкции программы манипулируют значениями в памяти. Но сама программа не есть активный компонент - она исполняется на физическом вычислительном устройстве (процессоре, ядре, виртуальном ядре в случае SMT), в некотором контексте, называемом поток управления.

Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Очереди и мониторы

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

Если захват блокировки реализован через spin-lock, т.е. поток в цикле пытается установить переменную через какой-нить testAndSet, то если таких потоков много, то пытающиеся захватить блокировку потоки будут постоянно и впустую жечь циклы. Посему более эффективно, с точки зрения расходования ресурсов, переводить те потоки, которым не удалось захватить блокировку в очередь, в состояние ожидания и помещать в специальную очередь, ожидающих момента, когда блокировка освободиться. А процессорное время можно выделить другим потокам. Когда же какой-то поток освободит блокировку, то scheduler возьмет какой-то поток из очереди, переведет в режим исполнения и выдаст ему блокировку. Таким образом, можно высвободить процессорные циклы и выдать их каким-то другим потокам (ну или хотя бы поберечь энергию).
Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Блокировки и мьютексы

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

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

Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Доступ к разделяемым данным

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

Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Проблема доступа к разделяемым данным

Основное различие программирования распределенных и многопоточных систем в том, что в распределенных системах есть частичные сбои. Посему сперва нужно рассмотреть проблематику программирования многопоточных систем. А в распределенных системах к ним добавиться проблемы восстановления после сбоев и маскирования отказов. Впрочем есть еще один важный момент, который важен в распределенных системах - высокие издержки на сетевую коммуникацию. Это сильно влияет на паттерны, которые используются в распределенных системах. Например, бывает проще переместить вычисление поближе к данным, нежели перемещать данные - принцип весьма актуальный для BigData. В общем, и целом, для распределенных систем важно помнить о том, когда происходит передача управления между разными нодами, и по возможности группировать такие операции. В то время как при объектно-ориентированном подходе часто код разбивают на кучу независимых операций, что конечно вносит некоторый оверхэд, но обычно не так фатально в плане производительности как в случае распределенных систем.

Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Кэширование

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

Collapse )
medved

Мини-учебнег по распределенным системам/протоколам. Репликация и масштабирование.

Отмечу, что репликация и избыточность могут использоваться не только для устранения SPOF'ов, но и для повышения производительности. Действительно, если мы удваиваем кол-во дивайсов, то хотелось бы их задействовать для обработки запросов. Что зачастую и делается. И поэтому вместо дорогих специализированых дивайсов типа там SAN'ов или специальных кластерных интерконнектов, бывает сподручнее поставить в два раза больше серваков, так можно и надежность увеличить и производительность обработки запросов.

Collapse )