CRDT: Полностью доступные распределённые системы

2020/2021

Статус: Дисциплина общефакультетского пула

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 4 модуль

Язык: русский

Кредиты: 3

Контактные часы: 44

Полная версия программы учебной дисциплины

Аннотация

Теория и практика построения высокодоступных и полностью доступных распределённых систем. Типы данных и алгоритмы CRDT как основа архитектуры доступной системы. Алгебра встречается с кодингом. Вы овладеете методами проектирования распределённых систем, сфокусированных на доступности и качестве сервиса для конечного пользователя. Научитесь создавать инструменты коллаборативного редактирования документов и мобильные приложения, продолжающие корректно работать в офлайне.

Цель освоения дисциплины

Ознакомление студентов с алгоритмами бесконфликтной репликации данных.
Ознакомление студентов с методами проектирования доступных распределённых систем.
Формирование у студентов навыков доказательства согласованности в конечном счёте и доступности распределённых систем.
Формирование у студентов навыков проектирования доступных распределённых систем.

Планируемые результаты обучения

Иметь понятие о согласованности, доступности, устойчивости к разделению. Знать теорему Брюэра и принцип PACELC. Иметь понятие о строгой согласованности в конечном счёте. Знать принципы ведения история совместных редакторов. Знать принцип преобразования операций (operational transformation).
Знать алгебраические конструкции: полугруппа, моноид, полурешётка. Знать определение полурешётки через операцию и отношение.
Иметь понятие о причинной связи и отношении причинности. Знать определение времени и часов Лэмпорта, гибридных часов. Уметь создавать уникальные идентификаторы, в том числе по RFC 4122.
Знать определение state-based CRDT: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Знать определение op-based CRDT: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Знать определение Replicated Object Notation и журнальной модели данных.
Уметь представлять множество с помощью Observed-Removed Set. State-based и op-based подходы.
Уметь представлять словари и объекты на основе LWW и OR-set.
Уметь представлять произвольные последовательности и текст с помощью Replicated Growable Array с точки зрения state-base и op-based. Знать типичные проблемы при работе с текстовыми данными
Уметь представлять последовательности с помощью Causal Trees.
Уметь проектировать распределённое полностью доступное приложение.
Знать недостатки CRDT и способы их обойти.

Содержание учебной дисциплины

Согласованность и доступность
Понятие о согласованности, доступности, устойчивости к разделению; теорема Брюэра и принцип PACELC; понятие о строгой согласованности в конечном счёте; принципы ведения история совместных редакторов; принцип преобразования операций (operational transformation).
Алгебра
Алгебраические конструкции: полугруппа, моноид, полурешётка; определение полурешётки через операцию и отношение.
Причинная связь
Понятие о причинной связи и отношении причинности; определение времени и часов Лэмпорта, гибридных часов; создавать уникальные идентификаторы, в том числе по RFC 4122.
State-based CRDT
Определение state-based CRDT: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Op-based CRDT
Определение op-based CRDT: LWW, max/min, G-counter, PN-counter, G-set, произведение типов.
Replicated Object Notation
Определение Replicated Object Notation и журнальной модели данных.
Множества
Представление множество с помощью Observed-Removed Set. State-based и op-based подходы.
Словари и объекты
Словари и объекты на основе LWW и OR-set
Последовательности
Представление произвольные последовательности и текст с помощью Replicated Growable Array с точки зрения state-base и op-based; типичные проблемы при работе с текстовыми данными.
Причинные деревья
Представление последовательности с помощью Causal Trees.
Проектирование приложения
Проектирование распределённого полностью доступного приложения.
Недостатки CRDT
Недостатки CRDT и способы их обойти.

Элементы контроля

Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа
Самостоятельная работа

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа + 0.1 * Самостоятельная работа

Программа дисциплины