репликация

Статьи

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

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

2 задачи

Задачи

Кто может стать лидером Пары реплик Список покупок на двоих Что зафиксировано Слить правки без сервера

Часто рядом

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