Enhance the region balance of the 1M tables imported by lightning

[HuSharp]

Development Task

Background

• PD ensures that the table level's scatter, but it doesn't care about table-to-table, which relies on balance-scheduler.
• Balance-Region will not schedule empty region, There is a hardcode in
  

  pd/pkg/schedule/filter/region_filters.go

  Lines 150 to 153 in 7e18a69

  	// isEmptyRegionAllowBalance returns true if the region is not empty or the number of regions is too small.
  	func isEmptyRegionAllowBalance(cluster sche.SharedCluster, region *core.RegionInfo) bool {
  	return region.GetApproximateSize() > core.EmptyRegionApproximateSize || cluster.GetTotalRegionCount() < core.InitClusterRegionThreshold
  	}

• When lightning imports tables, the table's region key is encoded in the table ID, while table IDs are created consecutively(basically next to each other). https://github.com/tikv/client-go/blob/6ba909c4ad2de65b5b36d0e5036d0a85f3154cc0/tikv/split_region.go#L241-L247

Problems faced

For lightning importing 1 million tables(one table corresponds to one region), even though there are more than 3 stores, consecutive region keys will generate a lot of regions aggregations in the first 3 stores. And since regions are not scheduled, the three stores have a high probability of OOM.

[River2000i]

i'm interesting in the issue.

[River2000i]

/assign @River2000i

[River2000i]

When lightning imports tables, the table's region key is encoded in the table ID, while table IDs are created consecutively(basically next to each other). https://github.com/tikv/client-go/blob/6ba909c4ad2de65b5b36d0e5036d0a85f3154cc0/tikv/split_region.go#L241-L247

PD schedule scatter region base on region_count in all store. And schedule new region to fewest store.

pd/pkg/schedule/scatter/region_scatterer.go

Line 346 in 13174b5

newPeer := r.selectNewPeer(context, group, peer, filters)

PD will compare region_count base on the group. For now, gourp define by table ID.(every table belong to a group)

pd/pkg/schedule/scatter/region_scatterer.go

Line 367 in 13174b5

targetLeader, leaderStorePickedCount := r.selectAvailableLeaderStore(group, region, leaderCandidateStores, r.ordinaryEngine)

Summary:

1. If there are lots of new split empty regions(close kv range), the region will split on the same store. In group level, scatter base on the region_count in a group. It will not scatter region to the store , which not contain the region belongs to the group.
2. In cluster level, scatter region base on the region_count in whole cluster. Region is balanced in whole cluster, but not balanced in group or table level.

root cause:
selectNewPeer() will pick origin store in first time trigger scatter region. Since it will compare all stores's region count in engineContext, but first time call context.selectedPeer.Get() will get 0 in all stores, so it will not scatter region in all stores.

pd/pkg/schedule/scatter/region_scatterer.go

Line 444 in 13174b5

func (r *RegionScatterer) selectNewPeer(context engineContext, group string, peer *metapb.Peer, filters []filter.Filter) *metapb.Peer {

If we want to schedule scatter region in cluster level, we can call ScatterRegion with the same group. It will be an options for caller.