Возможно ли это без проблем с согласованностью.Какой популярный алгоритм сжатия лучше всего подойдет для этих целей?
Сжатая файловая система - самый простой способ сделать это. Вы можете включить сжатие в NTFS, ZFS или BTRFS, в зависимости от вашей ОС. Но сжатие не велико.
Быстрый алгоритм с гибким контейнером тоже подойдет. Zip кажется работоспособным: Как обновить один файл в zip-архиве