Expiring map

[Rajanikanth Jammalamadaka]

Does somebody have a recommendation for an expiring dict? If I have to write my own, is there a way to avoid iterating over all the keys to delete the expired entries?

Thanks,

Raj

[Shawn Milochik]

On Wed, Jul 19, 2017 at 3:22 PM, Rajanikanth Jammalamadaka <rajan...@gmail.com> wrote:

Does somebody have a recommendation for an expiring dict? If I have to write my own, is there a way to avoid iterating over all the keys to delete the expired entries?

It's not expensive to get a read lock and iterate. That's what I usually do.

If you have few enough records you could kick off a goroutine for each with a timeout that would then delete the key. Probably a bad idea, but it could work.

You could put every newly-added key into a slice, and have an infinite loop which sleeps, reads from the list and purges anything expired and truncates the slice.

You can simply have the "get" function that pulls things out check the expiration and, if expired, delete it and return no result. This would bloat for unused keys, but you could combine it with one of the solutions above, or an infinite loop that grabs a random key every second (or less) to help prune.

[Jan Mercl]

On Wed, Jul 19, 2017 at 9:22 PM Rajanikanth Jammalamadaka <rajan...@gmail.com> wrote:

> Does somebody have a recommendation for an expiring dict? If I have to write my own, is there a way to avoid iterating over all the keys to delete the expired entries?

Common approach is to tag the entries with insertion or expiration time and remove invalid items only on retrieval. If there are not enough retrievals that keep the ratio of useful/expired map entries sane, a "cleaner" goroutine can be run concurrently.

--

-j

[Rajanikanth Jammalamadaka]

Thanks Shawn/Jan

[Jesper Louis Andersen]

A queue of keys stamped with the creation timestamp allows for dropping elements from the front easily. This makes the expiration cheap, but pays in memory resources. Jan's suggestion is subtly cheaper from a memory perspective, but pays with a bit more CPU cycles. Since this is just a simple queue, a ring buffer might be adequate.

Alternatively, you can consider using a LRU, 2Q or ARC cache[0], for instance github.com/hashicorp/golang-lru 

This can put an upper bound on the size of the data set and depending on your needs this might suit your application better: a sudden burst in insertion rates cannot accidentally overflow your systems memory, but will simply result in a system slowdown.

[0] 2Q caches often beat LRU caches. ARC caches are even better, but there are rumors around that the ghost-like feature of the ARC caches may have patents.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Bakul Shah]

Somewhat analogous to garbage collection via reference
counting (paying incremental cost) and occasional mark-and-sweep (for
things not caught by RC).

To avoid iterating over keys, on creation you can store
key+expiration time in a separate scheduling data structure
(which can be a ring buffer if all entries have the same life
time) but this will usually be less efficient and more
complicated.

[Sameer Ajmani]

We have a few implementations of this inside Google (expiring.Map, timedcache, and lru.Cache).  It might make sense to open source these, if they have no internal dependencies.

--

[Rajanikanth Jammalamadaka]

Thanks for the replies.

Sameer: it would be awesome if you can open source them.

Thanks,

Rajanikanth 

[DanB]

Rajanikanth,

If it helps you, have a look on the library we have posted which follows ideas out of implementation of groupcache/lru.go, adding expiring capabilities to LRU (same logic of list indexing behind):

https://github.com/cgrates/ltcache

DanB