Skip to content

Commit 1db4b1d

Browse files
authored
[fix](be) Validate SNII BKD splits against global bounds (apache#66864)
### What problem does this PR solve? Issue Number: None Related PR: apache#66052 Problem Summary: A CRC-valid SNII BKD index whose split catalogue was ordered but outside its persisted global bounds could open successfully and silently route queries to the wrong leaf. The issue reproduces with values 0 through 19 split into two leaves: changing the persisted split from 10 to 30 makes a point lookup for 15 inspect leaf 0 while the matching point remains in leaf 1. This PR validates the complete non-decreasing `min_value <= split_values... <= max_value` chain when opening the index and asserts the same invariant when encoding. Equal adjacent values and splits equal to either inclusive global bound remain valid.
1 parent a82cfa6 commit 1db4b1d

4 files changed

Lines changed: 118 additions & 28 deletions

File tree

‎be/src/storage/index/snii/bkd/bkd_index_block.cpp‎

Lines changed: 19 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -140,20 +140,21 @@ Status decode_header(ByteSource* src, BkdIndexHeader* header) {
140140
return Status::OK();
141141
}
142142

143-
// Non-decreasing rather than strictly increasing: a value spanning several leaves
144-
// makes consecutive leaves start at the same value. Comparison is unsigned
145-
// byte-wise from offset 0 (INV-1), i.e. plain memcmp over the sortable bytes.
146-
// An unordered array would silently route the binary search to the wrong leaf --
147-
// wrong results with no error -- so it must never survive open.
148-
Status validate_split_order(Slice splits, size_t bytes_per_dim, uint32_t leaf_count) {
149-
for (uint32_t i = 1; i + 1 < leaf_count; ++i) {
150-
const uint8_t* previous = splits.data() + (i - 1) * bytes_per_dim;
143+
// The whole routing catalogue is one non-decreasing chain. Equality is legal: a
144+
// value spanning several leaves makes consecutive leaves start at that value,
145+
// including at either global bound. Comparison is unsigned byte-wise from offset
146+
// 0 (INV-1), i.e. plain memcmp over the sortable bytes.
147+
bool value_order_is_valid(Slice min_value, Slice max_value, Slice splits, size_t bytes_per_dim,
148+
uint32_t leaf_count) {
149+
const uint8_t* previous = min_value.data();
150+
for (uint32_t i = 0; i + 1 < leaf_count; ++i) {
151151
const uint8_t* current = splits.data() + i * bytes_per_dim;
152152
if (std::memcmp(previous, current, bytes_per_dim) > 0) {
153-
return corrupted("split_values are not in ascending order");
153+
return false;
154154
}
155+
previous = current;
155156
}
156-
return Status::OK();
157+
return std::memcmp(previous, max_value.data(), bytes_per_dim) <= 0;
157158
}
158159

159160
// Leaf directory: delta-varint64 offsets, then varint32 counts (design 5.1).
@@ -245,20 +246,12 @@ void encode_bkd_index_block(const BkdIndexHeader& header, Slice min_value, Slice
245246
DORIS_CHECK_EQ(min_value.size(), bytes_per_dim);
246247
DORIS_CHECK_EQ(max_value.size(), bytes_per_dim);
247248
DORIS_CHECK_EQ(split_values.size(), (header.leaf_count - 1) * bytes_per_dim);
249+
DORIS_CHECK(value_order_is_valid(min_value, max_value, split_values, bytes_per_dim,
250+
header.leaf_count));
248251
payload.put_bytes(min_value);
249252
payload.put_bytes(max_value);
250253
payload.put_bytes(split_values);
251254

252-
// The reader binary-searches this array and indexes the leaf directory
253-
// without re-checking, so both orderings are asserted where they are
254-
// produced. Comparison is unsigned byte-wise from offset 0 (INV-1), which
255-
// is exactly memcmp over the sortable bytes.
256-
for (uint32_t i = 1; i + 1 < header.leaf_count; ++i) {
257-
DORIS_CHECK_LE(std::memcmp(split_values.data() + (i - 1) * bytes_per_dim,
258-
split_values.data() + i * bytes_per_dim, bytes_per_dim),
259-
0);
260-
}
261-
262255
uint64_t previous_offset = 0;
263256
uint64_t total_points = 0;
264257
for (size_t i = 0; i < leaves.size(); ++i) {
@@ -332,8 +325,12 @@ Status BkdIndexBlockReader::decode_payload(Slice payload, uint64_t data_length)
332325

333326
Slice splits;
334327
RETURN_IF_ERROR(src.get_bytes(static_cast<size_t>((leaf_count - 1) * bytes_per_dim), &splits));
335-
RETURN_IF_ERROR(
336-
validate_split_order(splits, static_cast<size_t>(bytes_per_dim), header.leaf_count));
328+
const auto value_width = static_cast<size_t>(bytes_per_dim);
329+
const Slice min_value(bounds.data(), value_width);
330+
const Slice max_value(bounds.data() + value_width, value_width);
331+
if (!value_order_is_valid(min_value, max_value, splits, value_width, header.leaf_count)) {
332+
return corrupted("global bounds and split_values are not in ascending order");
333+
}
337334

338335
std::vector<LeafRef> leaves;
339336
RETURN_IF_ERROR(decode_leaf_directory(&src, header, data_length, &leaves));

‎be/src/storage/index/snii/bkd/bkd_index_block.h‎

Lines changed: 9 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@
4646
// --- present only when leaf_count > 0 ---
4747
// min_value bytes[bytes_per_dim]
4848
// max_value bytes[bytes_per_dim]
49-
// split_values bytes[(leaf_count - 1) * bytes_per_dim] ascending, fixed width
49+
// split_values bytes[(leaf_count - 1) * bytes_per_dim] ascending inside min/max
5050
// leaf_offsets delta-varint64[leaf_count] strictly increasing
5151
// leaf_counts varint32[leaf_count]
5252
//
@@ -71,7 +71,8 @@ namespace doris::snii::bkd {
7171
// through BkdIndexBlockReader::open.
7272
//
7373
// min_value / max_value : exactly bytes_per_dim bytes, empty iff leaf_count == 0
74-
// split_values : (leaf_count - 1) * bytes_per_dim bytes, non-decreasing
74+
// split_values : (leaf_count - 1) * bytes_per_dim bytes, with
75+
// min_value <= splits... <= max_value
7576
// leaves : leaf_count entries, offsets strictly increasing,
7677
// counts summing to header.point_count
7778
void encode_bkd_index_block(const BkdIndexHeader& header, Slice min_value, Slice max_value,
@@ -100,9 +101,10 @@ class BkdIndexBlockReader {
100101
// capability boundary, so the caller reports "index unavailable" instead of a
101102
// damaged segment. Every other rejection (bad magic, unknown field_type,
102103
// bytes_per_dim disagreeing with field_type, array lengths disagreeing with
103-
// leaf_count, unordered split values, non-increasing or out-of-range leaf
104-
// offsets, leaf counts not summing to point_count, trailing bytes, crc
105-
// mismatch, truncation) -> INVERTED_INDEX_FILE_CORRUPTED.
104+
// leaf_count, min_value above max_value, split values outside the global
105+
// bounds or unordered, non-increasing or out-of-range leaf offsets, leaf
106+
// counts not summing to point_count, trailing bytes, crc mismatch,
107+
// truncation) -> INVERTED_INDEX_FILE_CORRUPTED.
106108
static Status open(Slice framed, uint64_t data_length, BkdIndexBlockReader* out);
107109

108110
const BkdIndexHeader& header() const { return header_; }
@@ -152,7 +154,8 @@ class BkdIndexBlockReader {
152154
BkdIndexHeader header_;
153155
// min_value followed by max_value, one allocation. Empty for an empty index.
154156
std::vector<uint8_t> bounds_;
155-
// (leaf_count - 1) * bytes_per_dim bytes, non-decreasing, fixed width.
157+
// (leaf_count - 1) * bytes_per_dim bytes, non-decreasing inside the inclusive
158+
// global bounds, fixed width.
156159
std::vector<uint8_t> split_values_;
157160
std::vector<LeafRef> leaves_;
158161
};

‎be/test/storage/index/snii/bkd/bkd_corruption_test.cpp‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -744,6 +744,52 @@ TEST(BkdCorruptionTest, AbsurdPointsPerLeafIsRejectedAtOpen) {
744744
}
745745
}
746746

747+
TEST(BkdCorruptionTest, SelfConsistentSplitAboveGlobalMaximumIsRejectedBeforeQueryRouting) {
748+
std::vector<Point> points;
749+
for (uint32_t i = 0; i < 20; ++i) {
750+
points.push_back(Point {static_cast<int64_t>(i), i});
751+
}
752+
Image original;
753+
ASSERT_TRUE(build_image(points, 10, &original).ok());
754+
const std::vector<uint8_t> data_bytes(
755+
original.bytes.begin() + static_cast<long>(original.data_begin),
756+
original.bytes.begin() + static_cast<long>(original.data_begin + original.data_size));
757+
IndexPayload payload;
758+
ASSERT_TRUE(parse_payload(payload_of(original.index_bytes()), &payload));
759+
ASSERT_EQ(payload.leaf_count, 2U);
760+
761+
ByteSource tail {Slice(payload.tail)};
762+
Slice min_value;
763+
Slice max_value;
764+
Slice old_split;
765+
Slice directory;
766+
ASSERT_TRUE(tail.get_bytes(kBytesPerDim, &min_value).ok());
767+
ASSERT_TRUE(tail.get_bytes(kBytesPerDim, &max_value).ok());
768+
ASSERT_TRUE(tail.get_bytes(kBytesPerDim, &old_split).ok());
769+
ASSERT_TRUE(tail.get_bytes(tail.remaining(), &directory).ok());
770+
ASSERT_EQ(std::memcmp(min_value.data(), sortable_bigint(0).data(), kBytesPerDim), 0);
771+
ASSERT_EQ(std::memcmp(max_value.data(), sortable_bigint(19).data(), kBytesPerDim), 0);
772+
ASSERT_EQ(std::memcmp(old_split.data(), sortable_bigint(10).data(), kBytesPerDim), 0);
773+
774+
const std::vector<uint8_t> malformed_split = sortable_bigint(30);
775+
ByteSink rebuilt;
776+
rebuilt.put_bytes(min_value);
777+
rebuilt.put_bytes(max_value);
778+
rebuilt.put_bytes(Slice(malformed_split));
779+
rebuilt.put_bytes(directory);
780+
payload.tail = rebuilt.take();
781+
const Image damaged = assemble(reframe(encode_payload(payload)), data_bytes);
782+
783+
// Before the open-time invariant was enforced, this CRC-valid image opened
784+
// successfully and a point lookup for 15 silently returned no rows: split 30
785+
// routed the query to leaf 0 while doc 15 remained in leaf 1.
786+
MemoryFileReader file(damaged.bytes);
787+
std::unique_ptr<BkdReader> reader;
788+
const Status status = BkdReader::open(&file, damaged.sections, &reader);
789+
EXPECT_TRUE(is_rejected(status, "split above global maximum"));
790+
EXPECT_EQ(reader, nullptr);
791+
}
792+
747793
TEST(BkdCorruptionTest, InflatedLeafBlockLengthFieldsAreRejectedAtQueryTime) {
748794
// A leaf block starts with { point_count varint32, value_mode u8,
749795
// common_prefix_len varint32, ... } and ends with { docid_block_offset

‎be/test/storage/index/snii/bkd/bkd_index_block_test.cpp‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -544,6 +544,50 @@ TEST(SniiBkdIndexBlock, SplitValuesNotAscendingIsCorrupted) {
544544
EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
545545
}
546546

547+
TEST(SniiBkdIndexBlock, GlobalMinimumAboveMaximumIsCorrupted) {
548+
RawIndexBlock raw = valid_three_leaf_block();
549+
raw.point_count = 4;
550+
raw.doc_count = 4;
551+
raw.leaf_count = 1;
552+
raw.min_value = sortable_bigint(20);
553+
raw.max_value = sortable_bigint(19);
554+
raw.split_values.clear();
555+
raw.leaf_offset_deltas = {0};
556+
raw.leaf_counts = {4};
557+
558+
BkdIndexBlockReader reader;
559+
EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
560+
}
561+
562+
TEST(SniiBkdIndexBlock, SplitValueBelowGlobalMinimumIsCorrupted) {
563+
RawIndexBlock raw = valid_three_leaf_block();
564+
raw.split_values.clear();
565+
append_bytes(&raw.split_values, sortable_bigint(-6));
566+
append_bytes(&raw.split_values, sortable_bigint(200));
567+
568+
BkdIndexBlockReader reader;
569+
EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
570+
}
571+
572+
TEST(SniiBkdIndexBlock, SplitValueAboveGlobalMaximumIsCorrupted) {
573+
RawIndexBlock raw = valid_three_leaf_block();
574+
raw.split_values.clear();
575+
append_bytes(&raw.split_values, sortable_bigint(100));
576+
append_bytes(&raw.split_values, sortable_bigint(301));
577+
578+
BkdIndexBlockReader reader;
579+
EXPECT_TRUE(IsCorrupted(open_raw(raw, &reader)));
580+
}
581+
582+
TEST(SniiBkdIndexBlock, SplitValuesMayEqualInclusiveGlobalBounds) {
583+
RawIndexBlock raw = valid_three_leaf_block();
584+
raw.min_value = sortable_bigint(100);
585+
raw.max_value = sortable_bigint(200);
586+
587+
BkdIndexBlockReader reader;
588+
EXPECT_TRUE(open_raw(raw, &reader).ok());
589+
}
590+
547591
// Ordering is UNSIGNED byte comparison, MSB first (INV-1). 0x80.. sorts above
548592
// 0x7F.. even though the same bytes read as a signed value would not.
549593
TEST(SniiBkdIndexBlock, SplitValueOrderingIsUnsignedByteWise) {

0 commit comments

Comments
 (0)