Эссе на тему:

«Распределенные вычисления и приложения»

Студент (ка) …. курса:

ФИО

Номер группы:…..

Проверил

Содержание

Введение. 3

Основная часть. 4

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

Список литературы. 33

Введение

На современном этапе роста темпов научно-технического прогресса все больше развиваются технологии Big Data, которые предусматривают использование распределенных вычислений и приложений. От выбора системы распределенных вычислений зависит не только возможность масштабирования приложений для хранения больших массивов данных, а их отказоустойчивость в процессе эксплуатации.

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

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

В настоящее время распределенные приложения основаны на работе распределенных файловых систем или DFS-систем, имеющих неограниченное количество дисков для хранения файлов с большими объемами данных, GFS-хранилищ для блочных устройств, KLV Storage хранилищ с фиксированным доступом к данным, распределенных очередях сообщений Massage Queries, сервисов координации и базах данных.

Внутри распределенного приложения производится обмен сообщениями по каналам связи между узлами node с применением модели согласованности, а во внешней среде для обработки RPC-вызовов применяется модель распределенной памяти.

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

На основании этого возникают вопросы, как организована работа распределенных приложений, которые получили популярность среди пользователей сети Интернет? Какие модели данных и алгоритмы синхронизации в этих приложениях?

Основная часть

Как организована работа распределенных приложений, которые получили популярность среди пользователей сети Интернет?

Компания Google использует распределенную файловую систему GFS, которая обеспечивает хранение и обработку больших массивов информации, технология MapReduce и распределенный механизм хеширования BigTable. К преимуществам распределенной файловой системы GFS относятся:

- высокая надежность Data-центров, поскольку один и тоже блок данных имеет три экземпляра на разных серверах;

- возможность масштабируемости узлов node;

- новые приложения могут использовать как существующие кластеры, так и новые, созданные специально для них;

- поддержка больших блоков данных;

- эффективное распределение операций между Data-центрами.

В состав распределенной файловой системы GFS входят master-сервера для хранения метаданных файлов. Для клиентов создана возможность выполнения операций с метаданными на master-серверах. Важную роль в распределенной файловой системе имеет API (Application Programming Interface), который использует распределенную файловую систему без корректировки кода, выполнения процедур экспорта и импорта данных.

Файлами распределенной файловой системы выступают виртуальные «блочные устройства. Архитектура распределенной файловой системы GFS приведена на рис.1.

Рис. 1. Архитектура распределенной файловой системы GFS

Распределенная файловая система GFS производит разделение потоков данных и потоков команд. При этом потоки команд проходят от GFS master к GFS client и от GFS master к GFS chunkserver[1].

В то время как потоки данных проходят от GFS chunkserver к GFS client напрямую, исключая GFS master, что позволяет увеличить способность к масштабируемости всего GFS кластера в целом.

В распределенной файловой системе GFS master-сервер в GFS является единичной точкой отказа. Для того чтобы максимально нивелировать влияние недоступности GFS master на общую доступность системы в GFS функционирует система log-операций и checkpoint (при достижении лога определенных объемов).

Недостатком распределенной файловой системы GFS является то, что она не позволяет реализовать географическую распределенность без существенных задержек времени. Для решения данной проблемы компанией Google была обновлена распределенная файловая система с выпуском multi cell-ориентированной архитектурой Colossus.

В системе Colossus пул master-серверов и пул chunk-серверов разделены на логические ячейки. В каждой ячейке содержится до 8 master-серверов, которые производят обслуживание одного и более ячеек chunk-серверов[2].

MapReduce является программной моделью и соответствующей реализацией обработки и генерации больших наборов данных. Пользователи могут задавать функцию, обрабатывающую пары ключ/значение для генерации промежуточных аналогичных пар, и сокращающую функцию, которая объединяет все промежуточные значения, соответствующие одному и тому же ключу. Многие реальные задачи могут быть выражены с помощью этой модели.

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

MapReduce использует три типа серверов:

- master server, который назначает задания остальным типам серверов, а также следит за процессом их выполнения;

- map server, который принимает входные данные от пользователей и обрабатывает их, результаты записываются в промежуточные файлы;

- Reduce server, который принимает промежуточные файлы от map-серверов.

Следующим примером использования распределенных вычислений и приложений выступает ресурс YouTube, который получил лидерство в сфере Интернет-видео. Ресурсом YouTube используются распределенные блокировки Zookeeper и BigTable для хранения изображений[3].

Программное обеспечение, используемое ресурсом Интернет-видео YouTube, отражено в таблице 1.

Таблица 1 – Программное обеспечение, используемое ресурсом Интернет-видео YouTube

BigTable – это распределенный механизм хэширования, который является крупномасштабной, устойчивой к потенциальным ошибкам, самоуправляемой системой, которая может включать в себя терабайты памяти и петабайты данных, а также управлять миллионами операций чтения и записи в секунду^[4].

BigTable предоставляет механизм просмотра данных для получения доступа к структурированным данным по имеющемуся ключу. С помощью контролирования своих низкоуровневых систем хранения данных, ресурс YouTube получает больше возможностей по управлению и модификации их системой. Каждый блок данных хранится в ячейке, доступ к которой может быть предоставлен как по ключу строки или столбца, так и по временной метке.

В BigTable тоже используется три типа серверов:

- master server, который распределяет таблицы по Tablet-серверам, а также следит за расположением таблиц и перераспределяет задания в случае необходимости;

- tablet server, который обрабатывают запросы чтения/записи для таблиц. Они разделяют таблицы, когда те превышают лимит размера (обычно 100-200 Мбайт);

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

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

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

Таблица 2 – Программное обеспечение, используемое социальной сетью Facebook

В основе модели данных HBase лежит концепция BigTable от компании Google, которая хорошо подходит для поиска строк по идентификаторам, фильтрации и сканированию наборов строк.

Среди недостатков следует отметить отсутствие поддержки сложных запросов, но этот недостаток компенсируется системой Apache Hive, которая выступает SQL-интерфейсом доступа к данным для платформы Apache Hadoop, разработанной Facebook для работы с большими массивами данных[5].

Архитектура системы Apache Hive отражена на рис. 2.

Рис. 2. Архитектура системы Apache Hive

Для данных в файловой системе HDFS используется схема доступа на чтение, позволяющая обращаться с данными, как с обыкновенной таблицей или реляционной СУБД. Запросы HiveQL транслируются в Java-код заданий MapReduce.

Архитектура HDFS содержит три части: NameNode, DataNode, клиент. NameNode используется для хранения, генерации файловых систем, а DataNode выполняет функции хранения фактических данных.

Процесс записи данных в распределенной файловой системе HDFS отражен на рис.3.

Рис.3. Процесс записи данных в распределенной файловой системе HDFS

Как видно из рис.3, на первоначальном этапе клиент HDFS Client создает файловый узел метаданных NameNode. Параллельно HDFS Client производит запись фактических данных через собственный протокол пакетов в DataNode. После того как запись данных завершена, информация для подтверждения направляется в HDFS Client, который вызывает сервисную функцию и закрывает процедуру записи файлов.

Процесс чтения данных в распределенной файловой системе HDFS отражен на рис.4.

Рис.4. Процесс чтения данных в распределенной файловой системе HDFS

Как видно из рис.4, на первоначальном этапе клиент HDFS Client открывает распределенную файловую систему Distributed FileSystem и получает доступ к NameNode. После этого HDFS Client производит чтение фактических данных через собственный протокол пакетов в DataNode. После того как чтение данных завершено, информация для подтверждения направляется в HDFS Client, который вызывает сервисную функцию и закрывает процедуру чтения файлов.

Таким образом, Facebook использует HBase, Hadoop и HDFS, не смотря на громоздкость системы, когда другие предпочитают Cassandra из-за её простой схемы масштабирования, поддержку нескольких дата-центров и легкость в использовании.

Какие модели данных в распределенных приложениях?

В распределенных приложениях компании Google используется модель распределенных вычислений MapReduce, и ее структура отражена на рис.5.

Рис.5. Структура модели распределенных вычислений MapReduce

В состав модели распределенных вычислений MapReduce входят следующие компоненты:

- map - предварительная обработка входных данных в виде список значений. При этом главный узел кластера (master node) получает этот список, делит его на части и передает рабочим узлам (worker node). Далее каждый рабочий узел применяет функцию map к локальным данным и записывает результат в формате «ключ-значение» во временное хранилище;

- shuffle, когда рабочие узлы перераспределяют данные на основе ключей, ранее созданных функцией map, таким образом, чтобы все данные одного ключа лежали на одном рабочем узле.

- reduce – параллельная обработка каждым рабочим узлом каждой группы данных по порядку следования ключей и «склейка» результатов на master node. Главный узел получает промежуточные ответы от рабочих узлов и передает их на свободные узлы для выполнения следующего шага. Получившийся после прохождения всех необходимых шагов результат – это и есть решение исходной задачи^[6].

Модель распределенных вычислений MapReduce ориентирована на параллельные вычисления в распределенных кластерах. Суть MapReduce состоит в разделении информационного массива на части, параллельной обработки каждой части на отдельном узле и финального объединения всех результатов.

Распределенные приложения компании Google, в том числе ресурс Интернет-видео YouTube, использующие модель распределенных вычислений MapReduce, автоматически распараллеливаются и исполняются на распределенных узлах кластера, при этом исполнительная система самостоятельно выполняет разбиение входных данных на части, разделение задач по узлам кластера, обработка сбоев и сообщение между распределенными компьютерами.

Также к областям применения модели распределенных вычислений MapReduce относится распределенный поиск и сортировка данных, обращение графа веб-ссылок, обработка статистики логов сети, построение инвертированных индексов, кластеризация документов, машинное обучение[7].

Среди достоинств модели распределенных вычислений MapReduce следует отметить[8]:

- возможность распределенного выполнения операций предварительной обработки (map) и свертки (reduce) большого объема данных. При этом функции map работают независимо друг от друга и могут выполняться параллельно на разных узлах кластера;

- быстрота обработки больших объемов данных;

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

В настоящее время применение получила версия MapReduce 2.0 выполнения распределенных приложений, которая предоставляет компоненты и API для разработки распределенных приложений различных типов, обеспечивая распределение ресурсов в ответ на запросы от выполняемых приложений и ответственность за отслеживанием статуса их выполнения^[9]. Принцип работы MapReduce 2.0 отражен на рис.6.

Рис.6. Принцип работы MapReduce 2.0

Как видно из рис.6. в состав модели распределенных вычислений MapReduce 2.0 входит компонент ResourceManager, который отвечает управление ресурсами кластера, а планирование и координацию жизненного цикла приложений осуществляет ApplicationMaster. При этом каждый вычислительный узел разделен на произвольное количество контейнеров Container, содержащих предопределенное количество ресурсов: CPU, RAM, за которыми наблюдает менеджер узла NodeManage^[10].

Социальной сетью Facebook используется модель данных распределенной, колоночно-ориентированной, мультиверсионной базы типа «ключ-значение» HBase, вид которой приведен на рис.7.

Рис. 7. Модель данных распределенной базы HBase, которая используется социальной сетью Facebook

Как видно из рис.7, приложения хранят данные в таблицах, состоящих из строк и столбцов. Для ячеек таблицы (пересечения строк и столбцов) действует контроль версии^[11].

Данные организованы в таблицы, проиндексированные первичным ключом, который в распределенной базе HBase называется RowKey. Для каждого RowKey ключа могут храниться неограниченные наборы атрибутов (или колонок)^[12].

Колонки организованны в группы колонок, называемые Column Family. Как правило, в одну Column Family объединяют колонки, для которых одинаковы паттерн использования и хранения.

Список и названия групп колонок фиксирован и имеет четкую схему. На уровне группы колонок задаются такие параметры как time to live (TTL) и максимальное количество хранимых версий. Если разница между timestamp для определенно версии и текущим временем больше TTL — запись помечается к удалению. Если количество версий для определённого атрибута превысило максимальное количество версий — запись также помечается к удалению.

Централизованной службой для поддержки информации о конфигурации, обеспечения распределенной синхронизации Apache Zookeeper применяется модель данных «клиент-сервер», вид которой приведен на рис.8.

Рис.8. Модель данных централизованной службы обеспечения распределенной синхронизации Apache Zookeeper

Клиенты Client представляют один из узлов в кластере распределенного приложения, имеют доступ к информации с сервера Server. Для конкретного интервала времени каждый Client посылает сообщение Server. Аналогично, Server посылает подтверждение, когда Client подключается. Если от сервера нет ответа, клиент автоматически перенаправляет сообщение другому серверу.

Централизованная служба для поддержки информации о конфигурации, обеспечения распределенной синхронизации Apache Zookeeper является распределенным приложением и позволяет создавать распределенные приложений посредством реализации следующих возможностей^[13]:

- идентифицировать узлы в кластере по имени;

- управлять конфигурацией и кластером в режиме реального времени;

- производить блокировку и синхронизацию данных в момент их изменения;

- кодировать данные в соответствии с определенными правилами. Этот подход может быть использован в MapReduce для координации очереди для выполнения запущенных потоков.

Результаты исследований команды разработчиков Apache Zookeeper в Yahoo! (рис.9) показывают, что особенно высокую производительность продукт демонстрирует в приложениях, где число операций чтения превышает количество записей, поскольку записи включают синхронизацию состояния всех серверов.

Рис.9. Пропускная способность Apache Zookeeper как коэффициент чтения-записи в зависимости от величины ансамбля

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

Какие алгоритмы синхронизации в распределенных приложениях?

В распределенных приложениях распространение получили алгоритмы Лэмпорта и Рикарта-Агравала.

Алгоритм, предложенный Л. Лэмпортом, является одним из самых ранних распределенных алгоритмов взаимного исключения и призван проиллюстрировать применение скалярных часов для линейного упорядочивания операций, производимых процессами в распределенной системе, таких, например, как вход в КС и выход из КС.

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

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

В данном случае под отметками времени запросов на вход в КС будем подразумевать упорядоченные пары (L_i, i), где L_i – скалярное время процесса P_i на момент формирования запроса, i – идентификатор процесса P_i.

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

Рассмотрим пример работы распределенного алгоритма Лэмпорта. На рис. 10 приблизительно в одно и то же время процессы Р₂ и Р₃ запрашивают вход в КС, изменяя показания своих скалярных часов L₂ и L₃; локальная очередь каждого процесса изображена прямоугольником (будем считать, что в очередях запросы сортируются в порядке возрастания их отметок времени).

Рис.10. Алгоритм Лэмпорта сортировки запросов в очередях в порядке возрастания времени

На рис. 11 процессы Р₁ и Р₃ получают запрос от Р₂ и отправляют ему ответные сообщения. Поскольку отметка времени запроса Р₂ меньше отметки времени запроса Р₃, запрос от Р₂ помещается перед запросом от Р₃ в его собственной очереди Q₃. Это дает возможность Р₂ войти в КС вперед Р₃.

При этом процесс Р₂ сможет рассчитывать на вход к КС только тогда, когда получит ответные сообщения от Р₁ и Р₃. Отметим, что благодаря свойству FIFO каналов связи, Р₂ не сможет получить ответное сообщение от Р₃ вперед запроса, отправленного ранее процессом Р₃. Поэтому вначале Р₂ получит запрос от Р₃, поместит его в свою локальную очередь Q₂ и отправит Р₃ ответное сообщение.

Рис.11. Алгоритм Лэмпорта получения запроса и помещения его в локальную очередь

Поскольку отметка времени, поступившего от Р₃ запроса больше отметки времени запроса Р₂, запрос от Р₃ помещается в конец очереди Q₂, как показано на рис. 12.

Рис.12. Алгоритм Лэмпорта помещения запроса в конец очереди

Получив ответные сообщения от Р₁ и Р₃, процесс Р₂ войдет в КС, т.к. его запрос находится во главе его собственной очереди Q₂. Далее в сценарии процесс Р₁ переходит в состояние запроса на вход в КС и рассылает соответствующее сообщение остальным процессам. При получении запроса от Р₁ процессы Р₂ и Р₃ отправляют ответные сообщения (рис. 13).

Рис.13. Алгоритм Лэмпорта получения запроса и отправки ответных сообщений

Обратим внимание, что к этому моменту запрос на вход в КС от процесса Р₃ был получен и подтвержден процессом Р₂. Однако этот же запрос, направляемый процессу Р₁, так и не был получен.

На рис. 14 процесс Р₂ выходит из КС, удаляет свой запрос из очереди Q₂ и рассылает всем процессам сообщение RELEASE.

Рис.14. Алгоритм Лэмпорта удаления запроса из очереди и рассылки всем процессам сообщения RELEASE

Желающий войти в КС процесс Р₁ получает от Р₂ ответное сообщение и, затем, сообщение RELASE, что приводит к удалению запроса от Р₂ из очереди Q₁. Отметим, что в состоянии запроса на вход в КС находится и процесс Р₁, и процесс Р₃.

В локальной очереди каждого из этих процессов на первом месте расположен собственный запрос этого процесса. Оба этих процесса получили ответные сообщения от Р₂. Тем не менее, получить доступ к КС процесс Р₃ сможет раньше, чем Р₁, поскольку его запрос произошел раньше запроса Р₁. Действительно, Р₁ не сможет войти в КС пока не получит ответное сообщение от Р₃. Благодаря свойству FIFO канала связи между Р₃ и Р₁ это сообщение придет в Р₁ только после поступления запроса от Р_3, что проиллюстрировано на рис.15.

Рис.15. Алгоритм Лэмпорта поступления запроса от Р₃

Когда же Р₁ получит запрос от Р₃, он поместит его вперед своего собственного запроса в своей очереди Q₁, поскольку запрос от Р₃ имеет меньшую отметку времени, чем запрос от Р₁ (рис.16).

Рис.16. Алгоритм Лэмпорта поступления запроса от Р₃ и помещение его вперед Р₁

Теперь Р₁ не сможет получить доступ к КС, пока Р₃ не войдет и не выйдет из КС. В свою очередь, Р₃ войдет в КС при получении ответного сообщения от Р₁.

При выходе из КС Р₃ разошлет всем процессам сообщение RELEASE, которое приведет к удалению его запроса из всех очередей, в том числе из очереди процесса Р₁. После этого запрос процесса Р₁ окажется первым в его собственной очереди Q₁, и он сможет войти в КС, как показано на рис. 17.

Рис.17. Алгоритм Лэмпорта поступления запроса Р₁ и его вход в КС

Чтобы оценить эффективность работы алгоритма Лэмпорта, отметим, что для обеспечения взаимного исключения необходимо переслать 3(N – 1) сообщений: для входа в КС требуется (N – 1) сообщений REQUEST и (N – 1) ответных сообщений REPLY, для выхода из КС требуется (N – 1) сообщений RELEASE.

Рассмотренный алгоритм Лэмпорта явным образом выстраивает запросы на доступ к КС в очередь в порядке возрастания их отметок времени. Еще раз обратим внимание на роль сообщений REPLY и RELEASE в этом алгоритме. Ответные сообщения REPLY используются исключительно для информирования процесса, запрашивающего вход в КС, о том, что в каналах не осталось ни одного другого запроса, который мог бы встать перед его запросом в его локальной очереди.

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

В работе Г. Рикарта и А. Агравала предпринята попытка оптимизировать алгоритм Лэмпорта, исключив из него сообщения RELEASE за счет объединения функций сообщений RELEASE и REPLY в одном сообщений. Более того, алгоритм Рикарта-Агравала не требует, чтобы каналы связи обладали свойством FIFO[14].

Основная идея этого алгоритма заключается в том, что для входа в КС процессу требуется собрать разрешения от всех других процессов распределенной системы. Для этого процесс, желающий получить доступ к КС, рассылает свой запрос REQUEST всем остальным процессам и ожидает от них поступления разрешений в виде сообщений REPLY.

Условия, при которых процессы дают свое разрешение на вход в КС, сформулированы таким образом, чтобы удовлетворить требованиям безопасности и живучести. А именно, если все остальные процессы находятся в состоянии выполнения вне КС, они немедленно отправляют процессу, запрашивающему доступ к КС, сообщения REPLY. Если же один из процессов выполняется в КС, то он откладывает отправку своего разрешения до тех пор, пока сам не покинет КС, тем самым, не позволяя двум процессам выполняться в КС одновременно.

Если же несколько процессов запрашивают разрешение на вход в КС в одно и то же время, то, как и в алгоритме Лэмпорта, для разрешения конфликта доступа к КС используются линейно упорядоченные отметки времени запросов (L_i, i), где L_i – скалярное время процесса P_i на момент формирования запроса, i – идентификатор процесса P_i. Процесс, запрос которого имеет наименьшую отметку времени, получит право войти в КС первым. Это достигается за счет того, что каждый находящийся в состоянии запроса на вход в КС процесс P_i при получении запроса от другого процесса P_j сравнивает отметку времени (L_i, i) своего запроса с отметкой времени (L_j, j) поступившего запроса, и откладывает отправку REPLY, если (L_i, i) < (L_j, j). Если же (L_i, i) > (L_j, j), то процесс P_i отправляет сообщение REPLY процессу P_j немедленно. Поэтому процесс с наименьшей отметкой времени запроса получит ответные сообщения от всех остальных процессов и сможет войти в КС.

Для реализации алгоритма Рикарта-Агравала каждый процесс P_i поддерживает работу с массивом DR_i[1..N], содержащим признаки отложенного ответа (от англ. deferred reply). Если процесс P_i откладывает отправку ответного сообщения процессу P_j, он устанавливает DR_i[j] = 1; после отправки сообщения REPLY элемент DR_i[j] сбрасывается в ноль. Все элементы DR_i[k] инициализируется нулем, 1 ≤ k ≤ N.

С учетом этого массива алгоритм Рикарта-Агравала будет определяться следующими правилами.

1. Запрос на вход в КС. Когда процессу Р_i нужен доступ к КС, он переходит в состояние запроса на вход в КС, фиксируя показания своих скалярных часов L_i, и рассылает сообщение REQUEST(L_i, i) всем остальным процессам. Когда процесс Р_j получает запрос.

2. REQUEST(L_i, i) от процесса Р_i, он отправляет процессу Р_i ответ REPLY в случае, если Р_j находится в состоянии выполнения вне КС, или в случае, если Р_j находится в состоянии запроса на вход в КС и отметка времени (L_j, j) его запроса больше отметки времени (L_i, i) запроса процесса Р_i. В противном случае Р_j откладывает отправку ответного сообщения REPLY и устанавливает DR_j[i] = 1.

3. Вход в КС. Процесс Р_i может войти в КС, если он получил ответные сообщения REPLY от всех остальных процессов.

4. Выход из КС. При выходе из КС процесс Р_i рассылает отложенные сообщения REPLY всем ожидающим процессам, т.е. всем процессам Р_j, для которых DR_i[j] = 1, и затем устанавливает DR_i[j] = 0.

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

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

При этом сообщение с запросом от Р_j достигло P_i после того, как P_i отправил свой запрос; в противном случае отметка времени запроса P_i должна была бы быть больше отметки времени запроса Р_j по правилам работы логических часов. По условиям алгоритма процесс P_i не может отослать ответное сообщение REPLY процессу Р_j, находясь в состоянии запроса на вход в КС и имея меньшее значение отметки времени своего запроса, до тех пор, пока P_i не выйдет из КС. Таким образом получаем противоречие с предположением, что Р_j получил ответные сообщения REPLY от всех процессов в системе, в том числе, от процесса P_i.

Покажем теперь, что алгоритм Рикарта-Агравала обладает свойством живучести. Процесс P_i не сможет получить доступ к КС, если он отправил свой запрос, но не получил необходимого ответа хотя бы от одного процесса P_j. В этом случае будем говорить, что P_i ждет P_j. Эта ситуация возможна, если процесс P_j находится либо в состоянии выполнения внутри КС, либо в состоянии запроса на вход в КС. При этом отметка времени запроса P_j должна быть меньше отметки времени запроса P_i. Если P_j выполняется внутри КС, то через ограниченное время он выйдет из КС и отправит ответное сообщение процессу P_i. Если же P_j находится в состоянии запроса на вход в КС, то либо он войдет в КС, либо должен существовать другой процесс P_k такой, что P_j ждет P_k. Продолжая эти рассуждения, построим цепь из процессов, ожидающих друг друга: P_i ждет P_j, P_j ждет P_k, P_k ждет P_m, и т.д. Важно отметить, что эта цепь имеет ограниченную длину и является ациклической: процессы располагаются в ней в порядке убывания отметок времени запросов. Последний процесс P_l в этой цепи с наименьшим временем запроса либо выполняется в КС, либо получит разрешения от всех остальных процессов и сможет войти в КС. При выходе из КС P_l разошлет ответные сообщения всем ожидающим процессам, в том числе процессу, стоящему непосредственно слева от него, тем самым позволяя этому процессу войти в КС. Поэтому за ограниченное число шагов любой процесс окажется последним в цепи ожидающих процессов и сможет войти в КС.

В алгоритме Рикарта-Агравала, также, как и в алгоритме Лэмпорта, доступ к КС предоставляется строго в соответствии с отметками времени запросов по порядку, сохраняющему частичный причинно-следственный порядок. Отсюда следует, что после получения сообщения REQUEST от процесса P_i всеми процессами ни один из них не сможет войти в КС более одного раза вперед P_i.

Рассмотрим пример работы алгоритма Рикарта-Агравала. Также, как и в сценарии, представленном выше для алгоритма Лэмпорта, на  рис. 18 процессы Р₂ и Р₃ запрашивают вход в КС приблизительно в одно и то же время.

Рис.18. Алгоритм Рикарта-Агравала запроса входа в КС процессами Р₂ и Р₃

В свою очередь процесс Р₂, получив запрос от Р₃, откладывает отправку ответного сообщения, т.к. Р₂ находится в состоянии запроса на вход в КС и отметка времени его запроса меньше отметки времени запроса Р₃. Соответствующий элемент массива DR₂ устанавливается в единицу. Поэтому процесс Р₃ не сможет получить доступ к КС до тех пор, пока Р₂ не войдет и не выйдет из нее. Далее в сценарии процесс Р₁ переходит в состояние запроса на вход в КС и рассылает соответствующее сообщение остальным процессам, как показано на рис. 19.

Рис.19. Алгоритм Рикарта-Агравала перехода процесса Р₁ в состояние запроса на вход в КС и рассылка соответствующих сообщений остальным процессам

Между тем, получив необходимые ответы от Р₁ и Р₃, процесс Р₂ входит в КС (рис. 20).

Рис.20. Алгоритм Рикарта-Агравала входа в КС процесса Р₂

Затем запрос от процесса Р₁ достигает процессов Р₂ и Р₃. Обратим внимание, что при получении запроса от Р₁ процессы Р₂ и Р₃ не отправляют ответные сообщения, поскольку Р₂ находится в состоянии выполнения в КС, а Р₃ находится в состоянии запроса на вход в КС и отметка времени его запроса меньше отметки времени запроса Р₁.

В итоге цепь ожидающих процессов будет выглядеть следующим образом: Р₁ ждет Р₃, Р₃ ждет Р₂. Действительно, процесс Р₃ знает о том, что его ждет процесс Р₁, т.к. DR₃[1] = 1, а процесс Р₂ знает о том, что его ждут процессы Р₁ и Р₃, т.к. DR₂[1] = 1 и DR₂[3] = 1.

На рис. 21 процесс Р₂ выходит из КС и рассылает отложенные ответы ожидающим процессам Р₁ и Р₃. Теперь последним в цепи ожидающих процессов оказывается процесс Р₃, и он войдет в КС следующим.

Рис.21. Алгоритм Рикарта-Агравала рассылки отложенных ответов ожидающим процессам Р₁ и Р₃

На рис. 22 запрос процесса Р₃ достигает процесса Р₁, и, несмотря на то, что сам Р₁ находится в состоянии запроса на вход в КС, он высылает Р₃ ответ, поскольку отметка времени запроса Р₁ больше отметки времени запроса Р₃.

Рис.22. Алгоритм Рикарта-Агравала, когда запрос процесса Р₃ достигает процесса Р₁

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

Отметим, что в отличие от алгоритма Лэмпорта, алгоритм Рикарта- Агравала использует для работы с КС 2(N – 1) сообщений: (N – 1) сообщений требуется для входа в КС и (N – 1) сообщений требуется для выхода из КС.

Заключение

На основании выполненного исследования можно сделать выводы, что компания Google использует распределенную файловую систему GFS, которая обеспечивает хранение и обработку больших массивов информации, технология MapReduce и распределенный механизм хеширования BigTable.

Недостатком распределенной файловой системы GFS является то, что она не позволяет реализовать географическую распределенность без существенных задержек времени. Для решения данной проблемы компанией Google была обновлена распределенная файловая система с выпуском multi cell-ориентированной архитектурой Colossus.

Мною был рассмотрен пример использования распределенных вычислений и приложений на ресурсе YouTube, который получил лидерство в сфере Интернет-видео. Ресурсом YouTube используются распределенные блокировки Zookeeper и BigTable для хранения изображений.

BigTable предоставляет механизм просмотра данных для получения доступа к структурированным данным по имеющемуся ключу. С помощью контролирования своих низкоуровневых систем хранения данных, ресурс YouTube получает больше возможностей по управлению и модификации их системой. Каждый блок данных хранится в ячейке, доступ к которой может быть предоставлен как по ключу строки или столбца, так и по временной метке.

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

В основе модели данных HBase лежит концепция BigTable от компании Google, которая хорошо подходит для поиска строк по идентификаторам, фильтрации и сканированию наборов строк.

Среди недостатков следует отметить отсутствие поддержки сложных запросов, но этот недостаток компенсируется системой Apache Hive, которая выступает SQL-интерфейсом доступа к данным для платформы Apache Hadoop, разработанной Facebook для работы с большими массивами данных.

Для данных в файловой системе HDFS используется схема доступа на чтение, позволяющая обращаться с данными, как с обыкновенной таблицей или реляционной СУБД. Запросы HiveQL транслируются в Java-код заданий MapReduce.

Модель распределенных вычислений MapReduce ориентирована на параллельные вычисления в распределенных кластерах. Суть MapReduce состоит в разделении информационного массива на части, параллельной обработки каждой части на отдельном узле и финального объединения всех результатов.

Распределенные приложения компании Google, в том числе ресурс Интернет-видео YouTube, использующие модель распределенных вычислений MapReduce, автоматически распараллеливаются и исполняются на распределенных узлах кластера, при этом исполнительная система самостоятельно выполняет разбиение входных данных на части, разделение задач по узлам кластера, обработка сбоев и сообщение между распределенными компьютерами.

Также к областям применения модели распределенных вычислений MapReduce относится распределенный поиск и сортировка данных, обращение графа веб-ссылок, обработка статистики логов сети, построение инвертированных индексов, кластеризация документов, машинное обучение.

В настоящее время применение получила версия MapReduce 2.0 выполнения распределенных приложений, которая предоставляет компоненты и API для разработки распределенных приложений различных типов, обеспечивая распределение ресурсов в ответ на запросы от выполняемых приложений и ответственность за отслеживанием статуса их выполнения.

При написании эссе мною были рассмотрены модель данных распределенной, колоночно-ориентированной, мультиверсионной базы типа «ключ-значение» HBase социальной сети Facebook и модель данных «клиент-сервер» централизованной службы для поддержки информации о конфигурации, обеспечения распределенной синхронизации Apache Zookeeper.

Для получения большего представления о распределенных приложениях мною были рассмотрены алгоритмы Лэмпорта и Рикарта-Агравала.

Было отмечено, что в отличие от алгоритма Лэмпорта, алгоритм Рикарта- Агравала использует для работы с КС 2(N – 1) сообщений: (N – 1) сообщений требуется для входа в КС и (N – 1) сообщений требуется для выхода из КС.

Список литературы

1. Google File System (GFS). URL: https://www.codeinstinct.pro/2013/11/gfs.html
2. Colossus. Распределенная файловая система от Google. URL: https://www.pvsm.ru/google/51440
3. Архитектура YouTube. URL: https://www.insight-it.ru/highload/2012/arkhitektura-youtube-2012/
4. Архитектура Google. URL: https://www.insight-it.ru/highload/2008/arkhitektura-google/
5. Система Apache Hive. URL: https://www.bigdataschool.ru/wiki/hive
6. MapReduce. URL:  https://www.bigdataschool.ru/wiki/mapreduce
7. Национальная библиотека им. Н. Э. Баумена. MapReduce. URL: https://ru.bmstu.wiki/MapReduce
8. Академик. MapReduce. URL: https://dic.academic.ru/dic.nsf/ruwiki/607046
9. MapReduce 2.0. URL: https://habr.com/ru/post/161437/
10. Data models of Apache HВase. URL: https://ru.wikipedia.org/wiki/HBase
11. Table data model of Apache HВase. URL: http://https://intellect.ml/big-data-ot-chast-4-hbase-6819
12. Apache ZooKeeper. URL: https://ru.bmstu.wiki/Apache_ZooKeeper
13. Косяков М. С. Введение в распределенные вычисления: учеб. пособие / М. С. Косяков. – СПб: НИУ ИТМО, 2014. – С.105.