6
\$\begingroup\$

The following code is in-memory repository that stores key/value pairs. It will be used on our server to keep information about active clients. Clients send keepalive messages to indicate that them are active. Important point: the information of inactive (expired) clients should be removed from repository ASAP. A client sends keepalive message every 30 seconds and I expect 1000 clients connected.

The methods usage:

  • put - adds new client (registration)
  • touch - updates client "last seen time" (keepalive)
  • remove - removes client (client leaves)
  • get - looks for client with given client's ID

I would like to get feedback on:

  • Coding style
  • Possible performance problem
  • Suggestions for improvement.

Thanks in advance.

import java.util.AbstractMap.SimpleEntry;
import java.util.HashMap;
import java.util.Objects;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;


public class ExpiringKeyValueRepository<K, V> {

    final public static long MAX_LIVE_TIME = Long.MAX_VALUE;

    private Node<K, V> first = null;
    private Node<K, V> last = null;

    private long timeToLive;

    private ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();

    private Lock writeLock = rwLock.writeLock();
    private Lock readLock = rwLock.readLock();

    private Condition checkCondition =  writeLock.newCondition();

    private HashMap<K, Node<K, V>> map = new HashMap<>();
    private Cleaner<K, V> cleaner = new Cleaner<>(this);
    private Thread cleanerThread = null;

    /**
     * Constructs an empty repository with the given live time period of stored elements
     * 
     * @param timeToLive the live time in milliseconds
     * 
     * @throws IllegalArgumentException if given live time is zero or negative
     */
    public ExpiringKeyValueRepository(long timeToLive) 
    throws IllegalArgumentException {

        if (timeToLive <= 0)
            throw new IllegalArgumentException();

        this.timeToLive = timeToLive;
    }

    /**
     * Starts the repository.
     * Call of this method on already running 
     * repository has no effect
     */
    synchronized public void start() {

        if (cleaner.isRunning())
            return;

        cleanerThread = new Thread(cleaner);
        cleaner.stopped = false;
        cleanerThread.start();  
    }

    /**
     * Stops the repository. The method also removes
     * all stored entries. Call of this method on already 
     * stopped repository has no effect
     */
    synchronized public void stop() {

        if (!cleaner.isRunning())
            return;

        try {
            cleaner.stop(); 
            cleanerThread.join();
        } catch (InterruptedException e){};

        reset ();
    }

    /**
     * Adds the given key/value mapping to this repository 
     * if the repository doesn't contain mapping for the given key
     *  
     * @param key the key
     * @param value the value
     * 
     * @return true if this repository did not already 
     *              contain mapping for the specified key
     * 
     * @throws NullPointerException if either key or value is null
     * @throws IllegalStateException if repository is not running
     */
    public boolean put(K key, V value) 
    throws NullPointerException, IllegalStateException {
        
        if (!cleaner.isRunning())
            throw new IllegalStateException();
        
        Objects.requireNonNull(key);
        Objects.requireNonNull(value);

        writeLock.lock();

        try {

            Node<K, V> node = map.get(key);

            if (node == null) {
                linkLast(key, value);
                map.put(key, last);
                return true;
            } 
            
            return false;
            
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    
    /**
     * Updates expiration time of entry mapped to the given key
     * 
     * @param key the key
     * 
     * @return true if mapping for given key found
     * 
     * @throws IllegalStateException if repository is not running
     */
    public boolean touch(K key)  throws IllegalStateException {
        
        if (!cleaner.isRunning())
            throw new IllegalStateException();
        
        Objects.requireNonNull(key);
        
        writeLock.lock();
        try {
            Node<K, V> node = map.get(key);
            
            if (node == null) 
                return false;
                
            node.updateExpirationTime(timeToLive);
            moveToEnd(node);
            checkCondition.notify();
            
            return true;
            
        } finally {
            rwLock.writeLock().unlock();
        }   
    }

    /**
     * Returns the value with which the given key is associated.
     * If this repository contains no mapping for the key or entry 
     * is expired then the method returns null. 
     * 
     * @param key the key
     * 
     * @return the value with which the given key is associated, returns null 
     *         if no mapping for the key or entry is expired
     *         
     * @throws IllegalStateException if repository is not running
     */ 
    public V get(K key) throws IllegalStateException {
        
        if (!cleaner.isRunning())
            throw new IllegalStateException();

        readLock.lock();

        try {

            Node<K, V> node = map.get(key);
            return node == null || node.isExpired() ? null : node.getValue();

        } finally {
            readLock.unlock();
        }
    }

    /**
     * Removes the association for the given key
     * 
     * @param key the key whose mapping is to be removed
     * 
     * @return the previous value associated with key, 
     *         or null if there was no mapping for key
     *         
     * @throws IllegalStateException if repository is not running
     */
    public V remove(K key) throws IllegalStateException {

        if (!cleaner.isRunning())
            throw new IllegalStateException();
        
        rwLock.writeLock().lock();

        try {

            V value = removeNoLock(key);
            checkCondition.notify();
            return value;

        } finally {
            rwLock.writeLock().unlock();
        }
    }

    private void reset () {
        first = last = null;
        map.clear();
    }

    private V removeNoLock(K key) {

        if (!cleaner.isRunning())
            throw new IllegalStateException();

        final Node<K, V> node = map.remove(key);

        if (node == null)
            return null;

        unlink(node);
        return node.getValue();
    }

    private void linkLast(K key, V value) {

        final Node<K, V> node = new Node<K, V>(key, value, timeToLive);
        linkLast(node);
    }

    private void linkLast(Node<K, V> node) {

        if (!cleaner.isRunning())
            throw new IllegalStateException();

        node.setLinks(last, null);
        last = node;

        if (last.prev == null)
            first = node;
        else
            last.prev.next = node;
    }

    private Node<K, V> unlink(Node<K, V> node) {

        if (!cleaner.isRunning())
            throw new IllegalStateException();

        if (first == null)
            return null;

        final Node<K, V> prev = node.prev;
        final Node<K, V> next = node.next;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            node.prev = null; // Help GC
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            node.next = null; // Help GC
        }

        return node;
    }

    private void moveToEnd(Node<K, V> node) {

        if (first == null)
            return; // should not be here

        if (first == last)
            return;

        unlink(node);
        linkLast(node);
    }

    private static class Node<K, V> extends SimpleEntry<K, V> {

        private static final long serialVersionUID = 1L;

        private Node<K, V> prev = null;
        private Node<K, V> next = null;

        private long expirationTime;

        private Node(K key, V value, long liveTime) {
            super(key, value);
            updateExpirationTime(liveTime);
        }

        private Node(Node<K, V> prev, Node<K, V> next, K key, V value, long liveTime) {
            this(key, value, liveTime);
            setLinks(prev, next);
        }

        private void setLinks(Node<K, V> prev, Node<K, V> next) {
            this.prev = prev;
            this.next = next;
        }

        private long timeTillExpiraton() {
            return expirationTime - System.currentTimeMillis();
        }

        private boolean isExpired() {
            return expirationTime - System.currentTimeMillis() <= 0;
        }

        public void updateExpirationTime(long liveTime) {
            expirationTime = System.currentTimeMillis() + liveTime;
        }
    }


    private static class Cleaner<K, V> implements Runnable {

        private ExpiringKeyValueRepository<K, V> rep;
        private boolean stopped = true;

        private Lock writeLock;
        private Condition checkCondition;

        private Cleaner(ExpiringKeyValueRepository<K, V> repository) {
            this.rep = repository;
            this.writeLock = repository.writeLock;
            this.checkCondition = repository.checkCondition;
        }

        @Override
        public void run() {

            writeLock.lock();
            
            try {

                while (!stopped) {

                    while (rep.first != null && rep.first.isExpired()) {
                        rep.removeNoLock(rep.first.getKey());
                    };

                    long timeToWait = rep.first == null ? MAX_LIVE_TIME : rep.first.timeTillExpiraton();
                    try {
                        checkCondition.await(timeToWait, TimeUnit.MILLISECONDS);
                    } catch (InterruptedException e) {} ;
                }


            } finally {
                writeLock.unlock();
            }
        }

        private void stop() {

            writeLock.lock();
            try {

                if (!stopped) 
                    stopped = true;

            } finally {
                writeLock.unlock();
            }
        }

        private boolean isRunning () {
            return !stopped;
        }
    }

}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Nice implementation, the code is well commented and easy to understand. My suggestions:

Design

Node keeps two pointers for the previous and the next. The repository also keeps two pointers for the first and last node. I think that is because HashMap is not ordered. Have you considered using LinkedHashMap? It keeps the insertion order so the oldest nodes are always on top and you don't need to do all the linking/unlinking.

To update the keepalive of one node in a LinkedHashMap you can remove, update and re-add the node.

Exception handling

  • Exception messages are missing in all exceptions. The JavaDoc helps but it's important to provide a message in the exception. It's odd that invoking .get(key) throws and IllegalStateException without a message.

  • Each method checks if the repository is started, otherwise throws an exception. To simplify that consider to start the repository directly in the constructor.

Stopping the repository issue

public class ExpiringKeyValueRepository<K, V> {
    //...
    synchronized public void stop() {
        //...
        try {
            cleaner.stop(); 
            cleanerThread.join();
        } catch (InterruptedException e){};
        //...
    }
    private static class Cleaner<K, V> implements Runnable {
        //...
        @Override
        public void run() {
                //...
                while (!stopped) {
                    //...
                    long timeToWait = rep.first == null ? MAX_LIVE_TIME : rep.first.timeTillExpiraton();
                    try {
                        checkCondition.await(timeToWait, TimeUnit.MILLISECONDS);
                    } catch (InterruptedException e) {} ;
                }
                //...
        }
        private void stop() {
            writeLock.lock();
            try {
                if (!stopped) 
                    stopped = true;
            } finally {
                writeLock.unlock();
            }
        }
    }
}

Consider this scenario:

  1. Start the repository: the thread cleaner is launched.
  2. Add and remove all keys.
  3. There are no keys left so the cleaner decides to go to sleep forever.
  4. Stop the repository: the main thread sets stopped=true and waits for cleaner to stop (.join) but it will never happen because it's sleeping.

Also the method Cleaner#stop is a little bit overkill. It is a private method that is invoked only by the parent class within an already synchronized method. I think it can be safely changed to:

private void stop(){
    stopped=true;
}

Alternative

The Google library Guava provides Cache that should fit your use case. See a simple usage:

Cache<Integer, String> cache = CacheBuilder.newBuilder()
                    .expireAfterAccess(1000,TimeUnit.MILLISECONDS)
                    .build();
// Add entry
cache.put(1, "user1");
// Get the value
assertEquals("user1",cache.getIfPresent(1));
// Refresh the entry (update keep alive)
cache.getIfPresent(1);
// Remove a key
cache.invalidate(1);
assertNull(cache.getIfPresent(1));
// Clear all keys
cache.cleanUp();

It is also thread-safe and can be used by multiple concurrent threads.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ @Markc Thanks for so deep and detailed review. 1. About usage of LinkedHashMap. I checked this option. The reason to not use it is that remove/add on timestamp update may cause map rehashing which is time consumed operation with map locking. 2. Cleaner stopping issue. You are right, this is a bug. I will fix it by insertion of checkCondition.notify() in Cleaner#stop, so cleaner will wakeup, check flag and exit. 3. As for other things you mentioned - you are right, I will fix it. Guava usage looks reasanable and I will check it too. \$\endgroup\$
    – bw_dev
    Nov 7, 2020 at 10:28
  • \$\begingroup\$ @bw_dev I am glad I could help ;) If you are satisfied with this answer consider to accept it. \$\endgroup\$
    – Marc
    Nov 29, 2020 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.