[
https://issues.apache.org/jira/browse/HDDS-17260?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Siyao Meng updated HDDS-17260:
------------------------------
Attachment: CR-1-compare-snapshot-diff-keys-in-utf8-byte-order.patch
> 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
> Affects Versions: 2.2.0, 2.2.1
> Reporter: Siyao Meng
> Priority: Major
> 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]
