TupleSoup, Part 6

I have just uploaded a new release of TupleSoup. Unless you have multiple threads accessing your data, there is no real benefit for you in this release. In fact, you are even required to change a few things in your source... sorry :-( ...however, the possibilities these changes open for are really exciting, which will be what the rest of this post is about.

The primary change since the last version has been that the class Table has been renamed to DualFileTable and Table has instead been recreated as an interface. The idea behind this is that it will be possible for other parts of the system to work with any kind of table storage as long as they adhere to the Table interface. To adapt your code, all you need to do is change your instantiations to use DualFileTable, instead of Table as shown in the following sample.

Table table=new DualFileTable("test","./");

The first new type of table is also included in this release, its called HashedTable and is basically a hash of 16 separate DualFileTable objects. Whenever you insert a new row, it uses the row id to decided which of the 16 tables it should be stored in. In an ideal situation, this allows up to 16 threads to write new rows to disk at the same time without locking (remember, even in an ideal situation most of these threads would still have to fight for io on a lower level). However, the penalty is that any thread who wants to scan through the entire set of data in the table, will now have to scan through 16 sets of data instead of one. Even though these will be smaller than the one large, this will bring in a substantial overhead, so only use this new table for data storage that rarely do full table scans.

This might not sound too exciting if you are not really doing massively parallel applications, however this whole refactoring has opened up great ways for me to add future functionality. One of the primary features I have been trying to find a good solution for is value indexing. That is, to create an index on a table that indexes all values of a single key on all rows. This will make it really snappy to select a set of rows based on the values of that key in the rows. With this new design, this type of indexing can be designed as an object that implements the Table interface and simply wraps around another table, injecting the indexing functionality where it is needed.

Thats about it for this post, I hope to soon follow up with a post that provides a longer full sample of TupleSoup usage.

TupleSoup Public Release

Tuplesoup is a small easy to use Java based framework for storing and retrieving simple hashes. If you are interested in the design and implementation choices I made, have a look at the following blog posts I made while working on the project.

• Part 1, Introduction
• Part 2, Record index
• Part 3, Index caching
• Part 4, First refactoring
• Part 5, Sorting

Since the last post in this series, I have done some further refactoring as well as added a set of statistic counters that can be polled to look for performance issues in usage patterns. The project is far from done, but I feel that it has reached a maturity that might make it useful for other developers. We have currently been using Tuplesoup for projects in our production environment for more than 3 months now without any stability issues. That being said, use at your own risk!

Let me end this post with a little bit of source code to show you how to actually use Tuplesoup in your own code. This very short completely useless example creates a table, adds a row and retrieves the row again. Hopefully I will soon find the time to write a more detailed piece of code showing some real world usage.

import com.solidosystems.tuplesoup.core.*;

Table table=new Table("test","./");

Row row=new Row("1");
row.put("username","kasperjj");
row.put("floatNumber",3.141592);
table.addRow(row);

row=table.getRow("1");
String username=row.getString("username");

Tuplesoup is available through sourceforge and has been released under the BSD license.

GTAC 07

I'm currently sitting in google's offices in New York for a small two day invitation-only conference called Google Test Automation Conference 07. This year, the primary theme seems to be automated testing of web interfaces using either WebDriver or Selenium.

The overall content of the conference so far has been very good, except for a few really boring sessions... however, since I'm primarily a developer and not directly within qa, I might just be too far away from the target audience for those sessions. This morning started off with a really interesting talk about using domain specific languages to write Selenium tests. It was very well delivered, and the content was definitely interesting, but at the same time I just couldn't help but notice how most of their samples in their dsl simply brought the interface of Selenium closer to the native interface for WebDriver. I haven't actually tried using either of the two systems yet, so this is purely prejudiced speculation from my side :-)

Although the rest of the day is filled with more talks about Selenium which all sound really interesting, I'm really starting to look forward to a lightning talk at the end of the day called "Selenium vs WebDriver steel cage knife fight". It will be featuring the authors of the two projects and I intend to be right up there by the edge of the cage ready to throw bacon at them as the fight begins!

Lunch at GTAC 07

Ok... I take it all back, lunch at google today was so incredibly yummy that I completely forgive the missing coffee this morning. Seriously, even after reading blog post after blog post of people raving about the food at google, I was in no way prepared for the actual deliciousness of it :-)

Now I just gotta find a way to sneak back into the offices around lunchtime every day... or maybe I could permanently occupy a stall in the bathroom and just come out once a day for lunch...

Caffeine free GTAC 07

I just arrived at googles offices in new york for a conference on testing automation. The invitation said breakfast included so I slept in late and went directly from my bed to the L train towards manhattan. The breakfast is fine, except for one important element... no more coffee... seriously, nothing but decaf :-(

How can you start a conference at 8:30 in the morning and run out of coffee at 8:35 ???

Netstat Sucks!!!

Well.. at least the following version of netstat sucks:

netstat 1.42 (2001-04-15) Fred Baumgarten, Alan Cox, Bernd Eckenfels, Phil Blundell, Tuan Hoang and others

At first glimpse, netstat works just fine. In fact, if you have less than 12 digits in the ip addresses you are looking at, you will probably never notice a problem. Unfortunately, the servers I'm usually working on has 12 digits. Have a look at the following output line from netstat.

tcp 0 0 ::ffff:217.116.236.191:25 ::ffff:217.116.236.18:40280 ESTABLISHED

It looks like a connection from 217.116.236.18 to 217.116.236.191. Unfortunately, thats not the case. In this case, it was a connection from .185. So what happened? Well, somebody in the group of people who wrote netstat, decided that it was more important to have nice and pretty looking columns than correct data. So they actually crop the ip address if the ip and port data doesn't fit the column width.

I really can't see any good reason for doing this.... netstat sucks!

Minimizing Id Size While Maximizing Readability

The last few posts have primarily been me bitching about things that annoy me, so I thought I would throw in a little happy-go-lucky constructive post with almost no bitching at all.

I mentioned in my last post about pretty urls that I always attempt to create my ids so they avoid using characters that are easily confused, such as I, 1, l, O and 0. Doing so is actually very easy and in this little post I will show you how I do it in Ravenous and even provide you with a ready to use implementation in Java.

The basic idea is that we convert integer ids into a string representation using only the letters and numbers that are not easily confused. For my implementation, I chose to use the following 31 characters: 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, H, J, K, M, N, P, Q, R, S, T, U, V, W, X, Y, Z.

A positive side benefit from this, is that we will also be moving from a base 10 system to a base 31, which means that we in many cases will be seriously reducing the number of characters used for an id.

So lets start talking about the implementation by looking at the way we would convert a number into a string. First, lets build an array of chars containing our 31 character set.

char[] digits={'2', '3', '4', '5', '6',
               '7', '8', '9', 'A', 'B',
               'C', 'D', 'E', 'F', 'G',
               'H', 'J', 'K', 'M', 'N',
               'P', 'Q', 'R', 'S', 'T',
               'U', 'V', 'W', 'X', 'Y',
               'Z'};

We use this array to directly lookup the character a number between 0 and 30 should be converted into. To convert a full number into a string, we simply keep dividing it by 31 and each time adding the character representing the remainder of the division to the string. When the remaining number is 0 we are done.

String convertToString(long num){
    StringBuilder buf=new StringBuilder();
    while(num>0){
        buf.append(digits[num % 31]);
        num=num/31;
    }
    return buf.toString();
}

Easy right? Converting a string back into a number is just as easy. This time simply run through each character, convert the single character back into a number based on its position in our translation array and multiplies that with 31 raised to the power of the current character position. Sound confusing? Try imagining if we where working with a 10 based system. The value of the first character would be multiplied by 10 ^ 0 = 1, the next by 10 ^ 1 = 10, the next by 10 ^ 2 = 100 and so forth. Thus multiplying each character by the value of its position. This is the exact same thing we are doing in our base 31 system. So lets look at the code. I'm assuming that we have a method called charToInt that will convert a base 31 character into its int value from our table.

long convertToLong(String str){
    str=str.toUpperCase().trim();
    long num=0;
    for(int i=0;i<str.length();i++){
        char c=str.charAt(i);
        num+=charToInt(c)*(Math.pow(31,i));
    }
    return num;
}

Easy right? So how about that charToInt method. Well, there are several strategies you can use for implementing it, but honestly the simplest is just to create a switch statement that utilizes the numeric value of the char to switch into a statement that returns the right value.

int charToInt(char c){
    switch(c){
        case '2':return 0;
        case '3':return 1;
        ...
    }
    return 0;
}

I have omitted the last 29 cases, but you should be getting the point by now :-). The last return is purely there to satisfy the Java compiler and to provide a semi rational behavior when (not if) someone attempts to feed it an invalid id string. If you want to optimize this further, you could create an array just like the one converting from numbers to characters. All you need to do is find the largest numeric value of those 31 characters, create an array of that size and fill in the right values.

So what do these ids look like and how much space will we save. Lets end this article with a set of sample ids, the strings they would be converted into and a rounded down percentage for how much space we are saving.

Integer	String	Saved
1	3	0 %
12	E	50 %
123	Z5	33 %
1234	UA3	25 %
12345	9VE	20 %
123456	GG66	33 %
1234567	SPFC3	28 %
12345678	QQEDF	37 %
123456789	425QB6	33 %