Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[cleanup] Introduce proper key'ing type for our Limit & Counter #328

Open
Tracked by #182
alexsnaps opened this issue May 15, 2024 · 3 comments · May be fixed by #397
Open
Tracked by #182

[cleanup] Introduce proper key'ing type for our Limit & Counter #328

alexsnaps opened this issue May 15, 2024 · 3 comments · May be fixed by #397
Assignees
Labels
area/library kind/enhancement New feature or request

Comments

@alexsnaps
Copy link
Member

alexsnaps commented May 15, 2024

rather than the hybrid model we currently use that has led to multiple issues in the past.
In Kuadrant, we probably want to leverage the #356 identity field always

This was referenced May 30, 2024
@alexsnaps alexsnaps added this to the Limitador Server v2.0.0 milestone Jul 29, 2024
@alexsnaps alexsnaps moved this to Todo in Kuadrant Nov 25, 2024
@alexsnaps alexsnaps added kind/enhancement New feature or request area/library labels Nov 25, 2024
@alexsnaps alexsnaps self-assigned this Nov 27, 2024
@alexsnaps alexsnaps moved this from Todo to In Progress in Kuadrant Nov 27, 2024
@alexsnaps alexsnaps linked a pull request Nov 27, 2024 that will close this issue
@alexsnaps
Copy link
Member Author

alexsnaps commented Nov 29, 2024

So I'm getting a little stuck here… This led me to refactor the CounterStorage trait(s) to look something like this:

pub trait CounterStorage: Sync + Send {
    fn add_counters(&self, keys: &[CounterKey]) -> Result<(), StorageErr>;
    fn get_counters(&self, keys: &[CounterKey]) -> Result<Vec<(u64, Duration)>, StorageErr>;
    fn update_counters(&self, key: &[CounterKey], delta: u64) -> Result<Vec<(u64, Duration)>, StorageErr>;
    fn delete_counters(&self, keys: &[CounterKey]) -> Result<(), StorageErr>;
    fn clear(&self) -> Result<(), StorageErr>;

    // This is where things get … interesting.
    fn check_and_update(
        &self,
        counters: &[CounterKey],
        delta: u64,
    ) -> Result<Authorization, StorageErr>;
    fn check_and_update_loading(
        &self,
        counters: &[CounterKey],
        delta: u64,
    ) -> Result<(Authorization, Vec<Counter>), StorageErr>;
}

These check_and_update have a weird contract. The first 5 are pretty straight forward CRUD operations… but the other two mix domain logic in them. Interestingly tho, they try to deal with the data races introduced by Read-Update-Write cycles, while only the InMemoryStorage does it somewhat reasonably. Redis, as one of the favorite "other" way to store counters, will "just" read, check no counter is above, and eventually write back. So being racy on checking, tho will be coherent on writing (so that two concurrent calls could be allowed where only one should have had, but the both counter increments will be accounted for).

So my dilemma here is: either we make embrace this race and just have the caller either get_counters, check them and then update_counters, which may lead to a value pass the limit's max_value… which is what we do in Redis; or keep that within the CounterStorage to deal with, some sort of conditional_update_counters, but would need to take the limit's max_value as additional data somehow… e.g. fn update_counters_cond(&self, key: &[(CounterKey, u64)], delta: u64) -> Result<Vec<(u64, Duration)>, StorageErr>;

wdyt?

For the curious, here is what I was thinking a CounterKey would be:

pub enum CounterKey {
    Identified((Namespace, String)),
    Simple((Namespace, SimpleCounterKey)),
    Qualified((Namespace, SimpleCounterKey, Vec<String>)),
}

impl CounterKey {
    fn namespace(&self) -> &Namespace {
        match self {
            CounterKey::Identified((ns, _)) => ns,
            CounterKey::Simple((ns, _)) => ns,
            CounterKey::Qualified((ns, _, _)) => ns,
        }
    }
}

impl Eq for CounterKey {}

impl PartialEq<Self> for CounterKey {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

impl PartialOrd<Self> for CounterKey {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for CounterKey {
    fn cmp(&self, other: &Self) -> Ordering {
        match self.namespace().cmp(other.namespace()) {
            Ordering::Equal => {
                match self {
                    CounterKey::Identified((_, id)) => {
                        match other {
                            CounterKey::Identified((_, other)) => id.cmp(other),
                            _ => Ordering::Less,
                        }
                    }
                    CounterKey::Simple((_, key)) => {
                        match other {
                            CounterKey::Identified(_) => Ordering::Greater,
                            CounterKey::Simple((_, other)) => key.cmp(other),
                            CounterKey::Qualified(_) => Ordering::Less,
                        }
                    }
                    CounterKey::Qualified((_, key, qualifiers)) => {
                        match other {
                            CounterKey::Identified(_) => Ordering::Greater,
                            CounterKey::Simple(_) => Ordering::Greater,
                            CounterKey::Qualified((_, other_key, other_qualifiers)) => {
                                match key.cmp(other_key) {
                                    Ordering::Equal => qualifiers.cmp(other_qualifiers),
                                    other => other,
                                }
                            }
                        }
                    }
                }
            },
            other => other,
        }
    }
}

#[derive(Eq, PartialEq, Ord, PartialOrd, Debug)]
pub struct SimpleCounterKey {
    seconds: u64,
    conditions: Vec<String>,
}

impl From<&Limit> for CounterKey {
    fn from(limit: &Limit) -> Self {
        let mut conditions = Vec::from(limit.conditions());
        conditions.sort();
        let mut variables = Vec::from(limit.variables());
        variables.sort();

        Self {
            namespace: limit.namespace().clone(),
            seconds: limit.seconds(),
            conditions,
            variables,
        }
    }
}

@eguzki
Copy link
Contributor

eguzki commented Dec 2, 2024

My take on this would be embrace this race and just have the caller either get_counters, check them and then update_counters, which may lead to a value pass the limit's max_value…. If the counter exceeds the max value due to racing... so what? 🤷

@alexsnaps
Copy link
Member Author

If the counter exceeds the max value due to racing... so what? 🤷

It's less about it happening than "forcing" all implementation of the CounterStorage to have to suffer from the race. So while, today, all implementation are effectively doing a get_counters, followed by a "blind" update_counters... I think I'll keep the compounded operations for the CounterStorage to do, i.e. have a check_and_update(&self, key: &[(CounterKey, u64)], delta: u64) function for the implementer to decide.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area/library kind/enhancement New feature or request
Projects
Status: In Progress
Development

Successfully merging a pull request may close this issue.

2 participants