Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fair: A Go library for serving resources fairly

github.com

Post reply on HN
Print view View original

31–40 of 44 posts

Re: Fair: A Go library for serving resources fairly

#31

Post by otterley »

foobazgt wrote: post #30
otterley wrote: post #29

Earlier quoted context omitted.

That would work if you can assign requests from a given tenant to a single instance, but there are many situations in which that's either impossible or unwise. What if a single server doesn't have enough capacity to handle all the traffic for a tenant? How do you preserve the state if that instance fails?

I'm sorry, I don't think I understand your question. Are you talking about the KVS? You shard the servers for extra capacity. Several KVS's have built-in clustering if you want to go that route. They're usually incredibly stable, but if one goes down for whatever reason (say the physical machine fails), you just spin another one up to take its place. In terms of preserving state, the answer for rate limiting is that…

I think I misunderstood what you were saying. By "in-memory KVS" with "access times in the microseconds" I thought you were implying a KVS hosted on the server that handles the requests. Otherwise, even if the KVS can respond in 100us to a local query, network latency is going to add much more than that.

Re: Fair: A Go library for serving resources fairly

#32

Post by foobazgt »

otterley wrote: post #31
foobazgt wrote: post #30

Earlier quoted context omitted.

I'm sorry, I don't think I understand your question. Are you talking about the KVS? You shard the servers for extra capacity. Several KVS's have built-in clustering if you want to go that route. They're usually incredibly stable, but if one goes down for whatever reason (say the physical machine fails), you just spin another one up to take its place. In terms of preserving state, the answer for rate limiting is that…

I think I misunderstood what you were saying. By "in-memory KVS" with "access times in the microseconds" I thought you were implying a KVS hosted on the server that handles the requests. Otherwise, even if the KVS can respond in 100us to a local query, network latency is going to add much more than that.

Ah ok, that makes sense. Over loopback, you can roundtrip Redis at least as fast as double-digit micros. Intra-DC, your network latency should be somewhere in the triple-digit micros. I'd say if you're not seeing that, something is probably wrong.

Re: Fair: A Go library for serving resources fairly

#33

Post by hinkley »

otterley wrote: post #25
hinkley wrote: post #22

Earlier quoted context omitted.

Bloom filters really shine when they avoid a network round trip or pulling data from disk. Those are so far away you can easily afford to spend 5% of the cost of the request to avoid 99% of the requests.

Agreed! In a typical token bucket implementation, bucket state must be shared across multiple servers, which means you need a shared state repository such as Redis or a database (SQL or noSQL). This can add milliseconds to each request being handled.

> This can add milliseconds

My previous (very long) project was in such a state when I got there that it was only in the last year I was there that measuring things in microseconds was something I could get on other people's radars. I wish I had started sooner because I found a lot of microseconds in about a four month period. That was the most intensive period of user-visible latency reduction I saw the entire time it was there and second through fourth place took years of manpower to accomplish. Past me and future me are both still mad about that.

Re: Fair: A Go library for serving resources fairly

#34

Post by hinkley »

otterley wrote: post #29
foobazgt wrote: post #28

Earlier quoted context omitted.

Rate limiters seem like the poster child for something you'd want to host in an in-memory KVS. Typical access times look more like ~100us, not milliseconds. Even if you have a complicated algorithm, you can still limit it to a single round trip by using a Redis Function or some moral equivalent.

That would work if you can assign requests from a given tenant to a single instance, but there are many situations in which that's either impossible or unwise. What if a single server doesn't have enough capacity to handle all the traffic for a tenant? How do you preserve the state if that instance fails?

I don't recall all the details but we did end up with lua to talk to redis or memcached to do some traffic shaping at one point. One for bouncing to error pages before we switched to CDN (long story), and another one for doing something too clever by half about TTFB. It's still really cheap especially on a box that is just doing load balancing and nothing else.

If you wanted to throw another layer of load balancer in, there are consistent hashing-adjacent strategies in nginx+ that would allow you to go from 2 ingress routers to 3 shards with rate limiters to your services, using one KV store per box. But I highly suspect that the latency profile there will look remarkably similar to ingress routers doing rate limiting talking to a KV store cluster.

Re: Fair: A Go library for serving resources fairly

#35

Post by udkl »

jerf wrote: post #18
dpatterbee wrote: post #13

Earlier quoted context omitted.

Isn't the exactly the problem that preemptive multitasking is built for? For example any program built on the BEAM[1] wouldn't have this problem presumably. Do most languages not have a standard solution for this? [1]: https://en.m.wikipedia.org/wiki/BEAM_(Erlang_virtual_machine...

Pre-emptive multitasking is a tool that a solution might use, but it is not a solution on its own. If you have three users spawning one thread/process/task and one user spawning a million (literally, not figuratively), that one user can easily completely starve the three little users. Some of their million tasks may also be starved. But they'll get more done overall. This whole problem gets way more complicated than…

Appreciate this very insightful comment

Re: Fair: A Go library for serving resources fairly

#36

Post by roboben »

Shouldn’t this be built into a queue somehow? I’d love to see a queuing solution like SQS but has a built in fairness, where you can fully utilize a capacity but as soon as, let’s say customers compete on resources, some fairness kicks in. Is there anything like that?

Re: Fair: A Go library for serving resources fairly

#37

Post by jrockway »

foobazgt wrote: post #28
otterley wrote: post #25

Earlier quoted context omitted.

Agreed! In a typical token bucket implementation, bucket state must be shared across multiple servers, which means you need a shared state repository such as Redis or a database (SQL or noSQL). This can add milliseconds to each request being handled.

Rate limiters seem like the poster child for something you'd want to host in an in-memory KVS. Typical access times look more like ~100us, not milliseconds. Even if you have a complicated algorithm, you can still limit it to a single round trip by using a Redis Function or some moral equivalent.

You can also rate limit on the server side. Service A talks to Service B. Service B is 3 replicas. Each replica keeps track of how many times Service A talked to it. If that goes over the limit / 3, deny the request. Now there is no IPC required.

This isn't as accurate, but it's often adequate. I have never liked making a network request to see if I can make a network request; too slow. (I do use this architecture to rate-limit my own website, mostly because I wanted to play with writing a service to do that. But I'd hesitate to make someone else use that.)

Re: Fair: A Go library for serving resources fairly

#39

Post by dpatterbee »

jerf wrote: post #18
dpatterbee wrote: post #13

Earlier quoted context omitted.

Isn't the exactly the problem that preemptive multitasking is built for? For example any program built on the BEAM[1] wouldn't have this problem presumably. Do most languages not have a standard solution for this? [1]: https://en.m.wikipedia.org/wiki/BEAM_(Erlang_virtual_machine...

Pre-emptive multitasking is a tool that a solution might use, but it is not a solution on its own. If you have three users spawning one thread/process/task and one user spawning a million (literally, not figuratively), that one user can easily completely starve the three little users. Some of their million tasks may also be starved. But they'll get more done overall. This whole problem gets way more complicated than…

Thank you for the explanation, I hadn't clocked the difference between fair allocation for tasks and fair allocation for users.

Re: Fair: A Go library for serving resources fairly

#40

Post by JensRantil »

ignoramous wrote: post #6

> Since the state is stored in a multi-level Bloom Filter style data structure, the memory needed is constant and does not scale with the number of clients. Constant memory, but those hashes will take up CPU cycles. If you're running a workload that completes sub 20 milliseconds, these cycles spent hashing may not be worth it over, say, a constant-time admission control like token bucket.

The world is full of trade-offs. I don't think the author intended to solve CPU-bound workloads like that. Or have they claimed that?
Post reply on HN