Distributed Storage & Paradigma MapReduce (Hadoop / HDFS)

Capaian Pembelajaran

Setelah minggu ini kamu bisa:

1. Menjelaskan kapan analitik harus berpindah dari satu mesin ke klaster.
2. Menjelaskan arsitektur HDFS: NameNode, DataNode, blok, replikasi, rack awareness.
3. Menghitung jumlah blok dan kebutuhan penyimpanan HDFS.
4. Menguraikan alur MapReduce: Map → Shuffle & Sort → Reduce, termasuk Combiner dan Partitioner.
5. Menulis program MapReduce sederhana (WordCount, agregasi log) dan mensimulasikannya di Python.

1. Mengapa Perlu Komputasi Terdistribusi?

Misal log transaksi 10 TB. Satu disk membaca ±200 MB/s:

10 TB / 200 MB/s = 10.000.000 MB / 200 = 50.000 detik ≈ 14 jam   (hanya MEMBACA!)

Jika dibagi ke 100 mesin yang membaca paralel → ±8,4 menit.

Dua strategi skala:

Hadoop (2006, terinspirasi paper Google File System 2003 & MapReduce 2004) mewujudkan scale out dengan dua prinsip:

1. Bawa komputasi ke data (data locality), bukan memindahkan data ke komputasi — jaringan lebih lambat dari disk lokal.
2. Kegagalan adalah hal normal — dengan ribuan mesin, selalu ada yang rusak; sistem harus otomatis pulih.

2. Ekosistem Hadoop

 ┌──────────────────────────────────────────────────────────┐
 │  Hive (SQL)   Pig   HBase (NoSQL)   Spark   Mahout ...   │  ← aplikasi/analitik
 ├──────────────────────────────────────────────────────────┤
 │  MapReduce (model pemrograman batch)                      │  ← komputasi
 ├──────────────────────────────────────────────────────────┤
 │  YARN (Yet Another Resource Negotiator)                   │  ← manajemen sumber daya
 ├──────────────────────────────────────────────────────────┤
 │  HDFS (Hadoop Distributed File System)                    │  ← penyimpanan
 └──────────────────────────────────────────────────────────┘

3. HDFS (Hadoop Distributed File System)

3a. Arsitektur master–worker

                    ┌───────────────────────┐
     Client ───────►│      NameNode         │  metadata: nama file, blok,
       │  (1) tanya │  (master, 1 aktif)    │  lokasi replika (di RAM)
       │  lokasi    └───────────────────────┘
       │                 ▲ heartbeat & block report (tiap ~3 detik)
       │ (2) baca/tulis langsung ke DataNode
       ▼                 │
 ┌──────────┐  ┌──────────┐  ┌──────────┐  ┌──────────┐
 │DataNode 1│  │DataNode 2│  │DataNode 3│  │DataNode 4│
 │ B1  B3   │  │ B1  B2   │  │ B2  B3   │  │ B1  B2 B3│
 └──────────┘  └──────────┘  └──────────┘  └──────────┘
      Rack 1          Rack 1        Rack 2        Rack 2

3b. Blok & replikasi

• File dipecah menjadi blok berukuran besar: default 128 MB (Hadoop 2+). Blok besar → sedikit metadata & seek disk relatif kecil dibanding waktu transfer.
• Setiap blok direplikasi 3 kali (default) di DataNode berbeda.
• Rack awareness (penempatan default): replika 1 di node penulis, replika 2 di node pada rack lain, replika 3 di node lain pada rack yang sama dengan replika 2 → tahan terhadap kegagalan satu rack.
• Blok terakhir tidak dipenuhi sampai 128 MB: file 300 MB → blok 128 + 128 + 44 MB (blok terakhir hanya memakai 44 MB disk).

Rumus:

jumlah_blok         = ceil(ukuran_file / ukuran_blok)
total_replika_blok  = jumlah_blok × faktor_replikasi
kapasitas_disk_raw  = ukuran_file × faktor_replikasi

Contoh: file log 1 GB (= 1024 MB), blok 128 MB, replikasi 3.

• Jumlah blok = ceil(1024 / 128) = 8
• Total salinan blok di klaster = 8 × 3 = 24
• Kapasitas disk terpakai = 1024 × 3 = 3072 MB (3 GB)

Contoh 2: file 500 MB → ceil(500/128) = ceil(3,906) = 4 blok (128, 128, 128, 116 MB).

HDFS dirancang untuk: file besar, pola write-once read-many, akses berurutan (throughput tinggi), bukan latensi rendah. Kurang cocok untuk jutaan file kecil (membebani RAM NameNode).

4. Paradigma MapReduce

Pemrogram cukup menulis dua fungsi:

map    : (k1, v1)        → list[(k2, v2)]
reduce : (k2, list[v2])  → list[(k3, v3)]

Framework mengurus pembagian data, penjadwalan, shuffle, toleransi kegagalan.

Alur lengkap

 Input (HDFS)      MAP              SHUFFLE & SORT                 REDUCE           Output
 ┌─────────┐   ┌──────────┐                                   ┌───────────┐
 │ split 1 │──►│ mapper 1 │──(data,1)(mining,1)(data,1)──┐    │ reducer 1 │──► (data, 3)
 └─────────┘   └──────────┘                              ├──► │ data:[1,1,1]   (big, 1)
 ┌─────────┐   ┌──────────┐                              │    │ big:[1]   │
 │ split 2 │──►│ mapper 2 │──(big,1)(data,1)(spark,1)────┤    └───────────┘
 └─────────┘   └──────────┘                              │    ┌───────────┐
                                                         └──► │ reducer 2 │──► (mining, 1)
                                 partisi berdasar             │ mining:[1]│    (spark, 1)
                                 hash(key) % R                │ spark:[1] │
                                                              └───────────┘

4a. WordCount (contoh "Hello World" big data)

def mapper(baris):
    for kata in baris.split():
        yield (kata, 1)

def reducer(kata, daftar_nilai):
    yield (kata, sum(daftar_nilai))

Trace dengan 2 dokumen: "data besar data" dan "data mining":

4b. Combiner: menghemat jaringan

Tanpa combiner, mapper 1 mengirim 3 pasangan. Dengan combiner (sama dengan reducer sum), mapper 1 mengirim (data,2)(besar,1) = 2 pasangan.

Syarat combiner: operasi asosiatif & komutatif (sum, max, min, count). Rata-rata tidak boleh langsung dijadikan combiner — avg(avg(1,2), avg(3)) = avg(1.5, 3) = 2.25 ≠ avg(1,2,3) = 2. Solusinya kirim pasangan (jumlah, banyak) lalu bagi di reducer.

4c. Agregasi log transaksi

Log CSV: tanggal,kota,produk,jumlah,harga. Pertanyaan: total pendapatan per kota?

def mapper(baris):
    tgl, kota, produk, jumlah, harga = baris.split(",")
    yield (kota, int(jumlah) * int(harga))

def reducer(kota, nilai):
    yield (kota, sum(nilai))

Ini setara SQL SELECT kota, SUM(jumlah*harga) FROM log GROUP BY kota — Hive menerjemahkan kueri SQL semacam ini menjadi job MapReduce.

5. Toleransi Kegagalan

• Map task gagal → dijalankan ulang di node lain yang punya replika blok tersebut.
• Reduce task gagal → dijalankan ulang; output map disimpan di disk lokal sehingga bisa diambil lagi.
• Speculative execution: task yang lambat (straggler) dijalankan duplikat; yang selesai duluan dipakai.
• DataNode mati → NameNode mendeteksi dari heartbeat yang hilang, lalu mereplikasi ulang blok agar kembali 3 salinan.

6. YARN

YARN membuat Hadoop bisa menjalankan bukan hanya MapReduce, tetapi juga Spark, Flink, dsb.

7. Keterbatasan MapReduce → Spark

MapReduce menulis hasil antara ke disk di setiap job. Algoritma iteratif (K-Means, regresi logistik, PageRank) butuh puluhan iterasi = puluhan job = sangat lambat. Apache Spark (Minggu 13) menyimpan data antara di memori, bisa 10–100× lebih cepat untuk beban iteratif.

8. Menjalankan Hadoop (opsional)

# Hadoop Streaming: mapper & reducer dalam Python (baca stdin, tulis stdout)
hdfs dfs -mkdir -p /user/mhs/input
hdfs dfs -put log_transaksi.csv /user/mhs/input/
hadoop jar $HADOOP_HOME/share/hadoop/tools/lib/hadoop-streaming-*.jar \
  -input /user/mhs/input -output /user/mhs/output \
  -mapper mapper.py -reducer reducer.py -file mapper.py -file reducer.py
hdfs dfs -cat /user/mhs/output/part-00000
hdfs fsck /user/mhs/input/log_transaksi.csv -files -blocks -locations   # lihat blok & replika

Cara termudah mencoba: image Docker Hadoop single-node atau layanan cloud (Dataproc, EMR). Di lab ini kita mensimulasikan MapReduce dengan Python murni supaya alurnya terlihat jelas.

Ringkasan

• HDFS memecah file menjadi blok 128 MB, direplikasi 3× di DataNode berbeda; NameNode menyimpan metadata.
• MapReduce = map (ubah ke key-value) → shuffle & sort (kelompokkan per key) → reduce (agregasi).
• Combiner mengurangi lalu lintas jaringan; hanya untuk operasi asosiatif & komutatif.
• Partitioner hash(key) mod R menjamin satu key ke satu reducer.
• MapReduce lambat untuk algoritma iteratif → motivasi Spark.

Bacaan

• Dean & Ghemawat (2004) — MapReduce: Simplified Data Processing on Large Clusters.
• Ghemawat, Gobioff & Leung (2003) — The Google File System.
• Leskovec, Rajaraman & Ullman — Mining of Massive Datasets, Bab 2.
• White — Hadoop: The Definitive Guide.

Tugas Minggu Ini

1. Kerjakan lab.ipynb sampai selesai.
2. Kerjakan kuis (di web, atau baca quiz.json).
3. Isi exercise.py, lalu cek: python check.py 12