Saturday, September 09, 2006
A Developer's Journal; Solaris/CMT #5
Friday, September 08, 2006
A Developer's Journal; Solaris 10 #4
Monday, September 04, 2006
A Developer's Journal; Solaris 10 #3
The T1 is here. Andrew called to let me know it's at the office. It only took 6 days. I'm impressed. I guess Sun has finally got the kinks in there supply chain hammered out.
I need to figure out where I'm going to put it. I can set it up at the office or take it down to the data center or set it up at home. I just don't know right now because my thoughts are elsewhere. I've got some integration work to do with Jetty and a heck of a lot of code to write for the web service interface for my project.
So much to do so little time.
Sunday, September 03, 2006
Latches in Java
David Holmes provides an excellent description of the difference between java.util.concurrent.CountDownLatch and java.util.concurrent.CyclicBarrier on the concurrency interest mailing list. I have posted it here for those of you who don't subscribe to the list and may not have a good grasp of these classes. And since I use CountDownLatch in code I've posted in the past and in code I'm planning on posting I'm happy to have such a clear explanation that I can link to in future entries.
... As Brian describes one notion of state "latching" is that it progresses to a terminal value from whence it no longer changes. It is permanently "latched". A synchronization object that behaves in this way is the CountDownLatch - once "open" it never closes and can't be reset.
More generally though latches can be reset - consider a digital flip-flop such as a "gated D-latch", the flip-flop latches the value of the data when the gate is pulsed/strobed; if you change the data without changing the gate then the latched value is unchanged, but change the gate and the latched value is updated.
In synchronization object terms a latch is sometimes called a "gate" - the connotation being that if the gate is open anyone/everyone can pass through; while if it is shut no one can pass through. The CountDownLatch operates this way, but a more general "gate" is the CyclicBarrier which can also be reset (and automatically does so). Of course the semantics of CountDownLatch and CyclicBarrier are somewhat different. CyclicBarrier is what can be called a "weighted gate" or "weighted bucket" - it is set up to expect N threads to arrive, when they arrive they have sufficient "weight" to open the gate, or tip the bucket - in this case the gate/bucket is spring-loaded and closes/rights-itself as soon as the threads leave, so it is ready for the next set of threads to use. CountDownLatch on the other hand is like a gate with multiple padlocks - when the last padlock is removed, the gate opens and it stays open. Aren't these analogies quaint :-) We could have defined CountDownLatch to allow reset but reset semantics are messy and usually not needed for CDL usage, in contrast barrier designs typically always use the barrier multiple times.
It seems the database folk are using the term "latch" for lightweight lock, which is an uncommon usage from a synchronization perspective and a poor choice in my view, though arguably there is an analogy between "locking a door/window" and just "latching it shut". In that sense "latching" is a weaker form of "locking". But I don't like the usage.
A Developer's Journal; Solaris 10 #2
After 2 "Try and Buy" applications Sun Microsystems has finally shipped my T1. The thought of getting my hands on it gets my geek johnson tingling. You may be wondering "why just a tingle?" Well, when I first read about CMT coming to a server near me my geek johnson pitched a tent with enough head room for Yao Ming to enter without bending his head. But the truth of the matter is I am a cynic to the core. Vendors are notorious for contorting the truth and calling it marketing. They all claim their product is the greatest thing since Internet porn which is obviously a lie. THERE IS NO THING BETTER THAN INTERNET PORN! There. I said it. Go tell your friends. I'll wait for you in the next paragraph....
So I'll read the technical specs and the research and whitepapers on a technology/product but I don't drink the marketing Kool-Aid. So until I get my hands on the box and start playing with it you'll only get a tingle out of me.
Friday, September 01, 2006
A Developer's Journal; Solaris 10 #1
I'm testing the Solaris 10 waters. My plan for this journal is to record my Solaris journey in as much useful detail as possible. But before I start reporting my trials and tribulations I want to discuss why I'm taking this path (remember Linux is my OS of choice). There are 5 reasons why I'm looking at Solaris 10 now (from most to least importance):
- Try and Buy
- Chip Multi-Threading (CMT)
- DTrace
- ZFS
- Hotspot
Try and Buy
Try and Buy made the list and snatched the number one spot because it makes number 2 accessible given my limited R&D budget.
CMT
Sun has jumped ahead of the competition (Intel/AMD/IBM) in terms of throughput computing with the release of the T1 processor, code-named Niagara. I had previously discussed the coming of throughput computing here and here and I'm surprised yet thrilled to see it come to pass so rapidly. Most of the reviews of Niagara I've read are from people who don't have a clue about multi-threading and/or what makes it great. I'm guessing they have a rudimentary understanding of what a process is and probably don't know why scaling systems with threads is more efficient and performant than doing it with processes. So I'm really excited to get a crack at throwing an application that was designed from the ground up for multi-threaded deployment at Niagara.
DTrace
I'm a performance junkie. I like to make things go fast and it is hard to make something go fast when you don't understand what the thing is doing. Before DTrace it was possible to get pieces of the puzzle and sometimes it was possible to postulate about the whole and get it right but that's usually a hit or miss and it takes years of experience to develop the facilities to get more hits than misses. With DTrace there is no need to postulate it becomes possible to know with absolute certainty what the hell is going on. DTrace takes the guessing out of performance tuning.
ZFS
The disk subsystem is probably the most mission critical part of a computer because it's where all the programs and data are stored and without programs or data a computer isn't worth squat.
Aside:
Okay I concede. You can turn it into a modern art piece or make an ugly end table but other than that it isn't worth squat!
Unfortunately the disk subsystem is also the most unreliable. So any practical technology that handles reliability w/o major performance costs is a big deal to me. For years we've been subject to either uber expensive SCSI/RAID systems or cheap unreliable (and slower) IDE systems. But that's all changing, SATA and it's ilk are catching up to SCSI in terms of reliability and performance which will eventually drive SCSI out of the picture or force the price of SCSI down to the point where there is really no difference in terms of choosing one over the other. The bottom line is ZFS makes reliable disk subsystems something everyone can afford.
Hotspot
Given that the hotspot JVM is a Sun product and so is Solaris I conjecture that hotspot works better on Solaris than anywhere else. Especially Solaris on Sparc. So even though I'm a big Linux fan I'm an even bigger Java one.
Monday, June 12, 2006
QOTD: "I’m not writing shitty code; I’m creating refactoring opportunities."
I've got nothing to add to it. It's just plain funny as hell so I thought I would share it.
Saturday, June 03, 2006
"Look Ma, No Locks!"
Brian Goetz has written an excellent introductory article on nonblocking algorithms and showcases some simple nonblocking data structures with code examples and pictures.
The core concept you should take away from the article is the importance of CAS. It sits at the root of all nonblocking data structures in the Java platform.
Saturday, April 29, 2006
Monday, April 24, 2006
Monday, April 10, 2006
New Template
I've just switched my blogger template so if you are a regular visitor don't freak out. The new template makes better use of screen real estate and is more code friendly.
Let me know what you think.
Saturday, April 08, 2006
regex vs. XML
I needed to screen-scrape wikipedia for the list of Top Level Domains for my email app so I could build an index of suffixes that would reduce the number of martian addresses the app would have to process. So I surfed over to the TLD page to have a look-see. Low and behold those beautiful wikipedians were nice enough to produce well formed XML (actually, XHTML 1.0 Transitional) content. My heart leaped w/ joy because no screen-scraping was needed. With a little bit of XPath I would have my index in no time.
WRONG!!!!!!!!!!!
I spent the next hour+ trying to get XOM to work and spit out my list via XPath because I sure as hell wasn't going to try to manually walk the tree extracting the TLDs. Do you have any idea how much code that would take? I had a feeling the reason it doesn't work has something to do w/ how XOM handles namespaces because when I access the tree the hard way it demands that I specify the namespace URI of the document to lookup any element in the tree even though the document declares one and only one namespace. Now this isn't a knock against XOM, though I'm sure if I had used dom4j it would have worked because dom4j is more concerned with being useful than being correct. But each have there place. By this time I was so aggravated I just didn't feel like downloading dom4j and unpacking it and setting my classpath, yada, yada, yada.
Regex to the rescue
This his how I got what I needed the old fashion screen-scraping way. 5 minutes tops from concept to results:
String tld = "http://en.wikipedia.org/wiki/List_of_Internet_top-level_domains"
Matcher regex =
Pattern.compile( "<td><a[^>]++>\\.(\\w++)</a></td>" ).matcher( "" );
BufferedReader reader =
new BufferedReader(
new InputStreamReader(
new BufferedInputStream( new URL( tld ).openStream() ), "utf-8" ) );
PrintWriter writer =
new PrintWriter(
new BufferedWriter(
new FileWriter( new File( "/home/HashiDiKo/temp/TLD" ) ) ) );
for( String line; null != (line = reader.readLine()); )
if( regex.reset( line ).matches() )
writer.println( regex.group( 1 ) );
reader.close();
writer.close();
Saturday, April 01, 2006
Monday, March 27, 2006
Gentoo is back!
I'm proud to announce my return to the Gentoo colony with my acquisition of a dual processor dual core AMD Opteron 270 box. But it is not all gravy.
Normally I stay on the KDE side of the fence but my time spent in Ubuntu land has given me a new appreciation for the Gnome desktop environment. The Ubuntu team has spent a great deal of time and effort making Gnome and all the apps in the Ubuntu distro a seamless whole. In Ubuntu most of the time I couldn't tell where Gnome ended and the application began. I'm currently running XFCE 4 and if it wasn't so damn fast I would switch to Gnome in a heartbeat. But I'm finding it difficult to give up the instant response time of XFCE. It is really fast. Click on a button any XFCE button and boom! it opens instantly, no waiting. It is intoxicating.
Even more impressive is the startup time. Booting up to a KDE/Gnome desktop is like booting up twice, once for the OS and another for the desktop. With XFCE startup is a none issue. startx and 2.5 - 3 seconds later I'm completely in my desktop. My only real gripe w/ XFCE is it doesn't come with a built-in graphical calculator and I can't find a decent one in the portage tree.
Like I said before, it's not all gravy. The box's fans are loud as hell so much so that my apartment sounds like the tarmac of an airport as planes prepare for takeoff. Which means when I 'm not working I have to turn it off or else I won't be able to hear myself think. There are positives to this though. I can't hear my neighbors.
The walls in my apartment are paper thin and I've got probably the loudest most obnoxious set of neighbors. They are constantly fighting and yelling and banging on the walls. One of them has this habit of going into the hallway to talk on his cell and it drives me absolutely insane because the hallway acts an echo chamber to his already loud and irritating voice. Like I give a shit what he has say to whoever he has to say to. If I could get away w/ it I would do not nice things to him ;)
Wow! I have no idea how I got from talking about my Gentoo environment to piss and vinegar about my neighbors. I guess they really get on my nerves. Anyway, the bottom line is Gentoo is da bomb and I'm glad to back and now w/ my tarmac apartment my neighbors are a none issue so if something happened to them it wasn't me!
Sunday, February 26, 2006
Annoyances: java.sun.com
Why are the people that run the java.sun.com site such idiots? Try to get to the JavaMail part of the J2EE stack from java.sun.com w/o using the search dialog box. Go ahead, try it! I'll wait .....
Can't be done huh? WTF you say? It's because they are idiots! I used to be able to get to any named Java technology 2 clicks from the home page but they changed it and change is good. Bullshit!!
As a company Sun is infamous for small annoyances this is one of them. And because I spend (or will be spending) so much time in Java (Sun) land the annoyances are beginning to add up. Even their own employees complain. Argh!!!!!!!!!!!
It's like there are two competing groups of people working at Sun. Some really brilliant, thoughtful, articulate people and a bunch of morons. The morons are winning! If you think I'm kidding take a look at some of the J2SE and J2EE source code. There are some parts of it where I get the feeling, these people really know what they are doing. Then there are other parts where I have to go, WTF?!!! The patients have definitely taken over the asylum.
Saturday, February 25, 2006
QOTD: The 'f' in framework
I love the English language. You can get away with saying almost anything.
Wednesday, February 15, 2006
The Long Way Around, An Exercise in Concurrent Programming
Adopting the mindset to fully utilize the classes in java.util.concurrent can be quite challenging. One of the side effects of concurrent programming is that it can require more code than it would take to achieve the same results using mutual exclusion locking.
Is concurrency worth writing more code? My current answer to the question is hell yes because I think most Java programmers need the practice it's going to take to get one's head around all the issues associated with concurrency. And if the programmer doesn't practice, how is he/she going to be able to fully exploit concurrency in the cases where it is decisive? With that in mind I would like to talk about some code that I've written, but first some background info.
Better event handling
I think Java's current event model sucks! It's biggest problem is that it tightly couples the firing of events with there processing. In other words, the thread that does the firing is usually the same thread that handles the event. This is not a very stable or scalable solution because all it takes to bring event firing/handling to its knees is one badly written event handler (think infinite loop or blocking I/O). It is for this reason that the Swing team introduce the Swing worker thread so the programmer could separate the handling of events from the firing of events without taking the main Swing thread hostage.
There is a better way based on asynchronous messages. It is not fundamentally new. It is based on how asynchronous network I/O is done on Unix operating systems. You tell the kernel your are interested in a set of events then you can either go about your business and periodically check if the things you are interested has happened (poll(2)) or you can sit around and wait until something you are interested in does happen (select(2)). The choice is yours. Plus you can be interested in as many things as you want without a) requiring a copy of yourself for each interest set or b) hogging the kernel. This is because all the kernel does is tell you that what you are interested in is ready, it is your job to do something useful with it. So how do we implement the functionality in Java? Queues!
To wait or not to wait? That is the question!
The basic idea is a class/service that fires events will provide methods for threads to receive notification of these events by registering java.util.Queue objects. You can use any Queue object but I highly recommend java.util.concurrent.BlockingQueue objects. Why BlockingQueue[s]? Simple! A BlockingQueue allows us to choose to wait indefinitely, wait temporarily, or not at all for events (take(), poll(long,TimeUnit), poll()). It's the decoupler see? It unbinds the firing of events from the processing of events. It's the service/class 's responsibility to fire the event and it's the registrant's responsibility to process them. Tada!
The code dammit! The code!
Before I present any code I need to put it in context so it makes sense to you because I'm not going to include a complete project, just snippets. The snippets are part of a class that provides availability testing services. What that means is if a thread tries to make a connection to some host on the network and the connection fails, the thread can register the host with the service and the service will continue to try connecting to the host until some pre-configured timeout has elapsed or it manages to establish a connection. The registrant will be notified of the outcome of the connection testing by the service via the notification mechanism I've been talking about.
Now that I've through all the background info lets look at some code:/** 37 * Container for listeners interested all test results. 38 */ 39 private final Collection<Queue<Result>> allResults = new ConcurrentHashSet<Queue<Result>>(); 40 41 /** 42 * Container for listeners interested in specific test results. 43 */ 44 private final ConcurrentMap<String, Collection<Queue<Result>>> hostResults = 45 new ConcurrentHashMap<String, Collection<Queue<Result>>>(); 46 47 /** 48 * Registers <tt>listener</tt> with <tt>this</tt> object to receive {@link Result} 49 * notifications for all hosts. 50 * 51 * @param listener The listener. 52 * @return <tt>true</tt> if the listener was registered, <tt>false</tt> otherwise. 53 */ 54 public boolean register( Queue<Result> listener ) 55 { 56 return allResults.add( listener ); 57 } 58 59 /** 60 * Registers <tt>listener</tt> with <tt>this</tt> object to receive {@link Result} 61 * notifications for hosts in <tt>hosts</tt>. 62 * 63 * @param hosts The interest set. 64 * @param listener The listener. 65 * @return The registration results. 66 */ 67 public boolean[] register( String[] hosts, Queue<Result> listener ) 68 { 69 boolean[] registrations = new boolean[ hosts.length ]; 70 for( int i = registrations.length; --i >= 0; ) 71 { 72 String host = hosts[ i ]; 73 Collection<Queue<Result>> listeners = hostResults.get( host ); 74 if( null == listeners ) 75 { 76 listeners = new ConcurrentHashSet<Queue<Result>>(); 77 Collection<Queue<Result>> preempt = hostResults.putIfAbsent( host, listeners ); 78 if( null != preempt ) 79 listeners = preempt; 80 } 81 registrations[ i ] = listeners.add( listener ); 82 } 83 return registrations; 84 } 85 86 /** 87 * Unregisters <tt>listener</tt>. 88 * @param listener The listener that was registered with this object via {@link #register(Queue)}. 89 */ 90 public void unregister( Queue<Result> listener ) 91 { 92 allResults.remove( listener ); 93 } 94 95 /** 96 * Unregister's <tt>listener</tt> from all <tt>hosts</tt>. 97 * @param hosts 98 * @param listener 99 */ 100 public void unregister( String[] hosts, Queue<Result> listener ) 101 { 102 for( String host : hosts ) 103 { 104 Collection<Queue<Result>> c = hostResults.get( host ); 105 if( null != c ) 106 { 107 c.remove( listener ); 108 if( c.isEmpty() ) 109 { 110 Queue<Result> temp = new ConcurrentLinkedQueue<Result>(); 111 boolean b = register( temp ); 112 assert b : "IMPOSSIBLE!";// but i like to check anyway. 113 hostResults.remove( host ); 114 if( !c.isEmpty() ) 115 { 116 Collection<Queue<Result>> preempt = hostResults.putIfAbsent( host, c ); 117 if( null != preempt ) 118 { 119 preempt.addAll( c ); 120 unregister( temp ); 121 c = preempt; 122 } 123 124 for( Result result : temp ) 125 if( result.host.equals( host ) ) 126 for( Queue<Result> queue : c ) 127 queue.offer( result ); 128 } 129 unregister( temp ); 130 } 131 } 132 } 133 } 134 135 /** 136 * Notifies registered listeners of a new event. 137 * @param result The event. 138 */ 139 private void fire( Result result ) 140 { 141 Collection<Queue<Result>> listeners = hostResults.get( result.host ); 142 if( null != listeners ) 143 for( Queue<Result> listener : listeners ) 144 listener.offer( result ); 145 146 for( Queue<Result> results : allResults ) 147 results.offer( result ); 148 }
If you've simply skimmed pass the code you may want to go back and take a minute to digest it because I'm going to rewrite parts of it as it would have been written without the concurrency tools.
No concurrency
private final Collection<Queue<Result>> allResults = 37 Collections.synchronizedCollection( new HashSet<Queue<Result>>() ); 38 39 private final Map<String, Collection<Queue<Result>>> hostResults = 40 new Hashtable<String, Collection<Queue<Result>>>(); 41 42 public boolean register( Queue<Result> listener ) 43 { 44 return allResults.add( listener ); 45 } 46 47 public boolean[] register( String[] hosts, Queue<Result> listener ) 48 { 49 boolean[] registrations = new boolean[ hosts.length ]; 50 for( int i = registrations.length; --i >= 0; ) 51 { 52 String host = hosts[ i ]; 53 Collection<Queue<Result>> listeners; 54 synchronized( hostResults ) 55 { 56 listeners = hostResults.get( host ); 57 if( null == listeners ) 58 { 59 listeners = Collections.synchronizedCollection( new HashSet<Queue<Result>>() ); 60 hostResults.put( host, listeners ); 61 } 62 } 63 registrations[ i ] = listeners.add( listener ); 64 } 65 return registrations; 66 } 67 68 public void unregister( Queue<Result> listener ) 69 { 70 allResults.remove( listener ); 71 } 72 73 public void unregister( String[] hosts, Queue<Result> listener ) 74 { 75 for( String host : hosts ) 76 { 77 synchronized( hostResults ) 78 { 79 Collection<Queue<Result>> c = hostResults.get( host ); 80 if( null != c ) 81 { 82 synchronized( c ) 83 { 84 c.remove( listener ); 85 if( c.isEmpty() ) 86 hostResults.remove( host ); 87 } 88 } 89 } 90 } 91 } 92 93 private void fire( Result result ) 94 { 95 Collection<Queue<Result>> listeners = hostResults.get( result.host ); 96 if( null != listeners ) 97 { 98 synchronized( listeners ) 99 { 100 for( Queue<Result> listener : listeners ) 101 listener.offer( result ); 102 } 103 } 104 105 synchronized( allResults ) 106 { 107 for( Queue<Result> results : allResults ) 108 results.offer( result ); 109 } 110 }
Let's compare
For the most part the non concurrent version looks pretty much like the concurrent version in terms of lines of code and complexity, except for public void unregister( String[], Queue).
It was because of this method that I started this blog entry in the first place, because I realized how much easier a synchronized version would have been to write. It just seemed to be the long way around for removing an entry from a Map. Lets walk through it.
First off, let me explain what it's supposed to be doing then (hopefully) it will make sense why it does what it does.
Basically, one host can have multiple listeners. So when all the listeners for a host have been unregistered we want to remove the mapping for the host. Otherwise, we are going to have an object retention bug on our hands. The problem is how do we remove the mapping in a thread safe way? Because we can't simply say,
if( c.isEmpty() )
hostResults.remove( host );
and stop there because it is entirely possible that between the test and the removal another thread has registered for host. This is the kind of problem that mutual exclusion (synchronized) solves. But since we aren't using mutual exclusion we have to get creative. What we do is create a dummy Queue and register it to receive all events that get fired this way when we actual remove the mapping, if we are wrong about it being empty we can put it back and re-fire all the events that got fired between the time we removed the mapping and the time we put it back. The only draw back to all this (beside the additional lines of code) is that it is possible for a listener to receive duplicate events in the gap between,
preempt.addAll( c );and
unregister( temp );
So is the additional complexity worth it? Maybe. If we did things the synchronized way the entire event notification mechanism can quickly become the bottle neck if a lot of threads are using it, especially if they are registering and unregistering for the same host. Now, we could replace the synchronized keyword with java.util.concurrent.locks.ReentrantLock[s]. It's a more scalable mutual exclusion mechanism than synchronized. But I've spoken to Doug Lea recently and he told me that the (Sun's) JVM team is working hard at making the synchronized keyword as performant as ReentrantLock. Ya gotta love that competition. I think everyone should email Doug and thank him and the rest of the jsr166 team for embarrassing the JVM team into trying to make contended monitor acquisition more performant.
One last thing
I want to point out there is no general purpose lock free solution/pattern to the problem that I was solving in the unregister method. I was able to get away with not using locks because of the class' support for listeners to be notified of all events regardless of host. This support wasn't put in there just for concurrency's sake but is simply a feature requirement of the class that I've leveraged to avoid locking.
Tuesday, February 14, 2006
Matching a Backslash in Java
Solution:
[\";:()\\[\\]<>@.\\\\,]Monday, February 13, 2006
Part 2's a come'n
In the mean time I've fixed a minor bug in the code. The entry has been updated.
It was a really D'oh! (think Homer Simpson) type of bug. The code (comments) promised to return MX records sorted by preference but in reality it used lexicographical sorting only. So if a domain had two exchangers with preferences of 77 and 100 the 100 would appear before the 77. D'oh!Saturday, February 11, 2006
Java too ubiquitous? (My Response)
Back to Gentoo
My litmus test of a good distro is how easy is it to build and install your own kernel. Nuff said! Gentoo rocks fo' shizzle!
Friday, February 10, 2006
I Am Spam No More
Hello, Your blog has been reviewed, verified, and whitelisted so that it will no longer appear as potential spam. If you sign out of Blogger and sign back in again, you should be able to post as normal. Thanks for your patience, and we apologize for any inconvenience this has caused. Sincerely, Blogger Support
Observations, Linking Trends
I know the motivation for new windows and popups was to keep people on a site. Granted, it created more confusion than stickyness, but it had a purpose. So what is the motivation for this new style of site design?
Anyway, maybe I'm hallucinating and it's the same as it always was or maybe my browsing tastes of changed and the sites I frequent now are better designed. Come to think of it, I do consume significantly less Internet porn now that I'm 30.I Am Spam
Warning, edited to make it sound worse than it is!
God forbid hypertext (this blog) should have hyperlinks in it. That's what I get for talking crap about big daddy (or more recently, Big Brother) Google.Spam blogs can be recognized by their irrelevant, repetitive, or nonsensical text, along with a large number of links, usually all pointing to a single site.
3 Most Annoying Things About Firefox
- Press F3 to bring up the search dialog but it doesn't give the search box focus. What's the point!?! And don't tell me about [CTRL-F]
- Why can't I search my history, not just the title but the contents of the pages. I know it caches the data so why don't they just get it over with and make the damn thing searchable!?! I don't want a hear a peep about the dman Google toolbar. Google has enough information on me. The amount of internet porn I consume is my business and my business only! You see what Yahoo is doing to the Chinese. Google could be next. The dollar$ associated with a billion+ pontential users is damn good reason to do evil.
- When I scroll down a long page and click on a link on the page then go back to the previous page it starts me from the top of the page again. What the f@ck!?!
Tuesday, February 07, 2006
Making Progress
In the mean time I am happy to report the DNS querying code that I posted in A Breakthrough! has graduated from the Whiteboard and found it's own home. It's been fully tricked out with hostname resolution caching and all. There are a few concurrency related goodies in the code that I want to talk about to those readers still trying to figure out what the java.util.concurrency packages are good for. Since the code is 183 lines long (with comments) I'm splitting its discussion into two entries. The first entry is the one you are reading now and it contains the source code. The second entry will discuss the concurrency goodies and I'll post that sometime later today or maybe tomorrow.
Here is the code, enjoy:(Updated 13 Feb 06, 10:14)
6 import javax.naming.CommunicationException;
7 import javax.naming.NameNotFoundException;
8 import javax.naming.NamingException;
9 import javax.naming.ServiceUnavailableException;
10
11 import javax.naming.directory.InitialDirContext;
12
13 import java.net.InetAddress;
14 import java.net.PortUnreachableException;
15 import java.net.UnknownHostException;
16
17 import java.util.Enumeration;
18 import java.util.Queue;
19 import java.util.TreeSet;
20
21 import java.util.concurrent.ConcurrentHashMap;
22 import java.util.concurrent.ConcurrentLinkedQueue;
23 import java.util.concurrent.ConcurrentMap;
24 import java.util.concurrent.CountDownLatch;
25
26 /**
27 * Lookup service for DNS MX records.
28 * <p>
29 * <b>Thread safe:</b> yes
30 * </p>
31 *
32 * @author HashiDiKo</a>
33 */
34 public final class MXRecordQueryService
35 {
36 private static final String URL = "dns:/";
37
38 private static final String MXATT = "MX";
39
40 private static final String[] MXFILTER = {MXATT};
41
42 private static final MXRecordQueryService THIS = new MXRecordQueryService();
43
44 /**
45 * Cache queries.
46 * @see MXRecordQueryService.CacheEntry
47 */
48 private final ConcurrentMap<String, CacheEntry> cache = new ConcurrentHashMap<String, CacheEntry>();
49
50 /**
51 * Provides a mechanism for ensuring that no 2 (or more) threads will race to query the same domain but at the same
52 * time allow concurrent queries of different domains.
53 */
54 private final ConcurrentMap<String, CountDownLatch> domainLocks = new ConcurrentHashMap<String, CountDownLatch>();
55
56 private MXRecordQueryService()
57 {
58 }
59
60 public static MXRecordQueryService getInstance()
61 {
62 return THIS;
63 }
64
65 /**
66 * Returns the IP addresses of the MX records for <tt>domain</tt> sorted by preference or <tt>null</tt> if no valid
67 * hostnames exits for the MX records.
68 *
69 * @param domain The domain name.
70 *
71 * @return The IP addresses of the MX records for <tt>domain</tt> sorted by preference or <tt>null</tt> if no valid
72 * hostnames exits for the MX records.
73 *
74 * @throws NameNotFoundException Indicates that the <tt>domain</tt> is invalid.
75 * @throws ServiceUnavailableException Indicates that <tt>domain</tt> is valid but no MX records exists for it.
76 * @throws CommunicationException Indicates a problem contacting the configured DNS server(s).
77 * @throws RuntimeException If some other <tt>javax.naming.NamingException</tt> occurs.
78 */
79 public Queue<String> get( String domain )
80 throws ServiceUnavailableException, NameNotFoundException, CommunicationException, InterruptedException
81 {
82 CacheEntry cached = cache.get( domain );
83 if( null != cached )
84 {
85 if( System.currentTimeMillis() <= cached.expiration )
86 return cached.object;
87 cache.remove( domain, cached );
88 }
89
90 CountDownLatch lock = domainLocks.get( domain );
91 if( null == lock )
92 {
93 lock = new CountDownLatch( 1 );
94 CountDownLatch prempted = domainLocks.putIfAbsent( domain, lock );
95 if( null == prempted )
96 { /* Take another look because we may have preempted and it's cheaper to look than to lookup. */
97 cached = cache.get( domain );
98 if( null != cached && System.currentTimeMillis() <= cached.expiration )
99 return cached.object;
100
101 try
102 {
103 TreeSet<MXRecord> sorter = new TreeSet<MXRecord>();
104 String url = URL.concat( domain );
105 for( Enumeration en = new InitialDirContext().getAttributes( url, MXFILTER ).get( MXATT ).getAll();
106 en.hasMoreElements(); )
107 sorter.add( new MXRecord( (String)en.nextElement() ) );
108
109 Queue<String> queue = new ConcurrentLinkedQueue<String>();
110 for( MXRecord mx : sorter )
111 {
112 try
113 {
114 for( InetAddress addr : InetAddress.getAllByName( mx.hostname ) )
115 queue.offer( addr.getHostAddress() );
116 }
117 catch( UnknownHostException ignore )
118 {
119 }
120 }
121 cache.put( domain, new CacheEntry( queue ) );
122 return queue;
123 }
124 catch( NameNotFoundException nex )
125 {
126 throw nex;
127 }
128 catch( ServiceUnavailableException sux )
129 {
130 throw sux;
131 }
132 catch( CommunicationException comx )
133 {
134 if( comx.getRootCause() instanceof PortUnreachableException )
135 throw comx;
136 throw new RuntimeException( comx );
137 }
138 catch( NamingException nex )
139 {
140 throw new RuntimeException( nex );
141 }
142 finally
143 {
144 lock.countDown();
145 boolean invariant = domainLocks.remove( domain, lock );
146 assert invariant : "Impossible!";
147 }
148 }
149 else
150 lock = prempted;
151 }
152 lock.await();
153 return get( domain );
154 }
155
156 private static final class CacheEntry
157 {
158 final Queue<String> object;
159
160 final long expiration;
161
162 CacheEntry( Queue<String> object )
163 {
164 this.object = object;
165 expiration = System.currentTimeMillis() + 60000;
166 }
167 }
168
169 /**
170 * Utility class for extracting the different parts of a MX record string.
171 */
172 private static final class MXRecord implements Comparable<MXRecord>
173 {
174 final String hostname;
175
176 private final int pref;
177
178 MXRecord( String mx )
179 {
180 assert mx.matches( "\\d++\\s++.+\\." ) : "Invalid MX record format: ".concat( mx );
181
182 int offset = 0;
183 int len = mx.length() - 1;// Strip trailing dot.
184
185 /* Extract preference integer. */
186 while( offset < len && Character.isDigit( mx.charAt( offset ) ) )
187 offset++;
188 pref = Integer.parseInt( mx.substring( 0, offset ) );
189
190 /* Extract domain name. */
191 while( offset < len && Character.isWhitespace( mx.charAt( offset ) ) )
192 offset++;
193
194 hostname = mx.substring( offset, len );
195 }
196
197 public int compareTo( MXRecord o )
198 {
199 int diff = pref - o.pref;
200 return 0 == diff ? hostname.compareTo( o.hostname ) : diff;
201 }
202 }
203 }
204
Monday, February 06, 2006
JNDI vs dnsjava
A Breakthrough!
More About DNS Queries
Normally if the Java standard library has the ability to doing something for which there exists external libraries I will use the standard library even if the standard library's approach is inelegant, so long as there isn't a performance reason not to. Today I've arrived at such an junction.In the standard library, if you want to issue DNS queries for anything besides A and PTR records, you must use JNDI. JNDI was really designed for use with LDAP but Sun managed to shoehorn some DNS into it. On the other hand there is dnsjava. An open-source java library for issuing all types of DNS queries.
Say I wanted to lookup the MX records for blogger.com. Using JNDI it would look like this:
String[] MX_RECORD = {"MX"};
/**
* Returns the MX records for domain sorted by preference or
* null if no MX records where found.
*
* @param domain The domain name.
*
* @return The MX records for domain.
*
* @throws NamingException
*/
public List getMX( String domain ) throws NamingException
{
DirContext ctx = new InitialDirContext();
try
{
String query = "dns:/".concat( domain );
Attribute att = ctx.getAttributes( query, MX_RECORD ).get( "MX" );
if( null == att )
return null;
Collection sorter = new TreeSet();
for( Enumeration e = att.getAll(); e.hasMoreElements(); )
sorter.add( ((String)e.nextElement()).trim() );
List sorted = new ArrayList( sorter.size() );
for( String mx : sorter )
{
/* Strip off preference integer. */
int offset = 0;
int len = mx.length();
for( char c;
offset < len
&& (Character.isDigit( c = mx.charAt( offset ) )
|| Character.isWhitespace( c )); )
offset++;
/* Strip trailing dot (.) if it exists. */
if( '.' == mx.charAt( len - 1 ) )
len -= 1;
mx = mx.substring( offset, len );
sorted.add( mx );
}
return sorted;
}
finally
{
try
{
ctx.close();
}
catch( NamingException ignore )
{
}
}
}
Doing the same with dnsjava it would look like this:
static Comparator MX_SORTER = new Comparator()
{
public int compare( Object r1, Object r2 )
{
return ((MXRecord)r1).getPriority() - ((MXRecord)r2).getPriority();
}
};
/**
* Returns the MX records for domain sorted by preference or
* null if no MX records where found.
*
* @param domain The domain name.
*
* @return The MX records for domain.
*/
public static List getMX( String domain )
{
try
{
Record[] records = new Lookup( domain, Type.MX ).run();
if( null == records )
return null;
Arrays.sort( records, MX_SORTER );
List mx = new ArrayList( records.length );
for( Record record : records )
{
String host = ((MXRecord)record).getTarget().toString();
int len = host.length();
if( '.' == host.charAt( len - 1 ) )
host = host.substring( 0, len - 1 );
mx.add( host );
}
return mx;
}
catch( TextParseException e )
{
throw new RuntimeException( e );
}
}
I'm praying that dnsjava outpeforms JNDI.
I'm off to perform some micro benchmarks. I'll let you know how it went.
Sunday, February 05, 2006
Blogger can't Spell blog
(Code) Writer's Block
The way things normally work is once I have a general idea what a program is supposed to do my brain will formulate an outline. I then code the outline, test, and refine. Sometimes I rip all the current code out and start from scratch with an entirely new design based upon whatever knowledge I gleaned from the old design(s). The point is, once I know what the program is supposed to do, some other part of my brain take over and I find it easy to write code. Today that hasn't happened. I know what the program is supposed to do. As a matter of fact, I've known what the program is supposed to do for years, yet I'm stuck like a woolly mammoth in a tar pit. But I'm not giving up.
I know what you are thinking. "Why doesn't he just use the old code as the basis for the new code"? I can't. Most of the old code got destroyed due to human error and shoddy back up media. What I have been able to salvage, other than the UI, is useless to me because I'm going in an entirely new direction this time around.
Since I can't figure out how to write the meat of the program I'm going to try doing the UI. The problem there is I'm graphically challenged. For some reason I'm incapable of conceptualizing graphical user interfaces. Color, positioning, icons, etc ... forget about it! My brain cannot construct a mental image of what a GUI is supposed to look like. A few weeks ago I was browsing the Ubuntu Linux website when I came across this requirement specification document. Throughout the spec the author had images of hand drawn pictures of what the UI would look like. My jaw dropped. I was absolutely impressed and green with envy. Not because the drawings were drop dead gorgeous or anything like that but because he is able to manifest his thoughts in pictures. It's easier to discuss something that is graphically represented than something that is not.
The good news is most of the screens already exists. The original project netted 4 screens. This version will net 7. In the original version I had very little to do with the design of the screens other than to approve them. In this version I'm hell bent on overcoming my GUI handicap by tweaking the original 4 and doing, from scratch, the remaining 3. So dear reader, if know of any good places for the graphically challenged to learn design with XHTML/CSS, please leave me a comment. In the meantime I'm going to cruise over to A List Apart and see if I can't learn something. I'll keep you posted on my progress. After all, this is a blog about my design decisions.