Repository: tikv/pd
Pull request #5720 (2022-11-21 10:49:09)

core: separate region lock
Signed-off-by: Ryan Leung <rleungx@gmail.com>

<!--
Thank you for working on PD! Please read PD's [CONTRIBUTING](https://github.com/tikv/pd/blob/master/CONTRIBUTING.md) document **BEFORE** filing this PR.
PR Title Format:
1. pkg [, pkg2, pkg3]: what's changed
2. *: what's changed
-->

### What problem does this PR solve?

<!--

Please create an issue first to describe the problem.
There MUST be one line starting with "Issue Number:  " and 
linking the relevant issues via the "close" or "ref".
For more info, check https://github.com/tikv/pd/blob/master/CONTRIBUTING.md#linking-issues.

-->
Issue Number: Ref #5712, #5586, #5648.

### What is changed and how does it work?
master:
```
[2022/11/23 15:13:15.599 +08:00] [INFO] [main.go:452] ["update speed of each category"] [rps=56747.8917] [save-tree=3404.8735] [save-kv=2269.9157] [save-space=8512.1838] [save-flow=19861.7621] [skip=28286.8378]
[2022/11/23 15:13:15.706 +08:00] [INFO] [main.go:398] ["region heartbeat stats"] [total=35.2433s] [slowest=34.8643s] [fastest=0.0000s] [average=16.5034s] [stddev=10.3169s] [rps=56748.3756]
```
this branch:
```
[2022/11/23 15:20:38.078 +08:00] [INFO] [main.go:452] ["update speed of each category"] [rps=80912.1055] [save-tree=4854.7263] [save-kv=3236.4842] [save-space=12136.8158] [save-flow=28319.2369] [skip=40331.8527]
[2022/11/23 15:20:38.239 +08:00] [INFO] [main.go:398] ["region heartbeat stats"] [total=24.7180s] [slowest=23.8633s] [fastest=0.0000s] [average=11.1023s] [stddev=6.8950s] [rps=80912.7660]
```

<!--

You could use the "commit message" code block to add more description to the final commit message.
For more info, check https://github.com/tikv/pd/blob/master/CONTRIBUTING.md#format-of-the-commit-message.

-->

```commit-message
```

### Check List

<!-- Remove the items that are not applicable. -->

Tests

<!-- At least one of these tests must be included. -->

- Unit test

### Release note

<!-- A bugfix or a new feature needs a release note. If there is no need release note, just uncomment the below line. -->

```release-note
None
```


ti-chi-bot: [REVIEW NOTIFICATION]

This pull request has not been approved.


To complete the [pull request process](https://book.prow.tidb.net/#/en/workflows/pr), please ask the reviewers in the [list](https://prow.tidb.net/tichi/repos/tikv/pd/pulls/5720/owners) to review by filling `/cc @reviewer` in the comment.
After your PR has acquired the required number of LGTMs, you can assign this pull request to the committer in the [list](https://prow.tidb.net/tichi/repos/tikv/pd/pulls/5720/owners) by filling  `/assign @committer` in the comment to help you merge this pull request.

The full list of commands accepted by this bot can be found [here](https://prow.tidb.net/command-help?repo=tikv%2Fpd).

<details>

Reviewer can indicate their review by submitting an approval review.
Reviewer can cancel approval by submitting a request changes review.
</details>

<!--Review Notification Identifier-->
ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

codecov[bot]: # [Codecov](https://codecov.io/gh/tikv/pd/pull/5720?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) Report
Base: **75.65**% // Head: **75.67**% // Increases project coverage by **`+0.02%`** :tada:
> Coverage data is based on head [(`e2af7e3`)](https://codecov.io/gh/tikv/pd/pull/5720?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) compared to base [(`7a040fd`)](https://codecov.io/gh/tikv/pd/commit/7a040fd3d64868d1b05d156cdcf334ce19b6acf2?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv).
> Patch coverage: 86.28% of modified lines in pull request are covered.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master    #5720      +/-   ##
==========================================
+ Coverage   75.65%   75.67%   +0.02%     
==========================================
  Files         329      329              
  Lines       32689    32754      +65     
==========================================
+ Hits        24730    24786      +56     
- Misses       5817     5836      +19     
+ Partials     2142     2132      -10     
```

| Flag | Coverage Δ | |
|---|---|---|
| unittests | `75.67% <86.28%> (+0.02%)` | :arrow_up: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/tikv/pd/pull/5720?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) | Coverage Δ | |
|---|---|---|
| [server/core/region.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL2NvcmUvcmVnaW9uLmdv) | `89.94% <85.18%> (-2.27%)` | :arrow_down: |
| [server/core/basic\_cluster.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL2NvcmUvYmFzaWNfY2x1c3Rlci5nbw==) | `90.69% <100.00%> (+0.37%)` | :arrow_up: |
| [server/schedule/range\_cluster.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3NjaGVkdWxlL3JhbmdlX2NsdXN0ZXIuZ28=) | `83.63% <100.00%> (+0.30%)` | :arrow_up: |
| [server/id/id.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL2lkL2lkLmdv) | `83.05% <0.00%> (-10.17%)` | :arrow_down: |
| [server/region\_syncer/client.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3JlZ2lvbl9zeW5jZXIvY2xpZW50Lmdv) | `81.34% <0.00%> (-4.48%)` | :arrow_down: |
| [server/region\_syncer/server.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3JlZ2lvbl9zeW5jZXIvc2VydmVyLmdv) | `82.96% <0.00%> (-4.40%)` | :arrow_down: |
| [server/election/leadership.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL2VsZWN0aW9uL2xlYWRlcnNoaXAuZ28=) | `75.25% <0.00%> (-2.07%)` | :arrow_down: |
| [server/schedulers/hot\_region\_v2.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3NjaGVkdWxlcnMvaG90X3JlZ2lvbl92Mi5nbw==) | `88.30% <0.00%> (-1.17%)` | :arrow_down: |
| [server/schedule/operator\_controller.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-c2VydmVyL3NjaGVkdWxlL29wZXJhdG9yX2NvbnRyb2xsZXIuZ28=) | `86.26% <0.00%> (-1.13%)` | :arrow_down: |
| [pkg/btree/btree.go](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv#diff-cGtnL2J0cmVlL2J0cmVlLmdv) | `86.26% <0.00%> (-0.97%)` | :arrow_down: |
| ... and [18 more](https://codecov.io/gh/tikv/pd/pull/5720/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv) | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/tikv/pd/pull/5720?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=tikv).

ti-chi-bot: 
[FORMAT CHECKER NOTIFICATION]

**Notice**: To remove the `do-not-merge/needs-linked-issue` label, please provide the linked issue number on one line in the PR body, for example: `Issue Number: close #123` or `Issue Number: ref #456`, multiple issues should use full syntax for each issue and be separated by a comma, like: `Issue Number: close #123, ref #456`.

<sub>:open_book: For more info, you can check the ["Linking issues"](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md#linking-issues) section in the [CONTRIBUTING.md](https://github.com/tikv/tikv/blob/master/CONTRIBUTING.md).</sub>


<!--Checker Notification Identifier-->

ti-chi-bot: @rleungx: PR needs rebase.

<details>

Instructions for interacting with me using PR comments are available [here](https://git.k8s.io/community/contributors/guide/pull-requests.md).  If you have questions or suggestions related to my behavior, please file an issue against the [kubernetes/test-infra](https://github.com/kubernetes/test-infra/issues/new?title=Prow%20issue:) repository.
</details>
rleungx: /hold
rleungx: /hold cancel
rleungx: /merge
ti-chi-bot: @rleungx: It seems you want to merge this PR, I will help you trigger all the tests:

/run-all-tests


<details>

Instructions for interacting with me using PR comments are available [here](https://prow.tidb.net/command-help).  If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.
</details>
ti-chi-bot: This pull request has been accepted and is ready to merge. <details>Commit hash: 99319505ddb7c7afefe7ab5b2c15ee73d1e5fe43</details>
ti-chi-bot: @rleungx: Your PR was out of date, I have automatically updated it for you.

At the same time I will also trigger all tests for you:

/run-all-tests

If the CI test fails, you just re-trigger the test that failed and the bot will merge the PR for you after the CI passes.


<details>

Instructions for interacting with me using PR comments are available [here](https://prow.tidb.net/command-help).  If you have questions or suggestions related to my behavior, please file an issue against the [ti-community-infra/tichi](https://github.com/ti-community-infra/tichi/issues/new?title=Prow%20issue:) repository.
</details>

Patch:
diff --git a/pkg/mock/mockcluster/mockcluster.go b/pkg/mock/mockcluster/mockcluster.go
index c751cf845..854996dd9 100644
--- a/pkg/mock/mockcluster/mockcluster.go
+++ b/pkg/mock/mockcluster/mockcluster.go
@@ -97,7 +97,7 @@ func (mc *Cluster) GetAllocator() id.Allocator {
 
 // ScanRegions scans region with start key, until number greater than limit.
 func (mc *Cluster) ScanRegions(startKey, endKey []byte, limit int) []*core.RegionInfo {
-	return mc.Regions.ScanRange(startKey, endKey, limit)
+	return mc.ScanRange(startKey, endKey, limit)
 }
 
 // LoadRegion puts region info without leader
@@ -113,11 +113,6 @@ func (mc *Cluster) GetStoresLoads() map[uint64][]float64 {
 	return mc.HotStat.GetStoresLoads()
 }
 
-// GetStoreRegionCount gets region count with a given store.
-func (mc *Cluster) GetStoreRegionCount(storeID uint64) int {
-	return mc.Regions.GetStoreRegionCount(storeID)
-}
-
 // GetStore gets a store with a given store ID.
 func (mc *Cluster) GetStore(storeID uint64) *core.StoreInfo {
 	return mc.Stores.GetStore(storeID)
@@ -659,11 +654,11 @@ func (mc *Cluster) updateStorageStatistics(storeID uint64, update func(*pdpb.Sto
 
 // UpdateStoreStatus updates store status.
 func (mc *Cluster) UpdateStoreStatus(id uint64) {
-	leaderCount := mc.Regions.GetStoreLeaderCount(id)
-	regionCount := mc.Regions.GetStoreRegionCount(id)
-	pendingPeerCount := mc.Regions.GetStorePendingPeerCount(id)
-	leaderSize := mc.Regions.GetStoreLeaderRegionSize(id)
-	regionSize := mc.Regions.GetStoreRegionSize(id)
+	leaderCount := mc.GetStoreLeaderCount(id)
+	regionCount := mc.GetStoreRegionCount(id)
+	pendingPeerCount := mc.GetStorePendingPeerCount(id)
+	leaderSize := mc.GetStoreLeaderRegionSize(id)
+	regionSize := mc.GetStoreRegionSize(id)
 	store := mc.Stores.GetStore(id)
 	stats := &pdpb.StoreStats{}
 	stats.Capacity = defaultStoreCapacity
diff --git a/server/core/basic_cluster.go b/server/core/basic_cluster.go
index e6bc2bb8d..e395a56b9 100644
--- a/server/core/basic_cluster.go
+++ b/server/core/basic_cluster.go
@@ -15,8 +15,6 @@
 package core
 
 import (
-	"bytes"
-
 	"github.com/pingcap/kvproto/pkg/metapb"
 	"github.com/pingcap/log"
 	"github.com/tikv/pd/pkg/errs"
@@ -32,10 +30,7 @@ type BasicCluster struct {
 		*StoresInfo
 	}
 
-	Regions struct {
-		mu syncutil.RWMutex
-		*RegionsInfo
-	}
+	*RegionsInfo
 }
 
 // NewBasicCluster creates a BasicCluster.
@@ -46,10 +41,7 @@ func NewBasicCluster() *BasicCluster {
 			*StoresInfo
 		}{StoresInfo: NewStoresInfo()},
 
-		Regions: struct {
-			mu syncutil.RWMutex
-			*RegionsInfo
-		}{RegionsInfo: NewRegionsInfo()},
+		RegionsInfo: NewRegionsInfo(),
 	}
 }
 
@@ -158,14 +150,7 @@ func (bc *BasicCluster) ResetStoreLimit(storeID uint64, limitType storelimit.Typ
 
 // UpdateStoreStatus updates the information of the store.
 func (bc *BasicCluster) UpdateStoreStatus(storeID uint64) {
-	bc.Regions.mu.RLock()
-	leaderCount := bc.Regions.GetStoreLeaderCount(storeID)
-	regionCount := bc.Regions.GetStoreRegionCount(storeID)
-	witnessCount := bc.Regions.GetStoreWitnessCount(storeID)
-	pendingPeerCount := bc.Regions.GetStorePendingPeerCount(storeID)
-	leaderRegionSize := bc.Regions.GetStoreLeaderRegionSize(storeID)
-	regionSize := bc.Regions.GetStoreRegionSize(storeID)
-	bc.Regions.mu.RUnlock()
+	leaderCount, regionCount, witnessCount, pendingPeerCount, leaderRegionSize, regionSize := bc.RegionsInfo.GetStoreStats(storeID)
 	bc.Stores.mu.Lock()
 	defer bc.Stores.mu.Unlock()
 	bc.Stores.UpdateStoreStatus(storeID, leaderCount, regionCount, pendingPeerCount, leaderRegionSize, regionSize, witnessCount)
@@ -194,199 +179,18 @@ func (bc *BasicCluster) DeleteStore(store *StoreInfo) {
 
 /* Regions read operations */
 
-// GetRegion searches for a region by ID.
-func (bc *BasicCluster) GetRegion(regionID uint64) *RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetRegion(regionID)
-}
-
-// GetRegions gets all RegionInfo from regionMap.
-func (bc *BasicCluster) GetRegions() []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetRegions()
-}
-
-// GetMetaRegions gets a set of metapb.Region from regionMap.
-func (bc *BasicCluster) GetMetaRegions() []*metapb.Region {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetMetaRegions()
-}
-
-// GetStoreRegions gets all RegionInfo with a given storeID.
-func (bc *BasicCluster) GetStoreRegions(storeID uint64) []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStoreRegions(storeID)
-}
-
 // GetLeaderStoreByRegionID returns the leader store of the given region.
 func (bc *BasicCluster) GetLeaderStoreByRegionID(regionID uint64) *StoreInfo {
-	bc.Regions.mu.RLock()
-	region := bc.Regions.GetRegion(regionID)
+	region := bc.RegionsInfo.GetRegion(regionID)
 	if region == nil || region.GetLeader() == nil {
-		bc.Regions.mu.RUnlock()
 		return nil
 	}
-	bc.Regions.mu.RUnlock()
 
 	bc.Stores.mu.RLock()
 	defer bc.Stores.mu.RUnlock()
 	return bc.Stores.GetStore(region.GetLeader().GetStoreId())
 }
 
-// GetAdjacentRegions returns region's info that is adjacent with specific region.
-func (bc *BasicCluster) GetAdjacentRegions(region *RegionInfo) (*RegionInfo, *RegionInfo) {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetAdjacentRegions(region)
-}
-
-// GetRangeHoles returns all range holes, i.e the key ranges without any region info.
-func (bc *BasicCluster) GetRangeHoles() [][]string {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetRangeHoles()
-}
-
-const randomRegionMaxRetry = 10
-
-// RandFollowerRegions returns a random region that has a follower on the store.
-func (bc *BasicCluster) RandFollowerRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.RandFollowerRegions(storeID, ranges, randomRegionMaxRetry)
-}
-
-// RandLeaderRegions returns a random region that has leader on the store.
-func (bc *BasicCluster) RandLeaderRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.RandLeaderRegions(storeID, ranges, randomRegionMaxRetry)
-}
-
-// RandPendingRegions returns a random region that has a pending peer on the store.
-func (bc *BasicCluster) RandPendingRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.RandPendingRegions(storeID, ranges, randomRegionMaxRetry)
-}
-
-// RandLearnerRegions returns a random region that has a learner peer on the store.
-func (bc *BasicCluster) RandLearnerRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.RandLearnerRegions(storeID, ranges, randomRegionMaxRetry)
-}
-
-// GetRegionCount gets the total count of RegionInfo of regionMap.
-func (bc *BasicCluster) GetRegionCount() int {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetRegionCount()
-}
-
-// GetStoreRegionCount gets the total count of a store's leader and follower RegionInfo by storeID.
-func (bc *BasicCluster) GetStoreRegionCount(storeID uint64) int {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStoreLeaderCount(storeID) + bc.Regions.GetStoreFollowerCount(storeID) + bc.Regions.GetStoreLearnerCount(storeID)
-}
-
-// GetStoreLeaderCount get the total count of a store's leader RegionInfo.
-func (bc *BasicCluster) GetStoreLeaderCount(storeID uint64) int {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStoreLeaderCount(storeID)
-}
-
-// GetStoreFollowerCount get the total count of a store's follower RegionInfo.
-func (bc *BasicCluster) GetStoreFollowerCount(storeID uint64) int {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStoreFollowerCount(storeID)
-}
-
-// GetStorePendingPeerCount gets the total count of a store's region that includes pending peer.
-func (bc *BasicCluster) GetStorePendingPeerCount(storeID uint64) int {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStorePendingPeerCount(storeID)
-}
-
-// GetStoreWitnessCount gets the total count of a store's witness RegionInfo.
-func (bc *BasicCluster) GetStoreWitnessCount(storeID uint64) int {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStoreWitnessCount(storeID)
-}
-
-// GetStoreLeaderRegionSize get total size of store's leader regions.
-func (bc *BasicCluster) GetStoreLeaderRegionSize(storeID uint64) int64 {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStoreLeaderRegionSize(storeID)
-}
-
-// GetStoreRegionSize get total size of store's regions.
-func (bc *BasicCluster) GetStoreRegionSize(storeID uint64) int64 {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetStoreRegionSize(storeID)
-}
-
-// GetAverageRegionSize returns the average region approximate size.
-func (bc *BasicCluster) GetAverageRegionSize() int64 {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetAverageRegionSize()
-}
-
-// GetRegionByKey searches RegionInfo from regionTree.
-func (bc *BasicCluster) GetRegionByKey(regionKey []byte) *RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetRegionByKey(regionKey)
-}
-
-// GetPrevRegionByKey searches previous RegionInfo from regionTree.
-func (bc *BasicCluster) GetPrevRegionByKey(regionKey []byte) *RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetPrevRegionByKey(regionKey)
-}
-
-// ScanRange scans regions intersecting [start key, end key), returns at most
-// `limit` regions. limit <= 0 means no limit.
-func (bc *BasicCluster) ScanRange(startKey, endKey []byte, limit int) []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.ScanRange(startKey, endKey, limit)
-}
-
-// GetRangeCount returns the number of regions that overlap with the range [startKey, endKey).
-func (bc *BasicCluster) GetRangeCount(startKey, endKey []byte) int {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetRangeCount(startKey, endKey)
-}
-
-// GetOverlaps returns the regions which are overlapped with the specified region range.
-func (bc *BasicCluster) GetOverlaps(region *RegionInfo) []*RegionInfo {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetOverlaps(region)
-}
-
-// GetRegionSizeByRange scans regions intersecting [start key, end key), returns the total region size of this range.
-func (bc *BasicCluster) GetRegionSizeByRange(startKey, endKey []byte) int64 {
-	bc.Regions.mu.RLock()
-	defer bc.Regions.mu.RUnlock()
-	return bc.Regions.GetRegionSizeByRange(startKey, endKey)
-}
-
 func (bc *BasicCluster) getWriteRate(
 	f func(storeID uint64) (bytesRate, keysRate float64),
 ) (storeIDs []uint64, bytesRates, keysRates []float64) {
@@ -400,9 +204,7 @@ func (bc *BasicCluster) getWriteRate(
 	bytesRates = make([]float64, 0, count)
 	keysRates = make([]float64, 0, count)
 	for _, id := range storeIDs {
-		bc.Regions.mu.RLock()
 		bytesRate, keysRate := f(id)
-		bc.Regions.mu.RUnlock()
 		bytesRates = append(bytesRates, bytesRate)
 		keysRates = append(keysRates, keysRate)
 	}
@@ -411,53 +213,20 @@ func (bc *BasicCluster) getWriteRate(
 
 // GetStoresLeaderWriteRate get total write rate of each store's leaders.
 func (bc *BasicCluster) GetStoresLeaderWriteRate() (storeIDs []uint64, bytesRates, keysRates []float64) {
-	return bc.getWriteRate(bc.Regions.GetStoreLeaderWriteRate)
+	return bc.getWriteRate(bc.RegionsInfo.GetStoreLeaderWriteRate)
 }
 
 // GetStoresWriteRate get total write rate of each store's regions.
 func (bc *BasicCluster) GetStoresWriteRate() (storeIDs []uint64, bytesRates, keysRates []float64) {
-	return bc.getWriteRate(bc.Regions.GetStoreWriteRate)
-}
-
-func (bc *BasicCluster) getRelevantRegionsLocked(region *RegionInfo) (origin *RegionInfo, overlaps []*RegionInfo) {
-	origin = bc.Regions.GetRegion(region.GetID())
-	if origin == nil || !bytes.Equal(origin.GetStartKey(), region.GetStartKey()) || !bytes.Equal(origin.GetEndKey(), region.GetEndKey()) {
-		overlaps = bc.Regions.GetOverlaps(region)
-	}
-	return
+	return bc.getWriteRate(bc.RegionsInfo.GetStoreWriteRate)
 }
 
 /* Regions write operations */
 
 // PreCheckPutRegion checks if the region is valid to put.
 func (bc *BasicCluster) PreCheckPutRegion(region *RegionInfo) (*RegionInfo, error) {
-	bc.Regions.mu.RLock()
-	origin, overlaps := bc.getRelevantRegionsLocked(region)
-	bc.Regions.mu.RUnlock()
-	return bc.check(region, origin, overlaps)
-}
-
-func (bc *BasicCluster) check(region, origin *RegionInfo, overlaps []*RegionInfo) (*RegionInfo, error) {
-	for _, item := range overlaps {
-		// PD ignores stale regions' heartbeats, unless it is recreated recently by unsafe recover operation.
-		if region.GetRegionEpoch().GetVersion() < item.GetRegionEpoch().GetVersion() && !region.isRegionRecreated() {
-			return nil, errRegionIsStale(region.GetMeta(), item.GetMeta())
-		}
-	}
-	if origin == nil {
-		return nil, nil
-	}
-
-	r := region.GetRegionEpoch()
-	o := origin.GetRegionEpoch()
-	// TiKV reports term after v3.0
-	isTermBehind := region.GetTerm() > 0 && region.GetTerm() < origin.GetTerm()
-	// Region meta is stale, return an error.
-	if (isTermBehind || r.GetVersion() < o.GetVersion() || r.GetConfVer() < o.GetConfVer()) && !region.isRegionRecreated() {
-		return origin, errRegionIsStale(region.GetMeta(), origin.GetMeta())
-	}
-
-	return origin, nil
+	origin, overlaps := bc.RegionsInfo.GetRelevantRegions(region)
+	return check(region, origin, overlaps)
 }
 
 // CheckAndPutRegion checks if the region is valid to put, if valid then put.
@@ -471,46 +240,24 @@ func (bc *BasicCluster) CheckAndPutRegion(region *RegionInfo) []*RegionInfo {
 	return bc.PutRegion(region)
 }
 
-// AtomicCheckAndPutRegion checks if the region is valid to put, if valid then put.
-func (bc *BasicCluster) AtomicCheckAndPutRegion(region *RegionInfo) ([]*RegionInfo, error) {
-	bc.Regions.mu.Lock()
-	defer bc.Regions.mu.Unlock()
-	origin, overlaps := bc.getRelevantRegionsLocked(region)
-	_, err := bc.check(region, origin, overlaps)
-	if err != nil {
-		return nil, err
-	}
-	return bc.Regions.SetRegion(region), nil
-}
-
 // PutRegion put a region.
 func (bc *BasicCluster) PutRegion(region *RegionInfo) []*RegionInfo {
-	bc.Regions.mu.Lock()
-	defer bc.Regions.mu.Unlock()
-	return bc.Regions.SetRegion(region)
+	origin, overlaps, rangeChanged := bc.RegionsInfo.SetRegionWithUpdate(region)
+	bc.RegionsInfo.UpdateSubTree(region, origin, overlaps, rangeChanged)
+	return overlaps
 }
 
 // RemoveRegionIfExist removes RegionInfo from regionTree and regionMap if exists.
 func (bc *BasicCluster) RemoveRegionIfExist(id uint64) {
-	bc.Regions.mu.Lock()
-	defer bc.Regions.mu.Unlock()
-	if r := bc.Regions.GetRegion(id); r != nil {
-		bc.Regions.RemoveRegion(r)
+	if r := bc.RegionsInfo.GetRegion(id); r != nil {
+		bc.RegionsInfo.RemoveRegion(r)
+		bc.RegionsInfo.RemoveRegionFromSubTree(r)
 	}
 }
 
 // ResetRegionCache drops all region cache.
 func (bc *BasicCluster) ResetRegionCache() {
-	bc.Regions.mu.Lock()
-	defer bc.Regions.mu.Unlock()
-	bc.Regions.RegionsInfo = NewRegionsInfo()
-}
-
-// RemoveRegion removes RegionInfo from regionTree and regionMap.
-func (bc *BasicCluster) RemoveRegion(region *RegionInfo) {
-	bc.Regions.mu.Lock()
-	defer bc.Regions.mu.Unlock()
-	bc.Regions.RemoveRegion(region)
+	bc.RegionsInfo.Reset()
 }
 
 // RegionSetInformer provides access to a shared informer of regions.
diff --git a/server/core/region.go b/server/core/region.go
index ae7063c79..03da953ba 100644
--- a/server/core/region.go
+++ b/server/core/region.go
@@ -32,10 +32,13 @@ import (
 	"github.com/pingcap/kvproto/pkg/replication_modepb"
 	"github.com/pingcap/log"
 	"github.com/tikv/pd/pkg/logutil"
+	"github.com/tikv/pd/pkg/syncutil"
 	"github.com/tikv/pd/pkg/typeutil"
 	"go.uber.org/zap"
 )
 
+const randomRegionMaxRetry = 10
+
 // errRegionIsStale is error info for region is stale.
 func errRegionIsStale(region *metapb.Region, origin *metapb.Region) error {
 	return errors.Errorf("region is stale: region %v origin %v", region, origin)
@@ -697,8 +700,11 @@ func GenerateRegionGuideFunc(enableLog bool) RegionGuideFunc {
 
 // RegionsInfo for export
 type RegionsInfo struct {
+	t            syncutil.RWMutex
 	tree         *regionTree
 	regions      map[uint64]*regionItem // regionID -> regionInfo
+	st           syncutil.RWMutex
+	subRegions   map[uint64]*regionItem // regionID -> regionInfo
 	leaders      map[uint64]*regionTree // storeID -> sub regionTree
 	followers    map[uint64]*regionTree // storeID -> sub regionTree
 	learners     map[uint64]*regionTree // storeID -> sub regionTree
@@ -711,6 +717,7 @@ func NewRegionsInfo() *RegionsInfo {
 	return &RegionsInfo{
 		tree:         newRegionTree(),
 		regions:      make(map[uint64]*regionItem),
+		subRegions:   make(map[uint64]*regionItem),
 		leaders:      make(map[uint64]*regionTree),
 		followers:    make(map[uint64]*regionTree),
 		learners:     make(map[uint64]*regionTree),
@@ -721,59 +728,156 @@ func NewRegionsInfo() *RegionsInfo {
 
 // GetRegion returns the RegionInfo with regionID
 func (r *RegionsInfo) GetRegion(regionID uint64) *RegionInfo {
+	r.t.RLock()
+	defer r.t.RUnlock()
+
+	return r.getRegionLocked(regionID)
+}
+
+func (r *RegionsInfo) getRegionLocked(regionID uint64) *RegionInfo {
 	if item := r.regions[regionID]; item != nil {
 		return item.RegionInfo
 	}
 	return nil
 }
 
+// AtomicCheckAndPutRegion checks if the region is valid to put, if valid then put.
+func (r *RegionsInfo) AtomicCheckAndPutRegion(region *RegionInfo) ([]*RegionInfo, error) {
+	r.t.Lock()
+	var overlaps []*RegionInfo
+	origin := r.getRegionLocked(region.GetID())
+	if origin == nil || !bytes.Equal(origin.GetStartKey(), region.GetStartKey()) || !bytes.Equal(origin.GetEndKey(), region.GetEndKey()) {
+		overlaps = r.tree.getOverlaps(region)
+	}
+	_, err := check(region, origin, overlaps)
+	if err != nil {
+		return nil, err
+	}
+	origin, overlaps, rangeChanged := r.setRegionLocked(region)
+	r.t.Unlock()
+	r.UpdateSubTree(region, origin, overlaps, rangeChanged)
+	return overlaps, nil
+}
+
+// GetRelevantRegions returns the relevant regions for a given region.
+func (r *RegionsInfo) GetRelevantRegions(region *RegionInfo) (origin *RegionInfo, overlaps []*RegionInfo) {
+	r.t.RLock()
+	defer r.t.RUnlock()
+	origin = r.getRegionLocked(region.GetID())
+	if origin == nil || !bytes.Equal(origin.GetStartKey(), region.GetStartKey()) || !bytes.Equal(origin.GetEndKey(), region.GetEndKey()) {
+		overlaps = r.tree.getOverlaps(region)
+	}
+	return
+}
+
+func check(region, origin *RegionInfo, overlaps []*RegionInfo) (*RegionInfo, error) {
+	for _, item := range overlaps {
+		// PD ignores stale regions' heartbeats, unless it is recreated recently by unsafe recover operation.
+		if region.GetRegionEpoch().GetVersion() < item.GetRegionEpoch().GetVersion() && !region.isRegionRecreated() {
+			return nil, errRegionIsStale(region.GetMeta(), item.GetMeta())
+		}
+	}
+	if origin == nil {
+		return nil, nil
+	}
+
+	r := region.GetRegionEpoch()
+	o := origin.GetRegionEpoch()
+	// TiKV reports term after v3.0
+	isTermBehind := region.GetTerm() > 0 && region.GetTerm() < origin.GetTerm()
+	// Region meta is stale, return an error.
+	if (isTermBehind || r.GetVersion() < o.GetVersion() || r.GetConfVer() < o.GetConfVer()) && !region.isRegionRecreated() {
+		return origin, errRegionIsStale(region.GetMeta(), origin.GetMeta())
+	}
+
+	return origin, nil
+}
+
 // SetRegion sets the RegionInfo to regionTree and regionMap, also update leaders and followers by region peers
 // overlaps: Other regions that overlap with the specified region, excluding itself.
-func (r *RegionsInfo) SetRegion(region *RegionInfo) (overlaps []*RegionInfo) {
-	var item *regionItem // Pointer to the *RegionInfo of this ID.
+func (r *RegionsInfo) SetRegion(region *RegionInfo) []*RegionInfo {
+	r.t.Lock()
+	defer r.t.Unlock()
+	_, overlaps, _ := r.setRegionLocked(region)
+	return overlaps
+}
+
+// SetRegionWithUpdate sets the RegionInfo to regionTree and regionMap and return the update info of subtree.
+func (r *RegionsInfo) SetRegionWithUpdate(region *RegionInfo) (*RegionInfo, []*RegionInfo, bool) {
+	r.t.Lock()
+	defer r.t.Unlock()
+	return r.setRegionLocked(region)
+}
+
+func (r *RegionsInfo) setRegionLocked(region *RegionInfo) (*RegionInfo, []*RegionInfo, bool) {
+	var (
+		item   *regionItem // Pointer to the *RegionInfo of this ID.
+		origin *RegionInfo
+	)
 	rangeChanged := true // This Region is new, or its range has changed.
+
 	if item = r.regions[region.GetID()]; item != nil {
 		// If this ID already exists, use the existing regionItem and pick out the origin.
-		origin := item.RegionInfo
+		origin = item.RegionInfo
 		rangeChanged = !origin.rangeEqualsTo(region)
 		if rangeChanged {
 			// Delete itself in regionTree so that overlaps will not contain itself.
 			// Because the regionItem is reused, there is no need to delete it in the regionMap.
 			r.tree.remove(origin)
+			// Update the RegionInfo in the regionItem.
+			item.RegionInfo = region
 		} else {
 			// If the range is not changed, only the statistical on the regionTree needs to be updated.
 			r.tree.updateStat(origin, region)
-		}
-
-		if !rangeChanged && origin.peersEqualTo(region) {
-			// If the peers are not changed, only the statistical on the sub regionTree needs to be updated.
-			r.updateSubTreeStat(origin, region)
 			// Update the RegionInfo in the regionItem.
 			item.RegionInfo = region
-			return
+			return origin, nil, rangeChanged
 		}
-		// If the range or peers have changed, the sub regionTree needs to be cleaned up.
-		// TODO: Improve performance by deleting only the different peers.
-		r.removeRegionFromSubTree(origin)
-		// Update the RegionInfo in the regionItem.
-		item.RegionInfo = region
 	} else {
 		// If this ID does not exist, generate a new regionItem and save it in the regionMap.
 		item = &regionItem{RegionInfo: region}
 		r.regions[region.GetID()] = item
 	}
 
+	var overlaps []*RegionInfo
 	if rangeChanged {
 		// It has been removed and all information needs to be updated again.
 		overlaps = r.tree.update(item)
 		for _, old := range overlaps {
-			r.RemoveRegion(r.GetRegion(old.GetID()))
+			o := r.getRegionLocked(old.GetID())
+			// Remove from tree and regions.
+			r.tree.remove(o)
+			delete(r.regions, o.GetID())
+		}
+	}
+	return origin, overlaps, rangeChanged
+}
+
+// UpdateSubTree updates the subtree.
+func (r *RegionsInfo) UpdateSubTree(region, origin *RegionInfo, toRemove []*RegionInfo, rangeChanged bool) {
+	r.st.Lock()
+	defer r.st.Unlock()
+	if origin != nil {
+		if rangeChanged || !origin.peersEqualTo(region) {
+			// If the range or peers have changed, the sub regionTree needs to be cleaned up.
+			// TODO: Improve performance by deleting only the different peers.
+			r.removeRegionFromSubTreeLocked(origin)
+		} else {
+			r.updateSubTreeStat(origin, region)
+			r.subRegions[region.GetID()].RegionInfo = region
+			return
+		}
+	}
+	if rangeChanged {
+		for _, re := range toRemove {
+			r.removeRegionFromSubTreeLocked(re)
 		}
 	}
 
+	item := &regionItem{region}
+	r.subRegions[region.GetID()] = item
 	// It has been removed and all information needs to be updated again.
 	// Set peers then.
-
 	setPeer := func(peersMap map[uint64]*regionTree, storeID uint64, item *regionItem) {
 		store, ok := peersMap[storeID]
 		if !ok {
@@ -807,13 +911,6 @@ func (r *RegionsInfo) SetRegion(region *RegionInfo) (overlaps []*RegionInfo) {
 	setPeers(r.witnesses, region.GetWitnesses())
 	// Add to PendingPeers
 	setPeers(r.pendingPeers, region.GetPendingPeers())
-
-	return
-}
-
-// TreeLen returns the RegionsInfo tree length(now only used in test)
-func (r *RegionsInfo) TreeLen() int {
-	return r.tree.length()
 }
 
 func (r *RegionsInfo) updateSubTreeStat(origin *RegionInfo, region *RegionInfo) {
@@ -841,24 +938,56 @@ func (r *RegionsInfo) updateSubTreeStat(origin *RegionInfo, region *RegionInfo)
 	updatePeersStat(r.pendingPeers, region.GetPendingPeers())
 }
 
+// TreeLen returns the RegionsInfo tree length(now only used in test)
+func (r *RegionsInfo) TreeLen() int {
+	r.t.RLock()
+	defer r.t.RUnlock()
+	return r.tree.length()
+}
+
 // GetOverlaps returns the regions which are overlapped with the specified region range.
 func (r *RegionsInfo) GetOverlaps(region *RegionInfo) []*RegionInfo {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	return r.tree.getOverlaps(region)
 }
 
 // RemoveRegion removes RegionInfo from regionTree and regionMap
 func (r *RegionsInfo) RemoveRegion(region *RegionInfo) {
+	r.t.Lock()
+	defer r.t.Unlock()
 	// Remove from tree and regions.
 	r.tree.remove(region)
 	delete(r.regions, region.GetID())
+}
+
+// Reset resets the regions info.
+func (r *RegionsInfo) Reset() {
+	r.t.Lock()
+	r.tree = newRegionTree()
+	r.regions = make(map[uint64]*regionItem)
+	r.t.Unlock()
+	r.st.Lock()
+	defer r.st.Unlock()
+	r.leaders = make(map[uint64]*regionTree)
+	r.followers = make(map[uint64]*regionTree)
+	r.learners = make(map[uint64]*regionTree)
+	r.witnesses = make(map[uint64]*regionTree)
+	r.pendingPeers = make(map[uint64]*regionTree)
+}
+
+// RemoveRegionFromSubTree removes RegionInfo from regionSubTrees
+func (r *RegionsInfo) RemoveRegionFromSubTree(region *RegionInfo) {
+	r.st.Lock()
+	defer r.st.Unlock()
 	// Remove from leaders and followers.
-	r.removeRegionFromSubTree(region)
+	r.removeRegionFromSubTreeLocked(region)
 }
 
-// removeRegionFromSubTree removes RegionInfo from regionSubTrees
-func (r *RegionsInfo) removeRegionFromSubTree(region *RegionInfo) {
+// removeRegionFromSubTreeLocked removes RegionInfo from regionSubTrees
+func (r *RegionsInfo) removeRegionFromSubTreeLocked(region *RegionInfo) {
 	// Remove from leaders and followers.
-	for _, peer := range region.meta.GetPeers() {
+	for _, peer := range region.GetMeta().GetPeers() {
 		storeID := peer.GetStoreId()
 		r.leaders[storeID].remove(region)
 		r.followers[storeID].remove(region)
@@ -866,6 +995,7 @@ func (r *RegionsInfo) removeRegionFromSubTree(region *RegionInfo) {
 		r.witnesses[storeID].remove(region)
 		r.pendingPeers[storeID].remove(region)
 	}
+	delete(r.subRegions, region.GetMeta().GetId())
 }
 
 type peerSlice []*metapb.Peer
@@ -923,24 +1053,30 @@ func SortedPeersStatsEqual(peersA, peersB []*pdpb.PeerStats) bool {
 
 // GetRegionByKey searches RegionInfo from regionTree
 func (r *RegionsInfo) GetRegionByKey(regionKey []byte) *RegionInfo {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	region := r.tree.search(regionKey)
 	if region == nil {
 		return nil
 	}
-	return r.GetRegion(region.GetID())
+	return r.getRegionLocked(region.GetID())
 }
 
 // GetPrevRegionByKey searches previous RegionInfo from regionTree
 func (r *RegionsInfo) GetPrevRegionByKey(regionKey []byte) *RegionInfo {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	region := r.tree.searchPrev(regionKey)
 	if region == nil {
 		return nil
 	}
-	return r.GetRegion(region.GetID())
+	return r.getRegionLocked(region.GetID())
 }
 
 // GetRegions gets all RegionInfo from regionMap
 func (r *RegionsInfo) GetRegions() []*RegionInfo {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	regions := make([]*RegionInfo, 0, len(r.regions))
 	for _, item := range r.regions {
 		regions = append(regions, item.RegionInfo)
@@ -950,7 +1086,9 @@ func (r *RegionsInfo) GetRegions() []*RegionInfo {
 
 // GetStoreRegions gets all RegionInfo with a given storeID
 func (r *RegionsInfo) GetStoreRegions(storeID uint64) []*RegionInfo {
-	regions := make([]*RegionInfo, 0, r.GetStoreRegionCount(storeID))
+	r.st.RLock()
+	defer r.st.RUnlock()
+	regions := make([]*RegionInfo, 0, r.getStoreRegionCountLocked(storeID))
 	if leaders, ok := r.leaders[storeID]; ok {
 		regions = append(regions, leaders.scanRanges()...)
 	}
@@ -966,31 +1104,48 @@ func (r *RegionsInfo) GetStoreRegions(storeID uint64) []*RegionInfo {
 
 // GetStoreLeaderRegionSize get total size of store's leader regions
 func (r *RegionsInfo) GetStoreLeaderRegionSize(storeID uint64) int64 {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.leaders[storeID].TotalSize()
 }
 
 // GetStoreFollowerRegionSize get total size of store's follower regions
 func (r *RegionsInfo) GetStoreFollowerRegionSize(storeID uint64) int64 {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.followers[storeID].TotalSize()
 }
 
 // GetStoreLearnerRegionSize get total size of store's learner regions
 func (r *RegionsInfo) GetStoreLearnerRegionSize(storeID uint64) int64 {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.learners[storeID].TotalSize()
 }
 
 // GetStoreRegionSize get total size of store's regions
 func (r *RegionsInfo) GetStoreRegionSize(storeID uint64) int64 {
-	return r.GetStoreLeaderRegionSize(storeID) + r.GetStoreFollowerRegionSize(storeID) + r.GetStoreLearnerRegionSize(storeID)
+	r.st.RLock()
+	defer r.st.RUnlock()
+	return r.getStoreRegionSizeLocked(storeID)
+}
+
+// getStoreRegionSizeLocked get total size of store's regions
+func (r *RegionsInfo) getStoreRegionSizeLocked(storeID uint64) int64 {
+	return r.leaders[storeID].TotalSize() + r.followers[storeID].TotalSize() + r.learners[storeID].TotalSize()
 }
 
 // GetStoreLeaderWriteRate get total write rate of store's leaders
 func (r *RegionsInfo) GetStoreLeaderWriteRate(storeID uint64) (bytesRate, keysRate float64) {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.leaders[storeID].TotalWriteRate()
 }
 
 // GetStoreWriteRate get total write rate of store's regions
 func (r *RegionsInfo) GetStoreWriteRate(storeID uint64) (bytesRate, keysRate float64) {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	storeBytesRate, storeKeysRate := r.leaders[storeID].TotalWriteRate()
 	bytesRate += storeBytesRate
 	keysRate += storeKeysRate
@@ -1005,6 +1160,8 @@ func (r *RegionsInfo) GetStoreWriteRate(storeID uint64) (bytesRate, keysRate flo
 
 // GetMetaRegions gets a set of metapb.Region from regionMap
 func (r *RegionsInfo) GetMetaRegions() []*metapb.Region {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	regions := make([]*metapb.Region, 0, len(r.regions))
 	for _, item := range r.regions {
 		regions = append(regions, typeutil.DeepClone(item.meta, RegionFactory))
@@ -1012,83 +1169,128 @@ func (r *RegionsInfo) GetMetaRegions() []*metapb.Region {
 	return regions
 }
 
+// GetStoreStats returns the store stats.
+func (r *RegionsInfo) GetStoreStats(storeID uint64) (leader, region, witness, pending int, leaderSize, regionSize int64) {
+	r.st.RLock()
+	defer r.st.RUnlock()
+	return r.leaders[storeID].length(), r.getStoreRegionCountLocked(storeID), r.witnesses[storeID].length(),
+		r.pendingPeers[storeID].length(), r.leaders[storeID].TotalSize(), r.getStoreRegionSizeLocked(storeID)
+}
+
 // GetRegionCount gets the total count of RegionInfo of regionMap
 func (r *RegionsInfo) GetRegionCount() int {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	return len(r.regions)
 }
 
 // GetStoreRegionCount gets the total count of a store's leader, follower and learner RegionInfo by storeID
 func (r *RegionsInfo) GetStoreRegionCount(storeID uint64) int {
-	return r.GetStoreLeaderCount(storeID) + r.GetStoreFollowerCount(storeID) + r.GetStoreLearnerCount(storeID)
+	r.st.RLock()
+	defer r.st.RUnlock()
+	return r.getStoreRegionCountLocked(storeID)
+}
+
+// GetStoreRegionCount gets the total count of a store's leader, follower and learner RegionInfo by storeID
+func (r *RegionsInfo) getStoreRegionCountLocked(storeID uint64) int {
+	return r.leaders[storeID].length() + r.followers[storeID].length() + r.learners[storeID].length()
 }
 
 // GetStorePendingPeerCount gets the total count of a store's region that includes pending peer
 func (r *RegionsInfo) GetStorePendingPeerCount(storeID uint64) int {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.pendingPeers[storeID].length()
 }
 
 // GetStoreLeaderCount get the total count of a store's leader RegionInfo
 func (r *RegionsInfo) GetStoreLeaderCount(storeID uint64) int {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.leaders[storeID].length()
 }
 
 // GetStoreFollowerCount get the total count of a store's follower RegionInfo
 func (r *RegionsInfo) GetStoreFollowerCount(storeID uint64) int {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.followers[storeID].length()
 }
 
 // GetStoreLearnerCount get the total count of a store's learner RegionInfo
 func (r *RegionsInfo) GetStoreLearnerCount(storeID uint64) int {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.learners[storeID].length()
 }
 
 // GetStoreWitnessCount get the total count of a store's witness RegionInfo
 func (r *RegionsInfo) GetStoreWitnessCount(storeID uint64) int {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.witnesses[storeID].length()
 }
 
 // RandPendingRegion randomly gets a store's region with a pending peer.
 func (r *RegionsInfo) RandPendingRegion(storeID uint64, ranges []KeyRange) *RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.pendingPeers[storeID].RandomRegion(ranges)
 }
 
 // RandPendingRegions randomly gets a store's n regions with a pending peer.
-func (r *RegionsInfo) RandPendingRegions(storeID uint64, ranges []KeyRange, n int) []*RegionInfo {
-	return r.pendingPeers[storeID].RandomRegions(n, ranges)
+func (r *RegionsInfo) RandPendingRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
+	return r.pendingPeers[storeID].RandomRegions(randomRegionMaxRetry, ranges)
 }
 
 // RandLeaderRegion randomly gets a store's leader region.
 func (r *RegionsInfo) RandLeaderRegion(storeID uint64, ranges []KeyRange) *RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.leaders[storeID].RandomRegion(ranges)
 }
 
 // RandLeaderRegions randomly gets a store's n leader regions.
-func (r *RegionsInfo) RandLeaderRegions(storeID uint64, ranges []KeyRange, n int) []*RegionInfo {
-	return r.leaders[storeID].RandomRegions(n, ranges)
+func (r *RegionsInfo) RandLeaderRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
+	return r.leaders[storeID].RandomRegions(randomRegionMaxRetry, ranges)
 }
 
 // RandFollowerRegion randomly gets a store's follower region.
 func (r *RegionsInfo) RandFollowerRegion(storeID uint64, ranges []KeyRange) *RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.followers[storeID].RandomRegion(ranges)
 }
 
 // RandFollowerRegions randomly gets a store's n follower regions.
-func (r *RegionsInfo) RandFollowerRegions(storeID uint64, ranges []KeyRange, n int) []*RegionInfo {
-	return r.followers[storeID].RandomRegions(n, ranges)
+func (r *RegionsInfo) RandFollowerRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
+	return r.followers[storeID].RandomRegions(randomRegionMaxRetry, ranges)
 }
 
 // RandLearnerRegion randomly gets a store's learner region.
 func (r *RegionsInfo) RandLearnerRegion(storeID uint64, ranges []KeyRange) *RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	return r.learners[storeID].RandomRegion(ranges)
 }
 
 // RandLearnerRegions randomly gets a store's n learner regions.
-func (r *RegionsInfo) RandLearnerRegions(storeID uint64, ranges []KeyRange, n int) []*RegionInfo {
-	return r.learners[storeID].RandomRegions(n, ranges)
+func (r *RegionsInfo) RandLearnerRegions(storeID uint64, ranges []KeyRange) []*RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
+	return r.learners[storeID].RandomRegions(randomRegionMaxRetry, ranges)
 }
 
 // GetLeader returns leader RegionInfo by storeID and regionID (now only used in test)
 func (r *RegionsInfo) GetLeader(storeID uint64, region *RegionInfo) *RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	if leaders, ok := r.leaders[storeID]; ok {
 		return leaders.find(&regionItem{RegionInfo: region}).RegionInfo
 	}
@@ -1097,6 +1299,8 @@ func (r *RegionsInfo) GetLeader(storeID uint64, region *RegionInfo) *RegionInfo
 
 // GetFollower returns follower RegionInfo by storeID and regionID (now only used in test)
 func (r *RegionsInfo) GetFollower(storeID uint64, region *RegionInfo) *RegionInfo {
+	r.st.RLock()
+	defer r.st.RUnlock()
 	if followers, ok := r.followers[storeID]; ok {
 		return followers.find(&regionItem{RegionInfo: region}).RegionInfo
 	}
@@ -1156,6 +1360,8 @@ func (r *RegionInfo) GetWriteLoads() []float64 {
 
 // GetRangeCount returns the number of regions that overlap with the range [startKey, endKey).
 func (r *RegionsInfo) GetRangeCount(startKey, endKey []byte) int {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	start := &regionItem{&RegionInfo{meta: &metapb.Region{StartKey: startKey}}}
 	end := &regionItem{&RegionInfo{meta: &metapb.Region{StartKey: endKey}}}
 	// it returns 0 if startKey is nil.
@@ -1178,6 +1384,8 @@ func (r *RegionsInfo) GetRangeCount(startKey, endKey []byte) int {
 // ScanRange scans regions intersecting [start key, end key), returns at most
 // `limit` regions. limit <= 0 means no limit.
 func (r *RegionsInfo) ScanRange(startKey, endKey []byte, limit int) []*RegionInfo {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	var res []*RegionInfo
 	r.tree.scanRange(startKey, func(region *RegionInfo) bool {
 		if len(endKey) > 0 && bytes.Compare(region.GetStartKey(), endKey) >= 0 {
@@ -1195,11 +1403,15 @@ func (r *RegionsInfo) ScanRange(startKey, endKey []byte, limit int) []*RegionInf
 // ScanRangeWithIterator scans from the first region containing or behind start key,
 // until iterator returns false.
 func (r *RegionsInfo) ScanRangeWithIterator(startKey []byte, iterator func(region *RegionInfo) bool) {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	r.tree.scanRange(startKey, iterator)
 }
 
 // GetRegionSizeByRange scans regions intersecting [start key, end key), returns the total region size of this range.
 func (r *RegionsInfo) GetRegionSizeByRange(startKey, endKey []byte) int64 {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	var size int64
 	r.tree.scanRange(startKey, func(region *RegionInfo) bool {
 		if len(endKey) > 0 && bytes.Compare(region.GetStartKey(), endKey) >= 0 {
@@ -1213,20 +1425,24 @@ func (r *RegionsInfo) GetRegionSizeByRange(startKey, endKey []byte) int64 {
 
 // GetAdjacentRegions returns region's info that is adjacent with specific region
 func (r *RegionsInfo) GetAdjacentRegions(region *RegionInfo) (*RegionInfo, *RegionInfo) {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	p, n := r.tree.getAdjacentRegions(region)
 	var prev, next *RegionInfo
 	// check key to avoid key range hole
 	if p != nil && bytes.Equal(p.GetEndKey(), region.GetStartKey()) {
-		prev = r.GetRegion(p.GetID())
+		prev = r.getRegionLocked(p.GetID())
 	}
 	if n != nil && bytes.Equal(region.GetEndKey(), n.GetStartKey()) {
-		next = r.GetRegion(n.GetID())
+		next = r.getRegionLocked(n.GetID())
 	}
 	return prev, next
 }
 
 // GetRangeHoles returns all range holes, i.e the key ranges without any region info.
 func (r *RegionsInfo) GetRangeHoles() [][]string {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	var (
 		rangeHoles = make([][]string, 0)
 		lastEndKey = []byte("")
@@ -1251,6 +1467,8 @@ func (r *RegionsInfo) GetRangeHoles() [][]string {
 
 // GetAverageRegionSize returns the average region approximate size.
 func (r *RegionsInfo) GetAverageRegionSize() int64 {
+	r.t.RLock()
+	defer r.t.RUnlock()
 	if r.tree.length() == 0 {
 		return 0
 	}
diff --git a/server/schedule/range_cluster.go b/server/schedule/range_cluster.go
index b3d1cb2e1..a9672e2a1 100644
--- a/server/schedule/range_cluster.go
+++ b/server/schedule/range_cluster.go
@@ -31,7 +31,8 @@ type RangeCluster struct {
 func GenRangeCluster(cluster Cluster, startKey, endKey []byte) *RangeCluster {
 	subCluster := core.NewBasicCluster()
 	for _, r := range cluster.ScanRegions(startKey, endKey, -1) {
-		subCluster.Regions.SetRegion(r)
+		origin, overlaps, rangeChanged := subCluster.SetRegionWithUpdate(r)
+		subCluster.UpdateSubTree(r, origin, overlaps, rangeChanged)
 	}
 	return &RangeCluster{
 		Cluster:    cluster,


Test patch:
diff --git a/server/cluster/cluster_test.go b/server/cluster/cluster_test.go
index c83c4e4de..025264c19 100644
--- a/server/cluster/cluster_test.go
+++ b/server/cluster/cluster_test.go
@@ -61,7 +61,7 @@ func TestStoreHeartbeat(t *testing.T) {
 	for _, region := range regions {
 		re.NoError(cluster.putRegion(region))
 	}
-	re.Equal(int(n), cluster.core.Regions.RegionsInfo.GetRegionCount())
+	re.Equal(int(n), cluster.GetRegionCount())
 
 	for i, store := range stores {
 		req := &pdpb.StoreHeartbeatRequest{}
@@ -715,25 +715,25 @@ func TestRegionHeartbeat(t *testing.T) {
 	for i, region := range regions {
 		// region does not exist.
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 
 		// region is the same, not updated.
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 		origin := region
 		// region is updated.
 		region = origin.Clone(core.WithIncVersion())
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 
 		// region is stale (Version).
 		stale := origin.Clone(core.WithIncConfVer())
 		re.Error(cluster.processRegionHeartbeat(stale))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 
 		// region is updated
@@ -743,13 +743,13 @@ func TestRegionHeartbeat(t *testing.T) {
 		)
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 
 		// region is stale (ConfVer).
 		stale = origin.Clone(core.WithIncConfVer())
 		re.Error(cluster.processRegionHeartbeat(stale))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 
 		// Add a down peer.
@@ -761,38 +761,38 @@ func TestRegionHeartbeat(t *testing.T) {
 		}))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Add a pending peer.
 		region = region.Clone(core.WithPendingPeers([]*metapb.Peer{region.GetPeers()[rand.Intn(len(region.GetPeers()))]}))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Clear down peers.
 		region = region.Clone(core.WithDownPeers(nil))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Clear pending peers.
 		region = region.Clone(core.WithPendingPeers(nil))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Remove peers.
 		origin = region
 		region = origin.Clone(core.SetPeers(region.GetPeers()[:1]))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 		// Add peers.
 		region = origin
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 		checkRegionsKV(re, cluster.storage, regions[:i+1])
 
 		// Change one peer to witness
@@ -802,37 +802,37 @@ func TestRegionHeartbeat(t *testing.T) {
 		)
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Change leader.
 		region = region.Clone(core.WithLeader(region.GetPeers()[1]))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Change ApproximateSize.
 		region = region.Clone(core.SetApproximateSize(144))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Change ApproximateKeys.
 		region = region.Clone(core.SetApproximateKeys(144000))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Change bytes written.
 		region = region.Clone(core.SetWrittenBytes(24000))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 
 		// Change bytes read.
 		region = region.Clone(core.SetReadBytes(1080000))
 		regions[i] = region
 		re.NoError(cluster.processRegionHeartbeat(region))
-		checkRegions(re, cluster.core.Regions.RegionsInfo, regions[:i+1])
+		checkRegions(re, cluster.core, regions[:i+1])
 	}
 
 	regionCounts := make(map[uint64]int)
@@ -1668,7 +1668,7 @@ func Test(t *testing.T) {
 	_, opts, err := newTestScheduleConfig()
 	re.NoError(err)
 	tc := newTestRaftCluster(ctx, mockid.NewIDAllocator(), opts, storage.NewStorageWithMemoryBackend(), core.NewBasicCluster())
-	cache := tc.core.Regions.RegionsInfo
+	cache := tc.core
 
 	for i := uint64(0); i < n; i++ {
 		region := regions[i]
@@ -1678,7 +1678,8 @@ func Test(t *testing.T) {
 		re.Nil(cache.GetRegionByKey(regionKey))
 		checkRegions(re, cache, regions[0:i])
 
-		cache.SetRegion(region)
+		origin, overlaps, rangeChanged := cache.SetRegionWithUpdate(region)
+		cache.UpdateSubTree(region, origin, overlaps, rangeChanged)
 		checkRegion(re, cache.GetRegion(i), region)
 		checkRegion(re, cache.GetRegionByKey(regionKey), region)
 		checkRegions(re, cache, regions[0:(i+1)])
@@ -1691,12 +1692,14 @@ func Test(t *testing.T) {
 		// Update leader to peer np-1.
 		newRegion := region.Clone(core.WithLeader(region.GetPeers()[np-1]))
 		regions[i] = newRegion
-		cache.SetRegion(newRegion)
+		origin, overlaps, rangeChanged = cache.SetRegionWithUpdate(newRegion)
+		cache.UpdateSubTree(newRegion, origin, overlaps, rangeChanged)
 		checkRegion(re, cache.GetRegion(i), newRegion)
 		checkRegion(re, cache.GetRegionByKey(regionKey), newRegion)
 		checkRegions(re, cache, regions[0:(i+1)])
 
 		cache.RemoveRegion(region)
+		cache.RemoveRegionFromSubTree(region)
 		re.Nil(cache.GetRegion(i))
 		re.Nil(cache.GetRegionByKey(regionKey))
 		checkRegions(re, cache, regions[0:i])
@@ -1704,7 +1707,8 @@ func Test(t *testing.T) {
 		// Reset leader to peer 0.
 		newRegion = region.Clone(core.WithLeader(region.GetPeers()[0]))
 		regions[i] = newRegion
-		cache.SetRegion(newRegion)
+		origin, overlaps, rangeChanged = cache.SetRegionWithUpdate(newRegion)
+		cache.UpdateSubTree(newRegion, origin, overlaps, rangeChanged)
 		checkRegion(re, cache.GetRegion(i), newRegion)
 		checkRegions(re, cache, regions[0:(i+1)])
 		checkRegion(re, cache.GetRegionByKey(regionKey), newRegion)
@@ -1725,7 +1729,8 @@ func Test(t *testing.T) {
 	// check overlaps
 	// clone it otherwise there are two items with the same key in the tree
 	overlapRegion := regions[n-1].Clone(core.WithStartKey(regions[n-2].GetStartKey()))
-	cache.SetRegion(overlapRegion)
+	origin, overlaps, rangeChanged := cache.SetRegionWithUpdate(overlapRegion)
+	cache.UpdateSubTree(overlapRegion, origin, overlaps, rangeChanged)
 	re.Nil(cache.GetRegion(n - 2))
 	re.NotNil(cache.GetRegion(n - 1))
 
@@ -1734,7 +1739,8 @@ func Test(t *testing.T) {
 		for j := 0; j < cache.GetStoreLeaderCount(i); j++ {
 			region := filter.SelectOneRegion(tc.RandLeaderRegions(i, []core.KeyRange{core.NewKeyRange("", "")}), nil, pendingFilter, downFilter)
 			newRegion := region.Clone(core.WithPendingPeers(region.GetPeers()))
-			cache.SetRegion(newRegion)
+			origin, overlaps, rangeChanged = cache.SetRegionWithUpdate(newRegion)
+			cache.UpdateSubTree(newRegion, origin, overlaps, rangeChanged)
 		}
 		re.Nil(filter.SelectOneRegion(tc.RandLeaderRegions(i, []core.KeyRange{core.NewKeyRange("", "")}), nil, pendingFilter, downFilter))
 	}
@@ -1913,7 +1919,7 @@ func checkRegionsKV(re *require.Assertions, s storage.Storage, regions []*core.R
 	}
 }
 
-func checkRegions(re *require.Assertions, cache *core.RegionsInfo, regions []*core.RegionInfo) {
+func checkRegions(re *require.Assertions, cache *core.BasicCluster, regions []*core.RegionInfo) {
 	regionCount := make(map[uint64]int)
 	leaderCount := make(map[uint64]int)
 	followerCount := make(map[uint64]int)
diff --git a/server/cluster/coordinator_test.go b/server/cluster/coordinator_test.go
index 24ca29c80..7df642f33 100644
--- a/server/cluster/coordinator_test.go
+++ b/server/cluster/coordinator_test.go
@@ -628,7 +628,7 @@ func TestShouldRun(t *testing.T) {
 	re.NoError(tc.LoadRegion(6, 2, 1, 4))
 	re.NoError(tc.LoadRegion(7, 2, 1, 4))
 	re.False(co.shouldRun())
-	re.Equal(2, tc.core.Regions.GetStoreRegionCount(4))
+	re.Equal(2, tc.GetStoreRegionCount(4))
 
 	testCases := []struct {
 		regionID  uint64
@@ -670,7 +670,7 @@ func TestShouldRunWithNonLeaderRegions(t *testing.T) {
 		re.NoError(tc.LoadRegion(uint64(i+1), 1, 2, 3))
 	}
 	re.False(co.shouldRun())
-	re.Equal(10, tc.core.Regions.GetStoreRegionCount(1))
+	re.Equal(10, tc.GetStoreRegionCount(1))
 
 	testCases := []struct {
 		regionID  uint64
diff --git a/server/core/region_test.go b/server/core/region_test.go
index 23acca770..d6030997f 100644
--- a/server/core/region_test.go
+++ b/server/core/region_test.go
@@ -368,24 +368,24 @@ func TestNeedSync(t *testing.T) {
 func TestRegionMap(t *testing.T) {
 	re := require.New(t)
 	rm := make(map[uint64]*regionItem)
-	check(re, rm)
+	checkMap(re, rm)
 	rm[1] = &regionItem{RegionInfo: regionInfo(1)}
-	check(re, rm, 1)
+	checkMap(re, rm, 1)
 
 	rm[2] = &regionItem{RegionInfo: regionInfo(2)}
 	rm[3] = &regionItem{RegionInfo: regionInfo(3)}
-	check(re, rm, 1, 2, 3)
+	checkMap(re, rm, 1, 2, 3)
 
 	rm[3] = &regionItem{RegionInfo: regionInfo(3)}
 	delete(rm, 4)
-	check(re, rm, 1, 2, 3)
+	checkMap(re, rm, 1, 2, 3)
 
 	delete(rm, 3)
 	delete(rm, 1)
-	check(re, rm, 2)
+	checkMap(re, rm, 2)
 
 	rm[3] = &regionItem{RegionInfo: regionInfo(3)}
-	check(re, rm, 2, 3)
+	checkMap(re, rm, 2, 3)
 }
 
 func regionInfo(id uint64) *RegionInfo {
@@ -398,7 +398,7 @@ func regionInfo(id uint64) *RegionInfo {
 	}
 }
 
-func check(re *require.Assertions, rm map[uint64]*regionItem, ids ...uint64) {
+func checkMap(re *require.Assertions, rm map[uint64]*regionItem, ids ...uint64) {
 	// Check Get.
 	for _, id := range ids {
 		re.Equal(id, rm[id].GetID())
@@ -466,7 +466,8 @@ func TestSetRegion(t *testing.T) {
 			StartKey: []byte(fmt.Sprintf("%20d", i*10)),
 			EndKey:   []byte(fmt.Sprintf("%20d", (i+1)*10)),
 		}, peer1)
-		regions.SetRegion(region)
+		origin, overlaps, rangeChanged := regions.SetRegionWithUpdate(region)
+		regions.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	}
 
 	peer1 := &metapb.Peer{StoreId: uint64(4), Id: uint64(101)}
@@ -479,12 +480,14 @@ func TestSetRegion(t *testing.T) {
 		EndKey:   []byte(fmt.Sprintf("%20d", 211)),
 	}, peer1)
 	region.pendingPeers = append(region.pendingPeers, peer3)
-	regions.SetRegion(region)
+	origin, overlaps, rangeChanged := regions.SetRegionWithUpdate(region)
+	regions.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	checkRegions(re, regions)
 	re.Equal(97, regions.tree.length())
 	re.Len(regions.GetRegions(), 97)
 
-	regions.SetRegion(region)
+	origin, overlaps, rangeChanged = regions.SetRegionWithUpdate(region)
+	regions.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	peer1 = &metapb.Peer{StoreId: uint64(2), Id: uint64(101)}
 	peer2 = &metapb.Peer{StoreId: uint64(3), Id: uint64(102), Role: metapb.PeerRole_Learner}
 	peer3 = &metapb.Peer{StoreId: uint64(1), Id: uint64(103)}
@@ -495,7 +498,8 @@ func TestSetRegion(t *testing.T) {
 		EndKey:   []byte(fmt.Sprintf("%20d", 212)),
 	}, peer1)
 	region.pendingPeers = append(region.pendingPeers, peer3)
-	regions.SetRegion(region)
+	origin, overlaps, rangeChanged = regions.SetRegionWithUpdate(region)
+	regions.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	checkRegions(re, regions)
 	re.Equal(97, regions.tree.length())
 	re.Len(regions.GetRegions(), 97)
@@ -504,7 +508,8 @@ func TestSetRegion(t *testing.T) {
 	region = region.Clone(WithStartKey([]byte(fmt.Sprintf("%20d", 175))), WithNewRegionID(201))
 	re.NotNil(regions.GetRegion(21))
 	re.NotNil(regions.GetRegion(18))
-	regions.SetRegion(region)
+	origin, overlaps, rangeChanged = regions.SetRegionWithUpdate(region)
+	regions.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	checkRegions(re, regions)
 	re.Equal(96, regions.tree.length())
 	re.Len(regions.GetRegions(), 96)
@@ -519,7 +524,8 @@ func TestSetRegion(t *testing.T) {
 		SetWrittenBytes(40),
 		SetWrittenKeys(10),
 		SetReportInterval(0, 5))
-	regions.SetRegion(region)
+	origin, overlaps, rangeChanged = regions.SetRegionWithUpdate(region)
+	regions.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	checkRegions(re, regions)
 	re.Equal(96, regions.tree.length())
 	re.Len(regions.GetRegions(), 96)
@@ -630,7 +636,8 @@ func BenchmarkRandomRegion(b *testing.B) {
 			StartKey: []byte(fmt.Sprintf("%20d", i)),
 			EndKey:   []byte(fmt.Sprintf("%20d", i+1)),
 		}, peer)
-		regions.SetRegion(region)
+		origin, overlaps, rangeChanged := regions.SetRegionWithUpdate(region)
+		regions.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	}
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
@@ -683,6 +690,7 @@ func BenchmarkAddRegion(b *testing.B) {
 	}
 	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
-		regions.SetRegion(items[i])
+		origin, overlaps, rangeChanged := regions.SetRegionWithUpdate(items[i])
+		regions.UpdateSubTree(items[i], origin, overlaps, rangeChanged)
 	}
 }
diff --git a/server/schedulers/balance_test.go b/server/schedulers/balance_test.go
index b1addea16..3c45daffb 100644
--- a/server/schedulers/balance_test.go
+++ b/server/schedulers/balance_test.go
@@ -640,17 +640,24 @@ func (suite *balanceLeaderRangeSchedulerTestSuite) TestMultiRangeBalance() {
 	suite.NoError(err)
 	ops, _ := lb.Schedule(suite.tc, false)
 	suite.Equal(uint64(1), ops[0].RegionID())
-	suite.tc.RemoveRegion(suite.tc.GetRegion(1))
+	r := suite.tc.GetRegion(1)
+	suite.tc.RemoveRegion(r)
+	suite.tc.RemoveRegionFromSubTree(r)
 	suite.tc.AddLeaderRegionWithRange(2, "p", "r", 1, 2, 3, 4)
 	suite.NoError(err)
 	ops, _ = lb.Schedule(suite.tc, false)
 	suite.Equal(uint64(2), ops[0].RegionID())
-	suite.tc.RemoveRegion(suite.tc.GetRegion(2))
+	r = suite.tc.GetRegion(2)
+	suite.tc.RemoveRegion(r)
+	suite.tc.RemoveRegionFromSubTree(r)
+
 	suite.tc.AddLeaderRegionWithRange(3, "u", "w", 1, 2, 3, 4)
 	suite.NoError(err)
 	ops, _ = lb.Schedule(suite.tc, false)
 	suite.Empty(ops)
-	suite.tc.RemoveRegion(suite.tc.GetRegion(3))
+	r = suite.tc.GetRegion(3)
+	suite.tc.RemoveRegion(r)
+	suite.tc.RemoveRegionFromSubTree(r)
 	suite.tc.AddLeaderRegionWithRange(4, "", "", 1, 2, 3, 4)
 	suite.NoError(err)
 	ops, _ = lb.Schedule(suite.tc, false)
@@ -1303,7 +1310,8 @@ func TestScatterRangeBalance(t *testing.T) {
 			core.SetApproximateKeys(1),
 			core.SetApproximateSize(1),
 		)
-		tc.Regions.SetRegion(regionInfo)
+		origin, overlaps, rangeChanged := tc.SetRegionWithUpdate(regionInfo)
+		tc.UpdateSubTree(regionInfo, origin, overlaps, rangeChanged)
 	}
 	for i := 0; i < 100; i++ {
 		_, err := tc.AllocPeer(1)
@@ -1319,9 +1327,9 @@ func TestScatterRangeBalance(t *testing.T) {
 
 	scheduleAndApplyOperator(tc, hb, 100)
 	for i := 1; i <= 5; i++ {
-		leaderCount := tc.Regions.GetStoreLeaderCount(uint64(i))
+		leaderCount := tc.GetStoreLeaderCount(uint64(i))
 		re.LessOrEqual(leaderCount, 12)
-		regionCount = tc.Regions.GetStoreRegionCount(uint64(i))
+		regionCount = tc.GetStoreRegionCount(uint64(i))
 		re.LessOrEqual(regionCount, 32)
 	}
 }
@@ -1371,7 +1379,8 @@ func TestBalanceLeaderLimit(t *testing.T) {
 			core.SetApproximateSize(96),
 		)
 
-		tc.Regions.SetRegion(regionInfo)
+		origin, overlaps, rangeChanged := tc.SetRegionWithUpdate(regionInfo)
+		tc.UpdateSubTree(regionInfo, origin, overlaps, rangeChanged)
 	}
 
 	for i := 0; i < 100; i++ {
@@ -1392,14 +1401,14 @@ func TestBalanceLeaderLimit(t *testing.T) {
 	maxLeaderCount := 0
 	minLeaderCount := 99
 	for i := 1; i <= 5; i++ {
-		leaderCount := tc.Regions.GetStoreLeaderCount(uint64(i))
+		leaderCount := tc.GetStoreLeaderCount(uint64(i))
 		if leaderCount < minLeaderCount {
 			minLeaderCount = leaderCount
 		}
 		if leaderCount > maxLeaderCount {
 			maxLeaderCount = leaderCount
 		}
-		regionCount = tc.Regions.GetStoreRegionCount(uint64(i))
+		regionCount = tc.GetStoreRegionCount(uint64(i))
 		re.LessOrEqual(regionCount, 32)
 	}
 	re.Greater(maxLeaderCount-minLeaderCount, 10)
@@ -1481,7 +1490,8 @@ func TestBalanceWhenRegionNotHeartbeat(t *testing.T) {
 			core.SetApproximateSize(96),
 		)
 
-		tc.Regions.SetRegion(regionInfo)
+		origin, overlaps, rangeChanged := tc.SetRegionWithUpdate(regionInfo)
+		tc.UpdateSubTree(regionInfo, origin, overlaps, rangeChanged)
 	}
 
 	for i := 1; i <= 3; i++ {
diff --git a/server/schedulers/hot_region_test.go b/server/schedulers/hot_region_test.go
index cbdf51df7..cdff13c55 100644
--- a/server/schedulers/hot_region_test.go
+++ b/server/schedulers/hot_region_test.go
@@ -374,7 +374,9 @@ func checkByteRateOnly(re *require.Assertions, tc *mockcluster.Cluster, hb sched
 
 	// Should not panic if region not found.
 	for i := uint64(1); i <= 3; i++ {
-		tc.Regions.RemoveRegion(tc.GetRegion(i))
+		r := tc.GetRegion(i)
+		tc.RemoveRegion(r)
+		tc.RemoveRegionFromSubTree(r)
 	}
 	hb.Schedule(tc, false)
 	clearPendingInfluence(hb.(*hotScheduler))
@@ -1119,7 +1121,9 @@ func TestHotReadRegionScheduleByteRateOnly(t *testing.T) {
 
 	// Should not panic if region not found.
 	for i := uint64(1); i <= 3; i++ {
-		tc.Regions.RemoveRegion(tc.GetRegion(i))
+		r := tc.GetRegion(i)
+		tc.RemoveRegion(r)
+		tc.RemoveRegionFromSubTree(r)
 	}
 	hb.Schedule(tc, false)
 	re.Contains(hb.regionPendings, uint64(4))
diff --git a/server/schedulers/scheduler_test.go b/server/schedulers/scheduler_test.go
index f4fd01844..54a502ea9 100644
--- a/server/schedulers/scheduler_test.go
+++ b/server/schedulers/scheduler_test.go
@@ -111,14 +111,15 @@ func TestRejectLeader(t *testing.T) {
 
 	// If the peer on store3 is pending, not transfer to store3 neither.
 	tc.SetStoreUp(3)
-	region := tc.Regions.GetRegion(1)
+	region := tc.GetRegion(1)
 	for _, p := range region.GetPeers() {
 		if p.GetStoreId() == 3 {
 			region = region.Clone(core.WithPendingPeers(append(region.GetPendingPeers(), p)))
 			break
 		}
 	}
-	tc.Regions.SetRegion(region)
+	origin, overlaps, rangeChanged := tc.SetRegionWithUpdate(region)
+	tc.UpdateSubTree(region, origin, overlaps, rangeChanged)
 	ops, _ = sl.Schedule(tc, false)
 	testutil.CheckTransferLeader(re, ops[0], operator.OpLeader, 1, 2)
 }
diff --git a/tests/server/cluster/cluster_test.go b/tests/server/cluster/cluster_test.go
index 0527b2cb0..80e4da737 100644
--- a/tests/server/cluster/cluster_test.go
+++ b/tests/server/cluster/cluster_test.go
@@ -29,6 +29,7 @@ import (
 	"github.com/pingcap/kvproto/pkg/metapb"
 	"github.com/pingcap/kvproto/pkg/pdpb"
 	"github.com/pingcap/kvproto/pkg/replication_modepb"
+	"github.com/sasha-s/go-deadlock"
 	"github.com/stretchr/testify/require"
 	"github.com/tikv/pd/pkg/dashboard"
 	"github.com/tikv/pd/pkg/mock/mockid"
@@ -565,6 +566,7 @@ func TestStoreVersionChange(t *testing.T) {
 
 func TestConcurrentHandleRegion(t *testing.T) {
 	re := require.New(t)
+	deadlock.Opts.DeadlockTimeout = time.Minute
 	ctx, cancel := context.WithCancel(context.Background())
 	defer cancel()
 	dashboard.SetCheckInterval(30 * time.Minute)