Алгоритмы и структуры для массивных наборов данных

Джейла Меджедович, Эмин Тахирович
Алгоритмы и структуры 
данных для массивных 
наборов данных

M A N N I N G
SHELTER ISLAND
Algorithms and
Data Structures for
Massive Datasets
DZEJLA MEDJEDOVIC
EMIN TAHIROVIC
Illustrated by INES DEDOVIC

Москва, 2024
Алгоритмы и структуры
для массивных наборов
данных
ДЖЕЙЛА МЕДЖЕДОВИЧ 
ЭМИН ТАХИРОВИЧ
Иллюстрации ИНЕС ДЕДОВИЧ

УДК   32.973.2
ББК   004.021
М42
М42    Джейла Меджедович, Эмин Тахирович
Алгоритмы и структуры для массивных наборов данных / пер. с  англ. 
А. В. Логунова. – М.: ДМК Пресс, 2024. – 340 с.: ил.
            ISBN 978-5-93700-250-1
Стандартные алгоритмы и структуры при применении к крупным 
распределенным наборам данных могут становиться медленными — 
или вообще не работать. Правильный подбор алгоритмов, предназначенных для работы с большими данными, экономит время, повышает 
точность и снижает стоимость обработки. 
Книга знакомит с методами обработки и анализа больших распределенных данных. Насыщенное отраслевыми историями и занимательными иллюстрациями, это удобное руководство позволяет легко понять 
даже сложные концепции. Вы научитесь применять на реальных примерах такие мощные алгоритмы, как фильтры Блума, набросок count-min, 
HyperLogLog и LSM-деревья, в своих собственных проектах.
Copyright © DMK Press 2023. Authorized translation of the English edition © 2023 
Manning Publications. This translation is published and sold by permission of Manning 
Publications, the owner of all rights to publish and sell the same.
Все права защищены. Любая часть этой книги не может быть воспроизведена в 
какой бы то ни было форме и какими бы то ни было средствами без письменного 
разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку 
вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи 
с этим издательство не несет ответственности за возможные ошибки, связанные 
с использованием книги.
ISBN 978-1-61729-803-5 (англ.)                   Copyright © 2022 by Manning Publications Co.
ISBN 978-5-93700-250-1 (рус.)                    © Оформление, перевод на русский язык, 
	
               издание, ДМК Пресс, 2024

Оглавление
Предисловие............................................................................................................11
Благодарности.........................................................................................................13
Об этой книге...........................................................................................................14
Об авторах...............................................................................................................18
Глава 1. Введение....................................................................................................19
1.1 Пример.........................................................................................................21
1.2 Структура этой книги..................................................................................28
1.3 Отличие этой книги от других и ее целевая аудитория............................28
1.4 Почему массивные данные представляют трудности  
для современных систем?...........................................................................30
1.4.1 Разрыв в производительности центрального процессора и памяти......30
1.4.2 Иерархия памяти..................................................................................... 30
1.4.3 Задержка относительно пропускной способности............................... 32
1.4.4 Как насчет распределенных систем?..................................................... 33
1.5 Конструирование алгоритмов с учетом аппаратного обеспечения.........33
Резюме................................................................................................................35
Часть I. Наброски на основе хеша......................................................................37
Глава 2. Обзор хеш-таблиц и современного хеширования.............................38
2.1 Хеширование повсюду................................................................................39
2.2 Ускоренный курс по структурам данных...................................................41
2.3 Сценарии использования в современных системах.................................44
2.3.1 Дедупликация в программных решениях по резервному 
копированию/хранению данных........................................................... 44
2.3.2 Обнаружение плагиата с помощью идентификации цифровых 
отпечатков на основе меры MOSS и алгоритма Рабина–Карпа.......... 46
2.4 O(1): что в этом такого?...............................................................................48
2.5 Урегулирование коллизий: теория и практика..........................................50
2.6 Сценарий использования: принцип работы словаря в языке Python......53
2.7 Хеш-функция MurmurHash.........................................................................54
2.8 Хеш-таблицы для распределенных систем: согласованное  
хеширование................................................................................................56
2.8.1 Типичная проблема хеширования......................................................... 56
2.8.2 Хеш-кольцо.............................................................................................. 58

6    Оглавление
2.8.3 Поиск........................................................................................................ 60
2.8.4 Добавление нового узла/ресурса............................................................ 61
2.8.5 Удаление узла.......................................................................................... 63
2.8.6 Сценарий согласованного хеширования: хордовый протокол............ 67
2.8.7 Согласованное хеширование: упражнения по программированию... 69
Резюме................................................................................................................69
Глава 3. Приближенная принадлежность: блумовские и порционные 
фильтры....................................................................................................................71
3.1 Принцип работы..........................................................................................74
3.1.1 Вставка..................................................................................................... 74
3.1.2 Поиск........................................................................................................ 75
3.2 Варианты использования............................................................................76
3.2.1 Фильтры Блума в сетях: Squid................................................................ 76
3.2.2 Мобильное приложение для биткоинов................................................ 76
3.3 Простая реализация.....................................................................................78
3.4 Конфигурирование фильтра Блума............................................................79
3.4.1 Работа с фильтрами Блума: мини-эксперименты................................ 82
3.5 Немного теории...........................................................................................83
3.5.1 Можно ли добиться большего?............................................................... 85
3.6 Адаптации и альтернативы фильтров Блума............................................87
3.7 Порционный фильтр...................................................................................88
3.7.1 Формирование частных и остатков....................................................... 89
3.7.2 Понятие битов метаданных.................................................................... 91
3.7.3 Вставка в порционный фильтр: пример................................................ 92
3.7.4 Исходный код Python для поиска........................................................... 94
3.7.5 Изменение размера и слияние............................................................... 97
3.7.6 Соображения по поводу частоты ложноположительных  
результатов и пространства................................................................... 98
3.8 Сравнение блумовских и порционных фильтров.....................................99
Резюме..............................................................................................................101
Глава 4. Оценивание частоты и набросок count-min......................................103
4.1 Преобладающий элемент..........................................................................105
4.1.1 Общая задача о тяжеловесах................................................................ 107
4.2 Набросок count-min: принцип работы.....................................................108
4.2.1 Обновление............................................................................................ 108
4.2.2 Оценивание........................................................................................... 108
4.3 Варианты использования..........................................................................110
4.3.1 k верхних беспокойно спящих пользователей.................................... 110
4.3.2 Масштабирование распределительного сходства между словами.... 114
4.4 Ошибка и пространство в наброске count-min........................................117

Оглавление    7
4.5 Простая реализация наброска count-min.................................................118
4.5.1 Упражнения........................................................................................... 119
4.5.2 Вытекающий из формулы интуитивный вывод: немного  
математики............................................................................................ 120
4.6 Диапазонные запросы с помощью наброска count-min.........................121
4.6.1 Диадические интервалы....................................................................... 122
4.6.2 Фаза обновления................................................................................... 123
4.6.3 Фаза оценивания................................................................................... 125
4.6.4 Вычисление диадических интервалов................................................. 126
Резюме..............................................................................................................128
Глава 5. Оценивание кардинального числа и алгоритм HyperLogLog.........130
5.1 Подсчет числа несовпадающих элементов в базах данных....................131
5.2 Постепенное конструирование алгоритма HyperLogLog........................133
5.2.1 Первая примерка: вероятностный подсчет ........................................ 134
5.2.2 Стохастическое усреднение, или «Когда жизнь преподносит  
вам лимоны».......................................................................................... 135
5.2.3 Алгоритм LogLog................................................................................... 137
5.2.4 Алгоритм HyperLogLog: стохастическое усреднение вместе  
с гармоническим средним.................................................................... 139
5.3 Пример использования: ловля червей с помощью алгоритма  
HyperLogLog...............................................................................................142
5.4 Но как это работает? Мини-эксперимент................................................144
5.4.1 Влияние числа корзин (m).................................................................... 146
5.5 Пример использования: агрегация с использованием  
алгоритма HyperLogLog............................................................................148
Резюме..............................................................................................................152
Часть II. Реально-временная аналитика..........................................................153
Глава 6. Потоковые данные: сведение всего воедино...................................154
6.1 Система обработки потоковых данных: метапример.............................159
6.1.1 Соединение на основе фильтра Блума................................................ 160
6.1.2 Дедупликация........................................................................................ 163
6.1.3 Балансировка нагрузки и отслеживание сетевого трафика............... 164
6.2 Практические ограничения и понятия потоков данных........................167
6.2.1 В реальном времени............................................................................. 167
6.2.2 Малое время и малое пространство.................................................... 168
6.2.3 Сдвиги в концепциях и дрейфы концепций....................................... 169
6.2.4 Модель скользящего окна..................................................................... 170
6.3 Немного математики: формирование и оценивание выборок..............172
6.3.1 Стратегия формирования смещенной выборки................................. 173
6.3.2 Оценивание по репрезентативной выборке....................................... 177
Резюме..............................................................................................................178

8    Оглавление
Глава 7. Формирование выборок из потоков данных....................................180
7.1 Формирование выборок из реперного потока.........................................181
7.1.1 Формирование выборки Бернулли....................................................... 181
7.1.2 Формирование резервуарной выборки............................................... 186
7.1.3 Формирование смещенной резервуарной выборки........................... 192
7.2 Формирование выборок из скользящего окна.........................................197
7.2.1 Формирование цепной выборки.......................................................... 198
7.2.2 Формирование приоритетной выборки.............................................. 202
7.3 Сравнение алгоритмов формирования выборок.....................................206
7.3.1 Настройка симуляции: алгоритмы и данные...................................... 206
Резюме..............................................................................................................210
Глава 8. Приближенные квантили на потоках данных...................................212
8.1 Точные квантили.......................................................................................213
8.2 Приближенные квантили..........................................................................216
8.2.1 Аддитивная ошибка.............................................................................. 216
8.2.2 Относительная ошибка......................................................................... 218
8.2.3 Относительная ошибка в области значений данных......................... 219
8.3 T-дайджест: принцип его работы.............................................................219
8.3.1 Дайджест................................................................................................ 220
8.3.2 Масштабные функции .......................................................................... 221
8.3.3 Слияние t-дайджестов.......................................................................... 226
8.3.4 Пространственные границы t-дайджеста............................................ 229
8.4 q-дайджест..................................................................................................230
8.4.1 Конструирование q-дайджеста с нуля................................................. 231
8.4.2 Слияние q-дайджестов.......................................................................... 233
8.4.3 Соображения по поводу ошибки и пространства в q-дайджестах..... 234
8.4.4 Квантильные запросы с использованием q-дайджестов................... 235
8.5 Исходный код симуляции и ее результаты .............................................236
Резюме..............................................................................................................241
Часть III. Структуры данных для баз данных и алгоритмы внешней  
памяти.....................................................................................................................243
Глава 9. Введение в модель внешней памятих...............................................244
9.1 Модель внешней памяти: предварительные сведения..............................246
9.2 Пример 1: отыскание минимума..............................................................249
9.2.1 Вариант использования: минимальный медианный доход.............. 249
9.3 Пример 2: двоичный поиск.......................................................................252
9.3.1 Вариант использования в области биоинформатики......................... 252
9.3.2 Анализ времени выполнения............................................................... 254
9.4 Оптимальный поиск..................................................................................256

Оглавление    9
9.5 Пример 3: слияние K сортированных списков........................................258
9.5.1 Слияние журналов времени/дат.......................................................... 259
9.5.2 Модель внешней памяти: простая либо упрощенческая?................. 263
9.6 Что дальше.................................................................................................264
Резюме..............................................................................................................264
Глава 10. Структуры данных для баз данных: B-деревья,  
Bε-деревья и LSM-деревья..................................................................................266
10.1 Принцип работы индексации.................................................................267
10.2 Структуры данных этой главы................................................................269
10.3 B-деревья..................................................................................................271
10.3.1 Балансирование B-дерева................................................................... 272
10.3.2 Поиск.................................................................................................... 273
10.3.3 Вставка................................................................................................. 273
10.3.4 Удаление.............................................................................................. 276
10.3.5 B+-деревья............................................................................................ 280
10.3.6 Чем отличаются операции на B+-дереве............................................ 281
10.3.7 Вариант использования: B-деревья в MySQL (и многих других 
местах)................................................................................................... 281
10.4 Немного математики: почему поиск в B-дереве оптимален  
во внешней памяти?.................................................................................282
10.4.1 Почему вставки/удаления в B-дереве не являются  
оптимальными во внешней памяти.................................................... 285
10.5 Bε-деревья.................................................................................................285
10.5.1 Bε-дерево: принцип работы................................................................ 286
10.5.2 Механика буферизации...................................................................... 286
10.5.3 Вставка и удаление.............................................................................. 288
10.5.4 Поиск.................................................................................................... 289
10.5.5 Анализ стоимости............................................................................... 290
10.5.6 Bε-дерево: спектр структур данных.................................................... 291
10.5.7 Вариант использования: Bε-деревья в TokuDB.................................. 292
10.5.8 Торопитесь медленно, как операции ввода-вывода......................... 293
10.6 Журнально-структурированные деревья слияния (LSM-деревья).......294
10.6.1 LSM-дерево: принцип работы............................................................ 296
10.6.2 Анализ стоимости LSM-дерева .......................................................... 299
10.6.3 Вариант использования: LSM-деревья в Cassandra.......................... 299
Резюме..............................................................................................................301
Глава 11. Сортировка во внешней памяти........................................................302
11.1 Варианты использования сортировки...................................................303
11.1.1 Планирование движений робота....................................................... 303
11.1.2 Онкогеномика..................................................................................... 304
11.2 Трудности сортировки во внешней памяти: пример............................306
11.2.1 Двупутная сортировка слиянием во внешней памяти..................... 307

10    Оглавление
11.3 Сортировка слиянием во внешней памяти (M/B-путная сортировка 
слиянием)...................................................................................................309
11.3.1 Поиск и сортировка: оперативная память по сравнению  
с внешней памятью............................................................................... 311
11.4 Как насчет внешней быстрой сортировки?............................................313
11.4.1 Двупутная быстрая сортировка во внешней памяти........................ 314
11.4.2 На пути к многопутной быстрой сортировке во внешней памяти.... 314
11.4.3 Отыскание достаточного числа опорных точек................................ 316
11.4.4 Отыскание достаточно хороших опорных точек.............................. 317
11.4.5 Сведение всего воедино...................................................................... 318
11.5 Немного математики: почему сортировка слиянием во внешней 
памяти оптимальна?.................................................................................318
11.6 Подведение итогов..................................................................................321
Резюме..............................................................................................................321
Справочные материалы.......................................................................................323
Об иллюстрации на обложке..............................................................................331
Предметный указатель........................................................................................332