распределённые системы

Статьи

SYS Алгоритм Консистентное хеширование Распределяет ключи по серверам так, что при добавлении сервера переезжает лишь его доля. O(log(N·v)) на поиск сервера 1 задача SYS Алгоритм Рандеву-хеширование Каждый ключ уходит к серверу с наибольшим хешем пары «ключ, сервер»: равномерно, без таблиц, отказ сдвигает только ключи упавшего. O(N) на ключ 2 задачи SYS Структура данных Дерево Меркла Хеши хешей: отпечаток всего набора, поиск расхождений за несколько сравнений и доказательство из log n хешей. O(n) на построение, O(log n) на доказательство и его проверку 2 задачи SYS Приём Повтор с джиттером Пауза перед повтором растёт вдвое и выбирается случайно: клиенты расходятся во времени и не бьют по серверу волнами. O(1) на решение о паузе 2 задачи SYS Алгоритм Raft Реплицированный журнал на ненадёжных серверах: лидер, сроки, большинство; выдерживает падение меньшей половины. один круг сообщений до большинства на запись 2 задачи SYS Алгоритм Часы Лэмпорта и векторные часы Логические часы: одно число Лэмпорта согласовано с «случилось раньше», вектор по процессам отличает «раньше» от «параллельно». O(1) на событие у Лэмпорта, O(n) у векторных 2 задачи SYS Структура данных CRDT Данные, копии которых правят независимо и сливают в любом порядке: счётчики, множества, текст.

O(1) на операцию у счётчика и множества; вставка в текст — O(1) в среднем

2 задачи SYS Алгоритм Два случайных выбора Спросить двух случайных и выбрать менее занятого: самая полная корзина — ln ln n вместо ln n / ln ln n. O(d) на решение: узнать нагрузку d серверов 2 задачи

Задачи

Векторные отметки Кто может стать лидером Новый сервер в кольце Пары реплик Сверка реплик Список покупок на двоих Что зафиксировано Шторм повторов Лавина повторов Параллельные пары Слить правки без сервера Топ по частям

Часто рядом

в проде 8 собеседования 7 репликация 5 базы данных 5 балансировка 4 хеширование 4 случайность 3 кэширование 2 контроль версий 2 сети 2 распределённость 1 дерево 1