作者： jiyf 原文来源：https://tidb.net/blog/48de3d68
【是否原创】是
【首发渠道】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 匹配的开始 keyend_key：rule 匹配的结束 keyrole：string 类型，可以为 voter、leader、 follower、learnercount：目标 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: trueruleB: group_id: 4, id: 1, override: trueruleC: group_id: 3ruleD: group_id: 2RuleGroupA: id:4, override: falseRuleGroupB: id:3, override: trueRuleGroupC: 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 .
评论