[
https://issues.apache.org/jira/browse/HDDS-17469?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Siyao Meng reassigned HDDS-17469:
---------------------------------
Assignee: Siyao Meng
> 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
> Affects Versions: 1.1.0, 1.2.0, 1.3.0, 1.2.1, 1.4.0, 2.0.0, 1.4.1, 2.1.0,
> 2.2.0, 2.1.1, 2.1.2, 2.2.1
> Reporter: Siyao Meng
> Assignee: Siyao Meng
> Priority: Critical
> 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]
