Hadoop, In-Memory Computing, Cloud, and Fault Tolerance

Big data analytics is not a volume game — velocity and variety matter as much as volume — and big data system technologies do not make relational databases (RDBMS) and data warehousing obsolete; they coexist with them. This unit covers the popular technologies used to build big data systems: Hadoop for storage and batch processing, in-memory computing (Spark) for speed, and the cloud for flexible infrastructure. It then moves to the hard part of running many machines at once: living with failures. That means reliability and availability metrics, fault-tolerant configurations, recovery strategies, and finally the CAP theorem, which states the fundamental trade-offs every distributed system must make.

1.1 Hadoop — Storage and Processing for Big Data

This unit covers the popular technologies used to build big data systems: Hadoop for storage and batch processing, in-memory computing (Spark) for speed, and the cloud for flexible infrastructure. It then moves to the hard part of running many machines at once: living with failures. That means reliability and availability metrics, fault-tolerant configurations, recovery strategies, and finally the CAP theorem, which states the fundamental trade-offs every distributed system must make.

1.1.1 The Problem Hadoop Solves

Organizations across the globe now realize there is a huge amount of untapped information locked in semi-structured and unstructured data. Three kinds of data show up in the wild:

• Structured data fits neatly into rows and columns — think of a bank ledger or an order table. Traditional RDBMS solutions already handled this well.
• Semi-structured data has some structure, but not a fixed one — JSON documents, XML files, and emails each have tags and fields, but no two records need the same fields.
• Unstructured data has no organization at all — free-form text, images, audio, and video.

The scale is hard to picture. A single stock exchange generates on the order of terabytes of trade data per day; large online platforms store hundreds of billions of photos; sensor networks, bank transactions, and retail logs add more every second. When terabytes pile up to petabytes, organizations see an opportunity: reveal something hidden inside that semi-structured and unstructured data. The sources are everywhere — stock exchanges, online retail stores such as Amazon and Facebook, banking transactions, sensor data, and many more.

The challenge with all this data is twofold: store this huge volume and variety, and process it. RDBMS systems are not built for every purpose; at the scale data is growing, there are performance challenges. This is where Hadoop comes in. Hadoop solves two problems:

Why not just buy one enormous machine? Because a single computer has a single disk arm and a single processor. Reading a whole large dataset from one disk takes hours, and running one huge job through one processor — including all its I/O — becomes a bottleneck at some point. The distributed trick is to cut the work into pieces and spread it over many ordinary machines at once.

1.1.2 Hadoop's Answers to the Multi-Node Challenges

Spreading data over many machines creates three new problems, and Hadoop answers each of them directly:

Processing is where the classic single-processor bottleneck appears: if you give a huge job to one processor, including all its I/O, that processor becomes a bottleneck at some point. The MapReduce framework that Hadoop provides works around this: you divide your data into multiple chunks, give each chunk to a map task to run on, and finally gather the results from each processing node and produce the final result with a reduce task. So both problems — storage and processing — are efficiently solved by Hadoop.

A concrete sense of the speedup: reading one full disk takes hours; reading the same data spread across many disks, all read in parallel, takes minutes. The entire design of Hadoop — replicate for safety, spread for speed — rests on that simple observation.

1.1.3 Hadoop versus Distributed Relational Databases: The Data Model

A distributed database built from RDBMS technology stores data in a relational model: data lives in tables (called relations in relational-model terminology), and tables are linked by primary keys and foreign keys, creating related data across tables. Distributed databases also support partitioning — fragmenting a table. There are two kinds:

• Horizontal fragmentation divides a table's records: records satisfying a particular fragmentation condition go in one part, and records that do not satisfy it go in another. You are dividing the set of records into two subsets. For example, a students table could be split by branch: records for Computer Science students in one fragment, records for Mechanical students in another.
• Vertical fragmentation takes a subset of attributes (columns) into one part and another subset of attributes into another. With vertical fragmentation you need a common attribute shared between the fragments, because joining on that common attribute reconstructs your original relation. For example, split a student table into name-and-ID in one fragment and ID-and-grades in another — the ID column is the shared key that lets you rejoin.

Relational systems also build indexes — B+ tree indexes are typical on RDBMS systems — to make fast search and optimized performance possible. All of this happens at the schema level: before you store anything, you decide the structure, the keys, the indexes, and the constraints.

Hadoop's data model is the opposite:

A side-by-side comparison on the dimensions that differ:

When to pick which: if your data is clean, fixed-shape, and transactional, an RDBMS with indexes wins. If your data is huge and messy, Hadoop wins. This is why the two coexist instead of one replacing the other.

1.1.4 The Compute Model of Relational Databases: Transactions and ACID

On the relational side, processing works on the notion of transactions. A transaction is the smallest unit that should be processed in its entirety or not at all. A transaction may consist of multiple operations — five or six, or more. Debiting my account and crediting somebody else's account is one form of transaction: those two operations cannot be divided so that one is done and the other undone. That is the atomicity property of a transaction: either you perform all operations or you do not perform even one.

Relational systems follow ACID semantics — atomicity, consistency, isolation, durability:

When relational databases are hosted on distributed systems, they also allow distributed transactions — there is coordination among the different systems, and they can globally commit a particular transaction when a single transaction is running across multiple nodes: every participating node agrees to commit together, or the whole transaction is abandoned. This model is quite suitable for OLTP workloads (online transaction processing), the workloads used to carry out day-to-day business transactions. A transaction may consist of insert, delete, update operations; once it is complete it has to commit. Committing means all operations have been performed and the changes are now permanent — the transaction cannot be rolled back at any stage. If anything happens partway through, a half-done transaction must be undone: a recovery subsystem performs the undo of that half-done transaction.

1.1.5 Hadoop's Compute Model: Jobs, Tasks, and MapReduce

Hadoop has no notion of a transaction; it has the notion of a job. A job is further divided into tasks, and each task runs at a different node. The compute model is the MapReduce model: every task is either a map task or a reduce task.

The data is given to the nodes, map tasks perform certain computations, and after computing, each map task passes results to the reduce task. The reduce task can live on the same node as a map task or on a separate node, but since map tasks run first, all map tasks complete their jobs before the reducer gathers the results. The reducer performs its own computations to produce the final result, whatever is required.

The name is a memory aid: "map" transforms each input item into output items, and "reduce" condenses many items with the same key into fewer items.

1.1.6 High-Level Hadoop Architecture

At a high level, a Hadoop cluster consists of a master node and slave nodes. The master node has a compute part and a management part.

• The compute part is the job tracker, which keeps track of a job submitted to the Hadoop cluster.
• Each node also has a task tracker, because each node does something — it holds certain data and performs map and reduce operations. Each task tracker communicates with the job tracker for coordination and for the status of the job.
• On the storage side, data is partitioned into files on data nodes, and the name node is the filesystem management node — a special node under the master that takes care of dividing the data into HDFS blocks.

So the architecture has two layers: the HDFS layer (storage, where data nodes keep the data) and the MapReduce layer (computation). One more important property is locality of reference: the data a node operates on sits in its local vicinity, so compute is close to the data, which helps achieve performance. Moving computation to the data is far cheaper than moving petabytes of data to the computation.

Visualizing the cluster: picture one master node at the top with two halves — the job tracker (scheduling and tracking jobs) and the name node (managing the file namespace and block placement). Beneath it sit the slave nodes, each with three things: a task tracker (executing map and reduce tasks), a data node (storing a share of the HDFS blocks), and its own local disk. A job flows top-down: it enters through the job tracker, which divides it into tasks and schedules them onto task trackers — preferably onto the node whose disk already holds the relevant data block (that is locality of reference in action). The name node simply answers "which node holds which blocks," so the scheduler can match tasks to data. Takeaway: two independent layers, one for storage and one for computation, coordinated by two master-side managers.

1.1.7 Worked Example: Word Count with MapReduce

The classic word count problem shows how a MapReduce program runs. First, state the objective: given input data of sentences, count the occurrence of each unique word.

The input. The input data here has two sentences: "hello world by world" and "hello hadoop goodbye hadoop". (Note on the source text: the first sentence is the version that matches the final counts — "world" must appear twice in the first sentence to reach the total of two, so the sentence is "hello world by world", not a different reading.)

Notice one detail that trips many beginners: even though a word appears twice within one sentence, the map task does not aggregate — it generates a separate key–value pair for each occurrence. Aggregation is not the map task's job; the reducer owns aggregation. This separation is what lets maps run in complete isolation and still produce correct combined answers.

The code shown for this has two pieces. The map function tokenizes the input string — it splits on spaces and, while tokens remain, emits (word, 1) key–value pairs. The reduce function sums the values for each key. This is not a full-fledged program, just the map and reduce functions:

def map(sentence):                          # one call per sentence
    for word in sentence.split(" "):        # split on spaces
        emit(word, 1)                       # one pair per occurrence

def reduce(key, values):                    # one call per word
    emit(key, sum(values))                  # sum the counts

For any problem, the skill being tested is: understand how the data is divided, what the map task should do, and what the reduce task should do. Parallelization, data division, and orchestration are provided by the platform — you only write the map code and the reduce code. The implementation can be in Java or Python; Python is preferred for the labs, since lab exercises run in Python.

1.1.8 Advantages of Hadoop

• Low cost. The technologies are open source, and Hadoop runs on low-cost commodity hardware, which is relatively cheaper than buying high-end servers.
• Computing power. Hadoop is based on a distributed computing model that can process very large amounts of data fairly quickly, because it is a cluster of nodes, not a single machine — the more nodes, the more processing power at hand.
• Scalability. Hadoop follows horizontal scalability. To increase computing power, add a node; to increase storage, add storage. There is no need to upgrade to high-end servers — just add commodity hardware. Vertical scaling (buying a bigger machine) hits a ceiling; horizontal scaling (adding more machines) does not.
• Storage flexibility. It helps store structured, semi-structured, and unstructured data, not only structured data like a traditional RDBMS.
• Inherent data protection. With replication, data is replicated on multiple nodes. If a node fails, the task is given to the node where the replica exists, or to any other node with enough capacity to do the job. The system does not go down with one or two failures — as long as replication is taken care of.

1.1.9 The Hadoop Ecosystem

An ecosystem here means the comprehensive set of technologies you can combine, effectively and cost-effectively, to provide big data solutions. The two core components are HDFS — the storage layer, which helps store different kinds of data and large data sets — and MapReduce — parallel processing. These two are good to start with, but sometimes they are not enough for very large-scale data sets, or for application requirements such as real-time processing. More tools fill those gaps.

To do anything with data, you first bring it into HDFS; only then can you compute on it. The ecosystem is best read as layers of jobs:

Two tools deserve a closer look because they target very different users. Hive lets you do analytics through an SQL-like interface — you write Hive queries and do analytics, so database-minded users feel at home. Pig serves people from non-programming backgrounds: it gives SQL-like commands for writing jobs, so you can write ten lines of Pig (in its language, Pig Latin) that do the work of roughly a hundred lines of a MapReduce program. MapReduce itself remains available for writing programs in different languages when you need full control.

1.2 In-Memory Computing with Spark

1.2.1 Where MapReduce Falls Short

MapReduce gave a big boost to big data processing: it lets you store and process huge amounts of data at very low cost, using commodity hardware, interconnected processing nodes, and distributed systems. It is an ideal platform for certain complex batch applications — going through system logs to identify patterns, running ETL tasks (extraction, transformation, loading), computing web indexes, and building recommendation systems. These are cases of standalone data that needs certain processing: the job is well defined, the data is scanned once or twice, and nobody is waiting at a terminal for the answer.

What makes MapReduce unsuitable for other applications is its reliance on persistent storage for fault tolerance and its one-pass computation model — together these make it a poor fit for low-latency applications. MapReduce reads files from the hard drive and stores results back to the hard drive; reading and writing persistent storage is time-consuming, and with the very large data sets that big data systems deal with, disk reads and writes increase latency. Every intermediate result is flushed to disk, every map output is written before the reducer can read it — safe, but slow. So MapReduce is not the right fit for real-time analysis, nor for iterative computations — something done and then repeated. Many machine learning algorithms run many iterations to train a model, so MapReduce is typically not suited for those iterative applications either.

1.2.2 The In-Memory Idea: Memory Instead of Disk

In-memory computing stores the data in RAM rather than on the hard drive: you read the data from RAM and write the data back to RAM. Hadoop's pattern is a loop of permanent storage round trips — input taken from HDFS, processed, stored back to permanent storage, read again, and so on. In-memory computing speeds up processing by using memory instead of disk: you first read the file, and once it is processed you keep it in a distributed RAM rather than storing it away.

1.2.3 Spark's Programming Model

Hadoop typically provides map tasks and reduce tasks, and each task is either a map task or a reduce task. Spark instead provides a programming model that lets developers write applications by composing many operators — mappers, reducers, joins, groupBys, filters, and more. The operator set is not limited to mappers and reducers.

1.2.4 Worked Example: Word Count in Spark

The same word count problem looks very different in Spark: a small piece of code.

lines  = read("hdfs://...")          # read input
words  = lines.flatMap(split)        # one line -> many words
pairs  = words.map(w -> (w, 1))      # each word -> (word, 1)
counts = pairs.reduceByKey(sum)      # sum counts per word
counts.save("hdfs://.../result")     # write back to permanent storage

The point of the example is that rather than writing complex map and reduce functions, these simple lines do a lot of work. Spark provides a rich set of primitives on top of the MapReduce model to make programming easier — otherwise you write long lines of code in Java. In-memory computing may involve a higher cost, but it makes Spark suitable for low-latency computations and efficient iterative algorithms.

1.2.5 Low Latency and Iterative Algorithms

With a working data set cached in memory, low-latency applications run computations at memory speeds: input is read and processed once, stored on the distributed memory, and every subsequent computation touches the memory instead of the disk. For iterative applications, the data is read from the hard drive once, an iteration is done and the result stored in distributed memory, then another iteration runs against memory, then another — and only after everything is computed is the result stored back to permanent storage.

1.2.6 Student Questions and Answers

1.3 Cloud Computing for Big Data

1.3.1 Why the Cloud

Organizations dealing with big data face the problem of storage and management, and owning the needed technologies and infrastructure is expensive: high-end servers and software have to be purchased. Then resources are hard to size. As the application scales, you may need more resources than you bought, so resources become over-utilized and application performance bottlenecks. Or you overbuy, and resources sit under-utilized.

The cloud answers both problems: a flexible way of allocating infrastructure, paying for services as you use them. The cloud lowers infrastructure cost, runs infrastructure more efficiently, and lets your business scale — upscale and downscale as needed. Managing infrastructure in-house is a complex overhead; nowadays everything is on the cloud.

1.3.2 The NIST Definition

The formal definition (from NIST, the U.S. standards body) is: a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources — networks, servers, storage, applications, and services — that can be rapidly provisioned and released with minimal management effort or service provider interaction.

1.3.3 The 3-4-5 Rule

Cloud computing is organized by the 3-4-5 rule: three cloud service models, four deployment models, and five essential characteristics. All three parts are covered below. Keep the rule as a mental index: the five characteristics say what makes something cloud-like, the four deployment models say who owns and who may use it, and the three service models say how much of the stack is given to you.

1.3.4 The Five Essential Characteristics

• On-demand self-service. Users can consume resources or computing capabilities for applications as and when needed, without much interaction with the service provider. Providers in this market include AWS, GCP (Google Cloud Platform), Azure, Rackspace, and others.
• Broad network access. Resources are available over standard network connections, from all commonly used machines such as laptops and PCs.
• Resource pooling. All consumers share resources from a common pool, assigned to them depending on demand, consumption, and usage. The pool may be scattered across different geographical locations.
• Rapid elasticity. Scaling must be elastic both upward and downward, seamless, and proportional — need more, add; need less, remove. Pay per use.
• Measured service. A pay-per-use model with transparency between provider and user: services are controlled, optimized, monitored, and reported frequently.

1.3.5 The Four Deployment Models

• Public cloud. Cloud service vendors manage a public cloud; each customer can take computing resources from it. It is a mega-scale cloud infrastructure made available to the general public or a large industry group, owned by the organization selling the cloud services. Examples include AWS.
• Private cloud. Set up for one particular organization only. It may sit inside the organization or outside it; it may be managed by the organization itself or by a third party with cloud expertise. Resources are not shared among different organizations; users of the same organization access it. Scaling still happens — you add resources to your private cloud as the application grows, and those resources are not shared with others; with a vendor managing it, you can include resources on the fly by paying, so scalability is not as tough as with infrastructure you own. For the private cloud, you are charged for the resources you occupy.
• Hybrid cloud. A combination of two or more clouds, such as private and public, as unique entities bound together. Standardized technologies are needed, because applications must be portable between them. A typical scenario: an organization's private cloud reaches capacity and cannot serve more requests, so part of the application moves to a public cloud rather than buying further infrastructure or setting up another private cloud.
• Community cloud. Built for a set of organizations that share common concerns — security requirements, policy, compliance. Government organizations, for example, may share a community cloud. It may be managed by the organizations themselves or by a third party, and may exist on-premise or off-premise.

1.3.6 The Three Service Models

• Infrastructure as a Service (IaaS). You take storage, network capacity, and computing resources. AWS provides a whole lot of infrastructure of this kind. You manage the operating system and everything above it; the provider manages the hardware.
• Platform as a Service (PaaS). An operating system and certain resources come with the infrastructure, and you can execute your code and deploy your applications on it; middleware services may be included. It supports software development as well as deployment — a platform you can use directly from the cloud. You bring your code; the provider manages the platform underneath.
• Software as a Service (SaaS). A software package is hosted in the cloud and can be accessed from anywhere; customers do not purchase the software or install it on their devices — they use it directly from the cloud. Salesforce CRM (customer relationship management) is a practical example of the SaaS model.

1.3.7 Cloud Services for Big Data

Each service model maps onto big data needs. As infrastructure, the cloud provides ample storage and computing power: AWS offers S3 — S3 buckets used to store large amounts of data — and EC2 instances for compute. As a platform, vendors offer platforms ready with Hadoop and MapReduce installed: you just write your mappers and reducers, bring the data into the cluster, and do your processing. AWS Elastic MapReduce provides exactly that, saving you the hassle of installing and managing these environments (installing Hadoop is not easy on a Windows machine). As software, SaaS is a great help for organizations that need specialized software for big data — social media analytics, feedback monitoring: the vendor provides an out-of-the-box solution for such common use cases.

1.3.8 Cloud Market Leaders

Amazon is the most popular cloud vendor for big data: Amazon Web Services offers EC2 instances, MapReduce, DynamoDB (quite popular), S3 buckets, high-performance computing, and Redshift, software used to boost data warehouses. Google Cloud Platform offers Compute Engine, BigQuery, and the Prediction API. Microsoft gives Windows Azure — a cloud based on Windows — with SQL Azure and HDInsight. AWS is the most popular, and Azure and GCP are also growing; these are the three market leaders.

1.3.9 Student Questions and Answers

1.4 Reliability and Availability

1.4.1 Living with Failures

Every system is prone to failures. A distributed system is composed of multiple nodes connected through an interconnection network, so, like any other system, its nodes may fail and the interconnections may also fail. Failure of nodes and links is a very common concern in distributed systems, so fault tolerance must be a core part of the design. Fault tolerance is a measure of how a distributed system functions in the presence of failures. A distributed system consists of multiple components; if one component fails, the system may fail. How the system reacts to failures is measured by two parameters: reliability and availability.

1.4.2 Reliability and Availability

Reliability is the inverse indicator of the failure rate: how soon a system will fail. If the failure rate is high, reliability is low; if the failure rate is low, reliability is high. Availability is the percentage or fraction of the time the system is available for use: the system is not available during failures.

1.4.3 Mean Time to Failure (MTTF)

MTTF, mean time to failure, is the amount of time on average that a component can run before it breaks. It is an averaged value: you observe a component over several failure instances, note the times at which it fails, and average them. MTTF relates to the failure rate \(\lambda\) (lambda, how often failures occur per unit time) by:

\[ MTTF = \frac{1}{\lambda} \]

Equivalently, the failure rate is the inverse: \(\lambda = \frac{1}{MTTF}\). MTTF can also be computed as the total operating time across all units divided by the total number of units — the same average, seen from the other side.

1.4.4 Worked Example: MTTF of Five CFLs

1.4.5 MTTD, MTTR, and MTBF

Three more metrics complete the failure story. MTTD, mean time to diagnose, is the time taken to detect which component has failed once something goes wrong. It can be minimal — a few seconds — and often negligible, but it is a real quantity measured as an average over a set of observations. MTTR, mean time to recovery (or repair), is the time to repair or recover the component: total maintenance time divided by total repairs. If one failure is fixed in 30 minutes, another in 20 minutes, another in 10, another in 40, the mean time to repair is the average of those values. MTBF, mean time between failures, is the time duration between the first failure and the second failure.

1.4.6 Reliability in Serial Assembly

Components can be connected in series or in parallel, and that changes the system's MTTF. In serial assembly, the system C is composed of components A and B such that if A fails, C fails; if B fails, C also fails — failure of any component results in system failure.

The failure rate of the system is the sum of the failure rates of the individual components:

\[ \lambda_C = \lambda_A + \lambda_B = \frac{1}{M_A} + \frac{1}{M_B} \]

where \(M_A\) and \(M_B\) are the mean times to failure of components A and B. Since MTTF is the inverse of the failure rate, the system's mean time to failure is:

\[ M_C = \frac{1}{\lambda_C} = \frac{1}{\frac{1}{M_A} + \frac{1}{M_B}} \]

Generalizing to N components connected in series, the system MTTF is one divided by the sum of the reciprocal MTTFs:

\[ M_{system} = \frac{1}{\sum_{i=1}^{N} \frac{1}{M_i}} \]

1.4.7 Reliability in Parallel Assembly

In parallel assembly, the components back each other up: if B fails alone, C does not fail; if A fails alone, C does not fail; only when both A and B fail does the system C fail. This is the kind of configuration used to build fault-tolerant distributed systems — multiple nodes achieving fault tolerance. The system's mean time to failure is the sum of the component MTTFs:

\[ M_C = M_A + M_B \]

This is a larger value than either individual component's MTTF, so the system's reliability increases. Generalizing to N components in parallel:

\[ M_{system} = \sum_{i=1}^{N} M_i \]

1.4.8 Worked Example: Availability of a Cluster

1.4.9 Worked Example: The Yearly Cost of Downtime

1.5 Fault Tolerance Configurations

With multiple nodes, when one node fails we want another to take over, and we want to minimize downtime. This section walks the four classic configurations — load balanced, hot standby, warm standby, cold standby — from the most expensive and fastest-recovering to the cheapest and slowest, then looks at how they map onto active-active/active-passive deployments and the N+1 / N+M / N-to-1 / N-to-N topologies.

1.5.1 Load Balanced

The load-balanced configuration keeps both the primary node and the secondary node active: they process system requests in parallel, sharing the workload. The "secondary" node is so-called because it is also acting as a backup while sharing the load. If the primary fails, the whole workload shifts over to the secondary node.

1.5.2 Hot Standby

In hot standby, a software component is installed on both the primary node and the secondary node. The secondary node is up and running but does not process data until the primary node fails. The primary does the computations; when the primary fails, the secondary takes over, and the switching may take a few seconds because the secondary was not involved in the computations earlier.

1.5.3 Warm Standby

In warm standby, the software component is installed and available on the secondary node, but it may not have been configured, and the data exchange and sync between primary and secondary may be less frequent than in load-balanced or hot-standby setups. When the primary fails, the software components are configured on the secondary node, started there, and the process is automated by the cluster manager. This may take a few minutes — an intermediate time between hot standby and cold standby.

1.5.4 Cold Standby

Cold standby keeps a secondary node that acts as a backup identical to the primary system, but the secondary is installed and configured only when the primary fails. At that moment the secondary node is powered on, data is restored, and the failed component is restarted. Because the standby node was not configured or installed in advance, this takes a few hours — so the term "cold" standby. It is the cheapest to run (nothing running, nothing synced) and the slowest to recover.

1.5.5 The Trade-off: Failover Time versus Cost

The four configurations form a trade-off curve. Moving from load balanced to hot standby to warm standby to cold standby, the mean time to repair increases — zero, few seconds, few minutes, few hours — while the cost decreases.

Load balanced is expensive but gives high availability; cold standby is cheap but compromises availability because MTTR is high. You buy high availability with money, or save money and accept longer downtime.

1.5.6 Active-Active and Active-Passive

The configurations map onto two deployment styles. Active-active: a load balancer stands in front of multiple nodes, distributing requests — the first request goes to one node, the second to another, the third to the first, and so on; when one node fails, the others take over. Active-passive: the standby is not operational in parallel; it keeps doing nothing until the primary fails.

1.5.7 More Topologies: N+1, N+M, N-to-1, N-to-N

Fault tolerance configurations also address how many standby nodes to keep.

• N+1: one secondary node; if the primary fails, the secondary takes over — the simple model. One spare for N workers.
• N+M: m standby nodes, kept because it is anticipated that multiple nodes may fail at the same time. More spares than N+1, for tougher failure expectations.
• N-to-1: no dedicated secondary; instead there is one node with a lighter workload. If the primary fails, the tasks it was doing move to that low-load node temporarily, and once the primary is up and running again the tasks shift back.
• N-to-N: every node carries a similar workload and no special standby exists; whenever a node fails, its work is redistributed among the other nodes, because every node has some spare capacity.

1.6 Recovery

1.6.1 Diagnosis

Once a system fails, recovery starts with diagnosis — the MTTD discussed earlier. There will always be some time to detect the failure and locate the failed component. One common detection mechanism is heartbeat messages: nodes in a cluster send "I am alive" messages to each other. If no heartbeat arrives from a node for a certain threshold amount of time, the master node considers that something is wrong with that node. This is a simple example; other mechanisms exist, but heartbeats are the common one.

1.6.2 Backward Recovery

Backward recovery is the checkpointing approach, familiar from the recovery module of the RDBMS course. The idea: periodically save the state of a node on stable storage; each saved state is a checkpoint. Every node is supposed to save its state periodically. On failure: isolate the failed component, roll back to the last checkpoint — look at the persistent storage for the most recent saved state — and resume normal operation from there. That is why it is called backward recovery: you go back to the last saved state and resume from that point.

1.6.3 Forward Recovery

Forward recovery is used in specialized systems: real-time or time-critical systems where you do not want to roll back, or cannot roll back. Instead, you reconstruct on the fly from diagnosis data. When the system fails, something is written to a log — the diagnosis data records what happened; you analyze that data and try to eliminate the failure from it. What to dump into the diagnosis data is important and application-specific, and forward recovery may also need more hardware support to recover from the failure.

1.7 The CAP Theorem

CAP stands for consistency, availability, and partition tolerance. The next three subsections define each property, then the three scenarios show why you can hold at most two of them at once.

1.7.1 Consistency

Consistency means: a read of a data item from any node results in the same data across multiple nodes. Picture a network with nodes N1, N2, N3, N4 connected through an interconnection; whatever replication model they follow — primary-secondary, centralized, or a combination — if you read a data item X from node 4 and you read X from node 2, you should see the same value, say 5. If one node returns 7 and another returns 5, the system is inconsistent.

1.7.2 Availability

Availability means: a read or write request will always be acknowledged. If a user sends a read or write request through a node, the system responds with success or failure within a reasonable time. Whether the operation is allowed or not, the system should respond — it should not leave the request hanging for an unreasonable time; that state is what we call the system being unavailable.

1.7.3 Partition Tolerance

Partition tolerance means: the system can continue to function when a communication outage splits the cluster into multiple silos, and can still service read and write requests. A node may get disconnected from the network; the question is whether the system continues to operate in that state or waits for the node to come back.

Visualizing a partition: draw the cluster as a ring of nodes N1, N2, N3, N4 connected by links. Now erase one link: the nodes on one side of the break form one silo and the nodes on the other side form another, with no message able to cross. That broken ring is the partition. The partition-tolerant system keeps serving both silos; the non-tolerant one effectively stops until the link returns.

1.7.4 The Three CAP Scenarios

The balance between the three properties is best seen through three scenarios, all involving a network partition where the user wants to update the value on replica PRC to 82.

Scenario 1 — CA, no P. A network partition happens and the user wants to update PRC. Any access by the user to PRC leads to a failure message. The system is available, because it comes back with a response; it is consistent, because the user's update is not processed and the value stays the same across all three replicas. But there is no partition tolerance: when the network partitioned, the system did not allow user operations to succeed. You have C and A, but no P.

Scenario 2 — AP, no C. A network partition happens and the user wants to update PRC. PRC records the update with success, even though it is disconnected and cannot communicate the update to PRA and PRB immediately. The value at PRC becomes inconsistent with the values at A and B. But the system is available — it responded with a success message — and it is partition tolerant, because it allowed the operation to complete across the partition. You have P and A, but no C.

Scenario 3 — CP, no A. A network partition happens and the user wants to update PRC. The user is made to wait until the partition is fixed and the data is replicated on PRC before the success message is sent. The update eventually reaches all nodes, so there is consistency; the system tolerated the partition, so there is partition tolerance. But the success message was delayed — the system was not available while waiting. You have C and P, but no A.

1.7.5 The Theorem: You Get Two of Three

The CAP theorem states what these scenarios show: any distributed system running on a multi-node cluster can have any two of the three properties — CA, CP, or AP — but cannot have all three at the same time. You cannot have a system that provides consistency, availability, and partition tolerance simultaneously.

1.7.6 Student Questions and Answers on Network Partitions

Exam Guidance Summary

• Expect mathematical problems on availability and reliability: MTTF, MTTR, availability percentage, and the cost of downtime. A practice problem on availability and reliability (of the kind worked in this unit) is posted on the forum.
• In numericals, state your assumptions — this is part of the answer. Specifically, if MTTD is not given, assume it is negligible (zero); if it is given, include it in the availability formula.
• Know the two assembly formulas: serial assembly makes system MTTF the reciprocal of the sum of reciprocal component MTTFs (system reliability worsens with every added component); parallel assembly makes system MTTF the sum of component MTTFs (reliability improves).
• MapReduce will be practiced in a lab session: be able to look at a problem and decide what code goes in the map task and what goes in the reduce task. Python is used for the labs. Questions about how data is shared between map and reduce tasks and where shuffling happens will be covered there.
• Know the CAP theorem in depth, including the three scenarios (CA, AP, CP). The full treatment of consistency levels continues in the next session.

Key Industry Applications

• Real-world: The data sources motivating big data systems — stock exchanges, online retail (Amazon, Facebook), banking transactions, sensor data — all feed the storage-and-processing problem Hadoop solves.
• Real-world: Hadoop's MapReduce is used in industry for batch workloads: identifying patterns in system logs, running ETL (extraction, transformation, loading) tasks, computing web indexes, and building recommendation systems.
• Real-world: Apache Spark (with Spark MLlib and Mahout) handles the workloads MapReduce handles poorly — iterative machine learning training, streaming, and low-latency analytics — by caching working data sets in memory.
• Real-world: The Hadoop ecosystem is the standard industry stack: HDFS + MapReduce for the core, YARN for resource management, Sqoop and Flume for data ingestion, Hive for SQL-like analytics, Pig (Pig Latin) for non-programmers, Oozie for job scheduling, ZooKeeper and Apache Ambari for coordination, and NoSQL databases for specialized stores.
• Real-world: Cloud providers deliver big data infrastructure as a service: AWS (S3 buckets for storage, EC2 for compute, Elastic MapReduce as a pre-installed Hadoop platform, DynamoDB, Redshift for data warehouse acceleration), Google Cloud Platform (Compute Engine, BigQuery, Prediction API), and Microsoft Azure (SQL Azure, HDInsight).
• Real-world: SaaS products such as Salesforce CRM show the software-as-a-service model, and vendors offer out-of-the-box SaaS for social media analytics and feedback monitoring.
• Real-world: Relational databases running OLTP workloads — day-to-day business transactions with ACID semantics and global commit for distributed transactions — remain the backbone of operational systems, coexisting with the big data stack.
• Real-world: Production clusters detect failed nodes with heartbeat messages, protect data with replication (factor three in HDFS), and use standby configurations (load balanced, hot, warm, cold) whose failover time versus cost trade-off is chosen per application.