We scaled the GitHub API with a sharded, replicated rate limiter in Redis

https://github.blog/2021-04-05-how-we-scaled-github-api-sharded-replicated-rate-limiter-redis/

143 21 5 years ago

gigatexal2• 5 years ago

We had a saying at my old job: if something’s broken it’s never Redis. Redis is such a tank in my experience. We set it up. Secured it. And then forgot about it.

junon3• 5 years ago

Absolutely. Of course I plan for what happens if Redis were to fail, but I don't remember a single time it ever did. It really, truly is a tank.

Antirez, if you're reading this (I know you'll eventually find your way here), thanks for making my job a little easier over the years <3

rshaw1• 5 years ago

I thought the same up until yesterday!

Yesterday the replica randomly disconnected from the master and could no longer reconnect, the resyncs were failing because a replication buffer on the master was being hit (https://redislabs.com/blog/top-redis-headaches-for-devops-re...). Once that buffer was increased the replica was able to sync the snapshot from the master but for some reason was taking a very long time to load the snapshot, during this time the sentinels thought the replica was healthy again and started allowing the application to read from them, of course Redis responded with an error "dataset loading". We were running Redis 6.0.8 and upgrading the replica to 6.2.1 allowed the replica to sync and become healthy in seconds.

I'm still not sure why the sentinels thought the replica was healthy as issuing commands to it always returned an error.

gigatexal2• 5 years ago

Whoa! You should blog about this for posterity for the next hopeless soul who has to figure out why the thing that never dies died.

lefrancaiz• 5 years ago

The sharding project bought us some time regarding database capacity, but as we soon found out, there was a huge single point of failure in our infrastructure. All those shards were still using a single Redis. At one point, the outage of that Redis took down all of Shopify, causing a major disruption we later called “Redismageddon”. This taught us an important lesson to avoid any resources that are shared across all of Shopify.

It seems that it does happen sometimes, however.

https://shopify.engineering/e-commerce-at-scale-inside-shopi...

spullara2• 5 years ago

At Twitter we hit 15s memory allocation pause times due to fragmentation. We had to switch the memory allocator to fix it.

hrpnk2• 5 years ago

Which memory allocator did you end up using?

junon3• 5 years ago

This is strange to me. Did Github do client-based sharding because they were trying to get around the upfront key enumeration limitation in Lua scripts? Why didn't they use the cluster's ability to proxy requests to the appropriate sharded worker?

As-is, they could have just passed `rate_limit_key+':exp'` as a second KEYS entry and it would have ensured the key existed for operation. They were deriving keys off of apriori information, so they could have just as easily foregone the client-side complexity and just put the redis cluster in a sharded configuration.

I wonder what sorts of performance impact this had (the page doesn't mention it). Client-side sharding almost certainly increased the codebase complexity and it doesn't seem like they measured any real impact from doing it this way (or maybe they just chose not to report it).

tlhunter• 5 years ago

I was concerned about the missing KEYS entry, too.

I believe the script would fail if the two keys were on different machines, assuming both key names were provided as KEYS, though the {} syntax should have avoided that. By generating the key name in a Lua script it forces the two related keys to be on the same machine.

At the end of the day, calculating the server client side isn't necessarily messy. Surely the Lua script deserves a warning about the key name being generated within the script.

I think the ideal script would use two keys, the first being like `foo-{1234}`, and the second `foo-{1234}:exp`, with both key names being provided via KEYS. Then the native Redis clustering should work.

junon3• 5 years ago

By generating the key name in a Lua script it forces the two related keys to be on the same machine.

Perhaps I'm misunderstanding what you're saying, but this isn't true. You have to supply ALL keys that you wish to read from in the KEYS array prior to running scripts in a sharded setup, otherwise Redis will fail as it can't lock the map long enough to perform potentially-failing I/O operations to fetch them.

I suppose it could, but it wouldn't make any sense to and would violate a bunch of otherwise strong and useful guarantees.

Surely the Lua script deserves a warning about the key name being generated within the script.

My point is they're able to guarantee the key is present simply because they're using client-side sharding with Redis in replica/sentinel (or even standalone) modes, thus you are free to construct keys within scripts without issue.

Since they're owning the `:exp` key within the script, then the `:exp` keys are guaranteed to be within the same instance.

I think the ideal script would use two keys, the first being like `foo-{1234}`, and the second `foo-{1234}:exp`, with both key names being provided via KEYS. Then the native Redis clustering should work.

This isn't ideal if the `:exp` key causes high colocation misses, causing extra I/O ops for each script execution (since they would have to be fetched prior to the script execution).

Also keep in mind that Redis has multiple clustering modes, so you should specify which you mean.

Lastly, I've never seen `{}` in keys, only `:`, just a nitpick. I don't think there's any benefit there except for extra bytes over the wire, as most people aren't putting un-sanitized user input in Redis keys (I'd hope not).

rattray2• 5 years ago

The article mentions they took some inspiration from a Stripe blogpost/gist; for convenience, here's the direct link to the relevant lua code (helps compare what is interesting/unique about github's approach):

https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff...

(disclaimer, I worked on the rate limiter at Stripe a bit, but can't remember how similar the 2019-era code was to what you see there; I think broadly similar).

rattray2• 5 years ago

Ah, it turns out my former colleagues @brandur, who worked on rate limiting at Stripe for some time after the blog post was written, has a Redis rate-limiting module published here: https://github.com/brandur/redis-cell/

Operyl• 5 years ago

Ah, that’s great! I was just looking down this path the other day for a project I need coming up soon. This’ll save a good days worth of work :).

uyt• 5 years ago

I also found https://cloud.google.com/solutions/rate-limiting-strategies-... to be useful. In particular at the very bottom they link to a lot of other blogs about rate limiting such as: https://www.figma.com/blog/an-alternative-approach-to-rate-l...

I am only reading about them because for whatever reason this has become a trendy "system design" interview question.

hrpnk2• 5 years ago

It's a task that's easy and quick to understand for any engineer in terms of requirements. Also, it offers great depth in terms of approaches, technology selection, and data volumes to be analyzed.

fasteo• 5 years ago

Related: mailgun’s gubernator[1]. No redis.

[1] https://www.mailgun.com/blog/gubernator-cloud-native-distrib...

tayloramurphy• 5 years ago

I originally thought this article was going to be about John Berryman's proposed Redis rate limiter [0]

[0] http://blog.jnbrymn.com/2021/03/18/estimated-average-recent-...

cylde_frog• 5 years ago

Can anyone make a comparison between GCRA and the sliding window algorithm? Why is GCRA superior?

We scaled the GitHub API with a sharded, replicated rate limiter in Redis

Related Stories