Java HashMap with time base expiry policy

I recently had to come with this data-structure, later I found that google collections has a MapMaker which essentially does the same. Posting some ideas and the code I have written here.

There are broadly two different ideas:
1. Create a time tracker along with the hashMap. Then run a thread to detect and delete expired items
2. Create a new hashMap periodically while flushing the contents of old map.

I have implemented the first kind. This makes use of jdk 6 concurrency features

package test; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.Executors; import java.util.concurrent.ScheduledExecutorService; import java.util.concurrent.ThreadFactory; import java.util.concurrent.TimeUnit; import java.util.concurrent.locks.ReentrantReadWriteLock; /** * Thread safe object map, which clears objects after a specified time. The objects are stored in the * underlying hashMap. * @author rongkan * */ public final class TimeLimitedCacheMap { private final ConcurrentHashMap<String, Object> objectMap = new ConcurrentHashMap<String, Object>(10); private final ConcurrentHashMap<String, Long> timeMap = new ConcurrentHashMap<String, Long>(); /* I need a shared lock, readwrite lock is an excellent candidate. * evcition is run with writeLock, put/remove with readLock */ private final ReentrantReadWriteLock accessLock = new ReentrantReadWriteLock(); //private final ReentrantLock accessLock = new ReentrantLock(); private final Runnable evictor = new Runnable() { /* evictor thread removes data, and changes map state. This is * in conflict with put() and remove(). So we need sync for these operations * * In case you are wondering why evictor needs sync (it just calls remove() right?) * eviction is a compound action that spans more than a single remove(). It enters * into a conflict with put() * * evictor: start looping ------------------------------> keyset is stale, evictor removes the recent put & armagedon comes * Thrd1:--------------------->put(same key, new object) * */ @Override public void run() { // avoid runs on empty maps if(timeMap.isEmpty()){ Thread.yield(); } long currentTime = System.nanoTime(); accessLock.writeLock().lock(); Set<String> keys = new HashSet<String>(timeMap.keySet()); accessLock.writeLock().unlock(); /* First attempt to detect & mark stale entries, but don't delete * The hash map may contain 1000s of objects dont' block it. The returned * Set returned may be stale, implying: * 1. contains keys for objects which are removed by user, using remove() (not a problem) * 2. contains keys for objects which are updated by user, using put() [a big problem] */ Set<String> markedForRemoval = new HashSet<String>(10); for (String key : keys) { long lastTime = timeMap.get(key); if(lastTime == 0){ continue; } long interval = currentTime - lastTime; long elapsedTime = TimeUnit.NANOSECONDS.convert(interval, expiryTimeUnit); if(elapsedTime > expiryTime){ markedForRemoval.add(key); } } /* Actual removal call, which runs on the objects marked earlier. * Assumption: marked objects.size() < hashmap.size() * Do not delete blindly, check for staleness before calling remove */ accessLock.writeLock().lock(); for (String key : markedForRemoval) { long lastTime = timeMap.get(key); if(lastTime == 0){ continue; } long interval = currentTime - lastTime; long elapsedTime = TimeUnit.NANOSECONDS.convert(interval, expiryTimeUnit); if(elapsedTime > expiryTime){ remove(key); } } accessLock.writeLock().unlock(); } }; private final ScheduledExecutorService timer = Executors.newSingleThreadScheduledExecutor(new MyThreadFactory(true)); private final class MyThreadFactory implements ThreadFactory { private boolean isDaemon = false; public MyThreadFactory(boolean daemon){ isDaemon = daemon; } @Override public Thread newThread(Runnable r) { Thread t = new Thread(r); t.setDaemon(isDaemon); return t; } }; private final long expiryTime; private final TimeUnit expiryTimeUnit; /** * Users can play around with evictionDelay and expiryTime. * 1. Large evictionDelay => less frequent checks, hence chances of finding expired Objects are more * 2. Lean evictionDelay => aggressive checks, and hence more sync overhead with put() and remove() * 3. Large expiryTime => increases the time object stays in object map and less chance of cache miss (cache miss is bad) * 4. Lean expiryTime => by itself does not force object to be removed aggressively, needs lean eviction to be configured * * In case you are wondering, above picture is not complete. * Another key aspect is "Arrival Periodicty", or the rate at which put() is called. * * Ideally: expiryTime == arrival periodicity + 1 [read '+1' as slightly greater] * evictionDelay == expiryTime + 1 * * For random arrival times, which is a more common scenario, use the following pointers * 1. eviction Delay > expiry Time * Here user needs to think of the impact of stale hit (define how stale is stale!) * 2. eviction Delay < arrival time * This has higher chances of cache miss and accidental treatment as failure * * 3. eviction Delay < expiry Time * Unwanted eviction run(s) resulting in sync overhead on map * 4. eviction Delay > arrival Time * Unwanted eviction run(s) resulting in sync overhead on map * * @param initialDelay, time after which scheduler starts * @param evictionDelay, periodicity with which eviction is carried out * @param expiryTime, age of the object, exceeding which the object is to be removed * @param unit */ public TimeLimitedCacheMap(long initialDelay, long evictionDelay, long expiryTime, TimeUnit unit){ timer.scheduleWithFixedDelay(evictor, initialDelay, evictionDelay, unit); this.expiryTime = expiryTime; this.expiryTimeUnit = unit; } /* The intention is to prevent user from modifying the object Map, * I want all adds/removals to be suspended. synchronizing on objectMap * would also work, but locks are easier to read without scope issues of {} * * Concurrent hashMap would have allowed put and remove to happen concurrently. * I did not use conc-map, because * 1. I want to update another map (timeMap) * 2. I want to sync the operation with evictor thread * * The unfortunate invariants: * 1. sync between evictor and put() * 2. sync between evictor and remove() * imply * 3. sync lock between put() and remove() * * 3. is unfortunate side effect, as you need to sync all exposed invariants on the same lock. * Lock duplication won't help. If I create putLock() and removeLock(), they will allow put() and remove() * to happen concurrently, but will not help two put()/remove() calls to happen in parallel. */ public void put(String key, Object value) { accessLock.readLock().lock(); Long nanoTime = System.nanoTime(); timeMap.put(key, nanoTime); objectMap.put(key, value); accessLock.readLock().unlock(); } /* Read comments for put() they apply here as well. * If had not allowed remove(), life would have been zillion times simpler. * However, an undoable action is quite bad. */ public Object remove(Object key) { accessLock.readLock().lock(); //accessLock.lock(); Object value = objectMap.remove(key); timeMap.remove(key); //accessLock.unlock(); accessLock.readLock().unlock(); return value; } /* Clone requires locking, to prevent the edge case where * the map is updated with clone is in progress */ public Map<String, Object> getClonedMap(){ accessLock.writeLock().lock(); HashMap<String, Object> mapClone = new HashMap<String, Object>(objectMap); accessLock.writeLock().unlock(); return Collections.unmodifiableMap(mapClone); } }

GXT Nuggets: Hipocrite's combo box

Bananas for the code monkey

Ever faced a situation where you want to show the user some information 'X' but you actually need 'Y' for the backend logic? Say you have an employee entity with a employee details and a auto-generated PK. You have designed a form to show the employee details, based on the user selection (in a drop-down combo). A hiprocrite's combo is up for this task. It shows employee name/number in the UI but secretly holds the PK deep down.

You may wonder why all the fuss, why not just set the state in the drop down. Works wonderfully provided you 'remember' the state's 'key'. If I have 10 such forms, this involves 10 if() stmts atleast. To overcome this and let the contract-driven design make life easier for us, I re-invented the combo box. I added an adaptive behaviour in form of DynamicProperyEditor. This enables us to query for various model properties without excessive intrusion.

public class DynamicPropertyEditor<Data extends BaseModelData> extends ListModelPropertyEditor<BaseModelData>{ private String propertyName; public DynamicPropertyEditor(String property) { this.propertyName = property; } public String getStringValue(Data value){ return value.get(propertyName); } public String getPropertyName() { return propertyName; } } public class X10ComboBox<D extends BaseModelData> extends ComboBox<D> { private DynamicPropertyEditor<D> dynamicPropertyEditor = null; public DynamicPropertyEditor<D> getDynamicPropertyEditor(){ return dynamicPropertyEditor; } public void setDynamicPropertyEditor(DynamicPropertyEditor<D> dynamicPropertyEditor) { this.dynamicPropertyEditor = dynamicPropertyEditor; } @Override public ListModelPropertyEditor<D> getPropertyEditor() { .... } }

GXT Nuggets: Preventive form validation

Bananas for the code monkey

It is always a good idea to prevent users from doing unwarranted things. Thats the whole idea of client side validation. (Client-side validation is one good way of catching errors before the code hits server, so....blah blah).

The general notion in UI is to accept user input using forms.(XSS, URL mangling etc left aside). In GXT, we can actually mandate/direct the hasty users to enter the correct data without cluttering the UI with error messages. The notion is simple, prevent the buttons from being enabled until all the validations are honored.

This is achieved using a FormButtonBinding object. The actual code:

private FormPanel createLabelSearchPanel(String formHeader, String keywordLabel, String submitLabel) { FormPanel formPanel = new FormPanel(); formPanel.setLabelAlign(FormPanel.LabelAlign.RIGHT); formPanel.setHeading(formHeader); formPanel.setFieldWidth(DashboardConstants.FIELD_WIDTH); formPanel.setLabelWidth(DashboardConstants.LABEL_WIDTH); formPanel.setFrame(true); formPanel.setAutoHeight(true); FormData formData = new FormData("-10"); TextField<BaseModelData> textField = TextFieldFactory.getDefault().getTextField(keywordLabel, "(Enter Search Key)", ""); formPanel.add(textField, formData); Button searchButton = new Button(submitLabel, new SubmitButtonListener(formPanel)); formPanel.getButtonBar().add(searchButton); FormButtonBinding binding = new FormButtonBinding(formPanel); binding.addButton(searchButton); formPanel.setButtonAlign(HorizontalAlignment.CENTER); return formPanel; } ------------------------------------------ private TextField<BaseModelData> createTextField(final String fieldLabel, final String defaultText, final String defaultValue) { final TextField<BaseModelData> textField = new TextField<BaseModelData>(); textField.setFieldLabel(fieldLabel); textField.setEmptyText(defaultText); textField.setSelectOnFocus(true); textField.setAllowBlank(true); return textField; }

Clutter free eclipse installations

The core principle of eclipse is plugin based architecture. This worked so well, that the eclipse eco-system is thriving with a plethora of addons. Earlier versions of eclipse (2.1 and earlier) were simple zip files, you could copy the whole directory structure and run it on any other machine. With the advent of 3.0, it is no longer the case.

Eclipse versions determine the target platform based on the configuration. Incompatible configurations can cause crashes. In such extreme cases, the only resort is to search for all conflicting workspace configurations, reinstall eclipse with required plugins and reload the workspace projects.

The latest versions come with P2 installer. P2 installations simplifies the burden of downloading large zip files. This ibm article describes how to share plugins across different installations.

However, advanced users prefer seggregating plugins under a single location. Like all EMF plugins under one directory and python plugins in a different directory. Then create links to such. The benefit of this approach, you can remove and add features and plugins by a simple add/removal of link file. This also implies less memory utilization, you will be able to tweak you VM args to make use of optimal memory, without burdening the system. Implying better overall performance.

Michael wrote an excellent article in this regards. Happy tweaking!

The punctuation of parsing

Awk scripts when interacting with shell tend to be problematic. Reason awk assumes a different parsing criteria which is incompatible with the shell's own expectation. For e.g: The quotes and whitespaces (',"," ") have a definitive meaning in korn shell, which conflicts with awks. Running the script with

 set -x 

flag shows the details.

So a script snippet that would work on command line

awk 'BEGIN {RS="_EOL@"}' 'END {print $NF}" a.txt

is to be transformed to:

ETL_RECORD_DELIMITER="_EOL@"
cmd=`awk BEGIN{RS="\"$ETL_RECORD_DELIMITER\""}" "END{print" "NR} a.txt`

The white spaces are to be demarcated using " ", if you missed the gist.

Learning everywhere

World is your playground, play if possible; if not learn to play; alteast try to learn to play; you will appreciate things more.

This applies to programming as well. Programmers who know more than one programming paradigms deliver better outcomes. Very early on, I was misinformed that javascript doesn't care for invariants. The folks discussing this were my seniors, had thorough handson experience on C++ and Java. They are reknown for their sane and lucid code. They were working on a GUI generator (HTML UI) and using embedded js for validation. They did not knew unobstrusive JS. All they wanted was some validation on client UI that was realized using

 onclick="validateForm()" 

. The statement now seems silly, but from their point of view, it is akeen to writing business invariants in sed or grep. I couldn't grasp why one could not write class invariants in javascript, so asked them and got a response that in javascript everything was public (access scope). It was only a couple of years later I learnt the better parts.

My intent is not to demean any, but to highlight that even the best of the team is often blinded by competence. If one doesnot empty his pot, how can one fill fresh water! Another example comes from SQL, sql is declarative hence no imperative syntax. While it is true for the most part, certain implementations specific functions say

case...when, coallesce, nullif

can be used to impart imperativeness.

Java developers are a different breed, some just write procedural code, mask it under the name of OOPS and live with it. Some advance to proper OOPS, design and architect properly. A few others master AOP, MDD, ORM and try to be a bit more smart. JavaScript programmers on the other hand are the most eccentric ones. A true master uses functional, procedural, prototyping, event handling/messaging & OOP concepts to the fullest. While it is true that JS allows a whole gamut of things, it is still not fully seen beyond webservers. However, it is one of the few areas that indicates life beyond the know IDE realm.

Learning new languages may or may not be fun, but understanding and appreciating the concepts is definitely delightful. When I started with JRuby, the concept of blocks was the most enticing. The brevity of code was just not plausible in Java. Python had similar givings. When I moved to GWT, the concept of callbacks and message bus usage was obvious to me (naturally, they are defacto occurences in JS apps). I found certain developers crack their heads trying to propogate references/spoil interface definitions all in an attempt to meet the goals. I just wish they read a bit more.

Programmers who claim to be good with languages are not exempt. Ask them to come up with a proper word document, they do it - do it with style corruption. Most of us do not even understand what style/doc corruption is. We donot use styles. If we showed the same zeal towards MSWord, the world would be more pleasent to us. A close analogy is learning to type (finger typing or soft typing). My friends and collegues at times express their awe, well I have trained some portion of my brain to instinctively use a qwerty keyboard, (my friends can do it, but they never cared, if only you saw their stupendously long combo movements on arcade games).

My mom cooks great food. Serving several dishes working on them simultaneously is not a straight chore. I used to wonder how she did that. I observed that she planned ahead, cut her veggies and gathered her spices ahead. Even when the flame is up, she knew the order and quantity required; and accordingly batched her job. All good cooks are great planners, the plans don't always work - but planning is indispensable. Last time I was deploying a project, I took a leaf from her and prepared a check list. After a couple of reviews, we use it pre deployment, to identify what all needs to be done. A thorough deployment without a need to revisit is a small achievement, but a happy one. I am not saying that the deployment worked because I can cook things; all I am saying is that I can appreciate a intangible task in a better way.

All we need to do is keep an open mind to suggestions, and a realization that we are ignorant for the most part. Ignorance is a bliss, knowledge is power. I am happy that I have forgotten my calclus (Ignorance) but not my friends :)

Coder cannon

An article on /. about new developers getting better monetary benefits than seniors made me ponder about IT.

To give an example. In the world of stock market, if one were to estimate the worthiness of a stock/asset, it can be simply done by monitoring the topline growth for a given period. Another option would be find out the profitability of the company (Assets - Liabilities). However, one often finds stocks trading at a much higher price (indicated by P/E). This is very much like real-estate, where the price is driven not by the cost, but by the valuation.

IT valuations are taken more personally - to heart. It is expected that niche technologies deserve niche pays. For the most part, professional IT is about picking some data, transforming it and presenting it. Game devs and System programmers are prominent exceptions. I used to wonder why a SAP analyst makes more than a Java programmer, or a C++ programmer.

Indian IT companies often take a different route. They just force the programmers on to a technology. The results of cold, passionless work are the ones that give a bad name. No university can teach passion. A good organisation and leader can instill a drive, but lack of passion causes one to burnout. Another surprising facet of IT: I recollect seeing a job posting in 2009, asking for GWT experts with 5+yrs of experience. Did the job poster even know when GWT came into existance? On one hand, you can see new technologies as an opportunity to move ahead in life, on the otherhand you may have a "dejavu" moment. Indian IT's cream are adept at catching up with the game, and the whey just sulks.

Western IT is more passionate, they master the one prime thing they chose. I have consultants coming from far more diverse backgrounds into IT. While their IT skills are mediocre (beyond their comfort zone), the rich experience they bring is invalueable. Seniors are valueable, not because they have grown in age but because they can mentor and communicate better. New developers on the other hand can go anywhere. It is either a hit or miss scenario.

If you want your seniors for their soft-skills, make it clear to them. If you want them for their technical skills, tell them clearly the direction being taken. Who knows, some of them may just take a break - learn the new stuff and may prove even more valueable. One harsh thing about large IT projects is the fact that, no one is indispensable. All seniors were once n00bs, they remember that well enough. If they are comfortable in their current roles and don't want to move out, you can always blame the demand-supply curve. We still have cobol dinosaur dragon tamers around, don't we!