I'd make it be an append-only log + some sort of kafka style compaction. So for example you can tell it to compact all the parts of the log involving that file

I'd make it be an append-only log + some sort of kafka style compaction. So for example you can tell it to compact all the parts of the log involving that file you've deleted. Create + Delete compacts to a no-op.