PadhaikoAll subjects

Distributed Storage and Data Processing

Distributed and Cloud Computing (ENCT 411)

Open in the Padhaiko app

5.1 Storage Models: File, Block, and Object Storage

Distributed storage systems expose three fundamental data abstractions depending on access patterns, scalability, and latency requirements.

Comparison of Storage Models: Block, File, and Object Storage
FeatureBlock StorageFile StorageObject Storage
Logical UnitFixed-size raw disk blocks ( sectors)Hierarchical directories and named filesFlat namespace of immutable objects (data + metadata + UUID)
Access ProtocoliSCSI, Fibre Channel, NVMe-oF, Cloud EBSPOSIX, NFS, SMB/CIFSHTTP/HTTPS REST (PUT, GET, DELETE — e.g. S3 API)
Metadata RichnessMinimal (block address LBA only)Fixed POSIX attributes (owner, permissions, timestamps)Rich custom key-value metadata (Content-Type, tags)
Update SemanticsIn-place random read/write of bytes/blocksIn-place file append and random byte modificationImmutable (full object overwrite/versioning)
Scalability & Use CasesUltra-low latency; databases, OS boot volumesModerate scale; shared home directories, web assetsMassive petabyte scale; data lakes, backups, media

5.2 Distributed File Systems: Design Issues, NFS, GFS, and HDFS

5.2.1 Design Issues in Distributed File Systems (DFS)

  1. Transparency: Network, location, and access transparency—allowing applications to use standard file APIs (open, read, write) seamlessly across remote servers.
  2. Naming and Name Resolution: Mapping human-readable paths to physical servers and block locations without global bottlenecks.
  3. Caching and Cache Coherence: Client-side caching reduces network round-trips, but concurrent updates require write-through, write-on-close, or lease/callback invalidation to prevent stale reads.
  4. Stateful vs. Stateless Servers: Stateless servers simplify crash recovery (client simply retries), whereas stateful servers enable read-ahead, file locking, and server-initiated callbacks.
  5. Fault Tolerance and Scalability: Striping and replicating large files across thousands of commodity disks where hardware failures are the norm, not the exception.

5.2.2 Network File System (NFS)

Developed by Sun Microsystems, NFS mounts remote server directories into a client's local VFS tree via ONC RPC:

5.2.3 Google File System (GFS) and Hadoop Distributed File System (HDFS)

Both GFS and HDFS are user-space, append-optimized distributed file systems built for multi-gigabyte/terabyte files and streaming batch reads across commodity hardware:

AspectGoogle File System (GFS)Hadoop DFS (HDFS)
Metadata CoordinatorSingle Master (+ Shadow Masters)NameNode (Active/Standby HA via JournalNodes)
Data NodesChunkservers ( chunks)DataNodes ( default blocks)
Write ModelRandom writes + atomic record append (multiple writers)Write-once, single writer per file (+ append)
API / EcosystemProprietary Google API (evolved into Colossus)Java / WebHDFS / POSIX-like CLI (Hadoop & Spark)

5.3 Software-Defined Storage: Ceph, Copy-on-Write, and Snapshots (ZFS)

5.3.1 Ceph (Unified Software-Defined Storage)

Ceph is an open-source, distributed, software-defined storage (SDS) platform that provides Object (RADOSGW/S3), Block (RBD), and POSIX File (CephFS) interfaces simultaneously on top of a single self-healing object cluster called RADOS (Reliable Autonomic Distributed Object Store).

5.3.2 Copy-on-Write (CoW) and Snapshots (ZFS)

Definition

Copy-on-Write (CoW) and ZFS Snapshots

Copy-on-Write (CoW) is a storage allocation strategy where modified blocks are never overwritten in place. Instead, new data is written to freshly allocated free blocks, and parent pointers in a tree of block pointers (Merkle tree / Uberblock root in ZFS) are updated atomically once the new blocks hit disk.


5.4 Concurrency Control Approaches: Lock, Optimistic, and Timestamp-Based

Distributed transactions running concurrently across shards require concurrency control to guarantee serializability (equivalent to some serial execution order).

5.4.1 Lock-Based Concurrency Control (Two-Phase Locking, 2PL)

Pessimistic approach assuming conflicts are common:

5.4.2 Optimistic Concurrency Control (OCC)

Assumes conflicts are rare (e.g., high-read web apps), executing without locks in three phases:

  1. Read Phase: Transaction reads items and buffers all writes into a private local workspace.
  2. Validation Phase: At commit time, verifies that no other concurrently committed transaction wrote to any item in this transaction's read set (or write set).
  3. Write Phase: If validation succeeds, writes are applied atomically; otherwise the transaction aborts and restarts cleanly.

5.4.3 Timestamp-Based Concurrency Control (Basic TO & Thomas Write Rule)

Every transaction is assigned a unique global monotonic timestamp at startup; each data item tracks (largest timestamp of any reader) and (largest timestamp of any writer):

Comparison of Distributed Concurrency Control Approaches
CriterionStrict 2PL (Locking)Optimistic (OCC)Timestamp Ordering (TO)
Conflict HandlingPessimistic (blocks before access)Optimistic (checks at commit)Pessimistic order by startup timestamp
Deadlocks Possible?Yes (requires detection or Wait-Die)NoNo (aborts on out-of-order access)
Best WorkloadHigh write contentionLow contention, read-heavyShort transactions with rare conflicts
Failure / Starvation RiskLock-wait delays & deadlocksRepeated aborts under high contentionStarvation if repeatedly restarted

5.5 Distributed Data Processing: MapReduce, Hadoop YARN, and Apache Spark

5.5.1 MapReduce Programming Model

Proposed by Dean and Ghemawat (Google, 2004), MapReduce processes massive datasets in parallel by moving computation to the data nodes (data locality):

  1. Input Split & Map(k1, v1) -> list(k2, v2): Each worker parses an HDFS block split and emits intermediate key-value pairs.
  2. Shuffle and Sort (Framework-Managed): Intermediate pairs are partitioned by hash of k2, sorted by k2, and transferred over the network to Reducer nodes (optional Combiner runs mini-reduction locally on mappers to shrink network traffic).
  3. Reduce(k2, list(v2)) -> list(k3, v3): Aggregates all values sharing key k2 and writes final outputs back to HDFS.

5.5.2 Hadoop YARN (Yet Another Resource Negotiator)

YARN separates resource management from job execution so Hadoop clusters can run MapReduce, Spark, and graph engines side-by-side:

5.5.3 Apache Spark

Apache Spark overcomes MapReduce's heavy disk I/O bottleneck between stages (where MapReduce writes intermediate outputs to HDFS after every job) by processing data in memory:

AspectHadoop MapReduceApache Spark
Intermediate StorageDisk / HDFS between every Map-Reduce stageIn-memory (RAM) across multi-stage DAGs
Execution ModelRigid 2-stage (Map -> Reduce)Flexible multi-stage DAG with lazy evaluation
Iterative ML / Graph SpeedSlow ( slower due to disk I/O)Very fast ( faster in RAM)
Fault ToleranceReplicates intermediate/output data on diskRecomputes lost partitions via RDD lineage
PySpark Word Count Pipeline (Transformations + Action)Python
# Assume 'sc' is an initialized SparkContext reading from HDFS
lines = sc.textFile("hdfs:///data/logs.txt")
counts = (
    lines.flatMap(lambda line: line.split())       # Transformation (lazy)
         .map(lambda word: (word.lower(), 1))      # Transformation (lazy)
         .reduceByKey(lambda a, b: a + b)          # Wide transformation (shuffle)
)
top_words = counts.take(10)                        # Action (triggers DAG execution)

Worked Out Examples

Example 5.1

5.1

An HDFS cluster stores of unique raw data (, ) using the default block size of and replication factor . Assume each block metadata entry (including 3 replica locations) consumes in NameNode RAM.

  1. Calculate the total number of unique HDFS blocks and total physical block replicas stored across all DataNodes.
  2. Calculate the NameNode RAM required to store all block metadata (in ).
  3. Why would choosing a block size instead of hurt this cluster?

1. Unique Blocks and Total Physical Replicas: Convert to :

Number of unique blocks:

With replication factor :

2. NameNode RAM Footprint:

3. Effect of Shrinking Block Size to : A block size increases block count by ( blocks, replicas), inflating NameNode RAM by to and causing massive disk seek overhead instead of sequential streaming.

Answer:
  1. unique blocks and physical block replicas ( raw storage).
  2. NameNode RAM required .
  3. A block size multiplies NameNode RAM () and destroys sequential read efficiency.
Example 5.2

5.2

Suppose data item initially has and . Trace the following operations arriving in sequence from transactions (), (), and () under (a) Basic Timestamp Ordering and (b) Timestamp Ordering with Thomas Write Rule:

  1. : Read(X)
  2. : Write(X)
  3. : Write(X)

Operation 1 — () executes Read(X): Since , the read is valid! Update:

Operation 2 — () executes Write(X): Check : is true! A younger transaction ( at ) has already read the older value of , so writing now would violate serializability. Under both Basic TO and Thomas Write Rule, is aborted and restarted! ( unchanged.)

Operation 3 — Suppose instead after Operation 1, a transaction () wrote (so ), and then (? Wait—say with vs with ): let's trace Operation 3 as given ( with executes Write(X) when ): Since , is attempting to write into the past before 's read (). Thus is aborted under both schemes. (Contrast with Thomas Write Rule case: if and , and with writes , then holds while —Basic TO aborts , whereas Thomas Write Rule safely ignores 's obsolete write without aborting!)

Answer:
  1. Read(X) succeeds ().
  2. Write(X) aborts ().
  3. Write(X) aborts (). (Thomas Write Rule skips aborts only when and .)
Example 5.3

5.3

Exam-Style Design (MapReduce + Spark): An analytics cluster processes of clickstream logs stored in HDFS at an aggregate disk read/write rate of ( per full read or write).

  1. Explain how a Combiner optimizes a MapReduce click-count job: if mappers emit of intermediate (product_id, 1) pairs and a Combiner compresses shuffle traffic by (down to ) over a network, compute the combined HDFS read plus reduced network shuffle time.
  2. Compare total I/O + pass time for a -iteration machine learning workload if MapReduce reads and writes to HDFS on every iteration ( read + write per iteration) versus Apache Spark reading into RAM once () and running in-memory iterations at each.

1. Combiner Optimization in MapReduce: Before sending intermediate (product_id, 1) records across the network, a Combiner performs a mini-reduction locally on each mapper node, merging (P101, 1), (P101, 1), (P101, 1) into (P101, 3).

  • HDFS read time .
  • Reduced shuffle data , which at takes (down from ).
  • Combined read + reduced shuffle time .

2. Six-Iteration Workload: MapReduce vs. Spark:

  • MapReduce (disk-backed between every stage): Each iteration pays HDFS read + HDFS write :
  • Apache Spark (RDD cached in RAM): Loads from HDFS once () and runs all iterations directly in memory ( each):

Spark achieves a speedup purely by eliminating redundant HDFS serialization between iterations.

Answer:
  1. Local Combiner pre-aggregation shrinks shuffle volume (), giving total read + shuffle time.
  2. Across iterations, MapReduce takes vs. Spark's (over faster).

Exercises

Practice Exercises — Distributed Storage and Data Processing

Question 1

Compare File, Block, and Object storage across data model, access protocol, mutability, scalability, and ideal cloud workloads.

Storage Model Comparison:

  • Block Storage: Raw fixed-size blocks over iSCSI/NVMe-oF; in-place updates, ultra-low latency, used for databases and VM boot disks.
  • File Storage: Hierarchical directory tree over NFS/SMB; POSIX file APIs, shared network folders.
  • Object Storage: Flat namespace of immutable objects (payload + rich metadata + UUID) over HTTP REST (S3); scales to exabytes for backups, media, and data lakes.
Answer:

Block offers lowest-latency raw block I/O for databases; File provides shared POSIX directories via NFS/SMB; Object delivers massively scalable immutable storage with rich metadata over HTTP REST.

Question 2

Explain why GFS and HDFS choose large block sizes ( / ) instead of standard filesystem blocks. For a dataset (), calculate the number of unique blocks under (a) chunks (GFS) and (b) blocks (HDFS).

Rationale for Large Blocks:

  1. Keeps all block metadata compact enough to reside completely in Master/NameNode RAM.
  2. Amortizes disk seek latency across huge sequential transfers and reduces client-to-Master RPC lookups.

Unique Block Counts ():

Answer:

Large blocks minimize Master RAM footprint and seek overhead. A dataset yields GFS chunks () or HDFS blocks ().

Question 3

Explain how Ceph eliminates centralized metadata bottlenecks using the CRUSH algorithm, and explain how ZFS Copy-on-Write (CoW) enables instant, crash-safe snapshots.

Ceph CRUSH Placement: Instead of querying a central NameNode on every read/write, Ceph clients run the deterministic CRUSH pseudo-random hash function locally over the compact cluster map to compute the exact Primary and Replica OSDs directly—eliminating lookup hotspots and automatically rebalancing on node failures.

ZFS Copy-on-Write and Snapshots: ZFS never overwrites live blocks in place; updates write to free blocks and atomically swap parent block pointers up to the root Uberblock. A snapshot simply pins an immutable reference to an older tree root in time with zero initial space cost, sharing unchanged blocks until subsequent writes diverge.

Answer:

Ceph CRUSH lets clients compute object-to-OSD locations mathematically without a central lookup server. ZFS CoW preserves prior block trees intact and swaps the root atomically, making snapshots instantaneous and crash-consistent.

Question 4

Compare Two-Phase Locking (Strict 2PL), Optimistic Concurrency Control (OCC), and Timestamp-Based Concurrency Control (including the Thomas Write Rule optimization).

Comparison of Mechanisms:

  • Strict 2PL: Acquires shared/exclusive locks before access and holds exclusive locks until commit; prevents dirty reads/cascading aborts, but can deadlock.
  • OCC: Runs lock-free in Read Validation Write phases; deadlock-free and fast under low contention, but wastes work on aborts under high contention.
  • Timestamp Ordering: Orders transactions by startup timestamp via per-item and ; deadlock-free. Thomas Write Rule avoids unnecessary aborts by silently ignoring obsolete writes ( when ).
Answer:

Strict 2PL uses pessimistic locks (deadlock-prone); OCC validates lock-free reads at commit (best for low contention); Timestamp Ordering enforces startup-timestamp order without deadlocks, optimized by the Thomas Write Rule to skip obsolete writes.

Question 5

Trace the stages of a MapReduce job (Map, Shuffle/Sort, Reduce), explain the roles of ResourceManager, NodeManager, and ApplicationMaster in Hadoop YARN, and state why Apache Spark outperforms MapReduce on iterative algorithms.

MapReduce and YARN Architecture:

  • MapReduce: Map transforms input splits into (k2, v2) pairs; the framework hashes, sorts, and shuffles them to reducers; Reduce aggregates each key's value list into final output.
  • YARN: ResourceManager allocates global containers, per-node NodeManager runs/monitors containers, and per-job ApplicationMaster negotiates resources and schedules tasks.

Why Apache Spark Is Faster: MapReduce writes intermediate data to HDFS between every job, incurring heavy disk and network serialization I/O. Spark keeps RDDs in cluster RAM across multi-stage DAGs with lazy evaluation and recovers faults via RDD lineage recomputation, speeding up iterative ML/graph workloads by .

Answer:

MapReduce runs Map -> Shuffle/Sort -> Reduce coordinated by YARN's ResourceManager, NodeManager, and ApplicationMaster. Spark avoids inter-stage HDFS disk writes by caching RDDs in memory across multi-stage DAGs with lineage-based fault tolerance.

← Replication, Consistency and ConsensusCloud Computing →