
Условие
Согласованность выбирается в каждом запросе, а реплики обязаны сойтись к одному содержимому, пока часть кластера всегда недоступна.
Спроектируйте распределённое хранилище пар «ключ — значение».
Приложение пишет значение по ключу, читает его и удаляет. Данные хранятся в трёх копиях на разных узлах, чтобы пережить потерю машин. Кластер работает, пока часть узлов недоступна, и продолжает принимать записи.
Считайте, что:
- в любой момент один-два узла из нескольких десятков недоступны или отстают: это штатный режим;
- разным обращениям нужна разная согласованность: профиль читают строго, счётчик просмотров как получится;
- двое могут записать один ключ одновременно, зная друг о друге и не зная;
- часам на разных машинах доверять нельзя.
Вне границ: вторичные индексы, транзакции по нескольким ключам, запросы по диапазону и схема данных.
Требования
Функциональные 7
- Запись, чтение и удаление значения по ключу
- Хранение значения в трёх копиях на разных узлах
- Уровень согласованности выбирается в каждом запросе
- Приём записей при недоступности части реплик
- Конкурентные независимые записи одного ключа не теряются молча
- Добавление и вывод узлов без остановки кластера
- Реплики сходятся к одинаковому содержимому после восстановления связи
Нефункциональные 6
- Запись обычного уровня принимается, пока недоступны до двух из трёх копий ключа
- Строгое чтение с двумя репликами после подтверждённой строгой записи с двумя подтверждениями возвращает её, пока недоступна не более чем одна копия из трёх; строгая запись при двух недоступных копиях отклоняется
- Запись обычного уровня: 99-й процентиль задержки (p99) < 10 мс
- Чтение обычного уровня: p99 < 10 мс
- При 100k записей/с и 500k чтений/с потеря одного узла не выводит p99 запроса за 10 мс
- Расхождение реплик после простоя узла до 2 суток устраняется не позже чем через 12 часов после его возвращения, без остановки записи
Задачи того же уровня
СложнаяРекламный аукцион и учёт показовВыбрать победителя из двух тысяч кандидатов за пятьдесят миллисекунд и не потратить чужой бюджет сверх согласованного. Точность и задержка здесь обе стоят денег, и размен между ними приходится называть числом.
СложнаяРекомендательная системаЛента рекомендаций на сто миллионов человек в сутки. Правильного ответа у неё нет, а система учится на данных, которые сама же породила.
СложнаяСбор метрик с миллиона серверовДесять миллионов точек в секунду — решаемая задача. Систему убивает число уникальных рядов: метка с идентификатором запроса порождает новые ряды быстрее, чем хранилище успевает их принимать.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




