CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 6 of 8 · 4 min read

Joins and state

A stream job often needs to remember things, and that memory must survive a crash.

Think of a waiter matching orders with the guests' table numbers. The orders arrive as a stream. The table plan changes during the evening as guests move. The waiter keeps a small notebook with the latest table plan, and looks each order up in it.

DDIA separates three joins on streams:

Join What is joined Example What the job remembers
Stream-stream (window join) Two event streams with a common key Search events and click events for the same session Recent events from both sides in a time window
Stream-table (enrichment) A stream and a table that changes Activity events plus user profiles A local copy of the table
Table-table (view maintenance) Two changing tables Tweets and follow relations making home timelines Both tables

Stream-stream. To find the click-through rate of search results, you need to match each search to a click with the same session id. The click may never come, or may arrive days later, or even before the search event. You choose a window, for example one hour. The processor keeps all events of the last hour indexed by session id. When a click arrives it checks for a search with the same id. If a search expires without a click, it emits "not clicked". Joining needs both streams: embedding search details in the click event would hide the searches that were never clicked.

Stream-table. Looking up each event's user in a remote database is slow and can overload it, as in batch. So a copy of the table is loaded into the processor, in memory or on local disk, as in a hash join. The copy must stay up to date. The answer is change data capture (page 7): the processor subscribes to the table's changelog and updates its local copy. So this becomes a join of two streams. The table stream has a window reaching back to the beginning of time, where newer versions replace older ones.

Table-table. The Twitter timeline cache of earlier levels is a view that has to be kept up to date from two streams: tweets (sent and deleted) and follows (started and stopped). The processor keeps the followers of each user, so it knows which timelines to update.

A worked example. A user profile table has user 7 in the country "UK". The stream has click events.

Time Input Local table copy Output
1 Profile change: user 7 country UK 7 = UK none
2 Click by user 7 7 = UK Click by user 7, country UK
3 Profile change: user 7 country FR 7 = FR none
4 Click by user 7 7 = FR Click by user 7, country FR

Joins are sensitive to order. DDIA points out that ordering is kept inside one partition but not across different streams. So when a user updates a profile, which clicks are joined with the old profile and which with the new? A related case is a tax rate that changes: an invoice should use the rate at the time of the sale, not today's rate, especially when old data is reprocessed. If the order of events across streams is undetermined, the join is nondeterministic: rerunning the same job on the same input may give a different result. Data warehouses call this a slowly changing dimension. The usual fix is to give each version of the joined record its own identifier, for example a new id whenever the tax rate changes, and to store that id in the invoice. That makes the join deterministic. The cost, the book notes, is that log compaction is no longer possible, because every version must be kept.

Keeping state. Any windowed count, average or join table is state that must survive a crash. DDIA gives options:

  • Keep state in a remote database. Each lookup costs a network trip and is slow.
  • Keep state local and replicate it. Apache Flink saves snapshots of operator state to durable storage. Samza and Kafka Streams send state changes to a compacted log topic, similar to change data capture.
  • Rebuild state from the input. If the state is an aggregate over a short window, replaying the events of that window is enough. If it is a copy of a database, it can be rebuilt from the compacted change stream.

The book says no choice suits all cases. It depends on whether the network is faster than the disk in the given system.

Check yourself:

  • Why must a stream-stream join keep events in memory or local storage for the length of the window?
  • Name two ways of making sure a stream job's state survives a crash.