I want a key-value store, with records stored on disk. (There are too many for memory.) I want to use a single machine.
What key-value store will provide the fastest random reads (off disk)?
Without context, this is a poor question.
You'll have to be more specific if you want answers of any value.
Edit: following comment.
Context would be a description of what you're building. As I indicated, whichever k-v system you choose you will be IO bound when constrained to a single machine. On EC2 block storage the choice of k-v becomes even more irrelevant.
If you're building on EC2 look at the native products they already provide e.g. SimpleDB or Elasticache.