I am learning about spark streaming, and i came across the function reduceByKeyAndWindow. It seems to be passed two lambda functions in official documention
reduceByKeyAndWindow(lambda x, y: x + y, lambda x, y: x - y, 30, 10)
I am a bit confuse, as to why second function is passed. As far as i know one function to reduce value is enough. I wanted to know what is the significance of the second function.
The first function is the actual reduce function. In this case you add the elements. The second is the inverse of the reduce function and it "undoes" what the reduce has computed, namely it performs a subtraction.
For example consider such window with overlapping values:
stream 2 3 5 8 1 ...
reduce = add
2 3 5 3 5 8 5 8 1 ...
|___| |___| |___|
10 16 14
Now in the example you could obtain 16 by adding 3+5+8 but since you already have 2+3+5 you "inverse reduce" by removing 2, i.e. you perform the subtraction (remember: reduce is sum, inverse of reduce is subtraction).
10-2
and then add 8. So, instead of computing (3+5) + 8 = 16 you compute (10-2) + 8 = 16.
From the source code https://github.com/apache/spark/blob/master/streaming/src/main/scala/org/apache/spark/streaming/dstream/DStream.scala
- reduce the new values that entered the window (e.g., adding new counts)
- "inverse reduce" the old values that left the window (e.g., subtracting old counts)
The advantage is that you avoid repeating the same computation. I assume that also caching values can bring some performance advantage.
Note that this can be done only for invertible functions (see also https://spark.apache.org/docs/latest/streaming-programming-guide.html#window-operations).