Во-первых, я бы предположил, что ваше мнение об использовании базы данных для этого было бы слишком дорогим для хранения, является недействительным. Само хранилище дешево, и я сомневаюсь, что набор записей получит такой огромный. Кроме того, при правильной индексации эта таблица будет быстро доступна (и в основном это будет доступ для чтения с довольно уникальными ограничениями). Но это ваше решение, а не мое :) 1001 *
Одной из идей было бы использование файлов cookie - это было бы действительно очень легко, хотя у вас есть ограничение по размеру, с которым можно справиться, что может немного усложнить ситуацию.
Проблема с памятью (и memcache) заключается в том, что она не постоянна. При следующей загрузке среды приложения данные сбрасываются. Поэтому для постоянного хранения вам все еще нужна какая-то база данных или постоянная очередь (например, Redis).