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

Предисловие....12

Благодарности....14

Об этой книге....15

Об авторах....19

Глава 1....20

Введение....20

1.1 Пример....22

1.2 Структура этой книги....29

1.3 Отличие этой книги от других и ее целевая аудитория....29

1.4 Почему массивные данные представляют трудности для современных систем?....31

1.4.1 Разрыв в производительности центрального процессора и памяти....31

1.4.2 Иерархия памяти....31

1.4.3 Задержка относительно пропускной способности....33

1.4.4 Как насчет распределенных систем?....34

1.5 Конструирование алгоритмов с учетом аппаратного обеспечения....34

Резюме....36

Часть I....38

Наброски на основе хеша....38

Глава 2....39

Обзор хеш-таблиц и современного хеширования....39

2.1 Хеширование повсюду....40

2.2 Ускоренный курс по структурам данных....42

2.3 Сценарии использования в современных системах....45

2.3.1 Дедупликация в программных решениях по резервному копированию/хранению данных....45

2.3.2 Обнаружение плагиата с помощью идентификации цифровых отпечатков на основе меры MOSS и алгоритма Рабина–Карпа....47

2.4 O(1): что в этом такого?....49

2.5 Урегулирование коллизий: теория и практика....51

2.6 Сценарий использования: принцип работы словаря в языке Python....54

2.7 Хеш-функция MurmurHash....55

2.8 Хеш-таблицы для распределенных систем: согласованное хеширование....57

2.8.1 Типичная проблема хеширования....57

2.8.2 Хеш-кольцо....59

2.8.3 Поиск....61

2.8.4 Добавление нового узла/ресурса....62

2.8.5 Удаление узла....64

2.8.6 Сценарий согласованного хеширования: хордовый протокол....68

2.8.7 Согласованное хеширование: упражнения по программированию....70

Резюме....70

Глава 3....72

Приближенная принадлежность: блумовские и порционные фильтры....72

3.1 Принцип работы....75

3.1.1 Вставка....75

3.1.2 Поиск....76

3.2 Варианты использования....77

3.2.1 Фильтры Блума в сетях: Squid....77

3.2.2 Мобильное приложение для биткоинов....77

3.3 Простая реализация....79

3.4 Конфигурирование фильтра Блума....80

3.4.1 Работа с фильтрами Блума: мини-эксперименты....83

3.5 Немного теории....84

3.5.1 Можно ли добиться большего?....86

3.6 Адаптации и альтернативы фильтров Блума....88

3.7 Порционный фильтр....89

3.7.1 Формирование частных и остатков....90

3.7.2 Понятие битов метаданных....92

3.7.3 Вставка в порционный фильтр: пример....93

3.7.4 Исходный код Python для поиска....95

3.7.5 Изменение размера и слияние....98

3.7.6 Соображения по поводу частоты ложноположительных результатов и пространства....99

3.8 Сравнение блумовских и порционных фильтров....100

Резюме....102

Глава 4....104

Оценивание частоты и набросок count-min....104

4.1 Преобладающий элемент....106

4.1.1 Общая задача о тяжеловесах....108

4.2 Набросок count-min: принцип работы....109

4.2.1 Обновление....109

4.2.2 Оценивание....109

4.3 Варианты использования....111

4.3.1 k верхних беспокойно спящих пользователей....111

4.3.2 Масштабирование распределительного сходства между словами....115

4.4 Ошибка и пространство в наброске count-min....118

4.5 Простая реализация наброска count-min....119

4.5.1 Упражнения....120

4.5.2 Вытекающий из формулы интуитивный вывод: немного математики....121

4.6 Диапазонные запросы с помощью наброска count-min....122

4.6.1 Диадические интервалы....123

4.6.2 Фаза обновления....124

4.6.3 Фаза оценивания....126

4.6.4 Вычисление диадических интервалов....127

Резюме....129

Глава 5....131

Оценивание кардинального числа и алгоритм HyperLogLo....131

5.1 Подсчет числа несовпадающих элементов в базах данных....132

5.2 Постепенное конструирование алгоритма HyperLogLog....134

5.2.1 Первая примерка: вероятностный подсчет ....135

5.2.2 Стохастическое усреднение, или «Когда жизнь преподносит вам лимоны»....136

5.2.3 Алгоритм LogLog....138

5.2.4 Алгоритм HyperLogLog: стохастическое усреднение вместе с гармоническим средним....140

5.3 Пример использования: ловля червей с помощью алгоритма HyperLogLog....143

5.4 Но как это работает? Мини-эксперимент....145

5.4.1 Влияние числа корзин (m)....147

5.5 Пример использования: агрегация с использованием алгоритма HyperLogLog....149

Резюме....153

Часть II....154

Реально-временная аналитика....154

Глава 6....155

Потоковые данные: сведение всего воедино....155

6.1 Система обработки потоковых данных: метапример....160

6.1.1 Соединение на основе фильтра Блума....161

6.1.2 Дедупликация....164

6.1.3 Балансировка нагрузки и отслеживание сетевого трафика....165

6.2 Практические ограничения и понятия потоков данных....168

6.2.1 В реальном времени....168

6.2.2 Малое время и малое пространство....169

6.2.3 Сдвиги в концепциях и дрейфы концепций....170

6.2.4 Модель скользящего окна....171

6.3 Немного математики: формирование и оценивание выборок....173

6.3.1 Стратегия формирования смещенной выборки....174

6.3.2 Оценивание по репрезентативной выборке....178

Резюме....179

Глава 7....181

Формирование выборок из потоков данных....181

7.1 Формирование выборок из реперного потока....182

7.1.1 Формирование выборки Бернулли....182

7.1.2 Формирование резервуарной выборки....187

7.1.3 Формирование смещенной резервуарной выборки....193

7.2 Формирование выборок из скользящего окна....198

7.2.1 Формирование цепной выборки....199

7.2.2 Формирование приоритетной выборки....203

7.3 Сравнение алгоритмов формирования выборок....207

7.3.1 Настройка симуляции: алгоритмы и данные....207

Резюме....211

Глава 8....213

Приближенные квантили на потоках данных....213

8.1 Точные квантили....214

8.2 Приближенные квантили....217

8.2.1 Аддитивная ошибка....217

8.2.2 Относительная ошибка....219

8.2.3 Относительная ошибка в области значений данных....220

8.3 T-дайджест: принцип его работы....220

8.3.1 Дайджест....221

8.3.2 Масштабные функции ....222

8.3.3 Слияние t-дайджестов....227

8.3.4 Пространственные границы t-дайджеста....230

8.4 Q-дайджест....231

8.4.1 Конструирование q-дайджеста с нуля....232

8.4.2 Слияние q-дайджестов....234

8.4.3 Соображения по поводу ошибки и пространства в q-дайджестах....235

8.4.4 Квантильные запросы с использованием q-дайджестов....236

8.5 Исходный код симуляции и ее результаты ....237

Резюме....242

Часть III....244

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

Глава 9....245

Введение в модель внешней памятих....245

9.1 Модель внешней памяти: предварительные сведения....247

9.2 Пример 1: отыскание минимума....250

9.2.1 Вариант использования: минимальный медианный доход....250

9.3 Пример 2: двоичный поиск....253

9.3.1 Вариант использования в области биоинформатики....253

9.3.2 Анализ времени выполнения....255

9.4 Оптимальный поиск....257

9.5 Пример 3: слияние K сортированных списков....259

9.5.1 Слияние журналов времени/дат....260

9.5.2 Модель внешней памяти: простая либо упрощенческая?....264

9.6 Что дальше....265

Резюме....265

Глава 10....267

Структуры данных для баз данных: B-деревья, Bε-деревья и LSM-деревьях....267

10.1 Принцип работы индексации....268

10.2 Структуры данных этой главы....270

10.3 B-деревья....272

10.3.1 Балансирование B-дерева....273

10.3.2 Поиск....274

10.3.3 Вставка....274

10.3.4 Удаление....277

10.3.5 B+-деревья....281

10.3.6 Чем отличаются операции на B+-дереве....282

10.3.7 Вариант использования: B-деревья в MySQL (и многих других местах)....282

10.4 Немного математики: почему поиск в B-дереве оптимален во внешней памяти?....283

10.4.1 Почему вставки/удаления в B-дереве не являются оптимальными во внешней памяти....286

10.5 Bε-деревья....286

10.5.1 Bε-дерево: принцип работы....287

10.5.2 Механика буферизации....287

10.5.3 Вставка и удаление....289

10.5.4 Поиск....290

10.5.5 Анализ стоимости....291

10.5.6 Bε-дерево: спектр структур данных....292

10.5.7 Вариант использования: Bε-деревья в TokuDB....293

10.5.8 Торопитесь медленно, как операции ввода-вывода....294

10.6 Журнально-структурированные деревья слияния (LSM-деревья)....295

10.6.1 LSM-дерево: принцип работы....297

10.6.2 Анализ стоимости LSM-дерева ....300

10.6.3 Вариант использования: LSM-деревья в Cassandra....300

Резюме....302

Глава 11....303

Сортировка во внешней памятих....303

11.1 Варианты использования сортировки....304

11.1.1 Планирование движений робота....304

11.1.2 Онкогеномика....305

11.2 Трудности сортировки во внешней памяти: пример....307

11.2.1 Двупутная сортировка слиянием во внешней памяти....308

11.3 Сортировка слиянием во внешней памяти (M/B-путная сортировка слиянием)....310

11.3.1 Поиск и сортировка: оперативная память по сравнению с внешней памятью....312

11.4 Как насчет внешней быстрой сортировки?....314

11.4.1 Двупутная быстрая сортировка во внешней памяти....315

11.4.2 На пути к многопутной быстрой сортировке во внешней памяти....315

11.4.3 Отыскание достаточного числа опорных точек....317

11.4.4 Отыскание достаточно хороших опорных точек....318

11.4.5 Сведение всего воедино....319

11.5 Немного математики: почему сортировка слиянием во внешней памяти оптимальна?....319

11.6 Подведение итогов....322

Резюме....322

Справочные материалы....324

Об иллюстрации на обложке....332

Предметный указатель....333

Стандартные алгоритмы и структуры при применении к крупным распределенным наборам данных могут становиться медленными — или вообще не работать. Правильный подбор алгоритмов, предназначенных для работы с большими данными, экономит время, повышает точность и снижает стоимость обработки.  Книга знакомит с методами обработки и анализа больших распределенных данных. Насыщенное отраслевыми историями и занимательными иллюстрациями, это удобное руководство позволяет легко понять даже сложные концепции. Вы научитесь применять на реальных примерах такие мощные алгоритмы, как фильтры Блума, набросок count-min, HyperLogLog и LSM-деревья, в своих собственных проектах.Приведены примеры на Python, R и в псевдокоде.

Основные темы:

• вероятностные структуры данных в виде набросков;
• выбор правильного движка базы данных;
• конструирование эффективных дисковых структур данных и алгоритмов;
• понимание алгоритмических компромиссов в крупно-масштабных системах;
• правильное формирование выборок из потоковых данных;
• вычисление процентилей при ограниченных пространственных ресурсах.