Первая специализированная книга для алгоритмической подготовки с реализацией этих алгоритмов на языке Go. Содержит необходимые знания по используемым в Go структурам данных и идиомам, рассматривает алгоритмы поиска, сортировки, сжатия данных, различные аспекты обслуживания распределенных систем и недопущения конфликтов в их работе, а также криптографические алгоритмы и работу с цифровыми подписями. Книга рассчитана на разработчиков среднего уровня, а также читателей, уже знакомых с базовыми возможностями Go.
Для Go-разработчиков
.
Современный бэкенд от API баз данных до вставок на TypeScript
Современный бэкенд от API баз данных до вставок на TypeScript, от небольших утилит до криптографических модулей и процедур для ускорения ядра Linux невозможно представить себе без кода на языке Go.
В этой книге рассмотрены алгоритмы и их реализации на языке Go, относящиеся к следующим предметным областям:
- Понятие о структурах данных
- Поиск, сортировка и сжатие данных
- Алгоритмы достижения консенсуса
- Алгоритмы для распределенных систем
- Криптографические алгоритмы
- Создание и защита цифровых подписей
Артём Михайлов — опытный программист, специалист по высоконагруженным системам, в настоящее время работает в стартапе, занятым высоконагруженными приложениями, ранее работал в научном кластере «Иннополис», компаниях «МТС» и «Тензор». Постоянно делится своим опытом на Хабре, пишет статьи для корпоративных блогов «Росатом», «ВТБ», «VK», «IBS», «OTUS».
Книгу “Алгоритмы на языке Go” можно купить в нашем интенет-магазине.
Предисловие. 7
– Глава 1 –
Алгоритмы, сложности и структуры данных. 9
Структуры данных: массивы, списки, хеш-таблицы, деревья. 11
Массивы.. 11
Связные списки. 13
Хеш-таблицы.. 14
Деревья. 15
Структуры данных в Go. 18
Массивы и срезы в Go. 18
Связные списки в Go. 20
Хеш-таблицы (отображения) в Go. 22
Деревья в Go. 24
– Глава 2 –
Поиск, сортировка и сжатие данных. 28
Алгоритмы поиска. 28
Двоичный поиск. 28
Интерполяционный поиск. 30
Поиск Фибоначчи. 31
Алгоритмы сортировки. 33
Быстрая сортировка. 34
Сортировка слиянием.. 36
Пирамидальная сортировка. 37
Поразрядная сортировка. 39
Алгоритмы сжатия данных. 42
Алгоритм Хаффмана. 42
Алгоритм LZW… 45
Алгоритм Brotli 48
Алгоритм Snappy. 50
Алгоритмы поиска подстроки. 52
Алгоритм Кнута–Морриса–Пратта. 52
Алгоритм Бойера–Мура. 54
Алгоритм Рабина–Карпа. 57
Алгоритмы кратчайших путей. 59
Алгоритм Дейкстры.. 60
Алгоритм Беллмана–Форда. 65
Алгоритм A*: эвристический поиск. 68
Примеры использования алгоритмов кратчайшего пути. 72
Сравнение алгоритмов кратчайших путей. 73
Потоки в сетях. 73
Сети и потоки. 73
Задача о максимальном потоке: найти поток наибольшей величины.. 74
Алгоритм Форда-Фалкерсона. 74
Алгоритм Диница. 76
Применения. 79
Теорема о максимальном потоке и минимальном разрезе. 79
– Глава 3 –
Распределенные алгоритмы.. 81
Что делает распределенные системы сложными?. 82
CAP-теорема: фундаментальный компромисс. 83
Три свойства. 84
Теорема. 84
Почему нельзя всё сразу?. 84
А что с CA?. 85
Примеры систем.. 85
Критика и уточнения. 86
Модели согласованности. 86
Строгая согласованность (Strong Consistency / Linearizability) 86
Последовательная согласованность (Sequential Consistency) 87
Причинная согласованность (Causal Consistency) 87
Read Your Writes (прочитайте ваши записи) 87
Eventual Consistency (согласованность в конечном счете) 88
Eventual Consistency. 88
Разрешение конфликтов. 90
Кворумы: настраиваемая согласованность. 93
Окно несогласованности. 94
Практические паттерны.. 94
Saga — для распределенных транзакций. 94
Outbox — для надежной публикации событий. 96
Idempotency key — для идемпотентных операций. 97
Circuit breaker — для устойчивости. 98
– Глава 4 –
Алгоритмы консенсуса. 101
Что такое консенсус и зачем он нужен?. 101
Формальное определение. 102
Практические применения. 102
Невозможность: почему это так сложно?. 103
Проблема двух генералов. 103
Почему это невозможно?. 103
FLP-невозможность. 104
Интуиция доказательства. 105
Как жить с невозможностью?. 105
Paxos: алгоритм, изменивший всё. 106
Одна инстанция Paxos. 106
Номера предложений (proposal numbers) 107
Протокол: две фазы.. 107
Почему это работает?. 110
Пример выполнения. 110
Сценарий 1: простой случай. 110
Сценарий 2: конкурирующие proposers. 111
Проблема прогресса: дуэль proposers. 113
Multi-Paxos: от одного значения к журналу. 114
Практические соображения. 115
Недостатки Paxos. 116
Raft: консенсус для смертных. 116
Философия Raft 116
Роли и термы.. 117
Выбор лидера. 118
Репликация журнала. 120
AppendEntries RPC.. 120
Алгоритм follower’а. 121
Алгоритм лидера. 122
Log Matching Property: свойство сопоставления с журналом.. 124
Leader Completeness Property: свойство безопасности. 124
Почему лидер не коммитит записи прошлых термов напрямую?. 125
Кластерное членство: Joint Consensus. 125
Снэпшоты и компактификация журнала. 126
Клиентское взаимодействие. 127
Полный пример: минимальный Raft на Go. 127
Системы на Raft 133
Заключение. 133
– Глава 5 –
Распределенные транзакции. 134
ACID в распределенном мире. 134
Проблема атомарного коммита. 134
Two-Phase Commit (2PC) 135
Фаза 1: Prepare (голосование) 135
Фаза 2: Commit/Abort (фиксация) 135
Проблемы 2PC.. 136
Пример: перевод денег. 137
Three-Phase Commit (3PC) 137
Saga. 138
Оркестрация. 139
Хореография. 140
TCC: Try-Confirm-Cancel 140
Outbox Pattern: надежная публикация событий. 141
Таблица outbox. 142
Идемпотентность. 142
Сравним подходы.. 143
Когда что использовать?. 143
– Глава 6 –
Криптографические алгоритмы.. 144
От Цезаря до Тьюринга: краткая история шифров. 144
Фундаментальные понятия. 146
Симметричное шифрование. 147
Одноразовый блокнот: идеал, недостижимый на практике. 148
Потоковые и блочные шифры.. 149
Реализация AES на Go. 151
Асимметричное шифрование. 153
Хеш-функции: MD5, SHA-256, Blake2, Argon2. 157
Исторический путь: от CRC до Argon2. 158
Односторонность, коллизии и эффект лавины.. 160
Зачем нужны разные хеш-функции?. 161
MD5 — эпоха надежд и коллизий. 163
SHA-256 — надежный наследник. 164
Blake2 — быстрее, сильнее, современнее. 167
Argon2 — хеширование паролей на стероидах. 169
Выбор хеш-функции. 171
– Глава 7 –
Реализация цифровых подписей и протоколов безопасности. 174
Математическая сущность цифровых подписей. 174
Схемы подписей на эллиптических кривых. 175
Реализация Ed25519 в Go. 177
– Глава 8 –
Атаки на цифровые подписи. 178
Replay-атаки и временны́е метки. 178
Подмена контекста (context substitution) 178
Слепые подписи и их применение. 179
Пороговые подписи. 179
BLS-подписи и агрегация. 180
JWT и stateless-аутентификация. 181
Идея: зашифровать сессию в токене. 181
Анатомия JWT: три части. 182
Жизненный цикл JWT.. 182
Симметричная и асимметричная подпись. 184
Распространение публичного ключа: JWKS. 185
Теперь про уязвимости. 186
Атака Algorithm substitution. 186
Уязвимость None algorithm… 187
Слабые секреты HMAC.. 187
Атаки JKU и X5U.. 188
Предметный указатель. 189
