Struct Counter

pub struct Counter<const N: usize, const M: usize> { /* private fields */ }

A counter useful for counting how many times a function invocation is called in last X seconds/minutes/hours. N is the number of buckets and M is the number of sub-buckets.

In the documentation and in the code, we use key to refer the temporal unit (e.g. seconds, minutes, hours) of the invocation. Because this library don’t want force you to use seconds, you can use any unit you want. You can consider to use std::time::Instant::elapsed().as_secs() as the key for instance.

Counter groups keys into buckets based on the group_shift_factor: key >> group_shift_factor % N will be the bucket index. The index for the sub-bucket is key % M.

Internal structure

Internally, the Counter uses a ring buffer of N buckets. Each bucket has M sub-buckets. This allows the Counter to distribute the load across multiple sub-buckets when the keys have the same index.

For instance, Counter<3, 2>::new(4) will be like:

               ----------   ----------   ----------
               | (0, 0) |   | (0, 0) |   | (0, 0) |
               | (0, 0) |   | (0, 0) |   | (0, 0) |
               ----------   ----------   ----------
index              0            1            2
key range 1       0-16        17-31        32-47
key range 2      48-63        64-80         ...

Implementations

impl<const N: usize, const M: usize> Counter<N, M>

pub fn new(group_shift_factor: u32) -> Self

Create a new counter with the given group shift factor.

group_shift_factor is the number of bits to shift the key to get the group index.

Examples found in repository

examples/readme.rs (line 9)

fn main() {
    const BUCKET_COUNT: usize = 16;
    const SUB_BUCKET_COUNT: usize = 2;
    const GROUP_SHIFT_FACTOR: u32 = 4;
    // 4 is the group_shift_factor
    // 16 is the number of buckets
    let counter = Counter::<BUCKET_COUNT, SUB_BUCKET_COUNT>::new(GROUP_SHIFT_FACTOR);

    // Typically you want to use something like `Instant::now().elapsed().as_secs()`
    let mut now: u64 = 0;
    counter.increment_by_one(now);

    now += 1; // Simulate a second passing
    counter.increment_by_one(now);

    assert_eq!(counter.get_count_till(now), 2);

    now += 2_u64.pow(GROUP_SHIFT_FACTOR) * BUCKET_COUNT as u64; // Move forward...
    counter.increment_by_one(now);
    // The counter forgot about the counts older than 2 ** 4 * 16 seconds
    assert_eq!(counter.get_count_till(now), 1);
}

pub fn increment_by_one(&self, key: u64)

Register an invocation.

This will increment the value of the key by one. You can use std::time::Instant::elapsed().as_secs() as the key for instance.

Examples found in repository

examples/readme.rs (line 13)

fn main() {
    const BUCKET_COUNT: usize = 16;
    const SUB_BUCKET_COUNT: usize = 2;
    const GROUP_SHIFT_FACTOR: u32 = 4;
    // 4 is the group_shift_factor
    // 16 is the number of buckets
    let counter = Counter::<BUCKET_COUNT, SUB_BUCKET_COUNT>::new(GROUP_SHIFT_FACTOR);

    // Typically you want to use something like `Instant::now().elapsed().as_secs()`
    let mut now: u64 = 0;
    counter.increment_by_one(now);

    now += 1; // Simulate a second passing
    counter.increment_by_one(now);

    assert_eq!(counter.get_count_till(now), 2);

    now += 2_u64.pow(GROUP_SHIFT_FACTOR) * BUCKET_COUNT as u64; // Move forward...
    counter.increment_by_one(now);
    // The counter forgot about the counts older than 2 ** 4 * 16 seconds
    assert_eq!(counter.get_count_till(now), 1);
}

pub fn get_count_till(&self, key: u64) -> usize

Get the count of invocations till the given key.

This will return the total count of invocations till the given key. You can use std::time::Instant::elapsed().as_secs() as the key for instance.

Examples found in repository

examples/readme.rs (line 18)

fn main() {
    const BUCKET_COUNT: usize = 16;
    const SUB_BUCKET_COUNT: usize = 2;
    const GROUP_SHIFT_FACTOR: u32 = 4;
    // 4 is the group_shift_factor
    // 16 is the number of buckets
    let counter = Counter::<BUCKET_COUNT, SUB_BUCKET_COUNT>::new(GROUP_SHIFT_FACTOR);

    // Typically you want to use something like `Instant::now().elapsed().as_secs()`
    let mut now: u64 = 0;
    counter.increment_by_one(now);

    now += 1; // Simulate a second passing
    counter.increment_by_one(now);

    assert_eq!(counter.get_count_till(now), 2);

    now += 2_u64.pow(GROUP_SHIFT_FACTOR) * BUCKET_COUNT as u64; // Move forward...
    counter.increment_by_one(now);
    // The counter forgot about the counts older than 2 ** 4 * 16 seconds
    assert_eq!(counter.get_count_till(now), 1);
}

Trait Implementations

impl<const N: usize, const M: usize> Debug for Counter<N, M>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.