Новые технологии распределенного хранения и обработки больших массивов данных о. В. Сухорослов
 Скачать 296.71 Kb.
|
|
2.3. Технология Microsoft Dryad Универсальная технология распределенной обработки данных Dryad [11] разрабатывается компанией Microsoft. В настоящее время эта технология является закрытой и применяется только внутри компании, например, в поисковой системе MSN Live Search. Описание технологии было опубликовано в работе [12]. Модель программирования Dryad основана на представлении приложения в виде ориентированного ациклического графа. Вершинами графа являются процессы. Ребра графа определяют потоки данных между процессами в виде односторонних каналов. У процесса может быть несколько входных и выходных каналов. Вершины графа могут быть сгруппированы в стадии (stage). Важно отметить, что модель программирования Dryad содержит в себе в качестве частных случаев реляционную алгебру и MapReduce. Система организует выполнение приложения на имеющихся вычислительных ресурсах, будь то многоядерная машина или кластер из большого числа машин. При этом система автоматически осуществляет планирование вычислений, распределение вершин между машинами, обработку отказов и динамическую оптимизацию структуры графа. В качестве вершин графа могут выступать программы на C++ или другом языке. Каналы между вершинами реализуются несколькими способами: файлы в распределенной и сетевой файловой системе, TCP-каналы, FIFO-очереди в оперативной памяти. Выбор того или иного варианта реализации каждого канала в графе может производиться системой автоматически, исходя из текущей конфигурации системы и размещения процессов по машинам. 33 Пользователь описывает граф приложения с помощь интерфейса прикладного программирования на языке C++. При запуске задания на кластере создается менеджер задания (job manager), которые управляет выполнением графа задания. Менеджер задания получает информацию о ресурсах кластера, генерирует граф задания, инициализирует его вершины, пересылает их код на узлы кластера и контролирует выполнение вершин. На узлах кластера запущены процессы, запускающие код вершин графа и позволяющие менеджеру задания отслеживать состояние выполнения вершин. При размещении вершин на узлах кластера система учитывает потоки данных между вершинами и старается разместить взаимодействующие вершины на одной машине или рядом друг с другом. Наиболее интересной особенностью Dryad является поддержка динамической модификации структуры графа задания во время его выполнения. Приведем несколько примеров. Система обнаруживает вершины, выполняемые медленнее других вершин данной стадии, и автоматически создает дублирующие вершины (аналогично backup- заданиям в MapReduce). Вершина, выполняющая агрегацию данных из множества вершин, может быть снабжена вспомогательными вершинами, которые производят локальную агрегацию данных из вершин в пределах серверной стойки и т.п. (аналогично combine-функции в MapReduce). Вершина может быть заменена на несколько вершин путем разбиения обрабатываемых вершиной данных. Для равномерного разбиения входных данных по значениям их ключей система создает вспомогательные вершины, которые определяют распределение данных по ключам и разбивают данные на равные части. Пользователь также может реализовывать собственные стратегии динамической модификации графа. Возможности Dryad интегрированы в высокоуровневые языки и системы, такие как DryadLINQ и Microsoft SQL Server. В настоящее время не существует общедоступных аналогов Dryad, таких как Hadoop для MapReduce. 34 3. Инфраструктурные сервисы В крупномасштабных распределенных системах, состоящих из ненадежных вычислительных машин, остро стоят вопросы обеспечения отказоустойчивости и бесперебойной работы функционирующих сервисов. Для решения подобных задач могут применяться высоконадежные реплицируемые сервисы координации распределенных процессов. В качестве примеров реализации подобных сервисов рассматриваются сервисы Chubby и Zookeeper. 3.1. Chubby Из соображений отказоустойчивости и масштабируемости, описанные выше технологии Google спроектированы как распределенные системы, компоненты которых слабо связаны друг с другом (loosely-coupled). Это означает, что компоненты системы должны динамически обнаруживать и отслеживать состояние друг друга, автоматически выбирать в случае отказа новый главный сервер и гибким образом координировать свои действия. Возложение подобных функций на главный сервер делает его уязвимым местом системы. С другой стороны, реализация полностью децентрализованных механизмов в присутствии большого количества машин может оказаться сложной и неэффективной в сравнении с централизованными решениями. Для решения этой проблемы в компании Google был создан отдельный высоконадежный сервис Chubby [13], используемый такими системами, как GFS, BigTable и MapReduce. Наличие готового сервиса координации упрощает создание сложных распределенных систем. Внутренние системы Google используют Chubby для обнаружения серверов, выбора главного сервера и хранения важных данных. По сути, GFS и BigTable используют Chubby в качестве корневого сервиса для своих распределенных структур данных. С точки зрения клиентов Chubby выглядит как централизованный сервис. Высокая надежность сервиса обеспечивается за счет репликации его на пяти машинах и использования децентрализованного механизма выборов главной реплики. Сервис доступен до тех пор, пока большинство реплик функционируют и могут 35 взаимодействовать друг с другом. Выбор главного сервера среди множества узлов является частным случаем задачи о консенсусе в распределенной системе. Для выбора главной реплики в Chubby используется известный алгоритм Paxos [14]. Chubby предоставляет клиентам интерфейс, напоминающий файловую систему с иерархическим пространством имен. В отличие от обычных файловых систем, акцент делается на высокой доступности и надежности, а не на хранимом объеме данных и пропускной способности. Сервис ориентирован на хранение большого числа небольших файлов и поддержку большого числа клиентов. При этом большую часть запросов составляют операции чтения. Обслуживаемые Chubby файлы и директории образуют узлы файловой системы. Клиенты могут создавать произвольные узлы и записывать в них данные. Кроме того, узлы могут использоваться в качестве блокировки (lock). Блокировка может быть исключающей (exclusive) или совместной (shared). Также существует специальный тип временных узлов, которые автоматически удаляются в том случае, если они не открыты ни одним клиентом (или пусты, в случае директорий). Каждый клиент Chubby поддерживает периодически продлеваемую сессию. В случае если клиент не продлил свою сессию в течение определенного времени, Chubby автоматически снимает удерживаемые клиентом блокировки и удаляет связанные с клиентом временные файлы. Этот механизм может использоваться для отслеживания статусов клиентов. В свою очередь, Chubby периодически отправляет клиентам уведомления о событиях, связанных с открытыми клиентом узлами: создании, удалении и модификации узлов, изменении содержимого или статуса блокировки узла и т.п. Приведем несколько примеров использования Chubby для координации компонентов распределенной системы. Для определения главного сервера в системе может использоваться исключительная блокировка выделенного файла в Chubby. Первый сервер, получивший блокировку файла, считается главным, после чего он записывает свой адрес в данный файл. Другие сервера отслеживают содержимое файла для определения текущего главного сервера и статус блокировки файла для обнаружения отказа главного сервера. Для получения главным сервером списка подчиненных серверов может использоваться выделенная директория, в который 36 каждый сервер создает временный файл со своим адресом. При отказе сервера его сессия в Chubby истекает, и файл автоматически удаляется. Подобные события могут отслеживаться главным сервером системы с помощью механизма уведомлений Chubby. Как было упомянуто в разделе 1.3, система BigTable хранит в Chubby различные метаданные и местоположение корневого таблета. Сервис также активно используется в качестве альтернативы сервису разрешения имен DNS. В заключение, отметим что, как и другие описанные ранее технологии Google, сервис Chubby является закрытой разработкой, используемой только внутри компании. 3.2. ZooKeeper Общедоступным аналогом описанной выше технологии Chubby является сервис ZooKeeper [15] , разработка которого ведется сотрудниками компании Yahoo на принципах open source. Опустим описание архитектуры и принципы реализации ZooKeeper, поскольку они практически совпадают с Chubby. Отметим, что ZooKeeper может быть применен в сочетании с платформой Hadoop для повышения надежности системы и координации отдельных серверов. Например, с помощью ZooKeeper можно произвести динамическую конфигурацию Hadoop во время запуска системы по требованию на вычислительном кластере. В этом случае клиент и развернутые на кластере TaskTracker-процессы могут определить через ZooKeeper адрес развернутого JobTracker- процесса. 37 Заключение В заключении остановимся на новизне описанных технологий, сферах их применения, а также дальнейших перспективах их развития. С точки зрения алгоритмов и методов в описанных технологиях мало нового. Во многом они опираются на наработки предшественников, сочетая их и, в некоторых случаях, упрощая. Главной заслугой этих систем является выход на принципиально новые масштабы обрабатываемых данных и самих вычислительных инфраструктур. Для этого потребовалось радикально пересмотреть использовавшиеся ранее предположения об архитектуре и принципах функционирования подобных систем. Например, в описанных системах отказ является штатной ситуацией, которая обнаруживается и обрабатывается в автоматическом режиме. В результате неизбежных компромиссов системы часто жертвуют привычной функциональностью, такой как строгие гарантии целостности данных, поддержка реляционной модели или реализация стандартных интерфейсов файловой системы. Модель программирования MapReduce жертвует гибкостью и универсальностью ради поддержки автоматического управления вычислениями в распределенной среде. Безусловно, круг приложений MapReduce ограничен параллельными по данным задачами, где не требуется организовывать сложное взаимодействие между процессами. Но, как показывает практика, таких приложений очень много, и тот уровень удобства, на который MapReduce поднимает программирование подобных вычислений, заслуживает внимания. Следующим шагом в данном направлении является технология Microsoft Dryad, более универсальная и мощная, чем MapReduce. Несмотря на то, что оригинальные реализации технологий являются закрытыми разработками, благодаря open source проектам активно развиваются их общедоступные аналоги. Хочется отметить, что данные технологии, пришедшие из индустрии, начинают активно использоваться в академической среде. Как упоминалось во введении, стоящие перед исследователями вычислительные задачи часто имеют такие же требования, что и задачи Google. Представляется, что подобные технологии в ближайшее время станут неотъемлемой частью современных информационных систем, 38 в которых все чаще возникает потребность в хранении и анализе больших объемов информации. 39 Литература [1] Barroso, L. A., Dean, J., and Urs Hölzle, U. Web search for a planet: The Google cluster architecture. IEEE Micro 23, 2, pp. 22-28, 2003. [2] J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. Commun. ACM, vol. 51, no. 1, pp. 107-113, January 2008. [3] J. Dean. Handling Large Datasets at Google: Current Systems and Future Directions. Data-Intensive Computing Symposium, March 2008. http://research.yahoo.com/files/6DeanGoogle.pdf [4] Ghemawat, S., Gobioff, H., and Leung, S.-T. The Google file system. In 19th Symposium on Operating Systems Principles, Lake George, NY, pp. 29-43, 2003. [5] The Hadoop Distributed File System: Architecture and Design. http://hadoop.apache.org/core/docs/current/hdfs_design.html [6] Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: A distributed storage system for structured data. In OSDI'06: Seventh Symposium on Operating System Design and Implementation, Seattle, WA, USA, November 2006, pp. 205-218. [7] HBase. http://hadoop.apache.org/hbase/ [8] Dean, J. and Ghemawat, S. MapReduce: Simplified data processing on large clusters. In Proceedings of Operating Systems Design and Implementation (OSDI). San Francisco, CA. 137-150, 2004. [9] M. Cole. Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press & Pitman, ISBN 0-262-53086-4, 1989. [10] Apache Hadoop. http://hadoop.apache.org/ [11] Microsoft Dryad. http://research.microsoft.com/research/sv/dryad/ [12] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. European Conference on Computer Systems (EuroSys), Lisbon, Portugal, March 21-23, 2007. [13] Burrows, M. The Chubby lock service for loosely-coupled distributed systems. In OSDI '06: Proceedings of the 7th symposium on Operating systems design and implementation. Berkeley, CA, USA: USENIX Association, 2006, pp. 335-350 40 [14] Lamport, L. The part-time parliament. ACM Trans. Comput. Syst., vol. 16, no. 2, pp. 133-169, May 1998. [15] ZooKeeper. http://zookeeper.sourceforge.net/ |