diff options
| -rw-r--r-- | src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp | 29 | ||||
| -rw-r--r-- | src/mongo/db/s/balancer/balancer_policy.cpp | 450 | ||||
| -rw-r--r-- | src/mongo/db/s/balancer/balancer_policy.h | 58 | ||||
| -rw-r--r-- | src/mongo/db/s/balancer/balancer_policy_test.cpp | 510 | ||||
| -rw-r--r-- | src/mongo/s/chunk_manager.h | 17 |
5 files changed, 456 insertions, 608 deletions
diff --git a/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp b/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp index 07427b21879..8371a27b950 100644 --- a/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp +++ b/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp @@ -47,9 +47,9 @@ #include "mongo/s/catalog/type_collection.h" #include "mongo/s/catalog/type_tags.h" #include "mongo/s/catalog_cache.h" -#include "mongo/s/chunk_manager.h" #include "mongo/s/grid.h" #include "mongo/util/str.h" + namespace mongo { using MigrateInfoVector = BalancerChunkSelectionPolicy::MigrateInfoVector; @@ -90,6 +90,27 @@ StatusWith<DistributionStatus> createCollectionDistributionStatus( const NamespaceString& nss, const ShardStatisticsVector& allShards, const ChunkManager& chunkMgr) { + ShardToChunksMap shardToChunksMap; + + // Makes sure there is an entry in shardToChunksMap for every shard, so empty shards will also + // be accounted for + for (const auto& stat : allShards) { + shardToChunksMap[stat.shardId]; + } + + chunkMgr.forEachChunk([&](const auto& chunkEntry) { + ChunkType chunk; + chunk.setNS(nss); + chunk.setMin(chunkEntry.getMin()); + chunk.setMax(chunkEntry.getMax()); + chunk.setJumbo(chunkEntry.isJumbo()); + chunk.setShard(chunkEntry.getShardId()); + chunk.setVersion(chunkEntry.getLastmod()); + + shardToChunksMap[chunkEntry.getShardId()].push_back(chunk); + + return true; + }); auto swZoneInfo = createCollectionZoneInfo(opCtx, nss, chunkMgr.getShardKeyPattern().getKeyPattern()); @@ -97,7 +118,7 @@ StatusWith<DistributionStatus> createCollectionDistributionStatus( return swZoneInfo.getStatus(); } - return {DistributionStatus{nss, std::move(swZoneInfo.getValue()), chunkMgr}}; + return {DistributionStatus{nss, std::move(shardToChunksMap), std::move(swZoneInfo.getValue())}}; } /** @@ -505,7 +526,7 @@ Status BalancerChunkSelectionPolicyImpl::checkMoveAllowed(OperationContext* opCt } return BalancerPolicy::isShardSuitableReceiver(*newShardIterator, - distribution.getTagForRange(chunk.getRange())); + distribution.getTagForChunk(chunk)); } StatusWith<SplitInfoVector> BalancerChunkSelectionPolicyImpl::_getSplitCandidatesForCollection( @@ -565,7 +586,7 @@ StatusWith<MigrateInfoVector> BalancerChunkSelectionPolicyImpl::_getMigrateCandi const DistributionStatus& distribution = collInfoStatus.getValue(); - for (const auto& tagRangeEntry : distribution.getZoneInfo().zoneRanges()) { + for (const auto& tagRangeEntry : distribution.tagRanges()) { const auto& tagRange = tagRangeEntry.second; const auto chunkAtZoneMin = cm.findIntersectingChunkWithSimpleCollation(tagRange.min); diff --git a/src/mongo/db/s/balancer/balancer_policy.cpp b/src/mongo/db/s/balancer/balancer_policy.cpp index 4e11ab57cb8..ec4041b9667 100644 --- a/src/mongo/db/s/balancer/balancer_policy.cpp +++ b/src/mongo/db/s/balancer/balancer_policy.cpp @@ -58,134 +58,65 @@ namespace { // optimal average across all shards for a zone for a rebalancing migration to be initiated. const size_t kDefaultImbalanceThreshold = 1; -ChunkType makeChunkType(const NamespaceString& nss, const Chunk& chunk) { - ChunkType ct{nss, chunk.getRange(), chunk.getLastmod(), chunk.getShardId()}; - ct.setJumbo(chunk.isJumbo()); - return ct; -} - -/** - * Return a vector of zones after they have been normalized according to the given chunk - * configuration. - * - * If a zone covers only partially a chunk, boundaries of that zone will be shrank so that the - * normalized zone won't overlap with that chunk. The boundaries of a normalized zone will never - * fall in the middle of a chunk. - * - * Additionally the vector will contain also zones for the "NoZone", - */ -std::vector<ZoneRange> normalizeZones(const ChunkManager& cm, const ZoneInfo& zoneInfo) { - std::vector<ZoneRange> normalizedRanges; - - auto lastMax = cm.getShardKeyPattern().getKeyPattern().globalMin(); - - for (const auto& [max, zoneRange] : zoneInfo.zoneRanges()) { - const auto& minChunk = cm.findIntersectingChunkWithSimpleCollation(zoneRange.min); - const auto gtMin = - SimpleBSONObjComparator::kInstance.evaluate(zoneRange.min > minChunk.getMin()); - const auto& normalizedMin = gtMin ? minChunk.getMax() : zoneRange.min; - - - const auto& maxChunk = cm.findIntersectingChunkWithSimpleCollation(zoneRange.max); - const auto gtMax = - SimpleBSONObjComparator::kInstance.evaluate(zoneRange.max > maxChunk.getMin()) && - SimpleBSONObjComparator::kInstance.evaluate( - zoneRange.max != cm.getShardKeyPattern().getKeyPattern().globalMax()); - const auto& normalizedMax = gtMax ? maxChunk.getMin() : zoneRange.max; - - - if (SimpleBSONObjComparator::kInstance.evaluate(normalizedMin == normalizedMax)) { - // This zone does not fully contain any chunk thus we can ignore it - continue; - } +} // namespace - if (SimpleBSONObjComparator::kInstance.evaluate(normalizedMin != lastMax)) { - // The zone is not contiguous with the previous one so we add a kNoZoneRange - // does not fully contain any chunk so we will ignore it - normalizedRanges.emplace_back(lastMax, normalizedMin, ZoneInfo::kNoZoneName); - } +DistributionStatus::DistributionStatus(NamespaceString nss, + ShardToChunksMap shardToChunksMap, + ZoneInfo zoneInfo) + : _nss(std::move(nss)), + _shardChunks(std::move(shardToChunksMap)), + _zoneInfo(std::move(zoneInfo)) {} - normalizedRanges.emplace_back(normalizedMin, normalizedMax, zoneRange.zone); - lastMax = normalizedMax; - } +size_t DistributionStatus::totalChunks() const { + size_t total = 0; - const auto& globalMaxKey = cm.getShardKeyPattern().getKeyPattern().globalMax(); - if (SimpleBSONObjComparator::kInstance.evaluate(lastMax != globalMaxKey)) { - normalizedRanges.emplace_back(lastMax, globalMaxKey, ZoneInfo::kNoZoneName); + for (const auto& shardChunk : _shardChunks) { + total += shardChunk.second.size(); } - return normalizedRanges; -} - -} // namespace -DistributionStatus::DistributionStatus(NamespaceString nss, - ZoneInfo zoneInfo, - const ChunkManager& chunkMngr) - : _nss(std::move(nss)), _zoneInfo(std::move(zoneInfo)), _chunkMngr(chunkMngr) { - - _normalizedZones = normalizeZones(_chunkMngr, _zoneInfo); - - for (const auto& zoneRange : _normalizedZones) { - chunkMngr.forEachOverlappingChunk( - zoneRange.min, zoneRange.max, false /* isMaxInclusive */, [&](const auto& chunkInfo) { - _shardToZoneSizeMap[chunkInfo.getShardId()][zoneRange.zone]++; - return true; - }); - } + return total; } size_t DistributionStatus::totalChunksWithTag(const std::string& tag) const { size_t total = 0; - for (const auto& [_, zoneSizeMap] : _shardToZoneSizeMap) { - const auto& zoneIt = zoneSizeMap.find(tag); - if (zoneIt != zoneSizeMap.end()) { - total += zoneIt->second; - } + + for (const auto& shardChunk : _shardChunks) { + total += numberOfChunksInShardWithTag(shardChunk.first, tag); } + return total; } size_t DistributionStatus::numberOfChunksInShard(const ShardId& shardId) const { - const auto shardZonesIt = _shardToZoneSizeMap.find(shardId); - if (shardZonesIt == _shardToZoneSizeMap.end()) { - return 0; - } - size_t total = 0; - for (const auto& [_, numChunks] : shardZonesIt->second) { - total += numChunks; - } - return total; + const auto& shardChunks = getChunks(shardId); + return shardChunks.size(); } size_t DistributionStatus::numberOfChunksInShardWithTag(const ShardId& shardId, const string& tag) const { - const auto shardZonesIt = _shardToZoneSizeMap.find(shardId); - if (shardZonesIt == _shardToZoneSizeMap.end()) { - return 0; - } - const auto& shardTags = shardZonesIt->second; + const auto& shardChunks = getChunks(shardId); - const auto& zoneIt = shardTags.find(tag); - if (zoneIt == shardTags.end()) { - return 0; + size_t total = 0; + + for (const auto& chunk : shardChunks) { + if (tag == getTagForChunk(chunk)) { + total++; + } } - return zoneIt->second; -} -string DistributionStatus::getTagForRange(const ChunkRange& range) const { - return _zoneInfo.getZoneForChunk(range); + return total; } -const StringMap<size_t>& DistributionStatus::getChunksPerTagMap(const ShardId& shardId) const { - static const StringMap<size_t> emptyMap; - const auto shardZonesIt = _shardToZoneSizeMap.find(shardId); - if (shardZonesIt == _shardToZoneSizeMap.end()) { - return emptyMap; - } - return shardZonesIt->second; +const vector<ChunkType>& DistributionStatus::getChunks(const ShardId& shardId) const { + ShardToChunksMap::const_iterator i = _shardChunks.find(shardId); + invariant(i != _shardChunks.end()); + + return i->second; } -const string ZoneInfo::kNoZoneName = ""; +string DistributionStatus::getTagForChunk(const ChunkType& chunk) const { + return _zoneInfo.getZoneForChunk(chunk.getRange()); +} ZoneInfo::ZoneInfo() : _zoneRanges(SimpleBSONObjComparator::kInstance.makeBSONObjIndexedMap<ZoneRange>()) {} @@ -237,11 +168,11 @@ string ZoneInfo::getZoneForChunk(const ChunkRange& chunk) const { // We should never have a partial overlap with a chunk range. If it happens, treat it as if this // chunk doesn't belong to a tag if (minIntersect != maxIntersect) { - return ZoneInfo::kNoZoneName; + return ""; } if (minIntersect == _zoneRanges.end()) { - return ZoneInfo::kNoZoneName; + return ""; } const ZoneRange& intersectRange = minIntersect->second; @@ -252,7 +183,7 @@ string ZoneInfo::getZoneForChunk(const ChunkRange& chunk) const { return intersectRange.zone; } - return ZoneInfo::kNoZoneName; + return ""; } void DistributionStatus::report(BSONObjBuilder* builder) const { @@ -260,15 +191,15 @@ void DistributionStatus::report(BSONObjBuilder* builder) const { // Report all shards BSONArrayBuilder shardArr(builder->subarrayStart("shards")); - for (const auto& [shardId, zoneSizeMap] : _shardToZoneSizeMap) { + for (const auto& shardChunk : _shardChunks) { BSONObjBuilder shardEntry(shardArr.subobjStart()); - shardEntry.append("name", shardId.toString()); + shardEntry.append("name", shardChunk.first.toString()); - BSONObjBuilder tagsObj(shardEntry.subobjStart("tags")); - for (const auto& [tagName, numChunks] : zoneSizeMap) { - tagsObj.appendNumber(tagName, static_cast<long long>(numChunks)); + BSONArrayBuilder chunkArr(shardEntry.subarrayStart("chunks")); + for (const auto& chunk : shardChunk.second) { + chunkArr.append(chunk.toConfigBSON()); } - tagsObj.doneFast(); + chunkArr.doneFast(); shardEntry.doneFast(); } @@ -311,7 +242,7 @@ Status BalancerPolicy::isShardSuitableReceiver(const ClusterStatistics::ShardSta str::stream() << stat.shardId << " is currently draining."}; } - if (chunkTag != ZoneInfo::kNoZoneName && !stat.shardTags.count(chunkTag)) { + if (!chunkTag.empty() && !stat.shardTags.count(chunkTag)) { return {ErrorCodes::IllegalOperation, str::stream() << stat.shardId << " is not in the correct zone " << chunkTag}; } @@ -429,28 +360,10 @@ MigrateInfo chooseRandomMigration(const ShardStatisticsVector& shardStats, "fromShardId"_attr = sourceShardId, "toShardId"_attr = destShardId); - const auto& randomChunk = [&] { - const auto numChunksOnSourceShard = distribution.numberOfChunksInShard(sourceShardId); - const auto rndChunkIdx = getRandomIndex(numChunksOnSourceShard); - ChunkType rndChunk; - - int idx{0}; - distribution.getChunkManager().forEachChunk([&](const auto& chunk) { - if (chunk.getShardId() == sourceShardId && idx++ == rndChunkIdx) { - rndChunk = makeChunkType(distribution.nss(), chunk); - rndChunk.setJumbo(chunk.isJumbo()); - return false; - } - return true; - }); - - invariant(rndChunk.getShard().isValid()); - return rndChunk; - }(); - + const auto& chunks = distribution.getChunks(sourceShardId); return {destShardId, - randomChunk, + chunks[getRandomIndex(chunks.size())], MoveChunkRequest::ForceJumbo::kDoNotForce, MigrateInfo::chunksImbalance}; } @@ -482,70 +395,57 @@ vector<MigrateInfo> BalancerPolicy::balance(const ShardStatisticsVector& shardSt if (!availableShards->count(stat.shardId)) continue; + const vector<ChunkType>& chunks = distribution.getChunks(stat.shardId); + + if (chunks.empty()) + continue; + // Now we know we need to move to chunks off this shard, but only if permitted by the // tags policy unsigned numJumboChunks = 0; - const auto& chunksPerTagMap = distribution.getChunksPerTagMap(stat.shardId); - for (const auto& tagIt : chunksPerTagMap) { - const auto& zoneName = tagIt.first; - for (const auto& zoneRange : distribution.getNormalizedZones()) { - if (zoneRange.zone != zoneName) { - continue; - } + // Since we have to move all chunks, lets just do in order + for (const auto& chunk : chunks) { + if (chunk.getJumbo()) { + numJumboChunks++; + continue; + } - distribution.getChunkManager().forEachOverlappingChunk( - zoneRange.min, - zoneRange.max, - false /* isMaxInclusive */, - [&](const auto& chunk) { - if (chunk.getShardId() != stat.shardId) { - return true; // continue - } - if (chunk.isJumbo()) { - numJumboChunks++; - return true; // continue - } - - const ShardId to = _getLeastLoadedReceiverShard( - shardStats, distribution, zoneName, *availableShards); - if (!to.isValid()) { - if (migrations.empty()) { - LOGV2_WARNING( - 21889, - "Chunk {chunk} is on a draining shard, but no appropriate " - "recipient found", - "Chunk is on a draining shard, but no appropriate " - "recipient found", - "chunk"_attr = redact( - makeChunkType(distribution.nss(), chunk).toString())); - } - return true; // continue - } - invariant(to != stat.shardId); - - migrations.emplace_back(to, - makeChunkType(distribution.nss(), chunk), - MoveChunkRequest::ForceJumbo::kForceBalancer, - MigrateInfo::drain); - invariant(availableShards->erase(stat.shardId)); - invariant(availableShards->erase(to)); - return false; // break - }); + const string tag = distribution.getTagForChunk(chunk); + const ShardId to = + _getLeastLoadedReceiverShard(shardStats, distribution, tag, *availableShards); + if (!to.isValid()) { if (migrations.empty()) { - LOGV2_WARNING(21890, - "Unable to find any chunk to move from draining shard " - "{shardId}. numJumboChunks: {numJumboChunks}", - "Unable to find any chunk to move from draining shard", - "shardId"_attr = stat.shardId, - "numJumboChunks"_attr = numJumboChunks); - } - - if (availableShards->size() < 2) { - return migrations; + LOGV2_WARNING(21889, + "Chunk {chunk} is on a draining shard, but no appropriate " + "recipient found", + "Chunk is on a draining shard, but no appropriate " + "recipient found", + "chunk"_attr = redact(chunk.toString())); } + continue; } + + invariant(to != stat.shardId); + migrations.emplace_back( + to, chunk, MoveChunkRequest::ForceJumbo::kForceBalancer, MigrateInfo::drain); + invariant(availableShards->erase(stat.shardId)); + invariant(availableShards->erase(to)); + break; + } + + if (migrations.empty()) { + LOGV2_WARNING(21890, + "Unable to find any chunk to move from draining shard " + "{shardId}. numJumboChunks: {numJumboChunks}", + "Unable to find any chunk to move from draining shard", + "shardId"_attr = stat.shardId, + "numJumboChunks"_attr = numJumboChunks); + } + + if (availableShards->size() < 2) { + return migrations; } } } @@ -553,77 +453,57 @@ vector<MigrateInfo> BalancerPolicy::balance(const ShardStatisticsVector& shardSt // 2) Check for chunks, which are on the wrong shard and must be moved off of it if (!distribution.tags().empty()) { for (const auto& stat : shardStats) { - if (!availableShards->count(stat.shardId)) continue; - const auto& chunksPerTagMap = distribution.getChunksPerTagMap(stat.shardId); - for (const auto& tagIt : chunksPerTagMap) { - const auto& zoneName = tagIt.first; + const vector<ChunkType>& chunks = distribution.getChunks(stat.shardId); - if (zoneName == ZoneInfo::kNoZoneName) + for (const auto& chunk : chunks) { + const string tag = distribution.getTagForChunk(chunk); + + if (tag.empty()) continue; - if (stat.shardTags.count(zoneName)) + if (stat.shardTags.count(tag)) continue; - for (const auto& zoneRange : distribution.getNormalizedZones()) { - if (zoneRange.zone != zoneName) { - continue; - } - distribution.getChunkManager().forEachOverlappingChunk( - zoneRange.min, - zoneRange.max, - false /* isMaxInclusive */, - [&](const auto& chunk) { - if (chunk.getShardId() != stat.shardId) { - return true; // continue - } - if (chunk.isJumbo()) { - LOGV2_WARNING( - 21891, - "Chunk {chunk} violates zone {zone}, but it is jumbo and " - "cannot be " - "moved", - "Chunk violates zone, but it is jumbo and cannot be moved", - "chunk"_attr = - redact(makeChunkType(distribution.nss(), chunk).toString()), - "zone"_attr = redact(zoneName)); - return true; // continue - } - - const ShardId to = _getLeastLoadedReceiverShard( - shardStats, distribution, zoneName, *availableShards); - if (!to.isValid()) { - if (migrations.empty()) { - LOGV2_WARNING( - 21892, - "Chunk {chunk} violates zone {zone}, but no appropriate " - "recipient found", - "Chunk violates zone, but no appropriate recipient found", - "chunk"_attr = redact( - makeChunkType(distribution.nss(), chunk).toString()), - "zone"_attr = redact(zoneName)); - } - return true; // continue - } - invariant(to != stat.shardId); - - migrations.emplace_back( - to, - makeChunkType(distribution.nss(), chunk), - forceJumbo ? MoveChunkRequest::ForceJumbo::kForceBalancer - : MoveChunkRequest::ForceJumbo::kDoNotForce, - MigrateInfo::zoneViolation); - invariant(availableShards->erase(stat.shardId)); - invariant(availableShards->erase(to)); - return false; // break - }); + if (chunk.getJumbo()) { + LOGV2_WARNING( + 21891, + "Chunk {chunk} violates zone {zone}, but it is jumbo and cannot be moved", + "Chunk violates zone, but it is jumbo and cannot be moved", + "chunk"_attr = redact(chunk.toString()), + "zone"_attr = redact(tag)); + continue; } - if (availableShards->size() < 2) { - return migrations; + const ShardId to = + _getLeastLoadedReceiverShard(shardStats, distribution, tag, *availableShards); + if (!to.isValid()) { + if (migrations.empty()) { + LOGV2_WARNING(21892, + "Chunk {chunk} violates zone {zone}, but no appropriate " + "recipient found", + "Chunk violates zone, but no appropriate recipient found", + "chunk"_attr = redact(chunk.toString()), + "zone"_attr = redact(tag)); + } + continue; } + + invariant(to != stat.shardId); + migrations.emplace_back(to, + chunk, + forceJumbo ? MoveChunkRequest::ForceJumbo::kForceBalancer + : MoveChunkRequest::ForceJumbo::kDoNotForce, + MigrateInfo::zoneViolation); + invariant(availableShards->erase(stat.shardId)); + invariant(availableShards->erase(to)); + break; + } + + if (availableShards->size() < 2) { + return migrations; } } } @@ -631,35 +511,24 @@ vector<MigrateInfo> BalancerPolicy::balance(const ShardStatisticsVector& shardSt // 3) for each tag balance vector<string> tagsPlusEmpty(distribution.tags().begin(), distribution.tags().end()); - tagsPlusEmpty.push_back(ZoneInfo::kNoZoneName); + tagsPlusEmpty.push_back(""); for (const auto& tag : tagsPlusEmpty) { + const size_t totalNumberOfChunksWithTag = + (tag.empty() ? distribution.totalChunks() : distribution.totalChunksWithTag(tag)); - const auto totalNumberOfChunksWithTag = [&] { - if (tag == ZoneInfo::kNoZoneName) { - return static_cast<size_t>(distribution.getChunkManager().numChunks()); - } - return distribution.totalChunksWithTag(tag); - }(); + size_t totalNumberOfShardsWithTag = 0; - const auto totalNumberOfShardsWithTag = [&] { - if (tag == ZoneInfo::kNoZoneName) { - return shardStats.size(); - } - - size_t numShardsWithTag{0}; - for (const auto& stat : shardStats) { - if (stat.shardTags.count(tag)) { - numShardsWithTag++; - } + for (const auto& stat : shardStats) { + if (tag.empty() || stat.shardTags.count(tag)) { + totalNumberOfShardsWithTag++; } - return numShardsWithTag; - }(); + } // Skip zones which have no shards assigned to them. This situation is not harmful, but // should not be possible so warn the operator to correct it. if (totalNumberOfShardsWithTag == 0) { - if (tag != ZoneInfo::kNoZoneName) { + if (!tag.empty()) { LOGV2_WARNING( 21893, "Zone {zone} in collection {namespace} has no assigned shards and chunks " @@ -696,7 +565,7 @@ boost::optional<MigrateInfo> BalancerPolicy::balanceSingleChunk( const ChunkType& chunk, const ShardStatisticsVector& shardStats, const DistributionStatus& distribution) { - const string tag = distribution.getTagForRange(chunk.getRange()); + const string tag = distribution.getTagForChunk(chunk); stdx::unordered_set<ShardId> availableShards; std::transform(shardStats.begin(), @@ -773,41 +642,26 @@ bool BalancerPolicy::_singleZoneBalance(const ShardStatisticsVector& shardStats, if (imbalance < kDefaultImbalanceThreshold) return false; + const vector<ChunkType>& chunks = distribution.getChunks(from); + unsigned numJumboChunks = 0; - bool chunkFound = false; - for (const auto& zoneRange : distribution.getNormalizedZones()) { - if (zoneRange.zone != tag) { + for (const auto& chunk : chunks) { + if (distribution.getTagForChunk(chunk) != tag) continue; - } - - distribution.getChunkManager().forEachOverlappingChunk( - zoneRange.min, zoneRange.max, false /* isMaxInclusive */, [&](const auto& chunk) { - if (chunk.getShardId() != from) { - return true; // continue - } - if (chunk.isJumbo()) { - numJumboChunks++; - return true; // continue - } - - migrations->emplace_back(to, - makeChunkType(distribution.nss(), chunk), - forceJumbo, - MigrateInfo::chunksImbalance); - invariant(availableShards->erase(chunk.getShardId())); - invariant(availableShards->erase(to)); - chunkFound = true; - return false; // break - }); - - if (chunkFound) { - return chunkFound; + if (chunk.getJumbo()) { + numJumboChunks++; + continue; } + + migrations->emplace_back(to, chunk, forceJumbo, MigrateInfo::chunksImbalance); + invariant(availableShards->erase(chunk.getShard())); + invariant(availableShards->erase(to)); + return true; } - if (!chunkFound && numJumboChunks) { + if (numJumboChunks) { LOGV2_WARNING( 21894, "Shard: {shardId}, collection: {namespace} has only jumbo chunks for " @@ -819,7 +673,7 @@ bool BalancerPolicy::_singleZoneBalance(const ShardStatisticsVector& shardStats, "numJumboChunks"_attr = numJumboChunks); } - return chunkFound; + return false; } ZoneRange::ZoneRange(const BSONObj& a_min, const BSONObj& a_max, const std::string& _zone) diff --git a/src/mongo/db/s/balancer/balancer_policy.h b/src/mongo/db/s/balancer/balancer_policy.h index 46a4adf6a14..b8403c3881f 100644 --- a/src/mongo/db/s/balancer/balancer_policy.h +++ b/src/mongo/db/s/balancer/balancer_policy.h @@ -37,12 +37,12 @@ #include "mongo/db/namespace_string.h" #include "mongo/db/s/balancer/cluster_statistics.h" #include "mongo/s/catalog/type_chunk.h" -#include "mongo/s/chunk_manager.h" #include "mongo/s/request_types/move_chunk_request.h" #include "mongo/s/shard_id.h" namespace mongo { + struct ZoneRange { ZoneRange(const BSONObj& a_min, const BSONObj& a_max, const std::string& _zone); @@ -78,15 +78,13 @@ struct MigrateInfo { }; typedef std::vector<ClusterStatistics::ShardStatistics> ShardStatisticsVector; -typedef std::map<ShardId, StringMap<size_t>> ShardToZoneSizeMap; +typedef std::map<ShardId, std::vector<ChunkType>> ShardToChunksMap; /** * Keeps track of zones for a collection. */ class ZoneInfo { public: - static const std::string kNoZoneName; - ZoneInfo(); ZoneInfo(ZoneInfo&&) = default; @@ -116,14 +114,6 @@ public: return _zoneRanges; } - const ZoneRange& getZoneRange(const std::string& zoneName) const { - for (const auto& [_, zoneRange] : _zoneRanges) { - if (zoneRange.zone == zoneName) - return zoneRange; - } - MONGO_UNREACHABLE; - } - private: // Map of zone max key to the zone description BSONObjIndexedMap<ZoneRange> _zoneRanges; @@ -142,7 +132,7 @@ class DistributionStatus { DistributionStatus& operator=(const DistributionStatus&) = delete; public: - DistributionStatus(NamespaceString nss, ZoneInfo zoneInfo, const ChunkManager& chunkMngr); + DistributionStatus(NamespaceString nss, ShardToChunksMap shardToChunksMap, ZoneInfo zoneInfo); DistributionStatus(DistributionStatus&&) = default; /** @@ -153,6 +143,11 @@ public: } /** + * Returns total number of chunks across all shards. + */ + size_t totalChunks() const; + + /** * Returns the total number of chunks across all shards, which fall into the specified zone's * range. */ @@ -169,6 +164,18 @@ public: size_t numberOfChunksInShardWithTag(const ShardId& shardId, const std::string& tag) const; /** + * Returns all chunks for the specified shard. + */ + const std::vector<ChunkType>& getChunks(const ShardId& shardId) const; + + /** + * Returns all tag ranges defined for the collection. + */ + const BSONObjIndexedMap<ZoneRange>& tagRanges() const { + return _zoneInfo.zoneRanges(); + } + + /** * Returns all tags defined for the collection. */ const std::set<std::string>& tags() const { @@ -179,21 +186,7 @@ public: * Using the set of tags defined for the collection, returns what tag corresponds to the * specified chunk. If the chunk doesn't fall into any tag returns the empty string. */ - std::string getTagForRange(const ChunkRange& range) const; - - const ChunkManager& getChunkManager() const { - return _chunkMngr; - } - - const std::vector<ZoneRange>& getNormalizedZones() const { - return _normalizedZones; - } - - const ZoneInfo& getZoneInfo() const { - return _zoneInfo; - } - - const StringMap<size_t>& getChunksPerTagMap(const ShardId& shardId) const; + std::string getTagForChunk(const ChunkType& chunk) const; /** * Returns a BSON/string representation of this distribution status. @@ -205,16 +198,11 @@ private: // Namespace for which this distribution applies NamespaceString _nss; - // Map that tracks how many chunks every shard is owning in each zone - // shardId -> zoneName -> numChunks - ShardToZoneSizeMap _shardToZoneSizeMap; + // Map of what chunks are owned by each shard + ShardToChunksMap _shardChunks; // Info for zones. ZoneInfo _zoneInfo; - - std::vector<ZoneRange> _normalizedZones; - - ChunkManager _chunkMngr; }; class BalancerPolicy { diff --git a/src/mongo/db/s/balancer/balancer_policy_test.cpp b/src/mongo/db/s/balancer/balancer_policy_test.cpp index 7441dfab2c7..8f3b340c82d 100644 --- a/src/mongo/db/s/balancer/balancer_policy_test.cpp +++ b/src/mongo/db/s/balancer/balancer_policy_test.cpp @@ -46,11 +46,9 @@ using std::stringstream; using std::vector; using ShardStatistics = ClusterStatistics::ShardStatistics; -typedef std::map<ShardId, std::vector<ChunkType>> ShardToChunksMap; const auto emptyTagSet = std::set<std::string>(); const std::string emptyShardVersion = ""; -const auto kConfigId = ShardId("config"); const auto kShardId0 = ShardId("shard0"); const auto kShardId1 = ShardId("shard1"); const auto kShardId2 = ShardId("shard2"); @@ -59,36 +57,6 @@ const auto kShardId4 = ShardId("shard4"); const auto kShardId5 = ShardId("shard5"); const NamespaceString kNamespace("TestDB", "TestColl"); const uint64_t kNoMaxSize = 0; -const KeyPattern kSKeyPattern(BSON("x" << 1)); -const boost::optional<Timestamp> kCollTimestamp; -const OID kCollEpoch; - -RoutingTableHistory makeRoutingTable(const std::vector<ChunkType>& chunks) { - static const UUID kCollectionUUID{UUID::gen()}; - - return RoutingTableHistory::makeNew(kNamespace, - kCollectionUUID, - kSKeyPattern, - nullptr, - false, - kCollEpoch, - kCollTimestamp, - boost::none /* timeseriesFields */, - boost::none /* reshardingFields */, - true, - chunks); -} - -ChunkManager makeChunkManager(const std::vector<ChunkType>& chunks) { - DatabaseVersion dbVersion; - auto rt = std::make_shared<RoutingTableHistory>(makeRoutingTable(chunks)); - - return {kConfigId, std::move(dbVersion), {std::move(rt)}, kCollTimestamp}; -} - -DistributionStatus makeDistStatus(const ChunkManager& cm, ZoneInfo zoneInfo = ZoneInfo()) { - return {kNamespace, std::move(zoneInfo), cm}; -} /** * Constructs a shard statistics vector and a consistent mapping of chunks to shards given the @@ -97,7 +65,7 @@ DistributionStatus makeDistStatus(const ChunkManager& cm, ZoneInfo zoneInfo = Zo * * [MinKey, 1), [1, 2), [2, 3) ... [N - 1, MaxKey) */ -std::pair<std::pair<ShardStatisticsVector, ShardToChunksMap>, ChunkManager> generateCluster( +std::pair<ShardStatisticsVector, ShardToChunksMap> generateCluster( const vector<std::pair<ShardStatistics, size_t>>& shardsAndNumChunks) { int64_t totalNumChunks = 0; for (const auto& entry : shardsAndNumChunks) { @@ -109,9 +77,9 @@ std::pair<std::pair<ShardStatisticsVector, ShardToChunksMap>, ChunkManager> gene int64_t currentChunk = 0; - ChunkVersion chunkVersion(1, 0, kCollEpoch, kCollTimestamp); + ChunkVersion chunkVersion(1, 0, OID::gen(), boost::none /* timestamp */); - std::vector<ChunkType> chunks; + const KeyPattern shardKeyPattern(BSON("x" << 1)); for (auto it = shardsAndNumChunks.begin(); it != shardsAndNumChunks.end(); it++) { ShardStatistics shard = std::move(it->first); @@ -124,23 +92,22 @@ std::pair<std::pair<ShardStatisticsVector, ShardToChunksMap>, ChunkManager> gene ChunkType chunk; chunk.setNS(kNamespace); - chunk.setMin(currentChunk == 0 ? kSKeyPattern.globalMin() : BSON("x" << currentChunk)); - chunk.setMax(currentChunk == totalNumChunks - 1 ? kSKeyPattern.globalMax() + chunk.setMin(currentChunk == 0 ? shardKeyPattern.globalMin() + : BSON("x" << currentChunk)); + chunk.setMax(currentChunk == totalNumChunks - 1 ? shardKeyPattern.globalMax() : BSON("x" << currentChunk + 1)); chunk.setShard(shard.shardId); chunk.setVersion(chunkVersion); chunkVersion.incMajor(); - chunkMap[shard.shardId].push_back(chunk); - chunks.push_back(std::move(chunk)); + chunkMap[shard.shardId].push_back(std::move(chunk)); } shardStats.push_back(std::move(shard)); } - return std::make_pair(std::make_pair(std::move(shardStats), std::move(chunkMap)), - makeChunkManager(chunks)); + return std::make_pair(std::move(shardStats), std::move(chunkMap)); } std::vector<MigrateInfo> balanceChunks(const ShardStatisticsVector& shardStats, @@ -158,12 +125,13 @@ std::vector<MigrateInfo> balanceChunks(const ShardStatisticsVector& shardStats, } TEST(BalancerPolicy, Basic) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}, {ShardStatistics(kShardId2, kNoMaxSize, 3, false, emptyTagSet, emptyShardVersion), 3}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); ASSERT_EQ(kShardId1, migrations[0].to); @@ -173,12 +141,13 @@ TEST(BalancerPolicy, Basic) { } TEST(BalancerPolicy, SmallClusterShouldBePerfectlyBalanced) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 1, false, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId1, kNoMaxSize, 2, false, emptyTagSet, emptyShardVersion), 2}, {ShardStatistics(kShardId2, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId1, migrations[0].from); ASSERT_EQ(kShardId2, migrations[0].to); @@ -188,33 +157,46 @@ TEST(BalancerPolicy, SmallClusterShouldBePerfectlyBalanced) { } TEST(BalancerPolicy, SingleChunkShouldNotMove) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 1, false, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId1, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}}); - ASSERT(balanceChunks(cluster.first, makeDistStatus(cm), true, false).empty()); - ASSERT(balanceChunks(cluster.first, makeDistStatus(cm), false, false).empty()); + ASSERT( + balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), true, false) + .empty()); + ASSERT( + balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false) + .empty()); } TEST(BalancerPolicy, BalanceThresholdObeyed) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, false, emptyTagSet, emptyShardVersion), 2}, {ShardStatistics(kShardId1, kNoMaxSize, 2, false, emptyTagSet, emptyShardVersion), 2}, {ShardStatistics(kShardId2, kNoMaxSize, 1, false, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId3, kNoMaxSize, 1, false, emptyTagSet, emptyShardVersion), 1}}); - ASSERT(balanceChunks(cluster.first, makeDistStatus(cm), true, false).empty()); - ASSERT(balanceChunks(cluster.first, makeDistStatus(cm), false, false).empty()); + ASSERT( + balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), true, false) + .empty()); + ASSERT( + balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false) + .empty()); } TEST(BalancerPolicy, ParallelBalancing) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId2, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}, {ShardStatistics(kShardId3, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(2U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); @@ -231,7 +213,7 @@ TEST(BalancerPolicy, ParallelBalancing) { } TEST(BalancerPolicy, ParallelBalancingDoesNotPutChunksOnShardsAboveTheOptimal) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 100, false, emptyTagSet, emptyShardVersion), 100}, {ShardStatistics(kShardId1, kNoMaxSize, 90, false, emptyTagSet, emptyShardVersion), 90}, {ShardStatistics(kShardId2, kNoMaxSize, 90, false, emptyTagSet, emptyShardVersion), 90}, @@ -239,7 +221,8 @@ TEST(BalancerPolicy, ParallelBalancingDoesNotPutChunksOnShardsAboveTheOptimal) { {ShardStatistics(kShardId4, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}, {ShardStatistics(kShardId5, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(2U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); @@ -256,13 +239,14 @@ TEST(BalancerPolicy, ParallelBalancingDoesNotPutChunksOnShardsAboveTheOptimal) { } TEST(BalancerPolicy, ParallelBalancingDoesNotMoveChunksFromShardsBelowOptimal) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 100, false, emptyTagSet, emptyShardVersion), 100}, {ShardStatistics(kShardId1, kNoMaxSize, 30, false, emptyTagSet, emptyShardVersion), 30}, {ShardStatistics(kShardId2, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 5}, {ShardStatistics(kShardId3, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); @@ -273,7 +257,7 @@ TEST(BalancerPolicy, ParallelBalancingDoesNotMoveChunksFromShardsBelowOptimal) { } TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseSourceShardsWithMoveNecessary) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 8, false, emptyTagSet, emptyShardVersion), 8}, {ShardStatistics(kShardId1, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId2, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}, @@ -282,7 +266,10 @@ TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseSourceShardsWithMoveNe // Here kShardId0 would have been selected as a donor stdx::unordered_set<ShardId> availableShards{kShardId1, kShardId2, kShardId3}; const auto migrations( - BalancerPolicy::balance(cluster.first, makeDistStatus(cm), &availableShards, false)); + BalancerPolicy::balance(cluster.first, + DistributionStatus(kNamespace, cluster.second, ZoneInfo()), + &availableShards, + false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId1, migrations[0].from); @@ -293,7 +280,7 @@ TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseSourceShardsWithMoveNe } TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseSourceShardsWithMoveNotNecessary) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 12, false, emptyTagSet, emptyShardVersion), 12}, {ShardStatistics(kShardId1, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId2, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}, @@ -302,12 +289,15 @@ TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseSourceShardsWithMoveNo // Here kShardId0 would have been selected as a donor stdx::unordered_set<ShardId> availableShards{kShardId1, kShardId2, kShardId3}; const auto migrations( - BalancerPolicy::balance(cluster.first, makeDistStatus(cm), &availableShards, false)); + BalancerPolicy::balance(cluster.first, + DistributionStatus(kNamespace, cluster.second, ZoneInfo()), + &availableShards, + false)); ASSERT_EQ(0U, migrations.size()); } TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseDestinationShards) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId2, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}, @@ -316,7 +306,10 @@ TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseDestinationShards) { // Here kShardId2 would have been selected as a recipient stdx::unordered_set<ShardId> availableShards{kShardId0, kShardId1, kShardId3}; const auto migrations( - BalancerPolicy::balance(cluster.first, makeDistStatus(cm), &availableShards, false)); + BalancerPolicy::balance(cluster.first, + DistributionStatus(kNamespace, cluster.second, ZoneInfo()), + &availableShards, + false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); @@ -326,115 +319,68 @@ TEST(BalancerPolicy, ParallelBalancingNotSchedulingOnInUseDestinationShards) { ASSERT_EQ(MigrateInfo::chunksImbalance, migrations[0].reason); } -TEST(BalancerPolicy, JumboChunksNotMovedWhileEnforcingZones) { - auto [cluster, cm] = generateCluster( - {{ShardStatistics(kShardId0, kNoMaxSize, 3, false, emptyTagSet, emptyShardVersion), 3}, - {ShardStatistics(kShardId1, kNoMaxSize, 3, false, {"a"}, emptyShardVersion), 3}}); - - // construct a new chunk map where all the chunks are jumbo except this one - const auto& jumboChunk = cluster.second[kShardId0][1]; - - std::vector<ChunkType> chunks; - cm.forEachChunk([&](const auto& chunk) { - ChunkType ct{kNamespace, chunk.getRange(), chunk.getLastmod(), chunk.getShardId()}; - if (chunk.getLastmod() == jumboChunk.getVersion()) - ct.setJumbo(false); - else - ct.setJumbo(true); - chunks.emplace_back(std::move(ct)); - return true; - }); - - ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone( - ZoneRange(kSKeyPattern.globalMin(), kSKeyPattern.globalMax(), "a"))); - const auto distribution = makeDistStatus(makeChunkManager(chunks), std::move(zoneInfo)); - - const auto migrations(balanceChunks(cluster.first, distribution, false, false)); - ASSERT_EQ(1U, migrations.size()); - ASSERT_EQ(kShardId0, migrations[0].from); - ASSERT_EQ(kShardId1, migrations[0].to); - ASSERT_BSONOBJ_EQ(jumboChunk.getMin(), migrations[0].minKey); - ASSERT_BSONOBJ_EQ(jumboChunk.getMax(), migrations[0].maxKey); - ASSERT_EQ(MigrateInfo::zoneViolation, migrations[0].reason); -} - TEST(BalancerPolicy, JumboChunksNotMoved) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}}); - // construct a new chunk map where all the chunks are jumbo except this one - const auto& jumboChunk = cluster.second[kShardId0][1]; - - std::vector<ChunkType> chunks; - cm.forEachChunk([&](const auto& chunk) { - ChunkType ct{kNamespace, chunk.getRange(), chunk.getLastmod(), chunk.getShardId()}; - if (chunk.getLastmod() == jumboChunk.getVersion()) - ct.setJumbo(false); - else - ct.setJumbo(true); - chunks.emplace_back(std::move(ct)); - return true; - }); + cluster.second[kShardId0][0].setJumbo(true); + cluster.second[kShardId0][1].setJumbo(false); // Only chunk 1 is not jumbo + cluster.second[kShardId0][2].setJumbo(true); + cluster.second[kShardId0][3].setJumbo(true); - const auto migrations( - balanceChunks(cluster.first, makeDistStatus(makeChunkManager(chunks)), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); ASSERT_EQ(kShardId1, migrations[0].to); - ASSERT_BSONOBJ_EQ(jumboChunk.getMin(), migrations[0].minKey); - ASSERT_BSONOBJ_EQ(jumboChunk.getMax(), migrations[0].maxKey); + ASSERT_BSONOBJ_EQ(cluster.second[kShardId0][1].getMin(), migrations[0].minKey); + ASSERT_BSONOBJ_EQ(cluster.second[kShardId0][1].getMax(), migrations[0].maxKey); ASSERT_EQ(MigrateInfo::chunksImbalance, migrations[0].reason); } TEST(BalancerPolicy, JumboChunksNotMovedParallel) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}, {ShardStatistics(kShardId2, kNoMaxSize, 2, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId3, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 0}}); - // construct a new chunk map where all the chunks are jumbo except the ones listed below - const auto& jumboChunk0 = cluster.second[kShardId0][1]; - const auto& jumboChunk1 = cluster.second[kShardId2][2]; - - std::vector<ChunkType> chunks; - cm.forEachChunk([&](const auto& chunk) { - ChunkType ct{kNamespace, chunk.getRange(), chunk.getLastmod(), chunk.getShardId()}; - if (chunk.getLastmod() == jumboChunk0.getVersion() || - chunk.getLastmod() == jumboChunk1.getVersion()) - ct.setJumbo(false); - else - ct.setJumbo(true); - chunks.emplace_back(std::move(ct)); - return true; - }); + cluster.second[kShardId0][0].setJumbo(true); + cluster.second[kShardId0][1].setJumbo(false); // Only chunk 1 is not jumbo + cluster.second[kShardId0][2].setJumbo(true); + cluster.second[kShardId0][3].setJumbo(true); - const auto migrations( - balanceChunks(cluster.first, makeDistStatus(makeChunkManager(chunks)), false, false)); + cluster.second[kShardId2][0].setJumbo(true); + cluster.second[kShardId2][1].setJumbo(true); + cluster.second[kShardId2][2].setJumbo(false); // Only chunk 1 is not jumbo + cluster.second[kShardId2][3].setJumbo(true); + + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(2U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); ASSERT_EQ(kShardId1, migrations[0].to); - ASSERT_BSONOBJ_EQ(jumboChunk0.getMin(), migrations[0].minKey); - ASSERT_BSONOBJ_EQ(jumboChunk0.getMax(), migrations[0].maxKey); + ASSERT_BSONOBJ_EQ(cluster.second[kShardId0][1].getMin(), migrations[0].minKey); + ASSERT_BSONOBJ_EQ(cluster.second[kShardId0][1].getMax(), migrations[0].maxKey); ASSERT_EQ(MigrateInfo::chunksImbalance, migrations[0].reason); ASSERT_EQ(kShardId2, migrations[1].from); ASSERT_EQ(kShardId3, migrations[1].to); - ASSERT_BSONOBJ_EQ(jumboChunk1.getMin(), migrations[1].minKey); - ASSERT_BSONOBJ_EQ(jumboChunk1.getMax(), migrations[1].maxKey); + ASSERT_BSONOBJ_EQ(cluster.second[kShardId2][2].getMin(), migrations[1].minKey); + ASSERT_BSONOBJ_EQ(cluster.second[kShardId2][2].getMax(), migrations[1].maxKey); ASSERT_EQ(MigrateInfo::chunksImbalance, migrations[1].reason); } TEST(BalancerPolicy, DrainingSingleChunk) { // shard0 is draining and chunks will go to shard1, even though it has a lot more chunks - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, true, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId1, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 5}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); ASSERT_EQ(kShardId1, migrations[0].to); @@ -445,13 +391,14 @@ TEST(BalancerPolicy, DrainingSingleChunk) { TEST(BalancerPolicy, DrainingSingleChunkPerShard) { // shard0 and shard2 are draining and chunks will go to shard1 and shard3 in parallel - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, true, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId1, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 5}, {ShardStatistics(kShardId2, kNoMaxSize, 2, true, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId3, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 5}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(2U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); @@ -469,11 +416,12 @@ TEST(BalancerPolicy, DrainingSingleChunkPerShard) { TEST(BalancerPolicy, DrainingWithTwoChunksFirstOneSelected) { // shard0 is draining and chunks will go to shard1, even though it has a lot more chunks - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, true, emptyTagSet, emptyShardVersion), 2}, {ShardStatistics(kShardId1, kNoMaxSize, 0, false, emptyTagSet, emptyShardVersion), 5}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); ASSERT_EQ(kShardId1, migrations[0].to); @@ -485,12 +433,13 @@ TEST(BalancerPolicy, DrainingWithTwoChunksFirstOneSelected) { TEST(BalancerPolicy, DrainingMultipleShardsFirstOneSelected) { // shard0 and shard1 are both draining with very little chunks in them and chunks will go to // shard2, even though it has a lot more chunks that the other two - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, true, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId1, kNoMaxSize, 5, true, emptyTagSet, emptyShardVersion), 2}, {ShardStatistics(kShardId2, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 16}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId0, migrations[0].from); ASSERT_EQ(kShardId2, migrations[0].to); @@ -501,17 +450,18 @@ TEST(BalancerPolicy, DrainingMultipleShardsFirstOneSelected) { TEST(BalancerPolicy, DrainingMultipleShardsWontAcceptChunks) { // shard0 has many chunks, but can't move them to shard1 or shard2 because they are draining - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 0, true, emptyTagSet, emptyShardVersion), 0}, {ShardStatistics(kShardId2, kNoMaxSize, 0, true, emptyTagSet, emptyShardVersion), 0}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT(migrations.empty()); } TEST(BalancerPolicy, DrainingSingleAppropriateShardFoundDueToTag) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, false, {"NYC"}, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 2, false, {"LAX"}, emptyShardVersion), 4}, {ShardStatistics(kShardId2, kNoMaxSize, 1, true, {"LAX"}, emptyShardVersion), 1}}); @@ -519,7 +469,7 @@ TEST(BalancerPolicy, DrainingSingleAppropriateShardFoundDueToTag) { ZoneInfo zoneInfo; ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange( cluster.second[kShardId2][0].getMin(), cluster.second[kShardId2][0].getMax(), "LAX"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT_EQ(1U, migrations.size()); @@ -531,7 +481,7 @@ TEST(BalancerPolicy, DrainingSingleAppropriateShardFoundDueToTag) { } TEST(BalancerPolicy, DrainingNoAppropriateShardsFoundDueToTag) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, false, {"NYC"}, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 2, false, {"LAX"}, emptyShardVersion), 4}, {ShardStatistics(kShardId2, kNoMaxSize, 1, true, {"SEA"}, emptyShardVersion), 1}}); @@ -539,7 +489,7 @@ TEST(BalancerPolicy, DrainingNoAppropriateShardsFoundDueToTag) { ZoneInfo zoneInfo; ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange( cluster.second[kShardId2][0].getMin(), cluster.second[kShardId2][0].getMax(), "SEA"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT(migrations.empty()); @@ -547,12 +497,13 @@ TEST(BalancerPolicy, DrainingNoAppropriateShardsFoundDueToTag) { TEST(BalancerPolicy, NoBalancingDueToAllNodesEitherDrainingOrMaxedOut) { // shard0 and shard2 are draining, shard1 is maxed out - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 2, true, emptyTagSet, emptyShardVersion), 1}, {ShardStatistics(kShardId1, 1, 1, false, emptyTagSet, emptyShardVersion), 6}, {ShardStatistics(kShardId2, kNoMaxSize, 1, true, emptyTagSet, emptyShardVersion), 1}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT(migrations.empty()); } @@ -560,12 +511,13 @@ TEST(BalancerPolicy, BalancerRespectsMaxShardSizeOnlyBalanceToNonMaxed) { // Note that maxSize of shard0 is 1, and it is therefore overloaded with currSize = 3. Other // shards have maxSize = 0 = unset. Even though the overloaded shard has the least number of // less chunks, we shouldn't move chunks to that shard. - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, 1, 3, false, emptyTagSet, emptyShardVersion), 2}, {ShardStatistics(kShardId1, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 5}, {ShardStatistics(kShardId2, kNoMaxSize, 10, false, emptyTagSet, emptyShardVersion), 10}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT_EQ(1U, migrations.size()); ASSERT_EQ(kShardId2, migrations[0].from); ASSERT_EQ(kShardId1, migrations[0].to); @@ -577,26 +529,27 @@ TEST(BalancerPolicy, BalancerRespectsMaxShardSizeWhenAllBalanced) { // Note that maxSize of shard0 is 1, and it is therefore overloaded with currSize = 4. Other // shards have maxSize = 0 = unset. We check that being over the maxSize is NOT equivalent to // draining, we don't want to empty shards for no other reason than they are over this limit. - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, 1, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId1, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}, {ShardStatistics(kShardId2, kNoMaxSize, 4, false, emptyTagSet, emptyShardVersion), 4}}); - const auto migrations(balanceChunks(cluster.first, makeDistStatus(cm), false, false)); + const auto migrations(balanceChunks( + cluster.first, DistributionStatus(kNamespace, cluster.second, ZoneInfo()), false, false)); ASSERT(migrations.empty()); } TEST(BalancerPolicy, BalancerRespectsTagsWhenDraining) { // shard1 drains the proper chunk to shard0, even though it is more loaded than shard2 - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 6}, - {ShardStatistics(kShardId1, kNoMaxSize, 5, true, {"a", "b"}, emptyShardVersion), 1}, + {ShardStatistics(kShardId1, kNoMaxSize, 5, true, {"a", "b"}, emptyShardVersion), 2}, {ShardStatistics(kShardId2, kNoMaxSize, 5, false, {"b"}, emptyShardVersion), 2}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 7), "a"))); - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 8), kSKeyPattern.globalMax(), "b"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 7), "a"))); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 8), kMaxBSONKey, "b"))); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT_EQ(1U, migrations.size()); @@ -610,14 +563,14 @@ TEST(BalancerPolicy, BalancerRespectsTagsWhenDraining) { TEST(BalancerPolicy, BalancerRespectsTagPolicyBeforeImbalance) { // There is a large imbalance between shard0 and shard1, but the balancer must first fix the // chunks, which are on a wrong shard due to tag policy - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 2}, {ShardStatistics(kShardId1, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 6}, {ShardStatistics(kShardId2, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 2}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 100), "a"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 100), "a"))); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT_EQ(1U, migrations.size()); @@ -631,15 +584,15 @@ TEST(BalancerPolicy, BalancerRespectsTagPolicyBeforeImbalance) { TEST(BalancerPolicy, BalancerFixesIncorrectTagsWithCrossShardViolationOfTags) { // The zone policy dictates that the same shard must donate and also receive chunks. The test // validates that the same shard is not used as a donor and recipient as part of the same round. - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 3}, {ShardStatistics(kShardId1, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 3}, {ShardStatistics(kShardId2, kNoMaxSize, 5, false, {"b"}, emptyShardVersion), 3}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 1), "b"))); - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 8), kSKeyPattern.globalMax(), "a"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 1), "b"))); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 8), kMaxBSONKey, "a"))); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT_EQ(1U, migrations.size()); @@ -652,14 +605,14 @@ TEST(BalancerPolicy, BalancerFixesIncorrectTagsWithCrossShardViolationOfTags) { TEST(BalancerPolicy, BalancerFixesIncorrectTagsInOtherwiseBalancedCluster) { // Chunks are balanced across shards, but there are wrong tags, which need to be fixed - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 3}, {ShardStatistics(kShardId1, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 3}, {ShardStatistics(kShardId2, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 3}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 10), "a"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 10), "a"))); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT_EQ(1U, migrations.size()); @@ -672,30 +625,29 @@ TEST(BalancerPolicy, BalancerFixesIncorrectTagsInOtherwiseBalancedCluster) { TEST(BalancerPolicy, BalancerTagAlreadyBalanced) { // Chunks are balanced across shards for the tag. - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 3, false, {"a"}, emptyShardVersion), 2}, {ShardStatistics(kShardId1, kNoMaxSize, 2, false, {"a"}, emptyShardVersion), 2}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone( - ZoneRange(kSKeyPattern.globalMin(), kSKeyPattern.globalMax(), "a"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, kMaxBSONKey, "a"))); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); ASSERT(balanceChunks(cluster.first, distribution, false, false).empty()); } TEST(BalancerPolicy, BalancerMostOverLoadShardHasMultipleTags) { // shard0 has chunks [MinKey, 1), [1, 2), [2, 3), [3, 4), [4, 5), so two chunks each // for tag "b" and "c". So [1, 2) is expected to be moved to shard1 in round 1. - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a", "b", "c"}, emptyShardVersion), 5}, {ShardStatistics(kShardId1, kNoMaxSize, 1, false, {"b"}, emptyShardVersion), 1}, {ShardStatistics(kShardId2, kNoMaxSize, 1, false, {"c"}, emptyShardVersion), 1}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 1), "a"))); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 1), "a"))); ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 1), BSON("x" << 3), "b"))); ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 3), BSON("x" << 5), "c"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT_EQ(1U, migrations.size()); @@ -710,16 +662,16 @@ TEST(BalancerPolicy, BalancerMostOverLoadShardHasMultipleTagsSkipTagWithShardInU // shard0 has chunks [MinKey, 1), [1, 2), [2, 3), [3, 4), [4, 5), so two chunks each // for tag "b" and "c". So [3, 4) is expected to be moved to shard2 because shard1 is // in use. - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a", "b", "c"}, emptyShardVersion), 5}, {ShardStatistics(kShardId1, kNoMaxSize, 1, false, {"b"}, emptyShardVersion), 1}, {ShardStatistics(kShardId2, kNoMaxSize, 1, false, {"c"}, emptyShardVersion), 1}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 1), "a"))); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 1), "a"))); ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 1), BSON("x" << 3), "b"))); ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 3), BSON("x" << 5), "c"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); stdx::unordered_set<ShardId> availableShards{kShardId0, kShardId2, kShardId3}; const auto migrations( @@ -734,15 +686,15 @@ TEST(BalancerPolicy, BalancerMostOverLoadShardHasMultipleTagsSkipTagWithShardInU TEST(BalancerPolicy, BalancerFixesIncorrectTagsInOtherwiseBalancedClusterParallel) { // Chunks are balanced across shards, but there are wrong tags, which need to be fixed - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 3}, {ShardStatistics(kShardId1, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 3}, {ShardStatistics(kShardId2, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 3}, {ShardStatistics(kShardId3, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 3}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 20), "a"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 20), "a"))); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); const auto migrations(balanceChunks(cluster.first, distribution, false, false)); ASSERT_EQ(2U, migrations.size()); @@ -760,55 +712,14 @@ TEST(BalancerPolicy, BalancerFixesIncorrectTagsInOtherwiseBalancedClusterParalle ASSERT_EQ(MigrateInfo::zoneViolation, migrations[0].reason); } -TEST(BalancerPolicy, ChunksInNoZoneSpanOnAllShardsWithEmptyZones) { - // Balanacer is able to move chunks in the noZone to shards with tags - auto [cluster, cm] = generateCluster( - {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 3}, - {ShardStatistics(kShardId1, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 0}}); - - ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(BSON("x" << 100), kSKeyPattern.globalMax(), "a"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); - - const auto migrations(balanceChunks(cluster.first, distribution, false, false)); - ASSERT_EQ(1U, migrations.size()); - - ASSERT_EQ(kShardId0, migrations[0].from); - ASSERT_EQ(kShardId1, migrations[0].to); - ASSERT_BSONOBJ_EQ(cluster.second[kShardId0][0].getMin(), migrations[0].minKey); - ASSERT_BSONOBJ_EQ(cluster.second[kShardId0][0].getMax(), migrations[0].maxKey); - ASSERT_EQ(MigrateInfo::chunksImbalance, migrations[0].reason); -} - -TEST(BalancerPolicy, BalancingNoZoneIgnoreTotalShardSize) { - // Shard1 is overloaded and contains: - // [min, 1) [1, 2) [2, 3] -> zone("a") - // [3, 4) [4, 5) [5, 6) -> NoZone - // - // But it won't donate any chunk since the - auto [cluster, cm] = generateCluster( - {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 3}, - {ShardStatistics(kShardId1, kNoMaxSize, 5, false, {"a"}, emptyShardVersion), 6}, - {ShardStatistics(kShardId2, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 3}}); - - ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 6), "a"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); - - const auto migrations(balanceChunks(cluster.first, distribution, false, false)); - ASSERT_EQ(0U, migrations.size()); -} - - TEST(BalancerPolicy, BalancerHandlesNoShardsWithTag) { - auto [cluster, cm] = generateCluster( + auto cluster = generateCluster( {{ShardStatistics(kShardId0, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 2}, {ShardStatistics(kShardId1, kNoMaxSize, 5, false, emptyTagSet, emptyShardVersion), 2}}); ZoneInfo zoneInfo; - ASSERT_OK(zoneInfo.addRangeToZone( - ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 7), "NonExistentZone"))); - const auto distribution = makeDistStatus(cm, std::move(zoneInfo)); + ASSERT_OK(zoneInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 7), "NonExistentZone"))); + DistributionStatus distribution(kNamespace, cluster.second, std::move(zoneInfo)); ASSERT(balanceChunks(cluster.first, distribution, false, false).empty()); } @@ -821,7 +732,7 @@ TEST(DistributionStatus, AddTagRangeOverlap) { ASSERT_OK(zInfo.addRangeToZone(ZoneRange(BSON("x" << 20), BSON("x" << 30), "b"))); ASSERT_EQ(ErrorCodes::RangeOverlapConflict, - zInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << 2), "d"))); + zInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << 2), "d"))); ASSERT_EQ(ErrorCodes::RangeOverlapConflict, zInfo.addRangeToZone(ZoneRange(BSON("x" << -1), BSON("x" << 5), "d"))); ASSERT_EQ(ErrorCodes::RangeOverlapConflict, @@ -833,7 +744,7 @@ TEST(DistributionStatus, AddTagRangeOverlap) { ASSERT_EQ(ErrorCodes::RangeOverlapConflict, zInfo.addRangeToZone(ZoneRange(BSON("x" << -1), BSON("x" << 32), "d"))); ASSERT_EQ(ErrorCodes::RangeOverlapConflict, - zInfo.addRangeToZone(ZoneRange(BSON("x" << 25), kSKeyPattern.globalMax(), "d"))); + zInfo.addRangeToZone(ZoneRange(BSON("x" << 25), kMaxBSONKey, "d"))); } TEST(DistributionStatus, ChunkTagsSelectorWithRegularKeys) { @@ -841,37 +752,128 @@ TEST(DistributionStatus, ChunkTagsSelectorWithRegularKeys) { ASSERT_OK(zInfo.addRangeToZone(ZoneRange(BSON("x" << 1), BSON("x" << 10), "a"))); ASSERT_OK(zInfo.addRangeToZone(ZoneRange(BSON("x" << 10), BSON("x" << 20), "b"))); ASSERT_OK(zInfo.addRangeToZone(ZoneRange(BSON("x" << 20), BSON("x" << 30), "c"))); + DistributionStatus d(kNamespace, ShardToChunksMap{}, std::move(zInfo)); + + { + ChunkType chunk; + chunk.setMin(kMinBSONKey); + chunk.setMax(BSON("x" << 1)); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 0)); + chunk.setMax(BSON("x" << 1)); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 1)); + chunk.setMax(BSON("x" << 5)); + ASSERT_EQUALS("a", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 10)); + chunk.setMax(BSON("x" << 20)); + ASSERT_EQUALS("b", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 15)); + chunk.setMax(BSON("x" << 20)); + ASSERT_EQUALS("b", d.getTagForChunk(chunk)); + } - ASSERT_EQUALS(ZoneInfo::kNoZoneName, - zInfo.getZoneForChunk({kSKeyPattern.globalMin(), BSON("x" << 1)})); - ASSERT_EQUALS(ZoneInfo::kNoZoneName, zInfo.getZoneForChunk({BSON("x" << 0), BSON("x" << 1)})); - ASSERT_EQUALS("a", zInfo.getZoneForChunk({BSON("x" << 1), BSON("x" << 5)})); - ASSERT_EQUALS("b", zInfo.getZoneForChunk({BSON("x" << 10), BSON("x" << 20)})); - ASSERT_EQUALS("b", zInfo.getZoneForChunk({BSON("x" << 15), BSON("x" << 20)})); - ASSERT_EQUALS("c", zInfo.getZoneForChunk({BSON("x" << 25), BSON("x" << 30)})); - ASSERT_EQUALS(ZoneInfo::kNoZoneName, zInfo.getZoneForChunk({BSON("x" << 35), BSON("x" << 40)})); - ASSERT_EQUALS(ZoneInfo::kNoZoneName, - zInfo.getZoneForChunk({BSON("x" << 30), kSKeyPattern.globalMax()})); - ASSERT_EQUALS(ZoneInfo::kNoZoneName, - zInfo.getZoneForChunk({BSON("x" << 40), kSKeyPattern.globalMax()})); + { + ChunkType chunk; + chunk.setMin(BSON("x" << 25)); + chunk.setMax(BSON("x" << 30)); + ASSERT_EQUALS("c", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 35)); + chunk.setMax(BSON("x" << 40)); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 30)); + chunk.setMax(kMaxBSONKey); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 40)); + chunk.setMax(kMaxBSONKey); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } } TEST(DistributionStatus, ChunkTagsSelectorWithMinMaxKeys) { ZoneInfo zInfo; - ASSERT_OK(zInfo.addRangeToZone(ZoneRange(kSKeyPattern.globalMin(), BSON("x" << -100), "a"))); + ASSERT_OK(zInfo.addRangeToZone(ZoneRange(kMinBSONKey, BSON("x" << -100), "a"))); ASSERT_OK(zInfo.addRangeToZone(ZoneRange(BSON("x" << -10), BSON("x" << 10), "b"))); - ASSERT_OK(zInfo.addRangeToZone(ZoneRange(BSON("x" << 100), kSKeyPattern.globalMax(), "c"))); - - ASSERT_EQUALS("a", zInfo.getZoneForChunk({kSKeyPattern.globalMin(), BSON("x" << -100)})); - ASSERT_EQUALS(ZoneInfo::kNoZoneName, - zInfo.getZoneForChunk({BSON("x" << -100), BSON("x" << -11)})); - ASSERT_EQUALS("b", zInfo.getZoneForChunk({BSON("x" << -10), BSON("x" << 0)})); - ASSERT_EQUALS("b", zInfo.getZoneForChunk({BSON("x" << 0), BSON("x" << 10)})); - ASSERT_EQUALS(ZoneInfo::kNoZoneName, zInfo.getZoneForChunk({BSON("x" << 10), BSON("x" << 20)})); - ASSERT_EQUALS(ZoneInfo::kNoZoneName, - zInfo.getZoneForChunk({BSON("x" << 10), BSON("x" << 100)})); - ASSERT_EQUALS("c", zInfo.getZoneForChunk({BSON("x" << 200), kSKeyPattern.globalMax()})); + ASSERT_OK(zInfo.addRangeToZone(ZoneRange(BSON("x" << 100), kMaxBSONKey, "c"))); + DistributionStatus d(kNamespace, ShardToChunksMap{}, std::move(zInfo)); + + { + ChunkType chunk; + chunk.setMin(kMinBSONKey); + chunk.setMax(BSON("x" << -100)); + ASSERT_EQUALS("a", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << -100)); + chunk.setMax(BSON("x" << -11)); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << -10)); + chunk.setMax(BSON("x" << 0)); + ASSERT_EQUALS("b", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 0)); + chunk.setMax(BSON("x" << 10)); + ASSERT_EQUALS("b", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 10)); + chunk.setMax(BSON("x" << 20)); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 10)); + chunk.setMax(BSON("x" << 100)); + ASSERT_EQUALS("", d.getTagForChunk(chunk)); + } + + { + ChunkType chunk; + chunk.setMin(BSON("x" << 200)); + chunk.setMax(kMaxBSONKey); + ASSERT_EQUALS("c", d.getTagForChunk(chunk)); + } } } // namespace diff --git a/src/mongo/s/chunk_manager.h b/src/mongo/s/chunk_manager.h index 138b04ffe34..d8ab66bc59f 100644 --- a/src/mongo/s/chunk_manager.h +++ b/src/mongo/s/chunk_manager.h @@ -680,23 +680,6 @@ public: }); } - template <typename Callable> - void forEachOverlappingChunk(const BSONObj& min, - const BSONObj& max, - bool isMaxInclusive, - Callable&& handler) const { - _rt->optRt->forEachOverlappingChunk( - min, - max, - isMaxInclusive, - [this, handler = std::forward<Callable>(handler)](const auto& chunkInfo) mutable { - if (!handler(Chunk{*chunkInfo, _clusterTime})) { - return false; - } - return true; - }); - } - /** * Returns true if a document with the given "shardKey" is owned by the shard with the given * "shardId" in this routing table. If "shardKey" is empty returns false. If "shardKey" is not a |