-
Notifications
You must be signed in to change notification settings - Fork 27
/
schedule.html
227 lines (227 loc) · 38 KB
/
schedule.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
<html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Методы использования СУБД в интернет-приложениях, Техносфера Mail.Ru, 2014 г.</title><meta name="generator" content="DocBook XSL Stylesheets V1.78.1"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="article"><div class="titlepage"><div><div><h2 class="title"><a name="nosql-schedule"></a>Методы использования СУБД в интернет-приложениях,
Техносфера Mail.Ru, 2014 г.</h2></div></div><hr></div><p>
Курс лекций раздёлён на 4 части, в конце каждой части
проводится колоквиум.
</p><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="idm6268240"></a>Структуры данных и алгоритмы для двухуровневой памяти</h2></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
Многообразие решений для хранения данных. Модели данных
классических и NoSQL систем. Модели консистентности.
Семантика и допустимость овердрафта в интернет-приложениях.
</p><p>
Достоинства и недостатки реляционной модели для
работы с данными в Интернет.
Модель данных ключ-значение. Модель BigTable. Различия между
документом и объектом. Понятие агрегата хранения.
Управление схемой данных. Компромисс между
консистентностью и производительностью. Конкурентный доступ
к данным в клиент-серверной и полностью распределённой
архитектуре. Пример графовых задач в РСУБД.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48772416"></a><p><span class="author">
Codd, E.F.
. </span><span class="title"><i>
A Relational Model of Data for Large Shared Data Banks
</i>. </span></p></div><div class="biblioentry"><a name="idp48773824"></a><p><span class="author">
Date, C. J.; Darwen, Hugh
. </span><span class="title"><i>
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.
</i>. </span></p></div><div class="biblioentry"><a name="idp48775520"></a><p><span class="author">
Pramod J. Sadalage, Martin Fowler
. </span><span class="title"><i>
NoSQL distilled
</i>. </span></p></div><div class="biblioentry"><a name="idp48776800"></a><p><span class="author">
Michael Stonebraker, Samuel Madden, Daniel J.
Abadi, Stavros Harizopoulos, Nabil Hachem, Pat
Helland
. </span><span class="title"><i>
The End of an Architectural Era (It’s Time for a
Complete Rewrite)
</i>. </span></p></div><div class="biblioentry"><a name="idp48778496"></a><p><span class="author">Christof Strauch. </span><span class="title"><i>NoSQL Databases</i>. </span></p></div><div class="biblioentry"><a name="idp48779776"></a><p><span class="author">
Mikael Ronström
. </span><span class="title"><i>
Design and Modelling of a Parallel Data Server for
Telecom Applications
</i>. </span></p></div><div class="biblioentry"><a name="idp48781184"></a><p><span class="author">
Fay Chang, Jeffrey Dean, Sanjay Ghemawat,
Wilson C. Hsieh, Deborah A. Wallach Mike
Burrows, Tushar Chandra, Andrew Fikes, Robert
E. Gruber
. </span><span class="title"><i>
Bigtable: A Distributed Storage System for Structured Data
</i>. </span></p></div><div class="biblioentry"><a name="idp48782704"></a><p><span class="author">
Joe Celko
. </span><span class="title"><i>
Trees and hierarchies in SQL
</i>. </span></p></div><div class="biblioentry"><a name="idp48783984"></a><p><span class="author">
Mike Buerli
. </span><span class="title"><i>
The Current State of Graph Databases
</i>. </span></p></div></div></li><li class="listitem"><p>
Классические алгоритмы организации даных для двухуровневой
памяти.
</p><p>
B-деревья. Инвертированные списки. Многопроходная сортировка
слиянием. Стоимостная модель DAM.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48787888"></a><p><span class="author">Alok Aggarwal, Jeffrey Scott Vitter. </span><span class="title"><i>The input/output complexity of sorting and related problems</i>. </span></p></div><div class="biblioentry"><a name="idp48789168"></a><p><span class="author">Douglas Comer. </span><span class="title"><i>The Ubiquitous B-tree</i>. </span></p></div><div class="biblioentry"><a name="idp48790448"></a><p><span class="author">Michael A. Bender, Bradley C. Kuszmaul. </span><span class="title"><i>Data Structures and Algorithms for Big Databases</i>. </span></p></div></div></li><li class="listitem"><p>
Современные специализированные алгоритмы хранения данных
в двухуровневой памяти.
</p><p>
Понятие cache-oblivious алгоритма. Базовые
cache-oblivious алгоритмы. Понятие write amplification.
Фрактальные деревья.
</p><p><b>Домашнее задание: </b>Реализовать библиотеку для хранения данных на диске.</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48795472"></a><p><span class="author">Harald Prokop. </span><span class="title"><i>Cache-Oblivious Algorithms</i>. </span></p></div><div class="biblioentry"><a name="idp48796752"></a><p><span class="author">Michael A. Bender Martin Farach-Colton Jeremy T. Fineman. </span><span class="title"><i>Cache-Oblivious Streaming B-trees </i>. </span></p></div><div class="biblioentry"><a name="idp48798032"></a><p><span class="author">Burton H. Bloom. </span><span class="title"><i>Space/time trade-offs in hash coding with allowable errors
</i>. </span></p></div></div></li><li class="listitem"><p>
Современные специализированные алгоритмы хранения данных
в двухуровневой памяти (часть 2).
</p><p>
LSM деревья. Блум-фильтры. Двухуровневые деревья.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48801856"></a><p><span class="author">Justin Sheehy, David Smith. </span><span class="title"><i>Bitcask A Log-Structured Hash Table for Fast Key/Value Data</i>. </span></p></div><div class="biblioentry"><a name="idp48803136"></a><p><span class="author">Patrick O'Neil , Edward Cheng, Dieter Gawlick, Elizabeth O'Neil. </span><span class="title"><i>The Log-Structured Merge-Tree (LSM-Tree)</i>. </span></p></div><div class="biblioentry"><a name="idp48804416"></a><p><span class="author">Burton H. Bloom. </span><span class="title"><i>Space/time trade-offs in hash coding with allowable errors
</i>. </span></p></div></div></li><li class="listitem"><p>
Кэширование как механизм повышения эффективности системы.
</p><p>
Понятие online алгоритмов. Кэширование. Алгоритмы FIFO, LRU.
Алгоритм LFD. Проблема конистентности кэша. Алгоритм
RCU. Протокол MESI. Проблема холодного старта.
</p><p><b>Домашнее задание: </b>
Реализовать LRU/midpoint insertion cache для библиотеки
хранения данных на диске.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48809856"></a><p><span class="author">
Amos Fiat, Richard M. Brp,Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, Neal E. Young
. </span><span class="title"><i>
Competitive Paging Algorithms
</i>. </span></p></div><div class="biblioentry"><a name="idp48811280"></a><p><span class="author">
Erik Demaine
. </span><span class="title"><i>
Online algorithms for paging (MIT OCW Lectures on Computer Science)
</i>. </span></p></div></div></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="idp48813200"></a>Основы устройства СУБД</h2></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
Принципиальная схема СУБД.
</p><p>
Сетевая подсистема. Разбор и оптимизация запросов.
План выполнения запроса. Управление страницами.
Управление блокировками. Журнал.
</p><p><b>Домашнее задание: </b>
Реализация конкурентного доступа к данным
с использованием библиотеки хранения данных
на диске.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48817952"></a><p><span class="author">
Heikki Tuuri
. </span><span class="title"><i>InnoDB Internals, presentation</i>. </span></p></div><div class="biblioentry"><a name="idp48819232"></a><p><span class="author">
Philip A. Bernstein, Eric Newcomer
. </span><span class="title"><i>Principles of Transaction Processing</i>. </span></p></div></div></li><li class="listitem"><p>
Транзакции. Принципы ACID транзакционной обработки данных.
Реализация подсистемы хранения с использованием журнала.
</p><p>
Принцип двойной записи. Понятие истории изменений.
Стратегии NO UNDO, NO REDO. Стратегии STEAL, NO STEAL.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48823312"></a><p><span class="title"><i>Database systems, the complete book</i>. </span><span class="author">
Hector Garcia-Molina, Jeffrey D. Ullman,
Jennifer Widom
. </span></p></div><div class="biblioentry"><a name="idp48824592"></a><p><span class="author">
Gerhard Weikum, Gottfried Vossen
. </span><span class="title"><i>Transactional Information Systems: Theory,
Algorithms, and the Practice of Concurrency Control and
Recovery </i>. </span></p></div></div></li><li class="listitem"><p>
Использование блокировок для управления транзакциями.
Понятие расписания. Теорема 2PL.
</p><p>
Понятие расписание. Сериальные и сериализуемые расписания.
Классы расписаний. Теорема 2PL: формулировка. Построение
графа зависимостей транзакций. Доказательство.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48828944"></a><p><span class="author">
Gerhard Weikum, Gottfried Vossen
. </span><span class="title"><i>Transactional Information Systems: Theory,
Algorithms, and the Practice of Concurrency Control and
Recovery </i>. </span></p></div></div></li><li class="listitem"><p>
Управление блокировками.
</p><p>
Иерархические блокировки. Специальные блокировки. Дедлоки.
Приоритеты локов. Понятие hot spot. Алгоритмы поиска
дедлоков. Понятие насыщения системы массового обслуживания
в применении к транзакционной системе.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48833072"></a><p><span class="author">
Dennis Shasha, Philippe Bonnet
. </span><span class="title"><i>Database Performance Tuning: Principles, Experiments
and Troubleshooting Techniques</i>. </span></p></div></div></li><li class="listitem"><p>
Оптимистичные алгоритмы управления транзакциями.
</p><p>
Понятие оптимистичного управления транзакциями.
Валидация. Временные метки. Правила установки меток.
Протокол многоверсионного управления транзакциями.
</p><div class="bibliolist"><div class="biblioentry"><a name="idp48836752"></a><p><span class="author">
C. Mohan
. </span><span class="title"><i>
ARIES: A Transaction Recovery Method Supporting
Fine-Granularity Locking and Partial Rollbacks
Using Write-Ahead Logging
</i>. </span></p></div></div></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="idp48838736"></a>Масштабирование и высокая доступность</h2></div></div></div><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Горизонтальное масштабирование СУБД</p><p>
Принцип эластичности. Шардинг. Консистентное хэширование.
Алгоритм Guava.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48841616"></a><p><span class="author">
Jason Baker, Chris Bond, James C. Corbett, JJ
Furman, Andrey Khorlin, James Larson,
Jean-Michel Leon, Yawei Li, Alexander Lloyd,
Vadim Yushprakh
. </span><span class="title"><i>
Megastore: Providing Scalable, Highly
Available Storage for Interactive Services
</i>. </span></p></div><div class="biblioentry"><a name="idp48843312"></a><p><span class="author">
David Karger Eric Lehman Matthew Levine Tom
Leighton Rina Panigrahy Daniel Lewin
. </span><span class="title"><i>
Consistent Hashing and Random Trees:
Distributed Caching Protocols for Relieving
Hot Spots on the World Wide Web
</i>. </span></p></div></div></li><li class="listitem"><p>
Введение в распределённые системы. Протокол 2PC.
</p><p>
Понятие распределённой системы. Свойства Safety и Liveness.
Дилемма двух генералов. Результат Фишера-Линча-Паттерсона.
Протокол 2PC. Возможные оптимизации.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48847728"></a><p><span class="author">Ken Birman. </span><span class="title"><i>A History of the Virtual Synchrony Replication Model</i>. </span></p></div><div class="biblioentry"><a name="idp48849008"></a><p><span class="author">
Eric Brewer
. </span><span class="title"><i>
Towards Robust Distributed Systems
</i>. </span></p></div><div class="biblioentry"><a name="idp48850288"></a><p><span class="author">
Nancy Lynch and Seth Gilbert
. </span><span class="title"><i>
Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services
</i>. </span></p></div></div></li><li class="listitem"><p>
Репликация. Разрешение конфликтов. Векторное время.
</p><p>
Принципы работы асинхронной репликации.
Задачи решаемые семи-синхронной и синхронной репликацией.
Включение и исключение узлов из распределённой реплицированной
системы без введения единой точки отказа. Мульти-мастер
репликация и понятие репликационного конфликта.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48854512"></a><p><span class="title"><i>
Dynamo: Amazon’s Highly Available Key-value Store
</i>. </span><span class="author">
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati,
Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall
and Werner Vogels
. </span></p></div><div class="biblioentry"><a name="idp48856208"></a><p><span class="author">
James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes,
Christopher Frost, JJ Furman, Sanjay Ghemawat, Andrey Gubarev,
Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian
Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey
Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao,
Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher
Taylor, Ruth Wang, Dale Woodford
. </span><span class="title"><i>Spanner: Google’s Globally-Distributed Database</i>. </span></p></div><div class="biblioentry"><a name="idp48858032"></a><p><span class="author">Colin J. Fidge. </span><span class="title"><i>Timestamps in Message-Passing Systems That Preserve the Partial Ordering</i>. </span></p></div><div class="biblioentry"><a name="idp48859312"></a><p><span class="author">Jim Gray, Pat Helland, Patrick O’Neil, Dennis Shasha. </span><span class="title"><i>The Dangers of Replication and a Solution</i>. </span></p></div></div></li><li class="listitem"><p>
Консистентность распределённого ДКА. Алгоритм Paxos.
</p><p>
Paxos: разбор алгоритма. Multi-Paxos.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48863008"></a><p><span class="author">Leslie Lamport, Robert Shostak, Marshall Pease. </span><span class="title"><i>The Byzantine Generals Problem</i>. </span></p></div><div class="biblioentry"><a name="idp48864288"></a><p><span class="author">Diego Ongaro, John Ousterhout. </span><span class="title"><i>In Search of an Understandable Consensus Algorithm</i>. </span></p></div><div class="biblioentry"><a name="idp48865568"></a><p><span class="author">Jun Rao, Eugene J. Shekita, Sandeep Tata. </span><span class="title"><i>Using Paxos to Build a Scalable, Consistent,
and Highly Available Datastore</i>. </span></p></div><div class="biblioentry"><a name="idp48866848"></a><p><span class="author">Leslie Lamport. </span><span class="title"><i>Time, clock and ordering of events in distributed systems</i>. </span></p></div><div class="biblioentry"><a name="idp48868128"></a><p><span class="author">Leslie Lamport. </span><span class="title"><i>Paxos Made Simple</i>. </span></p></div><div class="biblioentry"><a name="idp48869408"></a><p><span class="author">C.A.R. Hoare. </span><span class="title"><i>Communicating Sequential Processes</i>. </span></p></div><div class="biblioentry"><a name="idp48870688"></a><p><span class="author">Parisa Jalili Marandi. </span><span class="title"><i>Multi-ring paxos </i>. </span></p></div></div></li><li class="listitem"><p>
Задача репликации журнала БД. Алгоритм Raft.
</p><p>
Raft: разбор алгоритма. Задача смены конфигурации. Оптимизации.
</p><div class="bibliolist"><p class="title"><b>Литература</b></p><div class="biblioentry"><a name="idp48874352"></a><p><span class="title"><i>
Chord: A Scalable Peer-to-peer Lookup Service for Internet
Applications
</i>. </span><span class="author">
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan
. </span></p></div><div class="biblioentry"><a name="idp48875904"></a><p><span class="author">
Indranil Gupta Tushar D. Chandra German S. Goldszmidt
. </span><span class="title"><i>On Scalable and Efficient Distributed Failure Detectors</i>. </span></p></div><div class="biblioentry"><a name="idp48877184"></a><p><span class="author">André Allavena, Alan Demers, John E. Hopcroft. </span><span class="title"><i>Correctness of a Gossip Based Membership Protocol</i>. </span></p></div></div></li></ol></div></div></div></body></html>