Repository navigation
[fix](rle) Fix infinite loop when a repeated run reaches 2^30 values - #69100
Conversation
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 made the
indicator overflow into a negative number. BitWriter::PutVlqInt() then took
that as an int32_t and shifted it right arithmetically:
while ((v & 0xFFFFFF80) != 0L) {
PutAligned<uint8_t>((v & 0x7F) | 0x80, 1);
v >>= 7;
}
An arithmetic 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.
This was hit in production by a base compaction on a table with many nullable
columns. Vertical compaction derives the segment row limit from
`vertical_compaction_max_segment_size / avg_bytes_per_row`; for this table the
average row size integer-divided to 0, so the limit degenerated to the config
default of 1073741824 = 2^30 rows. ScalarColumnWriter::append_nulls() does not
check 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 of
2^30 rows in one page. Flushing that page wedged the compaction thread forever.
Because the base compaction slot stayed occupied, no base compaction was
scheduled on that backend again.
Three fixes:
1. Take `uint32_t` in PutVlqInt(). A logical shift always converges to 0, so
the loop terminates for every input. This is the backstop that makes a hang
impossible regardless of what callers pass.
2. Widen `repeat_count_` to int64_t and split runs longer than
MAX_VALUES_PER_REPEATED_RUN (2^30 - 1) into 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, which is exactly
the range previous versions could encode, so output stays byte-identical for
every run length that used to work.
3. Make faststring::reserve() grow geometrically via GrowToAtLeast() instead of
reallocating to exactly the requested capacity. BitWriter reserves a few
bytes at a time, so exact growth reallocated and memcpy'd the whole 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 too.
Not addressed here, worth separate changes: append_nulls() still lets a page
grow without bound, and get_avg_segment_rows() still degenerates to the
configured byte size when the average row size rounds down to zero.
|
Thank you for your contribution to Apache Doris. Please clearly describe your PR:
|
|
/review |
|
run buildall |
There was a problem hiding this comment.
Reviewed all seven changed files at 7bbe72075926a5d7d3cece71c59576fbe9cf5d1f, including upstream storage writers, downstream readers, shared buffer callers, and tests. No actionable defect was found. No existing inline findings require carrying forward. No additional user focus was supplied.
The review converged in 1 round: the complete-review agent and both independent risk reviewers returned NO_NEW_VALUABLE_FINDINGS; the main review verified their evidence and completed the final sweep. There are no unresolved candidates or uncovered changed files.
The triggering flow was traced through ScalarColumnWriter::append_nulls -> NullBitmapBuilder -> RleEncoder::Put/Flush -> BitWriter -> faststring -> OwnedSlice, then page readers using RleDecoder. The two risk questions were resolved: bounded adjacent repeated runs preserve the existing reader grammar, and geometric reserve reuses the existing tracked allocation/ownership/ASAN path without a demonstrated caller regression.
Critical checkpoint conclusions:
- Goal and evidence: unsigned VLQ shifting terminates within five bytes; widened counts and runs capped at 2^30-1 address the reported hang. Added boundary tests target this mechanism; their execution was not independently verified.
- Scope and reuse: changes are focused on encoding overflow, incremental buffer growth, and their tests; reserve reuses
GrowToAtLeast. - Concurrency: no new threads, shared state, locks, or lock-order changes. Encoder and buffer state remain caller-owned.
- Lifecycle: Flush/Clear/build/reset/destruction preserve ownership. The new constexpr constant introduces no dynamic or cross-translation-unit initialization.
- Configuration: no configuration changes.
- Compatibility: previously valid repeated runs retain their bytes. Larger runs use existing adjacent-run syntax with indicators <=0x7FFFFFFE; inspected scalar and batch readers accept these. The changed inline signature and encoder layout are internal.
- Thrift/protobuf: no field or enum changes.
- Parallel paths: inspected bulk and single-value writes, nullable and scalar RLE pages, Get/GetNextRun/Skip/RewindOne/get_values, batch readers, and page seek/read paths; no parallel fix was missing.
- Conditions and errors: the split loop has a concrete overflow rationale and makes bounded progress. Existing error propagation and state assertions are unchanged.
- Test coverage: new tests cover large runs around the cap and above INT32_MAX, VLQ boundaries through UINT32_MAX, and geometric reserve. Existing tests cover mixed/literal transitions, zero-length writes, bit widths, and bulk/incremental equivalence. Huge false/multibyte runs and partial/skip/rewind/mixed-tail combinations are not newly tested; static inspection found no failure in those paths. No end-to-end test was added.
- Test results: no golden files changed. New expectations are consistent by inspection; author-reported test results are not execution evidence from this review.
- Observability: no new distributed or asynchronous workflow needs additional logging or metrics.
- Transactions and persistence: no EditLog, version visibility, delete bitmap, commit, replay, or failover protocol changes. Stored RLE compatibility was checked separately above.
- Data writes and atomicity: page finish/publication and crash/error handling are unchanged; split counts preserve values without adding a publication path.
- FE/BE variables: no transmitted variables or send sites changed.
- Performance and memory: splitting costs O(number of capped runs), with only a few runs for uint32-limited segments. Geometric reserve removes quadratic copying; actual capacity stays tracked and is carried into OwnedSlice for freeing. Additional retained capacity is the intended growth tradeoff.
- Other BE obligations: no new dependency, libc API, PCH entry, explicit instantiation, or test inclusion of source .cpp files. The pure-text
build-support/check-build-hygiene.shcheck passed all header, pairing, and unity-skip gates.
Validation was static: no Doris build, unit/regression test, sanitizer run, released-binary compatibility run, or empirical benchmark was executed, and no source file was modified. These are validation limits; all assigned code-review scope and risk dispositions are complete.
Review converged after 1 round(s).
TPC-H: Total hot run time: 29600 ms |
TPC-DS: Total hot run time: 152213 ms |
ClickBench: Total hot run time: 24.65 s |
BE UT Coverage ReportIncrement line coverage Increment coverage report
|
BE Regression && UT Coverage ReportIncrement line coverage Increment coverage report
|
|
PR approved by anyone and no changes requested. |
|
PR approved by at least one committer and no changes requested. |
…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]>
…2^30 values #69100 (#69193) Cherry-picked from #69100 Co-authored-by: Xin Liao <[email protected]> Co-authored-by: Xin Liao <[email protected]>
What problem does this PR solve?
Problem Summary:
RleEncoder::FlushRepeatedRun()wroterepeat_count_ << 1into anint32_t.repeat_count_was anint, so a repeated run of 2^30 or more values overflowed the indicator into a negative number.BitWriter::PutVlqInt()then took that as anint32_tand shifted it right arithmetically:An arithmetic right shift of a negative value converges to
-1and stays there, and-1 & 0xFFFFFF80is non-zero, so the loop never exits. It appends0xFFto 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
textcolumns. TwoBaseCompactionTthreads sat in this stack for over a month:v=-1together withval=255pins it down exactly: the loop is emitting0xFFwithvstuck at-1.Two existing behaviours combined to produce a 2^30-value run:
vertical_compaction_max_segment_size / avg_bytes_per_row(Compaction::get_avg_segment_rows()). For this table the average row size integer-divided to0, so the divisor degenerated to1and the limit became the config default1073741824= 2^30 rows — visible asmax_rows_per_segment=1073741824in the stack above.ScalarColumnWriter::append_nulls()never checks whether the page is full, unlikeappend_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_diskdefaults to 2),_generate_cloud_compaction_tasks()computedbase_n = 0and 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
PutVlqInt()takesuint32_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.repeat_count_widened toint64_t, and long runs are split. Runs longer thanMAX_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 insideint32_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.faststring::reserve()grows geometrically via the existingGrowToAtLeast()instead of reallocating to exactly the requested capacity.BitWriterreserves 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 inmemcpywith 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)
New tests:
TestRle.TestRepeatedRunExceedingIndicatorRangeTestBitStreamUtil.TestPutVlqIntRoundTripPutVlqIntround-trips everyuint32_t, including values>= 2^31that used to hangFaststringTest.TestReserve_ExponentiallyExpandreserve()does not reallocate on every callVerified that the new tests actually catch the bug: built the exact repro (
RleEncoder<bool>::Put(true, 1 << 30)followed byFlush()) against unpatched master and it never returns (killed by timeout); with this patch it completes and emits 8 bytes. All pre-existing tests inrle_encoding_test,bit_stream_utils_testandfaststring_testpass (29 tests, withLOOP_LESS_OR_MOREforced to the slow/thorough branch).Also confirmed no format regression: a short run encoded via
Put(v)in a loop and viaPut(v, n)in one call still produce byte-identical output.Behavior changed:
Does this need documentation?