Total Order Sorting in MapReduce

When using multiple reducers, each reducer receives (key,value) pairs assigned to them by the Partitioner. When a reducer receives those pairs they are sorted by key, so generally the output of a reducer is also sorted by key. However, the outputs of different reducers are not ordered between each other, so they cannot be concatenated or read sequentially in the correct order.

For example with 2 reducers, sorting on simple Text keys, you can have :
– Reducer 1 output : (a,5), (d,6), (w,5)
– Reducer 2 output : (b,2), (c,5), (e,7)
The keys are only sorted if you look at each output individually, but if you read one after the other, the ordering is broken.

The objective of Total Order Sorting is to have all outputs sorted across all reducers :
– Reducer 1 output : (a,5), (b,2), (c,5)
– Reducer 2 output : (d,6), (e,7), (w,5)
This way the outputs can be read/searched/concatenated sequentially as a single ordered output.

Ans: 

We can create a manual total order sorting with a custom partitioner. 

We can also use Hadoop’s TotalOrderPartitioner to automatically create partitions on simple type keys. 

Finally we can use more advanced technique to use our Secondary Sort’s Composite Key with this partitioner to achieve “Total Secondary Sorting“.

Total Secondary Sort by Composite Key

• The TotalOrderPartitioner uses the map output keys to calculate partitioning.
• Our map output keys are of type CompositeKey, because we are doing Secondary Sorting.
• 

What is Hue?

Hue contains a Web application for accessing the Hive metastore called Metastore Browser, which lets you explore, create, or delete databases and tables using wizards. However, Hue uses HiveServer2 for accessing the metastore instead of HCatalog. This is because HiveServer2 is the new secure and concurrent server for Hive and it includes a fast Hive Metastore API.

What is HCatalog?

HCatalog is a module in Apache Hive that enables non-Hive scripts to access Hive tables. You can then directly load tables with Apache Pig or MapReduce without having to worry about re-defining the input schemas, or caring about or duplicating the data’s location.

How to store Pig output into Hive table

There are two approaches explained below with 'Employee' table example to store pig output into hive table. (Prerequisite is that hive table should be already created)
A =  LOAD 'EMPLOYEE.txt' USING PigStorage(',') AS(EMP_NUM:int,EMP_NAME:chararray,EMP_PHONE:int);



Approach 1: Using HCatalog
// dump pig result to Hive using Hcatalog 
store A into 'Empdb.employee' using org.apache.hive.hcatalog.pig.HCatStorer();
(or)

Approach 2: Using HDFS physical location
// dump pig result to external hive warehouse location
STORE A INTO 'hdfs://<<nmhost>>:<<port>>/user/hive/warehouse/Empdb/employee/' USING PigStorage(',')

How to read data stored in Hive table using Pig

Use HCatLoader to load Hive table data using Pig

A = LOAD 'hivedb.hivetable' using org.apache.hive.hcatalog.pig.HCatLoader();

-- Load table 'sample_07'
sample_07 = LOAD 'sample_07' USING org.apache.hcatalog.pig.HCatLoader();
 
-- Compute the average salary of the table
salaries = GROUP sample_07 ALL;
out = FOREACH salaries GENERATE AVG(sample_07.salary);
DUMP out;

Similar to HCatLoader, use HCatStorer to update the table, e.g.:


STORE alias INTO 'sample_07' USING org.apache.hcatalog.pig.HCatStorer();

Maximum Stock Profit in a single transaction

/*List of stock prices are given, find out maximum profit to get by buy and sell in a single transaction

prices = { 23, 28, 5, 6, 18, 15 }
*/


Solution:

public int maxProfit(int[] prices) {  
   int minPrice = Integer.MAX_VALUE;
   int maxProfit = 0;
   for(int price : prices) {
       maxProfit = Math.max(maxProfit, price-minPrice);
       minPrice = Math.min(minPrice, price);
   }
   return maxProfit;
 }  

This can be done in time O(n) with O(1) spaces

Bloom Filter

A Bloom filter is a probabilistic data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.

The base data structure of a Bloom filter is a Bit Array. It tells us that the element either definitely is not in the set or may be in the set.

Hive: Bloom filter are relatively new feature in Hive (1.2.0) and should be leveraged for any high-performance applications. Bloom filter are suitable for queries using where together with the = operator:

SELECT AVG(revenue) WHERE gender=0

A bloom filter can apply to numeric, but also non-numeric (categorical) data, which is an advantage over the storage index. Internally, a bloom filter is a hash value for the data in a column in a given block. This means you can "ask" a bloom filter if it contains a certain value, such as gender=male, without you needing to read the block at all. This obviously increases performance significantly, because most of the time a database is busy with reading non-relevant blocks for a query.

HBase: An HBase Bloom Filter is an efficient mechanism to test whether a StoreFile contains a specific row or row-col cell. Without Bloom Filter, the only way to decide if a row key is contained in a StoreFile is to check the StoreFile's block index, which stores the start row key of each block in the StoreFile. BloomFilters provide an in-memory structure to reduce disk reads to only the files likely to contain that Row. In short it can be considered as an in-memory index to determine probability of finding a row in a particular StoreFile.

Algorithm description

An example of a Bloom filter, representing the set {x, y, z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution. Typically, k is a constant, much smaller than m, which is proportional to the number of elements to be added; the precise choice of k and the constant of proportionality of m are determined by the intended false positive rate of the filter.

To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1.

To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions is 0, the element is definitely not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. In a simple Bloom filter, there is no way to distinguish between the two cases, but more advanced techniques can address this problem.

References :

https://en.wikipedia.org/wiki/Bloom_filter