НИС Распределенные системы (осень 2016) — различия между версиями
Smx (обсуждение | вклад) (Список курсовых работ заменен на ссылку.) |
Sandello (обсуждение | вклад) |
||
(не показано 7 промежуточных версии этого же участника) | |||
Строка 8: | Строка 8: | ||
''S = S_tasks + S_general'' | ''S = S_tasks + S_general'' | ||
− | Практических заданий -- | + | Практических заданий -- две штуки: одно на программирование, одно на работу с текстом. За первое задание можно получить максимум 5 баллов, за второе максимум 3 балла. Сдача после дедлайна штрафуется. За каждый просроченный модуль -- минус балл. Таким образом, максимум за первое задание при сдаче во втором модуле можно получить 4 балла, в третьем -- 3, в четвертом -- 2. |
− | + | Общая оценка складывается из трех частей: посещаемости, участия в семинарах и экзамена. Суммарно общая оценка ограничена сверху 3 баллами. Посещаемость оценивается в 0.25 балла за каждый модуль, если вы посетили более половины занятий в данном модуле. Активность -- до 0.50 балла каждый модуль по усмотрению преподавателя. Экзамен -- до 2.00 баллов (4*0.50). | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | Общая оценка складывается из трех частей: посещаемости, участия в семинарах и экзамена. Суммарно общая оценка ограничена сверху 3 | + | |
''S_general = min(3.00, S_attendance + S_participation + S_exam); S_attendance <= 1.00; S_participation <= 2.00; S_exam <= 2.00'' | ''S_general = min(3.00, S_attendance + S_participation + S_exam); S_attendance <= 1.00; S_participation <= 2.00; S_exam <= 2.00'' | ||
Строка 188: | Строка 173: | ||
* ''Mace et. al.'' -- Pivot tracing: dynamic causal monitoring for distributed systems ([https://yadi.sk/d/M2KqToyu3EqmX2 pdf]) | * ''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]) | ||
=== Будущие занятия === | === Будущие занятия === | ||
Строка 196: | Строка 195: | ||
== Практические задания == | == Практические задания == | ||
+ | |||
+ | === Сдача заданий === | ||
+ | |||
+ | Сдача заданий происходит через Anytask (ссылка: http://anytask.org/course/116 ; инвайт: Q8eM54X). Если инвайт перестает работать / не удается зарегистрироваться -- пишите [http://mailto:sandello@gmail.com мне]. | ||
=== Lamport Mutex === | === Lamport Mutex === | ||
− | В рамках первого практического задания вам предлагается реализовать распределенный алгоритм взаимного исключения, описанный Лампортом в статье ''Time, clocks and the ordering of events in a distributed system'' (см. материалы занятия от 23.09) | + | В рамках первого практического задания вам предлагается реализовать распределенный алгоритм взаимного исключения, описанный Лампортом в статье ''Time, clocks and the ordering of events in a distributed system'' (см. материалы занятия от 23.09). |
==== Требования к реализации ==== | ==== Требования к реализации ==== | ||
Строка 216: | Строка 219: | ||
==== Требования к сдаче ==== | ==== Требования к сдаче ==== | ||
− | + | При сдаче в Anytask (см. общую часть про сдачу задания) укажите: | |
* ссылку на github/bitbucket репозиторий; | * ссылку на github/bitbucket репозиторий; | ||
* ссылки на реализацию алгоритма Лампорта; | * ссылки на реализацию алгоритма Лампорта; | ||
Строка 238: | Строка 241: | ||
* Учтите, что в данном задании каждый процесс является и клиентом, и сервером одновременно. Чтобы не запутаться, реализуйте сначала простейший ping-pong сервис поверх вашего RPC-слоя, чтобы отработать сетевое взаимодействие. | * Учтите, что в данном задании каждый процесс является и клиентом, и сервером одновременно. Чтобы не запутаться, реализуйте сначала простейший 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 Список курсовых работ] | [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.
- Lamport -- Paxos made simple (pdf)
- (по желанию) Lamport -- The part-time parliament (pdf; история публикации)
- Ousterhout -- Paxos lecture (video; 1.0ч)
- Guerraoui -- Paxos lecture (video; 0.5ч)
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).
Требования к реализации
- Конфигурация конкретного процесса (например, локальный адрес и порт для слушающего сокета, список адресов и портов других процессов, режим работы) указывается через аргументы командной строки.
- Сетевое взаимодействие должно быть вынесено за 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 2016, 2014, 2012, ...
- VLDB 2016, 2015, 2014, ...
- SIGMOD/PODS 2016/ 2016, 2015/ 2015, 2014/ 2014, ...
- EUROSYS 2016, 2015, 2014, ...
- PODC 2016, 2015, 2014, ...
- SOCC 2016, 2015, 2014, ...
- SYSTOR 2016, 2015, 2014, ...
- HOTSTORAGE 2016, 2015, 2014, ...
- FAST 2016, 2015, 2014, ...
- ATC 2016, 2015, 2014, ...
Поисковик по статьям:
Скомпоновать работы можно из разных соображений:
- сравнительный анализ разных подходов,
- детальный углубленный разбор одной из существующих систем,
- вводный обзор по какой-либо тематике.
Примеры подборок:
- алгоритмы деанонимизации в 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 обусловлено удобством комментирования и рецензирования текста.