I'm not sure that it will work correctly with "actual part name" optimization...

You mean that here actual_new_part_name should be take into account?

Doesn't this means that removePartProducingOpsInRange already works not correctly when actual_new_part_name is not empty?

You mean that here actual_new_part_name should be take into account?

Not precisely, I mean that logic that "upgrades" currently executing entry to covering entry probably should be taken into account. See addFuturePartIfNotCoveredByThem and related methods. Seems like deadlock is possible, because setActualPartName may wait for older entries ("age" is determined by znode_name), but removePartProducingOpsInRange now may wait for all entries covered by part_info. And usually covered entries are older, but not when "actual part name" logic is involved.

Doesn't this means that removePartProducingOpsInRange already works not correctly when actual_new_part_name is not empty?

No, because currently removePartProducingOpsInRange can be called by DROP_RANGE or REPLACE_RANGE entries only and actual_new_part_name can be set only for simple part-producing operation (GET_PART, MERGE_PARTS, MUTATE_PART)

So I've looked at this again, and let me describe possible scenarios (that may lead to a possible deadlock):

• queue: [1_0_1_0, 1_1_2_0, 1_0_2_1]
  T1 will execute fetch of 1_0_1_0, and fetch 1_0_2_1 instead
  T2 will execute fetch of 1_1_2_0, no 1_0_2_1 in future_parts yet
  This should be safe because T2 will not fetch anything because of

  ClickHouse/src/Storages/MergeTree/ReplicatedMergeTreeQueue.cpp

  Lines 1116 to 1125 in d4a7e18

  	if (covered_entries_to_wait)
  	{
  	if (entry.znode_name < future_part_elem.second->znode_name)
  	{
  	out_reason = fmt::format(
  	"Not executing log entry {} for part {} "
  	"because it is not disjoint with part {} that is currently executing and another entry {} is newer.",
  	entry.znode_name, new_part_name, future_part_elem.first, future_part_elem.second->znode_name);
  	LOG_TRACE(log, fmt::runtime(out_reason));
  	return true;

• queue: [1_0_1_0, 1_1_2_0, 1_0_2_1]
  T1 will execute fetch of 1_0_1_0, and fetch 1_0_2_1 instead
  T2 will execute fetch of 1_1_2_0, and also fetch 1_0_2_1 instead
  This should be safe because of

  ClickHouse/src/Storages/MergeTree/ReplicatedMergeTreeQueue.cpp

  Lines 1069 to 1084 in d4a7e18

  	bool ReplicatedMergeTreeQueue::isCoveredByFuturePartsImpl(const LogEntry & entry, const String & new_part_name,
  	String & out_reason, std::unique_lock<std::mutex> & /* queue_lock */,
  	std::vector<LogEntryPtr> * covered_entries_to_wait) const
  	{
  	/// Let's check if the same part is now being created by another action.
  	auto entry_for_same_part_it = future_parts.find(new_part_name);
  	if (entry_for_same_part_it != future_parts.end())
  	{
  	const LogEntry & another_entry = *entry_for_same_part_it->second;
  	out_reason = fmt::format(
  	"Not executing log entry {} of type {} for part {} "
  	"because another log entry {} of type {} for the same part ({}) is being processed. This shouldn't happen often.",
  	entry.znode_name, entry.type, entry.new_part_name,
  	another_entry.znode_name, another_entry.type, another_entry.new_part_name);
  	LOG_INFO(log, fmt::runtime(out_reason));
  	return true;

• queue: [1_0_1_0, 1_1_2_0, 1_0_2_1]
  T1 will execute fetch of 1_0_1_0, and fetch 1_0_2_1 instead
  T2 will execute fetch of 1_0_2_1
  This should be safe, because actual_part_name is also added into

  ClickHouse/src/Storages/MergeTree/ReplicatedMergeTreeQueue.cpp

  Line 1492 in d4a7e18

  if (!queue.future_parts.emplace(entry.actual_new_part_name, entry.shared_from_this()).second)

So I don't see any possible deadlock, @tavplubix maybe you can suggest some example of it?

@tavplubix friendly ping

You're right, seems like deadlock is not possible.

Potential problem is that queue entries may be reordered during recovery of stale replica and in rare cases covering entry may have less znode_name (you can check it by running test 993):

2022.11.08 20:37:42.819521 [ 2601779 ] {} <Trace> test_zc23mw5c.alter_table_0 (ReplicatedMergeTreeQueue): Not executing log entry queue-0000000261 for part -1_5_21_1_47 because it is not disjoint with part -1_10_10_0_46 that is currently executing and another entry queue-0000000262 is newer.

And in this case -1_10_10_0_46 (queue-0000000262) could wait for -1_5_21_1_47 (queue-0000000261) that is currently executing. And -1_5_21_1_47 could wait for covered 1_10_10_0_46 in removePartProducingOpsInRange.

But currently it's not possible for two reasons:

1. We fill covered_entries_to_wait and wait for these entries only when calling isCoveredByFuturePartsImpl from addFuturePartIfNotCoveredByThem from findReplicaHavingCoveringPart. We do it only for "upgrading" a part to covering part and setting "actual part name". But findReplicaHavingCoveringPart will never call addFuturePartIfNotCoveredByThem for covered part (it can only "upgrade", not "downgrade"), so actually setActualPartName will wait only for covered parts. And seems like the comparison of znode_names is redundant.
2. Get, attach, merge and mutate entries for not-disjoint parts cannot work concurrently. The only exception is when some entry "upgrades" and sets "actual part name": it can wait for covered entries in setActualPartName. But when it will reach removePartProducingOpsInRange not-disjoint entries do not work concurrently.

I will verify that by adding some assertions and will try to simplify these functions.

P.S. I noticed that after 5ffc38d DROP_RANGEs are postponed if some covered entries are currently executing, but it should not work this way and DROP_RANGEs should have priority. Will try to fix it too.

Hm, no, p.1 is not true: If we are executing all_1_1_0 and trying to upgrade it to all_1_5_2 and all_1_3_1 is currently executing, then all_1_1_0 will wait for all_1_3_1. So it can wait for covering parts, not only for covered. But p.2 seems to be true.

@tavplubix thanks for the details and for finish the patch!

Maybe you can shed some light on the following?

Potential problem is that queue entries may be reordered during recovery of stale replica

But why can't they be reordered without recovery?

and in rare cases covering entry may have less znode_name (you can check it by running test 993):

And if this is possible then it seems that this check is indeed redundant, no?

But why can't they be reordered without recovery?

It depends of what "order" is. There are at least 3 orders:

• total order based on znode_name/sequential numbers of log/queue entries
• partial (or total (?) within partition) order based on MergeTreePartInfo of parts produced by queue entries
• "order" of entries execution (there's no order actually, it can be almost arbitrary)

This statement was about znode_name order. Entries for bigger (in terms of MergeTreePartInfo) parts usually get greater sequential numbers (and greater znode_names). Just because when we create an entry for a covering part, entries for all source parts were already created in the log. And entries are pulled from log to queue one by one in the same order.

But recovery of stale replica is tricky: it tries to copy queue of source replica (while this queue is concurrently changing) and additionally creates GET_PART entries for all parts that source replica had at the moment after copying queue entries. And an entry for bigger part can get less znode_name even if it had greater znode_name in source replica queue (just like in the log message above). Something similar may happen due to removePartAndEnqueueFetch without recovery.

And if this is possible then it seems that this check is indeed redundant, no?

No, this check is needed to enforce some order here, comparing znode_name was the simplest way to avoid deadlocks.

Something similar may happen due to removePartAndEnqueueFetch without recovery.

Oh, I see, thanks. Didn't know that queue can be filled not from the zookeeper log.

No, this check is needed to enforce some order here, comparing znode_name was the simplest way to avoid deadlocks

So let me describe how I understood it, and please correct me if I'm wrong.

Server (example for the link you provided) tries to fetch 1_417_417_0 (queue-0000004322), but it had been "upgraded" to fetch 1_300_433_10 instead, but it still waiting for:

• 1_381_386_1 (queue-0000004859)
• 1_381_394_2 (queue-0000004868)
• 1_381_412_3 (queue-0000004886)
• 1_388_388_0 (queue-0000004008)
• 1_417_417_0 (queue-0000004322) -- will not try to wait it

After your patch it will wait only for 1_388_388_0, but actually it will not start execution until it will be executed, and so deadlock is not possible after this?

Looks like this is happening because of the same "actual_part_name" optimization? And it is safe because this optimization can be done only locally, it is not stored in zookeeper, and so no issues if the queue entries will be reordered during replica clone. And it is also safe for the case with removePartAndEnqueueFetch, since it can create only parts with greater znode.

Maybe it worth putting a comment there (for znode comparison why it is safe, and what guarantees it has)?

Also maybe just for the sake of consistency it worth to make this check regardless covered_entries_to_wait was passed or not? (for the shouldExecuteLogEntry)