apple / apple/foundationdb

Better documentation and testing of the load balancing algorithm

Open
#3,851 0 comments 1 reaction 0 assignees View on GitHub
Dominant language
C++
Stars
16.7k
Forks
1.6k
Avg merge
1d 20h
Merged PRs (30d)
126

Description

As I commented at https://github.com/apple/foundationdb/pull/3845, the load balancing algorithm seems very sophisticated and complex. I don't think I completely understand how it works. (If anyone else beside Evan has a better idea, I'm very happy to talk with him/her.)

Documentation and better focused testing on load balancing algorithm will help reduce potential load balancing problems in prod in the future.

**[Documentation]**
How the load balancing algorithm works?
Some questions on the algorithm are:
(a) what the balancing goal is? Is it making every proxy have similar amount of requests or run at the similar amount of cpu utilization?
(b) what metrics are collected from proxies?
(c) how to use the collected proxy metrics to decide which proxy should get the next request?

Having a doc on the algorithm will also help people to identify if there is any corner cases that may break the algorithm.
**For example**, if a proxy has long network latency to the master role, each request on it will have higher latency. The proxy will process less requests compared to others and its CPU utilization will also be lower. If the load balancing algorithm tries to balance the number of requests or the cpu utilization among proxies, it will direct more requests to the problematic proxy and cause the cluster to have longer latency.

**[Testing]**
Is it possible to add a "test" that only tests the correctness of the load balancing algorithm?
For example, the test can create multiple proxies and simulates load on these proxies. The test then uses a client to send request to these proxies via the basicLoadBalance(..) actor. The test can check if proxies' load is well balanced after each request.

With the tests and documentation, we can be more confident on the load balancing algorithm.

Contributor guide

Open the contributing guide

Research direction

Start by tracing the basicLoadBalance(..) actor and reading the load-balancing discussion in PR #3845. Document the balancing goal, collected proxy metrics, and request-selection process, then define focused tests that exercise correctness under simulated proxy load. Done means the algorithm is explainable and its expected balancing behavior is covered by tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, distributed-systems, testing
Issue type
Documentation
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.