Although I think it'll be fine even without a cache for most workloads (it's super easily indexed since the cardinality of random data is extremely high), I'm curious what cache setup you've got that it would take a minute to do a KV lookup — Memcached or Redis for example should be single digit milliseconds or better.