CLI to Amazon S3 Service using Ruby

I was looking for a way to post code referred to in these posts that could accessed using URL's. I found that Amazon's S3 service, part of their AWS (Amazon Web Services), offered a way to store any type of files on it and access them using http/https. Amazon provides WSDL API's to the service and the 'aws/s3' ruby gem provides an ruby library to access it and a shell program 's3sh' to access the API's in an interactive fashion. I wanted to access s3 like a filesystem using commands similar to those found in Unix like "ls","mkdir" etc. So I developed a ruby script 's3cli.rb' that uses the 'aws/s3' gem and provides a cli to it. The commands look like "s3cli.rb ls", "s3cli.rb mkdir" etc. This script is still a work in progress but has enough functionality to be useful. I have also started using it to store backups both at work and at home. The current code and readme for the script are available at
http://s3.amazonaws.com/designandcode/s3cli.rb
http://s3.amazonaws.com/designandcode/s3cli-readme.html

I used the "send" method in ruby to eliminate a lot of code that would have been needed to parse the command and call the required method/function. The concerned code looks like

s = S3.new  
command = ARGV.shift
args = ARGV
if (command)
s.send(command,args)
else      
s.usage nil
end

Here the "send" method allows us to call a method of the S3 class by name. So all we need to do is parse the command name from the arguments and use "send" to call the correct method. The class defines the method "method_missing" which catches any calls for commands that do not exist yet. This eliminates the need for something like a "case" statement or a data structure mapping commands to function pointers. Further, adding a new command involves just adding another method to the class. We don't need to modify any existing code or data structure.

I already have a TODO list in the readme file. Please give me feedback on any new features you would like see, any bugs in my code or advice/critique on the ruby side of the code. Of course I will be happy to integrate any code snippets you provide into the script.

Media Player 1.0 - Uploading iTunes Media file info into MySQL (Cont)

The code is spread among the following six java files and one xsl template. The files are hosted at Amazon's Storage Service also known as S3. A future post will include a script to access the service using Ruby.

• iTunes.xsl The xsl template file needed to convert iTune's plist format to normal looking xml.
• DBoperations/MediaFileDatabaseOps.java This file defines a class that encapsulates all the database operations required by this program. It declares methods to open a database connection to MySQL, close it and create the "mediafiles" table. It also defines a method to add a mediafile to the table. JDBC is used to connect to the database and so raw SQL queries are exposed in these method.
• mediafile/mediafile.java The media file class encapsulates all the attributes of each entry in the iTunes database that are useful for a media player. The class also defines get/set functions for each of the attributes.
• uploadMediafilesFromiTunes/XMLparsedriver.java This class declares a "main" function to call the rest of the code and exists solely to create a standalone executable.
  
• uploadMediafilesFromiTunes/DOMUtil.java This class declares helper functions used in conjunction with the DOM parser. The "getSimpleElementText" function has a special case for the "Bit_Rate" attribute. iTunes does not have a value for the bitrate for some types of video files. We are storing the bitrate as an integer both in the class and the database. So if the value does not exist it is cleaner to return a zero than a null string.
• uploadMediafilesFromiTunes/ConvertiTunestoXML.java This class encapsulates the XSL transform function that converts the plist format into normal XML format. It instantiates the TransformerFactory using the xsl template above and performs the required transformation.
• uploadMediafilesFromiTunes/ImportiTunesMediafiles.java This class is the heart of the program. The pseudo code for the function "importfiles" looks like



* Transform iTunes plist file to normal XML
* Initialize database
* Parse the xml file
* Add each media file and its attributes to the database. I am 
  ignoring any files that belong to the genre "podcast".
* close database connection

That is all the code that I wrote to import mu iTunes library metadata into a MySQL database. The program works fine and I have done multiple imports with it. The code is written in Java but I don't think it uses OOP in any meaningful way. Most of the classes just declare static functions that are called without any object instantiation. The classes are just used as name spaces. The code looks close to a bunch of 'c' functions than true objects. It has probably more to do with my lack of extensive "Java" experience than anything else.

I later rewote this program in "Ruby" which I will post sometime in the future.

Media Player 1.0 - Uploading iTunes Media file info into MySQL

iTunes stores all meta data about the media files in its library in a XML like file. It conforms to the XML standard. However trying to read it using a standard XML parser caused me plenty of headaches. It is a format that Apple calls "plist" and looks something like this.

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple Computer//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
<key>Major Version</key><integer>1</integer>
<key>Minor Version</key><integer>1</integer>
<key>Application Version</key><string>7.0.2</string>
<key>Features</key><integer>1</integer>
<dict>
      <key>431</key>
      <dict>
              <key>Track ID</key><integer>431</integer>
              <key>Name</key><string>China Girl</string>
              <key>Artist</key><string>David Bowie</string>
              <key>Composer</key><string>David Bowie, Iggy Pop</string>
              <key>Album</key><string>VH1 Storytellers</string>
              <key>Genre</key><string>Rock</string>
              <key>Kind</key><string>MPEG audio file</string>
      </dict>

It would be a lot easier to parse something that looks like

<Name>China Girl</Name>

using an XML parser. After doing a few web searches I found that someone had solved this problem and developed an XSL tranformation that translates Apple's plist format into an XML format that is easier to work with. The XSLT file is listed below. I can't find the URL of the site where I found this little gem to put a link here. I promise to update this post if I find it again.

<xsl:stylesheet
   xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
   xsl:version="1.0">

   <xsl:template match="/">
           <songlist>
                   <xsl:apply-templates select=
                        "plist/dict/dict/dict"/>
           </songlist>
   </xsl:template>

   <xsl:template match="dict">
           <song>
                   <xsl:apply-templates select="key"/>
           </song>

   </xsl:template>

   <xsl:template match="key">
           <xsl:element name="{translate(text(), ' ', '_')}">
                   <xsl:value-of select=
                              "following-sibling::node()[1]"/>
           </xsl:element>
   </xsl:template>
</xsl:stylesheet>

Now the java code that takes in an iTunes XML data file and uploads it into the MySQL database is spread among 6 java class files.

1. DBoperations/MediaFileDatabaseOps.java - uploads a media file's metadata into the MySQL database.
2. mediafile/mediafile.java - defines a class to represent a media file's metadata.
3. uploadMediafilesFromiTunes/ConvertiTunestoXML.java - transforms the plist type iTunes data file into the XML format that can be fed to a DOM parser.
4. uploadMediafilesFromiTunes/DOMUtil.java - utilities to work with the DOM parser.
5. uploadMediafilesFromiTunes/ImportiTunesMediafiles.java - main class file that ties together all the pieces and uploads the meta data from iTunes into the database.
6. uploadMediafilesFromiTunes/XMLparsedriver.java - contains the "main" routine to call the program from the command line.

Before I publish the code let make a few comments about my code:

• It looks more like "c" code than java/OOP code. Definitely reflects the fact I have been coding exclusively in "c" and scripting languages off late.
• I could probably used other java libraries that would have made the task easier.

I will post each of the above mentioned files as independent posts along with a few comments about the code.

Long Break

It has been almost two months since I last posted to this blog. I got a little busy at work and also discovered something called Ruby and consequently Ruby on Rails. I have been spending time going over some tutorials and exploring both Ruby and Rails. I even rewrote a small part of the Media Player in Ruby. However as promised I will publish a series of posts that will detail the first version of my Media Player built using Java and GWT. I am happy to say that version 1.0 works and is being actively used as I write this post.

Media Player 1.0 - Overview

I rebuilt one my old PC's as a Linux based media player and connected it to my TV with an nVidia card using S-Video and connected the audio output to my amplifier. I rsync'd my iTunes directory from a Windows PC to the media player which included both audio and video files. At this point, I could use mplayer to play a single file or an entire directory from the shell using SSH to access the media player from my laptop. But I wanted more from my media player. I wanted a browser based interface where I could browse through my collection and select a bunch of media files and play them using mplayer.

I could have gone ahead and used an application like "Myth TV". But I did not want to lose all the information in the iTunes database. Further, I wanted to put together my own application and learn some new programming techniques and software. I have never developed a browser based application interface prior to this project. In addition, I wanted to refresh my OOP skills which were getting rusty . It has been a while since I did serious OOP development and that was in C++.

I looked around at all the pieces I needed to learn and came up with a list that looked like this: XML parsing, DOM models, JavaScript, Ajax, Java, JSP's etc. It looked like it would take me months to get through this stuff before I could develop my application. I happened to hear about the Google Web Toolkit which could hide or abstract away some of these requirements and get my application working in a short amount of time. I can always rewrite my application in the future using the above mentioned technologies and stop relying on the GWT. A working application makes it a lot easier to refer to when needed.

The application itself consists of two parts -
1. An utility that takes the iTunes song database in the form of XML or Text and populates a database.
2. A GWT application that lets the user browse a list of albums, display the songs in any selected album and allows the user to build up a playlist of selected songs and play them using mplayer.

I decided to use MySQL as the database and Tomcat as the application server. As mentioned earlier development was done using Java, GWT and eclipse.

The Tyranny of Debugging Tools

Debugging tools are great and I do like to use them when necessary. But like the proverb "To a man with a hammer everything looks like a nail", I have experienced a lot of situations where developers rush to apply their favorite tool to the problem/bug.

For example, a kernel crash happens and a bug is filed along with the "oops" information printed on the console. You may just need to look at the line of code where the crash occurred to diagnose the problem. But there seems to be a rush to try to recreate the problem using a kernel with KGDB turned on. The problem here is that it may actually take you longer to reproduce the problem due to timing changes, execution speed etc than to inspect the code and find the problem.

Similarly memory leak/overrun detection tools like dmalloc are used to debug problems where a few judiciously placed counters and print statements may be sufficient. dmalloc is great tool to use when you need to find obscure problems. But the tool also perturb the execution of the program in terms of speed and timing. This may make reproducing the bug very difficult.

In conclusion it is not only important to know how to use debugging tools but also when to use them. In some cases the humble print statement and few counters may be the simpler and quicker solution.

The Code Documentation Quagmire

Code documentation seems to get obsolete the minute it is written. As soon as a piece of code has been initially documented, what the code does and what the document describes seem to diverge very quickly with the passage of time. When a new project begins, there is a lot of enthusiasm for writing all kinds of documents - requirements, design, code and test documentation. As time passes and deadlines loom large, documentation is given the short shrift to finish the coding part of the project. Developers justify this with the expectation that they will catch up on documentation, once coding is done and there is some time before the next project starts. However, once QA gets its hands on the code, the bugs start piling up and the developers are under pressure to fix bugs to meet the project release dates. Once the project is released, the cycle repeats over. In addition, bugs are found in the previously released projects by customers. These are fixed in subsequent releases and shipped to the customer without updating the relevant documents which of course are anyway obsolete by now.

So how do we solve this problem? I will say upfront that I do not know the answer and what follows are some of my thoughts on the solution. First let's look at the need for program documentation. I don't believe in writing documentation because it is needed by some software development methodology. You write documentation so that somebody else can maintain and extend your code in the future when you are no longer working on that project. This is fairly common in startups where the first generation of developers are usually gone after a few years.

One assumption we can make is that whoever is going to look at this code is a competent developer. He does not really need a line by line description of your code. What he needs is more like a map of the program code so that he can navigate around it. What are the things I would like to see if I was taking over somebody's code?

I would like to see a brief description of the overall architecture of the program along with a brief description of the main data structures. I would also like to see a simple map of the source code tree that tells me how the main modules in the program are distributed across the files. Then in each source code file, I would like to see comments which help me understand the code. Here I would like the comments to describe obtuse pieces of code or state assumptions made in the code that are not obvious. My assumption is that if you name the functions and the variables based on what they are used for, a lot of documentation about the code is not required. For example something like "Boolean is_ip_hdr_valid(struct iphdr *ih);" does not really need comments to tell me what the function does.

The amount of documentation I suggest may be too little or may be too much. I know that I have not even written this level of documentation for a lot of projects I have been involved with. I am hoping to get to point where all my projects have atleast this level of documentation. I am also hoping someone out there will come up a tool that can help with writing and maintaining documentation.

Deploy Google Web Toolkit(GWT) Applications using Tomcat

I have been using the Google Web Toolkit to develop an Ajax based application to control my Linux based Media Player using a browser. I will post more details about the "MediaPlayer" application in the near future. This application uses the simple RPC classes provided by the GWT to communicate between the browser and the backend server. Everything worked fine in the development mode under Eclipse until I tried to deploy the compiled application under Tomcat. It took me a while to understand the deployment procedure which is not clearly explained in the toolkit documentation. I had to go through some messages at the GWT Developer Forum to get an idea about the procedure and had to spend some time debugging on the Tomcat side using its logs. Here is my take on the deployment procedure.

1) Get your application to run successfully in the development or hosted mode. Make sure that URL's used by the service entry points are of the form
String moduleRelativeURL = GWT.getModuleBaseURL() + "/mediaplayer";

The assumption is that the GWT XML file that you created for you application configuration looks like the one below and your servlet path is /mediaplayer.

<module>

   <!-- Inherit the core Web Toolkit stuff.-->
   <inherits name='com.google.gwt.user.User'/>

   <!-- Specify the app entry point class.-->
   <entry-point class='com.test.client.MediaPlayer'/>
       <servlet path='/mediaplayer' class='com.test.server.MediaPlayerServices'/>

</module>

2) Run the command mediaplayer-compile.cmd which GWT would have created for your application.

3) On the server side where Tomcat is running ,navigate over to the webapps directory . Under it create the following subtree.
webapps/MediaPlayer
webapps/MediaPlayer/WEB-INF
webapps/MediaPlayer/classes
webapps/MediaPlayer/lib

The assumption here is that your application is named MediaPlayer.

4) In your GWT application directory you will see a bunch of html,xml,css,js and gif files under the www/com.test.mediaplayer directory created whenever you ran your application in the hosted mode. Copy all the these files to your server into the webapps/MediaPlayer directory.

5) Create a web.xml file under webapps/MediaPlayer/WEB-INF to configure your application for Tomcat. It should look like

<web-app>
   <servlet>
      <servlet-name>MediaPlayer</servlet-name>
      <servlet-class>com.test.server.MediaPlayerServices</servlet-class>
   </servlet>
   <servlet-mapping>
      <servlet-name>MediaPlayer</servlet-name>
      <url-pattern>/mediaplayer</url-pattern>
   </servlet-mapping>
</web-app>

Note that the parameters you specify here should match the ones in your GWT application configuration xml file in your development area. In this example all the RPC interfaces are defined in a single class "MediaPlayerServices" and so there is a single servlet definition.

6) Copy your compiled class hierarchy under the bin directory for your GWT application area to the server under webapps/MediaPlayer/classes. The directory hierarchy should look exactly the same under bin on your client side and under "webapps/MediaPlayer/classes" on your server side.

└───com
   └───test
       ├───client
       ├───public
       └───server

Note the you do not really need to copy the public subdirectory. Also you do not need all the class files under the client sub directory. You only need the class that defines the RPC interfaces which in my case is called "MediaPlayerService.class".

7) The last step is to copy a couple of the jars that come with the GWT into the webapps/MediaPlayer/lib directory. The ones you need are "gwt-servlet.jar" and "gwt-user.jar". You can also copy other jar files related to libraries you used on the server side like the MySQL connector into this directory.

You should now be able to access your application on a browser using the URL
"http://10.0.0.1:8080/MediaPlayer/mediaplayer.html" where 10.0.0.1 is the host on which Tomcat is deployed and 8080 is the port it is listening on.

Fast Hash Tables

Hash tables seem to pop up everywhere in networking code. They are used to match TCP packets with their corresponding sockets. I have used them to match packets with actions to be taken based on destination IP and Port addresses. After having read a bit about hash tables, it seems like there is no perfect hash table but one that is the best compromise based on your requirements.

I needed a hash table that would perform well on an Intel Xeon processor and was willing to trade memory for performance. The hash table needed to be extensible as it was not possible to estimate the maximum possible size. There are couple of ways to increase the size of the hash table - one is to increase the number of buckets usually by doubling and the other by chaining entries within a bucket in the form of a linked list. There are a number of techniques to double the size of the table without locking the entire table, but most of these are complex. So extending the size of each bucket by chaining entries seems to be the way to go.

Chaining multiple entries in a bucket also means that we do not have to worry about hash collisions. There are some good techniques for calculating another hash if a bucket is full so that the entry can be inserted or found in another bucket. Hash collision techniques are great if memory is a constraint and the size of the hash table cannot be increased. Otherwise the additional complexity that comes with implementing them compared to a simple linked list does not give any advantages.

When high performance is required in situations like network packet processing, optimization needs to be done in terms of reducing latency caused due to main memory accesses by increasing the efficiency of caches. When a lookup is being done on a hash table, indexing to the bucket matching the key's hash value causes the first memory access. There does not seem to be much we can do to ensure that the bucket is in the cache in a typical server/appliance. However once the bucket has been accessed, an intel xeon processor will load 64 bytes into its L2 cache or 128 bytes if "Adjacent Sector Prefetch" is on. We can take advantage of this cache load by packing more than one entry into the 64 or 128 byte bucket. Even though the search for an entry inside the bucket would need to sequentially loop to go through the entries, it will be much faster than hashing again and accessing another bucket or following a pointer inside a linked list since the locations being accessed are in the L2 cache. Once the initial bucket entry is completely full then we can chain another 64/128 byte bucket of entries to the first one. The memory access to get to the second bucket by following the pointer is probably no worse than hashing again and accessing another bucket. Hence the previous decision on using a linked list to expand a bucket instead of double hashing or related techniques. Of course ensuring that each bucket is aligned at a 64 or 128 byte boundary is essential to take maximum advantage of the cache line size.

In short, you can get a hash table that performs well by stuffing as many entries as you can into a bucket of size that matches the cache line size of the CPU. If the bucket is full, then allocate memory equal to the cache line size and link it to the original bucket for expansion. Allocate enough buckets initially so that in most cases, you will not need to expand the hash table. Of course a good hash function is essential to distribute the entries evenly across the buckets to minimize buckets with a large number of entries that need to be searched sequentially. But that will be a discussion for another day.

Beginning

This is a collection of my thoughts and experiences with designing and coding various programs both as a part of my professional career and for personal use. I will also comment on pieces of third party code I use like the Linux kernel and on computer hardware I use and design systems with. I use a lot of tools to make me productive and will give my "very biased" opinions about them. I will post pieces of code wherever appropriate.

Please note that, whatever I publish in this blog are my personal opinions only and may not present a balanced or unbiased take on things. If you notice any factual errors on my part, please inform me and I will correct them as soon as I can.