Single Sign On for the cloud: SAML & OpenId

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 ?

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

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

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

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

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 ?

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.