Используйте
memcached - этот сервис хранит данные в памяти и удаляет неиспользуемые.
Если в сессии есть данные, которые нужно хранить постоянно, дублируйте запись в базу данных и в memcached.
Если у пользователя кука ещё жива, а сессия на сервере уже удалилась, запросите её из базы и опять сохраните в кэш.
Вот приблизительно так: