schedule: add region merge checker by Connor1996 · Pull Request #839 · tikv/pd

Connor1996 · 2017-11-08T08:00:54Z

in some case, region size is so small even empty, it would be better to merge it with adjacent region if allowed. So introduce region merge checker to detect whether it needs to merge every time receive heartbeat from region. If yes, pd schedule region's peers to make sure that two regions to be merged in same stores, and then launch a merge request to tikv.

disksing · 2017-11-10T02:28:06Z

server/coordinator.go

 	}
+
+	if op1, op2 := c.mergeChecker.Check(region); op1 != nil && op2 != nil {
+		if c.addOperator(op1) == true {


if c.addOperator(op1) {

disksing · 2017-11-10T02:31:35Z

server/coordinator.go

+
+	if op1, op2 := c.mergeChecker.Check(region); op1 != nil && op2 != nil {
+		if c.addOperator(op1) == true {
+			if c.addOperator(op2) == false {


if !c.addOperator(op2) {

disksing · 2017-11-10T02:33:05Z

server/coordinator.go

+	if op1, op2 := c.mergeChecker.Check(region); op1 != nil && op2 != nil {
+		if c.addOperator(op1) == true {
+			if c.addOperator(op2) == false {
+				c.removeOperator(op1)


The operator may have been sent to tikv already. I think it will better to check operators before add.

disksing · 2017-11-10T02:34:04Z

server/coordinator.go

 		}
 		c.hbStreams.sendMsg(region, cmd)
+	case schedule.MergeRegion:
+		if s.IsFake == true {


if s.IsFake {

disksing · 2017-11-10T02:44:16Z

server/schedule/merge_checker.go

+	var target *core.RegionInfo
+	prev, next := m.cluster.GetAdjacentRegions(region)
+	// check key to avoid key range hole
+	if prev != nil && bytes.Compare(prev.Region.EndKey, region.Region.StartKey) != 0 {


Maybe check it inside getAdjacentRegions?

disksing · 2017-11-10T02:48:24Z

server/schedule/merge_checker.go

+}
+
+func (m *MergeChecker) matchPeers(source *core.RegionInfo, target *core.RegionInfo) ([]OperatorStep, error) {
+	storeIDs := make(map[uint64]bool)


We usually use struct{} instead of bool when using map as set.

disksing · 2017-11-10T02:51:47Z

server/schedule/operator.go

+// IsFinish checks if cuurent step is finished
+func (mr MergeRegion) IsFinish(region *core.RegionInfo) bool {
+	// In view of pd doesn't know merge is success or not
+	// this step will not finish, so just let operator timeout and then be removed


How about save its key range then check if key range expands?

disksing · 2017-11-10T02:53:48Z

server/schedule/operator.go

+
+// Influence calculates the store difference that current step make
+func (mr MergeRegion) Influence(opInfluence OpInfluence, region *core.RegionInfo) {
+	// merge influence nothing


Seems it decreases region count, although we don't use it for balancing now.

disksing · 2017-11-10T02:54:29Z

server/schedule/operator.go

+	FromRegion uint64
+	ToRegion   uint64
+	Direction  pdpb.MergeDirection
+	IsFake     bool


What's this used for?

there are two regions involved in merge process, so to keep them from other scheduler, both of them should add operator. But actually, tikv just need one region to get the merge request, thus use a IsFake mark to indicate that this region doesn't need to send merge request to tikv

I don't think IsFake is reasonable name here, maybe IsPassive. Also need some comments here.

disksing · 2017-11-10T02:57:19Z

server/config.go

 	MaxPendingPeerCount uint64 `toml:"max-pending-peer-count,omitempty" json:"max-pending-peer-count"`
+	// If the size of region is smaller than this value,
+	// it will try to merge with adjacent regions.
+	MaxMergeRegionSize uint64 `toml:"max-merge-region-size,omitempty" json:"max-merge-region-size"`


I think we need another configuration to restrict maximum region size after merge, or the new region may need to split again soon after.

siddontang · 2017-11-15T02:00:15Z

server/core/region_tree.go

+		next = i.(*regionItem)
+		return false
+	})
+	item = &regionItem{region: &metapb.Region{StartKey: region.StartKey}}


why assign the item again?

siddontang · 2017-11-15T02:06:01Z

server/core/region_tree.go

+		return false
+	})
+	item = &regionItem{region: &metapb.Region{StartKey: region.StartKey}}
+	t.tree.AscendGreaterOrEqual(item, func(i btree.Item) bool {


The AscendGreaterOrEqual will iterate in [item, last], so I am confused that why you set prev here?

the item store in region_tree is in reversed order, namely startkey "a" is greater than "b". https://github.com/Connor1996/pd/blob/e81d31ff04bdb282b66521f09f1562088e8869e7/server/core/region_tree.go#L30

please add a comment

siddontang · 2018-03-19T08:29:54Z

server/coordinator.go

 		}
 		c.hbStreams.sendMsg(region, cmd)
+	case schedule.MergeRegion:
+		if s.IsPassive {


what is passive?

you can see the explanation at where it defines

siddontang · 2018-03-21T05:22:53Z

do we disable this by default?

disksing · 2018-03-21T08:21:09Z

pdctl/command/region_command.go

+func NewRegionWithSiblingCommand() *cobra.Command {
+	r := &cobra.Command{
+		Use:   "sibling <region_id>",
+		Short: "show the sibling region of specific region",


sibling regions?

disksing · 2018-03-21T08:40:01Z

server/handler.go

+
+	if bytes.Compare(region.StartKey, target.EndKey) != 0 && bytes.Compare(region.EndKey, target.StartKey) != 0 {
+		return ErrRegionNotAdjacent
+	}


What if merge the first region (start key is nil) with the last region (end key is nil) ?

disksing · 2018-03-21T08:43:11Z

server/schedule/merge_checker.go

+	if m.cluster.IsRegionHot(region.GetId()) {
+		checkerCounter.WithLabelValues("merge_checker", "hot_region").Inc()
+		return nil, nil
+	}


I think we can also skip the region if its replica count is different from default configuration.

disksing · 2018-03-21T08:47:52Z

PTAL @nolouch

nolouch · 2018-03-21T12:24:31Z

server/schedule/merge_checker.go

+	prev, next := m.cluster.GetAdjacentRegions(region)
+
+	target = m.checkTarget(region, prev, target)
+	target = m.checkTarget(region, next, target)


I think we also need to consider the state of target peers.

disksing · 2018-03-21T16:51:34Z

server/handler.go

-	if bytes.Compare(region.StartKey, target.EndKey) != 0 && bytes.Compare(region.EndKey, target.StartKey) != 0 {
+	// for the case first region (start key is nil) with the last region (end key is nil) but not adjacent
+	if (bytes.Compare(region.StartKey, target.EndKey) != 0 || region.StartKey == nil) &&
+		(bytes.Compare(region.EndKey, target.StartKey) != 0 || region.EndKey == nil) {


Do not use == nil to check empty []byte. Use len(b) == 0 instead.

disksing · 2018-03-22T05:51:14Z

LGTM.

Connor1996 added 3 commits November 8, 2017 15:51

schedule: add region merge checker

b2cc376

fix get adjacent region and add test

46a1e5c

fix check key range hole and add test

16a9ca7

Connor1996 force-pushed the region-merge-checker branch from 5825464 to 16a9ca7 Compare November 9, 2017 07:58

Connor1996 added 2 commits November 9, 2017 16:29

update kvproto

99fb18c

fit for kvproto

4100389

Connor1996 changed the title ~~[WIP] schedule: add region merge checker~~ [DNM] schedule: add region merge checker Nov 9, 2017

Connor1996 requested review from disksing, nolouch and siddontang November 9, 2017 08:59

merge master

b0331ef

Connor1996 force-pushed the region-merge-checker branch from aedf20e to b0331ef Compare November 9, 2017 09:17

disksing reviewed Nov 10, 2017

View reviewed changes

disksing added the DNM label Nov 10, 2017

disksing added this to the 1.1 milestone Nov 10, 2017

tiny adjust

94e00d5

Connor1996 force-pushed the region-merge-checker branch 2 times, most recently from ade7b64 to 97fe966 Compare November 10, 2017 05:05

Connor1996 added 2 commits November 10, 2017 13:38

check key range hole in getAdjacentRegions

501f8e4

check operators before add

230b0e3

Connor1996 force-pushed the region-merge-checker branch from 97fe966 to a57ec0f Compare November 10, 2017 05:39

Connor1996 added 2 commits November 10, 2017 14:28

IsFinish check if key range expands

22741ca

change influence

e89b7ff

Connor1996 force-pushed the region-merge-checker branch from a57ec0f to e89b7ff Compare November 10, 2017 06:31

Connor1996 added 3 commits November 10, 2017 15:01

add merge operator test

f086928

make merge-region-size unconfigurable temporarily

4f2aca5

check timeout operator in background

e81d31f

siddontang reviewed Nov 15, 2017

View reviewed changes

tiny clean

7089dfa

siddontang reviewed Mar 19, 2018

View reviewed changes

Connor1996 added 4 commits March 20, 2018 11:42

add region sibling command for pd-ctl

14069c2

Merge branch 'master' into region-merge-checker

c98fb24

fix format

bff23d3

fix test

74f28db

Connor1996 force-pushed the region-merge-checker branch from eb9e6f5 to 74f28db Compare March 20, 2018 06:13

skip down peers and pending peers

ee9825a

Connor1996 added 2 commits March 21, 2018 14:21

Merge branch 'master' into region-merge-checker

464b11b

skip zero

a4f9498

disksing reviewed Mar 21, 2018

View reviewed changes

address comment

d8fabe7

nolouch reviewed Mar 21, 2018

View reviewed changes

address comment

194498a

disksing reviewed Mar 21, 2018

View reviewed changes

address comment

a32f0ea

disksing and others added 3 commits March 22, 2018 13:51

Merge branch 'master' into region-merge-checker

90bb7c1

Merge branch 'master' into region-merge-checker

c1606c1

fix conflict

3ed34eb

Connor1996 force-pushed the region-merge-checker branch from 14a1cc2 to 3ed34eb Compare March 22, 2018 06:32

Merge branch 'master' into region-merge-checker

6653d74

Connor1996 merged commit 0889d2c into tikv:master Mar 22, 2018

Connor1996 deleted the region-merge-checker branch March 22, 2018 10:13

gengliqi mentioned this pull request Apr 27, 2020

raftstore: rely on the all-target-peer-exist guarantee during merging tikv/tikv#7672

Merged

gengliqi mentioned this pull request Jun 5, 2020

raftstore: rely on the all-target-peer-exist guarantee during merging(#7672) tikv/tikv#8048

Merged

Conversation

Connor1996 commented Nov 8, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

siddontang commented Mar 21, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

disksing commented Mar 21, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

disksing commented Mar 22, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants