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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 35 промежуточных версии 3 участников)
Строка 2: Строка 2:
 
В рамках научно-исследовательского семинара по распределенным системам изучаются основные понятия, принципы и результаты предметной области.  
 
В рамках научно-исследовательского семинара по распределенным системам изучаются основные понятия, принципы и результаты предметной области.  
  
[TBD: Оценка за НИС, отчетность, курсовые работы]
+
=== Оценка ===
  
 +
Оценка за НИС складывается из двух частей: оценки за практические задания и общей оценки.
 +
 +
''S = S_tasks + S_general''
 +
 +
Практических заданий -- две штуки: одно на программирование, одно на работу с текстом. За первое задание можно получить максимум 5 баллов, за второе максимум 3 балла. Сдача после дедлайна штрафуется. За каждый просроченный модуль -- минус балл. Таким образом, максимум за первое задание при сдаче во втором модуле можно получить 4 балла, в третьем -- 3, в четвертом -- 2.
 +
 +
Общая оценка складывается из трех частей: посещаемости, участия в семинарах и экзамена. Суммарно общая оценка ограничена сверху 3 баллами. Посещаемость оценивается в 0.25 балла за каждый модуль, если вы посетили более половины занятий в данном модуле. Активность -- до 0.50 балла каждый модуль по усмотрению преподавателя. Экзамен -- до 2.00 баллов (4*0.50).
 +
 +
''S_general = min(3.00, S_attendance + S_participation + S_exam); S_attendance <= 1.00; S_participation <= 2.00; S_exam <= 2.00''
 +
 +
Текущая таблица с оценками доступна [https://docs.google.com/spreadsheets/d/1s5ZTsYTt90PV2QJo0DVAcc0W7sGf8NsPBSoONIzdDAI/pubhtml по ссылке].
  
 
== Занятия ==
 
== Занятия ==
  
=== 2 сентября ===
+
=== 1 модуль ===
 +
 
 +
==== 2 сентября ====
 
Вводное занятие.
 
Вводное занятие.
  
Строка 13: Строка 26:
 
* ''Mockapetris, Dunlap'' -- Development of the domain name system ([https://yadi.sk/i/hSHHyuoUv9Xsk pdf])
 
* ''Mockapetris, Dunlap'' -- Development of the domain name system ([https://yadi.sk/i/hSHHyuoUv9Xsk pdf])
  
=== 9 сентября ===
+
==== 9 сентября ====
''Отмена занятия''.
+
'''Занятия не будет'''.
  
=== 16 сентября ===
+
==== 16 сентября ====
 
Сетевое взаимодействие в распределенных системах.
 
Сетевое взаимодействие в распределенных системах.
  
Строка 26: Строка 39:
 
* (по желанию) Futures/Promises в C++: интерфейс ([https://bartoszmilewski.com/2009/03/03/broken-promises-c0x-futures/ 1], [https://bartoszmilewski.com/2009/03/10/futures-done-right/ 2], [https://bartoszmilewski.com/2014/02/26/c17-i-see-a-monad-in-your-future/ 3]), рабочая имплементация ([https://github.com/facebook/folly/tree/master/folly/futures 1]).
 
* (по желанию) Futures/Promises в C++: интерфейс ([https://bartoszmilewski.com/2009/03/03/broken-promises-c0x-futures/ 1], [https://bartoszmilewski.com/2009/03/10/futures-done-right/ 2], [https://bartoszmilewski.com/2014/02/26/c17-i-see-a-monad-in-your-future/ 3]), рабочая имплементация ([https://github.com/facebook/folly/tree/master/folly/futures 1]).
  
Вопросы для самопроверки:
+
==== 23 сентября ====
* Какие классы сетевых ошибок встречаются в распределенных системах?
+
* Что такое удаленный вызов (Remote Procedure Call)?
+
* Опишите основные фазы исполнения удаленного вызова согласно оригинальной статье.
+
* Как осуществляется связывание вызывающей и вызываемой стороны?
+
* Как осуществляется передача аргументов и результата между вызывающей и вызываемой сторонами?
+
* Каким механизмом обеспечивается гарантия однократного исполнения вызова?
+
* Можно ли передавать указатели в удаленные вызовы?
+
* Какие новые классы ошибок появляются при удаленных вызовах и отсутствуют при локальных вызовах?
+
* Какие предпосылки в оригинальном дизайне RPC стоит пересмотреть с учетом прогресса за последние 30 лет?
+
* Зачем нужна концепция futures/promises? Чем отличается удаленный вызов с использованием future/promise и без?
+
* Как использование futures/promises влияет на структуру асинхронной программы?
+
* Какую роль играют сервисы, фильтры в Finagle? Перечислите аргументы "за" и "против" использования данных абстракций.
+
* Какие другие паттерны сетевого взаимодействия вы можете представить помимо RPC?
+
 
+
=== 23 сентября ===
+
 
Время, часы, синхронизация событий.
 
Время, часы, синхронизация событий.
  
Строка 49: Строка 47:
 
* ''Mills'' -- Internet time synchronization: the network time protocol ([https://yadi.sk/i/PdXX6TO2vN6Bw pdf])
 
* ''Mills'' -- Internet time synchronization: the network time protocol ([https://yadi.sk/i/PdXX6TO2vN6Bw pdf])
  
Вопросы для самопроверки:
+
==== 30 сентября ====
* Почему физические часы не используются для синхронизации в распределенной системе?
+
* Какие события называются конкурентными (одновременными)?
+
* Приведите пример исполнения распределенной системы и несколько различных логических часов, определяющих непротиворечивый порядок событий.
+
* Опишите распределенный алгоритм mutual exclusion и докажите его корректность.
+
* Опишите механизм точных часов, сохраняющих частичный порядок на событиях (векторные часы).
+
* Опишите протокол синхронизации часов NTP.
+
* Какие трудности возникают на практике при синхронизации часов?
+
 
+
=== 30 сентября ===
+
  
 
Синхронизация событий (продолжение). Когерентность памяти.
 
Синхронизация событий (продолжение). Когерентность памяти.
Строка 65: Строка 54:
 
* ''Li, Hudak'' -- Memory coherency in shared virtual memory systems ([https://yadi.sk/i/gXssi_hRvjUY6 pdf])
 
* ''Li, Hudak'' -- Memory coherency in shared virtual memory systems ([https://yadi.sk/i/gXssi_hRvjUY6 pdf])
  
Вопросы для самопроверки:
+
==== 7 октября ====
* Опишите плюсы и минусы использования общей виртуальной памяти в распределенных системах.
+
* Что такое когерентность?
+
* Опишите предлагаемые в статье протоколы обеспечения когерентности виртуальной памяти и их различия.
+
  
=== Будущие занятия ===
+
Ослабление модели памяти. Слабоконсистентные хранилища на примере Bayou.
Для справки ниже перечислен предполагаемый список тем для изучения на последующих занятиях. Если у вас есть предложения, что какие работы, темы стоит разобрать на семинаре, то пишите мне на [mailto:sandello@gmail.com sandello-at-gmail-dot-com].
+
  
* Консистентность (Bayou, CRDTs)
+
Материалы:
* Консенсус (Paxos, Raft)
+
* ''Terry et. al.'' -- Managing update conflicts in Bayou, a weakly connected replicated storage system ([https://yadi.sk/i/Gxu0RvtOw8inm pdf])
* P2P (BitTorrent, BitCoin)
+
* Управление ресурсами (DRF; Borg; Omega)
+
* Изоляция и конкурентное исполнение транзакций
+
  
== Практические задания ==
+
==== 14 октября ====
  
=== Первое задание: Lamport Mutex ===
+
'''Занятия не будет.'''
  
В рамках первого практического задания вам предлагается реализовать распределенный алгоритм взаимного исключения, описанный Лампортом в статье Time, clocks and the ordering of events in a distributed system (см. материалы занятия от 23.09). Реализовать данное задание требуется до 31-го октября, 14:00.
+
==== 21 октября ====
  
==== Требования к реализации ====
+
Детальный рассказ о предлагаемых курсовых работах от руководителей.
1. Конфигурация конкретного процесса (например, список сетевых адресов других процессов) указывается через аргументы командной строки.
+
2. Сетевое взаимодействие должно быть вынесено за RPC-слой. RPC-слой вам нужно реализовать самостоятельно. От вас не требуется сверхоптимальный код; от вас требуется создать целостную абстракцию. Клиентский код (использующий RPC-сервис), серверный код (реализующий RPC-сервис), транспортный код (сериализация/десериализация, работа с сетью) должны быть разделены.
+
3. Каждый процесс должен поддерживать логические часы.
+
4. Каждый из процессов должен вести собственный, локальный журнал событий request / acquire / release (запрос на взятие mutex-а, взятие mutex-а, освобождение mutex-а). Каждое событие должно быть аннотировано физическим временем, логическим временем, PID-ом.
+
5. При взятии mutex-а (событие acquire) процесс должен открыть некий специальный файл ("//tmp/mylog.txt"), вызывать flock(_, LOCK_EX), записывать в файл пометку (PID, логическое время взятие mutex-а, логическое время освобождение mutex-а), после чего отпускать (release) mutex.
+
6. Должны поддерживаться два режима работы: ручной, когда взятие mutex-а инициирует пользователь, и стрессовый, когда приложение в цикле пробует взять mutex.
+
7. Для реализации можно использовать языки C++, Python, Java, Go.
+
  
==== Требования к тестированию ====
+
=== 2 модуль ===
1. Должны быть написаны юнит-тесты на алгоритм взятия mutex-а, подменяющие сетевую имплементацию RPC-сервиса на локальную.
+
2. Должна быть проведена экспериментальная проверка корректности работы в стресс-режиме для 10 запущенных процессов (в случае корректной работы не должно быть ошибок от flock-а на разделяемый файл).
+
3. Должна быть написана утилита анализа локальных логов процессов, проверяющая, что по логическим часам периоды acquire-release не пересекаются, и что для каждого процесса acquire следует строго после request.
+
  
==== Требования к сдаче ====
+
==== 4 ноября ====
Сдача задания будет происходить через Anytask (http://anytask.org/course/116 / oMUmkee). При сдаче укажите:
+
* ссылку на github/bitbucket репозиторий;
+
* ссылки на реализацию алгоритма Лампорта;
+
* ссылку на реализацию RPC-слоя (где происходит сетевое взаимодействие, где устанавливаются соединения, где происходит серилизация/десериализация вызовов, где происходит регистрация сервисов);
+
* ссылку на реализацию логических часов;
+
* ссылку на анализатор локальных логов процессов;
+
* инструкцию по сборке проекта;
+
* инструкцию по запуску юнит-тестов;
+
* инструкцию по запуску стресс-теста с 10 процессами;
+
* инструкцию по запуску анализатора локальных логов.
+
  
==== Критерии сдачи ====
+
'''Занятия не будет.'''
Задание считается сданным, если:
+
* предоставлена реализация алгоритма, удовлетворяющая вышеуказанным требованиям;
+
* юнит-тесты успешно отрабатывают;
+
* стресс-тест успешно отрабатывает;
+
* анализатор локальных логов подтверждает корректность значений логических часов.
+
  
== Курсовые работы ==
+
==== 11 ноября ====
  
Ниже приведены описания возможных проектов курсовой работы. Если у вас есть собственная идея для курсовой работы, то вы можете попробовать ее предложить вашему потенциальному научному руководителю. На третьем курсе в качестве курсовой работы засчитывается также [http://wiki.cs.hse.ru/Проектная_работа проектная работа].  
+
Задача распределенного консенсуса. Paxos.
  
=== ClickHouse ===
+
* ''Lamport'' -- Paxos made simple ([https://yadi.sk/i/ZTjKI346y6C3m pdf])
 +
* (по желанию) ''Lamport'' -- The part-time parliament ([https://yadi.sk/i/bExaZsh4y6CqB pdf]; [http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#lamport-paxos история публикации])
 +
* ''Ousterhout'' -- Paxos lecture ([https://www.youtube.com/watch?v=JEpsBg0AO6o video]; 1.0ч)
 +
* ''Guerraoui'' -- Paxos lecture ([https://www.youtube.com/watch?v=WX4gjowx45E video]; 0.5ч)
  
'''Руководитель''': Алексей Миловидов
+
==== 18 ноября ====
  
[https://clickhouse.yandex/ ClickHouse] -- открытая колоночная СУБД, позволяющая выполнять аналитические запросы в интерактивном режиме по данным, обновляемым в реальном времени. ClickHouse разработан в Яндексе для задач Яндекс.Метрики -- второй по величине системы веб-аналитики в мире.
+
Распределенный консенсус, продолжение. Viewstamped replication.
  
==== Создание генератора тестовых данных, приближающих настоящие ====
+
* ''Liskov, Cowling'' -- Viewstamped replication revisited ([https://yadi.sk/i/EO37MNowy6Cwv pdf])
 +
* ''Oki, Liskov'' -- Viewstamped replication: a new primary copy method to support highly available distributed systems ([https://yadi.sk/i/5pVDiF7Qy6D3D pdf])
  
Существующие [https://clickhouse.yandex/benchmark.html бенчмарки] системы основаны на внутренних данных Яндекс.Метрики, и поэтому не могут быть воспроизведены людьми снаружи, что затрудняет корректное сравнение производительности. В рамках предлагаемой курсовой работы предлагается придумать и реализовать генератор псевдослучайных тестовых данных так, чтобы:
+
==== 25 ноября ====
  
* приблизительно сохранить вероятностные распределения значений в столбцах;
+
Распределенный консенсус, продолжение. Raft.
* для некоторых случаев, сохранить совместные распределения;
+
* приблизительно сохранить коэффициент сжатия данных в столбцах;
+
* желательно сделать модель данных достаточно компактной (например, несколько мегабайт).
+
  
==== Симуляция и анализ стратегий слияния данных ====
+
* ''Ongaro, Ousterhout'' -- In search of understandable consensus algorithm ([https://yadi.sk/i/K5gdY2X2y6EE4 pdf])
 +
* (по желанию) ''Howard et. al.'' -- Raft refloated: do we have consensus? ([https://yadi.sk/i/BQ6yMr-zy6EHW pdf])
 +
* ''Ousterhout'' -- Raft lecture ([https://www.youtube.com/watch?v=YbZ3zDzDnrw video]; 1.0ч)
  
В системе для обеспечения высокой пропускной способности при вставке данных используются различные вариации техники [https://en.wikipedia.org/wiki/Log-structured_merge-tree log structured merge tree], что приводит к эффекту, известному как write amplification: когда реальных объем записываемых данных на диск кратно превосходит объем данных, вставленный в систему. Причина такого эффекта -- необходимость фоновых слияний данных для предотвращения деградации производительности чтения. В данной работе предлагается разработать симулятор фоновых слияний, а также проанализировать различные стратегии слияния с точки зрения различных метрик эффективности.
+
==== 2 декабря ====
  
==== Автоматизация тестирования производительности ====
+
Распределенный консенсус, завершение.
  
В данной работе предлагается разработать и реализовать фреймворк для автоматического тестирования производительности различных компонент системы. Создаваемый фреймворк может быть использован для:
+
* ''Chandra et. al.'' -- Paxos made live: an engineering perspective ([https://yadi.sk/i/G7S7Ku6zy6ERw pdf])
 +
* ''van Renesse et. al.'' -- Vive la différence: Paxos vs. Viewstamped replication vs. Zab ([https://yadi.sk/i/aanIRk9ly6EVW pdf])
 +
* (по желанию) ''Junqueira et. al.'' -- Zab: high performance broadcast for primary-backup systems ([https://yadi.sk/i/iZMiY8ayy6EaS pdf])
 +
* (по желанию) ''Medeiros'' -- ZooKeeper's atomic broadcast protocol: theory and practice ([https://yadi.sk/i/gNHW6YuEy6EgQ pdf])
  
* регрессионных тестов производительности (основное применение);
+
==== 9 декабря ====
* сравнение версий компилятора и флагов сборки, сравнение библиотек, приёмка новых версий;
+
* тестирование железа, а также настроек ОС, получение рейтинга производительности с точки зрения ClickHouse;
+
* просмотр динамики изменения производительности с течением времени по мере разработки.
+
  
=== Планировщик ресурсов кластера ===
+
CRDTs: счетчики (G, PN, NN), множества (G, 2P, U, LWW, PN, OR).
  
'''Руководитель''': Игнат Колесниченко
+
* ''Shapiro et. al.'' -- A comprehensive study of convergent and commutative replicated data types ([https://yadi.sk/d/75pfodsK32UEKQ pdf])
  
В системе [https://habrahabr.ru/company/yandex/blog/311104/ YT] одна из наиболее значимых компонент -- это планировщик вычислений. Именно он отвечает за распределение ресурсов кластера между пользователями с учетом их требований и желаемых гарантий (зачастую, противоречивых). От эффективности работы планировщика зависит общая эффективность работы кластера и удовлетворенность пользователей. Для проведения оффлайн-экспериментов над алгоритмами планировщика был разработан симулятор, использующий "трейс" событий, снятый с реального кластера (запуск вычислений, освобождение вычислительных ресурсов, потеря вычислений в результате сбоя, и др.). Ниже представлены возможные направления для последующих исследований и улучшений данной функциональности.
+
==== 16 декабря ====
  
==== Улучшение симулятора ====
+
CRDTs: списочные структуры.
  
В текущей версии симулятора известен ряд недоработок, существенно влияющих на качество симуляции. Например, текущий симулятор не учитывает зависимость вычислений между собой (когда выход одного вычисления используется как вход для другого). За счет использования метаинформации (имя пользователя, время начала/окончания вычислений, именование входных/выходных данных) можно было бы восстановить данные зависимости, что позволит существенно улучшить качество симуляции и, соответственно, качество вычисляемых метрик для цепочек вычислений.
+
* ''Nedelec et. al.'' -- LSEQ: an adaptive structure for sequences in distributed collaborative editing ([https://yadi.sk/i/1te0_h1S32UG3G pdf])
  
==== Анализ различных стратегий вытеснения ====
+
=== 3 модуль ===
  
Один из механизмом для обеспечения честности распределения ресурсов -- это вытеснение (preemption) вычислений. Однако, вытеснение части MR-вычисления подразумевает потерю выполненной работы, так как результат вычисления никуда не сохраняется. В данной работе предлагается провести анализ различных стратегий вытеснения и их влияния на различные метрики качества.
+
==== 24 января ====
  
==== Учет истории потребления ресурсов ====
+
Иерархические блокировки.
  
Текущая стратегия планирования HDRF (hierarchical dominant resource fairness) никак не учитывает историю потребления ресурсов кластера, что, например, дает преимущство пользователям, постоянно запускающим какие-либо вычисления. В данной работе предлагается проанализировать разные способы учета истории потребления ресурсов, вывести метрики качества.
+
* ''Grey et. al.'' -- Granularity of locks in a shared database ([https://yadi.sk/i/xmxCp1CQ3Aiwob pdf])
  
=== Алгоритм консенсуса без явно выделенного мастера ===
+
==== 31 января ====
  
'''Руководитель''': Григорий Демченко
+
Уровни изоляции. Классификация через аномалии.
  
Современные системы и сервисы требуют отказоустойчивого поведения на всех уровнях. Как правило, такие системы крайне сложны для понимания, так как нельзя полагаться на различные допущения о временных интервалах посылки сообщений, уметь работать с отказами оборудования, а также сохранять доступность при потерях связности между частями системы. Асинхронная природа посылки сообщений также усложняет взаимодействие между компонентами. Для упрощения взаимодействия применяют достаточно сложные алгоритмы репликации для получения отказоустойчивого состояния, распределенного между узлами системы. Алгоритмы консистентного изменения распределенного состояния называют алгоритмами консенсуса.
+
* ''Bernson et. al.'' -- A critique of ANSI SQL isolation levels ([https://yadi.sk/i/O_Ub6TYs3AiuUE pdf])
+
Как правило, все существующие на сегодняшний день алгоритмы в той или иной степени используют выделенный мастер-узел для выполнения основной части работы по сохранению консистентности. Вам предлагается исследовать уникальный алгоритм консенсуса без мастера. Уникальность состоит в полном отказе от традиционных методов достижения консенсуса, позволяя добиться уникальных характеристик систем, работающих на основе такого алгоритма.
+
+
Так как алгоритм полностью новый, то любые исследования в этой области представляют несомненный интерес. Фактически -- передний край науки.
+
  
==== Формальная спецификация с использованием TLA+ ====
+
==== 7 февраля ====
  
Многие аспекты распределенных алгоритмов и систем не являются интуитивно понятными (параллельность исполнения, переупорядочивание событий), что приводит к труднодиагностируемым ошибкам в имплементациях. В рамках данной работы предлагается разработать формальную спецификацию алгоритма консенсуса с использованием языка [http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html TLA+].  
+
Уровни изоляции. Формальная модель.
  
==== Реализация алгоритма и экспериментальная оценка ====
+
* ''Adya, Liskov, O'Neil'' -- Generalized isolation level definitions ([https://yadi.sk/i/kTCgW3Jy3Aivtb pdf])
  
В данной работе вам предлагается имплементировать предлагаемый алгоритм, проверить его корректность и оценить производительность в различных интересных с точки зрения практики сценариях, например:
+
==== 14 февраля ====
  
* междатацентровая репликация с существенно различными временами >100мс между узлами;
+
Уровни изоляции & управление одновременным исполнением транзакций.
* внутридатацентровая репликация с временами <1мс;
+
* поведение в плохих сетях (выпадание пакетов, неопределенные задержки с доставкой);
+
* использование протокола UDP вместо TCP для обмена сообщениями;
+
* batching запросов;
+
* стабильность и производительность при выпадении/добавлении узлов;
+
* замеры для различного числа узлов, оценка деградации производительности с ростом числа узлов;
+
* сравнение с существующими алгоритмами консенсуса.
+
  
=== Физическое хранение данных ===
+
* ''Xie et. al.'' -- High-performance ACID via modular concurrency control ([https://yadi.sk/i/JYQeEg_63DJ9cR pdf])
  
'''Руководители''': Игнат Колесниченко, Иван Пузыревский, Павел Сушин
+
==== 21 февраля ====
  
При чтении/записи данных с современных облаков / распределенных файловых систем обычно задействовано много программных слоев: типизированное кодирование, компрессия, erasure-кодирование. Данный блок тем посвящен экспериментальному анализу различных аспектов систем хранения данных.
+
Отмена занятия.
  
==== Разработка системы оценки алгоритмов сжатия ====
+
==== 28 февраля ====
  
Наиболее часто алгоритмы сжатия сравнивают по скорости сжатия/расжатия и коэффициенту сжатия. Однако, данные характеристики варьируются в зависимости от конкретных входных данных, железа, и ряда других факторов. В данной работе предлагается систематически подойти к вопросу и реализовать фреймворк для оценки алгоритмов сжатия, с помощью которого можно быстро получить исчерпывающий анализ производительности на конкретном железе/на конкретных данных.
+
Окончание уровней изоляции (закончили разбор материалов с предыдущих семинаров).
  
==== Сравнительный анализ различных алгоритмов erasure-кодирования ====
+
==== 7 марта ====
  
Для экономии дискового места при хранении данных используются erasure-коды, позволяющие переживать отказ отдельных дисков/машин с небольшими накладными расходами (1.33x..1.5x; например, [https://ru.wikipedia.org/wiki/Код_Рида_—_Соломона коды Рида-Соломона]). По сравнению с обычной репликацией данных, erasure-коды более ресурсозатратны в процессе восстановления данных. За последние несколько лет появился ряд новых алгоритов erasure-кодирования, представляющих различные компромиссы в пространстве решений. В данной работе предлагается провести сравнительный и экспериментальный анализ данного класса алгоритмов.
+
Отладка распределенных систем: трассировка сетевого взаимодействия.
  
==== Экспериментальный анализ алгоритмов типизированного кодирования ====
+
* ''Fonseca et. al.'' -- X-Trace: a pervasive network tracing framework ([https://yadi.sk/i/M7NZeknW3EqkV9 pdf])
 +
* ''Sigelman et. al.'' -- Dapper, a large-scale distributed systems tracing infrastructure ([https://yadi.sk/i/5pfVnzBC3Eqkr5 pdf])
  
В дополнение к общим алгоритмам сжатия, работающим на уровне байт, на практике используются также типизированные кодеки, позволяющие добиться более высокой степени сжатия данных. К примеру, использование [https://en.wikipedia.org/wiki/Run-length_encoding RLE], [https://en.wikipedia.org/wiki/Shannon–Fano–Elias_coding кодов Элиса-Фано] для кодирования чисел; использование сжатых словарей для кодирования строк. Иногда кодированое представление допускает выполнение операций (например, поиска) поверх сжатых данных, без промежуточного расжатия; или допускает быстрый случайный доступ. В данной работе предлагается провести сравнительный и экспериментальный анализ различных кодеков для различных типов данных.
+
==== 14 марта ====
  
==== Анализ стратегий размещения реплик данных на кластере ====
+
Отладка распределенных систем: отладка производительности, вывод взаимосвязей событий.
  
Распределенные системы хранения данных почти всегда разбивают хранимые данные на блоки, которые размещаются на кластере согласно какой-либо стратегии. Например, на практике используется случайная стратегия размещения, стратегия размещения с учетом стоек/ЦОДов, с группировкой/без. Основные количественные метрики различных стратегий -- это вероятность потери данных; среднее количество потерянных блоков; среднее количество частично недоступных групп блоков (файлов). В данной работе предлагается разработать симулятор, моделирующий отказы узлов кластера по историческим данным, собранным с реального кластера, и оценивающий метрики качества различных стратегий.
+
* ''Barham et. al.'' -- Magpie: online modelling and performance-aware systems ([https://yadi.sk/i/ezE0m1m33EqmBW pdf])
 +
* ''Chow et. al.'' -- The mystery machine: end-to-end performance analysis of large-scale internet services ([https://yadi.sk/i/6PT-31-G3EqmHa pdf])
  
==== Анализ кеширования данных в кластерах с различной нагрузкой ====
+
==== 21 марта ====
  
Обычно на каждой машине в составе распределенной файловой системы присутствует локальный кеш данных. Данный кеш должен устойчиво работать при различных типах нагрузки на файловую систему. В частности, кеш должен быть устойчив к "вымыванию" -- вытеснению горячих данных данных при единоразовом чтении крупного объема данных (существенно превышающего объем доступной памяти). В рамках данной работы предлагается проанализировать эффективность различных стратегии кеширования по историческим данным, собранным с реального кластера.
+
Отладка распределенных систем: вывод взаимосвязей событий.
  
=== Остальные темы ===
+
* ''Mace et. al.'' -- Pivot tracing: dynamic causal monitoring for distributed systems ([https://yadi.sk/d/M2KqToyu3EqmX2 pdf])
  
==== Формальная спецификация HDFS ====
+
=== 4 модуль ===
  
'''Руководитель''': Иван Пузыревский
+
==== 10 апреля ====
 +
Сервисы блокировок.
  
HDFS (Hadoop Distributed File System) -- распределенная отказоустойчивая файловая система. В данной работе предлагается разработать и проверить формальную спецификацию системы с помощью [http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html TLA+].
+
* ''Burrows'' -- The Chubby lock service for loosely-coupled distributed systems ([https://yadi.sk/i/YHoCSaAU3Gb8pf pdf])
 +
* ''Hunt et. al.'' -- ZooKeeper: wait-free coordination for Internet-scale systems ([https://yadi.sk/i/NRcFm-uS3Gb8vH pdf])
  
==== Автоматическое определение проблемных узлов кластера ====
+
==== 17 апреля ====
 +
ZooKeeper, продолжение. Реализация примитивов блокировок, семафор, очередей, выбора лидера, двухфазной фиксации транзакций.
  
'''Руководитель''': Павел Сушин
+
==== 21 апреля ====
 +
* ''Tasci et. al'' -- Panopticon: an omniscient lock broker for efficient distributed transactions in the datacenter ([https://yadi.sk/i/c6bJ9kEt3Gb98a pdf])
  
В больших кластерах существенно повышается вероятность деградации одного узла кластера: иногда вследствие неудачно распределившейся нагрузки, иногда вследствие аппаратных сбоев, иногда вследствие программных ошибок. Иногда деградация обусловлена не самим узлом, а проблемами сетевой связности. Обнаруживать проблемные узлы кластера важно для обеспечения превентивной защиты (проблемные узлы чаще выходят из строя) и для уменьшения времени отклика системы (например, не читать данные с таких узлов). В рамках данной работы предлагается разработать метод автоматического определения проблемных узлов кластера на основе доступных системных метрик производительности. Для решения задачи можно  использовать методы машинного обучения.
+
=== Будущие занятия ===
 +
Для справки ниже перечислен предполагаемый список тем для изучения на последующих занятиях. Если у вас есть предложения, что какие работы, темы стоит разобрать на семинаре, то пишите мне на [mailto:sandello@gmail.com sandello@gmail.com].
  
==== Создание имитационных моделей вычислительных ресурсов и распределенных вычислительных инфраструктур ====
+
* P2P (BitTorrent, BitCoin)
'''Руководитель''': Олег Сухорослов
+
* Управление ресурсами (DRF; Borg; Omega)
  
==== Симуляция и сравнительный анализ алгоритмов планирования задач в распределенных вычислительных системах ====
+
== Практические задания ==
'''Руководитель''': Олег Сухорослов
+
  
==== Исследование и экспериментальная оценка технологий распределенных вычислений на основе pilot jobs ====
+
=== Сдача заданий ===
'''Руководитель''': Олег Сухорослов
+
  
==== Использование простаивающих вычислительных ресурсов для распределенных вычислений на базе платформы Everest ====
+
Сдача заданий происходит через Anytask (ссылка: http://anytask.org/course/116 ; инвайт: Q8eM54X). Если инвайт перестает работать / не удается зарегистрироваться -- пишите [http://mailto:sandello@gmail.com мне].
'''Руководитель''': Олег Сухорослов
+
  
==== Реализация универсального вычислительного агента для систем распределенных вычислений ====
+
=== Lamport Mutex ===
'''Руководитель''': Олег Сухорослов
+
  
==== Исследование и реализация методов прямой передачи данных по сети между узлами за NAT и межсетевыми экранами ====
+
В рамках первого практического задания вам предлагается реализовать распределенный алгоритм взаимного исключения, описанный Лампортом в статье ''Time, clocks and the ordering of events in a distributed system'' (см. материалы занятия от 23.09).
'''Руководитель''': Олег Сухорослов
+
 
 +
==== Требования к реализации ====
 +
# Конфигурация конкретного процесса (например, локальный адрес и порт для слушающего сокета, список адресов и портов других процессов, режим работы) указывается через аргументы командной строки.
 +
# Сетевое взаимодействие должно быть вынесено за RPC-слой. RPC-слой вам нужно реализовать самостоятельно. От вас не требуется сверхоптимальный код; от вас требуется создать целостную абстракцию. Клиентский код (использующий RPC-сервис), серверный код (реализующий RPC-сервис), транспортный код (сериализация/десериализация, работа с сетью) должны быть разделены.
 +
# Каждый процесс должен поддерживать логические часы.
 +
# Каждый из процессов должен вести собственный, локальный журнал событий request / acquire / release (запрос на взятие mutex-а, взятие mutex-а, освобождение mutex-а). Каждое событие должно быть аннотировано физическим временем, логическим временем, PID-ом.
 +
# При взятии mutex-а (событие acquire) процесс должен открыть некий специальный файл (например, ~/mutex.txt; путь до файла указывается в аргументах командной строки), вызывать flock(_, LOCK_EX | LOCK_NB), записывать в файл пометку (PID, логическое время взятие mutex-а, логическое время освобождение mutex-а), после чего отпускать (release) mutex.
 +
# Должны поддерживаться два режима работы: ручной, когда взятие mutex-а инициирует пользователь (по команде с stdin), и стрессовый, когда процесс в бесконечном цикле пробует взять mutex без задержек.
 +
# Для реализации можно использовать языки C++, Python, Java, Go.
 +
 
 +
==== Требования к тестированию ====
 +
# Должны быть написаны юнит-тесты на алгоритм взятия mutex-а, подменяющие сетевую имплементацию RPC-сервиса на локальную.
 +
# Должна быть проведена экспериментальная проверка корректности работы в стресс-режиме для 10 запущенных процессов (в случае корректной работы не должно быть ошибок от flock-а на разделяемый файл).
 +
# Должна быть написана утилита анализа локальных логов процессов, проверяющая, что по логическим часам периоды acquire-release не пересекаются, и что для каждого процесса acquire следует строго после request.
 +
 
 +
==== Требования к сдаче ====
 +
При сдаче в Anytask (см. общую часть про сдачу задания) укажите:
 +
* ссылку на github/bitbucket репозиторий;
 +
* ссылки на реализацию алгоритма Лампорта;
 +
* ссылку на реализацию RPC-слоя (где происходит сетевое взаимодействие, где устанавливаются соединения, где происходит серилизация/десериализация вызовов, где происходит регистрация сервисов);
 +
* ссылку на реализацию логических часов;
 +
* ссылку на анализатор локальных логов процессов;
 +
* инструкцию по сборке проекта;
 +
* инструкцию по запуску юнит-тестов;
 +
* инструкцию по запуску стресс-теста с 10 процессами;
 +
* инструкцию по запуску анализатора локальных логов.
 +
 
 +
==== Критерии сдачи ====
 +
Задание считается сданным, если:
 +
* предоставлена реализация алгоритма, удовлетворяющая вышеуказанным требованиям;
 +
* юнит-тесты успешно отрабатывают;
 +
* стресс-тест успешно отрабатывает;
 +
* анализатор локальных логов подтверждает корректность значений логических часов.
 +
 
 +
==== Дополнительные указания ====
 +
* Обычно при имплементации RPC-слоя возникают такие абстракции как стаб (интерфейс, используемый клиентской стороной и реализуемый серверной стороной), сервис (отвечает за маршрутизацию конкретного вызова в конкретный метод языка), сервер (отвечает за сетевое серверное взаимодействие (bind+accept), маршрутизацию вызова в конкретный сервис), канал (создается клиентом, скрывает сетевое взаимодействие (connect), реализует отправку запросов и получение ответов). На клиенте стаб связывается с каналом, на сервере -- с сервисом.
 +
* Учтите, что в данном задании каждый процесс является и клиентом, и сервером одновременно. Чтобы не запутаться, реализуйте сначала простейший ping-pong сервис поверх вашего RPC-слоя, чтобы отработать сетевое взаимодействие.
 +
* Алгоритм Лампорта, как и многие другие распределенные алгоритмы, формулируется в терминах реакции на события (сообщения). Если вы не знаете с чего начать имплементацию, то выделите события и пересылаемые сообщения, участвующие в алгоритме, распишите подробно реакцию на них, обдумайте, какое состояние должно сохраняться между вызовами обработчиков событий.
 +
 
 +
=== Обзор литературы и рецензирование ===
 +
 
 +
==== TL;DR ====
 +
# Определитесь с командой (2-3 человека), запишитесь в табличку: https://docs.google.com/spreadsheets/d/1pfcTgQQt8zFXePhFhFm4xK0gdoGqppzm-rP25d1v_Ug/edit?usp=sharing (первый лист), распределите статьи.
 +
# Напишите обзор по статьям. Отправьте обзор вашим рецензентам.
 +
# Определитесь с рецензируемыми вами работами, запишитесь в той же табличке на втором листе: в строке с вашей фамилией поставьте "X" в колонке с рецензируемой работой (одна работа должна быть из вашей команды, одна -- не из вашей).
 +
# Напишите реценизии. Не забудьте отправить копию авторам обзора.
 +
# Отправьте копию обзора (в Google Document) и копию рецензии (тоже в Google Document) в Anytask.
 +
 
 +
==== Описание задание ====
 +
В рамках данного задания вам нужно изучить несколько работ по интересной вам теме, написать краткий обзор по них, а также отрецензировать обзоры ваших однокурсников. Целей у данного задания две: первая -- научиться искать и разбирать материал по интересующей вас теме, выделять главные аспекты и воссоздавать логику работы; вторая -- научиться критически оценивать представляемые результаты и их аргументацию.
 +
 
 +
Структурно, задание проходит в несколько этапов:
 +
1. выбор работ для изучения,
 +
2. разбиение по минигруппам,
 +
3. изучение работ,
 +
4. написание обзора,
 +
5. рецензирование смежных обзоров.
 +
 
 +
Предполагается, что некоторой фиксированной темы 2-3 человека выбирают себе по 2-3 работы каждый; далее, каждый человек пишет собственный обзор выбранных работ; далее, каждый человек рецензирует 2-3 обзора от своих смежников (один обзор из своей группы + один обзор не из своей группы).
 +
 
 +
Оценка за задание складывается из двух частей -- "зачет//не зачет" за написание собственного обзора и "зачет//не зачет" за рецензирование работ.
 +
 
 +
Далее приведены более подробные пояснения по каждому из этапов.
 +
 
 +
==== Выбор работ для изучения ====
 +
Вы можете, в целом, выбрать любую интересную вам тему, по которой есть публикации за последние 15 лет.
 +
 
 +
Например, можете изучить работы с конференций:
 +
 
 +
# OSDI [https://www.usenix.org/conference/osdi16/program 2016], [https://www.usenix.org/conference/osdi14/technical-sessions 2014], [https://www.usenix.org/conference/osdi12/technical-sessions 2012], ...
 +
# VLDB [http://www.vldb.org/pvldb/vol9.html 2016], [http://www.vldb.org/pvldb/vol8.html 2015], [http://www.vldb.org/pvldb/vol7.html 2014], ...
 +
# SIGMOD/PODS [http://sigmod2016.org/sigmodtoc.html 2016]/ [http://sigmod2016.org/podstoc.html 2016], [http://www.sigmod2015.org/toc_sigmod.shtml 2015]/ [http://www.sigmod2015.org/toc_pods.shtml 2015], [http://www.sigmod2014.org/research_list.shtml 2014]/ [http://www.sigmod2014.org/pods_list.shtml 2014], ...
 +
# EUROSYS [http://eurosys16.doc.ic.ac.uk/program/papers/ 2016], [http://eurosys2015.labri.fr/program/papers/ 2015], [http://eurosys2014.vu.nl/papers/ 2014], ...
 +
# PODC [https://www.podc.org/podc2016/proceedings/ 2016], [https://www.podc.org/podc2015/proceedings/ 2015], [https://www.podc.org/podc2014/2014-proceedings/ 2014], ...
 +
# SOCC [http://acmsocc.github.io/2016/schedule.html 2016], [http://acmsocc.github.io/2015/accepted-papers.html 2015], [https://sites.google.com/site/2014socc/home/program 2014], ...
 +
# SYSTOR [http://www.systor.org/2016/program.html 2016], [http://www.systor.org/2015/program.html 2015], [http://www.systor.org/2014/program.html 2014], ...
 +
# HOTSTORAGE [https://www.usenix.org/conference/hotstorage16/workshop-program 2016], [https://www.usenix.org/conference/hotstorage15/workshop-program 2015], [https://www.usenix.org/conference/hotstorage14/workshop-program 2014], ...
 +
# FAST [https://www.usenix.org/conference/fast16/technical-sessions 2016], [https://www.usenix.org/conference/fast15/technical-sessions 2015], [https://www.usenix.org/conference/fast14/technical-sessions 2014], ...
 +
# ATC [https://www.usenix.org/conference/atc16/technical-sessions 2016], [https://www.usenix.org/conference/atc15/technical-sessions 2015], [https://www.usenix.org/conference/atc14/technical-sessions 2014], ...
 +
 
 +
Поисковик по статьям:
 +
# [http://scholar.google.com Scholar Google]
 +
 
 +
Скомпоновать работы можно из разных соображений:
 +
 
 +
# сравнительный анализ разных подходов,
 +
# детальный углубленный разбор одной из существующих систем,
 +
# вводный обзор по какой-либо тематике.
 +
 
 +
Примеры подборок:
 +
 
 +
# алгоритмы деанонимизации в Tor (выбрать несколько разных методов, выделить, чем они отличаются, сравнить),
 +
# вариации Paxos (Ring Paxos -- с мультикастом для доставки данных, Net Paxos -- с имплементацией на сетевом уровне, Egalitarian Paxos -- для WAN; методы эксплуатируют разные идеи -- выделить какие, зачем, где применимы),
 +
# ослабление требований в Paxos (Flexible Paxos, Ios),
 +
# криптовалюты (BTC-vs-ETH-vs-...),
 +
# gossip-протоколы ("Efficient and Adaptive Epidemic-Style Protocols for Reliable and Scalable Multicast", "Bounded gossip: a gossip protocol for large-scale datacenters"),
 +
# файловая система BetrFS ("BetrFS: A Right-Optimized Write-Optimized File System", "Optimizing Every Operation in a Write-Optimized File System", "File Systems Fated for Senescence? Nonsense, Says Science!").
 +
 
 +
==== Разбиение по минигруппам ====
 +
Одна минигруппа -- это 2-3 человека, которые разбирают 2-3 работы каждый. При этом у каждого в минигруппе хотя бы одна изучаемая работа уникальна.
 +
 
 +
Пример:
 +
# тема -- вариации Paxos; человек 1 -- Paxos Made Simple (базовая работа) + Ring Paxos; человек 2 -- Paxos Made Live + Net Paxos; человек 3 -- Paxos Made Simple + Egalitarian Paxos.
 +
# тема -- BetrFS: человек 1 -- BetrFS + Optimizing Every Opration; человек 2 -- BetrFS + File Systems Faed for Senescence?
 +
 
 +
==== Изучение работ и написание обзора ====
 +
От вас требуется разобраться в работе, определить её актуальность и значимость, выделить основные идеи и результаты работы, сравнить их с альтернативами (если применимо), выделить сильные и слабые стороны работы. Целевой объем обзора -- 2-3 страницы. Критерий хорошего обзора -- что на его основе ваш однокурсник может составить представление об изучаемой области.
 +
 
 +
Примерный список вопросов, которые стоит затронуть в обзоре:
 +
# какая задача решается?
 +
# почему эта задача важна, в чем польза от её решения?
 +
# почему эта задача актуальна, насколько часто она возникает, насколько широко распространена?
 +
# какие были предыдущие попытки решения этой задачи? какие были получены результаты?
 +
# в чем суть, идея предлагаемого решения?
 +
# каковы преимущества и недостатки предлагаемого решения по отношению к решаемой задачи?
 +
# каковы преимущества и недостатки предлагаемого решения по сравнению с другими решениями?
 +
# какие экспериментальные результаты получены?
 +
# какие аспекты работы хорошо/плохо проработаны?
 +
 
 +
При написании обзора следует не просто слепо копировать фрагменты оригинальной работы, но и сохранять логику работы: не пропускать аргументы, обоснования предлагаемых решений.
 +
 
 +
==== Рецензирование смежных обзоров  ====
 +
Вам нужно отрецензировать обзоры своих одногруппников в минигруппе, а также один из обзоров одногруппников в учебной группе. В рецензии вам нужно оценить, насколько аргументировано и последовательно излагается материал, насколько понятны переходы и выводы в работе.
 +
 
 +
Полученную рецензию не забудьте отправить автору обзора.
 +
 
 +
==== Требования к сдаче ====
 +
 
 +
При сдаче в Anytask (см. общую часть про сдачу задания) отправьте ссылку на Google Document с обзором и Google Document с рецензией. Требования про Google Document обусловлено удобством комментирования и рецензирования текста.
 +
 
 +
== Курсовые работы ==
  
==== Исследование и экспериментальная оценка методов обеспечения отказоустойчивости MPI-приложений ====
+
[http://wiki.cs.hse.ru/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BA%D1%83%D1%80%D1%81%D0%BE%D0%B2%D1%8B%D1%85_%D1%80%D0%B0%D0%B1%D0%BE%D1%82._%D0%A0%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B Список курсовых работ]
'''Руководитель''': Олег Сухорослов
+

Текущая версия на 13:00, 5 июня 2017

Содержание

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

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

Оценка

Оценка за НИС складывается из двух частей: оценки за практические задания и общей оценки.

S = S_tasks + S_general

Практических заданий -- две штуки: одно на программирование, одно на работу с текстом. За первое задание можно получить максимум 5 баллов, за второе максимум 3 балла. Сдача после дедлайна штрафуется. За каждый просроченный модуль -- минус балл. Таким образом, максимум за первое задание при сдаче во втором модуле можно получить 4 балла, в третьем -- 3, в четвертом -- 2.

Общая оценка складывается из трех частей: посещаемости, участия в семинарах и экзамена. Суммарно общая оценка ограничена сверху 3 баллами. Посещаемость оценивается в 0.25 балла за каждый модуль, если вы посетили более половины занятий в данном модуле. Активность -- до 0.50 балла каждый модуль по усмотрению преподавателя. Экзамен -- до 2.00 баллов (4*0.50).

S_general = min(3.00, S_attendance + S_participation + S_exam); S_attendance <= 1.00; S_participation <= 2.00; S_exam <= 2.00

Текущая таблица с оценками доступна по ссылке.

Занятия

1 модуль

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).

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)

30 сентября

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

Материалы:

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

7 октября

Ослабление модели памяти. Слабоконсистентные хранилища на примере Bayou.

Материалы:

  • Terry et. al. -- Managing update conflicts in Bayou, a weakly connected replicated storage system (pdf)

14 октября

Занятия не будет.

21 октября

Детальный рассказ о предлагаемых курсовых работах от руководителей.

2 модуль

4 ноября

Занятия не будет.

11 ноября

Задача распределенного консенсуса. Paxos.

18 ноября

Распределенный консенсус, продолжение. Viewstamped replication.

  • Liskov, Cowling -- Viewstamped replication revisited (pdf)
  • Oki, Liskov -- Viewstamped replication: a new primary copy method to support highly available distributed systems (pdf)

25 ноября

Распределенный консенсус, продолжение. Raft.

  • Ongaro, Ousterhout -- In search of understandable consensus algorithm (pdf)
  • (по желанию) Howard et. al. -- Raft refloated: do we have consensus? (pdf)
  • Ousterhout -- Raft lecture (video; 1.0ч)

2 декабря

Распределенный консенсус, завершение.

  • Chandra et. al. -- Paxos made live: an engineering perspective (pdf)
  • van Renesse et. al. -- Vive la différence: Paxos vs. Viewstamped replication vs. Zab (pdf)
  • (по желанию) Junqueira et. al. -- Zab: high performance broadcast for primary-backup systems (pdf)
  • (по желанию) Medeiros -- ZooKeeper's atomic broadcast protocol: theory and practice (pdf)

9 декабря

CRDTs: счетчики (G, PN, NN), множества (G, 2P, U, LWW, PN, OR).

  • Shapiro et. al. -- A comprehensive study of convergent and commutative replicated data types (pdf)

16 декабря

CRDTs: списочные структуры.

  • Nedelec et. al. -- LSEQ: an adaptive structure for sequences in distributed collaborative editing (pdf)

3 модуль

24 января

Иерархические блокировки.

  • Grey et. al. -- Granularity of locks in a shared database (pdf)

31 января

Уровни изоляции. Классификация через аномалии.

  • Bernson et. al. -- A critique of ANSI SQL isolation levels (pdf)

7 февраля

Уровни изоляции. Формальная модель.

  • Adya, Liskov, O'Neil -- Generalized isolation level definitions (pdf)

14 февраля

Уровни изоляции & управление одновременным исполнением транзакций.

  • Xie et. al. -- High-performance ACID via modular concurrency control (pdf)

21 февраля

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

28 февраля

Окончание уровней изоляции (закончили разбор материалов с предыдущих семинаров).

7 марта

Отладка распределенных систем: трассировка сетевого взаимодействия.

  • Fonseca et. al. -- X-Trace: a pervasive network tracing framework (pdf)
  • Sigelman et. al. -- Dapper, a large-scale distributed systems tracing infrastructure (pdf)

14 марта

Отладка распределенных систем: отладка производительности, вывод взаимосвязей событий.

  • Barham et. al. -- Magpie: online modelling and performance-aware systems (pdf)
  • Chow et. al. -- The mystery machine: end-to-end performance analysis of large-scale internet services (pdf)

21 марта

Отладка распределенных систем: вывод взаимосвязей событий.

  • Mace et. al. -- Pivot tracing: dynamic causal monitoring for distributed systems (pdf)

4 модуль

10 апреля

Сервисы блокировок.

  • Burrows -- The Chubby lock service for loosely-coupled distributed systems (pdf)
  • Hunt et. al. -- ZooKeeper: wait-free coordination for Internet-scale systems (pdf)

17 апреля

ZooKeeper, продолжение. Реализация примитивов блокировок, семафор, очередей, выбора лидера, двухфазной фиксации транзакций.

21 апреля

  • Tasci et. al -- Panopticon: an omniscient lock broker for efficient distributed transactions in the datacenter (pdf)

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

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

  • P2P (BitTorrent, BitCoin)
  • Управление ресурсами (DRF; Borg; Omega)

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

Сдача заданий

Сдача заданий происходит через Anytask (ссылка: http://anytask.org/course/116 ; инвайт: Q8eM54X). Если инвайт перестает работать / не удается зарегистрироваться -- пишите мне.

Lamport Mutex

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

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

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

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

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

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

При сдаче в Anytask (см. общую часть про сдачу задания) укажите:

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

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

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

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

Дополнительные указания

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

Обзор литературы и рецензирование

TL;DR

  1. Определитесь с командой (2-3 человека), запишитесь в табличку: https://docs.google.com/spreadsheets/d/1pfcTgQQt8zFXePhFhFm4xK0gdoGqppzm-rP25d1v_Ug/edit?usp=sharing (первый лист), распределите статьи.
  2. Напишите обзор по статьям. Отправьте обзор вашим рецензентам.
  3. Определитесь с рецензируемыми вами работами, запишитесь в той же табличке на втором листе: в строке с вашей фамилией поставьте "X" в колонке с рецензируемой работой (одна работа должна быть из вашей команды, одна -- не из вашей).
  4. Напишите реценизии. Не забудьте отправить копию авторам обзора.
  5. Отправьте копию обзора (в Google Document) и копию рецензии (тоже в Google Document) в Anytask.

Описание задание

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

Структурно, задание проходит в несколько этапов: 1. выбор работ для изучения, 2. разбиение по минигруппам, 3. изучение работ, 4. написание обзора, 5. рецензирование смежных обзоров.

Предполагается, что некоторой фиксированной темы 2-3 человека выбирают себе по 2-3 работы каждый; далее, каждый человек пишет собственный обзор выбранных работ; далее, каждый человек рецензирует 2-3 обзора от своих смежников (один обзор из своей группы + один обзор не из своей группы).

Оценка за задание складывается из двух частей -- "зачет//не зачет" за написание собственного обзора и "зачет//не зачет" за рецензирование работ.

Далее приведены более подробные пояснения по каждому из этапов.

Выбор работ для изучения

Вы можете, в целом, выбрать любую интересную вам тему, по которой есть публикации за последние 15 лет.

Например, можете изучить работы с конференций:

  1. OSDI 2016, 2014, 2012, ...
  2. VLDB 2016, 2015, 2014, ...
  3. SIGMOD/PODS 2016/ 2016, 2015/ 2015, 2014/ 2014, ...
  4. EUROSYS 2016, 2015, 2014, ...
  5. PODC 2016, 2015, 2014, ...
  6. SOCC 2016, 2015, 2014, ...
  7. SYSTOR 2016, 2015, 2014, ...
  8. HOTSTORAGE 2016, 2015, 2014, ...
  9. FAST 2016, 2015, 2014, ...
  10. ATC 2016, 2015, 2014, ...

Поисковик по статьям:

  1. Scholar Google

Скомпоновать работы можно из разных соображений:

  1. сравнительный анализ разных подходов,
  2. детальный углубленный разбор одной из существующих систем,
  3. вводный обзор по какой-либо тематике.

Примеры подборок:

  1. алгоритмы деанонимизации в Tor (выбрать несколько разных методов, выделить, чем они отличаются, сравнить),
  2. вариации Paxos (Ring Paxos -- с мультикастом для доставки данных, Net Paxos -- с имплементацией на сетевом уровне, Egalitarian Paxos -- для WAN; методы эксплуатируют разные идеи -- выделить какие, зачем, где применимы),
  3. ослабление требований в Paxos (Flexible Paxos, Ios),
  4. криптовалюты (BTC-vs-ETH-vs-...),
  5. gossip-протоколы ("Efficient and Adaptive Epidemic-Style Protocols for Reliable and Scalable Multicast", "Bounded gossip: a gossip protocol for large-scale datacenters"),
  6. файловая система BetrFS ("BetrFS: A Right-Optimized Write-Optimized File System", "Optimizing Every Operation in a Write-Optimized File System", "File Systems Fated for Senescence? Nonsense, Says Science!").

Разбиение по минигруппам

Одна минигруппа -- это 2-3 человека, которые разбирают 2-3 работы каждый. При этом у каждого в минигруппе хотя бы одна изучаемая работа уникальна.

Пример:

  1. тема -- вариации Paxos; человек 1 -- Paxos Made Simple (базовая работа) + Ring Paxos; человек 2 -- Paxos Made Live + Net Paxos; человек 3 -- Paxos Made Simple + Egalitarian Paxos.
  2. тема -- BetrFS: человек 1 -- BetrFS + Optimizing Every Opration; человек 2 -- BetrFS + File Systems Faed for Senescence?

Изучение работ и написание обзора

От вас требуется разобраться в работе, определить её актуальность и значимость, выделить основные идеи и результаты работы, сравнить их с альтернативами (если применимо), выделить сильные и слабые стороны работы. Целевой объем обзора -- 2-3 страницы. Критерий хорошего обзора -- что на его основе ваш однокурсник может составить представление об изучаемой области.

Примерный список вопросов, которые стоит затронуть в обзоре:

  1. какая задача решается?
  2. почему эта задача важна, в чем польза от её решения?
  3. почему эта задача актуальна, насколько часто она возникает, насколько широко распространена?
  4. какие были предыдущие попытки решения этой задачи? какие были получены результаты?
  5. в чем суть, идея предлагаемого решения?
  6. каковы преимущества и недостатки предлагаемого решения по отношению к решаемой задачи?
  7. каковы преимущества и недостатки предлагаемого решения по сравнению с другими решениями?
  8. какие экспериментальные результаты получены?
  9. какие аспекты работы хорошо/плохо проработаны?

При написании обзора следует не просто слепо копировать фрагменты оригинальной работы, но и сохранять логику работы: не пропускать аргументы, обоснования предлагаемых решений.

Рецензирование смежных обзоров

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

Полученную рецензию не забудьте отправить автору обзора.

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

При сдаче в Anytask (см. общую часть про сдачу задания) отправьте ссылку на Google Document с обзором и Google Document с рецензией. Требования про Google Document обусловлено удобством комментирования и рецензирования текста.

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

Список курсовых работ