Sliding Window CRDT Sketches

Sketches maintain compact approximate statistics about streams of data, thereby enabling quickly answering queries regarding the data stream without having to reprocess it. Often, recent data is considered more important than older one, which is captured by the sliding window model. In distributed settings, where parts of the stream are seen by different, potentially geographically distributed components of the system, it makes sense to collect global statistics about the stream, but in a decentralized manner. Further, in order to ensure availability, scalability, and good performance, it is appealing to treat sketches as a CRDT data-type. In this work we introduce the notion of sliding window CRDT sketches. We then present the CRDT All Timestamps (aka CRDT-AT) and CRDT Last Timestamp (aka CRDT-LT) algorithms for implementing such sketches and analyze them. We also study the performance of CRDT-AT and CRDT-LT using real workloads, to establish their viability.