Insert object to a map with ttl

Question

I am trying to implement some kind of map with the following characteristics.

Every item should be removed after the time-to-live has elapsed (unless time-to-live is 0 and then the item does not expire) get, put, remove, size should all have a complexity of o(1) in average

I have called a thread inside a constructor that goes in a while(true) loop and check if the ttl has expired

the code of the thread

    class ttlWatchdog extends Thread {
    @SneakyThrows
    @Override
    public void run() {
        long timeToSleep ;
        System.out.println("Initiating Cleaner Thread..");
        while (true) {
            timeToSleep = checkExpiredKeys();//need to change it to a diffrent
            //System.out.println("thread will sleep for  " + timeToSleep + "msc" );
            Thread.sleep(timeToSleep);

        }
    }
    public long checkExpiredKeys() throws BadParameterException {

        // Just remove if timeToLive has been set before...
        long timeToWake = 0;
        long currentTime = System.currentTimeMillis();
        int counter =0 ;
        Set<Map.Entry<String, ObjectTimeStampPair> >s = valuesMap.entrySet().stream().filter(a-> a.getValue().getTtl()!=0).collect(Collectors.toSet());
        for (Map.Entry<String, ObjectTimeStampPair> e : s) {
            long timeItShouldRemove = e.getValue().getTtl();
            if ((currentTime ) >= timeItShouldRemove) {
                remove(e.getKey());
            }else {// we need to take the minimum for the while loop everything here is bigger than current time i need to find the minumum
                if (counter == 0 ){ // if it is the first element take it
                    timeToWake = e.getValue().getTtl();
                    counter ++;
                }
                else if (timeToWake > timeItShouldRemove){
                    timeToWake = timeItShouldRemove;
                }

            }
        }
        long result = timeToWake !=0 ? timeToWake -currentTime : 0 ;
        //System.out.print("the time to wake is " +  timeToWake + " the current time is " + currentTime + " and the result is " +   result);
        return result;

//

    }

my problem is with the while(true) which is not very efficient especially when the map is empty or it is full of object with unlimited ttl.

Hello and welcome to Stackoverflow! :-) You notice, that the use of while(true) may be inefficient. But what is your actual question? How to make this more efficient oder what other technology you could use? — Yeti, Nov 26 '21 at 12:07

zysaaa · Answer 1 · 2021-11-28T13:08:58.527

1

I think it is not a good design to use a thread to check continuously(use while true), it will consume a lot of resources.

You can consider another implementation: use a timer internally, such as a ScheduledExecutorService, and start a timing task at the same time when inserting data. For example, the survival time of a key is 5 seconds, then start a task to be executed after 5 seconds to delete the key.

You can take a look at expiringmap.

Edit, generally there are these ways, from Java time-based map/cache with expiring keys,

A. Perform a cleanup operation every time this map is used. For example, a thread calls map#size(), map#get(), map.put(). In addition, you can use another DelayQueue, which will be more efficient. Refer: https://gist.github.com/pcan/16faf4e59942678377e0 or PassiveExpiringMap

B. Use a watchdog to check, sleep for a while after each check. Refer:apache#mina-org.apache.mina.util.ExpiringMap.

C.Use a timer: expiringmap.

edited Nov 28 '21 at 13:08

answered Nov 26 '21 at 12:06

zysaaa

1,777
2
8
19

and what happens if someone changes the ttl after I scheduled a thread? – Shmuel Nov 28 '21 at 11:46
I don’t quite understand what you mean, I edited the answer, hope it help – zysaaa Nov 28 '21 at 13:10
I would like to use ScheduledExecutorService solution , but I have noticed a corner case in which I entered an object with key X with ttl of 1000 msc and after that I entered key X with ttl 30000 but the scheduler of ttl 1000 will still be executed after 1000 msc ... my solution is to cancel the scheduled thread when the map key gets override – Shmuel Nov 28 '21 at 13:55
Yes, you need to cancel and re-schedule – zysaaa Nov 28 '21 at 14:48

The Bartman · Answer 2 · 2021-11-26T21:12:49.017

1

Looks like use case for DelayQueue. This is an implementation of BlockingQueue.

A BlockingQueue will block a thread reading from the queue until an element is present.

For a very good explanation of BlockingQueue see https://youtu.be/d3xb1Nj88pw

DelayQueue is a special kind of BlockingQueue where elements in the Queue are only visible for the reading thread when a delay has expired.

See https://howtodoinjava.com/java/multi-threading/java-delayqueue/

edited Nov 26 '21 at 21:12

answered Nov 26 '21 at 20:01

The Bartman

156
2
5

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Nov 26 '21 at 20:26

Insert object to a map with ttl

2 Answers2