System Design: backend
Сегодня разберём задачу, которую мне давали на собесе в Яндекс. Штука на стыке проектирования и алгоритмов: мало накидать красивую схему на доске — надо ещё нормально объяснить, как данные поедут через систему. И вот тут сразу видно, шаришь ты или просто заучил модные слова.
Условие такое. Надо забэкапить данные — до терабайта. При сжатии они ужмутся где-то в полтора-три раза. Хранилище, куда мы всё складываем, принимает файлы не больше 100 мегабайт за раз. Нужно собрать конвейер: прочитать данные, сжать, записать. И главный подвох, вокруг которого вся задача: целиком в память это не влезет.
Первое, что приходит в голову, — «читаем файл, жмём, отправляем». И это ловушка. Терабайт в оперативку просто не поместится, так что про «прочитать файл целиком» надо забыть сразу. Задача с самого начала не про файл, а про поток: данные текут через тебя, ты хватаешь их по кусочку, обрабатываешь и отпускаешь — и никогда не держишь всё разом.
Но прежде чем что-то проектировать, я бы задал интервьюеру один вопрос. Как по мне, ради него задачу и придумали. Что делать, если данные сожмутся хуже обещанного, и очередной сжатый кусок всё равно вылезет за 100 мегабайт? Полтора-три раза — это как средняя температура по больнице, а не гарантия. Попадётся кусок, который жмётся плохо (уже сжатое видео, случайный мусор), — и он не влезет в лимит. Если ты сам спотыкаешься об этот момент, до того как тебя носом ткнули, — считай, полдела сделал: дальше этот вопрос всё равно вылезет. Заодно спроси, нужна ли параллельность и надо ли уметь продолжить с места обрыва, если всё грохнется на середине.
Теперь как оно работает внутри. Читаем данные небольшими порциями, каждую жмём и отправляем в хранилище куском не больше лимита. Получается конвейер из трёх шагов: читаем, жмём, отправляем. И логично, чтобы шаги крутились не по очереди, а разом — пока один кусок улетает в хранилище, следующий уже читается, а средний в это время жмётся. Само сжатие — самое прожорливое место, так что его можно раскидать на несколько потоков и жать куски параллельно.
И вот тут вылезает тонкость, которую многие упускают. Читать почти всегда быстрее, чем отправлять по сети. Если читать на полной скорости, а отправка не поспевает, то непрожатые куски начнут копиться в памяти — и привет, мы вернулись ровно к той беде, от которой бежали: память забита под завязку. Поэтому между шагами ставим очередь ограниченного размера. Забилась — чтение притормаживает и ждёт, пока отправка разгребёт накопленное. По сути система сама себя придушивает под нагрузкой и не даёт быстрой части захлебнуть медленную.
Вернёмся к главному вопросу — про плохое сжатие. Ответ «ну возьмём кусок поменьше» не катит: это отмашка, а не решение. По-нормальному — не фиксить размер куска намертво, а подстраивать. Не влез после сжатия — уменьшаем входную порцию и пробуем ещё раз. Или наоборот: сразу берём порцию с запасом, с расчётом на самый паршивый случай, чтобы результат влез при любом раскладе. Оба варианта живые, суть в том, что ты вообще про это подумал, а не понадеялся, что «да обычно нормально жмётся».
И ещё пара штук, которые отличают продуманное решение от учебного. Первая — контрольная сумма на каждый кусок. Иначе бэкап может тихо побиться, а узнаешь ты об этом в самый неподходящий момент — когда полез восстанавливаться, а там каша. Вторая — уметь продолжить с последнего нормально записанного куска, а не гнать терабайт по новой из-за обрыва на 90%. Для этого достаточно отмечать, что уже доехало.
Если коротко: тут смотрят, думаешь ли ты про неудобные случаи заранее, и дошло ли до тебя, что «не влезает в память» — это про потоковую обработку, а не про поиск хитрого способа всё равно запихнуть всё целиком. Разложил историю с плохим сжатием на конкретное решение — задача твоя.
Подписаться: @codeof_art
Вступить в чатик: @code_of_art
Сегодня разберём задачу, которую мне давали на собесе в Яндекс. Штука на стыке проектирования и алгоритмов: мало накидать красивую схему на доске — надо ещё нормально объяснить, как данные поедут через систему. И вот тут сразу видно, шаришь ты или просто заучил модные слова.
Условие такое. Надо забэкапить данные — до терабайта. При сжатии они ужмутся где-то в полтора-три раза. Хранилище, куда мы всё складываем, принимает файлы не больше 100 мегабайт за раз. Нужно собрать конвейер: прочитать данные, сжать, записать. И главный подвох, вокруг которого вся задача: целиком в память это не влезет.
Первое, что приходит в голову, — «читаем файл, жмём, отправляем». И это ловушка. Терабайт в оперативку просто не поместится, так что про «прочитать файл целиком» надо забыть сразу. Задача с самого начала не про файл, а про поток: данные текут через тебя, ты хватаешь их по кусочку, обрабатываешь и отпускаешь — и никогда не держишь всё разом.
Но прежде чем что-то проектировать, я бы задал интервьюеру один вопрос. Как по мне, ради него задачу и придумали. Что делать, если данные сожмутся хуже обещанного, и очередной сжатый кусок всё равно вылезет за 100 мегабайт? Полтора-три раза — это как средняя температура по больнице, а не гарантия. Попадётся кусок, который жмётся плохо (уже сжатое видео, случайный мусор), — и он не влезет в лимит. Если ты сам спотыкаешься об этот момент, до того как тебя носом ткнули, — считай, полдела сделал: дальше этот вопрос всё равно вылезет. Заодно спроси, нужна ли параллельность и надо ли уметь продолжить с места обрыва, если всё грохнется на середине.
Теперь как оно работает внутри. Читаем данные небольшими порциями, каждую жмём и отправляем в хранилище куском не больше лимита. Получается конвейер из трёх шагов: читаем, жмём, отправляем. И логично, чтобы шаги крутились не по очереди, а разом — пока один кусок улетает в хранилище, следующий уже читается, а средний в это время жмётся. Само сжатие — самое прожорливое место, так что его можно раскидать на несколько потоков и жать куски параллельно.
И вот тут вылезает тонкость, которую многие упускают. Читать почти всегда быстрее, чем отправлять по сети. Если читать на полной скорости, а отправка не поспевает, то непрожатые куски начнут копиться в памяти — и привет, мы вернулись ровно к той беде, от которой бежали: память забита под завязку. Поэтому между шагами ставим очередь ограниченного размера. Забилась — чтение притормаживает и ждёт, пока отправка разгребёт накопленное. По сути система сама себя придушивает под нагрузкой и не даёт быстрой части захлебнуть медленную.
Вернёмся к главному вопросу — про плохое сжатие. Ответ «ну возьмём кусок поменьше» не катит: это отмашка, а не решение. По-нормальному — не фиксить размер куска намертво, а подстраивать. Не влез после сжатия — уменьшаем входную порцию и пробуем ещё раз. Или наоборот: сразу берём порцию с запасом, с расчётом на самый паршивый случай, чтобы результат влез при любом раскладе. Оба варианта живые, суть в том, что ты вообще про это подумал, а не понадеялся, что «да обычно нормально жмётся».
И ещё пара штук, которые отличают продуманное решение от учебного. Первая — контрольная сумма на каждый кусок. Иначе бэкап может тихо побиться, а узнаешь ты об этом в самый неподходящий момент — когда полез восстанавливаться, а там каша. Вторая — уметь продолжить с последнего нормально записанного куска, а не гнать терабайт по новой из-за обрыва на 90%. Для этого достаточно отмечать, что уже доехало.
Если коротко: тут смотрят, думаешь ли ты про неудобные случаи заранее, и дошло ли до тебя, что «не влезает в память» — это про потоковую обработку, а не про поиск хитрого способа всё равно запихнуть всё целиком. Разложил историю с плохим сжатием на конкретное решение — задача твоя.
Подписаться: @codeof_art
Вступить в чатик: @code_of_art