AVL Search Tree

With BST the problem is that it should be balanced properly so that the height of a tree with node n should be log(2)n. But since BST does not have any balancing algorithm which re-balances the tree on every insert/delete, the tree becomes unbalanced. In this case the height of the tree may go up to n (same as the number of elements n). So the worst case scenario for search is O(n) for a BST.

An AVL tree on the other hand is supposed to be balanced. Balanced means that
* Either the tree is empty
* Or for every node in a non-empty tree height(left_sub_tree) - height(right_sub_tree) <= 1

The idea is that whenever we insert/remove an element from the tree, we should check that the tree is balanced and if not, we should perform "rotations" to balance the tree.

For example we have a tree

        c
       /
      b

If we add a node "a" to the tree we will get

        c
       /
      b
     /
    a

Now the left subtree is of height 2 and the right subtree is of height 0, so it is unbalanced. So a single right rotation is performed to balance the tree.

      b
     / \
    a   c

Lets see a few algorithms to insert and remove nodes from an AVL tree

Single LL & RR rotation will do the following converstion



Simple rotation to left:

function Rotate_LL(oldRoot)
{
  Result = oldRoot.left;
  oldRoot.left = Result.right;
  Result.right = oldRoot;
  AdjustHeight(oldRoot);
  AdjustHeight(Result);
  AdjustHeight(oldRoot.left);
  return Result;
}

Simple rotation to right:

function Rotate_RR(oldRoot)
{
  Result = oldRoot.right;
  oldRoot.right = Result.left;
  Result.left = oldRoot;
  AdjustHeight(oldRoot);
  AdjustHeight(Result);
  AdjustHeight(oldRoot.right);
  return Result;
}

Following are the RL and LR rotations:

Double rotation to right:


Double rotation to left:


Lets assume that every node has a height attribute. AdjustHeight function updates the height to reflect the current height of the tree

Function adjustHeight(Node)
{
  if (Node != null) then
  {
    Node.height=1+max(height(node.left),height(node.right));
  }
}

Function to get the height of the node

Function getHeight(Node)
{
  if(Node == Void) return 0
  else return Node.height
}

Insert record in AVL tree. Remember that the tree has to be rebalanced after insert.

Function insertData(key, data)
{
  Node = new Node(key, data);
  root = insertNode(root, Node);
  root = rebalanceForInsert(root);
  adjustHeight(root);
}

Function insertNode(root, newNode)
{
  if (root == Void) root = newNode;
  else
  {
    if(root.key > newNode.key)
      root.left = insertNode(root.left, newNode);
    else
      root.right = insertNode(root.right, newNode);
  }
  result = rebalanceForInsert(root);
  adjustHeight(result);
}

Function rebalanceForInsert(Node)
{
  h_LL = height(Node.left.left);
  h_LR = height(Node.left.right);
  h_R = height(Node.right);
  h_RR = height(Node.right.right);
  h_RL = height(Node.right.left);
  h_L = height(Node.left);
  if( (h_LL == h_LR) && (h_LR >= h_R) )
    result = rotate_LL(Node);
  else if( (h_RR == h_RL) && (h_RL >= h_L) )
    result = rotate_RR(Node);
  else if( (h_LR == h_LL) && (h_LL >= h_R) )
    result = rotate_LR(Node);
  else if( (h_RL == h_RR) && (h_RR >= h_L) )
    result = rotate_RL(Node);
  else result = Node;
  return result;
}

Lets look at how to remove node from an AVL tree

Function Remove(key)
{
  if (root==void) result = void;
  else if(root.key == key)
  {
    result = root.data;
    root = removeNode(root);
  }
  else
    result = removeRec(root,key);
  adjustHeight(root);
  root = rebalanceForDel(root);
}

Function RemoveRec(node, key)
{
  if(root.key > key) //remove from left subtree
  {
    if(root.left == void) result = void;
    else if(root.left.key == key)
    {
      result = root.left.data;
      root.left = removeNode(root.left);
    }
    else
    {
      result = removeRec(root.left, key);
      adjustHeight(root.left);
      root.left = rebalanceForDel(root.left);
    }
  }
  else //remove from right subtree
  {
    if(root.right == void) result = void;
    else if(root.right.key == key)
    {
      result = root.right.data;
      root.right = removeNode(root.right);
    }
    else
    {
      result = removeRec(root.right, key);
      adjustHeight(root.right);
      root.right = rebalanceForDel(root.right);
  }
  return result;
}

Function removeNode(Node)
{
  if(Node.left == void) result = Node.right;
  else if(Node.right == void) result = Node.left;
  else (child = root.left)
  {
    if(child.right == void)
    {
      Node.data = child.data;
      Node.left = child.left;
    }
    else
      Node.left = swap_and_remove_left_nbr(Node,child);
    adjustHeight(Node);
    result = rebalanceForDel(Node);
  }
}

Function swap_and_remove_left_nbr(Parent, child)
{
  if(child.right.right != void)
    child.right = swap_and_remove_left_nbr(parent, child.right);
  else
  {
    parent.data = child.right.data;
    child.right = child.right.left;
  }
  adjustHeight(parent);
  result = rebalanceForDel(parent);
}

Function rebalanceForDel(Node)
{
  h_LL = height(Node.left.left);
  h_LR = height(Node.left.right);
  h_R = height(Node.right);
  h_RR = height(Node.right.right);
  h_RL = height(Node.right.left);
  h_L = height(Node.left);
  if( (h_LL >= h_LR) && (h_LR >= h_R) )
    result = rotate_LL(Node);
  else if( (h_RR >= h_RL) && (h_RL >= h_L) )
    result = rotate_RR(Node);
  else if( (h_LR >= h_LL) && (h_LL >= h_R) )
    result = rotate_LR(Node);
  else if( (h_RL >= h_RR) && (h_RR >= h_L) )
    result = rotate_RL(Node);
  else result = Node;
  return result;
}

That is quite a lot of stuff to digest...
Happy chewing...

Binary Search Tree

In a tightly packed binary search tree you need at max log(2)n comparisons to find a match for n elements. So, for example to search a list of 1000 elements, you should need max 10 comparisons. Additions and deletions from the BST (binary search tree) require that the sorted order of elements should be maintained.

Let us see some pseudo code for creating and maintaining binary search trees

Find an element X in a BST with root node N:

find (X, N)
{
  if(N == NULL) return NULL;
  if(X == N.data) return N;
  else if (X < N.data) return find(X, N.leftChild);
  else if (X > N.data) return find(X, N.rightChild);
}


Find the node with the minimum data. Start from root node N

findMinimum(N)
{
  if(N == NULL) return NULL;
  if(N.leftChild == NULL) return N;
  return findMinimum(N.leftChild);
}

Insert data X in a BST with root node N

Insert(X, N)
{
  if(N == NULL) //insert at last node
  {
    N = new BinaryNode(X, NULL, NULL);
    return;
  }
  if(X == N.data) // data already exists in BST, ignore X
    return;
  else if(X < N.data) Insert(X, N.leftChild);
  else Insert(X, N.rightChild);
}


Delete an element X from the BST with root node N

Delete(X, N)
{
  if(N == NULL) return;
  if(X < N.data) Delete(X, N.leftChild);
  else if (X > N.data) Delete(X, N.rightChild)
  else // X == N.data. Delete and readjust all children
  {
    if(N.leftChild == NULL && N.rightChild == NULL)
    {
      delete N;
      N = null;
      return;
    }
    else if(N.leftChild == NULL)
    {
      tmpN = N;
      N = N.rightChild;
      delete tmpN;
    }
    else if(N.rightChild == NULL)
    {
      tmpN = N;
      N = N.leftChild;
      delete tmpN;
    }
    else //replace N.data with minimum data from right subtree
    {
      tmpN = findMinimum(N.rightChild);
      N.data = tmpN.data;
      delete(N.data, N.rightChild);
    }
  }
}

Traversing binary trees

What are trees? Trees are data structures which contain a node and one or more children. A binary tree is a tree in which each node is either empty or contains at max two children.

A binary tree...

root --------> R
                /    \
               L     R
              /  \   /  \
             l  r   rl  

A binary tree of height h<=0 has at max 2^h+1 - 1 nodes. And the height of the tree h = log2(n), where n is the number of nodes in the binary tree.

Lets check out the recursive functions used to traverse the binary trees:

1. Preorder traversal:
Preorder traversal does the following recursively :
-> visit the root
-> traverse left subtree
-> traverse right subtree

function preorder(tree)
{
  if (tree == null) return;

  print(tree.root);
  call preorder(tree.left_subtree);
  call preorder(tree.right_subtree);
}

2. Inorder traversal:
Inorder traversal does the following recursively :
-> traverse left subtree
-> visit the root
-> traverse right subtree

function inorder(tree)
{
  if (tree == null) return;

  call inorder(tree.left_subtree);
  print(tree.root);
  call inorder(tree.right_subtree);
}

3. Postorder traversal:
Postorder traversal does the following recursively :
-> traverse left subtree
-> traverse right subtree
-> visit the root

function postorder(tree)
{
  if (tree == null) return;

  call postorder(tree.left_subtree);
  call postorder(tree.right_subtree);
  print(tree.root);
}

4. Breadth-first or level-order traversal:
In Level-order traversal each level is visited successively starting from root(level-0) and nodes are visited from left to right on each level. This is generally implemented using a queue data structure.

- push the root node in the queue
- pop the node from the queue, push the left and right child node in the queue.
- pop the root->left node from the queue and push the left and right child node of root->left in the queue.
- pop the root->right node from the queue and push the left and right child node of root->right in the queue.

function levelorder(tree)
{
  queue.push(tree.root);
  while(queue.size > 0)
  {
    Node n = queue.pop(); //get first node in queue
    if (n.left != null) queue.push(n.left);
    if (n.right != null) queue.push(n.right);
    print n;
  }
}

Priority Queue & Heapsort

A priority queue is a queue where each item has a priority associated with it. And the item with the highest priority is at the top of the queue. So, you will be removing the highest priority items from the queue first.

A priority queue can be implemented using a heap where the heap is implemented using a complete binary tree. A complete binary tree is supposed to have the heap property if the root has higher priority than its child and each child also follows the same heap property.

Now, lets try to understand this thing in english.

A complete binary tree is a tree filled from left to right. So, this is a complete binary tree. Also, it could be seen that for each node the root is always bigger than the child nodes. That is the heap property. And since the root has the highest priority and it is the first element, this is also a priority queue. If you remove the root, you will have to re-arrange the elements so that the new root again has the highest priority.

The benefit of using a heap structure is that inserting new element and removing root are handled in a constant O(log n) time, that is the time taken to re-arrange the elements. When the highest priority element is removed, we put the last element in the tree (lowest right element) at the root position. This new root is compared with both its children and if it has low priority as compared to either of its children, it is exchanged with the child. This goes on till the node resides at a place where its children are of lower priority and its parent is of higher priority. While inserting a new element, we place it at the last available node (remember, the tree should always be a complete tree), and move it up (basically follow the reverse procedure of removing root).

A heap of n elements could be easily stored using n sequential locations in an array. The left child node of node at position k is placed at position 2k, and the right child node is placed at 2k+1.

So, for the above heap, the elements would be stored as

16, 11, 9, 10, 5, 6, 8, 1, 2, 4



Lets check out the pseudo code for pushing and popping elements from the heap:

function heapPop(arr, count)
{
  start = (count-2)/2;
  while(start >= 0)
  {
    shiftDown(arr, start, count-1);
    start = start=1;
  }
}

function shiftDown(arr, start, end)
{
  root = start;
  while root*2+1 <= end // while root has only 1 child
  {
    child = root*2+1;
    if ( child+1 < end ) and ( arr[child]<a[child+1] )
      child = child+1;
    if ( arr[root] < arr[child] )
    {
      swap(arr[root], arr[child]);
      root = child;
    }
    else
      return;
  }
}

function heapPush( arr, count)
{
  end = 1;
  while (end < count )
  {
    shiftUp(arr, 0, end);
    end = end+1;
  }
}

function shiftUp(arr, start, end)
{
  child = end;
  while (child > start )
  {
    parent = floor((child-1)/2);
    if(arr[parent] < arr[child])
    {
      swap(arr[parent],arr[child]);
      child = parent;
    }
    else
      return;
  }
}

function heapSort(arr, count) // input is unsorted array "arr" of "count" elements
{
  heapPop(arr, count);
  end = count-1;
  while(end > 0)
  {
    swap(arr[end],arr[0]);
    end = end-1;
    heapPop(arr, count);
  }
}

Recursive algos

Few recursive algos:

Factorial:

function factorial(int n)
{
  if ( n==0 ) return 1;
  else return n*factorial(n-1);
}


Fibonacci numbers:

function fibo(int n)
{
  if( (n==0) || (n==1) ) return 1;
  else return fibo(n-1)+fibo(n-2);
}

Greatest common divisor of 2 numbers :

function gcd(int x, int y)
{
  if(y == 0) return x;
  else return gcd(y, x%y);
}

Tower of Hanoi: Given 3 pegs, one with a set of N disks of increasing size, determine the minimal/optimal no of steps required to move the disks from their initial position to another peg without placing a larger disk on top of a smaller one

function hanoi(int n)
{
  if(n==1) return 1;
  else return 2*hanoi(n-1)+1;
}

Binary search : Search an ordered array of elements by cutting the array in half on each pass

function binary_search(int* data, int tofind, int start, int end)
{
  int mid = start + (end-start)/2; // no float/double
  
  if(start > end)
    return -1;
  else if(data[mid] == tofind)
    return mid;
  else if(data[mid] > tofind)
    return binary_search(data, tofind, start, mid-1);
  else
    return binary_search(data, tofind, mid+1, end);
}

google chrome on linux

So, you visit http://www.google.com/chrome every other day with the hope that there would be version of chrome for linux out. And everytime you see the "For Windows Vista/XP only", you feel jealous of windows users and you want to ask google guys why they came out with "chrome for windows" before "chrome for linux".

Though, we still do not have any official version of chrome for linux, i looked around and found 2 ways of installing chrome on linux. It is possible using wine.

1 way gives you a complete geeky way of doing it. You can find it here : http://www.myscienceisbetter.info/2008/09/install-google-chrome-on-linux-using-wine.html. But it did not work on my system. Some problem with ALSA it said.

So i looked again and again and found out something known as crossover chromium. You can find it here http://www.codeweavers.com/services/ports/chromium/. It provides pre-compiled binaries for installation on your system.

Basically the guys at codeweavers had taken up some developer build 21 of chrome from google and ported it on linux using wine. It would not update itself. But if you are able to install the "geeky" way, then chrome might update itself. Basically something to feel a bit satisfied till you get the "google chrome for linux" official version

postgresql replication using slony-I

As most postgresql users must be knowing, postgresql does not provide any inbuilt replication solution. There are lots of 3rd party replication products available for postgresql. Slony is one of them. Slony is a trigger based replication solution, that is it used triggers to push data to the slave. Slony is supposed to be one of the most stable replication solutions for postgresql.

You can download slony from www.slony.info. There are two major versions of slony - slony-I & slony-II. Slony-I is a simple master-slave replication solution. Whereas slony-II is a advanced multi-master replication solution. We will go ahead with simple master-slave replication solution. So we will download Slony-I. The latest version available is Slony-I 1.2.15. Slony-I 2.0 is in RC and should be soon released. But we will go with a stable release - 1.2.15.

Postgresql version being used is 8.3.3. To install slony, simply untar the downloaded file and run
./configure --with-pgconfigdir=<path to pg_config>
make
sudo make install


I have used two machines for setting up replication. Installed postgresql and slony-I on both of them.

master server ip : 172.16.3.211
slave server ip : 172.16.3.173


We will be working with the superuser postgres which is used to start and stop the postgresql server.

Quick steps

• Define environment variables on master & slave. The main purpose is to make our task easier. Lets create an env.sh file containing all the definitions.
  
  #!/bin/sh
  
  REPLICATIONUSER=postgres
  CLUSTERNAME=replcluster
  MASTERDBNAME=repltestdb
  SLAVEDBNAME=repltestdb
  MASTERHOST=172.16.3.211
  SLAVEHOST=172.16.3.173
  MASTERPORT=5432
  SLAVEPORT=5432
  MASTERDBA=postgres
  SLAVEDBA=postgres
  PSQL=/usr/local/pgsql/bin/psql
  CREATEDB=/usr/local/pgsql/bin/createdb
  CREATELANG=/usr/local/pgsql/bin/createlang
  CREATEUSER=/usr/local/pgsql/bin/createuser
  PGDUMP=/usr/local/pgsql/bin/pg_dump
  
  export REPLICATIONUSER CLUSTERNAME MASTERDBNAME SLAVEDBNAME MASTERHOST SLAVEHOST PSQL CREATEDB CREATELANG CREATEUSER PGDUMP MASTERPORT SLAVEPORT MASTERDBA SLAVEDBA
  
  
  As you can see here, my postgresql is installed in /usr/local/pgsql. I have defined the IP addresses & ports of master and slave servers. I have used the superuser postgres for replication. And i have defined the master and slave databases to be used for replication. You can replicate between databases with different names on master and slave - just change the names in all the scripts.


• Create database on master & slave
  On master run
  /usr/local/pgsql/bin/createdb -O $REPLICATIONUSER -h $MASTERHOST -p $MASTERPORT $MASTERDBNAME
  On slave run
  /usr/local/pgsql/bin/createdb -O $REPLICATIONUSER -h $SLAVEHOST -p $SLAVEPORT $SLAVEDBNAME


• Since slony-I depends on triggers for replication, you will need to install the plsql procedural language on master to generate and run triggers & stored procedures for pushing data to slave.
  /usr/local/pgsql/bin/createlang -h $MASTERHOST -p $MASTERPORT plpgsql $MASTERDBNAME


• Put some tables in the $MASTERDBNAME on master, which you want to replicate. And port the tables to slave. It has to be done manually.
  
  Dump the tables on master
  /usr/local/pgsql/bin/pg_dump -s -U $MASTERDBA -h $MASTERHOST -p $MASTERPORT $MASTERDBNAME > replmaster.sql
  
  Import the tables on slave
  /usr/local/pgsql/bin/psql -U $SLAVEDBA -h $SLAVEHOST -p $SLAVEPORT $SLAVEDBNAME < replmaster.sql


• And now configure the databases for replication. When you install Slony-I, it puts two binaries slonik and slon in the pgsql/bin directory. Slonik is the tool which is used for creating configuration tables, stored procedures and triggers. All we need to do is create a configuration file to pass it to the slonik tool. Here i am assuming that there are two tables which need to be replicated - parent & child.
  
  vim replconfig.cnf
  # define the namespace the replication system uses in our example it is
  # replcluster
  cluster name = replcluster;
  # admin conninfo's are used by slonik to connect to the nodes one for each
  # node on each side of the cluster, the syntax is that of PQconnectdb in
  # the C-API
  node 1 admin conninfo = 'dbname=repltestdb host=172.16.3.211 port=5432 user=postgres';
  node 2 admin conninfo = 'dbname=repltestdb host=172.16.3.173 port=5432 user=postgres';
  # init the first node. Its id MUST be 1. This creates the schema
  # _$CLUSTERNAME containing all replication system specific database
  # objects.
  init cluster ( id=1, comment = 'Master Node');
  # Add unique keys to table that do not have one.
  # This command adds a bigint column named "_Slony-I_$CLUSTERNAME_rowID" to the table which will have a default value of nextval('_$CLUSTERNAME.s1_rowid_seq') and have UNIQUE & NOT NULL constraints applied on it.
  # table add key (node id = 1, fully qualified name = 'table_name');
  # Slony-I organizes tables into sets. The smallest unit a node can
  # subscribe is a set.
  # you need to have a set add table() for each table you wish to replicate
  create set (id=1, origin=1, comment='parent child table')
  set add table (set id=1, origin=1, id=1, fully qualified name = 'public.parent', comment='parent table');
  set add table (set id=1, origin=1, id=2, fully qualified name = 'public.child', comment='child table');
  # Create the second node (the slave) tell the 2 nodes how to connect to
  # each other and how they should listen for events.
  store node (id=2, comment = 'Slave node');
  store path (server = 1, client = 2, conninfo='dbname=repltestdb host=172.16.3.211 port=5432 user=postgres');
  store path (server = 2, client = 1, conninfo='dbname=repltestdb host=172.16.3.173 port=5432 user=postgres');
  store listen (origin=1, provider = 1, receiver =2);
  store listen (origin=2, provider = 2, receiver =1);
  
  Pass the config file to slonik for creating required triggers & config tables.
  
  /usr/local/pgsql/bin/slonik replconfig.cnf


• Lets start the replication daemons on master & slave
  
  On master run
  /usr/local/pgsql/bin/slon $CLUSTERNAME "dbname=$MASTERDBNAME user=$MASTERDBA host=$MASTERHOST port=$MASTERPORT" > slon.log &
  
  On slave run
  /usr/local/pgsql/bin/slon $CLUSTERNAME "dbname=$SLAVEDBNAME user=$SLAVEDBA host=$SLAVEHOST port=$SLAVEPORT" > slon.log &
  
  Check out the output in slon.log files


• Now everything is setup and from the slon.log files on master and slave you can see that both the servers are trying to sync with each other. But still replication is not on way. To start replication we need to make the slave subscribe to the master. Here is the required config file for doing this
  
  startrepl.cnf
  # This defines which namespace the replication system uses
  cluster name = replcluster;
  # connection info for slonik to connect to master & slave
  node 1 admin conninfo = 'dbname=repltestdb host=172.16.3.211 port=5432 user=postgres';
  node 2 admin conninfo = 'dbname=repltestdb host=172.16.3.173 port=5432 user=postgres';
  # Node 2 subscribes set 1
  subscribe set ( id = 1, provider = 1, receiver = 2, forward = no);
  
  Passing this file to slonik will do the trick and replication would start happening.
  
  /usr/local/pgsql/bin/slonik startrepl.cnf

Now simply make some inserts, updates and deletes on the master and check out whether they are happening on the slave as well. Officially, since replication is on full swing all changes in master tables should be replicated on the slave.

Please note that new tables & changes to table structures wont be replicated automatically. So whenever a new table is created or an existing table is altered the changes has to be manually propagated to slave and the scripts need to be run to make appropriate changes in the triggers and config tables.

Another important thing to note is that postgresql on master and slave should be able to communicate with both the ip addresses. For this add the ip addresses in the pgsql/data/pg_hba.conf.

For the able replication i had added the lines
host all all 172.16.3.211/32 trust
host all all 172.16.3.173/32 trust
to the pg_hba.conf file in both master & slave.

An auto ride in Delhi

I have been coming back from baroda and it was around 7 AM in the morning. The train was already 2 hours late and would stop at new delhi railway station in some time. I was ready with my backpack. As soon as the train stopped, i got down and proceeded to the exit (Ajmeri gate side) to catch an auto for noida (my residence).

As soon as i came to the road outside the station and almost half a kilometer from the auto stand, as usual i saw lots of people who were asking me for auto and taxi. The taxi agents came first - yes i called them agents cause they try to catch you first and take a commission from the auto/taxi. The quotes i got for noida was 250/-. I was like WTF!!! I said no to all of them and came out and approached the auto stand. There were tons of auto but only a few were going to noida and their fare was 200/- min. Officially the fare is around 120/-. Then i saw this man who was shouting "noida, noida", and i asked him for a quote. He told me 150/-, I bargained and finally we froze at 130/- I went to his auto and saw that it was already full. There were two good looking ladies in the back seat and i was supposed to ride with the driver. The "ladies" were paying 250/- for the trip to noida. So the auto was going to make 380/- for this ride. Ghosh!!!

I had avoided the prepaid booth cause of the long queue over there. As we rode out of the stand a white clothed police man stopped us and asked the auto wala for his prepaid receipt. Usually the prepaid booth issues a receipt which i have to give to the auto at the destination, and the auto wala presents this receipt to the prepaid booth to collect his payment. Since this auto was a totally self arranged one, we did not have any receipt. So, instead of issueing a receipt for us (convenience for passenger), we were asked to get down and another couple who had a receipt were asked to board the auto. I was again like WTF!!!. After half an hour of bargain, i get an auto and the police man simply hands it over to someone else.

Well, so i thought, why not get a receipt from the prepaid booth. I stood in the queue for 15 minutes and got a receipt for 140/- to a place known as ashok nagar which is on the border of noida & delhi. If you would ask, why not into noida to my destination, i would say that the prepaid booth does not provide service to U.P. It was just that i remembered the name of the place and got the receipt. Now, the police man who was assigning passengers to autos were not visible. I stood for some time and looked around and i spotted a crowd. The crowd would move to an auto and the auto would depart with passengers, then the crowd would move to the next auto. I went near "the crowd", and saw that it was a junior policeman surrounded with lots and lots of passengers all havine prepaid receipts. Everyone was trying to put his receipt on priority and the policeman was enjoying the attention he was getting. He would go to an auto, assign it a passenger, scold the auto-wala and then talk on his mobile and then move to the next auto - all at his liesure. He had to do this whole day, and it seemed he was enjoying his work.

Finally, the policeman saw my receipt and assigned me an auto. I jumped in, glad that finally i am going to get home. It was almost 8:30 - 1.5 hours to get an auto. We departed. But my adventure does not end here. As soon as we were out of the auto stand and on the road, the auto wala turned his head to me and asked me where was i going.

Let me try to paint a picture of the auto wala. He is a male, 40ish, with black and white hair. He is very untidy and smelly. It seems that he has not bathed in few days. He is smoking a bidi (an indian version of ciggerate) from the side of his mouth. And he has an attitude - "i am the king of the road".

So, i told him that i have to go to sector 12 in noida, but he can leave me at ashok nagar and i will take a manual rickshaw from there, if he wants. the auto wala says from the side of his mouth (he has bidi on the other side). He will drop me at my place - sector 12 noida, if i pay him 100/- extra. I was a bit shocked. After spending 1.5 hours in getting an auto i am still at the same price. I told him that i will pay him 40/- extra. After everything, we finally bargained a deal at 200/-. And, i finally relaxed on the back of the auto.

No sooner had i done this that, a bus overtook the auto from the wrong side and at a very close distance. I jumped up. The auto wala was cool. I asked him whether he had given indicator or not. And he showed me his foot which was sticking out in the direction where we were about to turn. I said "wow...".

Now, i began to notice the way the auto was being driven. We were exactly in the center of the road, in such a manner that no car can overtake us from the right side. If a vehicle has to overtake us, it has to do it from the wrong side. There were lots of honking behind us. A car was getting frustrated. We were moving at a constant speed of 35, and the car was trying to overtake us from the right side, but the auto would not give way to it. Finally the car overtook us from the wrong side. The car-driver glared at the auto-driver but the auto driver did not look at him.

We were half way and suddenly the auto started struggling. It coughed and died. I got down and pushed the auto to the side of the road. The auto-driver got out a bottle and put in some oil in his tank. I asked him what is this oil, and he told me it is kerosene. The auto was started and i could see the whitish black and smelly smoke from its exhaust. I got back in and we continued our journey. Now we were climbing a flyover and the auto's speed dropped to 15 kmph. It was not able to pull me up but the auto driver was very persistent, so we finally made it to the top.

Again we were in the middle of the road and some car was trying to overtake us. I looked to my side and i could see another auto just next to mine. Both autos were at their top speed i.e. 20 kmph and both were trying to race. There was a smile on my auto-driver's face because he was an inch ahead of the other auto. Behind, i could see cars and busses trying to adjust to this low speed and honking, so that they would be given side for overtaking. The flyover ended and so did the race (i think) and my auto driver won.

As soon as we entered noida, we started jumping red lights. Delhi traffic police are a bit strict and you cant jump red ligts there, but in noida, there are hardly any police at the red lights. Anyways, after saving his auto from 2-3 near collisions, we finally turned and parked the auto at my place. I handed over the prepaid receipt and another 100/- Rs. And the auto driver got out 40/- and paid me back. So, after a delay of 2.5 hours and after spending 200/- rs, i was finally home.

After Death

HTML / XML Expert...

Networking Expert...

Programmers...

setting up hadoop

Have updated the post with latest hadoop config changes compatible with hadoop 1.1.2

Hadoop is a distributes file system similar to google file system. It uses map-reduce to process large amounts of data on a large number of nodes. I will give a brief step by step process to set up hadoop on single and multiple nodes.

First lets go with a single node:

• Download hadoop.tar.gz from hadoop.apache.org.


• You can setup hadoop to work on any user, but it is preferred that you setup a separate user for running hadoop.
  sudo addgroup hadoop
  sudo adduser -g hadoop hadoop


• untar hadoop.tar.gz file in the user "hadoop's" home directory
  [hadoop@linuxbox ~]$ tar -xvzf hadoop.tar.gz


• check version of java - it should be atleast java 1.5 - preferred java 1.6
  $ java -version
  java version "1.6.0"
  Java(TM) SE Runtime Environment (build 1.6.0-b105)
  Java HotSpot(TM) Server VM (build 1.6.0-b105, mixed mode)


• Hadoop requires to ssh to the local server. So you would need to creat keys on local machine so that the ssh does not require password.
  $ ssh-keygen -t rsa
  Generating public/private rsa key pair.
  Enter file in which to save the key (/home/hadoop/.ssh/id_rsa):
  Enter passphrase (empty for no passphrase):
  Enter same passphrase again:
  Your identification has been saved in /home/hadoop/.ssh/id_rsa.
  Your public key has been saved in /home/hadoop/.ssh/id_rsa.pub.
  The key fingerprint is:
  fb:7a:cf:c5:c0:ec:30:a7:f9:eb:f0:a4:8b:da:6f:88 hadoop@linuxbox
  now copy the public key to the authorized_keys file, so that ssh should not require passwords
  cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys
  Now check
  $ ssh localhost
  Last login: Sat Oct 18 18:30:57 2008 from localhost
  $


• Change environment parameters in hadoop-env.sh
  export JAVA_HOME=/path/to/jdk_home_dir


• Change configuration parameters in hadoop-site.xml. 

In hadoop 1.1.1, hadoop-site.xml has been replaced by 3 files - core-site.xml, hdfs-site.xml and mapred-site.xml

<configuration>

in core-site.xml

<property>
<name>fs.default.name</name>
<value>hdfs://localhost:54310</value>
<description>The name of the default file system. A URI whose
scheme and authority determine the FileSystem implementation. The
uri's scheme determines the config property (fs.SCHEME.impl) naming
the FileSystem implementation class. The uri's authority is used to
determine the host, port, etc. for a filesystem.</description>
</property>

in hdfs-site.xml

<property>
<name>dfs.replication</name>
<value>1</value>
<description>Default block replication.
The actual number of replications can be specified when the file is created.
The default is used if replication is not specified in create time.
</description>
</property>

in mapred-site.xml

<property>
<name>mapred.job.tracker</name>
<value>localhost:54311</value>
<description>The host and port that the MapReduce job tracker runs
at. If "local", then jobs are run in-process as a single map
and reduce task.
</description>
</property>

</configuration>

• Format the name node
  $ cd /home/hadoop
  $ ./bin/hadoop namenode -format
  Check the output for errors.


• Start single node cluster
  $ <HADOOP_INSTALL>/bin/start-all.sh
  This should start the namenode, datanode, jobtracker and tasktracker - all on one machine.


• Check whether the nodes are up and running. The output should be approximately like
  $ jps
  28982 JobTracker
  28737 DataNode
  28615 NameNode
  30570 Jps
  29109 TaskTracker
  28870 SecondaryNameNode


• In case of any error, Please check the log files in the <HADOOP_INSTALL_DIR>/logs directory.


• To stop the node, run
  $ <HADOOP_INSTALL_DIR>/bin/stop-all.sh

We will skip running actual map-reduce tasks on a single node setup and go ahead with a multi-node setup. Once we have 2 machines up and running, we will run some example map-reduce tasks on those nodes. So, lets proceed with multi-node setup.

For multi node setup, you should have 2 machines up and running and both having hadoop - single node setup on them. We will refer the machines as master and slave, And assume that hadoop has been installed under /home/hadoop directory in both the nodes.

• Firstly stop the single node hadoop running on them.
  $ <HADOOP_INSTALL_DIR>/bin/stop-all.sh


• Edit /etc/hosts file on both the servers to setup master and slave names. Eg:
  aaa.bbb.ccc.ddd master
  www.xxx.yyy.zzz slave


• Now, the master should be able to ssh to the slave server without any password, so copy the public key of master to that of slave.
  master]$ ssh-keygen -t rsa
  master ~/.ssh]$ scp id_rsa.pub hadoop@slave:.ssh/
  slave ~/.ssh]$ cat id_rsa.pub >> authorized_keys
  Test the ssh setup
  master]$ ssh master
  master]$ ssh slave
  slave ]$ ssh slave


• Change the <HADOOP_INSTALL_DIR>/conf/masters & <HADOOP_INSTALL_DIR>/conf/slaves file to add the master & slave hosts there on the master server. The files should look like this.
  
  master ~/hadoop/conf]$ cat masters
  master
  
  The slaves file contains the hosts(one per line) where hadoop slave daemons (data nodes and task trackers) would run. In our case we are running the datanode & tasktracker on both machines. In addition the master server would also run the master related services (namenode). Both master and slave would store data.
  
  master ~/hadoop/conf]$ cat slaves
  master
  slave


• Now change the configuration (<HADOOP_INSTALL_DIR>/conf/hadoop-site.xml) on all machines (master & slave). Set/change the following variables.
  
  Specify the host and port of the name node(master server).
  fs.default.name = hdfs://master:54310
  
  Specify the host and port of the job tracker (map reduce master).
  mapred.job.tracker = master:54311
  
  Specify the number of machines a single file should be replicated to before it becomes available. It should be equal to the number of slave nodes. In our case it is 2 (master & slave - both act as slaves as well).
  dfs.replication = 2


• You need to format the namenode recreate the datanode. Do the following
  master ~/hadoop/hadoop-hadoop]$ rm -rf dfs mapred
  slave ~/hadoop/hadoop-hadoop]$ rm -rf dfs mapred
  
  Recreate/reformat the name node
  master ~/hadoop] $ ./bin/hadoop namenode -format


• Start the cluster.
  [master ~/hadoop]$ ./bin/start-dfs.sh
  starting namenode, logging to /home/hadoop/bin/../logs/hadoop-hadoop-namenode-master.out
  master: starting datanode, logging to /home/hadoop/bin/../logs/hadoop-hadoop-datanode-master.out
  slave: starting datanode, logging to /home/hadoop/bin/../logs/hadoop-hadoop-datanode-slave.out
  master: starting secondarynamenode, logging to /home/hadoop/bin/../logs/hadoop-hadoop-secondarynamenode-master.out
  Check the processes running on the master node
  [master ~/hadoop]$ jps
  5249 SecondaryNameNode
  5319 Jps
  5117 DataNode
  4995 NameNode
  Check the processes running on slave node
  [slave ~/hadoop]$ jps
  22256 Jps
  22203 DataNode
  Check the logs on the slave for errors. <HADOOP_INSTALL_DIR>/logs/hadoop-hadoop-datanode-slave.log


• Now start the mapreduce daemons:
  [master ~/hadoop]$ ./bin/start-mapred.sh
  starting jobtracker, logging to /home/hadoop/bin/../logs/hadoop-hadoop-jobtracker-master.out
  slave: starting tasktracker, logging to /home/hadoop/bin/../logs/hadoop-hadoop-tasktracker-slave.out
  master: starting tasktracker, logging to /home/hadoop/bin/../logs/hadoop-hadoop-tasktracker-master.out
  Check the processes on master
  [master ~/hadoop]$ jps
  5249 SecondaryNameNode
  5117 DataNode
  5725 TaskTracker
  5598 JobTracker
  5853 Jps
  4995 NameNode
  And the processes on the slave
  [slave ~/hadoop]$ jps
  22735 TaskTracker
  22856 Jps
  22413 DataNode

To shut down the hadoop cluste run the following on master

[master ~/hadoop]$ ./bin/stop-mapred.sh # to stop mapreduce daemons
[master ~/hadoop]$ ./bin/stop-dfs.sh # to stop the hdfs daemons

Now, lets populate some files on the hdfs and see if we can run some programs

Get the following files on your local filesystem in some test directory on master

[master ~/test]$ wget http://www.gutenberg.org/files/20417/20417-8.txt
[master ~/test]$ wget http://www.gutenberg.org/dirs/etext04/7ldvc10.txt
[master ~/test]$ wget http://www.gutenberg.org/files/4300/4300-8.txt
[master ~/test]$ wget http://www.gutenberg.org/dirs/etext99/advsh12.txt

Populate the files in the hdfs file system

[master ~/hadoop]$ ./bin/hadoop dfs -copyFromLocal ../test/ test

Check the files on the hdfs file system

[master ~/hadoop]$ ./bin/hadoop dfs -ls
Found 1 items
drwxr-xr-x - hadoop supergroup 0 2008-10-20 12:37 /user/hadoop/test
[master ~/hadoop]$ ./bin/hadoop dfs -ls test
Found 4 items
-rw-r--r-- 2 hadoop supergroup 674425 2008-10-20 12:37 /user/hadoop/test/20417-8.txt
-rw-r--r-- 2 hadoop supergroup 1573048 2008-10-20 12:37 /user/hadoop/test/4300-8.txt
-rw-r--r-- 2 hadoop supergroup 1423808 2008-10-20 12:37 /user/hadoop/test/7ldvc10.txt
-rw-r--r-- 2 hadoop supergroup 590093 2008-10-20 12:37 /user/hadoop/test/advsh12.txt

Now lets run some test programs. Lets run the wordcount example and collect the output in the test-op directory.

[master ~/hadoop]$ ./bin/hadoop jar hadoop-0.18.1-examples.jar wordcount test test-op
08/10/20 12:49:45 INFO mapred.FileInputFormat: Total input paths to process : 4
08/10/20 12:49:46 INFO mapred.FileInputFormat: Total input paths to process : 4
08/10/20 12:49:46 INFO mapred.JobClient: Running job: job_200810201146_0003
08/10/20 12:49:47 INFO mapred.JobClient: map 0% reduce 0%
08/10/20 12:49:52 INFO mapred.JobClient: map 50% reduce 0%
08/10/20 12:49:56 INFO mapred.JobClient: map 100% reduce 0%
08/10/20 12:50:02 INFO mapred.JobClient: map 100% reduce 16%
08/10/20 12:50:05 INFO mapred.JobClient: Job complete: job_200810201146_0003
08/10/20 12:50:05 INFO mapred.JobClient: Counters: 16
08/10/20 12:50:05 INFO mapred.JobClient: File Systems
08/10/20 12:50:05 INFO mapred.JobClient: HDFS bytes read=4261374
08/10/20 12:50:05 INFO mapred.JobClient: HDFS bytes written=949192
08/10/20 12:50:05 INFO mapred.JobClient: Local bytes read=2044286
08/10/20 12:50:05 INFO mapred.JobClient: Local bytes written=3757882
08/10/20 12:50:05 INFO mapred.JobClient: Job Counters
08/10/20 12:50:05 INFO mapred.JobClient: Launched reduce tasks=1
08/10/20 12:50:05 INFO mapred.JobClient: Launched map tasks=4
08/10/20 12:50:05 INFO mapred.JobClient: Data-local map tasks=4
08/10/20 12:50:05 INFO mapred.JobClient: Map-Reduce Framework
08/10/20 12:50:05 INFO mapred.JobClient: Reduce input groups=88307
08/10/20 12:50:05 INFO mapred.JobClient: Combine output records=205890
08/10/20 12:50:05 INFO mapred.JobClient: Map input records=90949
08/10/20 12:50:05 INFO mapred.JobClient: Reduce output records=88307
08/10/20 12:50:05 INFO mapred.JobClient: Map output bytes=7077676
08/10/20 12:50:05 INFO mapred.JobClient: Map input bytes=4261374
08/10/20 12:50:05 INFO mapred.JobClient: Combine input records=853602
08/10/20 12:50:05 INFO mapred.JobClient: Map output records=736019
08/10/20 12:50:05 INFO mapred.JobClient: Reduce input records=88307
Now, lets check the output.

[master ~/hadoop]$ ./bin/hadoop dfs -ls test-op
Found 2 items
drwxr-xr-x - hadoop supergroup 0 2008-10-20 12:45 /user/hadoop/test-op/_logs
-rw-r--r-- 2 hadoop supergroup 949192 2008-10-20 12:46 /user/hadoop/test-op/part-00000
[master ~/hadoop]$ ./bin/hadoop dfs -copyToLocal test-op/part-00000 test-op-part-00000
[master ~/hadoop]$ head test-op-part-00000
"'A 1
"'About 1
"'Absolute 1
"'Ah!' 2
"'Ah, 2
"'Ample.' 1
"'And 10
"'Arthur!' 1
"'As 1
"'At 1

That's it... We have a live setup of hadoop running on two machines...