Skip to content

branch-4.2: [fix](rle) Fix infinite loop when a repeated run reaches 2^30 values #69100 - #69193

Merged
yiguolei merged 1 commit into
branch-4.2from
auto-pick-69100-branch-4.2
Oct 16, 2026
Merged

yiguolei merged 1 commit into
branch-4.2from
auto-pick-69100-branch-4.2

Conversation

@github-actions

Copy link
Copy Markdown
Contributor

Cherry-picked from #69100

…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]>
@github-actions
github-actions Bot requested a review from yiguolei as a code owner October 16, 2026 09:09
@hello-stephen

Copy link
Copy Markdown
Contributor

Thank you for your contribution to Apache Doris.
Don't know what should be done next? See How to process your PR.

Please clearly describe your PR:

  1. What problem was fixed (it's best to include specific error reporting information). How it was fixed.
  2. Which behaviors were modified. What was the previous behavior, what is it now, why was it modified, and what possible impacts might there be.
  3. What features were added. Why was this function added?
  4. Which code was refactored and why was this part of the code refactored?
  5. Which functions were optimized and what is the difference before and after the optimization?

@hello-stephen

Copy link
Copy Markdown
Contributor

run buildall

@hello-stephen

Copy link
Copy Markdown
Contributor

BE Regression && UT Coverage Report

Increment line coverage 100.00% (13/13) 🎉

Increment coverage report
Complete coverage report

Category Coverage
Function Coverage 76.26% (34336/45026)
Line Coverage 61.16% (389425/636720)
Region Coverage 57.85% (327709/566518)
Branch Coverage 58.85% (150953/256503)

@yiguolei

Copy link
Copy Markdown
Contributor

skip buildall

@yiguolei
yiguolei merged commit 900935e into branch-4.2 Oct 16, 2026
37 of 38 checks passed
@github-actions

Copy link
Copy Markdown
Contributor Author

PR approved by anyone and no changes requested.

@github-actions github-actions Bot added the approved Indicates a PR has been approved by one committer. label Oct 16, 2026
@github-actions

Copy link
Copy Markdown
Contributor Author

PR approved by at least one committer and no changes requested.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

approved Indicates a PR has been approved by one committer. reviewed

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants