Java Solution for concurrent situation. Use space for ease of implementation


  • 0
    L

    Just started learning distributed systems, your comments are welcome!

    1. Use a long number as the total hit count since the beginning. The number range of long should be able to cover a very long time, even assuming 1M hits per second.
    2. Use the combination of a TreeMap and an AtomicInteger to avoid locking the whole Map. The AtomicInteger itself should be able to block concurrent access for that second, and later timestamp will not be blocked.
    3. I guess appending is much cheaper than updating/deleting, so I don't delete any data if that timestamp has passed. 1 Second is 1 entry in each Map, I don't know how large space each entry takes, assuming 100 bytes, then 1 day is 8 MB. Hopefully it is acceptable?
    4. At the time of getSum(int timestamp), I am not sure how to guarantee that get runs after all increments are done....

    import java.util.concurrent.atomic.*;

    public class HitCounter {
    private TreeMap<Integer, AtomicInteger> counts;
    private HashMap<Integer, Long> cache;
    Object lock;

    /** Initialize your data structure here. */
    public HitCounter() {
    	counts = new TreeMap<Integer, AtomicInteger>();
    	cache = new HashMap<Integer, Long>();
    	cache.put(0, 0L);
    	lock = new Object();
    }
    
    /**
     * Record a hit.
     * 
     * @param timestamp
     *            - The current timestamp (in seconds granularity).
     */
    public void hit(int timestamp) {
    	if (!counts.containsKey(timestamp)) {
    		synchronized (lock) {
    			if (!counts.containsKey(timestamp)) {
    				counts.put(timestamp, new AtomicInteger(0));
    			}
    		}
    	}
    
    	counts.get(timestamp).incrementAndGet();
    }
    
    /**
     * Return the number of hits in the past 5 minutes.
     * 
     * @param timestamp
     *            - The current timestamp (in seconds granularity).
     */
    public int getHits(int timestamp) {
    	if (timestamp <= 300) {
    		return (int) getSum(timestamp);
    	} else {
    		return (int) (getSum(timestamp) - getSum(timestamp - 300));
    	}
    }
    
    private long getSum(int timestamp) {
    	if (cache.containsKey(timestamp)) {
    		return cache.get(timestamp);
    	} else {
    		AtomicInteger currentAI = counts.get(timestamp);
    		long current = currentAI == null ? 0L : currentAI.get();
    		current += getSum(timestamp - 1);
    
    		if (counts.size() > 0 && counts.lastKey() > timestamp) {
    			cache.put(timestamp, current);
    		}
    
    		return current;
    	}
    }
    

    }


  • -1
    L

    I used ReentrantLock, and it seems working:

    public class HitCounter {
    	private TreeMap<Integer, Integer> counts;
    	private HashMap<Integer, Long> cache;
    	private HashMap<Integer, ReentrantLock> locks;
    	Object lock;
    
    	/** Initialize your data structure here. */
    	public HitCounter() {
    		counts = new TreeMap<Integer, Integer>();
    		locks = new HashMap<Integer, ReentrantLock>();
    		cache = new HashMap<Integer, Long>();
    		locks.put(0, new ReentrantLock(true));
    		cache.put(0, 0L);
    		lock = new Object();
    	}
    
    	/**
    	 * Record a hit.
    	 * 
    	 * @param timestamp
    	 *            - The current timestamp (in seconds granularity).
    	 */
    	public void hit(int timestamp) {
    		lock(timestamp);
    		counts.put(timestamp, counts.get(timestamp) + 1);
    	}
    
    	/**
    	 * Return the number of hits in the past 5 minutes.
    	 * 
    	 * @param timestamp
    	 *            - The current timestamp (in seconds granularity).
    	 */
    	public int getHits(int timestamp) {
    		if (timestamp <= 300) {
    			return (int) getSum(timestamp);
    		} else {
    			return (int) (getSum(timestamp) - getSum(timestamp - 300));
    		}
    	}
    
    	private void lock(int timestamp) {
    		if (!counts.containsKey(timestamp)) {
    			synchronized (lock) {
    				if (!counts.containsKey(timestamp)) {
    					counts.put(timestamp, 0);
    					locks.put(timestamp, new ReentrantLock(true));
    				}
    			}
    		}
    
    		locks.get(timestamp).lock();
    	}
    
    	private long getSum(int timestamp) {
    		if (cache.containsKey(timestamp)) {
    			return cache.get(timestamp);
    		} else {
    			if (counts.size() > 0 && counts.lastKey() > timestamp) {
    				lock(timestamp);
    				Integer currentI = counts.get(timestamp);
    				long current = currentI == null ? 0L : currentI;
    				current += getSum(timestamp - 1);
    				cache.put(timestamp, current);
    				return current;
    			} else {
    				Integer currentI = counts.get(timestamp);
    				long current = currentI == null ? 0L : currentI;
    				current += getSum(timestamp - 1);
    				return current;
    			}
    		}
    	}
    }

  • 0
    L

    @lop This is very rookie usage of concurrency. You don't even bother unlock when changing hit count!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.