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

Средняя

Распределённый кэш

Условие

Кэш превращает миллион запросов в секунду в пятьдесят тысяч к базе. Вся задача — удержать это соотношение, когда узел добавили, узел потеряли, кластер поднялся пустым или истёк горячий ключ.

Спроектируйте распределённый кэш в памяти.

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

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

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

Вне границ: структуры данных сверх строк, серверные скрипты, персистентность как гарантия, транзакции и подписка на события.

Требования

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

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

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

  • Чтение: 99-й процентиль задержки (p99) < 1 мс внутри дата-центра при 1M операций/с и 200M ключей
  • Поток запросов к базе не выше её предела в 100 тыс./с при потере одного узла и при холодном старте кластера
  • Запрос к недоступному узлу завершается не позже чем через 10 мс (ответом или признаком недоступности), остальные ключи кластер обслуживает как прежде
  • Добавление узла к десяти рабочим узлам кольца переносит не более 12% ключей
  • Перекос нагрузки между узлами не более 20% при равномерных ключах

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

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

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