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

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

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

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

=== Рекомендуемые темы проектной работы ===

==== Безопасность ====
По поводу тем курсовых работ на тему информационной безопасности можно обращаться напрямую к [[mailto:gamajun@gmail.com Денису Гамаюнову]]. В рамках командной проектной работы предлагается два проекта:
* http://wiki.cs.hse.ru/Децентрализованный_крипточат_(командный_проект)
* http://wiki.cs.hse.ru/Веб-краулер_для_поиска_уязвимостей_авторизации_(командный_проект)

==== Криптовалюты, блокчейн ====
По поводу курсовых работ на тему криптовалют, блокчейна можно обращаться напрямую к [[Участник:Ryavorsky|Ярославу Яворскому]] для непосредственного обсуждения. Ниже приведены примеры тем, предлагаемых в рамках проектной работы на 2-м курсе.
* http://wiki.cs.hse.ru/Анализ_данных,_хранимых_в_реестрах_криптовалют_(проект)
* http://wiki.cs.hse.ru/Аналитический_сервис_по_новостям_в_сфере_блокчейн_технологий_(проект)
* http://wiki.cs.hse.ru/Тестирование_и_верификация_смарт-контрактов_(проект)
* http://wiki.cs.hse.ru/Разработка_веб_интерфейсов_для_криптовалют_и_смарт-контрактов_(проект)

=== Темы возможных курсовых работ ===

==== ClickHouse (9 тем) ====

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

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

В качестве тем для курсовых работ предлагается следующий набор проектов:
* Использование первичного ключа при ORDER BY monotonic(PK), GROUP BY injective(subset(PK)).
* Поддержка форматов ввода-вывода Parquet и Protobuf.
* Модификаторы WITH ROLLUP и WITH CUBE для GROUP BY.
* Поддержка вычисляемых DEFAULT выражений для полуструктурированных форматов JSONEachRow, TSKV.
* Short-curcuit вычисление некоторых функций.
* Оптимизация простых выражений с помощью генерации LLVM кода.
* Кэширование промежуточных данных конвейера выполнения запроса.
* Оптимизация алгоритма слияний.
* Генератор тестовых данных.

==== Postgres Pro: Автоматизация смены мастера в кластере PostgreSQL, использующем логическую  репликацию ====
'''Руководитель''': [mailto:marat.abubekerov@gmail.com Абубекеров Марат]

Есть кластер  PostgreSQL  с  мастером  и  несколькими  репликами.  Используется логическая  репликация.  Требуется  разработать  приложение, которое  в  случае  выхода мастера  из  строя  автоматически  выбирает  нового  мастера  и  переключает  на  него остальные  реплики.  Допускается зависимость  от  сторонних  приложений,  в  частности etcd  или  Consul.

==== Postgres Pro: Приоритезация запросов  в  РСУБД  PostgreSQL ====
'''Руководитель''': [mailto:marat.abubekerov@gmail.com Абубекеров Марат]

Исследовать  различные  механизмы  приоритезации запросов  в  реляционных  базах данных.  Реализовать  механизм  приоритезации з апросов  для  РСУБД  PostgreSQL. Запросы  с  большим  приоритетом  выполняются  раньше запросов  с  низким приоритетом.  Кроме того,  время,  выделяемое  на  выполнение запросов, пропорционально  их  приоритетам.  Например,  при  одновременном  выполнении  OLTP  и OLAP запросов  становится  возможно  присвоить  первым  более  высокий  приоритет, чем  вторым.  В  результате  OLTP запросы  будут  выполняться как  можно  быстрее,  а OLAP запросы  будут  выполняться  в  фоне  с  меньшим  приоритетом.

==== Postgres Pro: Разработка  механизма  ограничения  используемых  ресурсов  в  PostgreSQL ====
'''Руководитель''': [mailto:marat.abubekerov@gmail.com Абубекеров Марат]

Исследование  механизмов  ограничения  использования  системных  ресурсов -   времени CPU,  оперативной  памяти,  места  на  диске,  сетевого трафика,  и так  далее.  Реализация механизма  ограничения  используемых  ресурсов  по  пользователям  и  сессиям  для РСУБД  PostgreSQL.  Допускается  использование  сторонних  механизмов,  в  частности cgroups.

==== Postgres Pro: Реализация  в  модуле  pg_trgm  поиска  по  N-граммам  с  N  >  3 ====
'''Руководитель''': [mailto:marat.abubekerov@gmail.com Абубекеров Марат]

Модуль  pg_trgm  для  PostgreSQL  позволяет  делать  индексы  по триграммам  для нечеткого  поиска.  К  примеру,  слово 'молоко'  будет  разложено  на  массив триграмм [ мол,  оло,  лок,  око]  и  если  поисковый  слово  содержит  опечатку, то большинство триграмм  останется  неизменным.  Это  свойство  используется  для поиска:  можно  разложить  искомые  слова/фразы  на триграммы,  построить  по ним  обратный ( инвертированный)  индекс  и  при  поиске  искать  документы  с максимальным  числом  одинаковых триграмм.  Такой  подход  хорошо  и  быстро работает  на  словах  и  небольших  фразах.
Однако  данный  подход  не  эффективен,  если  поиск  ведется  по  предложениям. Так как  предложение  большое, то  разных триграмм  от каждого  документа получается  много  и  поисковый запрос  будет  пересекаться  с  очень  большим количеством  строк  в таблице.  Чтобы  избежать  этого,  предлагается реализовать  поддержку  не триграмм,  а  на  N-грамм  с  N=4,5  и так  далее.  Тогда разных  N-грам  ставится  экспоненциально  больше  с  ростом  N  и  соответственно вероятность  встретить  данную  N-грамму -   меньше,  следовательно  при  поиске требуется  проверять  на  соответствие  меньше  строк  и  поиск  становится эффективнее.

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

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

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

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

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

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

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

==== Фреймворк для изучения, разработки и тестирования распределенных алгоритмов при наличии отказов ====

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

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

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

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

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

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

'''Руководитель''': [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-программ. В данной работе предлагается изучить данные методы, провести их экспериментальную оценку и, возможно, улучшить.