1

So I have a map from Key -> Struct

My key will be a devices IP address and the Value(Struct) will hold a devices IP address and a time which after that amount of time has elapsed will make the key-value pair expire and so be deleted from the map.

I am fairly new at this so was wondering what would be a good way to go about it.

I have googled around and seem to find a lot on time-based maps in Java only

EDIT

After coming across this I think I may have to create a map with items in it , and then have a deque in parallel with references to each elem. Then periodically call clean and if it has been in there longer than x amount of time delete it.

Is this correcto r can anyone suggest a more optimal way of doing it ?

Community
  • 1
  • 1
cxzp
  • 652
  • 2
  • 14
  • 28
  • It might be enough to clean the list on access (or even on insertion and just skip invalid entries in read operations). – urzeit Jul 22 '13 at 07:39

1 Answers1

1

I've used three approaches to solve a problem like this.

  1. Use a periodic timer. Once every time quantum, get all the expiring elements and expire them. Keep the elements in timer wheels, see scheme 7 in this paper for ideas. The overhead here is that the periodic timer will kick in when it has nothing to do and buckets have a constant memory overhead, but this is the most efficient thing you can do if you add and remove things from the map much more often than you expire elements from it.

  2. Check all elements for the shortest expiry time. Schedule a timer to kick in after that amount of time. In the timer, remove the expired element and schedule the next timer. Reschedule the timer every time a new element is added if its expiration time is shorter than the currently scheduled timer. Keep the elements in a heap for fast lookup of who needs to expire first. This has a quite large insertion and deletion overhead, but is pretty efficient when the most common deletion from the map is through expiry.

  3. Every time you access the map, check if the element you're accessing is expired. If it is, just throw it away and pretend it wasn't there in the first place. This could be quite inefficient because of all the calls to check timestamp on every access and doesn't work if you need to perform some action on expiry.

Art
  • 19,807
  • 1
  • 34
  • 60