НИС Распределенные системы (осень 2016)
Содержание
Информация про семинар
В рамках научно-исследовательского семинара по распределенным системам изучаются основные понятия, принципы и результаты предметной области.
Оценка
Оценка за НИС складывается из двух частей: оценки за практические задания и общей оценки.
S = S_tasks + S_general
Практических заданий -- четыре штуки; одно задание в один учебный модуль. За каждое задание можно получить максимум 1.75 балла. Сдача после дедлайна штрафуется (-0.50, -1.00, -1.50) за каждый пропущенный дедлайн. К примеру, если первое задание сдано после дедлайна первого задания, но до дедлайна второго задания, то штраф составляет 0.50 балла. Если первое задание сдано после дедлайна второго задания, но до дедлайна третьего задания, то штраф составляет 1.00 балл. Если первое задание сдано после дедлайна третьего задания, то штраф составляет 1.50 балла.
S_tasks = t1 + t2 + t3 + t4 <= 7.00
| <= d1 | <= d2 | <= d3 | <= d4 | |
| max t1 | 1.75 | 1.25 | 0.75 | 0.25 |
| max t2 | – | 1.75 | 1.25 | 0.75 |
| max t3 | – | – | 1.75 | 1.25 |
| max t4 | – | – | – | 1.75 |
Общая оценка складывается из трех частей: посещаемости, участия в семинарах и экзамена. Суммарно общая оценка ограничена сверху 3.00 баллами. Посещаемость оценивается в 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)
Будущие занятия
Для справки ниже перечислен предполагаемый список тем для изучения на последующих занятиях. Если у вас есть предложения, что какие работы, темы стоит разобрать на семинаре, то пишите мне на 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.
Требования к реализации
- Конфигурация конкретного процесса (например, локальный адрес и порт для слушающего сокета, список адресов и портов других процессов, режим работы) указывается через аргументы командной строки.
- Сетевое взаимодействие должно быть вынесено за 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 (ссылка: http://anytask.org/course/116 ; инвайт: oMUmkee). При сдаче укажите:
- ссылку на github/bitbucket репозиторий;
- ссылки на реализацию алгоритма Лампорта;
- ссылку на реализацию RPC-слоя (где происходит сетевое взаимодействие, где устанавливаются соединения, где происходит серилизация/десериализация вызовов, где происходит регистрация сервисов);
- ссылку на реализацию логических часов;
- ссылку на анализатор локальных логов процессов;
- инструкцию по сборке проекта;
- инструкцию по запуску юнит-тестов;
- инструкцию по запуску стресс-теста с 10 процессами;
- инструкцию по запуску анализатора локальных логов.
Критерии сдачи
Задание считается сданным, если:
- предоставлена реализация алгоритма, удовлетворяющая вышеуказанным требованиям;
- юнит-тесты успешно отрабатывают;
- стресс-тест успешно отрабатывает;
- анализатор локальных логов подтверждает корректность значений логических часов.
Дополнительные указания
- Обычно при имплементации RPC-слоя возникают такие абстракции как стаб (интерфейс, используемый клиентской стороной и реализуемый серверной стороной), сервис (отвечает за маршрутизацию конкретного вызова в конкретный метод языка), сервер (отвечает за сетевое серверное взаимодействие (bind+accept), маршрутизацию вызова в конкретный сервис), канал (создается клиентом, скрывает сетевое взаимодействие (connect), реализует отправку запросов и получение ответов). На клиенте стаб связывается с каналом, на сервере -- с сервисом.
- Учтите, что в данном задании каждый процесс является и клиентом, и сервером одновременно. Чтобы не запутаться, реализуйте сначала простейший ping-pong сервис поверх вашего RPC-слоя, чтобы отработать сетевое взаимодействие.
- Алгоритм Лампорта, как и многие другие распределенные алгоритмы, формулируется в терминах реакции на события (сообщения). Если вы не знаете с чего начать имплементацию, то выделите события и пересылаемые сообщения, участвующие в алгоритме, распишите подробно реакцию на них, обдумайте, какое состояние должно сохраняться между вызовами обработчиков событий.
