Add metadata for state backups.

This is part of my effort to split up the work for backups into a few smaller patches.
And please use NotFoundError when appropriate.