Worksheet

A13.7 Functional programming and big data

Functional programming · A level · AQA 7517 4.11.1, Eduqas A500QS 1.4 · about 25 min

What this lesson is about

Volume, velocity and variety, why big data needs distributed processing, and how immutability, statelessness and higher-order functions make MapReduce work.

• What makes data big
• When one machine is not enough
• Why functional programming fits
• MapReduce

Questions 6 marks in all

1. [1 mark]Which three features are used to describe big data?

   Tick every answer that is true.

   1. AVolume
   2. BVelocity
   3. CVariety
   4. DVisibility

2. [1 mark]Why does processing big data usually have to be distributed?

   1. AThe data is too big to fit on, or be processed by, a single server
   2. BRelational databases cannot store numbers
   3. CFunctional languages can only run on more than one machine
   4. DDistributed processing needs no network

3. [1 mark]Which features of functional programming make it easier to write correct distributed code?

   Tick every answer that is true.

   1. AImmutable data structures
   2. BStatelessness
   3. CHigher-order functions
   4. DGlobal variables shared by all machines
   5. EUpdating data in place

4. [1 mark]How does statelessness help when a job is spread over many machines?

   1. AA pure function gives the same result on any machine in any order, so chunks can be processed in parallel and failed work simply rerun
   2. BIt means the machines do not need any memory
   3. CIt stops the data from being split into chunks
   4. DIt makes every machine run the program one after another

5. [1 mark]In MapReduce, partial results can arrive in any order and in any grouping. Which combining function is safe to use in the reduce stage?

   1. AAdding counts
   2. BSubtracting one count from another
   3. CTaking the mean of two partial means
   4. DKeeping whichever result arrived first

6. [1 mark]In a graph schema, what does an edge represent?

   1. AA relationship between two nodes
   2. BA value stored about a node
   3. COne entity, such as a robot
   4. DA single timestamped fact

The task: count the fleet's events

Three machines each hold one chunk of a fleet's event log (in the starter). Each line is <robot>,<event>, such as "bot2,bump". Count how many times each event happens, MapReduce style: - to_counts(line) returns a dictionary with one key, the event, and the value 1: to_counts("bot2,bump") is {"bump": 1}. - merge(a, b) takes two dictionaries of counts and returns a new dictionary holding every event in either, with the counts added. It must not change a or b, so there must be no d[key] = ... assignment or update anywhere in the program: build the new dictionary with a dictionary comprehension. - machine(chunk) is what one machine does: map to_counts over the chunk's lines and fold the results together with merge, starting from {}. - Map machine over CHUNKS, then fold the three partial results together with merge. Print the totals one per line, events in alphabetical order, as <event> <count>, such as bump 4. Then print same as one machine: True if the result equals machine applied to all the lines joined into one tuple (it should).

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from functools import reduce

CHUNKS = (
    ("bot1,bump", "bot2,tag", "bot1,tag", "bot3,stall"),
    ("bot2,bump", "bot3,tag", "bot1,bump"),
    ("bot3,tag", "bot2,stall", "bot1,tag", "bot2,bump"),
)

counts = {}
for chunk in CHUNKS:
    for line in chunk:
        event = line.split(",")[1]
        counts[event] = counts.get(event, 0) + 1
print(counts)

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a13-7-functional-programming-and-big-data/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

1. Is "keep the larger of two numbers" associative? Is subtraction? For each, work out (8 with 5) with 2 and 8 with (5 with 2), and say which could be used as a reduce stage.
2. Change the program to count events per robot instead. Which function changes, and which stay exactly the same?
3. A fleet of robots streams readings at 10,000 per second. Which of volume, velocity and variety does that describe, and why can a relational database struggle with it?