Siyao Meng created HDDS-17469:
---------------------------------
Summary: OMKeysRenameResponse writes renames whose sources and
destinations overlap in map order, so the committed key table differs from the
cache
Key: HDDS-17469
URL: https://issues.apache.org/jira/browse/HDDS-17469
Project: Apache Ozone
Issue Type: Bug
Reporter: Siyao Meng
Attachments: CR-10-skip-overlapping-pairs-in-rename-keys.patch
h3. Mechanism
{{OMKeysRenameRequest.validateAndUpdateCache}} checks each pair against the key
table, whose cache already holds the result of the earlier pairs of the same
transaction, and stores the accepted pairs in a {{HashMap}} from source name to
the new {{OmKeyInfo}}. {{OMKeysRenameResponse.addToDBBatch}} iterates that map
and writes, per entry, a delete of the source and a put of the destination.
When the pairs of one response share key names, the batch therefore depends on
the map's iteration order, and a map keyed by source name cannot hold two pairs
with the same source at all. The committed key table then differs from the
cache that the request updated:
* A destination that a later pair renames away (source {{key}} to {{key_b}},
source {{key_b}} to {{key_c}}): when the second entry is iterated first, the
batch is delete {{key_b}}, put {{key_c}}, delete {{key}}, put {{key_b}}. The
table commits both {{key_b}} and {{key_c}} with the same object ID and block
list, while the cache holds only {{key_c}}.
* A destination that an earlier pair used as its source ({{key}} to {{key_b}},
{{other}} to {{key}}): when the second entry is iterated first, the batch is
delete {{other}}, put {{key}}, delete {{key}}, put {{key_b}}. The table commits
no {{key}}, while the cache holds {{key}} with the object of {{other}}.
* A source that appears in two pairs ({{a}} to {{b}}, {{c}} to {{a}}, {{a}} to
{{d}}): the map keeps only the last pair for {{a}}, so {{b}} is never written
and {{a}} and {{d}} both commit the object of {{c}}.
Responses whose pairs share no key name are not affected, since their deletes
and puts touch disjoint keys. The FSO layout has no multi key rename response,
and {{OMKeyRenameResponse}} carries one pair per response, so neither is
affected.
h3. Trigger
An {{OMKeysRenameResponse}} whose pairs share a key name, as described above.
{{validateAndUpdateCache}} builds such a response whenever a pair names a key
that an earlier accepted pair of the same transaction renamed from or to,
because the existence checks of the later pair read the cache entries written
by the earlier one. No timing or fault is needed. OMs running the same version
apply the transaction with the same map order, so they commit the same state.
h3. Impact
The cache entries of the transaction are evicted shortly after the double
buffer flush, and on restart, so the committed state becomes what every read
sees:
* In the first case {{key_b}} reappears as a second key on the blocks of
{{key_c}}. When one of the two is deleted, its blocks are added to
{{deletedTable}} and sent to SCM for deletion while the other key still lists
them, so that key loses its data once the blocks are deleted.
* In the second and third cases a key that the OM reported as renamed
disappears ({{key}}, respectively {{b}}). No key refers to its object any more
and its blocks never reach {{deletedTable}}, so they leak.
These effects were observed on a single real OM (single node Ratis, no
datanodes, blocks sent for deletion recorded by a test SCM); actual block
deletion on datanodes was not run.
h3. Reproduction
The attached patch carries the reproduction as a regression test:
{{TestOMKeysRenameRequest.testCommittedKeyTableMatchesCache}} runs a
transaction with the first and the second case through {{preExecute}} and
{{validateAndUpdateCache}}, commits its response, and compares each key in the
DB with the cache; a third case with disjoint pairs is the control. Without the
check in {{preExecute}} it fails for both cases ({{key_b}}: present in the DB
but not in the cache; {{key}}: present in the cache but not in the DB).
h3. Patch
[^CR-10-skip-overlapping-pairs-in-rename-keys.patch], against
a5814528cdc8d3c1b27f259e0db2256b585cb825. It also applies to master at
88119243f99.
{{OMKeysRenameRequest.preExecute}} rejects the transaction with
{{INVALID_REQUEST}} when a pair names a key that an earlier pair of the same
transaction uses as source or destination (pairs with an empty name are
skipped, as {{validateAndUpdateCache}} never applies them). The check needs
only the key names, so it runs on the leader before the transaction is
replicated, and {{validateAndUpdateCache}} and the response are unchanged:
entries already in the Raft log are applied as before, and OMs of different
versions applying the same entry stay consistent. A leader without the patch
still replicates such a transaction, and patched followers then apply it the
old way, consistent but unfixed.
Behaviour change: a transaction with pairs that share a key is now rejected as
a whole, nothing in it is renamed, and the caller gets {{INVALID_REQUEST}}.
Today the committed result of such a transaction depends on the key names: for
some names it matches the cache (for example {{k}} to {{k_b}}, then {{k_b}} to
{{k_c}}), for others keys are lost or duplicated. Those that work today by
chance are rejected too. Transactions whose pairs share no key behave as before.
Keeping the pairs in their original order in the response was considered and
not taken: the map keyed by source name loses the earlier of two pairs with one
source (third case), so it would need an ordered list of pairs passed from the
request to the response, a larger change of both.
With the patch {{TestOMKeysRenameRequest}}, {{TestOMKeysRenameResponse}},
{{TestOMKeyRenameRequest}}, {{TestOMKeyRenameRequestWithFSO}},
{{TestOMKeyRenameResponse}} and {{TestOMKeyRenameResponseWithFSO}} (36 tests)
pass, as do {{testKeysRename}} and {{testKeysRenameFail}} of the mini cluster
RPC suite and {{TestOzoneManagerRestart.testRestartOMWithKeyOperation}} on a
mini cluster, and checkstyle is clean.
Found by code review of the OM table cache, double buffer flush and startup
paths, as part of the TLA+ verification effort under HDDS-15926, on commit
a5814528cdc8d3c1b27f259e0db2256b585cb825. 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
(v10.3.26#10030026)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
