Repository navigation
Commit 76bd6f0
[fix](rle) Fix infinite loop when a repeated run reaches 2^30 values (#69100)
### What problem does this PR solve?
Problem Summary:
`RleEncoder::FlushRepeatedRun()` wrote `repeat_count_ << 1` into an
`int32_t`. `repeat_count_` was an `int`, so a repeated run of 2^30 or
more values overflowed the indicator into a negative number.
`BitWriter::PutVlqInt()` then took that as an `int32_t` and shifted it
right arithmetically:
```cpp
inline void BitWriter::PutVlqInt(int32_t v) {
while ((v & 0xFFFFFF80) != 0L) {
PutAligned<uint8_t>((v & 0x7F) | 0x80, 1);
v >>= 7;
}
PutAligned<uint8_t>(v & 0x7F, 1);
}
```
An arithmetic right shift of a negative value converges to `-1` and
stays there, and `-1 & 0xFFFFFF80` is non-zero, so **the loop never
exits**. It appends `0xFF` to the output buffer forever, pinning a core
at 100% and growing the buffer without bound.
#### How it was hit
A base compaction in a production cluster wedged on a table with many
nullable `text` columns. Two `BaseCompactionT` threads sat in this stack
for over a month:
```
#0 inline_memcpy (size=348057208)
#2 doris::faststring::GrowArray (newcapacity=502825728)
#4 doris::BitWriter::GetNextBytePtr (num_bytes=1)
#5 doris::BitWriter::PutAligned<unsigned char> (val=255 '\377')
#6 doris::BitWriter::PutVlqInt (v=-1) bit_stream_utils.inline.h:91
#7 doris::RleEncoder<bool>::FlushRepeatedRun rle_encoding.h:499
#9 doris::segment_v2::NullBitmapBuilder::finish
#11 doris::segment_v2::ScalarColumnWriter::finish
#15 doris::Merger::vertical_compact_one_group (is_key=false, max_rows_per_segment=1073741824)
#20 doris::CloudBaseCompaction::execute_compact
```
`v=-1` together with `val=255` pins it down exactly: the loop is
emitting `0xFF` with `v` stuck at `-1`.
Two existing behaviours combined to produce a 2^30-value run:
- Vertical compaction derives the segment row limit from
`vertical_compaction_max_segment_size / avg_bytes_per_row`
([`Compaction::get_avg_segment_rows()`](https://github.com/apache/doris/blob/master/be/src/olap/compaction.cpp)).
For this table the average row size integer-divided to `0`, so the
divisor degenerated to `1` and the limit became the config default
`1073741824` = 2^30 rows — visible as `max_rows_per_segment=1073741824`
in the stack above.
- `ScalarColumnWriter::append_nulls()` never checks whether the page is
full, unlike `append_data()`, and NULLs never reach the page builder. So
an all-NULL column accumulated a single null-bitmap run spanning the
whole 2^30-row segment in one page.
Because the stuck tasks kept the base compaction slots occupied
(`max_base_compaction_task_num_per_disk` defaults to 2),
`_generate_cloud_compaction_tasks()` computed `base_n = 0` and stopped
picking any tablet, so **no base compaction ran on that backend again**
and compaction scores climbed to the cap across the instance.
### What this PR changes
1. **`PutVlqInt()` takes `uint32_t`.** A logical shift always converges
to 0, so the loop terminates for every possible input. This is the
backstop that makes a hang impossible regardless of what callers pass.
2. **`repeat_count_` widened to `int64_t`, and long runs are split.**
Runs longer than `MAX_VALUES_PER_REPEATED_RUN` (2^30 - 1) are emitted as
several back-to-back repeated runs of the same value. Readers already
merge adjacent runs carrying the same value (`RleDecoder::GetNextRun`),
so splitting is invisible to them. The cap keeps the indicator inside
`int32_t`'s positive range — exactly the range previous versions could
encode — so **output stays byte-identical for every run length that used
to work**, and no reader change is needed.
3. **`faststring::reserve()` grows geometrically** via the existing
`GrowToAtLeast()` instead of reallocating to exactly the requested
capacity. `BitWriter` reserves a handful of bytes at a time, so exact
growth reallocated and memcpy'd the entire buffer every 8 bytes, making
an n-byte append cost O(n^2). This is what turned the infinite loop into
a thread stuck in `memcpy` with a ~500MB buffer, and it slows down every
other large RLE buffer as well. Measured: reaching 1 MiB now takes 26
reallocations instead of ~131,000.
Deliberately **not** in this PR, each worth its own change:
- `ScalarColumnWriter::append_nulls()` still lets a page grow without
bound.
- `Compaction::get_avg_segment_rows()` still degenerates to the
configured byte size when the average row size rounds down to zero.
### Release note
Fix a BE hang in RLE encoding when a column produces a run of 2^30 or
more identical values (for example an all-NULL column in a very large
segment), which could permanently stall base compaction on that backend.
### Check List (For Author)
- Test
- [x] Unit Test
New tests:
| Test | Covers |
|---|---|
| `TestRle.TestRepeatedRunExceedingIndicatorRange` | Run lengths around
and far beyond 2^30 encode compactly and decode back to the original
length |
| `TestBitStreamUtil.TestPutVlqIntRoundTrip` | `PutVlqInt` round-trips
every `uint32_t`, including values `>= 2^31` that used to hang |
| `FaststringTest.TestReserve_ExponentiallyExpand` | `reserve()` does
not reallocate on every call |
Verified that the new tests actually catch the bug: built the exact
repro (`RleEncoder<bool>::Put(true, 1 << 30)` followed by `Flush()`)
against unpatched master and it never returns (killed by timeout); with
this patch it completes and emits 8 bytes. All pre-existing tests in
`rle_encoding_test`, `bit_stream_utils_test` and `faststring_test` pass
(29 tests, with `LOOP_LESS_OR_MORE` forced to the slow/thorough branch).
Also confirmed no format regression: a short run encoded via `Put(v)` in
a loop and via `Put(v, n)` in one call still produce byte-identical
output.
- Behavior changed:
- [x] No. Encoded output is unchanged for every run length that
previously encoded correctly; only run lengths that used to hang now
produce (correct, readable) output.
- Does this need documentation?
- [x] No.
Co-authored-by: Xin Liao <[email protected]>1 parent e9b3373 commit 76bd6f0
7 files changed
Lines changed: 139 additions & 13 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
59 | 59 | | |
60 | 60 | | |
61 | 61 | | |
62 | | - | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
63 | 65 | | |
64 | 66 | | |
65 | 67 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
85 | 85 | | |
86 | 86 | | |
87 | 87 | | |
88 | | - | |
89 | | - | |
90 | | - | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
91 | 91 | | |
92 | 92 | | |
93 | | - | |
| 93 | + | |
94 | 94 | | |
95 | 95 | | |
96 | 96 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
106 | 106 | | |
107 | 107 | | |
108 | 108 | | |
109 | | - | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
110 | 113 | | |
111 | 114 | | |
112 | 115 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
18 | 18 | | |
19 | 19 | | |
20 | 20 | | |
| 21 | + | |
| 22 | + | |
21 | 23 | | |
22 | 24 | | |
23 | 25 | | |
| |||
156 | 158 | | |
157 | 159 | | |
158 | 160 | | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
159 | 171 | | |
160 | 172 | | |
161 | 173 | | |
| |||
212 | 224 | | |
213 | 225 | | |
214 | 226 | | |
215 | | - | |
| 227 | + | |
216 | 228 | | |
217 | 229 | | |
218 | 230 | | |
| |||
437 | 449 | | |
438 | 450 | | |
439 | 451 | | |
440 | | - | |
| 452 | + | |
441 | 453 | | |
442 | 454 | | |
443 | 455 | | |
| |||
457 | 469 | | |
458 | 470 | | |
459 | 471 | | |
460 | | - | |
| 472 | + | |
461 | 473 | | |
462 | 474 | | |
463 | 475 | | |
| |||
514 | 526 | | |
515 | 527 | | |
516 | 528 | | |
517 | | - | |
518 | | - | |
519 | | - | |
520 | | - | |
| 529 | + | |
| 530 | + | |
| 531 | + | |
| 532 | + | |
| 533 | + | |
| 534 | + | |
| 535 | + | |
| 536 | + | |
| 537 | + | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
521 | 541 | | |
| 542 | + | |
| 543 | + | |
522 | 544 | | |
523 | 545 | | |
524 | 546 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
218 | 218 | | |
219 | 219 | | |
220 | 220 | | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
221 | 246 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
135 | 135 | | |
136 | 136 | | |
137 | 137 | | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
138 | 162 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
698 | 698 | | |
699 | 699 | | |
700 | 700 | | |
| 701 | + | |
| 702 | + | |
| 703 | + | |
| 704 | + | |
| 705 | + | |
| 706 | + | |
| 707 | + | |
| 708 | + | |
| 709 | + | |
| 710 | + | |
| 711 | + | |
| 712 | + | |
| 713 | + | |
| 714 | + | |
| 715 | + | |
| 716 | + | |
| 717 | + | |
| 718 | + | |
| 719 | + | |
| 720 | + | |
| 721 | + | |
| 722 | + | |
| 723 | + | |
| 724 | + | |
| 725 | + | |
| 726 | + | |
| 727 | + | |
| 728 | + | |
| 729 | + | |
| 730 | + | |
| 731 | + | |
| 732 | + | |
| 733 | + | |
| 734 | + | |
| 735 | + | |
| 736 | + | |
| 737 | + | |
| 738 | + | |
| 739 | + | |
| 740 | + | |
| 741 | + | |
| 742 | + | |
| 743 | + | |
| 744 | + | |
| 745 | + | |
| 746 | + | |
| 747 | + | |
| 748 | + | |
| 749 | + | |
| 750 | + | |
701 | 751 | | |
702 | 752 | | |
703 | 753 | | |
| |||
0 commit comments