Fastest key-value store for random disk reads?
Without context, this is a poor question. 

Bound to a single machine your requirement is a function of IO performance, not platform. An Access mdb file on a FusionIO card could outperform Trinity on a 5400rpm drive in a narrow band of tests.

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.