【是否原创】是
【首发渠道】TiDB 社区

Placement rule 格式

系统的 placement-Rule 定义包括两个部分：ruleGroup 和 Rule，它们的关系是同一个 ruleGroup 下可以有多个 rule 规则，如下显示 ruleGroup ID 为 pd 的 rules 配置信息，上部分内容是 ruleGroup 信息，下面的 rules 是属于当前 ruleGroup 的 rule 列表。

» config placement-rules rule-bundle get pd
{
  "group_id": "pd",
  "group_index": 0,
  "group_override": false,
  "rules": [
    {
      "group_id": "pd",
      "id": "default",
      "start_key": "",
      "end_key": "",
      "role": "voter",
      "count": 3
    }
  ]
}

ruleGroup 只有三个 json 字段：

id：代表 ruleGroup 的唯一性 id、名称, string 类型，跟包含的 rule 规则下的 group_id 相同
index：各个 ruleGroup 之前的序号，int 类型，默认值为 0。index 越小，匹配的越早；另外就是 index 高的 ruleGroup 根据 override 配置如果为 true, 那么低 index 的 ruleGroup 规则将不会生效。
override：默认值 false，如果设置为 true，那么 index 较低的 ruleGroup 将不会生效

rule 有以下 json 字段：

group_id：ruleGroup 的 id，string 类型
id：同一个 ruleGroup 下面 rule 的唯一性 id，string 类型
index: rule 在当前 ruleGroup 下的序号，int 类型。 index 越小，匹配的越早；高 index 的 rule 根据 override 配置如果为 true, 那么低 index 的 rule 规则将不会生效。
override：布尔类型，如果设置为 true，那么 index 较低的 rule 将不会生效
start_key：rule 匹配的开始 key
end_key：rule 匹配的结束 key
role：string 类型，可以为 voter、leader、 follower、learner
count：目标 peer 数量，比如定义 3 个 tikv 副本，设置为 3.
label_constraints：这是个 json 数组，每个成员一个规则，定义了根据 label 筛选可用 store 的规则
location_labels：是 json string 数组类型，同 pd.replication.location-labels，用户表示 store 的物理标签，例如 ["zone", "rack", "host"]
isolation_level：string 类型，强制性的物理 store 隔离级别，比如 location_labels：["zone", "rack", "host"]， 而 isolation_level："rack"，那么 region peer 物理上不能在相同 rack 的 store 上

其中 [group_id, id] 确定了 rule 的唯一性。

label_constraints 是 json 数组，单个 item 具有以下字段：

key: store 的 label 名字，string 类型
Op: string 类型，可以为 "in"、"notIn"、"exists"、"notExists" 
Values: string 字符串

in: 满足条件的 store 的 label 值是 values 其中一个
notIn: 与 in 相反，label 值不在 values 列表里
exists：满足条件的 store 具有这个 label
notExists: 与 exists 相反，满足条件的 store 不具有这个 label

rule 生效算法

rule 排序规则

对所有的 rule 会根据 [GroupIndex, GroupID, Index, ID] 进行排序，来决定先后关系。

// Rules are ordered by (GroupID, Index, ID).
// 比较顺序 [GroupIndex, GroupID, Index, ID].
func compareRule(a, b *Rule) int {
	switch {
	case a.groupIndex() < b.groupIndex():
		return -1
	case a.groupIndex() > b.groupIndex():
		return 1
	case a.GroupID < b.GroupID:    // GroupID 和 ID 都是 string 啊。
		return -1
	case a.GroupID > b.GroupID:
		return 1
	case a.Index < b.Index:
		return -1
	case a.Index > b.Index:
		return 1
	case a.ID < b.ID:
		return -1
	case a.ID > b.ID:
		return 1
	default:
		return 0
	}
}

这里注意排序中用到 groupID 和 id 两个字段，但是这两个字段是 string 类型。

rule 配置生效规则

通过 rule 排序函数 compareRule 对所有适用于 [start_key, end_key] 的 rules 进行排序后，对增序的 rule 数组进行生效检查，检查按照以下准则（排序在后的可以理解为优先级高）：

ruleGroup 之间，高优先级的 ruleGroup 如果设置了 override 为 true，那么低优先级的 ruleGroup 所有 rule 都不会生效
同 ruleGroup 内，高优先级的 rule 如果设置了 override 为 true，那么同 ruleGroup 低优先级 rule 都不会生效
如果 1、2 没有 override 为 ture，那么低优先级的也会生效

举个例子：

ruleA: group_id: 4, id: 2, override: true
ruleB: group_id: 4, id: 1, override: true
ruleC: group_id: 3
ruleD: group_id: 2
RuleGroupA: id:4, override: false
RuleGroupB: id:3, override: true
RuleGroupC: id:2, override: false
最后生效的只有 ruleA 和 ruleC.

RuleGroupA、RuleGroupB、RuleGroupC 都没有设置 index, 那么默认值为 0，index 相同
由于 index 相同，根据 [GroupIndex, GroupID, Index, ID] 的比较顺序，那么 rule 排序后会是 [ruleD, ruleC, ruleB, ruleA] 的先后顺序
ruleC 的 groupID 为 3，所属的 RuleGroupB 将 override 设置为 ture, 那么 ruleC 前面的 ruleD 属于 RuleGroupC 将不会生效
ruleB 的 groupID 为 4，所属的 RuleGroupA override 为 false，那么 ruleC 会生效
对于同一个 ruleGroupA 内部，由于 ruleA 设置了 override: true，它使得 ruleB 不生效

所以最后将会以 [ruleC, ruleA] 的顺序应用这两个规则。

func prepareRulesForApply(rules []*Rule) []*Rule {
	var res []*Rule
	var i, j int
	for i = 1; i < len(rules); i++ {
		if rules[j].GroupID != rules[i].GroupID {
			if rules[i].group != nil && rules[i].group.Override {
				res = res[:0] // override all previous groups
			} else {
				res = append(res, rules[j:i]...) // save rules belong to previous group
			}
			j = i
		}
		if rules[i].Override {
			j = i // skip all previous rules in the same group
		}
	}
	return append(res, rules[j:]...)
}

Placement rule 配置更新

rule 是以 key-value 形式持久化在 storage 上了，key 为 groupID + ruleId 的编码。

SetRule、DeleteRule：只更新当前 rule，修改、创建、删除等，不会对所属同样 ruleGroup 其他 rule 改变。

SetRules：批量更新多个 rule，同样的不会对所属同样 ruleGroup 其他 rule 改变。

SetGroupBundle：覆盖更新 ruleGroup，把相同 ruleGroup 原来的 rule 删掉，再插入新 rule，同时更新 ruleGroup.

Range 适用规则维护

基于 rule 的 [start_key, end_key]，将 start_key、end_key 作为分隔点，分成连续的 range 段
计算不同 range 段需要匹配适用的 rule 规则列表
当有 region 需要检查的时候，根据 region 的 range 范围从维护的 range 规则中查找 rule 规则

Rule fit 优选算法

实质上就是遍历所有的可能性，在每一种可能性的情况下，根据优选算法，选择最优的方案：

// Pick the most suitable peer combination for the rule.
// Index specifies the position of the rule.
// returns true if it replaces `bestFit` with a better alternative.
func (w *fitWorker) fitRule(index int) bool {
	if index >= len(w.rules) {
		return false
	}

	var candidates []*fitPeer
	if checkRule(w.rules[index], w.stores) {
		// Only consider stores:
		// 1. Match label constraints
		// 2. Role match, or can match after transformed.
		// 3. Not selected by other rules.
		for _, p := range w.peers {    // 以这条规则去检查当前的peer.
			if MatchLabelConstraints(p.store, w.rules[index].LabelConstraints) &&
				p.matchRoleLoose(w.rules[index].Role) &&
				!p.selected {
				candidates = append(candidates, p)
			}
		}
	}

	count := w.rules[index].Count
	if len(candidates) < count {    // 这里都没有考虑down情况。
		count = len(candidates)
	}
	return w.enumPeers(candidates, nil, index, count)
}

// Recursively traverses all feasible peer combinations.
// For each combination, call `compareBest` to determine whether it is better
// than the existing option.
// Returns true if it replaces `bestFit` with a better alternative.
func (w *fitWorker) enumPeers(candidates, selected []*fitPeer, index int, count int) bool {
	if len(selected) == count {
		// We collect enough peers. End recursive.
		return w.compareBest(selected, index)
	}

	var better bool
	// 循环递归遍历出所有可能性。
	for i, p := range candidates {    // 递归循环。
		p.selected = true
		better = w.enumPeers(candidates[i+1:], append(selected, p), index, count) || better
		p.selected = false
	}
	return better

}

优选比较算法：

func compareRuleFit(a, b *RuleFit) int {
	switch {
	case len(a.Peers) < len(b.Peers):
		return -1
	case len(a.Peers) > len(b.Peers):
		return 1
	case len(a.PeersWithDifferentRole) > len(b.PeersWithDifferentRole):
		return -1
	case len(a.PeersWithDifferentRole) < len(b.PeersWithDifferentRole):
		return 1
	case a.IsolationScore < b.IsolationScore:
		return -1
	case a.IsolationScore > b.IsolationScore:
		return 1
	default:
		return 0
	}
}

这里算法感觉还是有挺多疑惑的！！！

fitRule 函数是从目前 region 的 peer 中，对比选择最优的方案，没有考虑非 peer 的其他 store.
fitRule 函数没有判断 peer store 的情况，有可能某个 peer store 有问题，但是计算过程没有考虑.
fitRule 函数原来 peer 数为 4 个，配置的副本数为 3 个，计算过程中只要求 peer count 为 3，那会多一个，被随机的选定，然后被清理吧
compareRuleFit 最优算法，由于先后 rule 列表中，每个 rule 选择都不能比以前差，并没法保证全局最优。

Region 调度

region check 函数

// Check checks if the region matches placement rules and returns Operator to
// fix it.
func (c *RuleChecker) Check(region *core.RegionInfo) *operator.Operator {
	...
	fit := c.cluster.FitRegion(region)
	if len(fit.RuleFits) == 0 {
		...
		// If the region matches no rules, the most possible reason is it spans across
		// multiple rules.
		return c.fixRange(region)
	}
	op, err := c.fixOrphanPeers(region, fit)
	if err == nil && op != nil {
		return op
	}
	log.Debug("fail to fix orphan peer", errs.ZapError(err))
	for _, rf := range fit.RuleFits {
		op, err := c.fixRulePeer(region, fit, rf)
		if err != nil {
			log.Debug("fail to fix rule peer", zap.String("rule-group", rf.Rule.GroupID), zap.String("rule-id", rf.Rule.ID), errs.ZapError(err))
			continue
		}
		if op != nil {
			return op
		}
	}
	return nil
}

基于现在的 region peer，调用 fitRegion 函数，在 peer 之间重新分配角色，选择最优的
对于 region 没有匹配到 rule 规则，会对 rule 进行分割
如果所有 rule 规则副本数都满足，那么清理多余的副本(orphan peer)，但是检查 rule 是否满足是简单通过 peer 数是否满足副本定义，没有判断 peer 是否正常等，所以感觉这方法不成熟
根据 rule 排序后的列表，从前向后，依次调度使其满足 rule 规则。
- 如果 rule 副本数不够，添加副本
- 对于 down peer、offline peer，替换副本
- 对于 peer 角色变化的，进行角色转移
  - leaner提升为voter
  - voter 提升为 leader
  - leader 降级为 follower，这里是用 leader 转移的方法实现的，找到一个可以作为 leader 的，通过从旧 leader 转移到新 leader 方法实现，防止长时间 raft 集群没有 leader 吧，但是这里找新 leader 是从现有 peer 判断的，没有从 fitRegion 最优中找
- 为当前的 rule，从非 peer store 中尝试选择个更好的 peer store，替换已有的 peer.
region check 函数对于 rule 规则，总是从前向后依次匹配，只要第一个 rule 规则没有适配好，那总是在适配第一个，所以在定义 rule 的时候，这一点必须要明晰。

balance leader 函数

实质就是比较提升 leader 以后，调用 fitRegion，看目标得分，选择最高分的方案，不怎么好用啊。

func (f *ruleLeaderFitFilter) Target(opt *config.PersistOptions, store *core.StoreInfo) bool {
	targetPeer := f.region.GetStorePeer(store.GetID())
	if targetPeer == nil {
		log.Warn("ruleLeaderFitFilter couldn't find peer on target Store", zap.Uint64("target-store", store.GetID()))
		return false
	}
	copyRegion := createRegionForRuleFit(f.region.GetStartKey(), f.region.GetEndKey(),
		f.region.GetPeers(), f.region.GetLeader(),
		core.WithLeader(targetPeer))
	newFit := f.fitter.FitRegion(copyRegion)
	return placement.CompareRegionFit(f.oldFit, newFit) <= 0
}

balance region 函数

执行 region peer 替换后，调用 fitRegion 函数计算得分，判断是否要替换。

func (f *ruleFitFilter) Target(opt *config.PersistOptions, store *core.StoreInfo) bool {
	region := createRegionForRuleFit(f.region.GetStartKey(), f.region.GetEndKey(),
		f.region.GetPeers(), f.region.GetLeader(),
		core.WithReplacePeerStore(f.srcStore, store.GetID()))
	newFit := f.fitter.FitRegion(region)
	return placement.CompareRegionFit(f.oldFit, newFit) <= 0
}

其他

例如 region merger 等其他调度器，没有考虑 rule 信息等。
调度算法有很多场景感觉还没考虑到，不够完善。
使用的话尽量让 rule 规则简单，不要太复杂。
使用体验不错的方式：alter table t set tiflash replica 2 .

Placement Rules 原理