The Khangaonkar Report

10 reasons for considering the Scala programming language

2013-04-25T17:27:00.000-07:00

Scala programming language has been around for a few years now and its popularity is increasing. Having programmed in Java for many years, I was initially skeptical whether we needed another programming language on the JVM. But after trying out Scala and reading about the language, I have had a change in heart. Whether your background is Java, C/C++, Ruby, python, C# or any other language, Scala has some very useful features that will force you to consider it, if you were looking for a programming language. This blog just lists the useful features. Programming examples will follow in subsequent blogs.

1. Objected oriented programming language (OOP)

Scala is a object oriented programming language. The benefits of OOP are well documented. A majority of programs today are written in some OO language. If you come from JAVA, C++, C# background, then you already know the benefits. If you are currently using a language that is not OO, then this might be one of the reasons for you to consider Scala. In Scala everything is an Object, unlike JAVA where primitives are not objects and the use of static methods lets you bypass the OO paradigm. OO programming enables you to write programs that have a structure that models that problem domain that the program is written for. This helps produce programs that are easier to read and maintain.

2. Functional programming

In contrast to OO programming, functional programming encourages the use of functions to do some work without changes in state or changes to the data it works on. Data is immutable. Functions take data as input and may produce new data as output. Additionally, a function is a type just like an Integer, String or any class. The advantage of functional programming is that there are no side effects - a function takes input and produces output , that is all. This make it easy to write error free programs that can scale or can be executed in parallel. Scala has very good support functional for programming.

3. Static Types

In statically typed languages like C++, Java and Scala, every variable has a type and the type
determines what the program can do with the variable. If you try to multiply 2 Strings, the compilation process will flag that as error. Statically typed language protect the programmer
by detecting errors and from shooting himself in the foot. If you think strong typing is annoying and leads to verbose code, then you will be pleased to know that unlike Java, Scala supports type inference ( ability to detect type ) which reduces verbosity.

4. Brevity

Scala has features that enable the programmer to write compact code as opposed to verbose code. Less code mean fewer bugs and less time spent on maintenance.

//Java
public class Person {
private String fname ;
private String lname ;

public Person(String first, String last) {
      fname = first ;
      lname = last ;
}

}

In Scala the same class is written as

class Person(fname: String,lname: String)

Scala supports type inference that helps avoid verbose code.

// Java String is in the statement twice
public String[] stringarray = new String[5] ;

// Scala type is infered as Array of Strings
val stringarray = new Array[String](5)

5. JVM language

Scala is compiled to bytecode that runs on the Java virtual machine. Since the JVM is available on every platform, your scala code will run on windows , linux , mac os and any other platform for which a JVM is available.

Another advantage is the integration with Java. Java has a very rich class library. There are several open source projects that provide additional libraries for very useful functions. Java code can be called from Scala programs very easily, which means all those function rich libraries are available for your use in Scala.

val calendar = new java.util.GregorianCalendar()
print(java.lang.String.format("%1$ty%1$tm%1$td",cal))

will print todays date in format YYMMDD.

6. Better support for concurrency

To write concurrent programs in JAVA, you had to deal with threads, the java memory model, locking , synchronization, deadlocks etc. Writing error free concurrent programs was difficult. Scala has a actor based programming model that shields the programmer from the issues you face in Java , C/C++. To write concurrent programs , you implement actors that send, receive and handle messages. The Actor model lets the programmer avoid sharing data between threads and the issues related to locking shared data.

7. Scalable programs

By avoiding locking in concurrent programs, Scala is able to exploit the parallelism in way that Java cannot. In Java, a recommended best practice for writing scalable code was to use immutable objects. With the Actor model is Scala, you use immutable objects as messages and have unsynchronized methods. Immutable object are also at the heart of functional programming (2) which Scala promotes.

How many times have we heard of a Ruby or Python application that has be rewritten in Java or C++ because it cannot scale to the increased demands of users ? With Scala, this will not be an issue.

8. Fast

Studies have shown that Scala is at least as fast as Java.
see http://research.google.com/pubs/pub37122.html

9. General purpose/multi-purpose

The brevity and compactness of Scale ensures that it can be used for scripting or rapid application development a la Ruby or Python. But the fact that it runs on JVM and its scalability features ensure that it can be used for complex applications.

10. It is getting more popular

This is a more non technical reason. Scala is getting more popular. More startups are moving to Scala. Many are skipping Java and going directly to Scala. If you are a Java programmer, learning Scala makes you more marketable. Even if you are not a Java programmer, learning Scala will open up a number of opportunities in the programming world.

Using HBase Part 2: Architecture

2013-04-04T16:54:00.000-07:00

In this blog, let us take a quick look at some architectural details of HBase.

For an introduction to NoSql and HBase, read the following blogs.
What is NoSql ?
Using HBase

Internally HBase is a a sparse, distributed, persistent, multidimensional sorted Map. While that sentence seems complicated, reading each word individually gives clarity.
sparse - some cells can be empty
distributed - data is partitioned across many hosts
persistent - stored to disk
multidimensional - more than 1 dimension (key,value,version)
Map - key and value
sorted - maps are generally not sorted but this one is

HBase uses HDFS to store the data.

An HBase table has rows and columns. Columns are grouped into column families. There is a version for each value. So table,row key, column family, column name, version are used to get to a value. Both row keys and values are byte[]s.

Table is sorted by row key, Within a column family, the columns are sorted. Storage is per column family. So logically related columns should be in a column family.

A Table is made of regions. A region has a subset of the rows in a table. A region can be described using tablename, start key, end key. A region is made up of one or more HDFS files.

The regions are managed by servers known as the region servers. There is a master server that assigns regions to region servers.

HBase has 2 catalog tables -ROOT- and .META. .META has information on all regions in the system. -ROOT- has information on .META. When a client wants to access data, these 2 tables are consulted to determine which region server has the region that should be used for this request. The client issues read/write requests to the region server directly.

HBase uses zookeeper to maintain cluster state. A simple diagram below shows the components of an HBase cluster.

Logical view of a table:
The table is figure 2 has 2 column families: cf1 with columns colA and ColB, cf2 with columns ColC

and ColD. The value in each cell is uniquely identified by row key, column family, column name and a timestamp or version.

Logical view of RegionServer:

The rows of a table are in a Region. Region is the unit of allocation and is identified by a start key and end key. The regions are distributed across the region servers in the cluster.

Physical view of Region Server:

Each Region has one of more stores. Each Store is per column family. The memStore is where changes are stored in memory before writing to disk. The file store is the persistent store and is a file written to HDFS. The Hfile is described in the blog HFile.

Each RegionServer has a write ahead log (WAL) . Writes are first written to the WAL. If the region server crashed before memory is flushed to disk, the WAL is used to recover. This implies data is stored in memory and flushed to disk periodically. Changes are sorted while in memory.

Reads look for data in memStore first and then go to disk if necessary. Data is flushed to disk in 64 Mb chunks. This size is configurable. HFiles are merged to larger files. Sorting in memory and merging files makes it like a mergeSort.

For delete, the row is marked as deleted ( as opposed to physically removing it).

HBase provides ACID semantics at a row level. HBase does multi version concurrent updates, which means updates happen by creating a new version as opposed to overwriting existing row. Writers need to acquire a lock to write. Readers do not acquire a lock.To ensure consistent reads without locking, HBase assigns a write number to each write. The read returns data from the highest write number that is durable. Locks stored in memory in the region server. This is sufficient because all values for a row are in one region server. Transactions are committed in a serial order.

Sharding is automatic. Regions split when files reach a certain size.

Compaction step which run in background combines files, removes deleted data.

This concludes the introduction to HBase architecture.

Using HBase

2013-03-15T18:38:00.000-07:00

HBase is a NoSQL database from the hadoop family. The NoSql concept is discussed in my blog at What is NoSql ? HBase is a column oriented key value store based on Google's Bigtable.

To recap, you would be considering a NoSql database because your RDBMS is probably not able to meet your requirements because of one or more of the following reasons:

You application deals with billions and billion of rows of data

Application does a lot of writes

Reads require low latency

linear scalability with commodity hardware is required

You frequently need to add more columns or remove columns

There are several NoSql databases that can address one or more of these issues. In this article I provide an introduction to HBase. The goal is to help you get started evaluating whether HBase would be appropriate for your problem. This is introductory material. More details in subsequent blogs.

Main features of HBase are :

Built on hadoop and HDFS. If you are already using hadoop , then HBase can be viewed as an extension to your hadoop infrastructure that provides random reads and writes.

A Simple data model based on keys , values and columns. More on this later.

Scales linearly by adding commodity hardware

Automatic partitioning of tables as they grow larger

Classes available for integration with MapReduce

Automatic failover support

Support rowkey range scans

Data Model

The main constructs of the model are Table, rows, column family and columns.

Data is written and read from a Table. A Table has rows and column families. Each row has a key.

Each Column family has one or more columns. Columns in a column family are logically related. Each column has a name and value. When a Table is created, the column families have to be declared. But the columns in each family do not need to be defined and can be added on demand. Each column is referred to using the syntax columnFamily:column. For example, an age column in a userprofile column family is referred to as userprofile:age. For each row, storage space is taken up only for the columns written in that row.

Let us design a Hbase table to store User web browsing information. Each user has a unique id called userid. For each user we need to store

(1) some profile information like sex, age, geolocation, membership.
(2) For each partner website he visits, store the page types viewed, products viewed.
(3) For each partner website he visits, store products purchased , product put in shopping cart but not purchased.

Our structure might look like

{
userid1:{ // rowkey
    profile:{ // column family
          sex: male, // column , value
          age : 25,

          member: Y

    },
    browsehistory: { // column family
          partner1.hp:23,    // visited partner1 homepage 23 times
          partner2.product.pr1 : 4 // viewed product pr1 4 times
    }

    shoppinghistory: { // column family

         partner3.pr3: 25.5 , // purchased pr3 from partner3 for $25.5

Let us design an Hbase table for the above structure.

Tablename : UserShoppingData. Since we will lookup data based on user, the key can be userid.

(1) ColumnFamily profile for profile information. Columns would be sex, age, member etc
(2) ColumnFamily browsehistory for browsing data. Columns are dynamic such as websitename.page or website.productid
(3) ColumnFamily shopping history for shopping data. Columns are dynamic.

The beauty is you can dynamically add columns. If visualizing this as columns is difficult, just think that you are dynamically adding key value pairs. This kind of data is required in a typical internet shopper analytics application.

HBase is an appropriate choice because you have several hundred million internet shoppers. That is several million rows. If you wanted to store data by date, you might make the key userid+date, in which case you might have even more rows - in the order of billions. Data is written as the user visits various internet shopping websites. Later the data might need to read with low latency to be able to show the user a promotion or advertisement based on his past history. A company I worked for in the past used a very popular RDBMS for such high volume writes and when ever the RDBMS was flooded with such write requests, the RDBMS would grind to a halt.

Let us use HBase shell to create the above table, insert some data into it and query it.

Step 1: Download and install HBase from http://hbase.apache.org

Step 2: Start hbase
$ ./start-hbase.sh
starting master, logging to /Users/jk/hbase-0.94.5/bin/../logs/hbase-jk-master-jk.local.out

Step 3: Start hbase shell
$ ./hbase shell
HBase Shell; enter 'help' for list of supported commands.
Type "exit" to leave the HBase Shell
Version 0.94.5, r1443843, Fri Feb 8 05:51:25 UTC 2013
hbase(main):001:0>

Step4: Create the table
hbase(main):004:0> create 'usershoppingdata','profile','browsehistory','shophistory'
0 row(s) in 3.9940 seconds

Step5: Insert some data
hbase(main):003:0> put 'usershoppingdata', 'userid1','profile:sex','male'
0 row(s) in 0.1990 seconds

hbase(main):004:0> put 'usershoppingdata', 'userid1','profile:age','25'
0 row(s) in 0.0090 seconds

hbase(main):005:0> put 'usershoppingdata', 'userid1','browsehistory:amazon.hp','11'
0 row(s) in 0.0100 seconds

hbase(main):006:0> put 'usershoppingdata', 'userid1','browsehistory:amazon.isbn123456','3'
0 row(s) in 0.0070 seconds

hbase(main):007:0> put 'usershoppingdata', 'userid1','shophistory:amazon.isbn123456','19.99'
0 row(s) in 0.0140 seconds

Step 6: Read the data
hbase(main):008:0> scan 'usershoppingdata'
ROW                        COLUMN+CELL
userid1                   column=browsehistory:amazon.hp, timestamp=1362784343421, value=11
userid1                   column=browsehistory:amazon.isbn123456, timestamp=1362786676092, value=3
userid1                   column=profile:age, timestamp=1362784243334, value=25
userid1                   column=profile:sex, timestamp=1362784225141, value=male
userid1                   column=shophistory:amazon.isbn123456, timestamp=1362786706557, value=19.99
1 row(s) in 0.1450 seconds

hbase(main):010:0> get 'usershoppingdata', 'userid1'
COLUMN                     CELL
browsehistory:amazon.hp   timestamp=1362784343421, value=11
browsehistory:amazon.isbn timestamp=1362786676092, value=3
123456
profile:age               timestamp=1362784243334, value=25
profile:sex               timestamp=1362784225141, value=male
shophistory:amazon.isbn12 timestamp=1362786706557, value=19.99
3456
5 row(s) in 0.0520 seconds

hbase(main):011:0> get 'usershoppingdata', 'userid1', 'browsehistory:amazon.hp'
COLUMN                     CELL
browsehistory:amazon.hp   timestamp=1362784343421, value=11
1 row(s) in 0.0360 seconds

Step 7: Add few more rows

hbase(main):015:0> put 'usershoppingdata', 'userid2','profile:sex','male'
0 row(s) in 0.0070 seconds

hbase(main):016:0> put 'usershoppingdata', 'userid3','profile:sex','male'
0 row(s) in 0.0060 seconds

hbase(main):017:0> put 'usershoppingdata', 'userid4','profile:sex','male'
0 row(s) in 0.0330 seconds

hbase(main):018:0> put 'usershoppingdata', 'userid5','profile:sex','male'
0 row(s) in 0.0050 seconds

Step 8: Let us do some range scans on the row key
hbase(main):024:0> scan 'usershoppingdata', {STARTROW => 'u'}
ROW                        COLUMN+CELL
userid1                   column=browsehistory:amazon.hp, timestamp=1362784343421, value=11
userid1                   column=browsehistory:amazon.isbn123456, timestamp=1362786676092, value=3
userid1                   column=profile:age, timestamp=1362784243334, value=25
userid1                   column=profile:sex, timestamp=1362784225141, value=male
userid1                   column=shophistory:amazon.isbn123456, timestamp=1362786706557, value=19.99
userid2                   column=profile:sex, timestamp=1362788377896, value=male
userid3                   column=profile:sex, timestamp=1362788385501, value=male
userid4                   column=profile:sex, timestamp=1362788392575, value=male
userid5                   column=profile:sex, timestamp=1362788398087, value=male
5 row(s) in 0.0780 seconds

hbase(main):019:0> scan 'usershoppingdata', {STARTROW => 'userid3'}
ROW                        COLUMN+CELL
userid3                   column=profile:sex, timestamp=1362788385501, value=male
userid4                   column=profile:sex, timestamp=1362788392575, value=male
userid5                   column=profile:sex, timestamp=1362788398087, value=male
3 row(s) in 0.0250 seconds

hbase(main):023:0> scan 'usershoppingdata', {STARTROW => 'userid3', STOPROW => 'userid5'}
ROW                        COLUMN+CELL
userid3                   column=profile:sex, timestamp=1362788385501, value=male
userid4                   column=profile:sex, timestamp=1362788392575, value=male
2 row(s) in 0.0160 seconds

The shell is very useful to playaround with the data model and get familiar with HBase. In a real world application , you might write code in a language like Java. There is more to HBase than this simple introduction. I will get into internals and architecture in future blogs.

Hadoop Secondary Sort: Sorting values

2013-02-15T12:37:00.001-08:00

Sorting is a core strength of the Hadoop MapReduce framework. But by default it sorts only the keys. The values for each key are not sorted. There are many use cases where the values for a key are required in a sorted order. For example, let us say a web application logs users interaction - user id, time and other log data. The log data is distributed across log files from different servers. The requirement is to get users log records in a chronological order.

The input to the map is the set of log records. Let us say (userid,time) not in any order.

The output from the reducer needs to be sorted by user by time.

user1, t1
user1, t2
user1, tn
.
.
usern, t1
usern,tn

where for each user, t1 < t2 ..... < tn.

We know Hadoop sorts the keys. We could make the map output a key that is a combination of user and time. In other words, a composite key that is a combination of userid and time. We need to write a comparator that hadoop can use to sort using the composite key. However a side effect of this is that hadoop will send records for the same user to different reducers. This means you will be not be able to reduce all the users records as a group.

Remember, the hadoop framework sorts the output of a Map by key. It then partitions the output. Each partition is intended for a Reducer. All values for a key from a Map are in the same partition. We want all the records for a user to go to the same Reducer. This implies they need to be in the same partition. Fortunately there is a way to influence partitioning. We tell hadoop to put all records for a user in the same partition by implementing a partioner that partitions just based on user id and not the composite key.

A Reducer receives partitions from several Mappers. Remember that reducer is called with a key and list of values for that key. Before the framework can call the reducer, it has to group the values for that key from all the partitions. We want the grouping to happen based on userid ( not userid + time).
So we need to implement a grouping comparator that hadoop uses for grouping and this will compare userids. Since the records in each partition are sorted by userid and time, grouping which is a merge process preserves the sort order - like a merge sort.

In summary you need to

Step 1: Make the map output key a composite of the natural key and value
Make the Map ouput key a composite of the natural key (userid) and the value (time). A composite key implements a WritableComparable. You need to override the compareTo method to use both userid and time. This method is used to order the keys using the composite key. You also need to override the write and readFields method which are called for serialization and deserialization.
You tell Hadoop to use this composite key by calling the method
job.setOutputKeyClass(UserTime.class) ;

Map output would be like

(user1,t1) , t1
(user1,t2),t2
.
(user2,t1),t1
(user2,t2),t2

Step 2: Partition Map output using only the natural key
To ensure all values for the key go the same reducer, you need to implement a partitioner. This is a class that extends org.apache.hadoop.mapreduce.Partitioner. Override the getPartition method to return a partition based on the natural key user id. You tell hadoop to partition using this partitioner with the call
job.setPartitionerClass(NaturalKeyPartitioner.class) ;

Partition from Map 1:
(user1,t1),t1
(user1,t2),t2
(user2,t1),t1
(user2,t2),t2

Partition from Map 2:
(user1,t3),t3
(user1,t4),t4
(user2,t3),t3
(user2,t4),t4

Step 3: Group values using only the natural key
To ensure the reducer gets called with all the values for the key, you need to implement a WritableComparator based on the natural key user id. Override the compare method to compare based on the userid. You tell hadoop to use this comparator for grouping with the call
job.setGroupingComparatorClass(NaturalKeyGroupComparator.class) ;

Input to Reducer 1:
key = (user1,t1), values = t1,t2,t3,t4

Input to Reducer 2:
key = (user2,t1), values = t1,t2,t3,t4

Output from Reducer1:
user1, t1
user1, t2
user1, t3
user1, t4

The complete sample source code is at SecondarySort.jar.

Generics : Array Creation

2013-01-16T17:18:00.000-08:00

How do you write a method to convert a generic collection to an Array ? A naive implementation would be:

 
public static <T> T[] convertToArray(Collection<T> c) {

   T[] a = new T[c.size()] ; // compilation error
   int i = 0 ;
   for (T x : c) {
      a[i++] = x ;

   }
     
}

The code does not compile because the type of Array is required to be able to create an array. Array is what is known as a reifiable type. A type is reifiable if its type information is available at runtime. Any java class or primitive type is reifiable.
Generics on the other hand are implemented by erasure - that is the type information is erased and runtime uses casts to get appropriate behavior. So while

 
List<T> a = new ArrayList<T> () ;

works because T is erased. Under the hood, just an ArrayList() is created and casts added when getting T. However,

 
T[] a = new T[size] ; // compile error

will not work because for arrays type information is required.
The solution is to use reflection, which is what you would if you wanted to dynamically create an instance of any reifiable type like a plain java class. The method signature in our example changes a little to take the array type as an additional parameter. Since it is easier to pass in the required array

 
public static <T> T[] convertToArray(Collection<T> c, T arry) {
   if (arry.length < c.size()) {

      arry = (T[]) java.lang.reflect.Array.newInstance(
                             arry.getClass().getComponentType(),c.size()) ;

      int i = 0 ;
      for (T x : c) {
          a[i++] = x ;
      }
   }
     
}

The newInstance method on Array creates an array of the required type. getComponentType returns the type of elements of the array. This is analagous to using reflection to a create an instance of class K. You would do

 
K.getClass.newInstance() ;

In summary, in generic methods, you can use new operator to create non-reifiable types (eg List<T>) because the type information is erased during compilation (List is created). But for reifiable type, you need to use reflection because the type information is required and cannot be erased

JAVA Garbage Collection

2012-12-19T13:10:00.000-08:00

Garbage (GC) collection is the process by which the java virtual machine frees up memory by releasing the memory taken up by objects that are no longer referenced by any other objects. Garbage collection is automatic. For simple applications, the developer does even need to be aware of garbage collection. But for applications with large memory footprint or are long running or have low latency requirements, some understanding is necessary to ensure that garbage collection does not interfere with the application. A common interference of garbage collection is that the application seems to stop responding or the time to respond goes up randomly. The articles lists a few important points every Java developer needs to know about garbage collection.

1.0 Generational GC

Since JDK 5 , the garbage collectors are what are called generational collectors. The heap is divided into regions based on the age of the objects. The young generation has objects that are short lived. The tenured generation has objects that are long lived. All objects are first created in the young region and after a while if they are alive, they are moved to the tenured generation. Garbage collection of the young region happens frequently and is generally fast. GC for the tenured region happens less frequently. Since most objects are short lived, this makes the GC more efficient.

2.0 Types of collectors

Serial Collector : Garbage from both young and tenured regions is done serially and while this happens your application is paused. This is the default collector on single cpu machines and for small heaps sizes ( less that 2G) . This is fine if your application does not care about pauses.

Parallel Collector: This is the default collector on server class machines ( multiple CPUs and greater than 2G heap size). Multiple threads/cpus are used to do garbage collection in parallel for the young region. This makes collection faster. But the application is still paused when GC happens. For the tenured region, the GC is serial as in a serial collector.

Parallel Compacting Collector: GC for the young region is the same as parallel collector and uses multiple threads. However GC for tenured region happens in parallel using multiple CPUs. Application is paused when GC happens.

Concurrent Mark Sweep Collector (CMS): For young region, it is same as in parallel collectors. But for tenured region, most of the time, GC runs concurrently with the application. The application pauses during GC are expected to be much shorter than the other collectors. This is an ideal choice for applications that cannot tolerate long pauses.

3.0 Understanding GC in your application

Before you try to tune your applications GC, it is important to understand when GC is happening, how much time it takes and how much memory it is reclaiming. The JVM provides the following options to log GC activity.

The -XX:+PrintGCDetails prints GC details described below. The -XX:+PrintGCTimeStamps prints the time from the start of the JVM to when each GC happened. The -Xloggc:gcfilename.log writes the log to gcfilename.log.

In the gc log, you will see a number of lines like

11.561: [GC [PSYoungGen: 868524K->294158K(1198848K)] 1303221K->728855K(4694144K), 0.3640750 secs] [Times: user=1.44 sys=0.02, real=0.37 secs]

This indicates that a GC of the young region occurred at time 11.561 secs from start. The young region was reduced from 868524k to 294158k (66%). The number (1198848K) is the memory allocated to the young region. The total heap was reduced from 1303221K to 728855K or 44%. The number (4694144K) is the total heap. This GC took .37 secs.

You will see a few lines like

3602.170: [Full GC (System) [PSYoungGen: 16250K->0K(1662080K)] [PSOldGen: 1594630K->1578665K(3495296K)] 1610881K->1578665K(5157376K) [PSPermGen: 22314K->22314K(35904K)], 3.4836190 secs] [Times: user=3.45 sys=0.03, real=3.48 secs]

This indicates that a full GC occurred at 3602.17 secs from the start. The young region was reduced from 16250K to 0K. The old or tenured region was reduced from 1594630K to 1578665K. The total heap was reduced from 1610881K to 1578665K. The GC took 3.48 sec.

The GCViewer is free tool to view GC logs graphically.

GC log viewed in GCViewer

The very small black lines at the bottom indicate the small GCs. The tall black lines at the hourly mark are the Full GCs. The blue peaks are lines indicating how the used heap goes up and goes down after a GC. The ruby red line just below the blue spikes shows the growth of the tenured region. You can see that the tenured region drops after a full GC. Full GCs take a lot of time and you want to reduce the frequency with which they occur.

4.0 Tuning options

The JVM offers a few knobs that one can turn to tune the GC in a way most suitable to your machine and your application.

-Xms -Xmx options are used to set the initial and maximum size of the heap. Maximum heap size should be less that physical memory on the machine to avoid paging and one should also leave aside memory for the operating system and other applications running on the same machine. While bigger heap and more memory are good because the GC has to collect less often, when it does have to collect, it has to do more work and the GC pauses could be longer.

–XX:+UseSerialGC
–XX:+UseParallelGC
–XX:+UseParallelOldGC
–XX:+UseConcMarkSweepGC

These options are used to select the GC. SerialGC and ParallelGC are selected by default depending on machine type as described earlier. Applications that have low latency requirements and cannot tolerate long GC pauses should consider switching to the Concurrent Mark Sweep GC.

-XX:NewSize=n is used to set the default initial size of the young generation. Most applications have many short lived objects and few long lived objects. The newsize should be large enough that short lived objects fit into the young generation and are garbage collected in the small GCs. If the young generation is too small, short lived object get moved to the tenured region which leads to longer Full GCs.

-XX:MaxPauseTimeMillis is a hint to the GC as to the desired maximum pause time. This is just a hint and may or may not be honoured.

5.0 References

There are many other tuning options and the following documents from Oracle are good references on tuning options as well as garbage collection in general:

1. http://www.oracle.com/technetwork/java/javase/gc-tuning-6-140523.html
2. http://www.oracle.com/technetwork/java/javase/tech/memorymanagement-whitepaper-1-150020.pdf

Spring JAVA config tutorial

2012-11-18T20:08:00.000-08:00

The classic way of configuring beans in Spring is using XML. But many programmers find switching between XML and java code annoying. Having to go into XML to debug dependencies and track down implementation classes has turned many programmers away from Spring. Since version 3.0, Spring has supported the ability to do configuration using classes and annotations without the need to use XML. In XML , to define a bean, you added to the application.xml
<bean id="Hello" class="com.mj.Hello"/>
To use the bean you wrote code like

ApplicationContext ac = new ClassPathXmlApplicationContext("application.xml") ; 
BeanFactory bf = (BeanFactory) ac ; 
Hello h = bf.getBean("Hello")
h.someMethod() ;

Let us write a new spring application using no XML.

Step1: Define the bean interface and implementation

public interface Greeting {
    public String getMessage() ;
}

public class NewYearGreeting implements Greeting {
    public String getMessage() {
        return "Happy New Year" ;
    }
}
public class BirthDayGreeting  implements Greeting {
    public String getMessage() {
        return "Happy Birthday" ;
    }
}

Step 2: Define the bean configuration in JAVA
The bean definitions are created by writing a class and annotating it with @Configuration. The individual beans are defined by annotating the method that creates the bean with @Bean.

@Configuration
public class GreetingSpringConfig {
    @Bean(name="newyear")
    public Greeting newyearGreeting() {
        return new NewYearGreeting() ;
    }
    @Bean(name="birthday")
    public Greeting birthdayGreeting() {
        return new BirthDayGreeting() ;
    }
 }

Step 3: Use the beans from a client

 public class GreetingSample {
    public static void main(String args[]) {
        ApplicationContext ac = new    
        AnnotationConfigApplicationContext(GreetingSpringConfig.class) ;
        Greeting g = (Greeting) ac.getBean("newyear") ;
        System.out.println(g.getMessage()) ; 
        g = (Greeting) ac.getBean("birthday") ;
        System.out.println(g.getMessage()) ; 
}

Note that instead of using ClassPathXmlApplicationContext ,we used AnnotationConfigApplicationContext. AnnotionConfigApplicationContext can process not just @Configuration annotated classes, but also JSR 330 annotated classes. If you don'nt like switching between JAVA & XML , then Java config is simple way of wiring your spring beans.

JAVA Synchronized HashMap vs ConcurrentHashMap

2012-10-19T18:34:00.000-07:00

A synchronized HashMap is a Map returned by calling synchronizedMap methods of java.util.Collections class.

Map syncMap = Collections.synchronizedMap(new HashMap()) ;

The characteristics of synchronized collections are:

1. Each method is synchronized using an object level lock. So the get and put methods on syncMap acquire a lock on syncMap.

2. Compound operations such as check -then - update or iterating over the collection require the client to explicitly acquire a lock on the collection object.

synchronized(syncMap) {
     Integer val = syncMap.get(key) ;
     if ( val == null) {
          syncMap.put(key, newvalue) ;

}

Without synchronization, multiple threads calling the code can lead to inconsistent values.

3. Locking the entire collection is a performance overhead. While one thread holds on to the lock, no other thread can use the collection.

4. HashMap and other collections from java.util.collections throw ConcurrentModificationException if a thread tries to modify a collection while another thread is iterating over it. The recommended approach is to acquire a lock before iterating over the map.

ConcurrentHashMap was introduced in JDK 5.

The characteristics of ConcurrentHashMap are:

1. There is no locking at the object level. The locking is at a much finer granularity. For a concurrentHashMap , the locks may be at a hashmap bucket level.

2. The effect of lower level locking is that you can have concurrent readers and writers which is not possible for synchronized collections. This leads to much more scalability.

3. Since there no locking at the object level, additional atomic methods are provided for some compound operations. The ConcurrentHashMap has methods putIfAbsent, remove, replace all of which require checking a key or value and then performing a put or remove.

The code above can be replaced by

ConcurrentHashMap concMap ;
.
.
.
concMap.putIfAbsent(key,newvalue) ;

4. ConcurrentHashMap does not throw a ConcurrentModificationException if one thread tries to modify it while another is iterating over it. The iterator returned by ConcurrentHashMap is an iterator on a snapshot of the data when the iterator was created. It may or may not have changes made by other threads after the iterator was created.

In general, using ConcurrentHashMap instead of synchronized Map gives you much better scalability and you do not have to explicitly synchronize on the map object.

Hadoop 2.x Tutorial

2012-09-16T18:59:00.000-07:00

Hadoop 2.x release involves many changes to Hadoop and MapReduce. The centralized JobTracker service is replaced with a ResourceManager that manages the resources in the cluster and an ApplicationManager that manages the application lifecycle. These architectural changes enable hadoop to scale to much larger clusters. A new release also has minor changes to scripts,directories and environment variables necessary to get started. This is a getting started tutorial for 2.x. The intended audience is someone who is completely new to hadoop and needs a jumpstart or someone who has played a little bit with a previous version and wants to start using 2.x. The emphasis on getting hadoop running and not necessarily explaining concepts which is covered in many other blogs.

In this tutorial we will

(1) Setup a hadoop in a single node environment
(2) Create and move files to HDFS
(3) Write and execute a simple MapReduce Application

Step 1: Download Hadoop and install
Download the current 2.x.x release from http://hadoop.apache.org/releases.html.
I downloaded hadoop-2.0.1-alpha.tar.gz.
Untar the file to a directory say ~/hadoop-2.0.1-alpha.

Step 2: Set the following environment variables
hadoop-2.0.1-alpha$ export HADOOP_HOME=~/hadoop-2.0.1-alpha
hadoop-2.0.1-alpha$ export HADOOP_MAPRED_HOME=~/hadoop-2.0.1-alpha
hadoop-2.0.1-alpha$ export HADOOP_COMMON_HOME=~/hadoop-2.0.1-alpha
hadoop-2.0.1-alpha$ export HADOOP_HDFS_HOME=~/hadoop-2.0.1-alpha
hadoop-2.0.1-alpha$ export YARN_HOME=~/hadoop-2.0.1-alpha
hadoop-2.0.1-alpha$ export HADOOP_CONF_DIR=~/hadoop-2.0.1-alpha/etc/hadoop

If these environment variables are not setup correctly, Step 4 might fail.

Step 3: Update the configuration files
hdfs-site.xml
Add the following configuration to etc/hadoop/hdfs-site.xml. If you do not set dfs.namenode.name.dir and dfs.datanote.data.dir explicitly, hadoop will default to a temp directory that the OS may clean up on restart and you will lose data. This is a common omission for newbees.
<?xml version="1.0" encoding="UTF-8"?>
<configuration>
<property>
    <name>dfs.replication</name>
    <value>1</value>
</property>
<property>
    <name>dfs.namenode.name.dir</name>
    <value>file:/Users/joe/hadoop-hdfs201/data/hdfs/namenode</value>
</property>
<property>
    <name>dfs.datanode.data.dir</name>
    <value>file:/Users/joe/hadoop-hdfs201/data/hdfs/datanode</value>
</property>
</configuration>
core-site.xml
Add the following to etc/hadoop/core-site.xml.
<?xml version="1.0" encoding="UTF-8"?>
<configuration>
<property>
    <name>fs.default.name</name>
    <value>hdfs://localhost:9000</value>
</property>
</configuration>
yarn-site.xml
Add the following to etc/hadoop/yarn-site.xml.
<?xml version="1.0"?>
<configuration>
<property>
    <name>yarn.nodemanager.aux-services</name>
    <value>mapreduce.shuffle</value>
</property>
<property>
    <name>yarn.nodemanager.aux-services.mapreduce.shuffle.class</name>
    <value>org.apache.hadoop.mapred.ShuffleHandler</value>
</property>
</configuration>
mapred-site.xml
Add the following to etc/hadoop/mapred-site.xml.
<?xml version="1.0"?>
<configuration>
<property>
    <name>mapreduce.framework.name</name>
    <value>yarn</value>
</property>
</configuration>

Step 4: Start the processes.

Change to the directory where hadoop is installed.
cd ~/hadoop-2.0.1-alpha

If you are running hadoop for the first time, the following command will format HDFS. Do not run this everytime as it formats and thus deletes any existing data

hadoop-2.0.1-alpha$ bin/hadoop namenode -format

Start the namenode.
hadoop-2.0.1-alpha$ sbin/hadoop-daemon.sh start namenode

Start the datanode.
hadoop-2.0.1-alpha$ sbin/hadoop-daemon.sh start datanode

In hadoop 2.x , there is no jobtracker. Instead there is a resourcemanager and a nodemanager.
Start the resourcemanager.
hadoop-2.0.1-alpha$ sbin/yarn-daemon.sh start resourcemanager

Start the nodemanager.
hadoop-2.0.1-alpha$ sbin/yarn-daemon.sh start nodemanager

Start the history server.
hadoop-2.0.1-alpha$ sbin/mr-jobhistory-daemon.sh start historyserver

Type jps. It lists the java processes running. Check that all the processes are started

hadoop-2.0.1-alpha$ jps

1380 DataNode
1558 Jps
1433 ResourceManager
1536 JobHistoryServer
1335 NameNode
1849 NodeManager

Once I ran into a problem where the mapreduce job was being accepted but never executed. In looking at the logs, I found that the NodeManager had not started. The jps command is a good check to ensure all necessary processes are started.

Step 5: Get familiar with HDFS
The HDFS commands are documented in the older releases of hadoop
http://hadoop.apache.org/docs/r1.0.3/file_system_shell.html

hadoop-2.0.1-alpha$ bin/hadoop fs -ls

will list the home directory. If you are user joe. HDFS creates a /user/joe directory for you. Any files or directories you create will be created here.

hadoop-2.0.1-alpha$ bin/hadoop fs -mkdir /user/joe/input
creates a directory input

In the local filesystem create a file app.log with the data

user01|1|2|3|4|5
user02|1|2|3|4|5
user03|1|2|3|4|5
user01|1|2|3|4|5
user02|1|2|3|4|5
user01|1|2|3|4|5
user03|1|2|3|4|5
user01|1|2|3|4|5
user04|1|2|3|4|5
user01|1|2|3|4|5

let us pretend this is a log file from a web application where for each request we have logged userid and some additional data. We will later use this .as input for a MapReduce program.
You can move it to hdfs using the command

hadoop-2.0.1-alpha$ bin/hadoop fs -moveFromLocal ~/projects/app.log /user/manoj/input/

To print the file just moved to hdfs
hadoop-2.0.1-alpha$ bin/hadoop fs -cat /user/manoj/input/app.log

Step 6: Create a MapReduce program
The MapReduce programming model is explained in the blog What is MapReduce ?. Let us write a simple mapreduce program that uses that app.log we created in step5 as input and outputs the number of times a user visited the site. UserCountMap reads a line and outputs (username,1). UserCountReducer takes as input (username, list of 1s) and outputs (username, sum).

public class UserCount {
    public static class UserCountMap extends Mapper
        public void map(LongWritable key, Text Value, Context context)
                        throws IOException, InterruptedException {
            String line = Value.toString() ;
            String tokens[] = line.split("\\|") ;
            if (tokens.length > 0) {
                context.write(new Text(tokens[0]),new IntWritable(1)) ;
            }
        }
    }
    public static class UserCountReducer extends Reducer
        public void reduce(Text key, Iterable values, Context context)
                    throws IOException, InterruptedException {
                 int count = 0 ;
            for (IntWritable value : values) {
                count = count + value.get() ;
            }
            context.write(key, new IntWritable(count)) ;
        }
    }

    public static void main(String[] args) throws Exception {
        Configuration conf = new Configuration();
        Job job = new Job(conf);
        job.setJarByClass(UserCount.class) ;
        FileInputFormat.addInputPath(job, new Path(args[0])) ;
        FileOutputFormat.setOutputPath(job, new Path(args[1])) ;
        job.setMapperClass(UserCountMap.class) ;
        job.setReducerClass(UserCountReducer.class) ;
        job.setOutputKeyClass(Text.class) ;
        job.setOutputValueClass(IntWritable.class) ;
        System.exit(job.waitForCompletion(true) ? 0 : 1) ;
    }

}

Compile the program and package into a jar called say usercount.jar.

Step 7: Run the madreduce program

hadoop-2.0.1-alpha$ bin/hadoop jar ~/projects/usercount.jar com.mj.UserCount /user/joe/input /user/joe/output

you should see output some of which is shown below.

12/09/12 17:41:28 INFO mapreduce.Job: The url to track the job: http://joe.local:8088/proxy/application_1347494786422_0003/
12/09/12 17:41:28 INFO mapreduce.Job: Running job: job_1347494786422_0003
12/09/12 17:41:37 INFO mapreduce.Job: Job job_1347494786422_0003 running in uber mode : false
12/09/12 17:41:37 INFO mapreduce.Job: map 0% reduce 0%
12/09/12 17:41:43 INFO mapreduce.Job: map 100% reduce 0%
12/09/12 17:41:45 INFO mapreduce.Job: map 100% reduce 100%
12/09/12 17:41:45 INFO mapreduce.Job: Job job_1347494786422_0003 completed successfully

You can see the status of the job at http:/localhost:8088

hadoop-2.0.1-alpha$ bin/hadoop fs -ls /user/joe/output
212/09/12 17:45:29 WARN util.KerberosName: Kerberos krb5 configuration not found, setting default realm to empty
Found 2 items
-rw-r--r--   1 manoj supergroup          0 2012-09-12 17:41 /user/joe/output/_SUCCESS
-rw-r--r--   1 manoj supergroup         39 2012-09-12 17:41 /user/joe/output/part-r-00000

The file part-r-00000 will have the output which is

user01    5
user02    2
user03    2
user04    1

Hoping these steps help jumpstart you with hadoop and get you going on your way to write more complex Map Reduce jobs to analyze your big data.

JAVA enum tutorial

2012-08-17T18:05:00.000-07:00

Java language has supported enum type for several releases. Yet, many programmers do not use it or do not fully understand all features of enum.

We still see a lot of code like this:

public static final int LIGHT = 1 ;

public static final int MEDIUM = 2 ;

public static final int HEAVY = 3 ;

public static final int SUPERHEAVY = 4 ;

int weight_range = getRange():

if (weight_range == LIGHT ) {

} else if (weight_range == MEDIUM) {

} else if (weight_range == HEAVY) {

}

Such code is error prone. It lacks type safety. If the weight_range is serialized/deserialized somewhere you are going to have to remember what 1,2,3 represent.

Java enum is a cleaner type safe way of working with constants. It is a type that has a fixed set of constant fields that are instances of the type.

1. Defining enum

Defining enum is like defining a class.

public enum WeightRange {

LIGHT, MEDIUM, HEAVY,SUPERHEAVY

} ;

defines a WeightRange enum type with 4 constant fields.

2. Creating a variable of type enum

WeightRange wclass = WeightRange.Medium ;

is like declaring any other type.

3. Using the enum

WeightRange boxer_class = getWtRangeFromSomeWhere();

if (boxer_class == WeightRange.LIGHT) {

} else if (boxer_class == WeightRange.HEAVY) {

}

is more type safe than the code without enums.

4. Enum is a class.

As mentioned above, enum is a class. Every enum type extends java.lang.Enum. All enum types thus can have additional fields and constructors.

The above WeightRange enum can be enhanced to add fields for low and high range. The values are provided in the constructor.

public enum WeightRange {

    LIGHT(0,70) ,
    MEDIUM(71,150),
    HEAVY(151,225),
    SUPERHEAVY(226,350) ;

    private final int low ;
    private final int high ;

    WeightRange(int low, int high) {
        this.low = low ;
        this.high = high ;
    }

}

5. Enum can also have methods.

In the above enum we can add a method to check if a given weight is within a weight range.

public boolean isInRange(int wt) {
       if (wt >= low && wt <= high)
           return true ;
       else
           return false ;

}

5. It can have static factory method that takes a weight as parameter and returns the correct enum.

public static WeightRange getWeightRange(int weight) {

        if (weight <= 70)
            return LIGHT ;
        else if (weight <= 150)
            return MEDIUM ;
        else if (weight <= 225)
            return HEAVY ;
        else
            return SUPERHEAVY ;

}

6. Calling toString on an enum value returns the name used to define the constant field.

System.out.println(WeightRange.LIGHT) ;

prints LIGHT

7. In converse, enum can be constructed using a String using the valueOf method.

WeightRange w3 = WeightRange.valueOf("MEDIUM") ;

System.out.println(w3) ;

will print MEDIUM

8. You can iterate over the constants defined in the enum.

for (WeightRange r : WeightRange.values()) {
System.out.println(r) ;

}

9. enum constants are final.

WeightRange.LIGHT = WeighRange.Heavy ; // compilation error

10. The only instances of an enum that can be created are the constants defined in the enum defintion.

WeightRange r = new WeightRange(12,100) ; // compilation error

Next time you need a fixed set of constants, consider using enum. It is type safe, leads to better code and your constants are within a namespace.

Scaling The Relational Database

2012-07-17T18:27:00.000-07:00

Scalability of a web application is the ability to handle increased load whether it is requests or number of users or data without having to redesign or re-architect the application. Scalability should not be confused with performance or raw speed.

One can scale by using bigger components : bigger machine, more memory, more cpu. This is vertical scaling. One can also scale by adding more copies of the same component to share the workload. This is horizontal scaling.

In a typical multi tiered web application, the middle tier, where the application logic executes, scales easily by going stateless or using a session cookie with state stored to a centralized storage. The middle tier thus scales horizontally by just adding more application servers. In reality, it has just punted the problem down the stack to the centralized storage which generally is a relational database. The database thus becomes that hardest component to scale.

The typical multi tiered web application starts with the architecture shown in figure 1. As the application become popular, the number of users increase, the number of concurrent reads and writes increase. The application slows down to a crawl and eventually grinds to halt like a braking train. In the rest of this article we discuss some strategies to avoid such a situation.

To understand issues involved in scaling the database, it is useful to think in terms of the two primary client operations on a database; READ and WRITE. Clients either read from a database or write to the database. READs can be scaled easily by adding additional servers, replicating the data and distributing the read requests across servers. Scaling WRITEs is much more complicated. Simply distributing write requests across servers will not work because the it is difficult to maintain consistency of data across servers.

Scaling reads: Master - Slave configuration

As mentioned above, a simple master slave configuration as shown in figure 2 will scale READs. In most web applications 80% of the traffic is read requests and 20% write request. Hence most of time, this configuration provides significant relief.

All WRITE requests are sent only to the master. READ requests are sent to the slaves. The master is replicated to the slaves. Note that a READ from a slave is not any faster than a READ from a master. This is because every WRITE on the master leads to a WRITE on the slave because of replication. However because there can be multiple slaves and READ request distributed across slaves, the system as whole has higher through put. As the number of READ requests go up, you can continue to scale by simply adding more slaves.

Master - Master configuration

In the master - master configuration shown in figure 3, the two servers are setup to replicate to each other. READ and WRITE requests are sent to both servers. While this gives the appearance of scaling WRITEs as well, this approach has some serious disadvantages.

Since there can be a replication lag, the data in the servers might not be identical in certain time windows, leading to read inconsistency. If any columns are ids that needs to be incremented, the logic will need to be implemented at an application level, since that has to be coordinated across the servers. You will not be able to use database features like auto incrementing ids. This does not scale beyond a couple of servers as each WRITE on every server has to be replicated to every other server.

Scaling writes : partitioning the database

The only way to scale WRITEs is to partition the database. The WRITE requests are sent to different instances of the database which may have the same or different schema. There is no replication or sharing between the instances.

Figure 4 shows an architecture where the database is partitioned by moving some of the tables to different database instances. Tables that needs joins need to be on the same instance. You cannot do SQL joins across servers. This approach works when you have many tables in the schema and some of the tables are not really related to others. This increases application complexity. The application needs connections to several instances and be aware of which instance has which table.

If you have a schema with few tables , but a large number of rows in the table, then another strategy is to keep the schema in instances the same but partition the data across servers based on some key range. For example , a USER table which has a billion rows with users from the all over the world can be partitioned across instances based on the geographical location of the user, say the continent. Figure 5 shows such an architecture. Again this requires the application logic to be smart enough to know which database instance to connect to , based on say a key value. To keep application logic simple, it helps to write a layer that handles the partitioning for the application.

Scaling even further : NoSql

If your data is even larger. of the order of petabytes or several hundred terrabytes and ACID consistancy is not a hard requirement, you might consider NoSql datastores as discussed in What is NoSql ?

5 Tips for building low latency web applications

2012-06-12T18:09:00.000-07:00

Low latency applications are those that need to service requests in a few milliseconds or microseconds. Examples of a low latency application are

Servers that serve ads to be shown on web pages. If you don'nt serve the ad as per SLA dictated by publishers, you will not be given the opportunity to serve the ad. Typically the server has a few milliseconds to respond.
Servers that participate in real time bidding. Again, taking internet advertising as an example, if you are bidding for the opportunity to show an ad, you have just a few milli-seconds to make a bid.
Applications that provide real time quotes such as a travel portal. The portal makes requests to its partner agents. For the portal to be usable, the quotes need to displayed before the user loses interest and moves on to another travel site. Typically the portal app gives each partner a few milliseconds to respond. Otherwise the response is ignored.

Here are 5 simple guidelines to remember when building low latency applications.

1. Read from Memory: Keep the data required to serve the request in memory. Keep as much as possible in local memory and then use external caches like memcached, Ehcache and the more recent NoSql key value stores. Having to read data from a database or filesystem is slow and should be avoided.

2. Write asynchronously: The thread that services the request should never be involved in writing to any external storage such database or disk. The main thread should hand off the write task to worker threads that do the writing asynchronously.

3. Avoid locks and contention: Design the application in way that multiple threads are not contending for the same data and requiring locks. This is generally not an issue if the application mostly reads data. But multiple threads trying to write requires accquiring locks that slows down the application. You should consider a design where write operations are delegated to a single thread. You might need to relax the requirement of ACID properties on data. In many cases, your users will be able to tolerate data that becomes eventually consistent.

4. Architect with loosely coupled components: When tuning for low latency, you might need to co locate certain components. Co location reduces hops and hence latency. In other cases, you might need to geographically distribute components, so that they are closer to the end user. An application built with loosely coupled components can accommodate such physical changes without requiring a rewrite of the application.

5. Horizontal scalability: Architect the application so that you can scale horizontally as the load on the application goes up. Even if you read all data from a cache, as the number of requests go up and size of data increases, because of things like garbage collection(in the case of JAVA) the latency will go up. To handle more requests without increasing latency, you will need to add more servers. If you are using a key-value store, you might need to shard the data across multiple servers to keep sub millisecond response time.

Most importantly, building and maintaining low latency is an iterative process that involves designing correctly, building, measuring performance and then tuning by looking at the design and code for improvements.

When to use explicit Locks in JAVA ?

2012-05-16T18:00:00.000-07:00

Prior to JDK 5, the only way to protect data from concurrent access was to use the synchronized keyword. The limitations of using synchronized are

(1) A thread that tries to acquire a lock has to wait till it gets the lock. There is no way to timeout.
(2) A thread that is waiting for a lock cannot be interrupted.
(3) Since synchronized applies to a block of code, the lock has to be acquired and released in the same block. While this is good most of the time, there are cases where you need the flexibility of acquiring and releasing the lock in different blocks.

The Lock interfaces and classes are well documented at java.util.concurrent.locks
The basic usage of the new Lock interface is

Lock l = new ReentrantLock() ;
l.lock() ;
try {
// update
} finally {
l.unlock() ;
}

You might be tempted to say that this can be done using synchronized. However the new Lock interface has several additional features.

1. Non blocking method
The trylock() method (without params) acquires the lock if it is available. If it is not available it returns immediately. This is very useful in avoiding deadlocks when you are trying to acquire multiple locks .

2. Timed
trylock(time......) acquires the lock if it is free within the time. Otherwise it returns false. The thread can be interrupted during the wait time.

This is useful when you have service time requirements such as in real time bidding. Say the method needs to response in 10 milli secs, otherwise the response is of no use because the bid is lost.

3. Interruptible
The lockInterruptibly method will try to acquire the lock till it is interrupted.
This is useful in implementing abort or cancel features.

4. Non block structured locking
You can acquire the lock in one method and release it in another. Or you can wrap the lock and unlock in your domain specific accquireLock() and releaseLock() methods.

This is useful in avoiding race conditions on read,update,save operations on data stored in caches. The synchronization provided by ConcurrentHashMap or Synchronized Map protects only for the duration of get and set operation. Not while the data is modified.

cache.acquireLock(key) ;
Data d = cache.get(key) ;
d.update1() ;
d.update2() ;
d.update3() ;
cache.put(key,d) ;
cache.releaseLock(key) ;

Acquiring and releasing the lock are abstracted away in acquirelock and releaseLock methods.

5. Read /Write Locks
This is my favorite feature. The ReadWriteLock interface exposes 2 locks objects. A read lock and a write lock.

You acquire the read lock when all you are doing is reading. Multiple threads can acquire the read lock.By allowing multiple readers, you achieve greater concurrency. A read lock cannot be acquired while a write lock is held by another thread.

You acquire the write lock when you need to write data. Only one thread can acquire a write lock at a time. A write lock cannot be acquired while other threads have acquired read locks.

Is the use of synchronized obsolete ?
Not really. Synchronized blocks are simple to use and are widely used. Most programmers are very familiar with its usage. They are less error prone as the lock is automatically release. It is reasonable to continue using synchronized for the the simpler use cases of locking. But if you need any of the features described above, using explicit locks is well worth the extra coding. Performance wise there is not much difference though studies have shown that explicit locks are slightly faster.

Build distributed applications using Spring HTTP Invoker

2012-04-20T13:31:00.000-07:00

Buliding distributed applications involves calling methods on objects that are remote - on different machines and/or different JVMs. Code running on machine A invokes a method on an object running on machine B and it works just as if the caller and the target were in the same JVM. In the past, CORBA, RMI and EJBs were technologies used for remote invocation. But they are complicated to use. The protocols are binary and difficult to troubleshoot. Also they are not suitable for use across intranets because they use ports that networks admins hate to open.

Since 2000, SOAP based web services enabled remote invocation using HTTP as the transport and XML for payload. While HTTP solved the problems of troubleshooting and firewalls, the performance of using XML was not very good. Some developers prefer web services using JSON over HTTP, but that requires modeling the data in JSON.

Spring HTTP Invoker is a remoting mechanism, where the programming model is plain java, but HTTP is used as the transport and the payload is created using java serialization. Spring HTTP gives developers the benefit of HTTP without the performance overhead of XML based web services. In the rest of the article, we explain with a simple example remoting using Sprint HTTP Invokers.

For this tutorial you will need

(1) Spring
(2) JDK
(3) Eclipse
(4) Tomcat

In this example, we create a service AccountService, with a method getAccount. The service is deployed to tomcat. We invoke the getAccount method from J2SE client in a different JVM. You may download the full source code for this sample at RemoteService

Step 1: create the service and implementation

Let us define an interface AccountService and its implementation AccountServiceImpl in plain JAVA.

public interface AccountService {
  public Account getAccount(int id) ;
}
public class AccountServiceImpl implements AccountService {
 @Override
 public Account getAccount(int id) {
  // TODO Auto-generated method stub
  return new Account(id,"testacct",100,2999.99F) ;
 }
}

Step 2: Spring Application context for server side
The Spring application context is defined in the file remoting-servlet.xml.

<beans>
    <bean id="accountService" class="com.mj.account.AccountServiceImpl"/>
    <bean> name="/AccountService" class="org.springframework.remoting.httpinvoker.HttpInvokerServiceExporter">
       <property name="service" ref="accountService"/>
       <property name="serviceInterface" value="com.mj.account.AccountService"/>
   </bean>
</beans>

The first bean accountService needs no explanation - it is a simple spring bean. The 2nd exports a bean /AccountService. This is exported by HttpInvokerServiceExporter, a Spring provided class. The service exported is accountService defined by the 1st bean. Since we will be invoking using HTTP, the url is /AccountService. (by convention).

Step 3: package as war and deploy to tomcat

The classes and context xml needs to be packaged as a war and deployed to tomcat. The standard spring MVC dispatcherServlet needs to be wired into the web.xml.

<servlet>
        <servlet-name>remoting</servlet-name>
        <servlet-class>
            org.springframework.web.servlet.DispatcherServlet
        </servlet-class>
        <load-on-startup>1</load-on-startup>
</servlet>
<servlet-mapping>
        <servlet-name>remoting</servlet-name>
        <url-pattern>/*</url-pattern>
</servlet-mapping>

Step 4: Create a application context for the client with the entry

<bean id="AccountProxy" class="org.springframework.remoting.httpinvoker.HttpInvokerProxyFactoryBean">
     <property name="serviceUrl" value="http://localhost:8080/remoteservice/AccountService"/>
     <property name="serviceInterface" value="com.mj.account.AccountService"/>
</bean>

This defines a bean AccountProxy whose implementation is the HttpInvokerProxyFactorybean, which will create the Http invoker. The url to invoke is http://localhost:8080/remoteservice/AccountService. http://localhost:8080 is where the target web server is listening. /remoteservice is the tomcat context ( I deployed the service as remoteservice.war). We defined /AccountService as the url for our bean in remoting-servlet.xml.

Step 5: Remote invoke the service

public class AccountServiceClient {
 public static void main(String[] args) {
   ApplicationContext applicationContext = new ClassPathXmlApplicationContext("remoteclient.xml");  
   AccountService testService = (AccountService) applicationContext.getBean("AccountProxy");  
   Account a = testService.getAccount(25) ;   
   System.out.println(a) ;
 }
}

You should see the output 25 testacct 100 2999.99

In summary, it is very easy to do remote invocation and distribute services using Spring HTTP invokers. You get the ease of plain JAVA programming and the ease of maintainence and troubleshooting because of HTTP. There is simply no reason to use RMI like protocols any more.

High Availability for Web applications

2012-03-18T10:36:00.000-07:00

As more mission critical applications move to the cloud, making the application highly available becomes super critical. An application not available for whatever reason, web server down, database down etc mean lost users, lost revenue that can be devastating to your business. In this blog we examine some basic high availability concepts.

Availability means your web application is available to your users to use. We would all like our applications to available 100% of the time. But for various reasons it does not happen. The goal of high availability is to make the application available as much as possible. Generally, availability is expressed as a percent of time that application is available per year. One may say availability is 99% or 99.9% and so on.

Redundancy and failover are techniques used to achieve high availability. Redundancy is achieved by having multiple copies of your server. Instead of 1 apache web server, you have two. One is the active server. The active server is monitered and if for some reason it fails, you failover to the 2nd server which becomes active. Another approach is to use a cluster of active servers as is done in a tomcat clusters. All servers are active. A load balancer distributes load among the members of the cluster. If one or two member of the cluster go down, no users are affects because other servers continue processing. Of course, the load balancer can become a point of failure and needs redundancy and failover.

If you were launching a new web application to the cloud, you might start of with a basic architecture as shown below without any HA consideration.

Phase 1: 1 Tomcat web server

Very soon you hit 2 issues. First whenever the server goes down, by accident or by intent, your users cannot use the application. As the number of users goes up, your server is not able to handle the load.

Phase 2: Tomcat cluster

You add redundancy and scalability by using a tomcat cluster as shown in the figure below. The cluster is fronted by Apache Web server + mod_proxy which distributes requests to the individual server. Mod_proxy is the load balancer.

Now the application scales horizontally. Tomcat or application failure is not an issue because there are other servers in the cluster. But we have introduced a new point a failure, the load balancer. If Apache+mod_proxy goes down, the application is unavailable.

To read more about setting up a tomcat cluster see Tomcat clustering

To learn how to use a load balancer with tomcat see Loadbalancing with Tomcat

Phase 3: Highly available Tomcat cluster
The figure below shows how to eliminate the point of failure and make the load balancer highly available.

You add redundancy by adding a second apache+mod_proxy. However only one of the apache is active. The second apache is not handling any requests. It merely monitors the active server using a tool like heartbeat. If for some reason, the active server goes down, the 2nd server knows and the passive server takes over the ip address and starts handling requests. How does this happen ?

This is possible because the ip address for this application that is advertised to the world is shared by the two apache's. This is know as a virtual ip address. While the 2 servers share the virtual IP, TCP/IP routes packets to only the active server. When the active server goes down, the passive server tells TCP/IP to start routing packets intended for this ip address to it. There are TCP/IP commands that let the server start and stop listening on the virtual ip address.

Tools like heartbeat and Ultramonkey enable you to maintain a heartbeat with another and failover when necessary. With heartbeat, there is a heartbeat process on each server. Config files have information on the virtual ip address, active server, passive server. There are several articles on the internet on how to setup heartbeat.

In summary, you can build highly available applications using open source tools. The key cocepts of HA, redundancy, monitoring & failover, virtual ip address apply to any service and not just web servers. You can use the same concepts to make your database server highly available.

Java Generics #2 : what is "? super T" ?

2012-02-19T22:13:00.000-08:00

Consider the merge method below that copies all elements from List source to List target.

public static <T> void merge(List<? super T> target, List<? extends T> source)

The <T> following static declares T as a new type variable for this method. We discussed "? extends T" in the blog Java Generics #1. Here, let us examine "? super T". One can guess that it is a wildcard that means any types, that are a superclass of T. If T is Integer, then List<? super T> could be List<Integer>, List<Number> or List<Object>. The code below shows the use of the merge method. In line 6, T is Integer and "? super T" is Number. In line 10, T is Number and "? super T" is Object.

1 List<Integer> aInts = new ArrayList<Integer>() ;
2 aInts.add(5) ;
3 aInts.add(7) ;
4 List<Number> aNums = new ArrayList<Number>() ;
5 aNums.add(12.5) ;
6 MCollections.<Integer>merge(aNums,aInts) ; // works
7 System.out.println(aNums.toString()) ; // aNums has 5,7,12.5
8 List<Object> aObjs = new ArrayList<Object>() ;
9 aObjs.add("hello") ;
10 MCollections.<Number>merge(aObjs,aNums) ; // works as well
11 System.out.println(aObjs.toString()) ; // aObjs has hello,5,7,12.5

We discussed in the last blog that if you have a Collection<? extends T> you can get values out of it, but you cannot put stuff into it. So what can you do with Collection<? super T> ?

In our merge example above, List<? super T> is the target, which means the implementation is putting/setting elements into it. "? super T" means any supertype of T. Logically it makes sense that you can put any supertype into the List.

The implementation of merge could be

1 public class MCollections {
2 public static <T> void merge(List<? super T> target, 
3                                List<? extends T> source) {
4   for(int i = 0 ; i < source.size(); i++) {
5     T e = source.get(i) ;
6     target.add(e) ;
7   }
8 }
9 }

But if you were to do a get, what would be the returned type ?. There would be no way to know. Hence it is not allowed as shown in line 4 of the code below.

1 List<? super Integer> aNums = new ArrayList<Number>() ;
2 aNums.add(11) ;
3 aNums.add(12) ;   
4 Number n = aNums.get(0) ; // Compilation Error - not allowed 
5 Object o = aNums.get(0) ; // allowed -- No compile error

The exception to the rule is getting an Object, which is allowed because since Object is a supertype of every other java type.

In summary, you can enable subtyping using "? super T" when you need to put objects into the collection. ( But you can get them out only as Object). You can enable subtyping using ? extends T when you need to get objects out of the collection. It follows that if you need to do both get and put, then you cannot use either of these wildcard mechanisms and you need to use a explicit type.

Java Generics #1 : Subtyping using wildcard with extends

2012-01-15T15:09:00.000-08:00

Generics is one of those more complicated language features in Java that is not well understood by many programmers. Many avoid it altogether. This is not without reason. While writing your program, if you have to stop and think a lot about syntax, there is more than a good chance, you would try to avoid that language construct. In this blog I discuss one type of subtyping with generics which can be tricky.

In Java we know that Integer extends Number. In other words, Integer is a subtype of Number. Anywhere a Number required, you can pass in an Integer. But does this mean that List<Integer> is a subtype of List<Number> ?

Consider the code. Will it work ?

1 List<Integer> aList = new ArrayList<Integer>() ;
2 aList.add(11) ;
3 aList.add(13) ;
4 List<Number> nList = aList ;
5 nList.add(11.5) ;

aList is a list of Integers. nList is a list of Numbers. In line4 nList is made to reference aList. In line 5 we add a double to aList. But aList is a list of integers. This is obviously not correct. And Java will not allow it. Line 4 will cause a compilation error. But sometimes we want to be able use subtypes. Generics have the concept of wildcards that enable subtyping when logically approriate.

Consider the addAll method of the Collection interface.

interface Collection<T> {
   public boolean addAll(Collection<? extends T> x) ;

}

? extend T says that given a collection of Type T , you can add to it elements from any collection whose type is a subtype of T. The following code is valid.

1 List<Number> aList = new ArrayList<Number>() ;
2 List<Integer> intList = Arrays.asList(11,12) ;
3 List<Double> dList = Arrays.asList(15.15) ;
4 aList.addAll(intList) ;
5 aList.addAll(dList) ;

The implemention of addAll method will get elements from the list passed in as parameter and put it into the target collection. Note that it is only a get operation on Collection<? extends T>. A put on Collection<? extends T> would however not be allowed. To understand, consider the code below

1 List <? extends Number> numList ;
2 List<Integer> intList = Arrays.asList(11,12) ;
3 numList = intList ; // Will this work ?
4 numList.add(5.67) ; // Will this work ?

Should line 3 work ? What about line 4 ?
The Java compiler allows line 3 because List<Integer> is considered a subtype of List <? extends Number>. But line 4 is a compilation error because you should not be allowed to add a double to List<Integer>.

In summary, when you have a Collection<? extends T>, it is safe to get elements out of the collection but not safe to put elements into it. Hence the compiler does not allow it.

Single Sign On for the cloud: SAML & OpenId

2011-12-18T09:29:00.000-08:00

When accessing different applications owned by different organizations, having to authenticate everytime you go from one application to another is annoying. Not only is it time consuming, but you also have to remember multiple passwords, which are often lost.

Single sign on is the ability to authenticate once and be able to move between applications seamlessly using the authenticated identity.

Within an intranet or between applications that are under the control of one development organization, single sign on for web applications can be easily implemented by generating a sessionid and passing it around using cookies. However, such a solution is proprietary and will not work if you need to leave the intranet and access other applications on the cloud. To interoperate with applications on the cloud, a more standards based solution is required.

A related concept and benefit is federated identity. Organizations can agree to a common name to refer to users. The user and his attributes needs to be created only in once place and others can refer to this information.

In this blog, we briefly examine two popular protocols that can be used for single sign on on the cloud: SAML and OpenId.

OpenId

The problem OpenId solves is that you as a user do not have to maintain and provide a password to each and every site you visit.

You maintain your password or other identifying credential with one provider known as the OpenId provider.

The website or application that you visit and that requires proof of who you are, relies on the OpenId provider to verify that you are who you claim to be. This is known as the relying party.

The basics of the OpenId protocol are:

1. You visit a web application (relying party) and enter an OpenId

2. Based on your OpenId, the relying party determines who your OpenId provider is.

3. The relying party redirects your request to the OpenId provider.

4. If you are already authenticated, this step is skipped.

The OpenId provider authenticates you by asking for a password or other information. The provider warns you that the relying party is requesting information about you.

5. The request is redirected back to the relying party where you are shown the URL you were trying to access.

The protocol does not require providers or relying parties to be registered anywhere. It uses plain HTTP requests and responses. The protocol messages are plain text key value pairs. The protocol works well with modern "Web20" AJAX style applications.

The OpenId protocol originated from consumer oriented websites such as Google, Twitter, Facebook etc and that is where this protocol is popular.

The OpenId specification is described at OpenId specification
There is a java implementation of OpenId at openid4java

SAML (Security Assertion Markup Language)

SAML is a XML based protocol that enables web based authentication, authorization and single sign on.

SAML involves a relying party requesting an assertion and a SAML provider responding with the assertion.

Examples of assertions are :
Authentication Assertion : This user was authenticated using such and such method at time t.
Attribute Assertion : This user has a title supermanager.
Authorization Assertion : This user has permission to delete file xyz.doc.

A typical SAML interaction would be as follows:

1. A user tries to access a URL or a web application which is the relying party
2. The relying party creates a SAML authentication request.
3. The relying party redirects the users browser to a SAML provider. Embedded in the request is the SAML authentication request.
4. The SAML provider evaluates the SAML request and authenticates the user.
5. The SAML provides returns a SAML authentication response to the user browser.
6. The browser forwards the SAML response back to the relying party.
7. The relying party verifies and interprets the SAML response.
8. If the response implies successful authentication, the user is redirected to the URL, he was originally trying to reach.

SAML has the concept of profiles. The interaction is different based on the profile. The interaction above is the Web SSO profile.

SAML has its origins more in enterprise software, in web services, in B2B communication and is from the early 2000s when XML was very popular. In fact SAML1.x had only a SOAP binding.

The SAML specification is at SAML Specification
There is a SAML implementation at OpenSAML

Which protocol should I use ?

OpenId is a simpler protocol. But has SAML has more features.

OpenId supports discovery of the OpenId provider. Using SAML has generally required expensive SAML projects.

OpenId supports only service provider initiated SSO. You go to a service provider web site and they need authentication. They start the conversation with the OpenId provider. SAML can also support identity provider initiated SSO. You are authenticated into your companys portal. Your company has a partner travel website for business travel. With SAML, you can go from your companys portal ( SAML provider) to the partner website ( relying party) without needing reauthentication.

SAML has been around longer than OpenId. SAML is more popular in the enterprise where as OpenId is more popular in consumer oriented applications.

Both OpenId and SAML rely on external transport layer security protocols such as SSL for the security of protocol messages.

If you are starting a new website and want to accept users from other popular sites such as google or twitter, you might consider OpenId. However if you are an enterprise and you want your authenticated users to access your partner sites without re-authentication, you might need SAML.

In summary, SAML is a feature rich protocol more popular in the enterprise. OpenId is simpler protocol with some limitations.

What is NoSQL ?

2011-11-19T20:54:00.000-08:00

NoSQL is a term used to refer to a class of database systems that differ from the traditional relational database management systems (RDBMS) in many ways. RDBMSs are accessed using SQL. Hence the term NoSQL implies not accessed by SQL. More specifically not RDBMS or more accurately not relational.

Some key characteristics of NqSQL databases are :

They are distributed, can scale horizontally and can handle data volumes of the order of several terrabytes or petabytes, with low latency.

They have less rigid schemas than a traditional RDBMS.

They have weaker transactional guarantees.

As suggested by the name, these databases do not support SQL.

Many NoSQL databases model data as row with column families, key value pairs or documents

To understand what non relational means, it might be useful to recap what relational means.

Theoretically, relational databases comply with Codds 12 rules of relational model. More simply, in RDBMS, a table is relation and database has a set of such relations. A table has rows and columns. Each table has contraints and the database enforces the constraints to ensure the integrity of data.Each row in a table is identified by a primary key and tables are related using foreign keys. You eliminate duplicate data during the process of normalization, by moving columns into separate tables but keeping the relation using foreign keys. To get data out of multiple tables requires joining the tables using the foreign keys. This relational model has been useful in modeling most real world problems and is in widespread use for the last 20 years.

In addition, RDBMS vendors have gone to great lengths to ensure that RDBMSs do a great job in maintaining ACID (actomic, consistent, integrity, durable) transactional properties for the data stored. Recovery is supported from unexpected failures. This has lead to relational databases becoming the de facto standard for storing enterprise data.

If RDBMSs are so good, Why does any one need NoSQL databases ?

Even the largest enterprises have users only in the order of 1000s and data requirements in the order of few terra bytes. But when your application is on the internet, where you are dealing with millions of users and data in the order of petabytes, things start to slow down with a RDBMS. The basic operations with any database are read and write. Reads can be scaled by replicating data to multiple machines and load balancing read requests. However this does not work for writes because data consistency needs to be maintained. Writes can be scaled only by partitioning the data. But this affects read as distributed joins can be slow and hard to implement. Additionally, to maintain ACID properties, databases need to lock data at the cost of performance.

The Googles, facebooks , Twitters have found that relaxing the constraints of RDBMSs and distributing data gives them better performance for usecases that involve

Large datasets of the order of petabytes. Typically this needs to stored using multiple machines.
The application does a lot of writes.
Reads require low latency.
Data is semi structured.
You need to be able to scale without hitting a bottleneck.
Application knows what it is looking for. Adhoc queries are not required.

What are the NoSQL solutions out there ?

There are a few different types.

1. Key Value Stores

They allow clients to read and write values using a key. Amazon's Dynamo is an example of a key value store.

get(key) returns an object or list of objects
put(key,object) store the object as a blob

Dynamo use hashing to partition data across hosts that store the data. To ensure high availability, each write is replicated across several hosts. Hosts are equal and there is no master. The advantage of Dynamo is that the key value model is simple and it is highly available for writes.

2. Document stores

The key value pairs that make up the data are encapsulated as a document. Apache CouchDB is an example of a document store. In CouchDB , documents have fields. Each field has a key and value. A document could be

"firstname " : " John ",
"lastname " : "Doe" ,
"street " : "1 main st",
"city " : "New york"

In CouchDB, distribution and replication is peer to peer. Client interface is RESTful HTTP, that integrated well with existing HTTP loadbalancing solutions.

3. Column based stores

Read and write is done using columns rather than rows. The best known examples are Google's BigTable and the likes of HBase and Cassandra that were inspired by BigTable. The BigTable paper says that BigTable is a sparse, distributed, persistent, multidimensional sorted Map. While that sentence seems complicated, reading each word individually gives clarity.
sparse - some cells can be empty
distributed - data is partitioned across many hosts
persistent - stored to disk
multidimensional - more than 1 dimension
Map - key and value
sorted - maps are generally not sorted but this one is

This sample might help you visualize a BigTable map

{
row1:{
    user:{
          name: john
          id : 123
    },
    post: {
          title:This is a post    
          text : xyxyxyxx
    }
}
row2:{
    user:{
          name: joe
          id : 124
    },
    post: {
          title:This is a post    
          text : xyxyxyxx
    }
}
row3:{
    user:{
          name: jill
          id : 125
    },
    post: {
          title:This is a post    
          text : xyxyxyxx
    }
}

}

The outermost keys row1,row2, row3 are analogues to rows. user and post are what are called column families. The column family user has columns name and id. post has columns title and text. Columnfamily:column is how you refer to a column. For eg user:id or post:text. In Hbase, when you create the table, the column families need to be specified. But columns can be added on the fly. HBase provides high availability and scalability using a master slave architecture.

Do I needs a NoSQL store ?

You do not need a NoSQL store if

All your data fits into 1 machine and does not need to be partitioned.
You are doing OLTP which required the ACID transaction properties and data consistency that RDBMSs are good at.
You need ad hoc querying using a language like SQL.
You have complicated relationships between the entities in your applications.
Decoupling data from application is important to you.

You might want to start considering NoSQL stores if

Your data has grown so large that it can no longer be handled without partitioning.

Your RDBMS can no longer handle the load.

You need very high write performance and low latency reads.

Your data is not very structured.

You can have no single point of failure.

You can tolerate some data inconsistency.

Bottomline is that NoSql stores are a new and complex technology. There are many choices and no standards. There are specific use cases for which NoSql is a good fit. But RDBMS does just fine for most vanilla use cases.

Apache Shiro : Application Security Made Easy

2011-10-18T17:02:00.000-07:00

Considering that JAVA is over 10+ years old, the number of choices for application developers that need to build authentication and authorization into their applications is shockingly low.

In JAVA & J2EE, the JAAS specification was an attempt to address security. While JAAS works for authentication, the authorization part is just too cumbersome to use. The EJB and Servlet specifications offer coarse grained authorization at a method and resource level. But these are too coarse to be of any use in real world applications. For Spring users, Spring Security is an alternative. But it is a little complicated to use, especially the authorization model. A majority of applications end up building their home grown solutions for authentication and authorization.

Apache Shiro is a open source JAVA security framework that addresses this problem. It is an elegant framework that lets you add authentication, authorization and session management to your application with ease.

The highlights of Shiro are:

It is a pure java framework. It works with all kinds of JAVA applications: J2SE, J2EE, Web, standalone or distributed.

It can integrate easily with various repositories that may host user and permissions metadata such as RDBMs, LDAPs.

It has a simple and intuitive permissions model that can apply to wide variety of problem domains. It is a model that lets you focus on your problem domain without getting you bogged down in the framework.

It has built in support for session management.

It has built in support for caching metadata.

It integrates very easily with Spring. Same applies to any J2EE application server.

Most importantly, it is very easy to use. Most of the time, all you will need to do to integrate Shiro, will be to implement a REALM that ties Shiro to your User and Permissions metadata.

Shiro Concepts

The SecurityManager encapsulates the security configuration of an application that uses Shiro.

Subject is the runtimes view of a user that is using the system. When the subject is created, it is not authenticated. For authentication, the login method must be called, passing in the proper credentials.

Session represents the session associated with an authenticated Subject. The session has a session id. Applications can store arbitrary data in the session. The session is valid until the user logs out or the session times out.

A permission represents what actions a subject may perform on a resource in the application. Out of the box Shiro supports permissions represented by colon separated tokens. Each token has some logical meaning. For example, my application may define a permission as ResourceType:actions:ResourceInstance. More concretely File:read:contacts.doc represents a permission to read a file contacts.doc. The permission must be associated with a user, to grant that permission to the user.

A Role is a collection of permissions that might represent ability to perform some organizational function. Roles make the association between users and permissions more manageable.

A Realm abstracts your user, permission and role metadata for Shiro. You make this data available to Shiro by implementing a realm and plugging it into Shiro. Typical realms use either a relational database or LDAP to store user data.

Tutorial
Let us build a simple java application that does some authentication and authorization. For this tutorial you will need:
(1) Apache Shiro
(2) A java development environment. I use Eclipse. But you can use other IDEs or command line tools as well.
(3) You may download the source code for this example at simpleshiro.zip

Step 1: Create a Shiro.ini configuration file

We will use the default file base realm that comes with Shiro. This reads the user/permission metadata from the shiro.ini file. In a subsequent tutorial, I will show how to build a realm that gets data from a relational database.

In the Ini file, let us define some users and associate some roles to them.

# Simple shiro.ini file
[users]
# user admin with password 123456 and role Administrator
admin = 123456, Administrator
# user mike with password abcdef and role Reader
mike = abcdef, Reader
# user joe with password !23abC2 and role Writer
joe = !23abC2, Writer
# -----------------------------------------------------------------------------
# Roles with assigned permissions
[roles]
# A permission is modeled as Resourcetype:actions:resourceinstances
# Administrator has permission to do all actions on all resources
Administrator = *:*:*
# Reader has permission to read all files
Reader = File:read:*
# Writer role has permission to read and write all files
Writer = File:read,write:*

In the above shiro.ini we have defined 3 users and 3 roles. The permission is modeled
as colon separated tokens. Each token can have multiple comma separated parts. Each domain and part grants permission to some application specific domain.

Step 2: BootStrap shiro into you application

Factory factory = new IniSecurityManagerFactory("classpath:shiro.ini");
SecurityManager securityManager = factory.getInstance();
SecurityUtils.setSecurityManager(securityManager);

IniSecurityManagerFactory loads the configuration from shiro.ini and creates a singleton SecurityManager for the application. For simplicity, Our shiro.ini goes with the default SecurityManager configuration which uses a Text based realm and gets user,permission,role metadata from the shiro.ini file.

Step 3: Login

Subject usr = SecurityUtils.getSubject();
UsernamePasswordToken token = new UsernamePasswordToken("mike", "abcdef");
try {
    usr.login(token);
} 
catch (AuthenticationException ae) {
    log.error(ae.toString()) ;
    return ;
}
log.info("User [" + usr.getPrincipal() + "] logged in successfully.");

SecurityUtils is a factory class for getting an existing subject or creating a new one. Credentials are passed in using an AuthenticationToken. In this case, we want to pass in a username and password and hence use the UsernamePasswordToken. Then we call the login method on the Subject passing in the authentication token.

Step 4: Check if the user has permission

if (usr.isPermitted("File:write:xyz.doc")) {
    log.info(usr.getPrincipal() + " has permission to write xyz.doc ");
} else {
    log.info(usr.getPrincipal() + " does not have permission to write xyz.doc ");
}
if (usr.isPermitted("File:read:xyz.doc")) {
    log.info(usr.getPrincipal() + " has permission to read xyz.doc ");
} else {
    log.info(usr.getPrincipal() + " does not have permission to read xyz.doc ");
}

Subject has a isPermitted method that takes a permission string as parameter and returns true/false.

Step 5: Logout

usr.logout() ;

The logout method logs the user out.
To get familiar with Shiro, try changing the UsernamePasswordToken and login as a different user. Check some other permissions. Modify the Shiro.ini file to create new users and roles with different permissions. Run the program a few times with different metadata and different input.

In a production environment, you will not want users and roles in an ini file. You want them in a secure repository like a relational database or LDAP. In the next part, I will show you how to build a Shiro Realm that can use user,role, permission metadata from a relational database.

Spring and Declarative Transactions

2011-09-10T15:06:00.000-07:00

A transaction is a unit of work that has ACID (atomic, consistent, isolated and durable) properties. Atomic means that the changes all happen or nothing happens. If money is debited from an account and credited to another account, a transaction ensures that either both the debit and credit complete or neither completes. Consistent implies that the changes leave the data in a consistent state. Isolated implies that changes do not interfere with other changes. Durable implies that once the changes are committed, they stay committed.

Resource managers such as relation databases provide a transaction manager and an API to control transactions. Those familiar with JDBC will know that by default a transaction is started because of the setting autocommit= true. Every statement that changes the database is automatically committed. This behavior can be changed by setting autocommit to false. Now the programmer must explicitly begin a transaction and then commit or rollback the transaction.

Transactions that deal with just one resource such as one database are known as local transactions. Transactions that span multiple resources such as more than one database or a database and a messaging engine are called global transactions. Global transaction are implemented using the XA protocol which involves a two phase commit. The JTA specification describes a java API for programmers to work with global transactions. The transaction methods in JDBC such as begin, commit, rollback work only with JDBC and relational databases, where as JTA can work with any transactional resource.

The code involved in working with transactions, however is boiler plate code that can be handled by a framework. At the start of the method, you need to begin a transaction and when the method completes, you need to either commit or rollback the transaction. If you have worked with EJBs, you might be familiar that you can specify in the deployment descriptor, the transactional environment in which the method should execute. For example you might say RequiresNew, which means start a new transaction before invoking the method. The container starts a new transaction before the method is invoked and commits it when the method returns. The programmer does not need to write any java code to handle transaction.

In rest of the article, we discuss with an example, declarative transaction management with Spring.

For this tutorial you will need:

(1) Spring 3.0
(2) Eclipse is optional. I use eclipse as my IDE. Eclipse lets you export the war that can be deployed to Tomcat. But you can use other IDEs or command line tools as well.
(3) You may download the source code for this example at springjdbcwithTransaction.zip .

We resuse the example from the JDBC with Spring blog we wrote some time ago. Let us add transactions support to MemberSpringJDBCDAO. This class has the insertMember method that inserts a member to the database. Let us modify the method a little bit to throw a RuntimeException after the insert into the database. The runtime exception is added to pretend that an error occured in business logic while updating the database.

public int insertMember(Member member) {
    JdbcTemplate jt = getJdbcTemplate() ;
    Object[] params = new Object[{member.getFirstname(),
        member.getLastname(),
        member.getStreet(),member.getCity(),
        member.getZip(),member.getEmail(),member.getPassword()} ;
  
    int ret = jt.update(insert_sql, params) ;
    throw new RuntimeException("simulate Error condition') ;
    return ret ;
}

In this method, would you expect the insert to be committed to the database ? The answer is Yes, though that is not the desirable behavior. The default behaviour of JDBC is autocommit = true , which means, each insert or update is committed immediately. You could set autocommit = false and explicitly commit or rollback at the end of the method. But it is much easier to let your container handle this.

To add declarative transaction management to the above method

Step 1: Define a transaction manager in springjdbcdao.xml

<bean id="txManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager"/>

Spring works with the transaction manager to begin and complete transactions.

Step 2: Turn on support for transaction annotations

Add to springjdbcdao.xml

<tx:annotation-driven transaction-manager="txManager"/>

Step 3: Add the @Transactional annotation to the insertMember method

@Transactional
public int insertMember(Member member) {

@Transactional can take properties but we will go with default values which are:

Propagation : Required

Required means a transaction is required. If there is no transaction, Spring requests the transaction manager to start one. The other possible values is Requires_New, which tells the transaction manager to always suspend the existing transaction and start a new one.

Isolation level : Default

Use the default isolation level of the underlying resource manager.

Rollback : Any runtime exception triggers a rollback

Step 4: Run the updated insertMember method using Junit test MemberSpringJDBCDAOTest.

You will see the following logs from the transaction manager indicating the transaction rolled back.

org.springframework.jdbc.datasource.DataSourceTransactionManager - Initiating transaction rollback
2501 [main] DEBUG org.springframework.jdbc.datasource.DataSourceTransactionManager - Initiating transaction rollback
2501 [main] DEBUG org.springframework.jdbc.datasource.DataSourceTransactionManager - Rolling back JDBC transaction on Connection [org.apache.derby.impl.jdbc.EmbedConnection40@13320911 (XID = 2827), (SESSIONID = 1), (DATABASE = c:\manoj\mjprojects\database\pumausers), (DRDAID = null) ]
2501 [main] DEBUG org.springframework.jdbc.datasource.DataSourceTransactionManager - Rolling back JDBC transaction on Connection [org.apache.derby.impl.jdbc.EmbedConnection40@13320911 (XID = 2827), (SESSIONID = 1), (DATABASE = c:\manoj\mjprojects\database\pumausers), (DRDAID = null) ]
2511

Use SQL to check the database table. Confirm that no record is added.

Step 5: Remove the runtimeexception from the insertMember method and run the test again.

The Spring debug log with show that the transaction is committed. Use SQL to check the database table. Confirm that a record is added to the table.

In summary, Transactions are necessary to maintain ACID properties for data sources. Declarative transactions using Spring makes that task easier.

Handling completion of concurrent tasks

2011-07-24T23:14:00.000-07:00

In the last blog on Java Executors I introduced Executors which have been the preferred way of writing multi-threaded programs in java since JDK5. In this blog we explain java.util.concurrent.Future, which helps in processing the results from concurrent task.

Prior to java.util.concurrent, if you wanted to wait for a task to complete and get some result from the task after it completed, you had to implement the wait/notify mechanism.

Up to JDK5, the interface used to model concurrent tasks was the Runnable, which has a run method. A major limitation of the run method is that it cannot return a result or throw a checked exception.

JDK5 introduced interface Callable to model concurrent tasks. The call method returns a result and can throw a checked exception.

public interface Callable {
    V call() throws Exception ;
}

How to get the result returned by call() ?
The interface Future provides methods to check if the task is completed and to retrieve the result.

public interface Future {
    boolean cancel(boolean interupt) ;
    boolean isCancelled() ;
    boolean isDone() ;
    V get() throws .......
    V get(long timeout, TimeUnit unit) throws ....... 
}

You call one of the get methods on Future to get the result. But how do you create or get a handle to a Future and how is it related to the concurrent task which might be a Callable ?

In the previous blog we discussed the ExecutorService to execute tasks and we did this by calling the execute method passing it a runnable. The ExecutorService also has a submit method that take a Callable as a parameter and returns a Future.

Future submit(Callable task) ;

The sample below brings it all together:


1 public class FileHandler {
2  private static final ExecutorService tp=Executors.newFixedThreadPool(50);
3
4  public void downloadandProcess(FileMetaData fdata) throws IOException {
5       final String filepath = fdata.getfilePath() ;   
6       Callable<File> task = new Callable() {
7       public File call() {
9          File result = download(filepath) ;   
10          return result ;
11      }
12      Future future = tp.submit(task) ;
13      //wait for the file to be downloaded 
14
15      try {
16        File f = future.get() ;
17        process(f) ;
19      } catch (InterruptedException e) {
20        Thread.currentThread().interrupt() ;
21        future.cancel(true) ;
22      }
23  }

In the above example there are 2 threads. The thread that calls the method downloadandProcess. This thread kicks of another task (thread) in line 12 to download a file. The task is defined as a Callable in lines 6-11.In line 16 the calling thread will block until a result is available from the download thread.

Using Executor, Callable & Future is thus much simpler than using java.lang.Thread and the wait/notify mechanism.

Java Executors

2011-06-05T18:31:00.000-07:00

The old way of creating threads in Java was to extend the java.lang.Thread class or to implement the java.lang.Runnable interface and pass it to Thread as argument. In this approach, the task is modeled as a Runnable and you create one or more threads for each task. There were no built in facilities to re-use threads such as thread pools. Additionally, once a task was started, there was no easy way to know when the task completed without implementing the wait/notify mechanism.

Since JDK5, another abstraction for concurrent execution of tasks is the Executor interface.

public interface Executor {
   void execute(Runnable cmd) ; 
}

The task to be executed is coded by implementating the Runnable interface, similar to the older model. However in the old model, execution is typically hard coded by extending the java.lang.Thread class.

With the executor framework, the submission and execution is decoupled by using the Executors class to create different kinds of Executor's that can execute the runnable.

The ExecutorService interface extends Executor and provides additional methods that lets callers submit tasks for concurrent execution.

While one can implement Executor or ExecutorService and delegate to Thread to do the actual work, that is generally not the recommended way.

java.util.concurrent.Executors is a class with factory methods to create concrete implementations of ExecutorService. This includes flexible thread pool based implementations. Using thread pools for concurrent execution has the advantage that it lets your application scale.

public static ExecutorService newFixedThreadPool(int nThreads) creates a thread pool that created threads upto the size nThreads. After that it created additional threads only if one of the existing thread dies.

public static ExecutorService newCachedThreadPool() created a threadpool with no upper bound on the number of threads. It will create threads as needed but can reuse existing threads.

public static ExecutorService newSingleThreadExecutor() creates a single thread. If the existing one dies, it will create a new one. But you will never have more that one thread.

public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize) lets you create a thread pool that can be scheduled to execute periodically.

Let us write a simple concurrent server using fixed thread pool.


1 public class WebServer {
2  private final ExecutorService tpool = Executors.newFixedThreadPool(50) ;
3
4  public void start() throws IOException {
5    ServerSocket socket = new ServerSocket(8080) ;
6    while(!tpool.isShutdown()) {
7        try {
8           Socket c = socket.accept() ;
9           tpool.execute(new Runnable() {
10               public void run() { process(c) ; }
11           }
12        } catch(Exception e) {
13           log("Error occured .." + e) ;
14        }
15    }
16  }
17  private void process(socket c) {
18    // service the request   
19  }
20  public void stop() {
21    tpool.shutdown() ;
22  }
23}

In line 2 we create an ExecutorService. In lines 9-11 we create a runnable for each task and submit it for execution. The shutdown call in line 21 is a graceful shutdown. Tasks that are already submitted will be completed and no new tasks are accepted.

The advantages of using Executors are:

   Decoupling of task creation with submission/excecution.
   Built in thread pools.
   Built in orderly shutdown.
   Built in scheduling. (mentioned above but not discussed)
   Ability to check or block on completion of tasks.

Today, if you needed a data structure such as a list or a Map, you use the classes in the collection framework java.util.*. Similarly for concurrent programming, you should use the executor framework in java.concurrent.* as it gives you lot of function that you would otherwise have to code yourself.

What is MapReduce ?

2011-05-08T16:38:00.000-07:00

MapReduce is a parallel programming technique made popular by Google. It is used for processing very very large amounts of data. Such processing can be completed in a reasonable amount of time only by distributing the work to multiple machines in parallel. Each machine processes a small subset of the data. MapReduce is a programming model that lets developers focus on the writing code that processes their data without having to worry about the details of parallel execution.

MapReduce requires modeling the data to be processed as key,value pairs. The developer codes a map function and a reduce function.

The MapReduce runtime calls the map function for each key,value pair. The map function takes as input a key,value pair and produces an output which is another key,value pair.

The MapReduce runtime sorts and groups the output from the map functions by key. It then calls the reduce function passing it a key and a list of values associated with the key. The reduce function is called for each key. The output from the reduce function is a key,value pair. The value is generally an aggregate or something calculated by processing the list of values that were passed in for the input key. The reduce function is called for each intermediate key produced by the map function. The output from the reduce function is the required result.

As an example , let us say you have a large number of log files that contain audit logs for some event such as access to an account. You need to find out how many times each account was accessed in the last 10 years.
Assume each line in the log file is a audit record. We are processing log files line by line.The map and reduce functions would look like this:

map(key , value) {

    // key = byte offset in log file 
    // value = a line in the log file
    if ( value is an account access audit log) {
        account number = parse account from value
        output key = account number, value = 1
    }
}
reduce(key, list of values) {
    // key = account number
    // list of values {1,1,1,1.....}
    for each value
       count = count + value

    output key , count 
}

The map function is called for each line in each log file. Lines that are not relevant are ignored. Account number is parsed out of relevant lines and output with a value 1. The MapReduce runtime sorts and groups the output by account number. The reduce function is called for each account. The reduce function aggregates the values for each account, which is the required result.

MapReduce jobs are generally executed on a cluster of machines. Each machine executes a task which is either a map task or reduce task. Each task is processing a subset of the data. In the above example, let us say we start with a set of large input files. The MapReduce runtime breaks the input data into partitions called splits or shards. Each split or shard is processed by a map task on a machine. The output from each map task is sorted and partitioned by key. The outputs from all the maps are merged to create partitions that are input to the reduce tasks.

There can be multiple machines each running a reduce task. Each reduce task gets a partition to process. The partition can have multiple keys. But all the data for each key is in 1 partition. In other words each key can processed by 1 reduce task only.

The number of machines , the number of map tasks , number of reduce tasks and several other things are configurable.

MapReduce is useful for problems that require some processing of large data sets. The algorithm can be broken into map and reduce functions. MapReduce runtime takes care of distributing the processing to multiple machines and aggregating the results.

Apache Hadoop is an open source Java implementation of mapreduce. Stay tuned for future blog / tutorial on mapreduce using hadoop.

Spring Security Tutorial #1 - Authentication and Authorization

2011-04-10T17:45:00.000-07:00

Spring security is a framework that lets you add security to spring based applications. Before Spring security, developers had to rely on J2EE security to secure java applications. J2EE provides very limited function. You could secure web resources or EJB methods. But there is nothing more. Additional drawback of J2EE security is that implementations are application server specific. If you do anything more that what is in the servlet or EJB specification, it is not portable.

In addition to basic authentication and authorization, Spring Security has support for:
Remember me authentication
Session management
ACL based security
Integration with CAS, LDAP, Open ID
and many other things.

It is not possible to cover all those topics in one article. I plan to write about Spring Security as a series of tutorials. This first installment #1 will get you started with Spring Security and help you setup basic authentication and authorization.

Authentication refers to ensuring that the user is who he or she claims to be. Any application that has any security will typically force the user to present a name and a password. If they match what is stored in the system, we say the user is authenticated and allow the user to continue using the application.

Authorization refers to ensuring that an authenticated user has the necessary permissions to perform some operation or access some data. Authorization involves checking a pre-defined policy which may say that these users have permission to perform these actions on this resource.

For this tutorial, let us take the simple web application we developed in Spring MVC blog and add security to it. Springmvc.zip was renamed to Springsecurityv1 and security metadata added. You can download the sample at Springsecurityv1.zip.

For this tutorial you will also need
(1) Spring 3.0
(2) Spring Security 3.x.
(3) Eclipse is optional. I use eclipse as my IDE. But you can use other IDEs or command line tools as well.
(4) A webserver like Tomcat
(5) Some familiarity with the Spring framework.

Note that Spring Security is packaged separately and is not included in core Spring.

Step 1:
As always, spring configuration begins in applicationcontext config file. We start by adding the namespace which has the spring configuration elements. In springsecurity-servlet.xml, the security namespace http://www.springframework.org/schema/security is added.

<beans xmlns:security="http://www.springframework.org/schema/security" 
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
       xmlns="http://www.springframework.org/schema/beans" 
       xsi:schemalocation="http://www.springframework.org/schema/beans
       http://www.springframework.org/schema/beans/spring-beans-2.0.xsd 
       http://www.springframework.org/schema/security
       http://www.springframework.org/schema/security/spring-security-3.0.3.xsd">
</beans>

Step 2:
Add the Spring security filters to the web.xml. These filters intercept requests and force authentication and authorization

<filter>
    <filter-name>springSecurityFilterChain</filter-name>
    <filter-class>org.springframework.web.filter.DelegatingFilterProxy</filter-class>
</filter>
<filter-mapping>
    <filter-name>springSecurityFilterChain</filter-name>
    <url-pattern>/*</url-pattern>
</filter-mapping>

Step 3:
Add a minimal Spring security configuration to springsecurity-servlet.xml.

<security:http auto-config="true">
    <security:intercept-url access="ROLE_manager" pattern="/**">
</security:intercept-url>
</security:http>

The http element is the element under which all web application related security configuration. The intercept-url says that for any request to any url ( pattern = "/*") , the user needs to be authenticated and a member of the role ROLE_manager.

When you try to access any URL in this application, Spring will redirect you to a page where you need to enter a username and password. The login page is generated by Spring.

But who are the valid users ? And which of them are part of role ROLE_manager.
Step 4:
A really simple way is to define the users in springsecurity-servlet.xml using the authentication-provider
element.

<security:authentication-manager>
    <security:authentication-provider>
      <security:user-service>
        <security:user authorities="ROLE_manager" name="tony" password="tony12">
        <security:user authorities="" name="raul" password="raul12">
        </security:user>
      </security:user>
    </security:user-service>
  </security:authentication-provider>
</security:authentication-manager>

In this authentication provider, 2 users tony and raul are defined in the configuration. Tony has the authority ROLE_manager.

For a production application, You will want define users, password and roles in database (or LDAP). see step 7 for database configuration.
Step 5:
From eclipse, export the war file (or use the provided war file).
Deploy the war file to tomcat.

Point your browser to http://localhost:8080/springsecurityv1/test.htm. You will be shown the login screen below.

Type in user tony and password tony12. Login will be successful and you will be served the web page below

Step 6:
Restart the browser. Clear cookies and sessions. Type the same URL.
You will be prompted for username/pwd. This time type in abc / abc12. The login will fail as abc is not a valid user.

Repeat with user raul /raul12. With raul the login succeeds. But access will be denied because raul does not have the ROLE_manager authority.
Step 7:
As mentioned earlier, you would normally not keep username/passwords in the spring configuration file. Spring provides the jdbc-user-service that lets you authenticate with users defined in a database.

In this app, springsecurity2-servlet.xml is second configuration that uses jdbc-user-service. The configuration is

<security:authentication-manager>
    <security:authentication-provider>
      <security:jdbc-user-service data-source-ref="securityDataSource"/>
    </security:authentication-provider>
  </security:authentication-manager>
  
   <bean id="securityDataSource"
       class="org.springframework.jdbc.datasource.DriverManagerDataSource">
       <property name="driverClassName" value="org.apache.derby.jdbc.EmbeddedDriver" />
       <property name="url" value="jdbc:derby:/home/mks/mkprojects/database/springusers" />
   </bean>

For this to work, you need to create database tables required by Spring. See Spring documentation for database table schema.

In summary, getting started with Spring Security is quite easy. In a few simple steps, by adding some configuration metadata, we have enabled authentication and authorization for our web application.