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

11–20 of 44 posts

Re: Fair: A Go library for serving resources fairly

#11

Post by mnadkvlb »

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.

Absolutely my thought as well. During my thesis i found token buckets to be better and more fair compared to other algos[1]. This was in libvirt. my finding was that it scaled well up to around 1k buckets if memory serves right. after that the results were weird to say the least. (of course the servers i tested on were quite old with not too much memory). Would be nice to run my thesis tests again to find what happened in the last decade.

I tried writing another algorithm for network splitting but didn't get any better results. [1]: https://www.csg.uzh.ch/publications/details.php?id=1007

Re: Fair: A Go library for serving resources fairly

#12

Post by mnadkvlb »

tazu wrote: post #4

Does anyone have some real-world use cases for something like this? The algorithm is cool but I'm struggling to see where this is applicable.

I responded above, but it could be used maybe for network libraries for eg. libvirt. I did my thesis on this topic a couple years ago.

I am very intrigued to find out how this would fit in, if at all.

Re: Fair: A Go library for serving resources fairly

#13

Post by dpatterbee »

joshuanapoli wrote: post #9
salomonk_mur wrote: post #5

Why would you learn and use this over typical load-balancing solutions like K8S? Honest question.

In a multi-tenant system, you might have one customer who drops a big job that creates a huge number of tasks. We'd like to process this as fast as possible, but not block the tasks of small jobs from other customers, which should normally be completed very quickly.

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...

Re: Fair: A Go library for serving resources fairly

#15

Post by remram »

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.

I'm not exactly sure what you propose, a token bucket per client? In a hashmap client=>bucket?

Re: Fair: A Go library for serving resources fairly

#16

Post by remram »

salomonk_mur wrote: post #5

Why would you learn and use this over typical load-balancing solutions like K8S? Honest question.

Those are completely unrelated. K8s does not provide client rate-control and FAIR does not do load-balancing. It appears you misunderstood what this is.

Re: Fair: A Go library for serving resources fairly

#17

Post by maxmcd »

dpatterbee wrote: post #13
joshuanapoli wrote: post #9

Earlier quoted context omitted.

In a multi-tenant system, you might have one customer who drops a big job that creates a huge number of tasks. We'd like to process this as fast as possible, but not block the tasks of small jobs from other customers, which should normally be completed very quickly.

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...

In preemptive multitasking you are trying to get all the work done as quickly as possible, but with FAIR and similar systems you want to make sure that a single client/user/resource cannot steal an inordinate amount of capacity.

I do not think languages/runtimes typically implement that kind of prioritization/limiting mechanism.

Re: Fair: A Go library for serving resources fairly

#18

Post by jerf »

dpatterbee wrote: post #13
joshuanapoli wrote: post #9

Earlier quoted context omitted.

In a multi-tenant system, you might have one customer who drops a big job that creates a huge number of tasks. We'd like to process this as fast as possible, but not block the tasks of small jobs from other customers, which should normally be completed very quickly.

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 our intuition generally can work with. The pathological distribution of the size of various workloads and the pathological distribution of the variety of resources that tasks can consume is not modeled well by our human brains, who really want to work with tasks that are essentially uniform. But they never are. A lot of systems end up punting, either to the OS which has to deal with this anyhow, or to letting programs do their own cooperative internal scheduling, which is what this library implements. In general "but what if I 'just'" solutions to this problem have undesirable pathological edge cases that seem like they "ought" to work, especially at the full generality of an operation system. See also the surprisingly difficult task of OOM-killing the "correct" process; the "well obviously you 'just'" algorithms don't work in the real world, for a very similar reason.

As computers have gotten larger, the pathological distributions have gotten worse. To be honest, if you're thinking of using "fair" it is likely you're better off working on the ability to scale resources instead. There's a niche for this sort of library, but it is constantly shrinking relative to the totality of computing tasks we want to perform (even though it is growing in absolute terms).

Re: Fair: A Go library for serving resources fairly

#19

Post by otterley »

remram wrote: post #15
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.

I'm not exactly sure what you propose, a token bucket per client? In a hashmap client=>bucket?

That's the typical design for a token-bucket rate limiter. A token-bucket limiter uses more memory but is a simpler design. I believe this bloom-filter based implementation is designed to be more memory efficient at the cost being less CPU efficient.

As usual, tradeoffs are everywhere.

Re: Fair: A Go library for serving resources fairly

#20

Post by dtjohnnymonkey »

jawns wrote: post #8
codaphiliac wrote: post #7

Earlier quoted context omitted.

Thinking this could be useful in a multi tenants service where you need to fairly allocate job processing capacity across tenants to a number of background workers (like data export api requests, encoding requests etc.)

That was my first thought as well. However, in a lot of real world cases, what matters is not the frequency of requests, but the duration of the jobs. For instance, one client might request a job that takes minutes or hours to complete, while another may only have requests that take a couple of seconds to complete. I don't think this library handles such cases.

To mitigate this case you could limit capacity in terms of concurrency instead of request rate. Basically it would be like a fairly-acquired semaphore.
Post reply on HN