Просмотр кода страницы Темы для курсовых работ 2016 (РС)

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

Ниже приведены описания возможных проектов курсовой работы (напоминаю, что на третьем курсе в качестве курсовой работы засчитывается и [http://wiki.cs.hse.ru/Проектная_работа проектная работа]).

Если вас заинтересовала какая-либо из предложенных тем и вы хотите над ней поработать в рамках вашей курсовой работы, то ваша последовательность действий такая:
# напишите письмо руководителю темы, в копию письма добавьте Пузыревского Ивана (ipuzyrevskiy@hse.ru); укажите, над какой задачей вы хотите поработать; укажите релевантную информацию про вас (публичный github, опыт по теме, что вы сочтете нужным);
# далее, вам нужно с руководителем обсудить задачу и возможность работы над ней; обычно руководитель вам чуть более подробно вам расскажет, что от вас будет требоваться, вы обсудите, насколько реально вам выполнить предлагаемую работу;
# в конечном итоге, вы вместе с руководителем приходите или к положительному решению (вы работаете над оговоренной задачей), или к отрицательному (вам необходимо выбрать другую тему курсовой работы).

=== ClickHouse ===

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

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

'''Руководитель''': [mailto:milovidov@yandex-team.ru Алексей Николаевич Миловидов]

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

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

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

'''Руководитель''': [mailto:milovidov@yandex-team.ru Алексей Николаевич Миловидов]

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

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

'''Руководитель''': [mailto:milovidov@yandex-team.ru Алексей Николаевич Миловидов]

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

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

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

В системе [https://habrahabr.ru/company/yandex/blog/311104/ YT] одна из наиболее значимых компонент -- это планировщик вычислений. Именно он отвечает за распределение ресурсов кластера между пользователями с учетом их требований и желаемых гарантий (зачастую, противоречивых). От эффективности работы планировщика зависит общая эффективность работы кластера и удовлетворенность пользователей. Для проведения оффлайн-экспериментов над алгоритмами планировщика был разработан симулятор, использующий "трейс" событий, снятый с реального кластера (запуск вычислений, освобождение вычислительных ресурсов, потеря вычислений в результате сбоя, и др.). Ниже представлены возможные направления для последующих исследований и улучшений данной функциональности.

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

'''Руководитель''': [mailto:ignat@yandex-team.ru Игнатий Игоревич Колесниченко]

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

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

'''Руководитель''': [mailto:ignat@yandex-team.ru Игнатий Игоревич Колесниченко]

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

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

'''Руководитель''': [mailto:ignat@yandex-team.ru Игнатий Игоревич Колесниченко]

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

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

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

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

'''Руководитель''': [mailto:gridem@yandex-team.ru Григорий Викторович Демченко]

Многие аспекты распределенных алгоритмов и систем не являются интуитивно понятными (параллельность исполнения, переупорядочивание событий), что приводит к труднодиагностируемым ошибкам в реализациях. В рамках данной работы предлагается разработать формальную спецификацию алгоритма консенсуса с использованием языка [http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html TLA+]. 

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

'''Руководитель''': [mailto:gridem@yandex-team.ru Григорий Викторович Демченко]

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

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

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

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

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

'''Руководитель''': [mailto:ignat@yandex-team.ru Игнатий Игоревич Колесниченко], [mailto:sandello@yandex-team.ru Иван Витальевич Пузыревский], [mailto:psushin@yandex-team.ru Павел Андреевич Сушин]

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

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

'''Руководитель''': [mailto:ignat@yandex-team.ru Игнатий Игоревич Колесниченко]

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

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

'''Руководители''': [mailto:sandello@yandex-team.ru Иван Витальевич Пузыревский], [mailto:psushin@yandex-team.ru Павел Андреевич Сушин]

В дополнение к общим алгоритмам сжатия, работающим на уровне байт, на практике используются также типизированные кодеки, позволяющие добиться более высокой степени сжатия данных. К примеру, использование [https://en.wikipedia.org/wiki/Run-length_encoding RLE], [https://en.wikipedia.org/wiki/Shannon–Fano–Elias_coding кодов Элиса-Фано] для кодирования чисел; использование сжатых словарей для кодирования строк. Иногда кодированое представление допускает выполнение операций (например, поиска) поверх сжатых данных, без промежуточного расжатия; или допускает быстрый случайный доступ. В данной работе предлагается провести сравнительный и экспериментальный анализ различных кодеков для различных типов данных.

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

'''Руководитель''': [mailto:ignat@yandex-team.ru Игнатий Игоревич Колесниченко], [mailto:psushin@yandex-team.ru Павел Андреевич Сушин]

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

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

'''Руководитель''': [mailto:sandello@yandex-team.ru Иван Витальевич Пузыревский]

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

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

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

'''Руководитель''': [mailto:sandello@yandex-team.ru Иван Витальевич Пузыревский]

HDFS (Hadoop Distributed File System) -- распределенная отказоустойчивая файловая система. В данной работе предлагается разработать и проверить формальную спецификацию системы с помощью [http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html TLA+].

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

'''Руководитель''': [mailto:psushin@yandex-team.ru Павел Андреевич Сушин]

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

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

'''Руководитель''': [mailto:oleg.sukhoroslov@gmail.com Олег Викторович Сухорослов]

Имитационное моделирование активно используется в исследованиях распределенных систем, заменяя натурные эксперименты и позволяя воспроизводимым образом сравнивать между собой различные методы (например, алгоритмы планирования задач). В данной работе объектом моделирования являются распределенные вычислительные инфраструктуры, состоящие из нескольких автономных ресурсов различного типа (кластеров, гридов, облаков, персональных компьютеров). Для реалистичного моделирования таких инфраструктур требуется хорошо моделировать отдельные ресурсы, их планировщики, нагрузку и доступность, а также передачу данных по сети. Для данных целей предлагается использовать [http://simgrid.gforge.inria.fr/ SimGrid], фреймворк для создания симуляторов распределенных систем. Требуется улучшить имеющиеся или реализовать новые модели ресурсов (например, кластер с планировщиком и внутренним потоком заданий), а также интегрировать их в единую модель. Возможны отдельные подтемы и работа в команде.

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

'''Руководитель''': [mailto:oleg.sukhoroslov@gmail.com Олег Викторович Сухорослов]

Планирование выполнения задач в распределенных системах в постановках, представляющих практический интерес, является NP-полной задачей. За последнее десятилетие было предложено множество алгоритмов планирования, основанных на различного рода (мета)эвристиках и ориентированных на различные классы приложений (bag of tasks, parallel job, workflow) и систем. При этом недостаточно хорошо изучен вопрос об области применимости и сравнительной эффективности данных алгоритмов в различных ситуациях. В данной работе предлагается реализовать на базе существующего симулятора наиболее известные алгоритмы и сравнить их друг с другом путем проведения имитационных экспериментов для различных типов приложений и систем. Возможны отдельные подтемы и работа в команде.

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

'''Руководитель''': [mailto:oleg.sukhoroslov@gmail.com Олег Викторович Сухорослов]

При реализации крупномасштабных вычислений на базе распределенных ресурсов с собственными планировщиками часто используется стратегия pilot jobs. Данная стратегия, заключающаяся в запуске на ресурсах заданий-агентов с последующим динамическим распределением по ним задач, позволяет уменьшить влияние задержек в очередях ресурсов и накладные расходы на запуск задач. В настоящее время существует несколько технологий (pilot job frameworks), реализующих данный подход, например HTCondor, DIANE, BigJob, Swift, DIRAC. В данной работе предлагается изучить и сравнить между собой несколько данных технологий путем их развертывания и проведения экспериментов на тестовой инфраструктуре. Особое внимание планируется уделить сравнению производительности различных решений, оценке их масштабируемости, выявлению узких мест и поиску способов их устранения.

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

'''Руководитель''': [mailto:oleg.sukhoroslov@gmail.com Олег Викторович Сухорослов]

Платформа [http://everest.distcomp.org/ Everest], разрабатываемая в ИППИ РАН, позволяет публиковать в виде веб-сервисов вычислительные приложения и запускать через веб-интерфейс расчеты на произвольных комбинациях внешних ресурсов, подключенных пользователями к платформе. Интеграция ресурсов с платформой реализована на основе специально разработанного агента, который выполняется на стороне ресурса. В настоящее время агент поддерживает запуск задач на одиночной машине (в монопольном режиме) и кластере (с приоритетом обычного пользователя), не учитывая внешнюю нагрузку на ресурс. В данной работе предлагается реализовать поддержку использования ресурса только в моменты его простоя, что требует мониторинга текущей загрузки ресурса и динамического управления задачами. При этом планируется использовать опыт и наработки систем, ориентированных на использование простаивающих персональных компьютеров (BOINC, Condor).

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

'''Руководитель''': [mailto:oleg.sukhoroslov@gmail.com Олег Викторович Сухорослов]

Платформа [http://everest.distcomp.org/ Everest], разрабатываемая в ИППИ РАН, позволяет публиковать в виде веб-сервисов вычислительные приложения и запускать через веб-интерфейс расчеты на произвольных комбинациях внешних ресурсов, подключенных пользователями к платформе. Интеграция ресурсов с платформой реализована на основе специально разработанного агента, который выполняется на стороне ресурса. Агент написан на языке Python с использованием фреймворка Tornado и реализует асинхронную обработку, запуск и мониторинг поступающих задач, загрузку данных и обмен сообщениями с платформой. В данной работе предлагается реализовать принципиально новую версию агента на языке Go. Помимо имеющейся функциональности планируется реализовать прямое взаимодействие по сети между агентами, автоматическое обновление кода агента, а также обеспечить универсальность агента для его использования с другими системами распределенных вычислений.

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

'''Руководитель''': [mailto:oleg.sukhoroslov@gmail.com Олег Викторович Сухорослов]

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

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

'''Руководитель''': [mailto:oleg.sukhoroslov@gmail.com Олег Викторович Сухорослов]

Одной из основных проблем, связанных с использованием в будущем мощных вычислительных систем уровня [https://en.wikipedia.org/wiki/Exascale_computing exascale], является обеспечение устойчивости параллельных программ к отказам. Поскольку данные системы могут включать миллионы процессоров, выполняющих до миллиарда потоков, то ожидается что в них с высокой частотой (до нескольких раз в час) будут возникать всевозможные сбои на аппаратном и программном уровнях, приводящие к падению процессов или потере данных. Традиционные методы, такие как checkpointing, становятся неэффективными в условиях, когда сохранение состояния требует времени сопоставимого с частотой отказов. В настоящее время активно ведется разработка новых методов, нацеленных на решение данной проблемы, в частности применительно к выполнению MPI-программ. В данной работе предлагается изучить данные методы, провести их экспериментальную оценку и, возможно, улучшить.