Section 8: Twenty Bytes Per Promise - Deep Dive: Guaranteed Processing — the Acker & XOR Tuple Trees

Executive Summary: Every tuple gets a random 64-bit id. An acker keeps one 64-bit "ack val" per spout tuple and XORs in every id when it is created and again when it is acked, so the value returns to zero exactly when the whole tuple tree is done. That costs about 20 bytes per pending post (the 2014 paper's figure), however large the tree. For the trending topology it means 4 acker messages per post, 2.4 M/s at peak and 12 ackers. A tree not finished within 30 s is failed and replayed from its Kafka offset. That is Decision 3, at-least-once, and it has two bills. The ack gates ingest, because every unfinished tree holds a max.spout.pending slot. And the duplicates: at most 0.18% of the window after a crash, inside trending's ±1% and unacceptable for billing.

Interviewer: "Post p-77120 turned into two hashtag tuples on two different machines. How does spout task 4 know both were counted, without anyone storing the tree?"

You: "Nobody stores the tree. One acker stores a single number that is zero only when the tree is complete."

The Algorithm in Four Rules

Every tuple gets a random 64-bit id, and every tuple in a tree carries its spout tuple's root id. Fields grouping on the root id sends every message about a tree to the same acker, which keeps one entry per pending root: root id → (ack val, spout task id).

1. Spout emit. Spout task 4 emits p-77120 with message id = its Kafka offset on partition 19, and Storm assigns root id R. The spout tells the acker "init R", so the ack val becomes R.
2. Anchored emit. The parse bolt emits #worldcup (id W) and #goal (id G), both anchored to R. Nothing is sent yet; the collector XORs each child id into a running value kept for the input tuple.
3. Ack. When the parse bolt acks its input, it sends one message carrying R ⊕ W ⊕ G: the input's own id combined with every child it emitted. The acker XORs that into the ack val. Count executor 9 acks W and count executor 2 acks G, and since they emit nothing anchored, each message carries just its own id.
4. Zero means done. When the ack val reaches 0, the acker tells spout task 4, which calls ack(msgId) and the Kafka offset becomes committable (the spout commits acked offsets every 5 s in our setting). If a bolt calls fail, or the tree is still pending after 30 s (the message timeout, default in recent releases), the spout calls fail(msgId) and re-emits from that offset.

So each id is XORed in exactly twice: once when it is created (R at init; W and G inside the parse bolt's ack) and once when it is acknowledged (R inside the parse bolt's ack; W and G in the count acks). Since x ⊕ x = 0 and XOR is order-independent, the total is zero exactly when every created tuple has been acked.

(The real implementation gives each tree edge its own random id, keyed by the root id; the algebra is identical.)

Quick check before moving on: