Перейти к содержанию

Сложная

Распределённое KV-хранилище

Условие

Согласованность выбирается в каждом запросе, а реплики обязаны сойтись к одному содержимому, пока часть кластера всегда недоступна.

Спроектируйте распределённое хранилище пар «ключ — значение».

Приложение пишет значение по ключу, читает его и удаляет. Данные хранятся в трёх копиях на разных узлах, чтобы пережить потерю машин. Кластер работает, пока часть узлов недоступна, и продолжает принимать записи.

Считайте, что:

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

Вне границ: вторичные индексы, транзакции по нескольким ключам, запросы по диапазону и схема данных.

Требования

Функциональные 7

  • Запись, чтение и удаление значения по ключу
  • Хранение значения в трёх копиях на разных узлах
  • Уровень согласованности выбирается в каждом запросе
  • Приём записей при недоступности части реплик
  • Конкурентные независимые записи одного ключа не теряются молча
  • Добавление и вывод узлов без остановки кластера
  • Реплики сходятся к одинаковому содержимому после восстановления связи

Нефункциональные 6

  • Запись обычного уровня принимается, пока недоступны до двух из трёх копий ключа
  • Строгое чтение с двумя репликами после подтверждённой строгой записи с двумя подтверждениями возвращает её, пока недоступна не более чем одна копия из трёх; строгая запись при двух недоступных копиях отклоняется
  • Запись обычного уровня: 99-й процентиль задержки (p99) < 10 мс
  • Чтение обычного уровня: p99 < 10 мс
  • При 100k записей/с и 500k чтений/с потеря одного узла не выводит p99 запроса за 10 мс
  • Расхождение реплик после простоя узла до 2 суток устраняется не позже чем через 12 часов после его возвращения, без остановки записи

Задачи того же уровня

Решите задачу у доски

Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям