Эх, ухнем! Распределенные вычисления вчера и сегодня

• Блог компании Intel ,
• Высокая производительность

Принцип параллельного проведения расчетов – один из тех, что буквально «витают в воздухе». И это естественно, ведь любую работу удобней выполнять сообща. Параллельные вычисления появились задолго до первой ЭВМ, однако идея расцвела именно в компьютерную эпоху, ведь именно тогда появились и задачи, требующие большой вычислительной мощности, и устройства, готовые «всем миром» эту мощность предоставить. В эти дни исполняется ровно 15 лет с моего первого знакомства с проектами распределенных вычислений – хороший повод, чтобы написать об их истории и сегодняшнем дне.

Краткое теоретическое предисловие

• Раздача «сырых» кусочков клиентам и прием от них результатов обработки;
• Контроль потерянных и неверно посчитанных фрагментов;
• Интерпретация полученных кусочков в свете общей цели;
• Подсчет и визуализация статистики.

Эпоха distributed.net

Интерфейс клиента distributed.net почти не изменился за время существования проекта

После завершения 64-битной фазы интерес к проекту стал угасать, прежде всего потому, что следующая, 72-битная, обещала быть очень долгой. Предчувствия нас не обманули: она продолжается уже более 10 лет, за это время проверено лишь чуть более 2,5% пространства ключей. Скорее всего, до 80-битного ключа дело уже не дойдет, хотя вычислительная мощность компьютеров за время проекта и возросла многократно. Что ни говори, а предполагаемая продолжительность этапа в 400 лет определенно пугает.

Считаем линейки и ищем инопланетян

Клиент BOINC выгодно отличается от всех прочих наличием дизайна

Важным событием в жизни «распределенного» сообщества стало появление в 2005 году платформы BOINC (Berkeley Open Infrastructure for Network Computing) производства краснознаменного Калифорнийского университета в Беркли, как у них водится – с открытым исходным кодом. BOINC представляет собой готовую обвязку (типовые серверные компоненты + клиент) для проектов по сетевым вычислениям, которая значительно облегчает их запуск, хотя и не избавляет полностью от умственного труда, поскольку ряд серверных модулей необходимо готовить под конкретную задачу. Зато клиент, можно сказать, готов почти полностью, отлаженный и красивый. Более того, он позволяет участвовать сразу в нескольких BOINC-совместимых проектах. Получается эдакая связка разнородных, но объединенных технологически задач, что идет на пользу и самим задачам, и идеологии в целом.

Закончить хотелось бы опять на лирической ноте. Возможно, распределенные вычисления – это не самый оптимальный способ потратить имеющиеся у вас процессорные мощности. Но, если подумать, другие способы ведь еще менее оптимальны? Зато почувствовать себя членом команды – более легкого пути, пожалуй, нет. Моя «карьера» в этой области закончилась в 2004 – почти 9 лет назад. И вот сюрприз: сейчас, когда писал этот пост, зашел в статистику своей команды – представляете, она до сих пор жива и по-прежнему занимает первое место в нашем регионе. Не перевелись еще на Руси увлеченные люди!
Я приглашаю всех, кто когда-либо участвовал в проектах по распределенным вычислениям, откликнуться и дополнить мой рассказ – может быть, я чего-то пропустил?

Теги:

• распределённые вычисления
• distributed.net

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

Благодаря совместным усилиям обычных пользователей удалось сделать множество значимых открытий. Только за последние три года они отыскали 53 пульсара, причём последние семь нашлись совсем недавно – в конце августа 2012 г. Результаты выполненных исследований используются при разработке лекарственных препаратов для лечения сахарного диабета второго типа, болезней Альцгеймера и Паркинсона, других тяжёлых заболеваний. По материалам выполненных работ опубликованы сотни научных статей.

Суперкомпьютеры и распределённые сети

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

Распределенные вычисления

Часть 1. Высокопроизводительные вычисления в каждый дом

Серия контента:

1. Введение

Что делает ваш компьютер, когда ничего не делает? Пользователи одной из альтернативных операционных систем знают, что самый прожорливый процесс – это «System Idle»: как правило, он «съедает» около 90% ресурсов процессора. А чем занят ваш компьютер?

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

Как же можно с пользой потратить время «безделья» компьютера? Ответу на этот вопрос и посвящена статья. Я расскажу вам, как можно заставить свою машину работать на благо человечества. В следующей статье речь пойдет о том, как создать собственный сервер распределенных вычислений.

2. Загадочная «решетка»

Речь пойдет об одной из форм распределенных вычислений (в международной терминологии такие вычисления называют GRID – решетка) – Volunteer Computing. Сначала поясним термины.

GRID – это объединение нескольких компьютеров для решения единой вычислительно сложной задачи, разбитой на подзадачи. Каждый компьютер решает несколько подзадач, а результаты отдельных вычислений объединяются. Основное преимущество GRID в том, что она может состоять из компьютеров, находящихся друг от друга на тысячи километров и имеющих различные характеристики (как аппаратные, так и программные). Задачу объединения этих разнородных компьютеров выполняет промежуточное программное обеспечение, которое (виртуально) связывает все компьютеры через Интернет в единый суперкомпьютер. Идея GRID возникла в 1990-х годах, когда с развитием средств компьютерных коммуникаций объединение географически удаленных друг от друга компьютеров стало более дешевым, простым и потенциально более мощным средством повышения производительности, чем наращивание мощности одного-единственного суперкомпьютера.

Существуют различные виды GRID. Volunteer Computing – это форма реализации GRID-вычислений, специфика которой заключается в использовании времени простоя компьютеров обычных пользователей по всему миру. На текущий момент самым крупным проектом Volunteer Computing как по числу участников, так и по суммарной мощности является Folding@home – проект по проведению компьютерной симуляции свертывания молекул белка, запущенный в октябре 2000 года учеными из Стэнфордского университета. Однако речь в этой статье пойдет не о Folding@home, а о втором по величине проекте – системе BOINC. Причина проста – в отличие от специализированного Folding@home, проект BOINC предоставляет возможность участия в самых разнообразных научных проектах, начиная от взлома криптографических систем и заканчивая поиском внеземных цивилизаций!

3. BOINC

Производительность

По состоянию на момент написания статьи, BOINC насчитывает 340 тысяч активных компьютеров, а суммарная производительность компьютеров участников проекта составляет 1,9 Петафлопа. Это почти в 2 раза превышает производительность мощнейшего современного суперкомпьютера IBM Roadrunner. Статистику проекта BOINC можно увидеть на официальной странице http://boinc.berkeley.edu/

Для организации распределенных вычислений (GRID-вычислений) необходима соответствующая программная платформа. Система должна уметь разбивать одну большую задачу на множество маленьких подзадач, распределять эти подзадачи по вычислительным узлам, принимать результаты вычислений и объединять их в единое целое. Для этого были созданы различные программные «прослойки» между управляющим сервером и вычислительными узлами. Одной из таких программных «прослоек» является BOINC.

3.1. Что такое BOINC

SETI@HOME

SETI@HOME – это некоммерческий проект по поиску внеземного разума с помощью анализа радиосигналов с радиотелескопа Аресибо.

SETI (Search for Extra Terrestrial Intelligence, Поиск ВнеЗемного Разума) – это направление исследований, направленное на обнаружение разумной жизни за пределами Земли. Основной метод – исследование радиосигналов, которыми пронизан космос. Ученые пытаются найти радиосигналы, источники которых не могут быть природными.

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

Предыдущие проекты SETI использовали специализированные суперкомпьютеры, выполнявшие основной объем анализа данных. В 1995 году Дэвид Андерсон (David Anderson) запустил проект по обработке данных SETI на виртуальном суперкомпьютере, состоящем из множества компьютеров, подключенных к сети Интернет, и организовал проект SETI@home (SETI на дому) для апробирования этой идеи. Проект SETI@home был запущен в мае 1999 года, а в 2005 году полностью перешел на платформу BOINC.

Выступление Дэвида Андерсона, посвященное SETI@HOME, распределенным вычислениям и BOINC, можно найти на YouTube: http://www.youtube.com/watch?v=8iSRLIK-x6A (EN).

BOINC (Berkeley Open Infrastructure for Network Computing – открытая платформа Университета Беркли для сетевых вычислений) – это свободная (распространяется под лицензией GNU LGPL) программная платформа для проведения распределенных вычислений (если точнее, то Volunteer Computing). Система BOINC была разработана в Калифорнийском университете в Беркли под руководством Дэвида Андерсона (David Anderson) командой, создавшей легендарный проект SETI@home. Основным мотивом разработки системы послужила нехватка свободных вычислительных мощностей для обработки данных, поступающих от радиотелескопов. Именно поэтому разработчики решили привлечь вычислительные ресурсы и объединить сообщества нескольких научных проектов. Для решения этой масштабной задачи и была создана программная платформа BOINC.

Система BOINC состоит из программы-клиента, общей для всех BOINC-проектов, составного сервера (термин «составной сервер» означает, что физически сервер может состоять из нескольких отдельных компьютеров) и программного обеспечения. Для выполнения распределенных вычислений используется архитектура клиент-сервер.

Пользователи, передающие вычислительные мощности BOINC-проектам типа SETI@home, «зарабатывают» кредиты, начисляемые за выполнение отдельных подзадач. Эти кредиты нужны только для создания духа соревновательности среди участников проекта – пользователи, имеющие наибольшее число кредитов, имеют шанс «засветиться» на главной странице проекта.

3.2. Установка

Установка программы-клиента BOINC в Linux проста до невозможности – пользуясь любимым пакетным менеджером, установите из репозитариев пакеты boinc-client, boinc-manager и boinc-gui. Если вы предпочитаете пользоваться новейшим программным обеспечением или если ваш дистрибутив Linux не имеет пакетного менеджера/репозитариев (а такие еще остались?), то получить установочный пакет свежей версии программы можно со страницы загрузки официального сайта проекта (ищите адрес сайта в разделе «Ссылки» под номером 1).

Вне зависимости от способа, которым вы установили программу-клиент, все основные файлы вы найдете в своем домашнем каталоге в подкаталоге BOINC – здесь находятся не только исполняемые файлы, но и файлы настроек, а также данные, необходимые для обсчета заданий. (Благодаря этому вы можете с легкостью «заставить работать» на один проект все компьютеры вашей корпоративной сети).

Для начала нужно запустить графический менеджер программы:

user: /home/user/run_manager

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

На следующем шаге нужно будет выбрать проект, к которому вы хотите присоединиться, затем ввести свой электронный адрес и придумать пароль, а потом, возможно, потребуется завершить регистрацию на сайте самого проекта. В частности, на сайте можно выбрать команду (например, «Russia Team ») или даже создать свою собственную (я создал команду «Linux users Team» на проекте Climateprediction.net, присоединяйтесь!). Команды, как и отдельные участники, тоже участвуют в неформальном соревновании «Собери больше кредитов!».

К сожалению, описаний проектов менеджер BOINC при регистрации не предоставляет, поэтому выбором придется озаботиться заранее, например, просмотрев списки проектов, представленные по адресам в разделе «Ссылки» (). Не все так гладко и с предлагаемыми менеджером проектами, например, Einstein@home требует значительных аппаратных ресурсов, а SHA-1 Collision Search Graz уже не предоставляет заданий для обработки...

3.3. Работаем на благо науки!

Сразу после регистрации в проекте, программа-клиент BOINC начнет загрузку данных, необходимых для выполнения заданий. Учтите, что в зависимости от проекта этот этап может занять довольно продолжительное время и повлиять на вашу статистику полученного Интернет-трафика. Проекту ClimatePrediction.net понадобилось загрузить более 100 MБ, прежде чем начать обсчитывать первое задание.

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

Помимо такого (упрощенного) вида окна программы-клиента BOINC, есть и более информативный расширенный вид – нажмите на кнопку Advanced View в правом нижем углу (см. рисунок 3).

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

На вкладке «Задания» выделите строчку с заданием – тогда станут активными кнопки на панели слева (как на рисунке 3). Нажмите кнопку «Показать графику», и вашему взору предстанет замечательная картинка – это та самая модель, которую обсчитывает ваш компьютер. Поиграв управляющими клавишами (см. подсказки слева: T – температурная карта, R – снег и дождь, P – давление, C – облачность, S – запуск/остановка вращения глобуса, G – показать/скрыть сетку, H – помощь), можно наблюдать что-то аналогичное показанному на рисунке 4.

Конечно, какую картинку вы увидите – это зависит от проекта. Ничто не мешает вам поискать для себя что-то более интересное.

Еще одно замечание практического плана. На рисунках 2 и 3 видно, что общее время, необходимое для расчета задания, превышает 200 часов. Конечно, не каждый (особенно домашний) компьютер имеет время непрерывной работы порядка 10 суток. Для того чтобы не потерять все результаты расчетов при выключении компьютера, BOINC устанавливает контрольные точки. Кнопка «Информация» на вкладке «Задания» покажет, в том числе, и информацию о времени последней контрольной точки – при выключении компьютера вы потеряете лишь порядка 15 минут работы процессора.

3.4. Настройка программы-клиента «под себя»

Пользователю дается большой контроль над программой-клиентом BOINC с помощью различных настроек. Некоторые из этих настроек специфичны для проекта, другие являются общими и влияют на работу программы в целом. В расширенном виде окна программы-клиента выберите пункт меню «Дополнительно» – «Настройки клиента». Здесь вы можете указать такие параметры использования компьютера, что работа программы-клиента BOINC будет практически незаметна! Вы можете ограничить объем используемых для распределенных вычислений ресурсов процессора. Кроме всего прочего, можно указать, будет ли программа-клиент запускать на обсчет задания в то время, когда пользователь активно использует компьютер, или работа над распределенным проектом начнется только после определенного времени простоя процессора.

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

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

Если вы до сих пор не определились, какому именно проекту отдать свободные силы своего компьютера, не переживайте! Вы можете участвовать сразу в нескольких проектах («Сервис» –«Добавить проект» в расширенном виде окна программы или кнопка «Add Project» – в упрощенном) – по умолчанию программа-клиент BOINC будет каждые 60 минут (этот параметр тоже можно изменить) переключаться между заданиями различных проектов.

3.5. Некоторые технические подробности

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

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

Однако в этой схеме для проекта распределенных вычислений спрятан ряд опасностей. Во-первых, программа-клиент, получившая задание, может по различным причинам никогда не выйти снова на связь с сервером. Например, если участник проекта, которому принадлежит программа-клиент, потерял интерес к проекту. Во-вторых, участники проекта (опять же по различным причинам) могут посылать неверные результаты. Это еще более опасно для проекта, чем просто отсутствие результата, так как одно-единственное неверно посчитанное задание может стать причиной полного фиаско проекта! И, в-третьих, участники проекта могут попытаться получить больше кредитов, чем они заработали. Конечно, так как заработанные кредиты используются только для статистики, эта опасность на первый взгляд не так уж страшна... Однако проблема лежит в психологии сохранения сообщества. Не такое уж большое число пользователей заинтересованы именно в помощи научному исследованию, большая часть пользователей будут раздражены «читерами» и, как следствие, разочарованы проектом, и перестанут уделять ему время.

Первую проблему система BOINC обходит просто – назначая конечный срок, к которому программа-клиент должна вернуть результат вычислений (например, на рисунке 3 видно, что конечный срок, к которому нужно вернуть результат задания – это 19 мая 2010 года).

Вторая проблема решается за счет передачи одного и того же задания нескольким пользователям (это называется избыточными вычислениями). Для каждого задания количество дублирующих друг друга исполнителей индивидуально, но значение по умолчанию платформы BOINC равняется пяти. Когда программа-клиент отчитывается о проведенных вычислениях, сервер сравнивает результаты, присланные разными участниками. Результат, принятый «кворумом» программ-клиентов, считается правильным, а неверные ответы отвергаются. Участники, вернувшие серверу неверные результаты, не получают кредитов. Число программ-клиентов, составляющее «кворум», также может быть указано для каждого задания в отдельности, а значение по умолчанию равняется трем. Кстати, именно из-за такой формы проверки результатов вы будете наблюдать задержки в подсчете заработанных кредитов.

Третью проблему BOINC решает так же, как и проблему неправильных ответов – выполняя избыточные вычисления. Если пользователь завышает значение кредитов, которые он должен получить, то он увеличивает также значение кредитов, которые получат честные пользователи. Это снижает ущерб от обмана.

3.6. Подведение итогов

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

Однако это далеко не все, что можно было бы рассказать о BOINC. Например, BOINC умеет использовать для вычислений GPU (Graphics Processing Unit) видеокарты NVIDIA. Вы можете создавать обложки («скины») для программы-клиента, запускать программу-клиента на разных компьютерах под одной учетной записью, управлять работой программы-клиента без графического интерфейса и даже найти свой украденный компьютер с помощью BOINC! Ну и, конечно же, любой человек может создать свой собственный проект распределенных вычислений на основе BOINC. Начните с этой страницы http://boinc.berkeley.edu/wiki/User_manual официального сайта, а в случае затруднений обратитесь на русскоязычный форум: http://boinc.ru/forum/ .

В следующей статье мы подробно остановимся на том, как создать свой собственный сервер BOINC. Кто знает, быть может, это послужит появлению новых отечественных проектов распределенных вычислений? А пока подождем, когда на полную мощность будет запущен российский проект DrugDiscovery@Home (смотрите адрес сайта в разделе «Ссылки» под номером 9), созданный и поддерживаемый интернациональной командой разработчиков и находящийся в стадии альфа-тестирования.

4. Заключение

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

Благодаря совместным усилиям обычных пользователей удалось сделать множество значимых открытий. Только за последние три года они отыскали 53 пульсара, причём последние семь нашлись совсем недавно – в конце августа 2012 г. Результаты выполненных исследований используются при разработке лекарственных препаратов для лечения сахарного диабета второго типа, болезней Альцгеймера и Паркинсона, других тяжёлых заболеваний. По материалам выполненных работ опубликованы сотни научных статей.

Суперкомпьютеры и распределённые сети

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

• Tutorial

Девять лет назад я начал «в свободное от основной работы время» преподавать компьютерные дисциплины в одном из университетов Санкт-Петербурга. И только сравнительно недавно к своему удивлению обнаружил, что в наших вузах практически отсутствуют курсы с фокусом на проблематику распределённых вычислений. И даже на Хабре эта тема не раскрыта в достаточной мере! Надо прямо сейчас исправлять ситуацию.

Этой теме я и хотел посвятить статью или даже серию статей. Но потом решил выложить своё учебное пособие по основам распределённых вычислений, вышедшее в свет в этом году (читай, небольшую книгу объемом 155 страниц). В итоге получился гибрид – статья со ссылкой на книгу. Книга распространяется бесплатно и доступна в электронном виде.

Вместо пролога. Приступив к тексту статьи, я в очередной раз задумался, а зачем программисту нужно знать теоретические основы распределённых вычислений. Этот вопрос я неоднократно слышал (и продолжаю слышать) от студентов и специалистов, уже работающих в области ИТ. Действительно, зачем, например, знать, что «множество событий распределённого вычисления упорядочено частично, а не линейно»? В чем, так сказать, каждодневная практическая польза этого фундаментального знания?

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

Давайте попробуем начать издалека. И чтобы было нагляднее – с медицины. Потому как, если речь заходит о врачебных ошибках, мозг начинает активно работать и генерировать сильное возмущение: ужас, ужас, могли человека угробить. Что они там, совсем что ли? Неужели не знают, чего делают?

Все мы совершенно естественным образом рассчитываем на то, что перед тем как начать какие-либо манипуляции с человеческим организмом врачи всё-таки изучают его внутреннее устройство и принципы работы. Мы абсолютно не согласны с утверждением, что хирургам гораздо важнее пройти практические курсы кройки и шитья вместо многолетней зубрежки теоретического материала о том, что у нас там внутри и зачем оно там. Так почему же программистам, занимающимся разработкой системы с сетевым взаимодействием (т.е. к настоящему моменту практически любой системы), не нужно знать «что там внутри и зачем оно там»? Почему ошибки в ИТ воспринимаются максимум с легкой иронией? Ну да, ну баг. А кто не пьет не делает багов?! Назови! Нет, я жду! Среди требований к программистам очень часто почему-то на передний план выходят практические навыки владения тем или иным языком программирования. Причем сильно на передний план, полностью затмевая собой требования к пониманию основных концепций, теоретических моделей, алгоритмов, в конце концов… Да и сами программисты, чего греха таить, с началом разговора «про никому не нужную теорию» вянут как цветы в пустыне… Чудеса, не правда ли…

Приведу небольшое высказывание Л. Лэмпорта на эту тему (чуть ниже я постарался перевести это высказывание на русский язык, не сильно отдаляясь от оригинала):

For quite a while, I"ve been disturbed by the emphasis on language in computer science. One result of that emphasis is programmers who are C++ experts but can"t write programs that do what they"re supposed to. The typical computer science response is that programmers need to use the right programming / specification / development language instead of / in addition to C++. The typical industrial response is to provide the programmer with better debugging tools, on the theory that we can obtain good programs by putting a monkey at a keyboard and automatically finding the errors in its code.
I believe that the best way to get better programs is to teach programmers how to think better. Thinking is not the ability to manipulate language; it"s the ability to manipulate concepts. Computer science should be about concepts, not languages.

Уже довольно длительное время меня беспокоит слишком большое внимание, уделяемое компьютерному языку в ИТ. В результате переизбытка такого внимания появляются программисты, которые являются экспертами в С++, но которые не в состоянии написать программы, делающие то, что от этих программ требуется. Типичная реакция представителей ИТ на эту проблему заключается в предложении программистам использовать другой более подходящий язык (программирования, спецификаций и т.п.) вместо / вдобавок к С++. В свою очередь характерный для индустрии разработки ПО выход из ситуации видится в предоставлении программистам более совершенных инструментов отладки, видимо, основываясь на предположении, что получить хорошие программы можно просто посадив мартышку за клавиатуру и затем отыскивая и исправляя ошибки в её коде.
Моё твердое убеждение в том, что для получения качественных программ необходимо учить программистов думать лучше. Умение думать – это не способность оперировать компьютерным языком; это способность оперировать концепциями. Изучение информационных технологий должно быть сфокусировано на изучении концепций, а не языков.

В действительности события происходят в следующей последовательности:

1. Первым отправляется сообщение от пользователя А.
2. Пользователь В получает его, читает и отправляет ответ.
3. Пользователь С получает оба сообщения от А и В и затем отправляет свой ответ, опирающийся на оба сообщения от А и В.

1. Сообщение от пользователя С с темой «Re:Re: Общее собрание».
2. Сообщение от пользователя А с темой «Общее собрание».
3. Сообщение от пользователя В с темой «Re: Общее собрание».

Ага, оказывается порядок поступления сообщений, наблюдаемый различными процессами, может быть различным даже для FIFO каналов! А что делать, если мы хотим, чтобы наблюдаемый порядок был везде одинаков (и при этом не хотим использовать синхронный обмен сообщениями)? К примеру, если мы пишем свой транспорт с соответствующими гарантиями. Или хотим построить отказоустойчивую службу (replicated state machine), где каждая реплика должна обрабатывать поступающие запросы в едином для всех реплик порядке, чтобы состояния реплик не различались? Вопрос…

Рассмотрим теперь еще одно выполнение распределённой системы, в которой процессы взаимодействуют только с помощью обмена сообщениями, и каждый процесс занимается включением / выключением фонаря с определенным светом. Пусть первый процесс управляет фонарем с красным светом, второй – с желтым, а третий – с зеленым. Такая вот светофорная система. На рисунке ниже включение процессом своего фонаря обозначено прямоугольником, а выключение – вертикальной линией; отправка и получение сообщения – стрелкой. Вопрос: могут ли процессы определить, какие фонари светили одновременно?

Так вот оказывается, что в данном выполнении асинхронной системы процессы никак не смогут определить был ли включен красный свет одновременно с желтым. Может быть да. А может и нет… Сие останется неизвестным. Но зато будет точно известно, что красный и зеленый фонари одновременно находились во включенном состоянии. Другими словами, оказывается, нет особого смысла говорить о том, что то или иное глобальное состояние достигается по ходу выполнения распределённой системы! Равно как и очень часто нельзя сказать, выполнялось ли какое-либо условие (предикат), заданное на множестве его глобальных состояний! Опять же вопрос: почему?

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

Из этой книги вы узнаете:

• про причинно-следственный порядок событий распределённого вычисления
• что такое справедливость, безопасность и живучесть
• что такое конус прошлого и конус будущего для события вычисления
• чем логический параллелизм отличается от физического параллелизма
• почему не имеет особого смысла говорить о совокупности глобальных состояний вычисления, а имеет смысл говорить о совокупности событий вычисления
• как нам упорядочить события распределённого вычисления в одну или несколько последовательностей, которые «могли бы» происходить в системе
• что такое логические часы, и какое такое логическое время они отсчитывают
• почему логическое время останавливается, если в системе ничего не происходит
• чем скалярное время отличается от векторного
• как и для чего можно использовать логическое время в распределённых алгоритмах
• какие есть подходы к эффективной реализации векторных часов
• зачем нам может понадобиться матричное время
• чем распределённый алгоритм отличается от централизованного
• как решать задачу взаимного исключения без использования разделяемых переменных
• на какие категории делятся все распределённые алгоритмы взаимного исключения
• зачем в алгоритмах на основе получения разрешений используется логическое время
• почему философам так трудно пообедать в распределённой системе
• зачем нам граф конфликтов и граф предшествования
• почему граф предшествования должен меняться со временем
• почему в алгоритмах на основе передачи маркера есть еще много чего кроме собственно «передачи маркера»
• и, я надеюсь, ещё кое-что…

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

Первый раздел по большей части болтологический и посвящен «качественным» особенностям распределённых систем. Если вы не знаете, что такое распределённая система, и какие к ней предъявляются требования, то первый раздел имеет смысл прочитать. Если же вы знаете, что поступающие процессу-получателю сообщения могут давать устаревшее представление о процессе-отправителе, точно так же, как и световое излучение, поступающее к нам от далекой звезды, дает представление о состоянии этой звезды в прошлом, то первые четыре пункта можно пропустить:) Отдельно стоит отметить п. 1.5 «Взаимодействие в распределённых системах», в котором я попытался привести несколько простых задач, демонстрирующих сложности, с которыми можно столкнуться при разработке распределённых систем. Эти задачи мы будем потом решать, вооружившись теоретическими знаниями, поэтому стоит с ними ознакомиться.

Во втором разделе представлена модель распределённого вычисления и основная теория, используемая при дальнейшем изложении. В определенном смысле этот раздел является ключевым. Однако надо быть готовым к работе с такими терминами как «множество / подмножество», «бинарное отношение», «отношение эквивалентности», «отношение порядка», «линейный / частичный порядок». В этом разделе вы встретите доказательства некоторых утверждений. Мне кажется, что их следует, как минимум, проглядеть (а лучше изучить) для более глубокого понимания существенных особенностей функционирования распределённых систем, выделяющих их среди систем других классов.

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

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

На кого ориентирована эта книга?

Материал книги следует рассматривать в качестве введения в проблематику распределённых вычислений. Она выросла из академической вузовской среды, и будет, безусловно, полезна, если вы только начинаете работать в этой области. Если же у вас уже есть определённый опыт в разработке распределённых систем и алгоритмов, возможно, вы найдете для себя что-то новое и поделитесь своим мнением в комментариях. Если же вы имеете многолетний опыт за плечами и являетесь экспертом в этой теме, надеюсь, что вы сможете дополнить меня своими мыслями и соображениями.

Чего бы мне хотелось?