Skip to content

Thread-safe, fixed-size, in-memory LRU cache that supports eviction, expiration, and out-of-band updates

License

Notifications You must be signed in to change notification settings

nathanjcochran/lru

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

24 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

lru

Build Status Coverage Status Go Report Card GoDoc license

A thread-safe, fixed-size, in-memory LRU cache that supports eviction, expiration, and out-of-band updates.

This cache is implemented as a lock-protected map whose values are elements in two doubly linked lists (unlike a traditional LRU, which only uses one). The first doubly linked list keeps track of upcoming evictions. It orders items by how recently they have been used. When an item is added to the cache, or retrieved via the Get method, it is moved to the front of this list. When an item needs to be evicted during a call to Add (because the cache is full), the item chosen for eviction is pulled from the back of this list.

The second doubly linked list keeps track of how soon items will expire. When items are added to the cache, they are added to the front of this list. A single worker goroutine - the "expiration worker" - reads from the back. If the item at the back is expired, it is removed from the cache. If it is not yet expired, the worker puts itself to sleep until it is scheduled to expire. Note that the worker may expire items early in order to avoid putting itself to sleep for very small amounts of time (configurable). A caveat of this design is that all items in the cache must share the same time-to-live (i.e. newly added items always expire after existing items).

If an update function is provided via SetUpdateFunc, expired items are queued in a channel by the expiration worker, rather than simply being removed from the cache (the default behavior). Updates are handled by a separate pool of worker goroutines - the "update workers". These workers read from the channel and call the user-provided update function with the key of an expired item. Depending on the value of the status flag returned, they either update the item with a new value, remove the item from the cache, or reset the item's time-to-live without updating its value. If the item is not removed from the cache, it is moved back to the front of the expiration list after the update. Its position in the eviction list is not changed. It is also possible to configure the cache to only update items if they have received a threshold number of hits since the last addition/update. This ensures that unused items are not needlessly incurring the cost of being updated.

Unit tests and benchmarks are provided.

For more information, see the documentation.

About

Thread-safe, fixed-size, in-memory LRU cache that supports eviction, expiration, and out-of-band updates

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages