Right now, we go over the list of RateLimitPolicies and take the first one whose hostname field (Regex) matches the request's hostname. This means we have O(N) complexity just to find the RateLimitPolicy and then we have to find the match rule for additional rate limits.
We can probably improve this by creating a Trie structure using the hostnames, which should make the lookup a bit better. We'll go from top-level to lowest-level domain i.e. for example, *.example.com, find all com endings -> find all example.com endings, etc. This can be best served using the longest hostname match policy.
eguzki
commented
1 year ago
Right now, we go over the list of
RateLimitPoliciesand take the first one whose hostname field (Regex) matches the request's hostname. This means we haveO(N)complexity just to find theRateLimitPolicyand then we have to find the matchrulefor additional rate limits.We can probably improve this by creating a
Triestructure using the hostnames, which should make the lookup a bit better. We'll go from top-level to lowest-level domain i.e. for example,*.example.com, find allcomendings -> find allexample.comendings, etc. This can be best served using thelongest hostname matchpolicy.