
Условие
Двести тысяч операций в секунду здесь не проблема, и рассылка правок почти не множит трафик. Вся задача в том, что две правки одного диапазона текста — это не гонка, а обычный режим работы, и его надо спроектировать, а не предотвратить.
Спроектируйте совместное редактирование текстового документа.
Несколько человек открывают один документ и печатают одновременно. Каждый видит правки остальных почти мгновенно и видит, где стоят их курсоры. Человек может уйти в офлайн, продолжать печатать и вернуться. Историю документа можно отмотать назад.
Считайте, что:
- двое могут править один и тот же абзац в одну и ту же секунду, и обе правки обязаны выжить; - чужая правка появляется на экране не позже чем через 200 мс после того, как её автор отправил пачку; - клиент копит нажатия и отправляет их пачкой раз в 200 мс; в любой момент печатает около 15% открытых сессий; - соединение рвётся, а человек продолжает печатать офлайн до двух часов; - документ живёт годами и копит миллионы операций.
Таблицы и презентации, комментарии и предложения правок, права доступа как система, экспорт и поиск по документам в задачу не входят.
Требования
Функциональные 6
- Одновременное редактирование текста несколькими соавторами: обе параллельные правки одного абзаца сохраняются, у всех один и тот же итоговый текст
- Правка соавтора появляется у остальных без действий с их стороны
- Работа офлайн с последующей синхронизацией накопленных правок
- Курсоры и выделения соавторов видны в реальном времени
- История версий с возможностью вернуться к прошлому состоянию
- Документ с многолетней историей открывается и показывает текущий текст
Нефункциональные 5
- Чужая правка видна не позже чем через 200 мс после отправки пачки на p99
- Подтверждённая автору правка не теряется при отказе или перезапуске любого одного процесса
- Правки, набранные офлайн до 2 часов, не пропадают без ведома автора
- Открытие документа: p99 < 1 с при истории в миллионы операций
- После отказа процесса документ снова принимает правки не позже чем через 15 с
Задачи того же уровня
СложнаяТоп-K по потоку событийЕсли каждый узел считает свой топ-100 и результаты складываются, ответ может оказаться неверным при безупречных логах. Задача про условия, при которых частичные результаты складываются.
СложнаяЦифровой кошелёкмиллион переводов в секунду между разделамиВнутренний кошелёк, в котором перевод связывает два произвольных счёта, а в пик их миллион в секунду. Нерв задачи — перевести деньги между счетами на разных узлах так, чтобы они не появились из ниоткуда и не пропали.
СложнаяCoinKeeperучёт личных финансов с импортом из банкаСервис личных финансов: ручные доходы и расходы плюс импорт операций из банка. Нерв задачи — узкое место вне вашей системы, лимит банка, и две разные цены ошибки: ручная запись не должна потеряться, а импортированная — продублироваться.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




