8 ms·

Fair: A Go library for serving resources fairly

213 points by ngaut 2y ago

nstateful 2y ago
Very interesting and looking forward to trying this. I am a big fan of SFB for this type of stuff but haven't seen anything in distributed space that's beyond a science project. Would be great if I can use it on my 10k+ user web site.
AnnaMere 2y ago
Extremely interesting and valuable
tazu 2y ago
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.
- codaphiliac 2y ago
  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.)
  - jawns 2y ago
    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.
    - codaphiliac 2y ago
      defining a unit of processing like duration or quantity and then feeding the algorithm with the equivalent of units consumed (pre or post processing a request) might help.
    - dtjohnnymonkey 2y ago
      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.
      - hinkley 2y ago
        I believe nginx+ has a feature that does max-conns by IP address. It’s a similar solution to what you describe. Of course that falls down wrt fairness when fanout causes the cost of a request to not be proportional to the response time.
    - hinkley 2y ago
      Lots of heuristics continue to work pretty well as long as the least and greatest are within an order of magnitude of each other. It’s one of the reasons why we break stories down to 1-10 business days. Anything bigger and the statistical characteristics begin to break down. That said, it’s quite easy for a big job to exceed 50x the cost of the smallest job.
- mnadkvlb 2y ago
  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.
- otterley 2y ago
  Rate limiters are used to protect servers from overload and to prevent attackers--or even legitimate but unintentionally greedy tenants--from starving other tenants of resources. They are a key component of a resilient distributed system. See, e.g., https://docs.aws.amazon.com/wellarchitected/latest/framework/rel_mitigate_interaction_failure_throttle_requests.html https://docs.aws.amazon.com/wellarchitected/latest/framework... This project, however, looks like a concurrency limiter, not a rate limiter. I'm also not sure how it works across a load-balanced cluster.
- itake 2y ago
  The text suggests a method for managing GPU or rate-limited resources across multiple clients. It highlights the problem of spikey workloads, where a client might generate a large number of events (e.g., from a CSV upload) causing resource starvation. The text advises against using naive solutions like FIFO, which could disadvantage clients with steady live traffic.
salomonk_mur 2y ago
Why would you learn and use this over typical load-balancing solutions like K8S? Honest question.
- joshuanapoli 2y ago
  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.
  - dpatterbee 2y ago
    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) https://en.m.wikipedia.org/wiki/BEAM_(Erlang_virtual_machine...
    - maxmcd 2y ago
      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.
    - jerf 2y ago
      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).
ignoramous 2y ago
> 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.
- mnadkvlb 2y ago
  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 https://www.csg.uzh.ch/publications/details.php?id=1007
- remram 2y ago
  I'm not exactly sure what you propose, a token bucket per client? In a hashmap client=>bucket?
  - otterley 2y ago
    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.
    - hinkley 2y ago
      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.
waqasloper 2y ago
[flagged]
roboben 2y ago
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?
- ahoka 2y ago
  Multiple queues?
alegonza212 2y ago
[flagged]
JensRantil 2y ago
I coded up something like Fair a couple 1-2 years ago: https://github.com/JensRantil/conc https://github.com/JensRantil/conc It's alpha software, but maybe interesting to someone don't know.

213 points by ngaut 2y ago

Very interesting and looking forward to trying this. I am a big fan of SFB for this type of stuff but haven't seen anything in distributed space that's beyond a science project. Would be great if I can use it on my 10k+ user web site.

AnnaMere 2y ago

Extremely interesting and valuable

tazu 2y ago

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.

codaphiliac 2y ago
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.)
- jawns 2y ago
  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.
  - codaphiliac 2y ago
    defining a unit of processing like duration or quantity and then feeding the algorithm with the equivalent of units consumed (pre or post processing a request) might help.
  - dtjohnnymonkey 2y ago
    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.
    - hinkley 2y ago
      I believe nginx+ has a feature that does max-conns by IP address. It’s a similar solution to what you describe. Of course that falls down wrt fairness when fanout causes the cost of a request to not be proportional to the response time.
  - hinkley 2y ago
    Lots of heuristics continue to work pretty well as long as the least and greatest are within an order of magnitude of each other. It’s one of the reasons why we break stories down to 1-10 business days. Anything bigger and the statistical characteristics begin to break down. That said, it’s quite easy for a big job to exceed 50x the cost of the smallest job.
mnadkvlb 2y ago
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.
otterley 2y ago
Rate limiters are used to protect servers from overload and to prevent attackers--or even legitimate but unintentionally greedy tenants--from starving other tenants of resources. They are a key component of a resilient distributed system. See, e.g., https://docs.aws.amazon.com/wellarchitected/latest/framework/rel_mitigate_interaction_failure_throttle_requests.html https://docs.aws.amazon.com/wellarchitected/latest/framework... This project, however, looks like a concurrency limiter, not a rate limiter. I'm also not sure how it works across a load-balanced cluster.
itake 2y ago
The text suggests a method for managing GPU or rate-limited resources across multiple clients. It highlights the problem of spikey workloads, where a client might generate a large number of events (e.g., from a CSV upload) causing resource starvation. The text advises against using naive solutions like FIFO, which could disadvantage clients with steady live traffic.

salomonk_mur 2y ago

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

joshuanapoli 2y ago
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.
- dpatterbee 2y ago
  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) https://en.m.wikipedia.org/wiki/BEAM_(Erlang_virtual_machine...
  - maxmcd 2y ago
    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.
  - jerf 2y ago
    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).

ignoramous 2y ago

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

mnadkvlb 2y ago
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 https://www.csg.uzh.ch/publications/details.php?id=1007
remram 2y ago
I'm not exactly sure what you propose, a token bucket per client? In a hashmap client=>bucket?
- otterley 2y ago
  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.
  - hinkley 2y ago
    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.

waqasloper 2y ago

[flagged]

roboben 2y ago

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?

ahoka 2y ago
Multiple queues?

alegonza212 2y ago

[flagged]

JensRantil 2y ago

I coded up something like Fair a couple 1-2 years ago: https://github.com/JensRantil/conc https://github.com/JensRantil/conc It's alpha software, but maybe interesting to someone don't know.