НИС Распределенные системы (осень 2016) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Практические задания)
(Практические задания)
Строка 100: Строка 100:
  
 
==== Требования к сдаче ====
 
==== Требования к сдаче ====
Сдача задания будет происходить через Anytask (http://anytask.org/course/116 / oMUmkee). При сдаче укажите:
+
Сдача задания будет происходить через Anytask (ссылка: http://anytask.org/course/116 ; инвайт: oMUmkee). При сдаче укажите:
 
* ссылку на github/bitbucket репозиторий;
 
* ссылку на github/bitbucket репозиторий;
 
* ссылки на реализацию алгоритма Лампорта;
 
* ссылки на реализацию алгоритма Лампорта;

Версия 15:57, 3 октября 2016

Содержание

Информация про семинар

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

[TBD: Оценка за НИС, отчетность, курсовые работы]


Занятия

2 сентября

Вводное занятие.

Материалы:

  • Mockapetris, Dunlap -- Development of the domain name system (pdf)

9 сентября

Отмена занятия.

16 сентября

Сетевое взаимодействие в распределенных системах.

Материалы:

  • Google Code University -- Introduction to Distributed Systems Design (pdf)
  • Birrell, Nelson -- Implementing remote procedure calls (pdf)
  • Eriksen -- Your server as a function (pdf)
  • (по желанию) Liskov -- Promises: linguistic support for efficient asynchronous procedure calls in distributed systems (pdf)
  • (по желанию) Futures/Promises в C++: интерфейс (1, 2, 3), рабочая имплементация (1).

Вопросы для самопроверки:

  • Какие классы сетевых ошибок встречаются в распределенных системах?
  • Что такое удаленный вызов (Remote Procedure Call)?
  • Опишите основные фазы исполнения удаленного вызова согласно оригинальной статье.
  • Как осуществляется связывание вызывающей и вызываемой стороны?
  • Как осуществляется передача аргументов и результата между вызывающей и вызываемой сторонами?
  • Каким механизмом обеспечивается гарантия однократного исполнения вызова?
  • Можно ли передавать указатели в удаленные вызовы?
  • Какие новые классы ошибок появляются при удаленных вызовах и отсутствуют при локальных вызовах?
  • Какие предпосылки в оригинальном дизайне RPC стоит пересмотреть с учетом прогресса за последние 30 лет?
  • Зачем нужна концепция futures/promises? Чем отличается удаленный вызов с использованием future/promise и без?
  • Как использование futures/promises влияет на структуру асинхронной программы?
  • Какую роль играют сервисы, фильтры в Finagle? Перечислите аргументы "за" и "против" использования данных абстракций.
  • Какие другие паттерны сетевого взаимодействия вы можете представить помимо RPC?

23 сентября

Время, часы, синхронизация событий.

Материалы:

  • Lamport -- Time, clocks and the ordering of events in a distributed system (pdf)
  • Fidge -- Timestamps in message-passing systems that preserve the partial ordering (pdf)
  • Mills -- Internet time synchronization: the network time protocol (pdf)

Вопросы для самопроверки:

  • Почему физические часы не используются для синхронизации в распределенной системе?
  • Какие события называются конкурентными (одновременными)?
  • Приведите пример исполнения распределенной системы и несколько различных логических часов, определяющих непротиворечивый порядок событий.
  • Опишите распределенный алгоритм mutual exclusion и докажите его корректность.
  • Опишите механизм точных часов, сохраняющих частичный порядок на событиях (векторные часы).
  • Опишите протокол синхронизации часов NTP.
  • Какие трудности возникают на практике при синхронизации часов?

30 сентября

Синхронизация событий (продолжение). Когерентность памяти.

Материалы:

  • Li, Hudak -- Memory coherency in shared virtual memory systems (pdf)

Вопросы для самопроверки:

  • Опишите плюсы и минусы использования общей виртуальной памяти в распределенных системах.
  • Что такое когерентность?
  • Опишите предлагаемые в статье протоколы обеспечения когерентности виртуальной памяти и их различия.

Будущие занятия

Для справки ниже перечислен предполагаемый список тем для изучения на последующих занятиях. Если у вас есть предложения, что какие работы, темы стоит разобрать на семинаре, то пишите мне на sandello-at-gmail-dot-com.

  • Консистентность (Bayou, CRDTs)
  • Консенсус (Paxos, Raft)
  • P2P (BitTorrent, BitCoin)
  • Управление ресурсами (DRF; Borg; Omega)
  • Изоляция и конкурентное исполнение транзакций

Практические задания

Lamport Mutex

В рамках первого практического задания вам предлагается реализовать распределенный алгоритм взаимного исключения, описанный Лампортом в статье Time, clocks and the ordering of events in a distributed system (см. материалы занятия от 23.09). Реализовать данное задание требуется до 31-го октября, 14:00.

Требования к реализации

  1. Конфигурация конкретного процесса (например, список сетевых адресов других процессов) указывается через аргументы командной строки.
  2. Сетевое взаимодействие должно быть вынесено за RPC-слой. RPC-слой вам нужно реализовать самостоятельно. От вас не требуется сверхоптимальный код; от вас требуется создать целостную абстракцию. Клиентский код (использующий RPC-сервис), серверный код (реализующий RPC-сервис), транспортный код (сериализация/десериализация, работа с сетью) должны быть разделены.
  3. Каждый процесс должен поддерживать логические часы.
  4. Каждый из процессов должен вести собственный, локальный журнал событий request / acquire / release (запрос на взятие mutex-а, взятие mutex-а, освобождение mutex-а). Каждое событие должно быть аннотировано физическим временем, логическим временем, PID-ом.
  5. При взятии mutex-а (событие acquire) процесс должен открыть некий специальный файл (например, ~/mutex.txt), вызывать flock(_, LOCK_EX), записывать в файл пометку (PID, логическое время взятие mutex-а, логическое время освобождение mutex-а), после чего отпускать (release) mutex.
  6. Должны поддерживаться два режима работы: ручной, когда взятие mutex-а инициирует пользователь, и стрессовый, когда приложение в цикле пробует взять mutex.
  7. Для реализации можно использовать языки C++, Python, Java, Go.

Требования к тестированию

  1. Должны быть написаны юнит-тесты на алгоритм взятия mutex-а, подменяющие сетевую имплементацию RPC-сервиса на локальную.
  2. Должна быть проведена экспериментальная проверка корректности работы в стресс-режиме для 10 запущенных процессов (в случае корректной работы не должно быть ошибок от flock-а на разделяемый файл).
  3. Должна быть написана утилита анализа локальных логов процессов, проверяющая, что по логическим часам периоды acquire-release не пересекаются, и что для каждого процесса acquire следует строго после request.

Требования к сдаче

Сдача задания будет происходить через Anytask (ссылка: http://anytask.org/course/116 ; инвайт: oMUmkee). При сдаче укажите:

  • ссылку на github/bitbucket репозиторий;
  • ссылки на реализацию алгоритма Лампорта;
  • ссылку на реализацию RPC-слоя (где происходит сетевое взаимодействие, где устанавливаются соединения, где происходит серилизация/десериализация вызовов, где происходит регистрация сервисов);
  • ссылку на реализацию логических часов;
  • ссылку на анализатор локальных логов процессов;
  • инструкцию по сборке проекта;
  • инструкцию по запуску юнит-тестов;
  • инструкцию по запуску стресс-теста с 10 процессами;
  • инструкцию по запуску анализатора локальных логов.

Критерии сдачи

Задание считается сданным, если:

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

Указания

  • Обычно при имплементации RPC-слоя возникают такие абстракции как стаб (интерфейс, используемый клиентской стороной и реализуемый серверной стороной), сервис (отвечает за маршрутизацию конкретного вызова в конкретный метод языка), сервер (отвечает за сетевое серверное взаимодействие (bind+accept), маршрутизацию вызова в конкретный сервис), канал (создается клиентом, скрывает сетевое взаимодействие (connect), реализует отправку запросов и получение ответов). На клиенте стаб связывается с каналом, на сервере -- с сервисом.
  • Учтите, что в данном задании каждый процесс является и клиентом, и сервером одновременно. Не усложняйте преждевременно имплементацию, начните с однопоточной версии.

Курсовые работы

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

ClickHouse

Руководитель: Алексей Миловидов

ClickHouse -- открытая колоночная СУБД, позволяющая выполнять аналитические запросы в интерактивном режиме по данным, обновляемым в реальном времени. ClickHouse разработан в Яндексе для задач Яндекс.Метрики -- второй по величине системы веб-аналитики в мире.

Создание генератора тестовых данных, приближающих настоящие

Существующие бенчмарки системы основаны на внутренних данных Яндекс.Метрики, и поэтому не могут быть воспроизведены людьми снаружи, что затрудняет корректное сравнение производительности. В рамках предлагаемой курсовой работы предлагается придумать и реализовать генератор псевдослучайных тестовых данных так, чтобы:

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

Симуляция и анализ стратегий слияния данных

В системе для обеспечения высокой пропускной способности при вставке данных используются различные вариации техники log structured merge tree, что приводит к эффекту, известному как write amplification: когда реальных объем записываемых данных на диск кратно превосходит объем данных, вставленный в систему. Причина такого эффекта -- необходимость фоновых слияний данных для предотвращения деградации производительности чтения. В данной работе предлагается разработать симулятор фоновых слияний, а также проанализировать различные стратегии слияния с точки зрения различных метрик эффективности.

Автоматизация тестирования производительности

В данной работе предлагается разработать и реализовать фреймворк для автоматического тестирования производительности различных компонент системы. Создаваемый фреймворк может быть использован для:

  • регрессионных тестов производительности (основное применение);
  • сравнение версий компилятора и флагов сборки, сравнение библиотек, приёмка новых версий;
  • тестирование железа, а также настроек ОС, получение рейтинга производительности с точки зрения ClickHouse;
  • просмотр динамики изменения производительности с течением времени по мере разработки.

Планировщик ресурсов кластера

Руководитель: Игнат Колесниченко

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

Улучшение симулятора

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

Анализ различных стратегий вытеснения

Один из механизмом для обеспечения честности распределения ресурсов -- это вытеснение (preemption) вычислений. Однако, вытеснение части MR-вычисления подразумевает потерю выполненной работы, так как результат вычисления никуда не сохраняется. В данной работе предлагается провести анализ различных стратегий вытеснения и их влияния на различные метрики качества.

Учет истории потребления ресурсов

Текущая стратегия планирования HDRF (hierarchical dominant resource fairness) никак не учитывает историю потребления ресурсов кластера, что, например, дает преимущство пользователям, постоянно запускающим какие-либо вычисления. В данной работе предлагается проанализировать разные способы учета истории потребления ресурсов, вывести метрики качества.

Алгоритм консенсуса без явно выделенного мастера

Руководитель: Григорий Демченко

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

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

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

Формальная спецификация с использованием TLA+

Многие аспекты распределенных алгоритмов и систем не являются интуитивно понятными (параллельность исполнения, переупорядочивание событий), что приводит к труднодиагностируемым ошибкам в имплементациях. В рамках данной работы предлагается разработать формальную спецификацию алгоритма консенсуса с использованием языка TLA+.

Реализация алгоритма и экспериментальная оценка

В данной работе вам предлагается имплементировать предлагаемый алгоритм, проверить его корректность и оценить производительность в различных интересных с точки зрения практики сценариях, например:

  • междатацентровая репликация с существенно различными временами >100мс между узлами;
  • внутридатацентровая репликация с временами <1мс;
  • поведение в плохих сетях (выпадание пакетов, неопределенные задержки с доставкой);
  • использование протокола UDP вместо TCP для обмена сообщениями;
  • batching запросов;
  • стабильность и производительность при выпадении/добавлении узлов;
  • замеры для различного числа узлов, оценка деградации производительности с ростом числа узлов;
  • сравнение с существующими алгоритмами консенсуса.

Физическое хранение данных

Руководители: Игнат Колесниченко, Иван Пузыревский, Павел Сушин

При чтении/записи данных с современных облаков / распределенных файловых систем обычно задействовано много программных слоев: типизированное кодирование, компрессия, erasure-кодирование. Данный блок тем посвящен экспериментальному анализу различных аспектов систем хранения данных.

Разработка системы оценки алгоритмов сжатия

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

Сравнительный анализ различных алгоритмов erasure-кодирования

Для экономии дискового места при хранении данных используются erasure-коды, позволяющие переживать отказ отдельных дисков/машин с небольшими накладными расходами (1.33x..1.5x; например, коды Рида-Соломона). По сравнению с обычной репликацией данных, erasure-коды более ресурсозатратны в процессе восстановления данных. За последние несколько лет появился ряд новых алгоритов erasure-кодирования, представляющих различные компромиссы в пространстве решений. В данной работе предлагается провести сравнительный и экспериментальный анализ данного класса алгоритмов.

Экспериментальный анализ алгоритмов типизированного кодирования

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

Анализ стратегий размещения реплик данных на кластере

Распределенные системы хранения данных почти всегда разбивают хранимые данные на блоки, которые размещаются на кластере согласно какой-либо стратегии. Например, на практике используется случайная стратегия размещения, стратегия размещения с учетом стоек/ЦОДов, с группировкой/без. Основные количественные метрики различных стратегий -- это вероятность потери данных; среднее количество потерянных блоков; среднее количество частично недоступных групп блоков (файлов). В данной работе предлагается разработать симулятор, моделирующий отказы узлов кластера по историческим данным, собранным с реального кластера, и оценивающий метрики качества различных стратегий.

Анализ кеширования данных в кластерах с различной нагрузкой

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

Остальные темы

Формальная спецификация HDFS

Руководитель: Иван Пузыревский

HDFS (Hadoop Distributed File System) -- распределенная отказоустойчивая файловая система. В данной работе предлагается разработать и проверить формальную спецификацию системы с помощью TLA+.

Автоматическое определение проблемных узлов кластера

Руководитель: Павел Сушин

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

Создание имитационных моделей вычислительных ресурсов и распределенных вычислительных инфраструктур

Руководитель: Олег Сухорослов

Симуляция и сравнительный анализ алгоритмов планирования задач в распределенных вычислительных системах

Руководитель: Олег Сухорослов

Исследование и экспериментальная оценка технологий распределенных вычислений на основе pilot jobs

Руководитель: Олег Сухорослов

Использование простаивающих вычислительных ресурсов для распределенных вычислений на базе платформы Everest

Руководитель: Олег Сухорослов

Реализация универсального вычислительного агента для систем распределенных вычислений

Руководитель: Олег Сухорослов

Исследование и реализация методов прямой передачи данных по сети между узлами за NAT и межсетевыми экранами

Руководитель: Олег Сухорослов

Исследование и экспериментальная оценка методов обеспечения отказоустойчивости MPI-приложений

Руководитель: Олег Сухорослов