I suppose there's always the approach of running the thing like a DB, as in you don't care about the representation of data being the same and liberally mark pa

I suppose there's always the approach of running the thing like a DB, as in you don't care about the representation of data being the same and liberally mark parts as "unused", compacting once in a while. But then the integrity check & delta update code of your distribution platform needs to understand that too. You wouldn't even need Linux extensions for that. You just do it like ZIP (or multisession CD-R, whatever) and put a new directory at the end. Just don't ask about streaming.