Repository navigation
branch-4.2: [fix](rle) Fix infinite loop when a repeated run reaches 2^30 values #69100 - #69193
Merged
Merged
Conversation
…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]>
Contributor
|
Thank you for your contribution to Apache Doris. Please clearly describe your PR:
|
Contributor
|
run buildall |
Contributor
BE Regression && UT Coverage ReportIncrement line coverage Increment coverage report
|
Contributor
|
skip buildall |
yiguolei
approved these changes
Oct 16, 2026
Contributor
Author
|
PR approved by anyone and no changes requested. |
Contributor
Author
|
PR approved by at least one committer and no changes requested. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Cherry-picked from #69100