Complex event processing
What is the state of a pattern match, and what keeps it bounded?
CEP matches patterns over a sequence of events. Example, from the fraud team: "an order, then zero or more cancellations, then a refund, all within 30 minutes."
An automaton over event time
A pattern compiles to an NFA (non-deterministic finite automaton): a small state machine that can be in several states at the same time, because a new event may continue several partial matches. The state kept per key is not the events but the set of live partial matches. That is where the cost hides.
With quantifiers (A B* C, meaning "A, then any number of B, then C") and a within bound, the number of simultaneously live partial matches can be combinatorial in the number of candidate events. So state is O(keys × partial matches), rather than O(keys).
Small example. Pattern A B* C with relaxed matching (other events may occur between matched ones). After one A and k B events, each B can be included in a partial match or not, so there can be 2^k different partial matches. With k = 20 candidate B events that is 2^20 = 1,048,576 partial matches for one key.
- candidate B events seen after an A
Data table
| Candidate B events k | Partial matches |
|---|---|
| 0 | 1 |
| 0.375 | 1.3 |
| 0.75 | 1.68 |
| 1.13 | 2.18 |
| 1.5 | 2.83 |
| 1.88 | 3.67 |
| 2.25 | 4.76 |
| 2.63 | 6.17 |
| 3 | 8 |
| 3.38 | 10.4 |
| 3.75 | 13.5 |
| 4.13 | 17.4 |
| 4.5 | 22.6 |
| 4.88 | 29.3 |
| 5.25 | 38.1 |
| 5.63 | 49.4 |
| 6 | 64 |
| 6.38 | 83 |
| 6.75 | 108 |
| 7.13 | 140 |
| 7.5 | 181 |
| 7.88 | 235 |
| 8.25 | 304 |
| 8.63 | 395 |
| 9 | 512 |
| 9.38 | 664 |
| 9.75 | 861 |
| 10.1 | 1.12K |
| 10.5 | 1.45K |
| 10.9 | 1.88K |
| 11.3 | 2.44K |
| 11.6 | 3.16K |
| 12 | 4.1K |
| 12.4 | 5.31K |
| 12.8 | 6.89K |
| 13.1 | 8.93K |
| 13.5 | 11.6K |
| 13.9 | 15K |
| 14.3 | 19.5K |
| 14.6 | 25.3K |
| 15 | 32.8K |
| 15.4 | 42.5K |
| 15.8 | 55.1K |
| 16.1 | 71.5K |
| 16.5 | 92.7K |
| 16.9 | 120K |
| 17.3 | 156K |
| 17.6 | 202K |
| 18 | 262K |
| 18.4 | 340K |
| 18.8 | 441K |
| 19.1 | 572K |
| 19.5 | 741K |
| 19.9 | 962K |
| 20.3 | 1.25M |
| 20.6 | 1.62M |
| 21 | 2.1M |
| 21.4 | 2.72M |
| 21.8 | 3.53M |
| 22.1 | 4.57M |
| 22.5 | 5.93M |
| 22.9 | 7.69M |
| 23.3 | 9.98M |
| 23.6 | 12.9M |
| 24 | 16.8M |
| 24.4 | 21.8M |
| 24.8 | 28.2M |
| 25.1 | 36.6M |
| 25.5 | 47.5M |
| 25.9 | 61.5M |
| 26.3 | 79.8M |
| 26.6 | 103M |
| 27 | 134M |
| 27.4 | 174M |
| 27.8 | 226M |
| 28.1 | 293M |
| 28.5 | 380M |
| 28.9 | 492M |
| 29.3 | 638M |
| 29.6 | 828M |
| 30 | 1.07B |
Bounding mechanisms are all about pruning
- The
withintimeout kills stale partial matches. It is the retention rule of CEP. - Contiguity semantics decide how many branches are spawned per event. Strict contiguity (matched events must be directly adjacent) spawns few. Relaxed contiguity (other events may lie between) spawns many.
- The after-match skip strategy decides how many overlapping matches survive. "Skip past last match" (continue after the last event of a found match) instead of "skip to next row" (restart from the event after the first matched one) can be the difference between linear and quadratic state.
The sort buffer
The NFA assumes per-key input is in event order, which it is not. So a CEP operator needs an event-time sort buffer in front of it: events wait until the watermark passes them, then are released in timestamp order. This is another retention rule, sized by the allowed lateness (how late an event may be and still be used). It is paid for here.