I would like to store data persistently for my application, but I don't really need a full blown relational database. I really could get by with a basic "cache"-like persistent storage where the structure is just a (key, value) pair.
In lieu of a database what are my best, scalable options?
I ask a similar question recently. Here are some choices:
If your writing a java program that wants an imbedded database look at hsqldb since it is written in java and works much better then sqlite if being called from java programs.
I'm really not sure you should but have you considered just storing info in an XML doc if it really is that light? And if it's not have you considered SQLite?
You could try CounchDB, it is a very flexible document-oriented database that doesn't force you to define a schema up-front. It was written in Erlang and thanks to this it is considered very scalable solution. It can be easily queried through a REST interface.
If you need scalability, then a RDBMS is your best bet. At the most basic level, you can serialize data structures into files - however, then you'd need to account for file locking issues which would limit concurrency.
SQLite is an SQL file-based database engine, which can run without a persistent database daemon (in PHP for example, it runs as an extension), however it too has concurrency issues (read the answers to this question which could help you decide if SQLite is right for you).
Unless you have a really good reason not to use a real DRBMS, I'd suggest you stick with MySQL or other "full-blown" engines.