Exemplary methods for managing cache based on approximate least recently used (LRU) cache entries include maintaining a distributed data structure (DDS) of data elements, each corresponding to a cache entry of a plurality of cache entries, wherein each data element can be atomically accessed by multiple threads. In response to a cache eviction request from a first thread, determining an approximately LRU cache entry among the cache entries based on values atomically accessed from a first subset of the DDS of data elements, wherein the first subset of the DDS is atomically accessed using an atomic instruction without acquiring a lock to prevent another thread from accessing the first subset of the DDS to determine other approximately LRU cache entries among the cache entries, while allowing a second thread accessing a second subset of the DDS substantially concurrently. Evicting the determined approximately LRU cache entry.