[xCluster] Locality-Aware Placement for M:N tablet mapping in setup_replication

[nspiegelberg]

Currently, setup_replication only does tablet mapping between Consumer & Producer clusters in the 1:1 use case. For the M:N use case, a naive round-robin strategy is used. It would be useful to have a best-effort mapping instead.

In addition to getting the list of tablets on the Producer side, get the start & end rowkey. Compute the max overlap in a rowkey interval with a local tablet and assign accordingly (only assign RR on failure).

• Add an Interval Overlap Calculation
  -- Calculate a set of candidate tablets on the Consumer that have their [StartKey_C, EndKey_C] within the Producer’s [StartKey_P, EndKey_P] range.
  -- For each candidate, determine the overlap window
  -- [StartKey_O, EndKey_O] == [ max(StartKey_C, StartKey_P), min (EndKey_C, EndKey_P) ].
  -- Pick the candidate with max(EndKey_O - StartKey_O)

We might be able to approximate this faster using a middle key algorithm:

• For a Producer tablet, calculate the middle key. Assign to the Consumer tablet that contains the middle key.
  Use the logical MiddleKey, instead of GetEncodedMiddleSplitKey(), for a fully in-memory operation.

This task is the first step towards adding this heuristic to the xDC + tablet splitting use case to keep reasonably good locality while allowing their split keys to diverge. See the Tablet Splitting + xDC Design Doc: https://docs.google.com/document/d/1MlhwjqSypnP8i6r7DJcm85GNIaguV51ZqiekRIyf0eU

[hulien22]

Some code pointers to help out, currently we process tablet mappings in two locations:

1. At the end of setting up replication, we initialize the consumer. As part of this, we fetch all the consumer table's tablets and compare with the producer tablets to create the tablet mapping. If it is a M:N setup, then this assignment is done round-robin:

   yugabyte-db/ent/src/yb/master/cdc_consumer_registry_service.cc

   Line 83 in b7d6a7d

   consumer = consumer_tablets_resp.tablet_locations(i % consumer_tablets_size).tablet_id();

2. For tablet splitting, when a consumer side tablet splits, we need to re-assign the parent tablet's pollers. This is currently also done in a naive round-robin fashion:

   yugabyte-db/ent/src/yb/master/cdc_consumer_registry_service.cc

   Lines 114 to 130 in b7d6a7d

   	Status UpdateTableMappingOnTabletSplit(
   	cdc::StreamEntryPB* stream_entry,
   	const SplitTabletIds& split_tablet_ids) {
   	auto* mutable_map = stream_entry->mutable_consumer_producer_tablet_map();
   	auto producer_tablets = (*mutable_map)[split_tablet_ids.source];
   	mutable_map->erase(split_tablet_ids.source);
   	// TODO introduce a better mapping of tablets to improve locality (GH #10186).
   	// For now we just distribute the producer tablets between both children.
   	for (int i = 0; i < producer_tablets.tablets().size(); ++i) {
   	if (i % 2) {
   	*(*mutable_map)[split_tablet_ids.children.first].add_tablets() = producer_tablets.tablets(i);
   	} else {
   	*(*mutable_map)[split_tablet_ids.children.second].add_tablets() = producer_tablets.tablets(i);
   	}
   	}
   	return Status::OK();
   	}

Ideally we can use the same logic in both these cases, but tbd.. Tablet splitting already provides the start and end keys for all the producer tablets, but some work would be required if we want these keys for the setup case as well.

[bmatican]

@hulien22 to confirm, does this mapping also dynamically change, at runtime, based on consumer cluster changes, eg: add/remove nodes, LB moving tablets around, etc?

[hulien22]

The mapping won't change since its purely a tablet id : tablet id mapping. So moving tablets around won't change anything, but splitting tablets does as that is creating new tablets that need to be added/removed from the mapping