To improve image cache management in their Android app, Grab engineers transitioned from a Least Recently Used (LRU) cache to a Time-Aware Least Recently Used (TLRU) cache, enabling them to reclaim storage more effectively without degrading user experience or increasing server costs.
The Grab Android app used Glide as its primary image loading framework, including an LRU cache to store images locally in order to reduce network calls, improve load times, and lower server costs. However, analytics showed that using a 100 MB LRU cache had significant shortcomings: it often filled up quickly for many users, leading to performance degradation, while in other cases images remained cached for months if the cache never exceeded the size limit, thus wasting storage.
To circumvent these limitations, they decided to extend LRU with time-based expiration. TLRU uses three parameters, Time To Live (TTL), which determines when a cache entry is considered expired; a minimum cache size threshold, which ensures essential images remain cached even when they expire if the cache is underpopulated; and maximum cache size, which enforces the upper storage limit.
Instead of implementing TLRU from scratch, Grab engineers chose to fork Glide and extend its DiskLruCache implementation, leveraging its “mature, battle-tested foundation”
This implementation is widely adopted across the Android ecosystem and handles complex edge cases like crash recovery, thread safety, and performance optimization that would require substantial effort to replicate.
DiskLruCache needed to be extended along three dimensions by adding support for tracking last-access time, implementing time-based eviction logic, and including a migration mechanism for existing user caches.
Last-access times were required to sort cache entries by their most recent access and had to be persisted across app restarts. The time-based eviction logic ran on each cache access to check if the least recently accessed entry has expired before removing it. For existing cache migration, the main challenge was assigning last-access timestamps to LRU entries. Since filesystem APIs did not provide a reliable source, Grab engineers decided to assign the migration timestamp to all entries:
This approach preserves all cached content and establishes a consistent baseline, although it necessitates waiting one TTL period to realize the full benefits of eviction. We also ensured bidirectional compatibility – the original LRU implementation can read TLRU journal files by ignoring timestamp suffixes, enabling safe rollbacks if needed.
Another challenge was finding optimal configuration values, which was based on controlled experiments.
Our success criteria is for a cache hit ratio decrease of no more than 3 percentage points (pp) during the transition to TLRU. For instance, a decrease from 59% to 56% hit ratio would result in 7% increase in server requests. This threshold balances storage optimization with acceptable performance impact.
Using this approach, 95% of the app users saw a 50MB reduction in cache size, with the top 5% seeing even larger savings. Based on these results, Grab engineers estimated that they could reclaim terabytes of storage across devices while maintaining the cache hit ratio within acceptable limits and without increasing server costs.
The original post provides highly valuable detail on LRU behavior and TLRU implementation than can be covered here. Make sure you read it to get the full detail.
