Introduction

Types of data
quantative (discrete & continuous)
qualitative
Information: processed data
Steps to be performed
collection
warehouse (storage)
analysis/process
reporting
7 V's of BD
volume (amount)
variety (types)
velocity (speed)
veracity (trustworthiness)
value
variability (inconsistency)
visualization
Other V's:
viscosity (complexity)
volatility (how long is this data valid for?)
validity (legality)
viability (is it active?)
BD: schema less and semi-structured or unstructured
structured (tablular format)
semi-structured (csv, xml, json)
unstructured (text, image, audio, video)
BD processing tools
 hadoop: distributed computing framework
map reduce: program model for distributed computing
spark: real time data processing framework
kafka: distributed event store and stream processing platform

Distributed Computing
Distributed computing: make N number of systems (hardware/software) work as a single unit
client-server: client (front end) and server (back end)
3 tier: client, application and database
peer-to-peer: no server and all machines are considered equal
Parallel computing: N number of systems carry out tasks simultaneously
Serial computing: tasks are broken into series and executed one after another on a single system
Parallel vs Distributed computing
parallel: same memory, different processor (CPU)
distributed: different memory, different processor (CPU)
Cluster computing: N number of systems are used to construct virtual parallel computer
each system is called node
cheaper than parallel computing
slower than parallel computing
Grid computing: geographically distributed computer networks but work on a common problem
HDFS: hadoop distributed file system (descendant of google file system)

Text Representation
Boolean model
represented as set of keywords
connected by AND, OR and NOT
output: weather the document is relevant or not. no partial matches or ranking
 very rigid: AND means all, OR means any
difficult to rank output
search outcome is either too much or too less
jaccard measure: (A intersect B) / (A union B)
where A and B may not be of same size
does not consider term frequency
it does not consider rare terms which can be more important than common terms
Bag of Words (BoW)
does not consider ordering of words
counts the occurance of each word
Term frequency (Tf): number of times a particular term occurs in a document
W (Tf) = 1 + log(tf) for tf > 0, 0 for otherwise
Score: Sigma (W (Tf))
Inverse document frequency (Idf): total no of documents (N) / no of documents containing particular term (df)
w (Tf-Idf) = (log(1 + tf)) x (log(N / df))
Score: Sigma (W (tf-idf))
Similarity measure: document vector DOT query vector
Euclidean distance is a bad idea bcz it is large for vectors of different lengths
It is better to measure angle in terms of cosine bcz its a monotonically decreasing function from 0 to 180
Vector space model
convert all documents into tf-idf vector "d" for vocabulary V
convert query into tf-idf vector "q"
score = cosine similarity (d, q)
sort documents in decreasing score
present top ranked documents to user

Hadoop
Components
HDFS: Storage (main component)
 Map Reduce: data processing using programming (main component)
Yarn: Resource management (main component)
Spark: In-memory (real time) data processing
Pig / Hive: data processing using SQL like query
Hbase: no-Sql database
Mahout / Spark ML Library: machine learning
Drill: SQL on hadoop
Zookeeper: cluster management
Oozie: Job scheduling
Flume / Scoop: data ingestion
Solr / Lucene: search & index
Ambari: monitor and maintain cluster
HDFS
master-slave (namenode-datanode) architecture
data locality: moving computation instead of moving data
Namenode
metadata: editlog (latest changes) and fsimage (all changes from the beginning)
Secondary Namenode (SNN)
performs periodic checkpoints
maintains copy of editlog and fsimage
copies fsimage every hour (by default) from namenode and merges this image with the edit log and copy it back to
the namenode so that namenode will have the fresh copy of this image
Data replication
stores each file as sequence of blocks
blocks are replicated for fault tolerance
all blocks are of same size
files are write once (except appends and truncates) and have one writer at a time
Heartbeats
datanode sends signal (heartbeat) to namenode every 3 seconds (by default)
if no heartbeat is received in last 10 mins then the datanode is considered dead
heartbeat carries other info like total storage capacity, node capacity, number of data transfers currently in progress,
etc
 Write
setup pipeline
data streaming and replication
shutdown of pipeline
MapReduce
the input dataset is broken into blocks which are processed by the map tasks in parallel manner
can compare it with merge sort
map
split the input dataset into blocks
processes these blocks in parallel
reduce
use output of map as input
reducers process the data from the maps into smaller data
aggregates the output
combiner (optional)
it is used to optimize the performance of mapreduce jobs
it works by reducing output of the map at node level
this makes the shuffle and sort phase work even quicker

Yarn
manages resource allocation and job scheduling
introduced in hadoop 2 to improve mapreduce performance
supports multiple processing frameworks
stream processing
graph processing
batch processing
interactive
hadoop 1.0: HDFS (storage) > map reduce (process + resource management)
hadoop 2.0: HDFS (storage) > yarn (resource management) > map reduce (process) and other data processing frameworks
pig and hive are all examples of processing frameworks that run on mapreduce or spark and dont interact with yarn directly
resource manager (RM)
one per cluster
application manager (AM)
manages running applications
monitors/restarts applications
scheduler
schedules the job
allocates resources
no monitor/tracking of the application
node manager (NM)
runs on all nodes
executes task on every data node
monitors containers and reports to resource manager
tracks the health of nodes
application master
starts the job and reports to AM in RM (not NM)
workflow
resource manager (RM) recieves a job
scheduler in RM recieves the job and asks AM to search for available NM
NM creates "Application Master (App Master)" starts the job and reports to AM in RM
AM monitors the entire life cycle of the job and can reallocate resources if a NM fails
if resources are not sufficient
app master creates list of requests
app master directly requests scheduler in RM (not through NM)
RM requests AM for more resources
new container is launched with new NM but without app master
types of schedulers
fifo
not recommended for shared clusters
large applications occupy all the processes and there is no space left for other processes
capacity
 better for shared clusters
reserves small amount of resource for small jobs and rest for big jobs
fair schedulers
best for shared clusters (personal opinion)
does not reserve any resource
dynamically balances resource between all jobs
streaming data
is the continuous flow of data generated by various sources
batch processing vs real time streams
batch processing methods require data to be downloaded as batches before it can be processed
streaming data flows in continuously, allowing that data to be processed simultaneously in real time

CPU Scheduling
Types
FCFS
SJF
Priority Queue
RR

Spark
faster than mapreduce because it stores data in RAM rather than storage
supports real time data processing
it is a unified computing engine for parallel data processing on computer clusters
it is designed to support tasks such as
simple data loading
sql queries
machine learning
 streaming computation
it includes
spark core
foundation of the platform
responsible for
memory management
fault recovery
scheduling
distributing and monitoring jobs
interacting with storage system (does not have storage on its own)
can be used through APIs for java, python, scala, R
spark SQL
discussed in detail in next section
spark streaming
real time solution for streaming analytics
ingests data in mini batches
spark mllib
spark graphx
pyspark: libary written in python to run python applications using spark
fault tolerance using RDD
immutable
master-slave architecture
components
driver
seperatres process to execute
creates "SparkContext" to schedule job application and communicates with cluster manager
consists of driver and set of executor process
runs main() function
sits on node in a cluster
responsible for
maintain info about spark application
responds to user input
 analyzing, distributing, scheduling work across executors
executors
runs tasks scheduled by driver
stores output in memory, disk or somewhere else
responsible for
executing task assigned by driver
reporting the state of execution back to driver
cluster manager
spark standalone / yarn / kubernetes
spark session
spark context
SQL context
streaming context
hive context
RDD
core data structure of spark
are immutable
handle structured/unstructured data
spark operations
transformations
core data structures are immutable but in order to use it, changes have to be made
to change a dataframe, spark needs instructions on how to change it
these are called transformations
transformations create new RDD from previous one
is a lazy operation (using DAG) on RDD which creates another RDD
eg map, flatmap, filter, union
types: narrow, wide
actions
action instructs spark to calculate result from a series of transformations
eg collect, count, first, take(n)
shares the result to driver program or saves it somewhere
actions are RDD operations that produce non-RDD values
 partition
spark breaks data into chunks called partitions
partition is a collection of rows
lazy evaulation
it will wait and collect the instructions to execute all at once

SQL
works with structured / semi structured data
it is not a database
dataset API
contains features such as RDD, lambda, etc
can be constructed using transformations such as map, flatmap, filter, etc
dataframe API
df is dataset with named columns
conceptually equal to a table in RDBMS or dataframe in python
optimizer
catalyst
in-built optimizer
custom techniques can be added to it
automatically finds out most efficient path
tungsten
uses tree data structure to calculate lowest cost path. helpful for CPU instead of IO

Text Classification
types
binary: 2 options, 1 possible selection
multi class: N options, 1 possible selection
 multi label: N options, N possible selection
basic classification
input
document
fixed set of classes
output
predicted class
classification using supervised ML
input
document
fixed set of classes
label (usually given manually)
output
learned and predicted class

Clustering
Types
hiearchical algorithms
bottom up
merging similar clusters into larger one
top down
breaking clusters into smaller ones
partitional clustering
K-means