imported>Sandello: Migrated current public revision from wiki.cs.hse.ru

2017-06-05T10:00:19Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

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

=== Оценка ===

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

''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 по ссылке].

== Занятия ==

=== 1 модуль ===

==== 2 сентября ====
Вводное занятие.

Материалы:
* ''Mockapetris, Dunlap'' -- Development of the domain name system ([https://yadi.sk/i/hSHHyuoUv9Xsk pdf])

==== 9 сентября ====
'''Занятия не будет'''.

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

Материалы:
* ''Google Code University'' -- Introduction to Distributed Systems Design ([https://yadi.sk/i/qVqtGXs4v9YEy pdf])
* ''Birrell, Nelson'' -- Implementing remote procedure calls ([https://yadi.sk/i/L_t0OemAv9Yzc pdf])
* ''Eriksen'' -- Your server as a function ([https://yadi.sk/i/2lFIzNyIv9YGT pdf])
* (по желанию) ''Liskov'' -- Promises: linguistic support for efficient asynchronous procedure calls in distributed systems ([https://yadi.sk/i/nxcDLp4yv9YG4 pdf])
* (по желанию) 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 сентября ====
Время, часы, синхронизация событий.

Материалы:
* ''Lamport'' -- Time, clocks and the ordering of events in a distributed system ([https://yadi.sk/i/0cE6EdG5vN5mr pdf])
* ''Fidge'' -- Timestamps in message-passing systems that preserve the partial ordering ([https://yadi.sk/i/LyhtLfOMvN64M pdf])
* ''Mills'' -- Internet time synchronization: the network time protocol ([https://yadi.sk/i/PdXX6TO2vN6Bw pdf])

==== 30 сентября ====

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

Материалы:
* ''Li, Hudak'' -- Memory coherency in shared virtual memory systems ([https://yadi.sk/i/gXssi_hRvjUY6 pdf])

==== 7 октября ====

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

Материалы:
* ''Terry et. al.'' -- Managing update conflicts in Bayou, a weakly connected replicated storage system ([https://yadi.sk/i/Gxu0RvtOw8inm pdf])

==== 14 октября ====

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

==== 21 октября ====

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

=== 2 модуль ===

==== 4 ноября ====

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

==== 11 ноября ====

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

* ''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 ноября ====

Распределенный консенсус, продолжение. 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])

==== 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ч)

==== 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 декабря ====

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

==== 16 декабря ====

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

* ''Nedelec et. al.'' -- LSEQ: an adaptive structure for sequences in distributed collaborative editing ([https://yadi.sk/i/1te0_h1S32UG3G pdf])

=== 3 модуль ===

==== 24 января ====

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

* ''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])

==== 7 февраля ====

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

* ''Adya, Liskov, O'Neil'' -- Generalized isolation level definitions ([https://yadi.sk/i/kTCgW3Jy3Aivtb pdf])

==== 14 февраля ====

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

* ''Xie et. al.'' -- High-performance ACID via modular concurrency control ([https://yadi.sk/i/JYQeEg_63DJ9cR pdf])

==== 21 февраля ====

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

==== 28 февраля ====

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

==== 7 марта ====

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

* ''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])

==== 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])

=== 4 модуль ===

==== 10 апреля ====
Сервисы блокировок.

* ''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)

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

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

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

=== Lamport Mutex ===

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

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

[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 Список курсовых работ]

НИС Распределенные системы (осень 2016) - История изменений

imported>Sandello: Migrated current public revision from wiki.cs.hse.ru