На что сменить MongoDB
Потому что 1 миллиард ключей — это уже 166 гигабайт. Вполне нормально для сервера с 256Гб. 
Но если по каждому ключу еще и данные хранить, то уже не впишемся по объему. У нас максимум 512Гб можно установить на мать. 
Можно, конечно, делать user-level sharding для redis или использовать memcached. Думаем теперь и над этим.

С другой стороны, весь миллиард хранить в памяти не надо совсем. Из него активных — 100 млн. максимум. А остальное все же хотелось бы хранить в бд. И если вдруг потребуется — быстро вычитать и положить в кэш.

Возможно, нам стоит перейти на другой тип БД? Нам нужна отложенная запись (только insert) и быстрое (не более 2 мс) чтение. SSD готовы поставить, лишь бы помогло. 
Ведь insert делается сначала в кэш. И все ноды забирают данные из кэша. Так что не особо важно, через сколько БД запишет данные. 
А вот минимальная задержка при кэш промахе очень важна.
Может кто Berkley DB пользовался на SSD? Расскажите тогда, как оно?
Find и insert нужны. Delete — вообще нет