Easily solved with SSDs. Sort the keys, value is stored right after the key. On each request do a binary search. It takes 32 seeks in the worst case. Even cur

Easily solved with SSDs. Sort the keys, value is stored right after the key. On each request do a binary search. It takes 32 seeks in the worst case. Even current consumer level SSDs can handle 45K IOPS, so you'd get 1400 complete searches/sec from one SSD. You might need to spread your data over 4 SSDs, but you can search in parallel, so it will even be faster. If you want more speed, replicate your drives and load balance. There are better ways (with perfect hash functions), but this is the easiest, and requires no additional storage.