
Условие
Файл правится на трёх устройствах, часть из них была офлайн, и все обязаны прийти к одному состоянию, не потеряв ничью правку молча. Нерв задачи: найти изменения среди десятков тысяч файлов и не гонять по сети мегабайты ради небольшой правки.
Спроектируйте облачный диск с синхронизацией папки между устройствами.
Пользователь кладёт файлы в папку на ноутбуке, и они появляются на телефоне и на втором компьютере. Правка на любом устройстве расходится на остальные. Устройство может быть выключено или без сети сколько угодно долго, а потом догнать.
Считайте, что:
- один и тот же файл могут изменить на двух устройствах, пока оба офлайн; - типичная правка документа затрагивает около 10% файла; - устройство хранит локальную копию и должно работать без сети; - у пользователя десятки тысяч файлов, и сравнивать их все при каждой синхронизации нельзя.
Совместное редактирование в реальном времени, предпросмотр документов, поиск по содержимому и корпоративные права доступа в задачу не входят.
Требования
Функциональные 6
- Синхронизация папки между устройствами одного пользователя: правка на любом устройстве доходит до остальных
- Работа офлайн с досинхронизацией после появления сети
- Разрешение конфликта при одновременной правке на двух устройствах: обе версии сохраняются
- Загрузка и скачивание файлов
- Переименование и перемещение файлов и папок
- Общий доступ к файлу по ссылке
Нефункциональные 4
- Ни одна правка не теряется молча: каждый конфликт виден пользователю
- Изменение доходит до другого онлайн-устройства за p99 < 10 с
- Устройство после недели офлайн (около 140 изменений при 50 000 файлах) догоняет состояние за p99 < 30 с на канале 20 Мбит/с
- Типичная правка документа в 1 МБ передаёт по сети не больше ~150 КБ
Задачи того же уровня
СложнаяСовместное редактирование документаДвести тысяч операций в секунду здесь не проблема, и рассылка правок почти не множит трафик. Вся задача в том, что две правки одного диапазона текста — это не гонка, а обычный режим работы, и его надо спроектировать, а не предотвратить.
СложнаяТоп-K по потоку событийЕсли каждый узел считает свой топ-100 и результаты складываются, ответ может оказаться неверным при безупречных логах. Задача про условия, при которых частичные результаты складываются.
СложнаяЦифровой кошелёкмиллион переводов в секунду между разделамиВнутренний кошелёк, в котором перевод связывает два произвольных счёта, а в пик их миллион в секунду. Нерв задачи — перевести деньги между счетами на разных узлах так, чтобы они не появились из ниоткуда и не пропали.
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




