Personal Workflow Blog

Free Exception lunch : Use unchecked exceptions, but still announce which ones you might throw.

Steve Schnepp — Sat, 20 Feb 2010 16:01:00 +0100

In a previous article I choosed my side : Unchecked Exceptions are much simpler to use.

But, on the other side of this great division, there is a very valid point : You usually declare checked exceptions. Sure it's possible to only declare to throw Exception, but that would defeat the whole purpose of using checked exceptions.

The nicest thing is that you can also have a custom exception hierarchy, but based on RuntimeException instead of a plain Exception. This way it's like in C++. Everything might be thrown, and you don't need to handle them.

Declaring them, on the other side, is very interesting because you are documenting your interface for almost free.

So, use unchecked exceptions to free yourself of the checked catch-slavery, but still declare the custom ones you might throw.

Immutability of an URL

Steve Schnepp — Sat, 20 Feb 2010 15:18:00 +0100

In the pure spirit of Data is King I think that URL should never change. Even the W3C agrees with their Cool URIs don't change article.

But we all know that in IT never is only not in the foreseen future. So URL do change, at least after a while, and usually for technical reasons^[1].

Since you can update your website to update the URLs, but the inbound link cannot be easily updated. To handle this need, the HTTP protocol has specified the 301 response code.

The solution is that the site should remember all the urls that it generated and redirects accordingly. This way you'll never loose a potential reader to the infamous 404 (this page does not exist).

Some sites even try to approximate the page on a custom 404 page. That's another reason to have user-friendly urls : to be able to hint your reader to appropriate pages in case you don't find his initial destination.

Sadly, this redirect behavior isn't supported by my blog engine (dotclear)... That's for the eat your own dog's food, but I'm looking forward to do it on my current blogging platform.

Notes

[1] upgrade to another blog engine...

Avoid the Preprocessor : Use ''Compile-Time Polymorphism'' for Cross-platform Development

Steve Schnepp — Fri, 11 Dec 2009 23:00:00 +0100

When writing portable cross-platform code, don't litter your code with preprocessor macros, use compile-time polymorphism instead.

A flexible build system will enable you to use advanced OOP-like compile-time polymorphism. That way you can hide all the specifics of the different platform behind an interface firewall. It is the usual way that most cross-platform toolkits and frameworks (such as QT, GTK or wxWidgets) are designed.

We'll take a very simple file I/O subsystem here as an example (open, close). We'll also only take Linux and Windows, since that's usually the 2 most common platforms people want to develop for^[1].

The usual abstraction with the preprocessor

Usually preprocessor #ifdefs are used to compile specific parts for the underlying OS.

The file fileiosys.cpp looks^[2] like the one below :

fileiosys_filedesc open(char* filename) {
#ifdefine __WIN32__
    return OpenFile(
        filename, 
        GENERIC_READ | GENERIC_WRITE, 
        FILE_SHARE_READ | FILE_SHARE_WRITE, 
        NULL,
    );  
#else // UNIX
    return open(filename, O_READ | O_WRITE, 0666);
#endif
}

int close (fileiosys_filedesc fd) {
#ifdefine __WIN32__
    return CloseHandle(fd) ? 0 : -1;
#else // UNIX
    return close(fd);
#endif
}

The header fileiosys.h looks then like :

// Define a custom file descriptor
#ifdefine __WIN32__
    #define fileiosys_filedesc HANDLE
#else // UNIX
    #define fileiosys_filedesc int
#endif

fileiosys_filedesc open(char* filename); 
int close(fileiosys_filedesc fd);

Avoid the preprocessor Compile-time polymorphism

As the previous little example, the code isn't really easy to read. You have to always think which environnement you are in. All the specifics are multiplexed in the same file, and the programmer has to always demultiplex it in real time each time he reads the code.

The last part of the interface file is quite simple to read since it's already abstracted away. Now let's completely demultiplex the implementation in several implementation files.

The header file is the common interface

The interface is the most important part of the design. It should be high-level enough to mask the differences between the plateforms you want to support, but not too high-level, otherwise you'll end up duplicating to much code.

So, for our file I/O subsystem, we'll just abstract the usual syscalls open, close in the same way as before.

The parameters that are passed through the interface are also very important. You cannot usually leak a platform-specific structure. So here all the file descriptors are just an opaque handle, represented by a pointer to a structure defined only as a forward declaration in the header. This pattern, sometimes called the pimpl idiom, enables use to really share the representation while implementing it differently.

The header file is preserved as fileiosys.h, whereas the implementation is in the files linux/fileiosys.cpp and win32/fileiosys.cpp

`fileiosys.h`

// Define the forward declaration
struct fis_filedesc;
fis_filedesc* open(char* filename); 
int close(fileiosys_filedesc* fd);

`win32/fileiosys.cpp`

struct fis_filedesc {
    HANDLE handle;
};

fis_filedesc* open(char* filename) {
    fis_filedesc* fd = new fis_filedesc();
    fd->handle = OpenFile(
        filename, 
        GENERIC_READ | GENERIC_WRITE, 
        FILE_SHARE_READ | FILE_SHARE_WRITE, 
        NULL,
    );  

    return fd;
}

int close (fis_filedesc* fd) {
    int retval = CloseHandle(fd->handle) ? 0 : -1;
    delete(fd);
    return retval;
}

`linux/fileiosys.cpp`

struct fis_filedesc {
    int file_descriptor;
};

static fis_filedesc[32];

fis_filedesc* open(char* filename) {
    fis_filedesc* fd = new fis_filedesc();
    fd->file_descriptor = open(filename, O_READ | O_WRITE, 0666);
    return fd;
}

int close (fis_filedesc* fd) {
    int retval = close(fd);
    delete(fd);
    return retval;
}

The build system : `Makefile`

The makefile should take into account the different platforms, and only compile the needed implementation file. All the gluing magic will then be done at linking time instead of preprocessor time.

Conclusion

The interest of have multiple implementation files is obvious. It is much more straightforward to read and only marginally harder to write. But since most of the time code is read and not written, the choose is quite a no-brainer.

The nicest part is that all this is possible even without the expensive run-time polymorphism and RTTI, since the choose is done at compile-time.

Notes

[1] actually when targeting Linux, you usually target all Unix-like systems since they already have POSIX as a common abstraction

[2] The code is not real, it has been sweetened

Native SSH transport for Munin

Steve Schnepp — Thu, 26 Nov 2009 22:00:00 +0100

I blogged about the munin monitoring system a while ago.

The fact the Munin team did quite a remarkable job in cleaning up the 1.2 code for the 1.4 release enabled me to add a native SSH transport for Munin, and made be able to get rid of all SSH tunnels.

Actually the tunnel won't disappear, but they will be launched only when needed and, most importantly configured in munin.conf.

The native ssh for munin patch should applies quite cleanly on revision 3101 of the svn trunk.

Its use is quite straightforward : in /etc/munin/munin.conf, you just migrate address to the new configuration directive remote_connection_cmd that take the whole ssh command to launch a stdio munin-node such as pmmn.

If we take the examples from the previous post, it becomes clear it's much easier to configure.

munin.conf snippet - Inetd version

[server1]
    address localhost
    port 7001
[server2]
    address localhost
    port 7002

munin.conf snippet - Native SSH transport version

Right now, the address directive is still mandatory, but ignored when connecting.

[server1]
    address dummy
    remote_connection_cmd /usr/bin/ssh -- supusr@server1 /home/suprusr/pmmn/pmmn.pl
[server2]
    address dummy
    remote_connection_cmd /usr/bin/ssh -- supusr@server2 /home/suprusr/pmmn/pmmn.pl

Warning

Beware that the ssh process will now be launched by the munin user, so you have to update the key-based SSH authentication accordingly.

Sed is much slower than Perl, or not...

Steve Schnepp — Sat, 14 Nov 2009 12:18:00 +0100

I wanted to do some text replacement with a huge file (think ~18GiB), filled with huge lines (think ~2MiB per ligne)^[1].

I naïvely piped it through sed and I was quite shocked that it was CPU bound, and not I/O bound. The average rate was about 5 MiB/s (measured with pv, and the CPU was at almost 100%.The text file was gzipped on the filesystem, but with a 1/100 ratio, so the gzip process just took less than 2% CPU. I replaced then the sed -e with the Perl one-liner perl -lnpe, and .... tadaa, it was flying at a rate of 50MiB/s !

While I'm a big fan of Perl, and know its effectiveness to handle text streams, I'm was still astonished : being 10x faster than sed was something.

But in the good old saying Too good to be true means suspect, I remembered something about the character encoding of the regular expression. Since the system is entirely configured in UTF8, I suspected the infamous UTF8 overhead over plain ASCII.

I was right : a little LANG=C in front of the sed command line restored the rate to 50MiB/s.

So, beware of the performance impact of UTF8 strings, and try to avoid it if you can.

Notes

[1] For the record, it was a MySQL dump

Quickly replicate the clock between remote hosts with SSH

Steve Schnepp — Fri, 11 Sep 2009 08:00:00 +0200

NTP is very handy for server clock synchronisation, but it can be cumbersome to deploy.

Sometimes you just need to do a one-shot clock synchronisation, so you use the standard date command. But there isn't a flag to easily copy a setting to another.

From a remote host

Quite easy :

# date `ssh remoteuser@remotehost date +%m%d%H%M%Y.%S`

To a remote host

It's also very easy^[1] :

# ssh root@remotehost date `date +%m%d%H%M%Y.%S`

Notes

[1] Yes, I do know that logging remotely as root is a security pitfall...

Databases: Efficient Case-insensitive searches with Function-based Indexing

Steve Schnepp — Tue, 08 Sep 2009 22:00:00 +0200

Doing a case insensitive search is a very common task, but is quite hard to optimize correctly. But since it's done via a UPPER(MY_COLUMN) = UPPER('MY_DATA'), it doesn't use the index that could be on MY_COLUMN.

Different RDMS means different approaches.

Special case of case-insensitive search

In Oracle10g, you might use the new case-insensitive search with a NLS_SORT=BINARY_CI command.

Pro

Designed for this purpose, so it's very straightforward to use

Con

Limited to case-insensitive searching by design

Native functional indexes

Some databases provides native functional indexes.

On these databases optimization is done simply by creating an index on UPPER(MY_COLUMN) and letting the query optimizer transparently^[1] use the newly created index.

It usually work by applies a function to the data just before handing it to the index, so the function output doesn't exist in the database.

Pro

Very easy to use : it just feels right (you can naïvely create an index on the WHERE clause)
Doesn't take any extra space in the database (only the index).
Generic, can be used for something else than just case-insensitive searches.

Con

Since the data isn't stored in the database, a call to the function has to be made when
Functions have to be from the immutable category in the function volatility categories

Generated columns

DB2 provides something called generated columns. It's almost the same than the native indexes, except that the functional column is explicit.

Pro

Quite easy to use, since the column is updated and used transparently.
Generic, can be used for something else than just case-insensitive searches. Just make sure the optimizer uses the extra column. You might have to rewrite the request a little.

Con

Requires extra space in the table.
Removing a column can be cumbersome (in DB2 you have to recreate the whole table for example), whereas removing a simple index is much easier.
The extra column is returned when doing a SELECT * FROM ...^[2].

Trigger-based Generated columns Emulation

If nothing else is provided, you always have the option to emulate. The solution will be trigger-based since it's one of the few perfect match for them.

So, the base idea is derived from the Generated columns : have a special extra column that represents the output of the function. An index will be created on this column and used via a manual update of the involved requests (Adding an extra WHERE clause should be more than enough, this way you might even benefit from a partial match).

Pro

Universal. Useful if portability is paramount.
Very simple : there is no need to understand advanced database features.

Con

Only a poor man's solution : everything is manual
The same than Generated columns since it's the same idea, just manually implemented.

Notes

[1] You might have to update some kind of statistics for the new index

[2] But you don't do that anyway, do you ?

Overloading a method is hard : a common pitfall

Steve Schnepp — Mon, 07 Sep 2009 22:00:00 +0200

As I said in my equality article, overloading in Java^[1] is resolved by the static type of the argument, not the run-time type.

It's a generic problem of most compiled OO languages since usually overloading resolution happens at compile-time and not at runtime.

Now, that militates for the well known idiom :

Never overload a method with one that has the same number of parameters.

Actually, it should be enough to overload a method with one that accept parameters that are not inheritance-related : String and Number would be OK, but MyClass and Object would not.

Notes

[1] It's not really a Java-ism, it's the same in other languages, such as C++ .

A Simple Dns Server for a SOHO Network

Steve Schnepp — Mon, 10 Aug 2009 20:00:00 +0200

I'm in search of a very simple DNS Server for a small network. It should be :

recursive & caching (can be used as a proxy)
very simple administration (parsing /etc/hosts would be perfect, raw DNS zones like BIND would be a little bit overkill)
quite lightweight (aka no dependency on an SQL engine like MySQL, such as MyDNS)
Seamless integration to Windows lookups (nmblookup) via proxying functions (DNS to/from NMB)

Databases: Better Defer Constraints than Avoid Them

Steve Schnepp — Fri, 31 Jul 2009 08:00:00 +0200

Constraints are considered a Good Thing. They enable to rely more heavily on the validity of the database. It is quite important to note that validity is in terms of modeling and not in terms of business ^[1].

The biggest complains we can have about constraints is that it is sometimes quite annoying to do some updates while consistently validating the constraints. You have to care about the order of the operations you do.

Notes

[1] I'll write an article about this later

ACIDity of transactions as rescue...

Let's examine what all of the A, the C, the I and the D have for implications on our current subject.

Transactions are atomic (A)

The database should not really care about validating the constraints all the time Only the beginning and end state is really important. Inside a transaction, the data may be inconsistent : Dust hasn't yet settled.

Let's study an example. You have an unique index on an ordering.

TABLE ITEMS (
    ITEM_ID SERIAL,
    GROUP_ID INTEGER,
    ORDER INTEGER,
    LABEL VARCHAR
)

ADD UNIQUE INDEX ON ITEMS(GROUP_ID, ORDER)

Here, if you want to swap 2 items, you have to use an unused temporary value, otherwise the check won't be valid at all times.

Transactions are consistent (C)

The check needs to be done at least when the transaction ends. No special need here except that you need to re-enable before ending the transaction.

Transactions are isolated (I)

We can also easily imagine that the check only needs to be done when the transaction ends, just before the commit. Normally no one should be able to see the changing data meanwhile it's not completed.

One very important thing to know is that if you are using a READ UNCOMMITTED isolation for other transactions you will see inconsistent data.

Anyway, if you are doing that, you know what you are doing and are obviously taking special care about it, don't you ?

Transactions are durable (D)

This final property has nothing to do with our current issue. Good.

... But sometimes early warning is quite nice

When interacting with external systems, that don't participate in our transaction, extra care should be taken in order to cope with the exceptional case of a constraint failure. Distributed transactions is a very complex subject, and usually it's not ~~supported~~ done^[1].

Conclusion

With the principle of least surprise in mind, we can easily understand why deferred is not the default behavior, but it makes a very nice addition to our toolbox.

So now there isn't any good reason anymore not to use (and abuse) constraints in your databases.

Remember, your data is you most precious asset, protect it at all cost from evil misbehaved bug-ridden software^[2] !

Wow... Just in time before the end of the month... I would have failed my motto on URLs ;-)

Notes

[1] Do you always implement a double-phase commit on every SOAP/REST/XML-HTTP/POST interface that you expose ?

[2] Yeah, I have chosen my side in the coming war...

Checked or Unchecked Exceptions for Legacy Code ?

Steve Schnepp — Wed, 15 Jul 2009 20:55:00 +0200

This question can almost trigger a religious war. On Internet no fixed consensus on the matter seems to exists. But most of the articles there have usually something in common : they are always mostly applicable when you start a new application.

Is the situation the same when you have a certain amount of existing code to maintain ?

Checked Exceptions are breaking encapsulation

In theory it's quite nice since the called code can communicate with it's caller when something unexpected happened.

The key word here is unexpected. If you have to explicitly know the exceptions that could occur, it's not really unexpected. And if it's not unexpected, using exception handling just add an out-of-band data path. It's on par with transporting data in a private class field when calling a member instead of using its arguments. This leads to breaking encapsulation as Alan Griffiths wrote in Exceptional Java. This vision is also shared by Bruce Eckel in his article entitled Does Java need Checked Exceptions?.

Checked Exceptions are quite painful to use

Local Exception Handling is hard to manage

I personally find checked exceptions quite painful to use. By definition, you have to catch every exception that is thrown by the underlaying code.

And if the underlaying code doesn't know what to do with the exception, chances are, that you don't know either, so you just pass the exception to the caller. And so on...

Too much code to change

Therefore exceptions are usually caught at the top level with a generic catch-all structure that logs the error, since no layer could sensibly do something clever with the exception.

Then you just have to change all the signature of the whole stack, just to be able to catch them at the top. Using unchecked exception lets you have this for free, and conveys the meaning that nothing is caught until the top.

Unchecked Exceptions might be dangerous...

Obviously, unchecked means not checked. So you might fail to catch them at the top level and then the whole application crashes. Checked exceptions are a safeguard against that. Just like strong static typing is.

You trade compile-time safety (checked) for development-time speed and ease (unchecked).

... but are not really.

On the other hand, if you have a good design, you don't have much different top levels, and then the risk is somewhat limited.

Moreover, since you always have to take unchecked one into account, why don't use them ?

By the way, in C++, the exceptions are unchecked by default.

Databases: Efficient Denormalization with Views

Steve Schnepp — Tue, 02 Jun 2009 08:00:00 +0200

Everyone is unanimous that database normalization is considered a Good Thing.

But it usually comes with a cost : writing queries can be very tedious since you always have to join many tables together to be able to retrieve useful human data from all those reference tables.

On the other side, to denormalize is sometimes seen as a way to :

optimize development : you do not need to write (and debug) complex queries since all the data is nicely located in the same table
optimize performance : the data has a better locality (no need to fetch or compute data from elsewhere). You can even pre-compute order totals^[1].

Denormalize correctly is quite difficult since one change snowballs in multiple updates to keep the redundant data coherent. It is therefore usually done on the application side with ready-to-use ORM frameworks. But managing it at the application level comes with an ugly cost : it has to be reimplemented over and over each time the application switches technology, version or when a new application is connecting to the database.

In almost every programming language, code reuse is encouraged. Here, at the database level, we can also apply the same principles, and use views to transparently present a denormalized API (read tables) on a more normalized schema.

The main points are :

Views are the main code reuse vector at the database level. Current database usually correctly optimize (by rewrite and recombination) the simple queries so that performance is on par with a hand crafted query that doesn't use the views
Sometime even faster since the data is nicely organized, so there is much less data to transfer, and I/O bandwidth is a usual suspect.
The application part doesn't even need to know that normalization happens under-hood since updates to views are possible in many modern RDMs with the @@INSTEAD OF@@ trigger (or something equivalent).
Theses updates can be created with Materialized views are a step even further on the denormalizing road, since it provides the common benefits of denormalize without the implementation caveats. We can even hand-craft these Materialized views directly in an aggregation table in order to have the space benefits of normalisation and the performance benefits of denormalization.

So, nothing stops you from normalizing at will, and denormalizing when needed. Where to put the cursor is yours to decide, but moving it afterwards is finally easier that what is commonly admited.

Notes

[1] That article also explains why denormalization maintenance must stay at the database level with a very interesting metaphor

Equality in Java is a Hot Topic, but a Hazardous one.

Steve Schnepp — Mon, 01 Jun 2009 17:38:00 +0200

It seems that comparing two objects isn't as a simple task to do as it seems at first.

My concept for smart comparison still holds, but is completed perfectly with the How to Write an Equality Method in Java article posted on Artima soon after mine^[1].

2 main points that you have to be careful to (Others are also detailed in this article) :

hasCode() has to be redefined usually since otherwise the equality contract on Object.hascode() would be broken.
the equals() has to take an Object as parameter since overloading in Java is resolved by the compile-time type of the argument, not the run-time type.

I just got bitten by the second one, but not much (yet) since I mostly rely on compile-time overloading. My purpose here was only to compare objects either to constants or to simple variables. But in the generalization I would certainly have overlooked this and be bitten much more deeply.

Notes

[1] But as much as I wished it to be, it is not related :-)

Synthetic Style for Blog Posts : Presentation Style Blogging

Steve Schnepp — Fri, 29 May 2009 08:00:00 +0200

The good

With SMS, IM and now Twitter becoming more and more predominant : ideas might be given as bullet points
A presentation is much more dense in meaning than a big blob of text, Less time is required to read the post and be inspired by the content
Blogging is much less time consuming. As Jeff Artwood said Quantity Always Trumps Quality, it is the commitment that is important (hence the schedule).
You might divide a long article in several short and related posts.

The bad

Blog articles are usually a medium-depth analysis of a problem whereas presentation are usually a written support of a more detailed oral presentation.
Presentation sentences are usually hard to understand since they are just headlines without the underlying context.
You can always do a fast-reading version by putting the important sentences in bold for all those hasty readers.

The ugly

Longer don't always mean more interesting. Voltaire said Perfection is attained by slow degrees; it requires the hand of time. and Antoine de Saint-Exupery completed Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away..

Conclusion

As concluded by Pascal, I made this letter longer than usual because I lack the time to make it shorter, a good and terse article is therefore much more difficult to achieve. Therefore Presentation Style Blogging may be a false good idea.

Compare Efficiently in Java : Embrace Smart Comparison

Steve Schnepp — Tue, 26 May 2009 08:00:00 +0200

In Java, comparing things can be quite tricky. Comparing them with a simple == only compares the references, and for example 2 strings could be the same without being the same object. You have to compare them with the equals() method. Now the infamous NullPointerException (NPE) shows its ugly head when the first object to compare is null.

Bill the Lizard shows us a nice trick to avoid this NPE when used with string literals : call the method on the string literal. It's possible because it's also an object, and cannot be null.

But, as much as this trick code seems sweet, but it just feels like a red herring on the long run, First it only works for comparing strings and even only when comparing a string with a string literal.

To Equality ...

It is what he said at the end that is much more interesting :

The lesson to be learned here is that if you have to resort to "clever" tricks to get something done, with just a little bit of lateral thinking you can probably find a cleaner, simpler way.

Let's take this lesson even further.

I had a Perl & C++ background before coming to the Java world, and I am sometimes puzzled that Java makes things quite unnecessary complicated for the programmer from time to time.

My little suggestion : create a quite simple helper static function :

static boolean isEqual(String a, String b) {
   if (a == b) return true;

   // a & b cannot be null at the same time
   if (a == null || b == null) return false;

   // Now none can be null
   return a.equals(b);
}

Now, the NPE is avoided for any kind of string, with any order. We could also have a smarter equality comparison function by first converting to a string, and comparing the resulting string instead of comparing the original numbers.

static boolean isEqualSmart(Object a, Object b) {
   if (a == b) return true;

   // a & b cannot be null at the same time
   if (a == null || b == null) return false;

   // Now none can be null
   return a.toString().equals(b.toString());
}

With the wonders of Java's function overloading, you can even write specialized functions that convert even more smartly their arguments. And then be able to compare a string with a number (even a primitive type).

... and Beyond

We began about testing equality, but for comparison such as <= or >, you have to decode the output of the quite ugly compareTo() method. The helper static function trick comes also handy here.

First, we design a complete API that enable alphanumeric, and numeric comparison : the so-called smart comparison. The API should take any Object, or even primitive types, and convert it at will to enable hybrid comparison. This will greatly enhance the comparisons abilities of Java.

class OpAlpha {

   // Alphanumeric comparison
   public static boolean lt(Object a, Object b) { 
      /* convert to string and compare */ 
   }
   public static boolean gt(Object a, Object b) { 
      /* convert to string and compare */ 
   }

   // ... rest of the implementation ...
}


class OpNum {

   // numeric comparison
   public static boolean lt(Object a, Object b) { 
      /* convert to numeric and compare */ 
   }

   // ... rest of the implementation ...
}

class Op {
   // smart comparison, depends on the 2nd argument type
   public static boolean lt(Object a, int b) {
      /* convert to int and compare */
   }
   public static boolean lt(Object a, String b) {
      /* convert to string and compare */
   }
   public static boolean lt(Object a, Number b) {
      /* convert to Number and compare */
   }

   // ... rest of the implementation ...
}

The usage is like this :

String a = "124";
assertTrue( Op.eq(a, 124) );
assertFalse( Op.lt(a, 1) );
assertTrue( OpAlpha.lt(a, 1) );

We can see that all the tedious part of handling the conversions is done under the hood. Choosing the comparison to is just a matter of choosing the right class. A little more work could even be done to take the Op classes to implement Comparator in a complete OO way in addition of the static helpers.

Update (01/06/2009)

It seems that equality in Java is quite hazardous, and that you have to be extra careful not to set a comparison-land-mine off by accident.

Surrogate Keys : Globally Unique, Application Unique or Type Unique ?

Steve Schnepp — Tue, 19 May 2009 08:00:00 +0200

When you just decided to use Surrogate Keys, another problem arises : which value should I use ? It seems to be a very simple problem since the key now is completely in isolation in your application and is not related to any data. The choice is quite bonding, since a change means that every value has to be changed, and you did not let this key leak outside the database did you ?

The keypoint here is isolation. Many differents kinds of isolation are available, and soon you will be able to make a informed decision.

Type unique : One sequence per table

The most common idiom out there. Just define a surrogate key per table, usually done via an auto_increment field, serial field or a sequence per table.

It is the most natural way of thinking, since the ID is usually seen as a monotically incrementing counter. Therefore many applications use even the evil^[1] SELECT MAX(ID)+1 construct, because they specifically require that there should be no missed rows and that the ID have to be strictly in order.

The usual implementation of this is to have a kind of thread-local function that hands unique ID allocated in group and never trying to reuse an already issued/allocated ID. If you reserve 50 ID at once you directly level the cost of locking the ressource to only 1 in 50 requests, and not trying to reuse them enables you to just have to lock the end of the spectrum and not the whole spectrum. That's what the CACHE keyword is about in Oracle and PostgreSQL. Others RDBMS usually also have a similar option

But this optimisation leaves us with a big side-effect : the ID that are generated are not strictly in order anymore, and furthermore there can be huge gaps in them. Since one of the main purpose of one ID per table is now gone, why not directly bite the bullet and use the same ID generation on the the whole application ?

Application unique : One sequence to rule them all

This is something I first experienced with Subversion, coming from a CVS background : the revision number is repository-wide and not file-wide anymore. This has some mental drawbacks at first, since you still know that a file of version 5324 is more recent than version 3200, but not how much more since the commits could have been done in another place. The difference is more visible with 1.4 versus 1.5.

But as I was more used to it, that thinking was obviously a red herring. It did divert us that a file could have been completely rewritten in just one revision, and that one signle line could have be flipped back and forth in several revisions,

So the number, and the gap between them, as the basis of the amount of modifications has its value decreased. What could be quite interesting though is that the revision number is globally incrementing^[2]. That enables us to know that a file in revision 1000 was commited before another one with revision 2000.

Back in our database, if we just define one sequence for all the ID in the database we have 2 advantages :

One ID represents only one row. Debugging is easier and when you see an ID in the wild, you can think of which row it represents.
You can establish an almost exact history of sequencing the creations of the rows.

The inevitable locking performance issue that arises often is made painless through bigger block allocations.

One of the lesser known issue is that, usually when using an ID per table, after a while you begin to know which ID belongs to wich table since all the tables are filled at different rates : 50083 is an order ID, whereas 13650239 looks more like a message ID.

Globally unique :

If you push this logic a little bit further, you can even imagine that all the ID produced could be unique. Then you will have the benefits of unicity, but even on the whole IT level. It makes interapplication debugging easier, since the leaked keys can be nicely tracked down to their origin. How to generate such an unique ID is tricky question, since the applications usually are coded in heterogeneous environemments and technologies.

A central ID service

The most obvious way is to have a central ID service, the same as the unique sequence in the application. It has to be accessed in a distributed way, and the implementation can be quite cumbersome thoughout all the different technologies that exists.

This service has also to have the highest SLA as the applications that depends on it. It becomes then quickly a SPOF if not designed carefully.

GUID

Since online ID generation has some serious drawbacks, the easiest offline way is to generate GUIDs, there are many hooks in each technology/application to be a quite educated move.

It also has drawbacks, but more in the semantic fields. A GUID is quite semantically opaque since looking at it does not tell you anything about where/when the ID was generated. You have to do a full key scan of all the applications to find its origin.

Almost globally unique : Application ID + Application Unique

Earlier, we just found out the application-unique ID. If you pair it with an unique application ID, you just managed to have a globally unique ID. In the generation of this ID, you just prefix it with the ID of the application, and tada.... you have your globally unique ID.

The net effect is that if you see this ID in the wild, you know where it was created. If you have an increasing one, you can even guess almost when.

Parallels between applications and networks

The more I think about it, the more I can draw parallels between rows in applications and adresses in networks, but I'll write more on that later in another article.

Notes

[1] Evil because it's usually not thread safe and quite horridly inefficient

[2] Actually in subversion it has a **strict** incrementing policy

Are Excerpts a Good Thing ?

Steve Schnepp — Mon, 18 May 2009 12:04:00 +0200

One thing I'm really wondering is : Should I use excerpts ?

On the plus side :

The list is easier to read & shorter to parse. You can then just click on the link that are interesting to you
I can manage to see which posts are mostly read (useful ?) since the comments aren't a good indicator^[1]
Mostly all my readers comes from Google. Having a little list and only then content on a dedicated page seems to help being nicely referenced on more specifics, hence ususally more relevant topics.

On the down side :

The RSS flow and the front page list are truncated. You are one click further to the whole story.
It seems quite arrogant to force the reader to come to your site.

I just edited my articles to have an excerpt when it is quite long.

What do you think ?

Notes

[1] It is very far from being a very famous blog with hordes of readers :-p

Bringing C++ Const to Java

Steve Schnepp — Wed, 06 May 2009 11:15:00 +0200

Constness is another C++ idiom, like RAII that I talked about earlier. We can then write code that are side effects free : when a function is called with a const argument, we are assured that this argument will not be modified under the hood without us knowing^[1].

In Java, the commonly accepted way is to use the final keyword. But it has a major drawback : the object cannot be redefined, but can be modified by calling mutable members. You have to convert it to an immutable type. This is a simple task, but radically different ways exists.

Notes

[1] Of course, C++ being what it is, there always will be ways. But let's say it's not as tempting to do as otherwise.

Achieve Immutable in Java

We'll see some differents methods with a common example. Let's start with a very simple Point class :

public class Point {
    private int x;
    private int y;
    void setX(int i) { this.x = i; }
    void setY(int i) { this.y = i; }
    int getX() { return this.x; }
    int getY() { return this.y; }
}

The Java Collection way

It is the easiest way. It is designed to be a drop-in, like in the Java Collection API. You just create a read-only class that derives your read-write class just like the PointReadOnly that mimics the r/o List. It overrides all the methods either to delegate or to forbid calling by throwing a run-time exception.

public class PointReadOnly extends Point {
    private final Point inner;
    public PointReadOnly(Point p) { this.inner = p }; 

    void setX(int i) { 
        throw new UnsupportedOperationException("PointReadOnly is read-only"); 
    }
    void setY(int i) {
        throw new UnsupportedOperationException("PointReadOnly is read-only");
    }

    int getX() { return inner.getX(); }
    int getY() { return inner.getY(); }
}

Advantages

You can use it right-now : Your code can slowly evolve to progressively generate and integrate this new object without really knowing it's here. The misuses, that are changing the object, will be catched in the testing phase when exceptions are being thrown. The use of a good logging system in the setters is a nice addition.

Disadvantages

Any pedantic compiler should warn you that the setter parameter isn't read. I tried to be quite clever and find ways to ignore it. Just rewrite it as :

    void setX(int i) { 
        if (i == 0) { /* Do nothing but keep the compiler happy */ }
        throw new UnsupportedOperationException("PointReadOnly is read-only"); 
    }

The performance penalty is minimal since any compiler should optimize the if-case away and even if not, this function should not be called anyway.

But as a user on StackOverflow pointed, that warning definitively indicates a code smell : this hierarchy blatantly violates Liskov's principle of substitution since a class receiving an instance of a Point expects setX() to work, and may not handle this exception correctly. Obviously a read-writeable class is readable, but a readable class is not necessarly a read-writeable class. This may introduce subtle bugs that would only be catched at runtime, and therefore testing, as simple as it may be, has to be quite thorough in order not to be bitten at a inconvenient time.

A good solution that respects Liskov's principle is to redesign the hierarchy, we'll talk about it just later. But right now, don't despair, you can have almost the best of the both world : simple, yet almost respecting Liskov's principle.

Circus time : ride two horses at once

Actually what violates Liskov's principle is that the setters don't do the job they are entitled to do. Throwing an exception is a sure way to ensure that the object won't be modified, but that is usually overkill^[1]. If you just log the erroneous call, but still do what it should do, you have the warnings, but not the nasty consequences. Just take care to log the callstack also, in order to be able to fix it much more easily.

The new method becomes then :

void setX(int i) { 
    Log.warn(new UnsupportedOperationException("PointReadOnly is read-only")); 
    return inner.setX(i);
}

A notable side effect is that your class isn't really read-only anymore though, just complain-only.

The Object-Oriented way

A much better solution is to create a read-only super class that the read-write one would inherit. The read-only class only implements getters (or any non-changing method). The read-write complement them with the setters.

It would lead to code like :

public class PointReadOnly {
    private final Point inner;
    public PointReadOnly(Point p) { this.inner = p }; 

    int getX() { return inner.getX(); }
    int getY() { return inner.getY(); }
}

public class Point extends PointReadOnly {
    private int x;
    private int y;
    void setX(int i) { this.x = i; }
    void setY(int i) { this.y = i; }
    int getX() { return this.x; }
    int getY() { return this.y; }
}

Advantages

Now Liskov's principle is not violated anymore and code that expects a read-only class can seamlessly have a r/o or a r/w class.

The changing will also spread naturally all throughout the codebase, just like the C++ const modifier and failures to comply would be caught at compile time and not at runtime.

The r/o is a nice wrapper for the read-only class, and a r/w can even be used in place of the r/o place.

Disadvantages

It doesn't feel right :The r/o class is just a placeholder for a r/w class.

Comments

An interface-base inheritance scheme can even be better. Point as the r/o interface, PointMutable as the r/w and PointBase as the base implentation class. This way you can avoid the wrapper class. You also get the C++ const_cast<>() for free (by just downcasting as PointMutable).

interface Point { 
        int getX(); 
        int getY(); 
}
interface PointMutable extends Point { 
        void setX(int i); 
        void setY(int i);
}
class PointBase implements Point { 
    private int x;
    private int y;
    void setX(int i) { this.x = i; }
    void setY(int i) { this.y = i; }
    int getX() { return this.x; }
    int getY() { return this.y; }
}

I realize this does not answer your question about getting rid of the warnings. But warnings can either be suppressed, ignored, or addressed. An unused parameter is often a bad smell that indicates your method might not be doing what it's expected to do. Methods should only get essential parameters. If the parameter is not used, the parameter is not essential, and therefore something needs to be changed.

The `String` way

Another way is just to avoid the read-only and mutable API all together and go the functional way. Since it's a completely different paradigm, it doesn't exactly fits the bill here but it's a quite important way of cutting the gordian knot. Its concepts are rooted in both functional programming and RAII. It is quite practical only if you have an efficient garbage collection system, since it has the tendency to create lots of temporary objets that are mostly created, used and forgot.

Do do thing, you have to redesign the whole class, in order to be able to defined it only once, and when you call a modifying method, you end up with an other object, also immutable. The String, Integer and Class class make extensive usage of this.

So, our class will become :

class final Point {
    private final int x;
    private final int y;
    Point(int x, int y) { this.x = x; this.y = y; }
    int getX() { return this.x; }
    int getY() { return this.y; }

    void setX(int i) { return new Point(i, this.y); }
    void setY(int i) { return new Point(this.x, i); }
}

As you can see, every object is not modifiable, if a method recieves the object as an argument, it cannot modify it, since it would have a new object. The properties are final, and the class has usually to be made final in order not to be able to mutate the class by inheritance.

This enables programming without side-effect and therefore is quite interesting for multi-thread programming.

Conclusion & thoughts

The UnsupportedOperationException is a very practical idiom, that even the Java Collection API is based on it. It may not be very nice in theory, but in practice it has its usages. It should not be abused thought, and the OO-way should be prefered when possible, usually when you are in control of all the code base.

The logging approch doesn't really solve the problem since it's only advisory, but can fit the bill when the code base is huge and you want to be able to understand what is going wrong.

The OO-way is a nice compromise between the abstract beauty of the String-way and the quite hugly kludge of the Collection-way, especially when used with the interfaces scheme : it spreads out as the const param, and force the coder to think if a modifying is really needed.

The String-way is very tempting, as a true create-and-forget way. If you could even enforce to only have one instance of each representation you'll have a free == (almost) overloaded operator^[2].

So we have at least 3 ways to learn and adapt idioms from C++ in Java. The major issue is that it's not as itegrated as const : every object needs custom code except maybe the String-way.

Notes

[1] It all depends on the indent, specific policies on specific usages.

[2] Just be aware of classloader issue with static. Hmmm that will be covered in another article.

Databases: Partial Indexing

Steve Schnepp — Fri, 17 Apr 2009 17:05:00 +0200

In huge tables, usually only a fraction of the table is used on a regular basis. The rest is useful either for historical purpose, or is just not being treated right now.

Let's take the table that contains orders that we created in my previous post to show you some examples.

Orders have usually a state, Let's create it ^[1] :

ALTER TABLE ORDERS ADD COLUMN STATE

Now usually a application makes use of the state of the order by querying it, even quite often. The main problem is that this query will do a full scan of the table unless the state field is indexed. Here comes the other issue : indexes take very much space since they have to be ordered and cannot be trimmed (except throw an expensive DROP/CREATE or REINDEX).

The space used is adequate if the index has many different values, but usually a state has only a finite set of values, and usually some are very transient and other quite long. Compare for example the state CANCELLED or SHIPPED that are mostly final to the very transient state INVOICE_TO_BE_PRINTED.

The number of orders that are in the state INVOICE_TO_BE_PRINTED are quite a few (especially compared to the final states). However these temporary states are the mostly queried (usually by batches, pollers or even web pages that present the workload to the users for manual polling).

Another overlooked usage is to have an ALMOST-UNIQUE index. I mean an unique index, but only on selected entries. In our ORDERS table, we can add a field that represent the PRINTING_PID of the process that is responsible for printing the invoice. It is only unique for the orders that are in the INVOICE_TO_BE_PRINTED state. A normal index isn't much of a help here since either you have to clear it afterwards, but you loose information, or you cannot enforce any uniqueness.

So there comes the PARTIAL INDEX. It is native in some databases^[2] but in most it isn't. Triggers comes then to the rescue. Some are not really fond of triggers since many things can happen undercover, but my moto is to use trigger in order to, and only to, maintain business-agnostic extra datas (usually to cope automatically with denormalization). Triggers shall not change the data, merely copy and/or move it around.

The new almost-unique column is also created :

ALTER TABLE ORDERS ADD COLUMN PRINTING_ID

Implementations

Reducing the index size and the overhead

So, a new table is created to contain the partial index :

TABLE PI_ORDERS_STATE ( 
   INT ORDERS_ID FOREIGN KEY ON ORDERS(ORDERS_ID),
   STATE, 
   INDEX ON (STATE)
)

And the insertion/deletion for the table is done via triggers. I do it a little rapidly since the real creation is a little more tedious than the pseudo-code here :

CREATE TRIGGER ON ORDERS WHERE INSERT, UPDATE
  WHEN o.STATE not in (PENDING, CANCELLED, SHIPPED) 
    INSERT INTO PI_ORDERS_STATE(o.ORDERS_ID, o.STATE) IF ORDERS_ID NOT PRESENT
  ELSE
    DELETE FROM PI_ORDERS_STATE 
      WHERE ORDERS_ID = o.ORDERS_ID

One should rewrite queries to take advantage of this partial index since when it's integrated in the database the optimizer just does it himself. A query like this

Old :

SELECT * FROM ORDERS WHERE ORDERS.STATE = INVOICE_TO_BE_PRINTED

New :

SELECT o.* FROM ORDERS o
INNER JOIN PI_ORDERS_STATE p ON p.ORDERS_ID = o.ORDERS_ID p.STATE = INVOICE_TO_BE_PRINTED

The query optimizer should now be able to use the small index in PI_ORDERS_STATE, and retrieve only the relevant orders via their primary key in ORDERS.

Almost-unique colums

To handle the almost-unique column, it's basically the same idea : a new table, new triggers :

TABLE PI_ORDERS_PRINTING_PID ( 
   INT ORDERS_ID FOREIGN KEY ON ORDERS(ORDERS_ID),
   PRINTING_PID, 
   UNIQUE INDEX ON (PRINTING_PID)
)

CREATE TRIGGER ON ORDERS WHERE INSERT, UPDATE
  WHEN o.STATE = INVOICE_TO_BE_PRINTED
    INSERT INTO PI_ORDERS_PRINTING_PID(o.ORDERS_ID, o.PRINTING_PID) IF ORDERS_ID NOT PRESENT
  ELSE
    DELETE FROM PI_ORDERS_PRINTING_PID
      WHERE ORDERS_ID = o.ORDERS_ID

No need to rewrite any query here.

Notes

[1] Notice that here I don't create all the meta-data stuff. That is left as an exercise to the reader - Yeah, I always wanted to say that...

[2] MS-SQL has it but calls it Filtered Index. PostgreSQL calls it PARTIAL INDEX. )

Email Ping to Comments Reply on Blogs

Steve Schnepp — Fri, 10 Apr 2009 12:46:00 +0200

As a blog writer I can receive the comments written on my blog via email.

I'm wondering why this service isn't implemented for replies to my comments on foreign blogs. I don't really want to remember all the blogs I left a comment on in order to poll them to see if there is a reply to my comment.

Actually, a quick hack would be to subscribe to the RSS feed of this particular entry and let the RSS feeder handle all the remembrance and polling for us, but that seems so inneffective. Just imagine all the wasted traffic induced by polling if this habit becomes mainstreams.

I thought about turning it the other way around, since it seems that I'm forced to leave an email adress on each comment I leave, why don't the blogging engines just use this adress to send a notification (maybe opt-in) if there is a activity ?

I wanted to activate this feature on my blog and it seems non-existant. I therefore searched around quickly only to discover that noone seems to be having this particular need.

Strange...

Edit(15/04/2009): I just found out that WordPress seems to support this functionality via a plugin : Subscribe to Comments

Personal Workflow Blog

Free Exception lunch : Use unchecked exceptions, but still announce which ones you might throw.

Immutability of an URL

Notes

Avoid the Preprocessor : Use ''Compile-Time Polymorphism'' for Cross-platform Development

The usual abstraction with the preprocessor

Avoid the preprocessor Compile-time polymorphism

The header file is the common interface

fileiosys.h

win32/fileiosys.cpp

linux/fileiosys.cpp

The build system : Makefile

Conclusion

Notes

Native SSH transport for Munin

munin.conf snippet - Inetd version

munin.conf snippet - Native SSH transport version

Warning

Sed is much slower than Perl, or not...

Notes

Quickly replicate the clock between remote hosts with SSH

From a remote host

To a remote host

Notes

Databases: Efficient Case-insensitive searches with Function-based Indexing

Special case of case-insensitive search

Pro

Con

Native functional indexes

Pro

Con

Generated columns

Pro

Con

Trigger-based Generated columns Emulation

Pro

Con

Notes

Overloading a method is hard : a common pitfall

Notes

A Simple Dns Server for a SOHO Network

Databases: Better Defer Constraints than Avoid Them

Notes

ACIDity of transactions as rescue...

Transactions are atomic (A)

Transactions are consistent (C)

Transactions are isolated (I)

Transactions are durable (D)

... But sometimes early warning is quite nice

Conclusion

Notes

Checked or Unchecked Exceptions for Legacy Code ?

Checked Exceptions are breaking encapsulation

Checked Exceptions are quite painful to use

Local Exception Handling is hard to manage

Too much code to change

Unchecked Exceptions might be dangerous...

... but are not really.

Databases: Efficient Denormalization with Views

Notes

Equality in Java is a Hot Topic, but a Hazardous one.

Notes

Synthetic Style for Blog Posts : Presentation Style Blogging

The good

The bad

The ugly

Conclusion

Compare Efficiently in Java : Embrace Smart Comparison

To Equality ...

... and Beyond

Update (01/06/2009)

Surrogate Keys : Globally Unique, Application Unique or Type Unique ?

Type unique : One sequence per table

Application unique : One sequence to rule them all

Globally unique :

A central ID service

GUID

Almost globally unique : Application ID + Application Unique

Parallels between applications and networks

Notes

`fileiosys.h`

`win32/fileiosys.cpp`

`linux/fileiosys.cpp`

The build system : `Makefile`

The `String` way