
Условие
Кэш превращает миллион запросов в секунду в пятьдесят тысяч к базе. Вся задача — удержать это соотношение, когда узел добавили, узел потеряли, кластер поднялся пустым или истёк горячий ключ.
Спроектируйте распределённый кэш в памяти.
Приложение кладёт значение по ключу и читает его обратно. У ключа есть срок жизни. Когда память кончается, кэш сам решает, что выбросить. Кластер переживает потерю узла и добавление нового без остановки.
Считайте, что:
- за кэшем стоит база, которая выдерживает до 100 тыс. запросов в секунду, но не миллион;
- узлы добавляют и выводят из кластера в обычном режиме эксплуатации;
- значение можно потерять: кэш не источник истины;
- есть ключи, которые читают на порядки чаще остальных.
Вне границ: структуры данных сверх строк, серверные скрипты, персистентность как гарантия, транзакции и подписка на события.
Требования
Функциональные 5
- Запись и чтение значения по ключу
- Срок жизни ключа, после которого он перестаёт отдаваться
- Удаление ключа по требованию приложения
- Вытеснение при нехватке памяти без участия приложения
- Добавление и вывод узла без остановки кластера
Нефункциональные 5
- Чтение: 99-й процентиль задержки (p99) < 1 мс внутри дата-центра при 1M операций/с и 200M ключей
- Поток запросов к базе не выше её предела в 100 тыс./с при потере одного узла и при холодном старте кластера
- Запрос к недоступному узлу завершается не позже чем через 10 мс (ответом или признаком недоступности), остальные ключи кластер обслуживает как прежде
- Добавление узла к десяти рабочим узлам кольца переносит не более 12% ключей
- Перекос нагрузки между узлами не более 20% при равномерных ключах
Задачи того же уровня
СредняяСчётчик просмотров объявленийЗадача выглядит как «прибавить единицу» и на этом ловит. Настоящий вопрос — что считать: обновление страницы, человека или человека за сутки. От ответа зависит, уместится ли счёт в 800 МБ или потребует терабайт.
СредняяТаблица лидеров сезонаместо каждого из 400 миллионовПока таблица помещается в один узел, место игрока — одна команда. На 400 миллионах игроков таблицу режут на шарды, и позиция игрока в своём шарде уже ничего не говорит о его месте в сезоне. Как ответить «какое я место» каждому из 400 миллионов, пока результаты идут по сто пятьдесят тысяч в секунду, — вся задача.
СредняяGoogle Calendarсобытия, повторы и часовые поясаНесколько сотен записей в секунду — масштаб здесь ничего не решает. Решает время: повторяющееся событие нельзя развернуть заранее, а событие в 10:00 по местному времени и в 07:00 UTC — не одно и то же дважды в год.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




