[Discussion] Requirements and design choices for a sketch-based streaming pre-compute

[milindsrivastava1997]

This is an issue to discuss requirements, constraints and other design choices to be made for a sketch-based streaming precompute engine.

[milindsrivastava1997]

Originally by @linear[bot] on 2026-02-19:

PRO-419

[milindsrivastava1997]

Originally by @milindsrivastava1997 on 2026-02-19:

Possible candidates for creating an embeddable stream processing library as a replacement for arroyo+ArroyoSketch:

* [Denormalized](https://github.com/probably-nothing-labs/denormalized). Seems to be exactly what we want, but repo is abandoned

* Extract core functionality from arroyo

* timely-dataflow

* Make one using datafusion. Datafusion contributors were discussing adding streaming support, but [discussion](https://github.com/apache/datafusion/issues/11404) is inactive from Jul 2024

* Fluvio

From #102 (https://github.com/ProjectASAP/asap-internal/issues/314#issuecomment-3792550734)

[milindsrivastava1997]

Originally by @milindsrivastava1997 on 2026-02-19:

Some requirements to implement our pre-compute engine (I can think of):

* A buffer for out-of-order arriving samples in terms of time

* An internal time series data structure as the buffer to store raw samples

* Sketchlib-rust import given required sketches to precompute.

* Be ware of reducing memory allocation for sketches

* If a single-node version, this should be multi-threading. We can check out how VictoriaMetrics implements their streaming aggregation.

* If a distributed cluster version, this can be natively partitioned by time series metric name, or a better load balancing mechanism TBD.

From ProjectASAP/asap-internal#395 (https://github.com/ProjectASAP/asap-internal/issues/395#issuecomment-3918465908)

[milindsrivastava1997]

Originally by @milindsrivastava1997 on 2026-02-19:

We can take inspiration from the following:

• VictoriaMetrics streaming aggregation
• Non-o11y time series databases like Influx, Timescale, Clickhouse

There is some info on these here. The TLDR seems to be that none of these are expressive enough to implement sliding windows. They do simple tumbling windows or simple trigger-based recomputation.

cc @zzylol

[milindsrivastava1997]

Originally by @zzylol on 2026-02-20:

@milindsrivastava1997 Thanks. Could you share where the code in Arroyo right now is in the sliding window?

[milindsrivastava1997]

Originally by @milindsrivastava1997 on 2026-02-20:

I do not know where the logic is in the arroyo source code. This is where the sliding window queries get instantiated in ArroyoSketch.

[milindsrivastava1997]

Originally by @zzylol on 2026-02-20:

I guess my question is, in ArroyoSketch, when do you need a sliding window? Also, I think it's easier if we build our own precompute engine with a sliding window, because then we have full control of memory states, and any optimizations for our own purpose.

[milindsrivastava1997]

Originally by @milindsrivastava1997 on 2026-02-20:

I guess my question is, in ArroyoSketch, when do you need a sliding window?

Ah. I was trying it as an alternative to tumbling windows. Consider this example. quantile_over_time(data[10m]) repeating every 30 sec.

One solution is to compute KLL sketches for tumbling windows of 30 sec in arroyo. QueryEngine will merge 10m/30sec = 20 sketches to answer each quantile_over_time query.

Another solution is to compute KLL sketches in arroyo in sliding windows of size=10m and slide=30s. In this case, QueryEngine does not need to do any merging.

There are possible designs in between these two as well. For e.g., you can compute sliding windows with size=5m and slide=30s, and then QueryEngine has to merge 10m/5m = 2 sketches to answer each query.

[milindsrivastava1997]

Originally by @zzylol on 2026-02-20:

"to compute KLL sketches in arroyo in sliding windows of size=10m and slide=30s. In this case, QueryEngine does not need to do any merging." If you do with DDSketch, it is possible, but I don't think you can do subtraction for KLL directly.
For the sliding window solution, we need to make sure Arroyo indeed maintains it as a multiple tumbling window implementation behind the sliding window interface.

Same question as, how can you construct a sliding quantile algorithm? And how can you implement the real sliding quantile algorithm in the sliding window interface provided by streaming engines?

[milindsrivastava1997]

Originally by @milindsrivastava1997 on 2026-02-20:

Yes, this depends on the subtraction capability.

For the sliding window solution, we need to make sure Arroyo indeed maintains it as a multiple tumbling window implementation behind the sliding window interface.

Idk how they implement it but those are the semantics, yes. That's what all streaming engines like Flink and Arroyo do.

Same question as, how can you construct a sliding quantile algorithm? And how can you implement the real sliding quantile algorithm in the sliding window interface provided by streaming engines?

Didn't understand. Are you asking how we can answer sliding window quantile_over_time queries? There is no fancy sliding window sketches here. It's just "maintain independent KLL sketches for each sliding window". In the TurboProm design, each window is treated separately.

[milindsrivastava1997]

Originally by @zzylol on 2026-02-20:

So in Flink and Arroyo, sliding windows are essentially multiple tumbling windows?

[milindsrivastava1997]

Originally by @milindsrivastava1997 on 2026-02-20:

I wouldn't call it multiple tumbling windows exactly. Tumbling windows, by definition, do not overlap. Sliding windows overlap but each sliding window is maintained independently of the other. See https://nightlies.apache.org/flink/flink-docs-release-2.2/docs/dev/datastream/operators/windows/#sliding-windows