Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature Request: Eviction of an object happens immediately upon expiration #35

Open
pcman312 opened this issue Jun 8, 2017 · 4 comments

Comments

@pcman312
Copy link
Contributor

pcman312 commented Jun 8, 2017

Currently, the cache doesn't evict an object when the expiration of that object passes but rather waits until the next Get() call before evicting it. This is problematic when the object in the cache has connections/goroutines/etc. that should be closed when not in use. I propose restructuring the expiration code such that it evicts the object upon expiration rather than waiting for a subsequent Get() call.

@erwanor
Copy link
Contributor

erwanor commented Jun 12, 2017

It would be optimal indeed, do you have a specific strategy in mind. The current implementation does delay eviction until a later stage, but it has the advantage of being relatively standard and easy to maintain.

@pcman312
Copy link
Contributor Author

pcman312 commented Jun 12, 2017

I have a couple of ideas, but I'm not sold on any of them yet.
Note: all of these options have the need to deal with mutexes on the cache since a separate goroutine would be editing the contents of the cache.

  • Idea 1: When an object is put into the cache, spawn a goroutine that sleeps until the expiration happens and then evict it.

    • Pros: Simple to understand and implement
    • Cons: Spawns a ton of extra goroutines. Cursory research online suggests that the only cost is memory usage. One source suggests 4-4.5KB per routine. If you have 1,000,000 objects in the cache, you'd end up using ~4-4.5 GB of extra memory. This is not ideal.
  • Idea 2: This one is a bit less fleshed out in terms of the details, but we could have a single goroutine that monitors the cache and evicts items that are expired.

    • Idea 2A: Create a goroutine that looks at a sorted (by expiration time) list of items in the cache and evict the ones that need to be. The routine could poll every X seconds (I'd want to make this configurable with a default value) and then just look at the top of that sorted list and evict as needed.
      • Pros: Fairly simple to understand. Uses far less memory than option 1
      • Implementation is a bit more complicated due to the need to keep a sorted slice of the elements in the cache. Accounting of that data is also important since we'd need to keep both a map of the data (for quick lookups) and a slice (for evictions).
    • Idea 2B: Similar to 2A, we could have the goroutine look at the sorted list of objects for eviction, but instead of polling the cache every X seconds, it would look at the top item (A) on the eviction list and sleep until it needs to be evicted. The problem here is that if another item (B) comes into the cache and needs to expire before A does, that sleep would need to be interrupted and reset. We could probably accomplish that with a time.Timer rather than using an actual time.Sleep.
      • Pros: More efficient than 2A
      • Cons: More difficult to achieve because it has to be smarter around its sleeps rather than just doing a constant sleep all the time.

Ideally I'd prefer option 2B, but I'm not entirely sure of how practical it is to achieve.

@pcman312
Copy link
Contributor Author

Another option is to change the eviction from evicting object A when querying object A to evicting all objects that need eviction when querying any object. Basically change it to a more global approach on eviction rather than an object-by-object basis. I'm not a huge fan of this for my particular use cases since the query load on the cache is relatively low. This approach works better for a higher load cache.

@kogan69
Copy link

kogan69 commented Oct 1, 2017

@pcman312 @aaronwinter
I vote for 2A.
I'd also like to suggest to extend the simple cache with the following optional feature - every time when the item is accessed, its expiration time is extended automatically. It could be configured through the builder, of course.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants