Существует несколько доступных библиотек кеша, которые могут справиться с вашей ситуацией, записывая записи кеша на диск, если достигнут определенный порог. Хорошая стратегия - записывать записи на диск, которые находятся в аренде. Существуют также кэши, которые распределяют записи кэша по кластеру, сохраняя все в памяти.
Решением кеширования, которое я часто использую, является Infinispan: http://www.jboss.org/infinispan
Это быстрый, простой в использовании, масштабируемый и, безусловно, может решить вашу проблему.