https://github.com/satmihir/fair Skip to content Navigation Menu Toggle navigation Sign in * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + GitHub Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions By size + Enterprise + Teams + Startups By industry + Healthcare + Financial services + Manufacturing By use case + CI/CD & Automation + DevOps + DevSecOps * Resources Topics + AI + DevOps + Security + Software Development + View all Explore + Learning Pathways + White papers, Ebooks, Webinars + Customer Stories + Partners * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Enterprise + Enterprise platform AI-powered developer platform Available add-ons + Advanced Security Enterprise-grade security features + GitHub Copilot Enterprise-grade AI features + Premium Support Enterprise-grade 24/7 support * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up Reseting focus You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert {{ message }} satmihir / fair Public * Notifications You must be signed in to change notification settings * Fork 3 * Star 387 A Go library for serving resources fairly License MIT license 387 stars 3 forks Branches Tags Activity Star Notifications You must be signed in to change notification settings * Code * Issues 0 * Pull requests 0 * Actions * Projects 0 * Security * Insights Additional navigation options * Code * Issues * Pull requests * Actions * Projects * Security * Insights satmihir/fair This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. main BranchesTags Go to file Code Folders and files Name Name Last commit Last commit message date Latest commit History 18 Commits .github/workflows .github/ workflows pkg pkg .gitignore .gitignore LICENSE LICENSE README.md README.md eval.png eval.png go.mod go.mod go.sum go.sum View all files Repository files navigation * README * MIT license FAIR Coverage FAIR is a Go library designed to ensure fairness in the resource-constrained environments. It helps distribute the limited resources (e.g., database/blob storage throughput, job execution resources etc.) evenly across multiple clients during the time of shortage, preventing over-allocation and starvation based on client behavior. Introduction The core algorithm of FAIR is based on the Stochastic Fair BLUE often used for network congestion control with a few modifications. The philosophy of FAIR is to only throttle when there's a genuine shortage of resources as opposed to the approaches like token bucket or leaky bucket which may reject requests even when the resource is still available (a creative configuration of FAIR can enable that type of behavior but we don't encourage it). 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. When properly configured, FAIR can scale to a very large number of clients with a low probability of false positives and a near zero probability of persistent false positives thanks to the hash rotation mechanism that regularly rehashes clients to avoid any correlated behavior longer than a few minutes. Key Features * Framework and protocol agnostic and easy to integrate into any HTTP/GRPC service. * Automatic tuning with minimal configuration out of the box with flexibility to fully tune if needed. * Scalable to large numbers of clients with constant memory requirements. * A simple resource and error tracking model that can be easily morphed into many types of throttling scenarios. Evaluation Evaluation In this example, 20 clients are competing for a resource that regenerates at the rate of 20/s (every data point in the graph is 5s apart). 18 out of 20 clients are "well behaved" because they request a resource every second while the remaining two clients try to get a resource every 100ms which is an "unfair" rate. On the left, we see that when left unthrottled, the two unfair clients grab a disproportionately large amount of resource while the regular workloads starve and get a lot less than 1/s rate. On the right, when throttled with fair, the regular workloads stay virtually unaffected while the unfair ones get throttled. On average, even the unfair workloads get their fair share when seen over larger time periods. Installation To install the FAIR library, use go get: go get github.com/satmihir/fair Then, import it into your Go code: import "github.com/satmihir/fair" Usage To use the default config which should work well is most cases: trkB := NewFairnessTrackerBuilder() trk, err := trkB.BuildWithDefaultConfig() defer trk.Close() If you want to make some changes to the config, you can use the setters on the builder: trkB := NewFairnessTrackerBuilder() // Rotate the underlying hashes every one minute to avoid correlated false positives trkB.SetRotationFrequency(1 * time.Minute) trk, err := trkB.Build() defer trk.Close() For every incoming request, you have to pass the flow identifier (the id over which you want to maintain fairness) into the tracket to see if it needs to be throttled. A client ID for example could be such ID to maintain resource fairness among all your clients. ctx := context.Background() id := []byte("client_id") resp, _ := trk.RegisterRequest(ctx, id) if resp.ShouldThrottle { throttleRequest() } For any failure that indicates a shortage of resource (which is our trigger to start throttling), you report outcome as a failure. For any other outcomes that are considered failures in your business logic that don't indicate resource shortage, do not report any outcome. ctx := context.Background() id := []byte("client_id") trk.ReportOutcome(ctx, id, request.OutcomeFailure) On the other hand, when you are able to get the resource, you report success. ctx := context.Background() id := []byte("client_id") trk.ReportOutcome(ctx, id, request.OutcomeSuccess) Tuning You can use the GenerateTunedStructureConfig to tune the tracker without directly touching the algorithm parameters. It exposes a simple interface where you have to pass the following things based on your application logic and scaling requirements. * expectedClientFlows - Number of concurrent clients you expect to your app * bucketsPerLevel - Number of buckets per level in the core structure * tolerableBadRequestsPerBadFlow - Number of requests we can tolerate before we fully shut down a flow conf := config.GenerateTunedStructureConfig(1000, 1000, 25) trkB := NewFairnessTrackerBuilder() trk, err := trkB.BuildWithConfig(config) defer trk.Close() About A Go library for serving resources fairly Topics distributed-systems throttling fairness go-library Resources Readme License MIT license Activity Stars 387 stars Watchers 3 watching Forks 3 forks Report repository Releases No releases published Packages 0 No packages published Contributors 3 * @satmihir satmihir Mihir Sathe * @actions-user actions-user * @mihir-sathe mihir-sathe Languages * Go 100.0% Footer (c) 2024 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact * Manage cookies * Do not share my personal information You can't perform that action at this time.