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
|
/*
* Utilities for dealing with chunk bounds.
*/
var chunkBoundsUtil = (function() {
let eq = function(shardKeyA, shardKeyB) {
return bsonWoCompare(shardKeyA, shardKeyB) == 0;
};
let gte = function(shardKeyA, shardKeyB) {
return bsonWoCompare(shardKeyA, shardKeyB) >= 0;
};
let lt = function(shardKeyA, shardKeyB) {
return bsonWoCompare(shardKeyA, shardKeyB) < 0;
};
let max = function(shardKeyA, shardKeyB) {
return gte(shardKeyA, shardKeyB) ? shardKeyA : shardKeyB;
};
let min = function(shardKeyA, shardKeyB) {
return lt(shardKeyA, shardKeyB) ? shardKeyA : shardKeyB;
};
let containsKey = function(shardKey, minKey, maxKey) {
return gte(shardKey, minKey) && lt(shardKey, maxKey);
};
let overlapsWith = function(chunkBoundsA, chunkBoundsB) {
return containsKey(chunkBoundsA[0], chunkBoundsB[0], chunkBoundsB[1]) ||
containsKey(chunkBoundsA[1], chunkBoundsB[0], chunkBoundsB[1]);
};
/*
* Combines chunk bounds chunkBoundsA and chunkBoundsB. Assumes that the bounds
* overlap.
*/
let combine = function(chunkBoundsA, chunkBoundsB) {
let rangeMin = min(chunkBoundsA[0], chunkBoundsB[0]);
let rangeMax = max(chunkBoundsA[1], chunkBoundsB[1]);
return [rangeMin, rangeMax];
};
/*
* Computes the range that the given chunk bounds are in by combining the given chunk
* bounds into bounds for one chunk. Assumes the chunk bounds are contiguous and in
* nondescending order.
*/
let computeRange = function(allChunkBounds) {
let combinedBounds = allChunkBounds[0];
for (let i = 1; i < allChunkBounds.length; i++) {
assert(overlapsWith(combinedBounds, allChunkBounds[i]));
combinedBounds = combine(combinedBounds, allChunkBounds[i]);
}
return combinedBounds;
};
/*
* Returns a object mapping each shard name to an array of chunk bounds
* that it owns.
*
* @param chunkDocs {Array} an array of chunk documents in the config database.
*/
let findShardChunkBounds = function(chunkDocs) {
let allBounds = {};
for (let chunkDoc of chunkDocs) {
let bounds = [chunkDoc.min, chunkDoc.max];
if (!(chunkDoc.shard in allBounds)) {
allBounds[chunkDoc.shard] = [bounds];
} else {
allBounds[chunkDoc.shard].push(bounds);
}
}
return allBounds;
};
/*
* Returns the corresponding shard object for the given shard name.
*/
let _getShard = function(st, shardName) {
for (let i = 0; i < st._connections.length; i++) {
const conn = st._connections[i];
if (conn.shardName === shardName) {
return conn;
}
}
};
/*
* Returns the shard object for the shard that owns the chunk that contains
* the given shard key value and the bounds of the chunk.
*
* @param shardChunkBounds {Object} a map from each shard name to an array of the bounds
* for all the chunks on the shard. Each pair of chunk
* bounds is an array of the form [minKey, maxKey].
*/
let findShardAndChunkBoundsForShardKey = function(st, shardChunkBounds, shardKey) {
for (const [shardName, chunkBounds] of Object.entries(shardChunkBounds)) {
for (let bounds of chunkBounds) {
if (containsKey(shardKey, bounds[0], bounds[1])) {
return {shard: _getShard(st, shardName), bounds: bounds};
}
}
}
};
/*
* Returns the shard object for the shard that owns the chunk that contains
* the given shard key value.
*
* @param shardChunkBounds {Object} a map from each shard name to an array of the bounds
* for all the chunks on the shard. Each pair of chunk
* bounds is an array of the form [minKey, maxKey].
*/
let findShardForShardKey = function(st, shardChunkBounds, shardKey) {
return findShardAndChunkBoundsForShardKey(st, shardChunkBounds, shardKey).shard;
};
return {
eq,
gte,
lt,
computeRange,
containsKey,
findShardChunkBounds,
findShardAndChunkBoundsForShardKey,
findShardForShardKey
};
})();
|
