Measure the latency of the different "happy" scenarios

[alexsnaps]

In order to better understand the implications of leveraging the cloud providers Redis instances, we want to build a latency distribution matrix for all the different providers, but starting our with AWS's Elasticache.

We need a distribution for a LRT that:

• Increments a counter, without ever reaching the limit (i.e. a RW usecase for Redis)
• Reaches a limit and consistently responds with a 429 HTTP response code for a period
• The same as the above, but with qualified counters (which we'll use to introduce data locality)

We then need to test these in multiple deployment scenarios:

• From one location: same as the "master" (if applicable), from a different AZ, from different regions across the globe
• From multiple location, distributed according the above

That use:

• all the same limit (single globally shared counter)
• each use a qualified counter for their az/region

Performance tests

• AWS 1 EC2 instance with Limitador (memory backend) and Driver #71
• AWS 1 EC2 instance with Limitador and Driver, 1 EC2 instance with redis single master #72
• AWS 1 EC2 instance with Limitador and Driver, Elasticache (1 instance with 1 single master node) #73
• AWS 1 EC2 instance with Limitador and Driver, Elasticache (1 instance with 1 master 1 slave nodes) #74
• AWS 1 EC2 instance with Limitador and Driver, 1 EC2 instance with redis single master, 1 EC2 instance with redis single slave #75

Latencies in multiple deployment scenarios

Using cloudping as latency data source

• Same AZ AWS 1 EC2 instance with Limitador and Driver, Elasticache (1 instance with 1 master 1 slave nodes) #74
• Different AZ (Increment Counter / single globally shared counter / Elasticache 1 replica) #77
• us-east-2 (Ohio) -- > us-east-1 (N. Virginia) ~10ms #78
• eu-north-1 (Stockholm) -- > eu-central-1 (Frankfurt) ~36ms #79
• us-east-1 (N. Virginia) -- > us-west-1 (N. California) ~75ms #80
• eu-west-1 (Ireland) -- > us-west-2 (Oregon) ~126ms #81
• ap-east-1 (Asia Pacific Hong Kong) -> ca-central-1 (Canada Central) ~209ms #82
• ap-southeast-2 (Asia Pacific (Sydney)) -> eu-north-1 (Stockholm) ~295ms #83
• ap-southeast-2 (Asia Pacific (Sydney)) -> af-south-1 (Africa Cape Town) ~417ms #84

EDIT: no need to test further. We confirmed expected understanding of limitdor's request to redis model. The N+1 model.

Scenarios with transient gw & redis_cached

• Test with 3 limits across 2 regions
• Test with 3 limits & redis_cached instead across these 2 same regions
• Do we want to test the bin encoding as well? It should reduce the amount of bytes sent over the wires...

Scenario with write-behind-lock Kuadrant/limitador#276

• sa-east-1 (Sao Paulo) -- > elasticache eu-central-1 (Frankfurt) ~200ms 3 limits with low time periods #87
• sa-east-1 (Sao Paulo) -- > elasticache eu-central-1 (Frankfurt) ~200ms 3 limits one 1 with low time periods #88

[alexsnaps]

What happens (currently)

Today, Limitador will do n + 1 round-trips to Redis (or in this case the cloud provider's Redis-alike, e.g. Elasticache) when "in the happy path", where n is amount of limits being hit.

sequenceDiagram
    participant E as Envoy
    participant L as Limitador
    box grey Cloud provider's Redis-alike
        participant R as Redis
    end
    
    E->>+L: should_rate_limit?
    L->>R: MGET
    R->>L: counter values
    loop for every counter
        L->>R: LUA script increment
        R->>L: ()
    end
    L->>-E: Ok!

Loading

So say you have 3 limits (per hour, per day and per month) and your user is currently not above the threshold of these 3 limits, we'd need to do 4 round-trips to Redis to let them thru and increment the counters. Based on the testing above, we can fairly much confirm that a single round-trip to Redis is about the figures from cloudping.

What we could do about it (for now)

Improve on the current design

Instead of going to Redis n + 1 times, we could invoke a server-side Lua script that increments all counters in one go and returns the latest values in a single round-trip. While 1 is obviously much better than the current n + 1, a single round-trip time quickly goes in double digit milliseconds. So going to Redis on every single request that is rate limited seems unreasonable.

Leverage the existing CachedRedisStorage

We do have an alternate Redis-backed AsyncCounterStorage implementation that caches counter values in Limitador's memory, avoiding needing the round-trip to the backend Redis storage.

sequenceDiagram
    participant E as Envoy
    participant L as Limitador
    participant C as Cached counter
    box grey Cloud provider's Redis-alike
        participant R as Redis
    end
    
    E->>+L: should_rate_limit?
    L->>C: Read local values
    L->>R: Fetch missing counters 
    R->>L: values & ttl
    L->>C: (Store and) Increment counters
    L->>-E: Ok!
        loop Every second (by default)
        loop Per counter
           L->>R: LUA script increment
           R->>L: ()
        end
    end

Loading

While this addresses most of the cases, the jitter on the user's request remains with a max of 1 time the round-trip to the Redis' region from the call-site (tho right now it's worse than one rtt, because of the blocking nature of the write-behind task). At least it's paid once, rather than once with an addition round-trip per counter.

While this is probably the easiest way forward addressing what we've now seen happening in AWS, there are few items to address:

• The "write-behind" task is currently blocking reads for the entire duration of writing of each counter
• Bulk update counters instead of one by one (see how big that batch can become)
• Possibly returning the latest value and update the cached values
• Fix --ratio on the command line…
• Look into asynchronously pre-reloading the counters

[alexsnaps]

Obviously, the list above are small improvements for us to get closer to something sustainable in such a deployment. Probably some better caching strategy (rather than time based expiry), e.g. Hi/Lo, would be preferable, as we know we are dealing with counters that tends towards a known limit. And eventually get to completely avoid the need for coordination across the different limitador, probably by leveraging CRDTs, like a grow-only counter.