Literature

Методы использования СУБД в интернет-приложениях, Техносфера Mail.Ru, 2014 г.

Курс лекций разделен на 4 части. В конце каждой части проводится коллоквиум.

Структуры данных и алгоритмов для двухуровневой памяти

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

   • B-деревья
   • Инвертированные списки
   • Многопроходная сортировка слиянием
   • Стоимостная модель DAM

   Литература:

   • The input/output complexity of sorting and related problems by Aggarwal, Vitter
   • The Ubiquitous B-tree by Douglas Comer
   • Data Structures and Algorithms for Big Databases by Bender, Kuszmaul

2. Современные специализированные алгоритмы хранения данных в двухуровневой памяти (2)

   • Понятие cache-oblivious алгоритма
   • Базовые cache-oblivious алгоритмы
   • Понятие write amplification
   • Фрактальные деревья
   • LSM деревья
   • Bloom фильтры

   Домашнее задание: Реализовать библиотеку для хранения данных на диске.

   Литература:

   • Bitcask: A Log-Structured Hash Table for Fast Key/Value Data by Sheeshy, Smith
   • The Log-Structured Merge-Tree (LSM-Tree) by O'Neil, Cheng ..
   • Cache-Oblivious Algorithms by Harald Prokop
   • Cache-Oblivious Streaming B-trees by Bender, Farach-Colton, Fineman
   • Space/time trade-offs in hash coding with allowable errors by Burton H. Bloom

3. Кэширование как механизм повышения эффективности системы (3)

   • Понятие online алгоритмов
   • Кэширование
   • Алгоритм FIFO
   • Алгоритм LRU
   • Алгоритм LFD
   • Проблема конистентности кэша
   • Алгоритм RCU
   • Протокол MESI
   • Проблема холодного старта

   Домашнее задание: Реализовать LRU/midpoint insertion cache для библиотеки хранения данных на диске.

   Литература:

   • Competitive Paging Algorithms by Fiat, Karp, Luby ..
   • Online algorithms for paging (MIT OCW Lectures on CS) by Erik Demaine

Основы устройства СУБД

1. Принципиальная схема СУБД (4)

   • Сетевая подсистема
   • Разбор и оптимизация запросов
   • План выполнения запроса
   • Управление страницами
   • Управление блокировками
   • Журналирование

   Домашнее задание: Реализация конкурентного доступа к данным с использованием библиотеки хранения данных на диске.

   Литература:

   • InnoDB Internals by Heikki Tuuri
   • Principles of Transaction Processing by Bernstein, Newcomer

2. Свойства транзакции, консистентность данных и модели консистентности данных (5)

   • Принцип двойной записи
   • Запрет на исправления
   • Семантика и допустимость овердрафта в интернет-приложениях
   • Понятие истории изменений
   • Транзакции в распределённых системах
   • Виды аномалий при конкурентном доступе к данным
   • Пессимистичные блокировки
   • 2PL теорема

   Литература:

   • Database Systems. The Complete Book by Ullman, Widom ..
   • Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery by Weikum, Vossen

3. Управление конкурентным доступом к данным на основе иерархии блокировок (6)

   • Иерархические блокировки
   • Специальные блокировки
   • Дедлоки
   • Приоритеты локов
   • Понятие hot spot
   • Алгоритмы поиска дедлоков
   • Понятие насыщения системы массового обслуживания в применении к транзакционной системе

   Литература:

   • Database Performance Tuning: Principles, Experiments and Troubleshooting Techniques by Shasha, Bonnet

4. Управление конкурентным доступом к данным на основе временных меток (7)

   • Понятие оптимистичного управления транзакциями
   • Временные метки
   • Правила установки меток
   • Протокол многоверсионного управления транзакциями

   Литература:

   • ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging by C. Mohan

5. Проблемы физического размещения данных при двухуровневом хранении (8)

   • Фрагментация
   • Управление разделами
   • Назначение сегментов и экстентов
   • UNDO/REDO логирование
   • Восстановление после сбоя
   • Управление кэшем страниц
   • Стратегии Steal/No Steal

Масштабирование и высокая доступность

1. Автоматизация роста распределённой системы (9)

   • Принцип эластичности
   • Шардинг
   • Консистентное хэширование
   • Алгоритм SUMBUR

   Литература:

   • Megastore: Providing Scalable, Highly Available Storage for Interactive Services by Baker, Bond ..
   • Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web by Karget, Lehman ..

2. Модели слабой консистентности в специализированных приложениях, CAP теорема и протокол 2PC (10)

   • Резервирование отелей и авиалиний
   • Корзина покупок пользователя
   • Последовательные коммуницирующие процессы и состояние распределённой системы
   • Виртуальная синхрония

   Литература:

   • A History of the Virtual Synchrony Replication Model by Ken Birman
   • Towards Robust Distributed Systems by Eric Brewer
   • Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services by Lynch, Gilbert

3. Очереди, принципы и приёмы обработки очередей (11)

   • Задача банковского перевода
   • Очереди как средство обеспечения высокой доступности системы и балансировки нагрузки

   Литература:

   • Principles of Transaction Processing by Bernstein, Newcomer

4. Репликация, разрешение конфликтов и векторное время. (12)

   • Принципы работы асинхронной репликации
   • Задачи решаемые семи-синхронной и синхронной репликациейэ
   • Включение и исключение узлов из распределённой реплицированной системы без введения единой точки отказа
   • Мульти-мастер репликация и понятие репликационного конфликта

   Литература:

   • Dynamo: Amazon’s Highly Available Key-value Store by DeCandia, Hastorun ..
   • Spanner: Google’s Globally-Distributed Database by Corbett, Dean ..
   • Timestamps in Message-Passing Systems That Preserve the Partial Ordering by Colin Fidge
   • The Dangers of Replication and a Solution by Gray, Helland

5. Консистентность распределённого ДКА, Paxos и Raft (13)

   • Paxos: разбор алгоритма
   • Multi-Paxos
   • Raft

   Литература:

   • The Byzantine Generals Problem by Lamport, Shostak, Pease
   • In Search of an Understandable Consensus Algorithm by Ongaro, Ousterhost
   • Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore by Rao, Shekita, Tata
   • Time, clock and ordering of events in distributed systems by Leslie Lamport
   • Paxos Made Simple by Leslie Lamport
   • Communicating Sequential Processes by C.A.R. Hoare
   • Multi-ring paxos by Parisa Jalili Marandi

6. Понятие сбоя и принципы восстановления после сбоя (14)

   • Оценка надёжности системы: MTTR и MTBF
   • Причины и частота сбоя
   • Оценка экономической целесообразности программных и аппаратных решений в контексте вероятности сбоя
   • Протокол Gossip

   Литература:

   • Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications by Stoica, Morris ..
   • On Scalable and Efficient Distributed Failure Detectors by Gupta, Goldszmidt ..
   • Correctness of a Gossip Based Membership Protocol

Современные тенденции развития СУБД: NoSQL и NewSQL

1. Обзор различных моделей данных СУБД. (15)

   • Модель сущность-связь
   • Иерархическая модель
   • Реляционная модель
   • Сетевая модель
   • Проблемы разнообразия, скорости изменения и общего объёма данных

   Литература:

   • A Relational Model of Data for Large Shared Data Banks by Edgar F. Codd
   • Foundation for future database systems: the third manifesto: a detailed study of the impact of type theory on the relational model of data, including a comprehensive model of type inheritance by Date, Hugh.
   • NoSQL distilled by Martin Fowler
   • The End of an Architectural Era (It’s Time for a Complete Rewrite) by Stonebraker, Madden ..
   • NoSQL Databases by Christof Strauch
   • Design and Modelling of a Parallel Data Server for Telecom Applications by Mikael Ronström

2. Модели данных в NoSQL. (16)

   • Достоинства и недостатки реляционной модели для работы с данными в Интернет
   • Модель данных ключ-значение
   • Модель BigTable
   • Различия между документом и объектом
   • Понятие агрегата хранения
   • Управление схемой данных
   • Компромисс между консистентностью и производительностью
   • Конкурентный доступ к данным в клиент-серверной и полностью распределённой архитектуре
   • Пример графовых задач в РСУБД

   Домашнее задание: Реализация библиотеки типовых операций с графом на основе реляционной СУБД (MySQL/PostgreSQL/etc).

   Литература

   • Bigtable: A Distributed Storage System for Structured Data by Chand, Dean ..
   • Trees and hierarchies in SQL by Joe Celko
   • The Current State of Graph Databases by Mike Buerli