A log too big for one disk
An online shop keeps a log of every click. After two years the log is 4 TB. No single disk in the office holds it, and one computer would need most of a working day just to read it once.
Big data tools cut the file into pieces, store the pieces on many machines and let every machine work on its own piece.
By the end of this lesson
Note
I can explain how a file is split and processed in parallel.
Key words
| Word | What it means | Example |
|---|---|---|
| Block | one fixed-size piece of a big file | 128 MB |
| NameNode | the machine that knows where every block is | |
| DataNode | a machine that holds blocks | |
| Replica | an extra copy of a block on another machine | |
| Map | the step that turns each piece of data into pairs | |
| Reduce | the step that adds the pairs for one key together |
The cells students fill in are left blank in this preview.
HDFS cuts a file into blocks
HDFS is the Hadoop file system. It cuts every file into blocks of a fixed size, 128 MB by default. The last block is whatever is left over.
Each block is stored on a DataNode, and copied to others so one failure loses nothing. One NameNode keeps the list: which blocks make up which file, and where they are.
Worked example: a 300 MB file
| Block | Size | Copies kept | Held by |
|---|---|---|---|
| 1 | 128 MB | 3 | three different DataNodes |
| 2 | 128 MB | 3 | three different DataNodes |
| 3 | 44 MB | 3 | three different DataNodes |
| Total | 300 MB | 9 copies | The NameNode holds only the list |
The cells students fill in are left blank in this preview.
Count the blocks of a file
# A file is cut into blocks of a fixed size.
size_mb = 300
block_mb = 128
full = size_mb // block_mb
rest = size_mb % block_mb
blocks = full
if rest > 0:
blocks = blocks + 1
print("blocks:", blocks)
print("size of the last block:", rest, "MB")
copies = blocks * 3
print("copies kept on disk:", copies)
# Change size_mb to 500 and run again.
List the lab's input folder
curl -s 'http://namenode:9870/webhdfs/v1/user/lab/input?op=LISTSTATUS' | grep -o '"pathSuffix":"[^"]*"'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask for its block size and length
curl -s 'http://namenode:9870/webhdfs/v1/user/lab/input/sentence.txt?op=GETFILESTATUS' | grep -o '"blockSize":[0-9]*\|"length":[0-9]*'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask how many copies HDFS keeps
curl -s 'http://namenode:9870/webhdfs/v1/user/lab/input/sentence.txt?op=GETFILESTATUS' | grep -o '"replication":[0-9]*'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask how much disk the folder uses
curl -s 'http://namenode:9870/webhdfs/v1/user/lab/input?op=GETCONTENTSUMMARY' | grep -o '"spaceConsumed":[0-9]*'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think the NameNode stores the file. It stores only the list of blocks and where they are. The DataNodes hold the bytes. Ask "who has the bytes?" and the answer is a DataNode.
MapReduce moves the work to the data
Copying 4 TB over a network is slow. So Hadoop sends the small program to the machines that already hold the blocks.
Each machine runs the map step on its own block, with no talking to the others. The pairs are then grouped by key, which is called the shuffle. The reduce step adds up each group.
Worked example: counting words
| Step | Block one | Block two |
|---|---|---|
| Input | red fish / blue fish | red car / red bus |
| Map | red 1, fish 1, blue 1, fish 1 | red 1, car 1, red 1, bus 1 |
| Shuffle (group by word) | red: 1, 1, 1 / fish: 1, 1 / blue: 1 / car: 1 / bus: 1 | Pairs from both blocks meet here |
| Reduce (add up) | red 3, fish 2, blue 1, car 1, bus 1 | One total for each word |
The cells students fill in are left blank in this preview.
Map and reduce in plain Python
# Two blocks of a log of items sold.
block_one = ["red fish", "blue fish"]
block_two = ["red car", "red bus"]
def map_block(lines):
# The map step: turn every word into a pair [word, 1].
pairs = []
for line in lines:
for word in line.split():
pairs.append([word, 1])
return pairs
def reduce_pairs(pairs):
# The reduce step: add up the ones for each word.
totals = {}
for pair in pairs:
word = pair[0]
if word in totals:
totals[word] = totals[word] + pair[1]
else:
totals[word] = pair[1]
return totals
mapped = map_block(block_one) + map_block(block_two)
print(reduce_pairs(mapped))
# Add the line "blue bus" to block_two and run again.
A job leaves its answer in HDFS
A MapReduce run is called a job. The ResourceManager hands out the work, and the answer is written back into HDFS as files.
Each reducer writes one file called part-r- and a number. An empty file called _SUCCESS says the job finished.
List the job's output folder
curl -s 'http://namenode:9870/webhdfs/v1/user/lab/wordcount-out?op=LISTSTATUS' | grep -o '"pathSuffix":"[^"]*"'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Count the different words it found
curl -s -L 'http://namenode:9870/webhdfs/v1/user/lab/wordcount-out/part-r-00000?op=OPEN' | wc -lShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask how the job ended
curl -s http://resourcemanager:8088/ws/v1/cluster/apps | grep -o '"finalStatus":"[A-Z]*"'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Going further: add up before sending
Block two sends four pairs to the shuffle, and two of them are "red 1". A real job can add up inside each block first. This step is called a combiner.
Change map_block in the MapReduce block so it returns totals for its own block, as pairs. Run it. How many pairs leave block two now, and is the final answer the same?