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

Add option specifying how frequently to check if items have expired (performance) #28

Closed
jmdobry opened this issue Aug 14, 2013 · 6 comments
Assignees
Milestone

Comments

@jmdobry
Copy link
Owner

jmdobry commented Aug 14, 2013

In aggressive delete mode, this method eliminates a $timeout for every item in the cache and instead uses setInterval to sweep the cache for expired items. Setting this to 60000 for example, has the cache only checking for expired items once a minute, instead of the browser watching a timeout for every item in the cache.

Is it worth it to look into this?

@gosusnp
Copy link

gosusnp commented Aug 30, 2013

In that case, what do you think of keeping track of the expiration dates in a heap?

@jmdobry
Copy link
Owner Author

jmdobry commented Aug 30, 2013

Can you elaborate?

@gosusnp
Copy link

gosusnp commented Aug 30, 2013

Using a heap, you can keep track of the next expiring item.
It is then possible to avoid setting a timeout for every item and use a shorter interval to only check the next item that would expire.

@jmdobry
Copy link
Owner Author

jmdobry commented Aug 30, 2013

My initial thought was to simply iterate over the items in the cache and remove the expired items, but this could potentially result in a lot of wasted computing time. Using a heap would solve the wasted computing time problem, but introduces the overhead of maintaining the heap in sorted order based on expiration date. Like you said, each interval would do something like this:

var i = 0;
while (expirationHeap[0].isExpired) {
  this.remove(expirationHeap[0].key);
  i++;
}

if (i) {
  expirationHeap.splice(0, i);
}

Option 1 is the least completing. It does not require any extra data structures, but may waste CPU time because it's a dumb solution.

Option 2 introduces complexity, but delivers better performance.

Thoughts?

@gosusnp
Copy link

gosusnp commented Aug 30, 2013

I find option 2 to be more elegant.

If the number of the items stored grows, then with Option 1 each check would be more complex. I would say O(n) where n is the number of items.
Using Option 2, each check should more efficient since we check at most 1 item that would not be removed. The cost of maintaining the heap would be O(log (n)) on insertion and O(log (n)) on suppression.
However, if we want to use aggressive delete mode, we would run O(n) every seconds in Option 1 whereas with Option 2, we would have some O(log (n)) operation when and only when it is needed. Unless the expiration time is very short, Option 2 looks better.

Another option that might be worth considering is what is done in Redis. In general, it is a passive deletion and from time to time (10 times per seconds for Redis), a few keys are randomly checked for deletion. It is easier to implement and it avoids leaking expired cached items for too long.

@jmdobry
Copy link
Owner Author

jmdobry commented Sep 21, 2013

Slating this for the 2.0.0 release. #51

This was referenced Sep 21, 2013
@jmdobry jmdobry closed this as completed Oct 6, 2013
jmdobry added a commit that referenced this issue Oct 6, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants