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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Требования к сдаче)
(Обзор литературы и рецензирование)
Строка 238: Строка 238:
 
* Алгоритм Лампорта, как и многие другие распределенные алгоритмы, формулируется в терминах реакции на события (сообщения). Если вы не знаете с чего начать имплементацию, то выделите события и пересылаемые сообщения, участвующие в алгоритме, распишите подробно реакцию на них, обдумайте, какое состояние должно сохраняться между вызовами обработчиков событий.
 
* Алгоритм Лампорта, как и многие другие распределенные алгоритмы, формулируется в терминах реакции на события (сообщения). Если вы не знаете с чего начать имплементацию, то выделите события и пересылаемые сообщения, участвующие в алгоритме, распишите подробно реакцию на них, обдумайте, какое состояние должно сохраняться между вызовами обработчиков событий.
  
=== Обзор литературы и рецензирование ===
+
[[Заголовок ссылки]]=== Обзор литературы и рецензирование ===
  
 
==== TL;DR ====
 
==== TL;DR ====
1. Определитесь с командой (2-3 человека), запишитесь в табличку: https://docs.google.com/spreadsheets/d/1pfcTgQQt8zFXePhFhFm4xK0gdoGqppzm-rP25d1v_Ug/edit?usp=sharing , распределите статьи.
+
# Определитесь с командой (2-3 человека), запишитесь в табличку: https://docs.google.com/spreadsheets/d/1pfcTgQQt8zFXePhFhFm4xK0gdoGqppzm-rP25d1v_Ug/edit?usp=sharing (первый лист), распределите статьи.
2. Напишите обзор по статьям.  
+
# Напишите обзор по статьям.  
3. Напишите одну рецензию на обзор вашего однокомандника, одну рецензию на обзор вашего одногруппника (не из вашей команды).
+
# Определитесь с рецензируемыми вами работами, запишитесь в той же табличке на втором листе: в строке с вашей фамилией поставьте "X" в колонке с рецензируемой работой (одна работа должна быть из вашей команды, одна -- не из вашей).
  
 
==== Описание задание ====
 
==== Описание задание ====
Строка 255: Строка 255:
 
5. рецензирование смежных обзоров.
 
5. рецензирование смежных обзоров.
  
Предполагается, что некоторой фиксированной темы 2-3 человека выбирают себе по 2-3 работы каждый; далее, каждый человек пишет собственный обзор выбранных работ; далее, каждый человек рецензирует 3-4 обзора от своих смежников (все обзоры по фиксированной теме + хотя бы один обзор не по теме).
+
Предполагается, что некоторой фиксированной темы 2-3 человека выбирают себе по 2-3 работы каждый; далее, каждый человек пишет собственный обзор выбранных работ; далее, каждый человек рецензирует 2-3 обзора от своих смежников (один обзор из своей группы + один обзор не из своей группы).
  
 
Оценка за задание складывается из двух частей -- "зачет//не зачет" за написание собственного обзора и "зачет//не зачет" за рецензирование работ.
 
Оценка за задание складывается из двух частей -- "зачет//не зачет" за написание собственного обзора и "зачет//не зачет" за рецензирование работ.

Версия 12:46, 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)

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

Lamport Mutex

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

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

  1. Конфигурация конкретного процесса (например, локальный адрес и порт для слушающего сокета, список адресов и портов других процессов, режим работы) указывается через аргументы командной строки.
  2. Сетевое взаимодействие должно быть вынесено за RPC-слой. RPC-слой вам нужно реализовать самостоятельно. От вас не требуется сверхоптимальный код; от вас требуется создать целостную абстракцию. Клиентский код (использующий RPC-сервис), серверный код (реализующий RPC-сервис), транспортный код (сериализация/десериализация, работа с сетью) должны быть разделены.
  3. Каждый процесс должен поддерживать логические часы.
  4. Каждый из процессов должен вести собственный, локальный журнал событий request / acquire / release (запрос на взятие mutex-а, взятие mutex-а, освобождение mutex-а). Каждое событие должно быть аннотировано физическим временем, логическим временем, PID-ом.
  5. При взятии mutex-а (событие acquire) процесс должен открыть некий специальный файл (например, ~/mutex.txt; путь до файла указывается в аргументах командной строки), вызывать flock(_, LOCK_EX | 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 (ссылка: http://anytask.org/course/116 ; инвайт: Q8eM54X). При сдаче укажите:

  • ссылку на 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" в колонке с рецензируемой работой (одна работа должна быть из вашей команды, одна -- не из вашей).

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

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

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

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

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

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

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

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

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

  1. OSDI [2016](https://www.usenix.org/conference/osdi16/program), [2014](https://www.usenix.org/conference/osdi14/technical-sessions), [2012](https://www.usenix.org/conference/osdi12/technical-sessions), ...
  2. VLDB [2016](http://www.vldb.org/pvldb/vol9.html), [2015](http://www.vldb.org/pvldb/vol8.html), [2014](http://www.vldb.org/pvldb/vol7.html), ...
  3. SIGMOD/PODS [2016](http://sigmod2016.org/sigmodtoc.html)/ [2016](http://sigmod2016.org/podstoc.html), [2015](http://www.sigmod2015.org/toc_sigmod.shtml)/ [2015](http://www.sigmod2015.org/toc_pods.shtml), [2014](http://www.sigmod2014.org/research_list.shtml)/ [2014](http://www.sigmod2014.org/pods_list.shtml), ...
  4. EUROSYS [2016](http://eurosys16.doc.ic.ac.uk/program/papers/), [2015](http://eurosys2015.labri.fr/program/papers/), [2014](http://eurosys2014.vu.nl/papers/), ...
  5. PODC [2016](https://www.podc.org/podc2016/proceedings/), [2015](https://www.podc.org/podc2015/proceedings/), [2014](https://www.podc.org/podc2014/2014-proceedings/), ...
  6. SOCC [2016](http://acmsocc.github.io/2016/schedule.html), [2015](http://acmsocc.github.io/2015/accepted-papers.html), [2014](https://sites.google.com/site/2014socc/home/program), ...
  7. SYSTOR [2016](http://www.systor.org/2016/program.html), [2015](http://www.systor.org/2015/program.html), [2014](http://www.systor.org/2014/program.html), ...
  8. HOTSTORAGE [2016](https://www.usenix.org/conference/hotstorage16/workshop-program), [2015](https://www.usenix.org/conference/hotstorage15/workshop-program), [2014](https://www.usenix.org/conference/hotstorage14/workshop-program), ...
  9. FAST [2016](https://www.usenix.org/conference/fast16/technical-sessions), [2015](https://www.usenix.org/conference/fast15/technical-sessions), [2014](https://www.usenix.org/conference/fast14/technical-sessions), ...
  10. ATC [2016](https://www.usenix.org/conference/atc16/technical-sessions), [2015](https://www.usenix.org/conference/atc15/technical-sessions), [2014](https://www.usenix.org/conference/atc14/technical-sessions), ...

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

  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. какие аспекты работы хорошо/плохо проработаны?

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

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

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

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

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