2020/2021

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

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

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

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

Когда читается: 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 * Самостоятельная работа

Список литературы

Рекомендуемая основная литература

• Preguiça, N., Baquero, C., & Shapiro, M. (2018). Conflict-free Replicated Data Types (CRDTs). https://doi.org/10.1007/978-3-319-63962-8\_185-1
• Метрики репутации: модели и алгоритмы построения открытых информационных сред : автореф. дис. ... канд. физико-математических наук: 05.13.18, Грищенко, В. С., 2007

Рекомендуемая дополнительная литература

• Leslie Lamport. (1978). Time, Clocks, and the Ordering of Events in a Distributed System. Http://Portal.Acm.Org/Ft_gateway.Cfm?Id=359563&type=pdf&coll=GUIDE&dl=GUIDE&CFID=819630&CFTOKEN=77629298.