Siyao Meng created HDDS-17260:
---------------------------------
Summary: Snapshot diff can omit changed keys whose names differ
from a nearby key by a supplementary character against a character in U+E000 to
U+FFFF
Key: HDDS-17260
URL: https://issues.apache.org/jira/browse/HDDS-17260
Project: Apache Ozone
Issue Type: Bug
Reporter: Siyao Meng
Attachments: CR-1-compare-snapshot-diff-keys-in-utf8-byte-order.patch
h3. Mechanism
OM tables store {{String}} keys as UTF-8, and RocksDB iterators, including the
SST file readers that snapshot diff uses for the delta files, return them in
unsigned byte order. The snapshot diff key merge compares the same keys with
{{String.compareTo}}, which orders by UTF-16 code units, in two places:
* {{SstFileSetReader.MultipleSstFileIterator}} merges the keys of several delta
SST files with a {{MinHeapMergeIterator}} built with {{Comparable::compareTo}}.
* {{TableMergeIterator.updateAndGetValueAtIndex}} looks each merged key up in
the from and to snapshot tables. It seeks a table only when the key is greater,
by {{String.compareTo}}, than the key that table's iterator holds from its last
seek; otherwise it uses the held key and returns null when that key does not
match.
The two orders agree except for names that differ at some position by a
supplementary character (a surrogate pair, for example U+1F600, UTF-8 {{F0 9F
98 80}}) against a character in U+E000 to U+FFFF (for example U+FF21, UTF-8
{{EF BC A1}}). RocksDB puts the supplementary character after the other one,
{{String.compareTo}} before it.
Around such names the merge goes wrong:
* In a single delta file the keys arrive in byte order. When the held key sorts
after the next key in byte order but before it as a {{String}},
{{TableMergeIterator}} skips the seek and returns null for a key the table
contains. If both lookups are then null,
{{SnapshotDiffManager.addToObjectIdMap}} treats the key as unchanged and skips
it.
* With several delta files the heap merge returns keys out of byte order and
can return the same key more than once. {{TableMergeIterator}} then also gets
keys that lie behind its last seek, and the skipped key can be one with only
BMP characters, for example the U+E000 to U+FFFF name.
h3. Affected key names
Names in the same bucket and table that differ by a supplementary character
against a character in U+E000 to U+FFFF, for example {{kＡ}} and {{k😀}}, or
{{report（1）.txt}} (fullwidth parentheses) and {{report😀}}, where at least one
of them changed within the diff range. Supplementary characters include emoji
and the CJK extension ideographs; U+E000 to U+FFFF covers the private use area,
the CJK compatibility ideographs, the halfwidth and fullwidth forms and U+FFFD.
Key name validation accepts these characters. Names that differ only in other
characters are not affected.
h3. Impact
* The snapshot diff report can miss changed keys, for creates and deletes,
without an error. The job finishes as DONE and the incomplete report is stored
and served. Seen on FSO and OBS buckets, with the compaction DAG diff and with
a forced full diff, all without the native RocksDB tools library. The native
library path uses another per file reader but the same merge and the same
{{TableMergeIterator}}; argued from code, not run.
* {{SnapshotDefragService.spillTableDiffIntoSstFile}} (incremental snapshot
defragmentation, off by default) reads the delta files through the same
{{SstFileSetReader}} and {{TableMergeIterator}}. By code, a defragmented
snapshot can then miss changed keys; argued, not run.
* Affects 2.2.0 and 2.2.1. The {{TableMergeIterator}} seek check came with
HDDS-13930; up to 2.1.x the diff looked every key up with {{Table.get}}, which
does not depend on the key order.
* Proposed priority: Major. The output is silently incomplete, but no live data
is lost and only names with the character combination above are affected.
h3. Reproduction
No standalone reproduction is attached. The regression tests in the patch cover
the defect; each fails without the change:
* {{TestSstFileSetReader.testKeysMergedInUtf8ByteOrder}} merges two real SST
files whose keys straddle the boundary (a common prefix, ASCII, U+00E9, U+D7FF,
U+E000, U+FF21, U+10000, U+1F600). Without the change it returns keys out of
order and twice: {{[k, kz, ké, k, k, k𐀀, k, kＡ, k𐀀, k😀]}} (the U+E000
character is invisible) instead of each key once in byte order.
* {{TestTableMergeIterator.testWithKeysInUtf8ByteOrder}} looks up {{k}},
{{kＡ}}, {{k😀}} in two RocksDB tables. With {{String.compareTo}} as the order it
returns null for {{k😀}} from the table that contains it ({{[null, value3]}}
instead of {{[value2, value3]}}).
* {{OmSnapshotTests.testSnapDiffWithKeysInUtf8ByteOrder}} creates and then
deletes {{kＡ}} and {{k😀}} between snapshots on a mini cluster. Without the
change the reports are {{[+ ./kＡ, + ./kz]}} and {{[- ./kＡ]}}, without {{k😀}}.
h3. Patch
[^CR-1-compare-snapshot-diff-keys-in-utf8-byte-order.patch], against
b10a7d427bdf83807a7e48a1be507d3b02d5a503. It also applies to master at
d3b5f518556.
The patch adds {{StringUtils.compareUtf8}}, which orders well formed strings
like their UTF-8 bytes (Unicode code point order) without encoding them: it
differs from {{String.compareTo}} only when exactly one of the first differing
code units is a surrogate, which it then sorts last. {{SstFileSetReader}}
passes it to {{MinHeapMergeIterator}} instead of {{Comparable::compareTo}}.
{{TableMergeIterator}} gets a constructor that takes the key order for its seek
check, and both callers, {{SnapshotDiffManager.addToObjectIdMap}} and
{{SnapshotDefragService.spillTableDiffIntoSstFile}}, pass
{{StringUtils::compareUtf8}}. The existing {{TableMergeIterator}} constructor
keeps the natural order. For names without the character combination above the
order, and so the behaviour, is unchanged; there is no config, wire or on disk
change.
With the change the three tests above pass, as do the existing
{{TestSstFileSetReader}}, {{TestMinHeapMergeIterator}},
{{TestTableMergeIterator}}, {{TestSnapshotDiffManager}},
{{TestSnapshotDefragService}} and {{TestRocksDiffUtils}} suites and the
{{OmSnapshotTests}} subclasses that run without the native library. The native
library subclasses were not run.
Found by code review of the OM snapshot diff paths, as part of the TLA+
verification effort under HDDS-15926, on commit
b10a7d427bdf83807a7e48a1be507d3b02d5a503. Checked against HDDS issues and
apache/ozone pull requests for duplicates before filing. The attached patch is
a proposal for review. Generated with Specula (Claude Opus 5.5).
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
