0

I require a data structure which satisfies the following properties:-

  1. Get max in O(1)
  2. Insert in O(log n)
  3. Delete max in O(log n) (Bonus points on delete ANY in O(log n))
  4. Delete is ONLY called whenever a particular TTL (time to live) is crossed.

Operation 4 only needs to be eventually consistent, but a bounded time complexity would be very good nice to have.

1, 2 and 3 is the standard priority queue using the heap data structure. However short of implementing an eviction thread on my own, I do not see any way to implementing 4. I have two questions:

  • What is the best approach to implementing 4?
  • Is there an existing implementation in Java or any other JVM based lang that I can directly consume without writing the eviction policy myself?
Arunav Sanyal
  • 1,708
  • 1
  • 16
  • 36
  • You may want to check this out http://stackoverflow.com/questions/3802370/java-time-based-map-cache-with-expiring-keys – Shubham Chaurasia Jan 27 '17 at 10:46
  • @ShubhamChaurasia - Thanks for the post, it comes pretty close to my use case. However short of maintaining a priority queue of my own, this still does not solve my use case. Get max is not O(1) for a concurrenthashmap – Arunav Sanyal Jan 27 '17 at 10:54
  • Just be to clear? The key in the PQ is different form the TTL, right? If so, i'd just recommend a standard PQ + extra eviction like you already mentioned (just a sorted array/binary tree, key := time to expire). Ideally you could use a Fibonacci Heap & only flag items for deletion in the eviction thread and then only delete items that get touched during the reconstruction when deleteMIn is called on the fib heap. But I don't think it's necessarily worth the implementation effort – b.buchhold Jan 27 '17 at 11:18
  • 1
    What do you mean by TTL and what is its behaviour? – xrisk Jan 27 '17 at 11:20
  • 1
    @Rishav: TTL typically means "time to live." It's the amount of time that an item should remain in the queue. – Jim Mischel Jan 27 '17 at 15:11
  • @b.buchold - Yes the PQ key and TTL are different entities. – Arunav Sanyal Jan 27 '17 at 16:16

1 Answers1

1

Yes, a standard binary heap will give you your requirements except the delete any in O(log n).

You can implement a skip list priority queue that has O(1) get max, O(log n) insertion, O(1) delete max, O(log n) delete any.

Pairing heap has O(1) get max, O(1) insertion, amortized O(log n) delete max. You can implement O(log n) (again, amortized) remove any with an additional data structure.

In my experience, pairing heap is much easier to implement than skip list.

For eviction notification, I would recommend computing an eviction time, and using that as the key in the priority queue. Then, I use a timer to notify me when it's time to call remove.

  1. At program startup, initialize a nextRemovalTime value to hold the next time an item should be removed. Set the initial value far into the future. Set a timer that will notify you at that time.
  2. To add an item to the queue, compute the expiration time by adding the TTL to the current time. Then insert the item into the queue.
  3. Compare the nextRemovalTime with the removal time for the item at the head of the queue.
  4. If the item at the head of the queue is earlier than nextRemovalTime, then cancel the existing timer, set nextRemovalTime equal to the time the first node should be removed, and re-initialize the timer.

The idea here is that when the timer ticks, a background thread is created, and will remove the top item. And any other items whose time has expired. It then computes the new removal time and re-initializes the timer.

The drawback to that approach is that the priority queue data structure must be able to handle concurrent access. Typically that's a lock, unless you have a lock-free concurrent priority queue. It shouldn't be a problem, really, unless the queue is hit very frequently.

Another way to do it, if you're not terribly concerned about the queue growing too large, is to check for expired items whenever a new item is added or an existing item is removed. That is, insert becomes:

while (queue.peek().expirationTime < currentTime)
{
    queue.removeMax();
}
queue.insert(newItem);
Jim Mischel
  • 131,090
  • 20
  • 188
  • 351