Break out a MessageStore interface.

The sole implementation, for now, is the existing in-memory/map-based
one.