Provide a way to use different storage for legacy migration

It would be nice to be able to move to a new storage backend when migrating to the new format.

This adds a `:legacy_storage` option to do that.