S3 locality

Тут я хотел рассказать о каких-то челленджах в построении storage систем по типу S3. Обычно в таком духе я спрашиваю людей на собеседованиях, поэтому тут мысли вслух, любые совпадения случайны.

Всё понятно с корректностью -- храним метаданные транзакционно, чтобы ни дай бог ничего не потерять, Paxos нам в помощь, это много работы, но хотя бы понятно как сделать.

Диски хоть и дешёвые, но на масштабах S3 любая экономия байт уходит за миллионы/сотни миллионов долларов. S3 сжимает данные с помощью ZSTD https://news.ycombinator.com/item?id=32529412 и внутри скорее всего есть какой-нибудь Erasure Coding, чтобы не хранить дорогие копии.

Понятное дело, что когда вы загружаете данные, никто не будет сжимать или хранить в памяти весь файл, поэтому скорее всего данные как-то разбиваются на чанки по несколько мегабайт максимум, иначе было бы очень дорого поддерживать такую систему. Учитывая, что S3 спокойно утилизирует всю пропускную способность вашей сети, скорее всего эти чанки по несколько мегабайт независимы, то есть не надо знать результат декомпрессии предыдущего для следующего. Откуда дальше происходит несколько интересных размышлений:

* Есть свобода хранить чанки как угодно

* Чтобы избежать фрагментации, хочется их как-нибудь паковать в большие шарды (сотни мегабайт, гигабайты?)

* Упаковка также помогает процессам вида FSCK и garbage collection работать лучше и использовать меньше дисков, например, проверять на консистентность и удалять больше данных вместе, что снимает нагрузку

А дальше интересный вопрос, на который я и сам не знаю ответов: как лучше всего сделать упаковку? С одной стороны не хочется паковать блоки, которые должны быть скоро удалены с теми, кто никогда не должен удаляться, потому что иногда в упаковке шардов образуются дырки, с другой сделать что-то совсем простое не так тривиально. Без дырок не обойтись, но хотелось бы их поменьше. Я придумал только несколько небольших эвристик

* Хранить данные с похожим TTL в +-1 день вместе. Тем самым не образовывая много дырок

* Скорее всего некоторые пользователи или форматы файлов удаляются без TTL какими-нибудь человеческими усилиями. На них нужно писать предикторы с простыми линейными моделями

* Делать холодные данные холоднее, горячие горячее, например, выделить бюджет дисков, чтобы увеличивать размерность Erasure Coding и хранить ещё меньше байт для них.

Если кто-то знает литературу о упаковках и локальности в таких системах, напишите, я не нашёл.