How can HBase be low-latency if Hadoop is high-latency?

Hadoop is optimized for streaming large amounts of data and processing the data as a stream. Hadoop doesn't require a set data structure, the structure may be imposed at read time. That said, there are helper classes that allow you to write in various record-oriented formats.

Hadoop is said to be high-latency because when you run a MapReduce job, there's a bit of overhead for the job to start up and run. It is also optimized for volume--it is fast when you want to load a huge amount of data from disk, albeit not instantaneously. Not to mention, if you want to read a specific record, you will have to scan through potentially the entire data set to get your result.

HBase lives on top of Hadoop and reads/writes records in a custom format. HBase is a column-oriented Key/Value store, where keys are sorted in a b-tree for fast retrieval. HBase allows for low-latency random reads and writes, and it achieves this largely by caching data operations in memory.


(source: http://getsatisfaction.com/cloudera/topics/difference_between_hbase_and_hadoop_structure_i_e_both_denormalized_already)

Database Normalization

Consider a org chart that has to be represented in a database


1 NF


Table A
Column Header > Person ID  |  Person Name | Report ID 1 | Report ID 2 | Report ID 3
  Row >                    23                Jack                  24                     14               10


Here, multiple manager-report relationships are represented in one row.
In 1NF, each relationship is represented in it's own row.


The new structure would look like:
Table A

 Column Header >  Person ID  |   Person Name

  Row >                      23                Jack      

Table B

 Column Header >  Person ID  | Report ID  |

  Row >                      23                   24      

  Row >                      23                   14  

  Row >                      23                   10




2 NF

Consider we are storing addess for each Person in Table A


Table A
Column Header > Person Id | Person Name | Address   |   City   |  State | Zip
  Row                      1                 Jack            10 R rd      NYC     NY     100001
  Row                      2                 Jill               12 Z Rd     NYC     NY     100001


The last 3 columns in the two rows contain duplicate information and can be converted into its on data unit.


Table C
Column Header   Place Id  | City |  State  | Zip
  Row                   1              NYC   NY    100001


Table A

Column Header > Person Id | Person Name | Address   |   Place Id

  Row                      1                 Jack            10 R rd         1

  Row                      2                 Jill               12 Z Rd        1

2NF involves exposing a hidden relationship within the same unit of data. In the example above, data about a person (name, address, city, state, zip) could be split in two two units of data with a relationship i.e. Person (name,  address, Place Id) and Place (City, State, Zip)


In general, normalization improves (update/delete/add) efficiency, but reduces read efficiency. For data, which is not updated frequently (thus not requiring write efficiency), we might want to keep the data in denormalized form, instead of splitting in over multiple tables. Data redundancy increases, storage requirement increases, data modifications are more complex and need to be made in several places/rows/tables.

3 NF


Consider
Orders Table
Column Header  |   Order Id  |  UnitPrice |  Quantity  |  Total
Row                           1               10            2               20 

Row                           2                5             6               30


This table can be reduced to

Column Header  |   Order Id  |  UnitPrice |  Quantity 

Row                           1               10            2           

Row                           2                5             6           

Our Data (Unit Price, Quantity, Total) has an implicit relationship Total = Unit Price * Quantity.  Our data can thus be reduced to (Unit Price, Quantity). Since the relationship is implicit, we do not need to store the relationship in some second table (unlike 1NF, 2NF).

4 NF


Consider a data struct (A, B, C)
A to B is a 1:many relationship.
A to C is a 1:many relationship.
B and C have no relationship between them.


Storying (A,B,C) in a table would give us composite key uniqueness, but would involve more keys than necessary.
e.g
A takes values (1,2,3)
B takes values (x,y,z)
C takes values (P,Q,R)


(A,B) have an explicit relationship where only certain pairs are possible.
(A,C) have an explicit relationship where only certain pairs are possible.
(B,C) have an implicit relationship. Any pair is possible.


We can leverage the fact that there is an implicit relationship, to reduce the number of rows. The implicit relationship does not need to be represented.
Each explicit relationship can be expressed in its own table.


We'll now have upto 3 * 3 * 3 = 27 rows (Table 1), when the same information can be represented in upto 18 rows over two tables.(Tables 2, 3)


Table 1   A    B    C  (27 rows)
               1     x    P
               1     x    Q
               .....
               3      z    R


Table 2   A   B   (upto 9 rows)
              1     x
              ...
              3     z


Table 3  A   C   (upto 9 rows)
              1    P
              ...
              3    R


4NF involves exposing multiple relationships in the same unit of data.
Here the reduction is possible only because there is no relationship between B, C.
Otherwise 4 NF would not have been possible. e.g. if the (B,C) combination of (y, Q) is not possible, it implies that B,C are coupled and we would probably have to see if 5 NF could be applied.


Check out http://en.wikipedia.org/wiki/Fourth_normal_form#Example for a better 4NF example.


A unit of data should be one, where any two fields cannot be expressed as a seperate unit of data. A relationship can only be formed between independent units of data.




5NF
Consider a table with 3 columns, A, B, C
Assume that (A,B), (B,C), (A,C) are relationships that are independent of each other.
Then, we can break the table into 3 tables, leading to lesser number of rows.
We break (A,B,C) into (A,B), (B,C) and (A,C)


If the relationships were not independent of each other, 5 NF would not have been possible.


Check out http://en.wikipedia.org/wiki/Fifth_normal_form#Example for a great example.

Lock-Free Concurrent Stack

package self.concurrent;

import java.util.concurrent.atomic.AtomicReference;

public class Stack {

   AtomicReference> atomicHead;
  
   public Stack()
   {
      atomicHead = new AtomicReference>();
   }
  
   public void push(T item)
   {
      Node currentHead = null;
      Node newHead = null;
      do
      {
         currentHead = atomicHead.get();
         newHead = new Node(item, currentHead);
      }
      while(!atomicHead.compareAndSet(currentHead, newHead));    
   }
  
   public T pop()
   {
      Node currentHead = null;
      Node newHead = null;
      do
      {
         currentHead = atomicHead.get();
         if (currentHead == null) return null;
         newHead = currentHead.next;
      }
      while(!atomicHead.compareAndSet(currentHead, newHead));
    
      return currentHead.item;
   }
}

ConcurrentQueue using Lock-Conditions

package self.synchronization;
import java.util.concurrent.locks.*;

public class BlockingQueue3
{
private Node head = null;
private Node tail = null;
private final Lock lock = new ReentrantLock();
private final Condition itemAvailableCondition = lock.newCondition();
private final Condition spaceAvailableCondition = lock.newCondition();

private final int maxCount = 10; // make this a constructor param
private volatile int currentCount = 0;

public void produce(T item) throws InterruptedException {
Node newTail = new Node(item, null);
try
{
this.lock.lock();
// condition
while (this.currentCount >= maxCount) {
spaceAvailableCondition.await();
}

if (tail != null) {
tail.next = newTail;
} else {
tail = newTail;
head = newTail;
}

++this.currentCount;
this.itemAvailableCondition.signal();
}
finally
{
this.lock.unlock();
}

}

public T consume() throws InterruptedException {
Node returnNode = null;
try
{
this.lock.lock();
// condition
while (currentCount == 0) {
this.itemAvailableCondition.await();
}

returnNode = head;
head = head.next;
if (head == null)
tail = null;
--currentCount;
this.spaceAvailableCondition.signal();
}
finally
{
this.lock.unlock();
}

return returnNode.item;
}

private class Node {
public final T item;
public Node next;

Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}

What's the number again

The previous post "What's The Number" had a non-recursive implementation. Here is a recursive way of doing the same. It's not as bad to have a recursive implementation as the max recursion depth is limited by the length of  a telephone number. If the input was longer / without an upper bound, recursion would be a bad move. This Recursive algorithm does a Depth First walk. A recursive Breadth First walk is much more painful to implement and has a higher memory overhead.

/*

Given a telephone number like 4156434531, get all possible names that would match it.

e.g. If the number is 23, the names could be "ad", "bd", "cd", "ae" etc..

*/

public static class TelNumber

{

private static char[][] KeyChars = new char[10][];

static TelNumber()

{

KeyChars[0] = new char[]{'+'};

KeyChars[1] = new char[]{' '};

KeyChars[2] = new char[]{'a','b','c'};

KeyChars[3] = new char[]{'d','e','f'};

KeyChars[4] = new char[]{'g','h','i'};

..

}

public static void PrintCombination(StringBuffer prefix, int[] tel_no)

{

int index = prefix.Count;

if (index >= tel_no.Length)

{

System.Console.Writeline(prefix);

return;

}

foreach(char c in KeyChars[tel_no[index]])

{

prefix.Add(c);

PrintCombination(prefix, tel_no);

prefix.RemoveLastChar();

}

}

What's the number

/*

Given a telephone number like 4156434531, get all possible names that would match it.

e.g. If the number is 23, the names could be "ad", "bd", "cd", "ae" etc..

*/

This non recursive implementation does not use a queue/stack to simulate recursion either.

namespace AlphaNumerics

{

public static class TelNumber

{

private static char[][] KeyChars = new char[10][];

static TelNumber()

{

KeyChars[0] = new char[]{'+'};

KeyChars[1] = new char[]{' '};

KeyChars[2] = new char[]{'a','b','c'};

KeyChars[3] = new char[]{'d','e','f'};

KeyChars[4] = new char[]{'g','h','i'};

}

public static void GetCombinations(int[] tel_no)

{

int[] digits = new int[tel_no.Length];

while(true)

{

Print(digits, tel_no);

if (!Increment(digits, tel_no)) break;

}

}

public static bool Increment(int[] digits, int[] tel_no)

{

int i = 0;

bool overflow = false;

for (; i < digits.Length; i++)

{

digits[i] = (digits[i] + 1) % KeyChars[tel_no[i]].Length;

if (digits[i] != 0) { overflow = false; break; }

else overflow = true;

}

return !overflow;

}

public static void Print(int[] digits, int[] tel_no)

{

for (int i = 0; i < tel_no.Length; i++)

{

System.Console.Write(KeyChars[tel_no[i]][digits[i]]);

}

System.Console.WriteLine();

}

}

}

Fuzzy Regex Matcher

/*
This Fuzzy RegexMatcher does not handle *,?, ^ etc., but, it takes in a tolerance/forgiveness factor.
With a forgiveness value of 1, regex "ac" would match strings like "abc" or "ad" or "c".  With a forgiveness factor of 0, the match would fail.
*/

using System;

namespace StringHelpers

{

public static partial class RegexMatcher

{

public static bool AreSimilar(char[] str, char[] pattern, int forgiveness)

{

// Args check todo

for (int i = 0; i <= str.Length - pattern.Length; i++)

{

if (AreSimilar(str, pattern, i/*str index*/, 0/*pattern index*/, forgiveness)) return true;

}

return false;

}

private static bool AreSimilar(char[] str, char[] pattern, int si, int pi, int forgiveness)

{

if (pi >= pattern.Length) return true;

if (si >= str.Length) return false;

if (str[si] == pattern[pi])

{

return AreSimilar(str, pattern, si + 1, pi + 1, forgiveness);

}

else if (forgiveness > 0)

{

return AreSimilar(str, pattern, si, pi + 1, forgiveness - 1)|| AreSimilar(str, pattern, si + 1, pi + 1, forgiveness - 1);

}

return false;

}

}

}