I'm not sure about the prefix querying like getByPrefix. Not every engine you'd want to connect this data store to is going to have a way to list keys by prefix. In fact since what you're doing is key-value storage most of the most efficient engines which you are most llikely to want to connect to this storage are not going to support that kind of query.
Topic on Talk:Requests for comment/DataStore
What engine do you have in mind? At a quick glance, this kind of searches is supported by MongoDB, Cassandra, CouchDB and DynamoDB.
Riak, Voldemort I'd expect, LevelDB, Kai, MemcacheDB, there are probably some others. Think, actual key-value databases rather than higher level NoSQL databases.
Ok, ignore LevelDB.
OK, rm LevelDB, while MemcacheDB and Kai are abandonware that nobody should use, what else? :)
Further, Riak supports prefix search while Voldemort doesn't have a reasonable PHP client at all so we don't need to cae about it at all.