We (Adroll) have been very happy with DynamoDB for use cases like this. Works fine with ~500B keys, while maintaining very low, and consistent, latencies.
+1 -- we also used DynamoDB at Adzerk for the same use case.
The alst 4 ads
Even then we need a fast lookup. 4 ads means 4 advertisers, 4 creative, 4 potentisl clicks, imps, mids/ends (video), conversions/ etc. There are also multiple cookies depending on which exchange the ad came from. Having to map them on the fly requires a fast and large datastore.
A cookie won't fit all that data and a more traditional database generally won't work. In memory k/v stores like Redis won't work due to data size (TBs of data). Hbase/Cassandra/etc sort of work with latency in the 5ms range. That's fairly expensive in a 90ms SLA, but you can make it work. It does limit the amount of work you are able to do.