Wednesday, March 20, 2013

Reactor Pattern Explained - Part 2

This is the continuation of my previous post Reactor Pattern Explained - Part 1 which gives a high-level understanding of the topic.

In this blog post I will explain the implementation of Reactor Pattern with a simple Client - Server system where the server will send Hello messages to each client when their names are told to the server. The server will listen to port 9900 and multiple clients will connect to the server to shout out their names. A thread pool will not be used here. First lets run the server in a single thread. Part 3 of this series will explain how a Thread pool is used.

First lets make the Client to connect to port 9900.

public class Client {
    String hostIp;
    int hostPort;

    public Client(String hostIp, int hostPort) {
        this.hostIp = hostIp;
        this.hostPort = hostPort;
    }

    public void runClient() throws IOException {
        Socket clientSocket = null;
        PrintWriter out = null;
        BufferedReader in = null;

        try {
            clientSocket = new Socket(hostIp, hostPort);
            out = new PrintWriter(clientSocket.getOutputStream(), true);
            in = new BufferedReader(new InputStreamReader(clientSocket.getInputStream()));
        } catch (UnknownHostException e) {
            System.err.println("Unknown host: " + hostIp);
            System.exit(1);
        } catch (IOException e) {
            System.err.println("Couldn't connect to: " + hostIp);
            System.exit(1);
        }

        BufferedReader stdIn = new BufferedReader(new InputStreamReader(System.in));
        String userInput;

        System.out.println("Client connected to host : " + hostIp + " port: " + hostPort);
        System.out.println("Type (\"Bye\" to quit)");
        System.out.println("Tell what your name is to the Server.....");

        while ((userInput = stdIn.readLine()) != null) {

            out.println(userInput);

            // Break when client says Bye.
            if (userInput.equalsIgnoreCase("Bye"))
                break;

            System.out.println("Server says: " + in.readLine());
        }

        out.close();
        in.close();
        stdIn.close();
        clientSocket.close();
    }

    public static void main(String[] args) throws IOException {

        Client client = new Client("127.0.0.1", 9900);
        client.runClient();
    }
}

Notice that the client doesn't use java.nio to create the Socket. It simply uses a java.net.Socket everybody knows about.

Now lets make the Reactor in the Server.

public class Reactor implements Runnable {

    final Selector selector;
    final ServerSocketChannel serverSocketChannel;
    final boolean isWithThreadPool;

    Reactor(int port, boolean isWithThreadPool) throws IOException {

        this.isWithThreadPool = isWithThreadPool;
        selector = Selector.open();
        serverSocketChannel = ServerSocketChannel.open();
        serverSocketChannel.socket().bind(new InetSocketAddress(port));
        serverSocketChannel.configureBlocking(false);
        SelectionKey selectionKey0 = serverSocketChannel.register(selector, SelectionKey.OP_ACCEPT);
        selectionKey0.attach(new Acceptor());
    }


    public void run() {
        System.out.println("Server listening to port: " + serverSocketChannel.socket().getLocalPort());
        try {
            while (!Thread.interrupted()) {
                selector.select();
                Set selected = selector.selectedKeys();
                Iterator it = selected.iterator();
                while (it.hasNext()) {
                    dispatch((SelectionKey) (it.next()));
                }
                selected.clear();
            }
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    void dispatch(SelectionKey k) {
        Runnable r = (Runnable) (k.attachment());
        if (r != null) {
            r.run();
        } 
    }

    class Acceptor implements Runnable {
        public void run() {
            try {
                SocketChannel socketChannel = serverSocketChannel.accept();
                if (socketChannel != null) {
                    if (isWithThreadPool)
                        new HandlerWithThreadPool(selector, socketChannel);
                    else
                        new Handler(selector, socketChannel);
                }
                System.out.println("Connection Accepted by Reactor");
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }
    }
}

The Reactor is a Runnable. See the while loop in the run() method. It will call selector.select() to get the SelectionKeys which have pending IO events. When the SelectionKeys are selected, they will be dispatched one by one. See the dispatch() method. The SelectionKey will have an attatchment which is also a Runnable. This attatchement will either be an Acceptor or a Handler.
Notice how the Acceptor inner class in the Reactor accepts connections to make SocketChannels. When a SocketChannel is created a new Handler will be created as well. (HandlerWithThreadPool will be discussed in the next section)


public class Handler implements Runnable {

    final SocketChannel socketChannel;
    final SelectionKey selectionKey;
    ByteBuffer input = ByteBuffer.allocate(1024);
    static final int READING = 0, SENDING = 1;
    int state = READING;
    String clientName = "";

    Handler(Selector selector, SocketChannel c) throws IOException {
        socketChannel = c;
        c.configureBlocking(false);
        selectionKey = socketChannel.register(selector, 0);
        selectionKey.attach(this);
        selectionKey.interestOps(SelectionKey.OP_READ);
        selector.wakeup();
    }


    public void run() {
        try {
            if (state == READING) {
                read();
            } else if (state == SENDING) {
                send();
            }
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }

    void read() throws IOException {
        int readCount = socketChannel.read(input);
        if (readCount > 0) {
            readProcess(readCount);
        }
        state = SENDING;
        // Interested in writing
        selectionKey.interestOps(SelectionKey.OP_WRITE);
    }

    /**
     * Processing of the read message. This only prints the message to stdOut.
     *
     * @param readCount
     */
    synchronized void readProcess(int readCount) {
        StringBuilder sb = new StringBuilder();
        input.flip();
        byte[] subStringBytes = new byte[readCount];
        byte[] array = input.array();
        System.arraycopy(array, 0, subStringBytes, 0, readCount);
        // Assuming ASCII (bad assumption but simplifies the example)
        sb.append(new String(subStringBytes));
        input.clear();
        clientName = sb.toString().trim();
    }

    void send() throws IOException {
        System.out.println("Saying hello to " + clientName);
        ByteBuffer output = ByteBuffer.wrap(("Hello " + clientName + "\n").getBytes());
        socketChannel.write(output);
        selectionKey.interestOps(SelectionKey.OP_READ);
        state = READING;
    }
}

A Handler has 2 states, READING and SENDING. Both cant be handled at the same time because a Channel supports only one operation at one time. Since its the client who speaks first, a server Handler will start with the READING state. Notice how this Handler is attatched to the SelectionKey and how the Interested Operation is set to OP_READ. This means that the Selector should only select this SelectionKey when a Read Event occurs. Once the read process is done, the Handler will change its state to SENDING and will change the Interested Operation to OP_WRITE. Now the Selector will select this SelectionKey only when it gets a Write Event from the Channel when its ready to be written with data. When a Write Event is dispatched to this Handler, it will write the Hello message to the output buffer since now the state is SENDING. Once sending is done, it will change back to READING state with Interested Operation changed to OP_READ again. It should be obvious that since both Handler and Acceptor are Runnables, the dispatch() method of the Reactor can execute the run() method of any attatchment it gets from a selected SelectionKey.

Here is the main method. We will run it without a Thread pool for the moment.

public static void main(String[] args) throws IOException{

    Reactor reactor  = new Reactor(9900, false);
    new Thread(reactor).start();
}

To see how this works first run the server. Then run several clients and see how they get connected to the server. When each client writes a name to standard in of the client, the sever will respond to the client with a Hello message. Notice that the server runs in a single Thread but responds to any number of clients which connect to the server.

Read the next section Reacter Pattern Explained - Part 3 to see how to use a Thread pool to run Handlers.

Friday, February 22, 2013

Reactor Pattern Explained - Part 1

Handling concurrent events a Server receives is often thought of as a use-case for creating a separate thread for each IO event listener. Most programmers are tempted to use the famous socket loop for creating Sockets for every incoming connection.

class Server implements Runnable {
    public void run() {
        try {
            ServerSocket ss = new ServerSocket(PORT);
        while (!Thread.interrupted())
            new Thread(new Handler(ss.accept())).start();
            // or, single-threaded, or a thread pool
        } catch (IOException ex) { }
    }
}

class Handler implements Runnable {
    final Socket socket;
    Handler(Socket s) { socket = s; }
    public void run() {
        try {
            byte[] input = new byte[MAX_INPUT];
            socket.getInputStream().read(input);
            byte[] output = process(input);
            socket.getOutputStream().write(output);
        } catch (IOException ex) { }
    }
    private byte[] process(byte[] cmd) { }
}

The disadvantage of using a separate thread for each event listener is the overhead of context switching. In the worst case, some threads handling event listeners which do not read or write data frequently, will be context switched periodically without doing useful work. Every time such a Thread is dispatched to the CPU by the scheduler, it will be blocked until an IO event occurs, in which case all the time spent waiting for an IO event will be wasted. Note that ss.accept() is a blocking call which blocks the server thread till a client connects. The server thread will not be able to call start() method of the new Handler thread until it is returned from ss.accept(). To reduce the wastage of CPU time by unnecessary context switches, the concept of non blocking IO was invented.

Reactor Pattern is an event handling design pattern used to address this issue. Here, one Reactor will keep looking for events and will inform the corresponding event handler to handle it once the event gets triggered. To explain this I am using some Java code borrowed from some lecture slides by Professor Doug Lea. To see his explanation please go through this set of slides.

Java provides a standard API (java.nio) which could be used to design non-blocking IO systems. I will explain the Reactor pattern with a simple client server model where the clients will shout out their names to the server while the server will respond to the corresponding client with a Hello message.

There are two important participants in the architecture of Reactor Pattern.

1. Reactor  


A Reactor runs in a separate thread and its job is to react to IO events by dispatching the work to the appropriate handler. Its like a telephone operator in a company who answers the calls from clients and transfers the communication line to the appropriate receiver. Don't go too far with the analogy though :).

2. Handlers


A Handler performs the actual work to be done with an IO event similar to the actual officer in the company the client who called wants to speak to.

Since we are using java.nio package, its important to understand some of the classes used to implement the system. I will simply repeat some of the explanations by Doug Lea in his lecture sides to make the readers lives easy :).

Channels


These are connections to files, sockets etc. that support non blocking reads. Just like many TV channels can be watched from one physical connection to the antena, many java.nio.channels.SocketChannels corresponding to each client can be made from a single java.nio.channels.ServerSocketChannel which is bound to a single port.

Buffers


Array-like objects that can be directly read or written to by Channels.

Selectors


Selectors tell which of a set of Channels has IO events.

Selection Keys


Selection Keys maintain IO event status and bindings. Its a representation of the relationship between a Selector and a Channel. By looking at the Selection Key given by the Selector, the Reactor can decide what to do with the IO event which occurs on the Channel.

Now lets try to understand what Reactor Pattern is. Take a look at this diagram.

 
Here, there is a single ServerSocketChannel which is registered with a Selector. The SelectionKey 0 for this registration has information on what to do with the ServerSocketChannel if it gets an event. Obviously the ServerSocketChannel should receive events from incoming connection requests from clients. When a client requests for a connection and wants to have a dedicated SocketChannel, the ServerSocketChannel should get triggered with an IO event. What does the Reactor have to do with this event? It simply has to Accept it to make a SocketChannel. Therefore SelectionKey 0 will be bound to an Acceptor which is a special handler made to accept connections so that the Reactor can figure out that the event should be dispatched to the Acceptor by looking at SelectionKey 0. Notice that ServerSocketChannel, SelectionKey 0 and Acceptor are all in same colour ( Gray I suppose :) )

The Selector is made to keep looking for IO events. When the Reactor calls Selector.select() method, the Selector will provide a set of SelectionKeys for the channels which have pending events. When SelectionKey 0 is selected, it means that an event has occurred on ServerSocketChannel. So the Reactor will dispatch the event to the Acceptor.

When the Acceptor accepts the connection from Client 1, it will create a dedicated SocketChannel 1 for the client. This SocketChannel will be registered with the same Selector with SelectionKey 1. What would the client do with this SocketChannel? It will simply read from and write to the server. The server does not need to accept connections from client 1 any more since it already accepted the connection. Now what the server needs is to Read and Write data to the channel. So SelectionKey 1 will be bound to Handler 1 object which handles reading and writing. Notice that SocketChannel 1, SelectionKey 1 and Handler 1 are all in Green.

The next time the Reactor calles Selector.select(), if the returned SelectionKey Set has SelectionKey 1 in it,  it means that SocketChannel 1 is triggered with an event. Now by looking at SelectionKey 1, the Reactor knows that it has to dispatch the event to Handler 1 since Hander 1 is bound to SelectionKey 1. If the returned SelectionKey Set has SelectionKey 0 in it, it means that ServerSocketChannel has received an event from another client and by looking at the SelectionKey 0 the Reactor knows that it has to dispatch the event to the Acceptor again. When the event is dispatched to the Acceptor it will make SocketChannel 2 for client 2 and register the socket channel with the Selector with SelectionKey 2.

So in this scenario we are interested in 3 types of events.
  1. Connection request events which get triggered on the ServerSocketChannel which we need to Accept.
  2. Read events which get triggerd on SocketChannels when they have data to be read, from which we need to Read.
  3. Write events which get triggered on SocketChannels when they are ready to be written with data, to which we need to Write.

A SelectionKey will have all the information about the relationship with its corresponding Channel and the Selector. It will have information about the corresponding Handler too. Selector will just select the SelectionKeys which have pending IO events. This way the Reactor can decide how to deal with the IO events accordingly. The relationships among the Channels, Selection Keys and Handlers can be put in a table as follows.

Selection Key Channel Handler Interested Operation
SelectionKey 0 ServerSocketChannel Acceptor Accept
SelectionKey 1 SocketChannel 1 Handler 1 Read and Write
SelectionKey 2 SocketChannel 2 Handler 2 Read and Write
SelectionKey 3 SocketChannel 3 Handler 3 Read and Write

Now what does a Thread pool has to do with this? Let me explain. The beauty of non blocking architecture is that we can write the server to run in a single Thread while catering all the requests from clients. Just forget about the Thread pool for a while. Naturally when concurrency is not used to design a server it should obviously be less responsive to events. In this scenario when the system runs in a single Thread the Reactor will not respond to other events until the Handler to which the event is dispatched is done with the event. Why? Because we are using one Thread to handle all the events. We naturally have to go one by one.

We can add concurrency to our design to make the system more responsive and faster. When the Reactor dispatches the event to a Handler, it can start the Handler in a new Thread so that the Reactor can happily continue to deal with other events. This will always be a better design when performance is concerned. To limit the number of Threads in the system and to make things more organized, a Thread pool can be used.

I believe this explanation is adequate for us to get our hands dirty with some coding.

Please read Reactor Pattern Explained - Part 2 and Reactor Pattern Explained - Part 3.

Wednesday, November 28, 2012

Eulerian Trail

Remember the puzzle your friends gave you when you were a kid "Traverse the graph without lifting your pencil" ? Had you known about the "Eulerian Trails" then, you could have dazzled your friends. A more advanced version of the puzzle would be "Draw the longest trail on the graph without lifting your pencil". So how do you handle this?

In Graph Theory, Eular showed the necessary conditions for a graph to be traversed as such. Such a trail or path which traverses the entire graph is called an "Eulerian Tail". To say this more mathematically "A trail which visits every edge exactly once is an Eulerian Trail". If the Eulerian Trail ends at the point where it was started, then the trail becomes a closed circuit which would be named as an "Eulerian Circuit". A graph which has an Eulerian Circuit is an "Eulerian Graph". If the graph does not have an Eulerian Circuit but just an Eulerian Trail which does not end at the point where it was started, then the graph is called "Semi-Eulerian". Got it so far?

So the bottom line is, "a trail which can be drawn to traverse the entire graph without lifting the pencil will exist if and only if the graph is Eulerian or Semi-Eulerian".

Euler gives the necessary conditions for a graph to be Eulerian or Semi-Eulerian.
  • Every vertex in the graph must have an even degree, for the graph to be Eulerian.
  • If the graph has two odd vertices, Then the graph is Semi-Eulerian where the Eulerian trail will start from one odd vertex and end at the other.
  • If there are more than two odd vertices, then the graph does not have an Eulerian tail.
What Eular says is logically correct because,
  • If a vertex has an even degree, then that vertex will not be a dead end where you would get stuck when traversing, because when you enter such a vertex there is always a way to exit. So you can visit every edge connected to that vertex.
  • If all the vertices in the graph are even, then you can traverse the entire graph and come back to the vertex where you started.
  • If you meet an odd vertex on your way traversing the graph, then could get stuck there, unless of course this vertex is the end of the Eulerian trail, because in an odd vertex, the number of edges to exit the vertex will be one less than the number of edges to enter the vertex. (Just like Hotel California, "You can checkout any time you like, but you can never leave" :P)
  • Logically, if you start the Eulerian trail from one odd vertex, you wont end your trail there, and neither will you at an even vertex, but you will end the trail in another odd vertex.
  • So obviously if you have more than two odd vertices, some of the edges connected to those odd vertices will be not be visited. In such a case, the graph will not be Eulerian.
There is a special property in Non-Eulerian graphs. That is, the number of odd vertices is always even. To understand this logically, lets take the smallest graph you can draw which is a single line. Here you have two odd vertices. When you create larger graphs by adding edges to this smaller graph,
  • if the vertex to which you connect the new edge, is odd, it will become even.
  • If you don't connect the other end of the new edge to any vertex in the graph, like the edge (6,4) in the bellow graph, then the total number of odd vertices in the graph won't change.
  • If you connect the other end to an odd vertex it will become even too, in which case the total number of odd vertices will be reduced by 2.
  • If the other end is connected to an even vertex, then that vertex will become odd and the total number of odd vertices will be unchanged.
If you apply this logic to the case where you connect the first end of the new edge to an even vertex, you'll see that to total number of odd vertices will always be even.
Get the idea? For more information, read the Wikipedia article Eulerian Path.

Now lets do some coding. :)

First lets assume a graph like this is represented as an "Adjacency List". In Java we can create an Adjacency List as follows, assuming vertices are numbered with integers.


When such a graph is given, it should be checked if it's Eulerian , Semi-Eulerian or Non-Eulerian. We can use the Eulers' conditions to decide that. Check this piece of code.


If the graph is not Eulerian, we can make it Semi-Eulerian so that we can find the longest trail to visit the maximum number of edges without lifting the pencil.

To do this we have to remove the minimum number of edges from the graph such that the graph becomes Semi-Eulerian. The following code shows how a Non-Eulerian graph is converted to a Semi-Eulerian graph when the set of odd vertices is given. Here the edges will be removed such that the number of odd vertices in the set be reduced to 2. So here 2 odd vertices will be chosen from the set such that the path connecting the the 2 chosen odd vertices will be the shortest. This will make sure that the number of edges removed to make the 2 chosen odd vertices even, be minimal. This procedure is continued until you get 2 odd vertices in the graph. For this we need a shortest path finding algorithm. I'm using the famous Breadth First Search algorithm for its simplicity. Explaining BFS is out of the scope of this post. Here is the code.


Get the code for BFS from here.

Excellent!! Now we have a graph which has an Eulerian trail. Now we have to find it :). How ?? Simple !! Hierholzer's algorithm provides a simple yet effective solution. The idea is straight forward.
  • If the graph is Eulerian, start from any vertex, if its Semi-Eulerian start from one of the odd vertices.
  • When an edge is visited, add the vertices to the path and remove the edge from the graph, so that it won't be visited again.
  • If the graph is Semi-Eulerian you might come to the other odd vertex without traversing the entire graph where as if the graph is Eulerian, you might come to the starting vertex without traversing the whole graph. Here, the unvisited edges make up an Eulerian graph. 
  • In this case, look for vertices which are already in the path with non visited edges. Start traversing from one of them until you come back to that vertex.  If you still have edges left continue the same process recursively until you run out of edges.
  • You have to keep track of the path accordingly. 
Check the code below. This algorithm returns the Eulerian Trail.

Hope this would come in handy. GL & HF :D