Moved the Store interface to a real key/value store

The usual comment about overloading