forked from pingcap/br
/
split.go
412 lines (379 loc) · 12.5 KB
/
split.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
// Copyright 2020 PingCAP, Inc. Licensed under Apache-2.0.
package restore
import (
"bytes"
"context"
"encoding/hex"
"strings"
"time"
"github.com/opentracing/opentracing-go"
"github.com/pingcap/errors"
sst "github.com/pingcap/kvproto/pkg/import_sstpb"
"github.com/pingcap/kvproto/pkg/metapb"
"github.com/pingcap/kvproto/pkg/pdpb"
"github.com/pingcap/log"
"github.com/tikv/pd/pkg/codec"
"go.uber.org/zap"
berrors "github.com/pingcap/br/pkg/errors"
"github.com/pingcap/br/pkg/logutil"
"github.com/pingcap/br/pkg/rtree"
)
// Constants for split retry machinery.
const (
SplitRetryTimes = 32
SplitRetryInterval = 50 * time.Millisecond
SplitMaxRetryInterval = time.Second
SplitCheckMaxRetryTimes = 64
SplitCheckInterval = 8 * time.Millisecond
SplitMaxCheckInterval = time.Second
ScatterWaitMaxRetryTimes = 64
ScatterWaitInterval = 50 * time.Millisecond
ScatterMaxWaitInterval = time.Second
ScatterWaitUpperInterval = 180 * time.Second
ScanRegionPaginationLimit = 128
RejectStoreCheckRetryTimes = 64
RejectStoreCheckInterval = 100 * time.Millisecond
RejectStoreMaxCheckInterval = 2 * time.Second
)
// RegionSplitter is a executor of region split by rules.
type RegionSplitter struct {
client SplitClient
}
// NewRegionSplitter returns a new RegionSplitter.
func NewRegionSplitter(client SplitClient) *RegionSplitter {
return &RegionSplitter{
client: client,
}
}
// OnSplitFunc is called before split a range.
type OnSplitFunc func(key [][]byte)
// Split executes a region split. It will split regions by the rewrite rules,
// then it will split regions by the end key of each range.
// tableRules includes the prefix of a table, since some ranges may have
// a prefix with record sequence or index sequence.
// note: all ranges and rewrite rules must have raw key.
func (rs *RegionSplitter) Split(
ctx context.Context,
ranges []rtree.Range,
rewriteRules *RewriteRules,
onSplit OnSplitFunc,
) error {
if len(ranges) == 0 {
log.Info("skip split regions, no range")
return nil
}
if span := opentracing.SpanFromContext(ctx); span != nil && span.Tracer() != nil {
span1 := span.Tracer().StartSpan("RegionSplitter.Split", opentracing.ChildOf(span.Context()))
defer span1.Finish()
ctx = opentracing.ContextWithSpan(ctx, span1)
}
startTime := time.Now()
// Sort the range for getting the min and max key of the ranges
sortedRanges, errSplit := SortRanges(ranges, rewriteRules)
if errSplit != nil {
return errors.Trace(errSplit)
}
minKey := codec.EncodeBytes(sortedRanges[0].StartKey)
maxKey := codec.EncodeBytes(sortedRanges[len(sortedRanges)-1].EndKey)
for _, rule := range rewriteRules.Table {
if bytes.Compare(minKey, rule.GetNewKeyPrefix()) > 0 {
minKey = rule.GetNewKeyPrefix()
}
if bytes.Compare(maxKey, rule.GetNewKeyPrefix()) < 0 {
maxKey = rule.GetNewKeyPrefix()
}
}
for _, rule := range rewriteRules.Data {
if bytes.Compare(minKey, rule.GetNewKeyPrefix()) > 0 {
minKey = rule.GetNewKeyPrefix()
}
if bytes.Compare(maxKey, rule.GetNewKeyPrefix()) < 0 {
maxKey = rule.GetNewKeyPrefix()
}
}
interval := SplitRetryInterval
scatterRegions := make([]*RegionInfo, 0)
SplitRegions:
for i := 0; i < SplitRetryTimes; i++ {
regions, errScan := PaginateScanRegion(ctx, rs.client, minKey, maxKey, ScanRegionPaginationLimit)
if errScan != nil {
return errors.Trace(errScan)
}
if len(regions) == 0 {
log.Warn("split regions cannot scan any region")
return nil
}
splitKeyMap := getSplitKeys(rewriteRules, sortedRanges, regions)
regionMap := make(map[uint64]*RegionInfo)
for _, region := range regions {
regionMap[region.Region.GetId()] = region
}
for regionID, keys := range splitKeyMap {
var newRegions []*RegionInfo
region := regionMap[regionID]
log.Info("split regions",
logutil.Region(region.Region), logutil.Keys(keys), rtree.ZapRanges(ranges))
newRegions, errSplit = rs.splitAndScatterRegions(ctx, region, keys)
if errSplit != nil {
if strings.Contains(errSplit.Error(), "no valid key") {
for _, key := range keys {
// Region start/end keys are encoded. split_region RPC
// requires raw keys (without encoding).
log.Error("split regions no valid key",
logutil.Key("startKey", region.Region.StartKey),
logutil.Key("endKey", region.Region.EndKey),
logutil.Key("key", codec.EncodeBytes(key)),
rtree.ZapRanges(ranges))
}
return errors.Trace(errSplit)
}
interval = 2 * interval
if interval > SplitMaxRetryInterval {
interval = SplitMaxRetryInterval
}
time.Sleep(interval)
log.Warn("split regions failed, retry",
zap.Error(errSplit),
logutil.Region(region.Region),
logutil.Leader(region.Leader),
logutil.Keys(keys), rtree.ZapRanges(ranges))
continue SplitRegions
}
if len(newRegions) != len(keys) {
log.Warn("split key count and new region count mismatch",
zap.Int("new region count", len(newRegions)),
zap.Int("split key count", len(keys)))
}
scatterRegions = append(scatterRegions, newRegions...)
onSplit(keys)
}
break
}
if errSplit != nil {
return errors.Trace(errSplit)
}
log.Info("start to wait for scattering regions",
zap.Int("regions", len(scatterRegions)), zap.Duration("take", time.Since(startTime)))
startTime = time.Now()
scatterCount := 0
for _, region := range scatterRegions {
rs.waitForScatterRegion(ctx, region)
if time.Since(startTime) > ScatterWaitUpperInterval {
break
}
scatterCount++
}
if scatterCount == len(scatterRegions) {
log.Info("waiting for scattering regions done",
zap.Int("regions", len(scatterRegions)), zap.Duration("take", time.Since(startTime)))
} else {
log.Warn("waiting for scattering regions timeout",
zap.Int("scatterCount", scatterCount),
zap.Int("regions", len(scatterRegions)),
zap.Duration("take", time.Since(startTime)))
}
return nil
}
func (rs *RegionSplitter) hasRegion(ctx context.Context, regionID uint64) (bool, error) {
regionInfo, err := rs.client.GetRegionByID(ctx, regionID)
if err != nil {
return false, errors.Trace(err)
}
return regionInfo != nil, nil
}
func (rs *RegionSplitter) isScatterRegionFinished(ctx context.Context, regionID uint64) (bool, error) {
resp, err := rs.client.GetOperator(ctx, regionID)
if err != nil {
return false, errors.Trace(err)
}
// Heartbeat may not be sent to PD
if respErr := resp.GetHeader().GetError(); respErr != nil {
if respErr.GetType() == pdpb.ErrorType_REGION_NOT_FOUND {
return true, nil
}
return false, errors.Annotatef(berrors.ErrPDInvalidResponse, "get operator error: %s", respErr.GetType())
}
retryTimes := ctx.Value(retryTimes).(int)
if retryTimes > 3 {
log.Info("get operator", zap.Uint64("regionID", regionID), zap.Stringer("resp", resp))
}
// If the current operator of the region is not 'scatter-region', we could assume
// that 'scatter-operator' has finished or timeout
ok := string(resp.GetDesc()) != "scatter-region" || resp.GetStatus() != pdpb.OperatorStatus_RUNNING
return ok, nil
}
func (rs *RegionSplitter) waitForSplit(ctx context.Context, regionID uint64) {
interval := SplitCheckInterval
for i := 0; i < SplitCheckMaxRetryTimes; i++ {
ok, err := rs.hasRegion(ctx, regionID)
if err != nil {
log.Warn("wait for split failed", zap.Error(err))
return
}
if ok {
break
}
interval = 2 * interval
if interval > SplitMaxCheckInterval {
interval = SplitMaxCheckInterval
}
time.Sleep(interval)
}
}
type retryTimeKey struct{}
var retryTimes = new(retryTimeKey)
func (rs *RegionSplitter) waitForScatterRegion(ctx context.Context, regionInfo *RegionInfo) {
interval := ScatterWaitInterval
regionID := regionInfo.Region.GetId()
for i := 0; i < ScatterWaitMaxRetryTimes; i++ {
ctx1 := context.WithValue(ctx, retryTimes, i)
ok, err := rs.isScatterRegionFinished(ctx1, regionID)
if err != nil {
log.Warn("scatter region failed: do not have the region",
logutil.Region(regionInfo.Region))
return
}
if ok {
break
}
interval = 2 * interval
if interval > ScatterMaxWaitInterval {
interval = ScatterMaxWaitInterval
}
time.Sleep(interval)
}
}
func (rs *RegionSplitter) splitAndScatterRegions(
ctx context.Context, regionInfo *RegionInfo, keys [][]byte,
) ([]*RegionInfo, error) {
newRegions, err := rs.client.BatchSplitRegions(ctx, regionInfo, keys)
if err != nil {
return nil, errors.Trace(err)
}
for _, region := range newRegions {
// Wait for a while until the regions successfully split.
rs.waitForSplit(ctx, region.Region.Id)
if err = rs.client.ScatterRegion(ctx, region); err != nil {
log.Warn("scatter region failed", logutil.Region(region.Region), zap.Error(err))
}
}
return newRegions, nil
}
// PaginateScanRegion scan regions with a limit pagination and
// return all regions at once.
// It reduces max gRPC message size.
func PaginateScanRegion(
ctx context.Context, client SplitClient, startKey, endKey []byte, limit int,
) ([]*RegionInfo, error) {
if len(endKey) != 0 && bytes.Compare(startKey, endKey) >= 0 {
return nil, errors.Annotatef(berrors.ErrRestoreInvalidRange, "startKey >= endKey, startKey %s, endkey %s",
hex.EncodeToString(startKey), hex.EncodeToString(endKey))
}
regions := []*RegionInfo{}
for {
batch, err := client.ScanRegions(ctx, startKey, endKey, limit)
if err != nil {
return nil, errors.Trace(err)
}
regions = append(regions, batch...)
if len(batch) < limit {
// No more region
break
}
startKey = batch[len(batch)-1].Region.GetEndKey()
if len(startKey) == 0 ||
(len(endKey) > 0 && bytes.Compare(startKey, endKey) >= 0) {
// All key space have scanned
break
}
}
return regions, nil
}
// getSplitKeys checks if the regions should be split by the new prefix of the rewrites rule and the end key of
// the ranges, groups the split keys by region id.
func getSplitKeys(rewriteRules *RewriteRules, ranges []rtree.Range, regions []*RegionInfo) map[uint64][][]byte {
splitKeyMap := make(map[uint64][][]byte)
checkKeys := make([][]byte, 0)
for _, rule := range rewriteRules.Table {
checkKeys = append(checkKeys, rule.GetNewKeyPrefix())
}
for _, rule := range rewriteRules.Data {
checkKeys = append(checkKeys, rule.GetNewKeyPrefix())
}
for _, rg := range ranges {
checkKeys = append(checkKeys, rg.EndKey)
}
for _, key := range checkKeys {
if region := NeedSplit(key, regions); region != nil {
splitKeys, ok := splitKeyMap[region.Region.GetId()]
if !ok {
splitKeys = make([][]byte, 0, 1)
}
splitKeyMap[region.Region.GetId()] = append(splitKeys, key)
log.Debug("get key for split region",
logutil.Key("key", key),
logutil.Key("startKey", region.Region.StartKey),
logutil.Key("endKey", region.Region.EndKey))
}
}
return splitKeyMap
}
// NeedSplit checks whether a key is necessary to split, if true returns the split region.
func NeedSplit(splitKey []byte, regions []*RegionInfo) *RegionInfo {
// If splitKey is the max key.
if len(splitKey) == 0 {
return nil
}
splitKey = codec.EncodeBytes(splitKey)
for _, region := range regions {
// If splitKey is the boundary of the region
if bytes.Equal(splitKey, region.Region.GetStartKey()) {
return nil
}
// If splitKey is in a region
if region.ContainsInterior(splitKey) {
return region
}
}
return nil
}
func replacePrefix(s []byte, rewriteRules *RewriteRules) ([]byte, *sst.RewriteRule) {
// We should search the dataRules firstly.
for _, rule := range rewriteRules.Data {
if bytes.HasPrefix(s, rule.GetOldKeyPrefix()) {
return append(append([]byte{}, rule.GetNewKeyPrefix()...), s[len(rule.GetOldKeyPrefix()):]...), rule
}
}
for _, rule := range rewriteRules.Table {
if bytes.HasPrefix(s, rule.GetOldKeyPrefix()) {
return append(append([]byte{}, rule.GetNewKeyPrefix()...), s[len(rule.GetOldKeyPrefix()):]...), rule
}
}
return s, nil
}
func beforeEnd(key []byte, end []byte) bool {
return bytes.Compare(key, end) < 0 || len(end) == 0
}
func intersectRange(region *metapb.Region, rg Range) Range {
var startKey, endKey []byte
if len(region.StartKey) > 0 {
_, startKey, _ = codec.DecodeBytes(region.StartKey)
}
if bytes.Compare(startKey, rg.Start) < 0 {
startKey = rg.Start
}
if len(region.EndKey) > 0 {
_, endKey, _ = codec.DecodeBytes(region.EndKey)
}
if beforeEnd(rg.End, endKey) {
endKey = rg.End
}
return Range{Start: startKey, End: endKey}
}
func insideRegion(region *metapb.Region, meta *sst.SSTMeta) bool {
rg := meta.GetRange()
return keyInsideRegion(region, rg.GetStart()) && keyInsideRegion(region, rg.GetEnd())
}
func keyInsideRegion(region *metapb.Region, key []byte) bool {
return bytes.Compare(key, region.GetStartKey()) >= 0 && (beforeEnd(key, region.GetEndKey()))
}