relay_cardinality/
window.rs

1use std::fmt;
2
3use relay_common::time::UnixTimestamp;
4use serde::{Deserialize, Serialize};
5
6/// A sliding window.
7#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord, Deserialize, Serialize)]
8#[serde(rename_all = "camelCase")]
9pub struct SlidingWindow {
10    /// The number of seconds to apply the limit to.
11    pub window_seconds: u64,
12    /// A number between 1 and `window_seconds`. Since `window_seconds` is a
13    /// sliding window, configure what the granularity of that window is.
14    ///
15    /// If this is equal to `window_seconds`, the quota resets to 0 every
16    /// `window_seconds`.  If this is a very small number, the window slides
17    /// "more smoothly" at the expense of having much more redis keys.
18    ///
19    /// The number of redis keys required to enforce a quota is `window_seconds /
20    /// granularity_seconds`.
21    pub granularity_seconds: u64,
22}
23
24impl SlidingWindow {
25    /// Iterate over the quota's window, yielding values representing each
26    /// (absolute) granule.
27    ///
28    /// This function is used to calculate keys for storing the number of
29    /// requests made in each granule.
30    ///
31    /// The iteration is done in natural-order (oldest timestamp to newest),
32    /// starting with the key to which a currently-processed request should be
33    /// added. That request's timestamp is `request_timestamp`.
34    ///
35    /// * `request_timestamp / self.granularity_seconds`
36    /// * `request_timestamp / self.granularity_seconds + 1`
37    /// * `request_timestamp / self.granularity_seconds + 2`
38    /// * ...
39    pub fn iter(&self, timestamp: UnixTimestamp) -> impl Iterator<Item = Slot> {
40        let value = timestamp.as_secs() / self.granularity_seconds;
41        (0..self.window_seconds / self.granularity_seconds)
42            .map(move |i| value + i)
43            .map(Slot)
44    }
45
46    /// The active bucket is the oldest active granule.
47    pub fn active_slot(&self, timestamp: UnixTimestamp) -> Slot {
48        self.iter(timestamp).next().unwrap_or(Slot(0))
49    }
50}
51
52/// A single slot from a [`SlidingWindow`].
53#[derive(Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
54pub struct Slot(u64);
55
56impl fmt::Display for Slot {
57    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
58        write!(f, "{}", self.0)
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use std::time::Duration;
65
66    use super::*;
67
68    #[test]
69    fn test_sliding_window() {
70        let window = SlidingWindow {
71            window_seconds: 3600,
72            granularity_seconds: 720,
73        };
74
75        let timestamp = UnixTimestamp::from_secs(7200);
76        let r = window.iter(timestamp).collect::<Vec<_>>();
77        assert_eq!(
78            r.len() as u64,
79            window.window_seconds / window.granularity_seconds
80        );
81
82        assert_eq!(r, vec![Slot(10), Slot(11), Slot(12), Slot(13), Slot(14)]);
83        assert_eq!(window.active_slot(timestamp), *r.first().unwrap());
84
85        let r2 = window
86            .iter(timestamp + Duration::from_secs(10))
87            .collect::<Vec<_>>();
88        assert_eq!(r2, r);
89
90        let r3 = window
91            .iter(timestamp + Duration::from_secs(window.granularity_seconds))
92            .collect::<Vec<_>>();
93        assert_ne!(r3, r);
94    }
95}
relay_cardinality/window.rs

relay_cardinality/
window.rs
