Well, what about SQLite? It’s public-domain(!), used in cell phones all over the planet, and known to be quite efficient. Maybe you could make that your primary backing-store. (Perhaps also this would eliminate the need for sorting?) Because SQLite is used in many resource-constrained situations, it has a lot of options for making efficient use of memory. (Here, I’m referring to the software itself, not just its Perl implementation ...)
(Quite seriously, “SQLite is another Swiss Army® knife of computer programming” ...)
A homebrew in-memory NRU caching scheme is fairly easy to construct in Perl ... if it turns out that you actually need one when using SQLite. (Find out, first.) A hashref can provide random access to strings, while a separate array of hashrefs (to the same Perl objects) provides for round-robin recycling: when the array has reached its arbitrarily-set limit, shift or pop an element off, delete the key from the hashref (you must do both!), then let the now-unreferenced data disappear into the gloom while you create another key, add a reference to it to the hash, and unshift or push another reference to the same thing onto the array. (The data-records now have a reference-count of 2, one from the hash, the other from the list, as they will for the duration.) It’s NRU = Not Recently Used, not LRU = Least Recently Used, but it’s all resident-memory, so, so what.