J-HowHuang opened a new pull request, #19386:
URL: https://github.com/apache/pinot/pull/19386
## Description
Low disk mode today in table rebalance only guarantees that within a
segment, the replica to offload will be done first, then the replica to add.
The scope is limited to a segment, not server. However, when servers have
limited disk space, we want to further guarantee that at any step, a server
won't load more bytes than they initially did if a server is to net lose some
bytes, or a server won't load more bytes than it would eventually load if it's
to net gain some bytes.
Current implementation won't give this guarantee (see example), and we need
this guarantee to avoid jamming disk spaces. Also when the disk is already
jammed such that no segments can be added to it, we need this guarantee to
rebalance our way out without segments getting into error state due to no disk
space.
## Example of the current implementation
```
3 servers → 3 servers with 2 in the overlap, replication 2, 6 segments,
minAvailableReplicas=1:
segment start step 1 step 2 step 3 step 4 = target
s0 A,B B B,C B,C B,C
s1 A,C C C,D D B,D
s2 B,C C C,D C,D C,D
s3 A,B B B,C B,C B,C
s4 A,C C C,D D B,D
s5 B,C C C,D C,D C,D
segments hosted
A 4 0 0 0 0
B 4 2 2 2 4
C 4 4 → 6 ← 4 4
D 0 0 4 4 4
```
## New design and new constraint
Scope: we only change how we derive the next step, i.e. the result returned
by `getNextAssignment`. Nothing change in deriving target assignment, only the
intermediate steps. Also, for `lowDiskMode=false` the algorithm is the same.
The illustration here are shown the segment count, but this PR generalize it
to segment bytes.
### DiskUsageBudget
We compute the budget of each server on how many bytes of segments they can
load at most at the beginning of the rebalance.
The idea is that each server won't load more bytes than they initially did
if a server is to net lose some bytes, or won't load more bytes than it would
eventually load if it's to net gain some bytes.
### StepDiskBudget
Compute for each step. This tells you how many bytes you can still take
based on the current assignment, respect to the DiskUsageBudget we initially
fixed on.
### computeNextAssignment
It will only change the segment's assignment if it fits the
`StepDiskBudget`. Reject the new assignment if it violates, so the segment stay
at its places for this step. In the case of strict replica group, the cost is
computed on the entire replica group since they'll be moved together.
For this mechanism, most of the cases should be able to resolve a sequence
that fits the `DiskUsageBudget` constraint entirely. The above example would
become this:
```
segment start step 1 step 2 step 3 step 4 = target
s0 A,B B B B B,C
s1 A,C C C,D D B,D
s2 B,C C C,D C,D C,D
s3 A,B B B B B,C
s4 A,C C C,D D B,D
s5 B,C C C,D C,D C,D
segments hosted
A 4 0 0 0 0
B 4 2 2 2 4
C 4 4 → 4 ← 2 4
D 0 0 4 4 4
```
### Precheck
No guarantee that such sequence is resolvable under the any algorithm,
though. If next assignment couldn't be obtained under the constraint, it will
fall back to the original low disk mode implementation.
Therefore we have a pre-check to tell if the rebalance will violate this
constraint (since the sequence resolution is deterministic, we can verify that
during pre-check).
```
"preChecksResult": {
"diskUtilization": {
"preCheckStatus": "ERROR",
"message": "UNSAFE. Servers with unsafe disk utilization DURING
rebalance (>=50%): Server_1 (52%). lowDiskMode cannot avoid it for this target
assignment: the rebalance cannot make
progress without going over the disk these servers start with, by up to
Server_1 (150B). Rebalance to a target assignment that frees up space on them
first, or add capacity"
}
}
```
It names the server, how far over it would go, and two concrete remedies.
The case it replaces
Before this PR, that same situation returned PASS, because the check
assumed lowDiskMode always removed the transient usage:
```
{
"preCheckStatus": "PASS",
"message": "Within threshold (<50%) AFTER rebalance. Servers that would
go over it DURING the rebalance: Server_1 (52%). lowDiskMode avoids that
transient disk usage by deleting segments
before adding the new ones"
}
```
That message is still returned — but now only when the replay confirms the
budget actually holds, rather than being asserted unconditionally.
The other outcomes on this path, unchanged
```
PASS Within threshold (<50%)
```
```
ERROR UNSAFE. Servers with unsafe disk utilization AFTER rebalance
(>=50%): Server_1 (52%)
```
```
ERROR UNSAFE. Servers with unsafe disk utilization DURING rebalance
(>=50%): Server_1 (52%).
Enable lowDiskMode to delete segments before adding the new ones
```
### In case of mid-flight uploaded segments
When a new segment appear in ideal state by external sources (e.g. segment
upload, consuming segment committed), there are two cases:
1. They are added to the ideal state as the target assignment. This case the
rebalance steps outcome won't change
2. They are added to the ideal state that's different to their target
assignments. For example when strict replica routing is in place. This case, it
might lead to a different computeNextAssignment result.
Every step we check if there are new segments added into the ideal state
that's not seen in the beginning, account for their bytes as if they were in
the ideal state when we computed the `DiskUsageBudget`.
Notice that we don't guarantee the disk would be in the safe shape if the
segments are added mid-flight because pre-check won't see that. But we'll still
move the segments so that no servers would bare additional bytes.
## Testing
`LowDiskModeRebalanceSimulatorTest` drives the real
TableRebalancer.getNextAssignment in a loop, exactly as doRebalance does,
tracking every server's bytes at each step — so it exercises
production code, not a re-implementation. Three properties are asserted
over 21 fixed scenarios:
1. the rebalance always reaches the target assignment;
2. no server exceeds max(bytes it held that this rebalance did not place,
bytes the target places on it), unless the disk-utilization pre-check names it
up front;
3. under strict replica group routing, segments of a partition are never
assigned different instances.
Scenarios cover balanced and replica-group assignment, both routing modes,
batchSizePerServer, skewed segment sizes, segments uploaded mid-rebalance, and
the two assignments a randomized
search found hardest. main() additionally runs ~32k randomized scenarios
for comparing effectiveness by hand; those are not tests.
Constraint violations, before and after
```
┌─────────────────────────────────────┬────────────────────────────────────────┬───────┐
│ corpus │ before
│ after │
├─────────────────────────────────────┼────────────────────────────────────────┼───────┤
│ old/new server sets, 648 │ 120 over-allocate (18.5%), worst
2.00× │ 0 │
├─────────────────────────────────────┼────────────────────────────────────────┼───────┤
│ strict replica group, 324 │ 92 over-allocate (28.4%), worst
1.78× │ 0 │
├─────────────────────────────────────┼────────────────────────────────────────┼───────┤
│ random non-uniform assignments, 400 │ 47 over-allocate (11.8%), worst
2.00× │ 0 │
└─────────────────────────────────────┴────────────────────────────────────────┴───────┘
```
Post-change the wider sweeps — 1,944 server-set shapes and 30,000 random
group structures — also report zero. Mean step count moves 3.4 → 3.5, so the
bound costs essentially nothing.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
