SERVER-32526 Use KeyString for ChunkMap key instead of BSONObj

4 files changed, 224 insertions, 175 deletions

diff --git a/src/mongo/db/s/collection_metadata.cpp b/src/mongo/db/s/collection_metadata.cpp
index 20b419d0bc5..7d357f415f7 100644
--- a/src/mongo/db/s/collection_metadata.cpp
+++ b/src/mongo/db/s/collection_metadata.cpp
@@ -44,9 +44,8 @@ namespace mongo {
 CollectionMetadata::CollectionMetadata(std::shared_ptr<ChunkManager> cm, const ShardId& thisShardId)
     : _cm(std::move(cm)),
       _thisShardId(thisShardId),
-      _shardVersion(_cm->getVersion(_thisShardId)),
-      _chunksMap(SimpleBSONObjComparator::kInstance.makeBSONObjIndexedMap<BSONObj>()),
-      _rangesMap(SimpleBSONObjComparator::kInstance.makeBSONObjIndexedMap<BSONObj>()) {
+      _shardVersion(_cm->getVersion(thisShardId)),
+      _chunksMap(SimpleBSONObjComparator::kInstance.makeBSONObjIndexedMap<BSONObj>()) {
 
     invariant(_cm->getVersion().isSet());
     invariant(_cm->getVersion() >= _shardVersion);
@@ -63,103 +62,34 @@ CollectionMetadata::CollectionMetadata(std::shared_ptr<ChunkManager> cm, const S
         return;
     }
     invariant(_shardVersion.isSet());
-
-    _buildRangesMap();
-}
-
-CollectionMetadata::~CollectionMetadata() = default;
-
-void CollectionMetadata::_buildRangesMap() {
-    _rangesMap.clear();
-
-    // Load the chunk information, coalescing their ranges. The version for this shard would be
-    // the highest version for any of the chunks.
-
-    BSONObj min, max;
-
-    for (const auto& entry : _chunksMap) {
-        BSONObj const& currMin = entry.first;
-        BSONObj const& currMax = entry.second;
-
-        // Coalesce the chunk's bounds in ranges if they are adjacent chunks
-        if (min.isEmpty()) {
-            min = currMin;
-            max = currMax;
-            continue;
-        }
-
-        if (SimpleBSONObjComparator::kInstance.evaluate(max == currMin)) {
-            max = currMax;
-            continue;
-        }
-
-        _rangesMap.emplace_hint(_rangesMap.end(), min, max);
-
-        min = currMin;
-        max = currMax;
-    }
-
-    invariant(!min.isEmpty());
-    invariant(!max.isEmpty());
-
-    _rangesMap.emplace(min, max);
-}
-
-bool CollectionMetadata::keyBelongsToMe(const BSONObj& key) const {
-    if (_rangesMap.empty()) {
-        return false;
-    }
-
-    auto it = _rangesMap.upper_bound(key);
-    if (it != _rangesMap.begin())
-        it--;
-
-    return rangeContains(it->first, it->second, key);
 }
 
 bool CollectionMetadata::getNextChunk(const BSONObj& lookupKey, ChunkType* chunk) const {
-    RangeMap::const_iterator upperChunkIt = _chunksMap.upper_bound(lookupKey);
-    RangeMap::const_iterator lowerChunkIt = upperChunkIt;
-
-    if (upperChunkIt != _chunksMap.begin()) {
-        --lowerChunkIt;
-    } else {
-        lowerChunkIt = _chunksMap.end();
-    }
-
-    if (lowerChunkIt != _chunksMap.end() && lowerChunkIt->second.woCompare(lookupKey) > 0) {
-        chunk->setMin(lowerChunkIt->first);
-        chunk->setMax(lowerChunkIt->second);
-        return true;
-    }
-
-    if (upperChunkIt != _chunksMap.end()) {
-        chunk->setMin(upperChunkIt->first);
-        chunk->setMax(upperChunkIt->second);
-        return true;
-    }
+    auto foundIt = _cm->getNextChunkOnShard(lookupKey, _thisShardId);
+    if (foundIt.begin() == foundIt.end())
+        return false;
 
-    return false;
+    const auto& nextChunk = *foundIt.begin();
+    chunk->setMin(nextChunk->getMin());
+    chunk->setMax(nextChunk->getMax());
+    return true;
 }
 
 bool CollectionMetadata::getDifferentChunk(const BSONObj& chunkMinKey,
                                            ChunkType* differentChunk) const {
-    RangeMap::const_iterator upperChunkIt = _chunksMap.end();
-    RangeMap::const_iterator lowerChunkIt = _chunksMap.begin();
-
-    while (lowerChunkIt != upperChunkIt) {
-        if (lowerChunkIt->first.woCompare(chunkMinKey) != 0) {
-            differentChunk->setMin(lowerChunkIt->first);
-            differentChunk->setMax(lowerChunkIt->second);
-            return true;
+    for (const auto& found : _cm->chunks()) {
+        if (found->getShardId() == _thisShardId) {
+            if (found->getMin().woCompare(chunkMinKey) != 0) {
+                differentChunk->setMin(found->getMin());
+                differentChunk->setMax(found->getMax());
+                return true;
+            }
         }
-        ++lowerChunkIt;
     }
-
     return false;
 }
 
-Status CollectionMetadata::checkChunkIsValid(const ChunkType& chunk) {
+Status CollectionMetadata::checkChunkIsValid(const ChunkType& chunk) const {
     ChunkType existingChunk;
 
     if (!getNextChunk(chunk.getMin(), &existingChunk)) {
@@ -181,10 +111,6 @@ Status CollectionMetadata::checkChunkIsValid(const ChunkType& chunk) {
     return Status::OK();
 }
 
-bool CollectionMetadata::rangeOverlapsChunk(ChunkRange const& range) {
-    return rangeMapOverlaps(_rangesMap, range.getMin(), range.getMax());
-}
-
 void CollectionMetadata::toBSONBasic(BSONObjBuilder& bb) const {
     _cm->getVersion().addToBSON(bb, "collVersion");
     _shardVersion.addToBSON(bb, "shardVersion");
@@ -192,14 +118,13 @@ void CollectionMetadata::toBSONBasic(BSONObjBuilder& bb) const {
 }
 
 void CollectionMetadata::toBSONChunks(BSONArrayBuilder& bb) const {
-    if (_chunksMap.empty())
-        return;
-
-    for (RangeMap::const_iterator it = _chunksMap.begin(); it != _chunksMap.end(); ++it) {
-        BSONArrayBuilder chunkBB(bb.subarrayStart());
-        chunkBB.append(it->first);
-        chunkBB.append(it->second);
-        chunkBB.done();
+    for (const auto& chunk : _cm->chunks()) {
+        if (chunk->getShardId() == _thisShardId) {
+            BSONArrayBuilder chunkBB(bb.subarrayStart());
+            chunkBB.append(chunk->getMin());
+            chunkBB.append(chunk->getMax());
+            chunkBB.done();
+        }
     }
 }
 
diff --git a/src/mongo/db/s/collection_metadata.h b/src/mongo/db/s/collection_metadata.h
index e606058eae5..1f2135d2674 100644
--- a/src/mongo/db/s/collection_metadata.h
+++ b/src/mongo/db/s/collection_metadata.h
@@ -54,7 +54,6 @@ public:
      * "does this key belong to this shard"?
      */
     CollectionMetadata(std::shared_ptr<ChunkManager> cm, const ShardId& thisShardId);
-    ~CollectionMetadata();
 
     /**
      * Returns true if 'key' contains exactly the same fields as the shard key pattern.
@@ -67,7 +66,9 @@ public:
      * Returns true if the document with the given key belongs to this chunkset. If the key is empty
      * returns false. If key is not a valid shard key, the behaviour is undefined.
      */
-    bool keyBelongsToMe(const BSONObj& key) const;
+    bool keyBelongsToMe(const BSONObj& key) const {
+        return _cm->keyBelongsToShard(key, _thisShardId);
+    }
 
     /**
      * Given a key 'lookupKey' in the shard key range, get the next chunk which overlaps or is
@@ -85,12 +86,14 @@ public:
     /**
      * Validates that the passed-in chunk's bounds exactly match a chunk in the metadata cache.
      */
-    Status checkChunkIsValid(const ChunkType& chunk);
+    Status checkChunkIsValid(const ChunkType& chunk) const;
 
     /**
      * Returns true if the argument range overlaps any chunk.
      */
-    bool rangeOverlapsChunk(ChunkRange const& range);
+    bool rangeOverlapsChunk(ChunkRange const& range) const {
+        return _cm->rangeOverlapsShard(range, _thisShardId);
+    }
 
     /**
      * Given a key in the shard key range, get the next range which overlaps or is greater than
@@ -169,11 +172,6 @@ public:
     }
 
 private:
-    /**
-     * Builds _rangesMap from the contents of _chunksMap.
-     */
-    void _buildRangesMap();
-
     // The full routing table for the collection.
     std::shared_ptr<ChunkManager> _cm;
 
@@ -185,11 +183,6 @@ private:
 
     // Map of chunks tracked by this shard
     RangeMap _chunksMap;
-
-    // A second map from a min key into a range of contiguous chunks. This map is redundant with
-    // respect to the contents of _chunkMap but we expect high chunk contiguity, especially in small
-    // clusters.
-    RangeMap _rangesMap;
 };
 
 }  // namespace mongo
diff --git a/src/mongo/s/chunk_manager.cpp b/src/mongo/s/chunk_manager.cpp
index 964be3ed1b9..fdcb35984b5 100644
--- a/src/mongo/s/chunk_manager.cpp
+++ b/src/mongo/s/chunk_manager.cpp
@@ -32,8 +32,6 @@
 
 #include "mongo/s/chunk_manager.h"
 
-#include <vector>
-
 #include "mongo/base/owned_pointer_vector.h"
 #include "mongo/bson/simple_bsonobj_comparator.h"
 #include "mongo/db/matcher/extensions_callback_noop.h"
@@ -41,6 +39,7 @@
 #include "mongo/db/query/index_bounds_builder.h"
 #include "mongo/db/query/query_planner.h"
 #include "mongo/db/query/query_planner_common.h"
+#include "mongo/db/storage/key_string.h"
 #include "mongo/util/log.h"
 
 namespace mongo {
@@ -57,6 +56,16 @@ void checkAllElementsAreOfType(BSONType type, const BSONObj& o) {
     }
 }
 
+std::string extractKeyStringInternal(const BSONObj& shardKeyValue, Ordering ordering) {
+    BSONObjBuilder strippedKeyValue;
+    for (const auto& elem : shardKeyValue) {
+        strippedKeyValue.appendAs(elem, ""_sd);
+    }
+
+    KeyString ks(KeyString::Version::V1, strippedKeyValue.done(), ordering);
+    return {ks.getBuffer(), ks.getSize()};
+}
+
 }  // namespace
 
 ChunkManager::ChunkManager(NamespaceString nss,
@@ -70,10 +79,12 @@ ChunkManager::ChunkManager(NamespaceString nss,
       _nss(std::move(nss)),
       _uuid(uuid),
       _shardKeyPattern(shardKeyPattern),
+      _shardKeyOrdering(Ordering::make(_shardKeyPattern.toBSON())),
       _defaultCollator(std::move(defaultCollator)),
       _unique(unique),
       _chunkMap(std::move(chunkMap)),
-      _chunkMapViews(_constructChunkMapViews(collectionVersion.epoch(), _chunkMap)),
+      _chunkMapViews(
+          _constructChunkMapViews(collectionVersion.epoch(), _chunkMap, _shardKeyOrdering)),
       _collectionVersion(collectionVersion) {}
 
 std::shared_ptr<Chunk> ChunkManager::findIntersectingChunk(const BSONObj& shardKey,
@@ -89,7 +100,7 @@ std::shared_ptr<Chunk> ChunkManager::findIntersectingChunk(const BSONObj& shardK
         }
     }
 
-    const auto it = _chunkMap.upper_bound(shardKey);
+    const auto it = _chunkMap.upper_bound(_extractKeyString(shardKey));
     uassert(ErrorCodes::ShardKeyNotFound,
             str::stream() << "Cannot target single shard using key " << shardKey,
             it != _chunkMap.end() && it->second->containsKey(shardKey));
@@ -102,6 +113,17 @@ std::shared_ptr<Chunk> ChunkManager::findIntersectingChunkWithSimpleCollation(
     return findIntersectingChunk(shardKey, CollationSpec::kSimpleSpec);
 }
 
+bool ChunkManager::keyBelongsToShard(const BSONObj& shardKey, const ShardId& shardId) const {
+    if (shardKey.isEmpty())
+        return false;
+
+    const auto it = _rangeMapUpperBound(shardKey);
+    if (it == _chunkMapViews.chunkRangeMap.end())
+        return false;
+
+    return it->shardId == shardId;
+}
+
 void ChunkManager::getShardIdsForQuery(OperationContext* opCtx,
                                        const BSONObj& query,
                                        const BSONObj& collation,
@@ -163,26 +185,16 @@ void ChunkManager::getShardIdsForQuery(OperationContext* opCtx,
     // For now, we satisfy that assumption by adding a shard with no matches rather than returning
     // an empty set of shards.
     if (shardIds->empty()) {
-        shardIds->insert(_chunkMapViews.chunkRangeMap.begin()->second.shardId);
+        shardIds->insert(_chunkMapViews.chunkRangeMap.begin()->shardId);
     }
 }
 
 void ChunkManager::getShardIdsForRange(const BSONObj& min,
                                        const BSONObj& max,
                                        std::set<ShardId>* shardIds) const {
-    auto it = _chunkMapViews.chunkRangeMap.upper_bound(min);
-    auto end = _chunkMapViews.chunkRangeMap.upper_bound(max);
-
-    // The chunk range map must always cover the entire key space
-    invariant(it != _chunkMapViews.chunkRangeMap.end());
-
-    // We need to include the last chunk
-    if (end != _chunkMapViews.chunkRangeMap.end()) {
-        ++end;
-    }
-
-    for (; it != end; ++it) {
-        shardIds->insert(it->second.shardId);
+    const auto bounds = _overlappingRanges(min, max, true);
+    for (auto it = bounds.first; it != bounds.second; ++it) {
+        shardIds->insert(it->shardId);
 
         // No need to iterate through the rest of the ranges, because we already know we need to use
         // all shards.
@@ -192,6 +204,29 @@ void ChunkManager::getShardIdsForRange(const BSONObj& min,
     }
 }
 
+bool ChunkManager::rangeOverlapsShard(const ChunkRange& range, const ShardId& shardId) const {
+    const auto bounds = _overlappingRanges(range.getMin(), range.getMax(), false);
+    const auto it = std::find_if(bounds.first, bounds.second, [&shardId](const auto& scr) {
+        return scr.shardId == shardId;
+    });
+    return it != bounds.second;
+}
+
+ChunkManager::ConstRangeOfChunks ChunkManager::getNextChunkOnShard(const BSONObj& shardKey,
+                                                                   const ShardId& shardId) const {
+    for (auto it = _chunkMap.upper_bound(_extractKeyString(shardKey)); it != _chunkMap.end();
+         ++it) {
+        const auto& chunk = it->second;
+        if (chunk->getShardId() == shardId) {
+            const auto begin = it;
+            const auto end = ++it;
+            return {ConstChunkIterator(begin), ConstChunkIterator(end)};
+        }
+    }
+
+    return {ConstChunkIterator(), ConstChunkIterator()};
+}
+
 void ChunkManager::getAllShardIds(std::set<ShardId>* all) const {
     std::transform(_chunkMapViews.shardVersions.begin(),
                    _chunkMapViews.shardVersions.end(),
@@ -338,14 +373,13 @@ std::string ChunkManager::toString() const {
     sb << "ChunkManager: " << _nss.ns() << " key: " << _shardKeyPattern.toString() << '\n';
 
     sb << "Chunks:\n";
-    for (const auto& entry : _chunkMap) {
-        sb << "\t" << entry.first << ": " << entry.second->toString() << '\n';
+    for (const auto& chunk : chunks()) {
+        sb << "\t" << chunk->toString() << '\n';
     }
 
     sb << "Ranges:\n";
     for (const auto& entry : _chunkMapViews.chunkRangeMap) {
-        sb << "\t" << entry.first << ": " << entry.second.range.toString() << " @ "
-           << entry.second.shardId << '\n';
+        sb << "\t" << entry.range.toString() << " @ " << entry.shardId << '\n';
     }
 
     sb << "Shard versions:\n";
@@ -357,13 +391,10 @@ std::string ChunkManager::toString() const {
 }
 
 ChunkManager::ChunkMapViews ChunkManager::_constructChunkMapViews(const OID& epoch,
-                                                                  const ChunkMap& chunkMap) {
-
-    ChunkRangeMap chunkRangeMap =
-        SimpleBSONObjComparator::kInstance.makeBSONObjIndexedMap<ShardAndChunkRange>();
-
+                                                                  const ChunkMap& chunkMap,
+                                                                  Ordering shardKeyOrdering) {
+    ChunkRangeMap chunkRangeMap;
     ShardVersionMap shardVersions;
-
     ChunkMap::const_iterator current = chunkMap.cbegin();
 
     while (current != chunkMap.cend()) {
@@ -399,29 +430,31 @@ ChunkManager::ChunkMapViews ChunkManager::_constructChunkMapViews(const OID& epo
         const BSONObj rangeMin = firstChunkInRange->getMin();
         const BSONObj rangeMax = rangeLast->second->getMax();
 
-        const auto oldSize = chunkRangeMap.size();
-        const auto insertIterator = chunkRangeMap.insert(
-            chunkRangeMap.end(),
-            std::make_pair(
-                rangeMax,
-                ShardAndChunkRange{{rangeMin, rangeMax}, firstChunkInRange->getShardId()}));
-        uassert(ErrorCodes::ConflictingOperationInProgress,
-                str::stream() << "Metadata contains two chunks with the same max value "
-                              << rangeMax,
-                oldSize + 1 == chunkRangeMap.size());
-
-
-        if (insertIterator != chunkRangeMap.begin()) {
+        if (!chunkRangeMap.empty()) {
+            uassert(
+                ErrorCodes::ConflictingOperationInProgress,
+                str::stream()
+                    << "Metadata contains chunks with the same or out-of-order max value; "
+                       "expected "
+                    << chunkRangeMap.back().max()
+                    << " < "
+                    << rangeMax,
+                SimpleBSONObjComparator::kInstance.evaluate(chunkRangeMap.back().max() < rangeMax));
             // Make sure there are no gaps in the ranges
             uassert(ErrorCodes::ConflictingOperationInProgress,
                     str::stream() << "Gap or an overlap between ranges "
-                                  << insertIterator->second.range.toString()
+                                  << ChunkRange(rangeMin, rangeMax).toString()
                                   << " and "
-                                  << std::prev(insertIterator)->second.range.toString(),
-                    SimpleBSONObjComparator::kInstance.evaluate(std::prev(insertIterator)->first ==
+                                  << chunkRangeMap.back().range.toString(),
+                    SimpleBSONObjComparator::kInstance.evaluate(chunkRangeMap.back().max() ==
                                                                 rangeMin));
         }
 
+        chunkRangeMap.emplace_back(
+            ShardAndChunkRange{{rangeMin, rangeMax},
+                               firstChunkInRange->getShardId(),
+                               extractKeyStringInternal(rangeMax, shardKeyOrdering)});
+
         // If a shard has chunks it must have a shard version, otherwise we have an invalid chunk
         // somewhere, which should have been caught at chunk load time
         invariant(maxShardVersion.isSet());
@@ -431,13 +464,76 @@ ChunkManager::ChunkMapViews ChunkManager::_constructChunkMapViews(const OID& epo
         invariant(!chunkRangeMap.empty());
         invariant(!shardVersions.empty());
 
-        checkAllElementsAreOfType(MinKey, chunkRangeMap.begin()->second.min());
-        checkAllElementsAreOfType(MaxKey, chunkRangeMap.rbegin()->first);
+        checkAllElementsAreOfType(MinKey, chunkRangeMap.front().min());
+        checkAllElementsAreOfType(MaxKey, chunkRangeMap.back().max());
+
+        DEV for (size_t i = 0; i < chunkRangeMap.size() - 1; ++i) {
+            const auto& c1 = chunkRangeMap[i];
+            const auto& c2 = chunkRangeMap[i + 1];
+
+            invariant(SimpleBSONObjComparator::kInstance.evaluate(c1.max() == c2.min()),
+                      str::stream() << "Found gap between " << c1.range.toString() << " and "
+                                    << c2.range.toString());
+        }
     }
 
     return {std::move(chunkRangeMap), std::move(shardVersions)};
 }
 
+std::string ChunkManager::_extractKeyString(const BSONObj& shardKeyValue) const {
+    return extractKeyStringInternal(shardKeyValue, _shardKeyOrdering);
+}
+
+ChunkManager::ChunkRangeMap::const_iterator ChunkManager::_rangeMapUpperBound(
+    const BSONObj& key) const {
+
+    // This class is necessary, because the last argument to std::upper_bound is a functor which
+    // implements the BinaryPredicate concept. A binary predicate pred must be able to evaluate both
+    // pred(*iter1, *iter2) and pred(*iter1, value). The type of "value" in this case is
+    // std::string, while the type of *Iter is ShardAndChunkRange.
+    struct Key {
+        static const std::string& extract(const std::string& k) {
+            return k;
+        }
+        static void extract(std::string&& k) = delete;
+        static const std::string& extract(const ShardAndChunkRange& scr) {
+            return scr.ksMax;
+        }
+        static const std::string& extract(ShardAndChunkRange&&) = delete;
+    };
+
+    return std::upper_bound(_chunkMapViews.chunkRangeMap.cbegin(),
+                            _chunkMapViews.chunkRangeMap.cend(),
+                            _extractKeyString(key),
+                            [](const auto& lhs, const auto& rhs) -> bool {
+                                return Key::extract(lhs) < Key::extract(rhs);
+                            });
+}
+
+std::pair<ChunkManager::ChunkRangeMap::const_iterator, ChunkManager::ChunkRangeMap::const_iterator>
+ChunkManager::_overlappingRanges(const mongo::BSONObj& min,
+                                 const mongo::BSONObj& max,
+                                 bool isMaxInclusive) const {
+    dassert(SimpleBSONObjComparator::kInstance.evaluate(min <= max));
+    const auto begin = _rangeMapUpperBound(min);
+    auto end = _rangeMapUpperBound(max);
+
+    // The chunk range map must always cover the entire key space
+    invariant(begin != _chunkMapViews.chunkRangeMap.cend());
+
+    // Bump the end chunk, because the second iterator in the returned pair is exclusive. There is
+    // one caveat - if the exclusive max boundary of the range looked up is the same as the
+    // inclusive min of the end chunk returned, it is still possible that the min is not in the end
+    // chunk, in which case bumping the end will result in one extra chunk claimed to cover the
+    // range.
+    if (end != _chunkMapViews.chunkRangeMap.cend() &&
+        (isMaxInclusive || SimpleBSONObjComparator::kInstance.evaluate(max > end->min()))) {
+        ++end;
+    }
+
+    return {begin, end};
+}
+
 std::shared_ptr<ChunkManager> ChunkManager::makeNew(
     NamespaceString nss,
     boost::optional<UUID> uuid,
@@ -446,20 +542,19 @@ std::shared_ptr<ChunkManager> ChunkManager::makeNew(
     bool unique,
     OID epoch,
     const std::vector<ChunkType>& chunks) {
-
-    return ChunkManager(
-               std::move(nss),
-               uuid,
-               std::move(shardKeyPattern),
-               std::move(defaultCollator),
-               std::move(unique),
-               SimpleBSONObjComparator::kInstance.makeBSONObjIndexedMap<std::shared_ptr<Chunk>>(),
-               {0, 0, epoch})
+    return ChunkManager(std::move(nss),
+                        std::move(uuid),
+                        std::move(shardKeyPattern),
+                        std::move(defaultCollator),
+                        std::move(unique),
+                        {},
+                        {0, 0, epoch})
         .makeUpdated(chunks);
 }
 
 std::shared_ptr<ChunkManager> ChunkManager::makeUpdated(
     const std::vector<ChunkType>& changedChunks) {
+
     const auto startingCollectionVersion = getVersion();
     auto chunkMap = _chunkMap;
 
@@ -477,19 +572,22 @@ std::shared_ptr<ChunkManager> ChunkManager::makeUpdated(
         invariant(chunkVersion >= collectionVersion);
         collectionVersion = chunkVersion;
 
+        const auto chunkMinKeyString = _extractKeyString(chunk.getMin());
+        const auto chunkMaxKeyString = _extractKeyString(chunk.getMax());
+
         // Returns the first chunk with a max key that is > min - implies that the chunk overlaps
         // min
-        const auto low = chunkMap.upper_bound(chunk.getMin());
+        const auto low = chunkMap.upper_bound(chunkMinKeyString);
 
         // Returns the first chunk with a max key that is > max - implies that the next chunk cannot
         // not overlap max
-        const auto high = chunkMap.upper_bound(chunk.getMax());
+        const auto high = chunkMap.upper_bound(chunkMaxKeyString);
 
         // Erase all chunks from the map, which overlap the chunk we got from the persistent store
         chunkMap.erase(low, high);
 
         // Insert only the chunk itself
-        chunkMap.insert(std::make_pair(chunk.getMax(), std::make_shared<Chunk>(chunk)));
+        chunkMap.insert(std::make_pair(chunkMaxKeyString, std::make_shared<Chunk>(chunk)));
     }
 
     // If at least one diff was applied, the metadata is correct, but it might not have changed so
@@ -512,4 +610,5 @@ std::shared_ptr<ChunkManager> ChunkManager::makeUpdated(
                          std::move(chunkMap),
                          collectionVersion));
 }
+
 }  // namespace mongo
diff --git a/src/mongo/s/chunk_manager.h b/src/mongo/s/chunk_manager.h
index 51bc9df1e5c..ed7a34d5468 100644
--- a/src/mongo/s/chunk_manager.h
+++ b/src/mongo/s/chunk_manager.h
@@ -31,6 +31,7 @@
 #include <map>
 #include <set>
 #include <string>
+#include <vector>
 
 #include "mongo/base/disallow_copying.h"
 #include "mongo/db/namespace_string.h"
@@ -48,7 +49,7 @@ struct QuerySolutionNode;
 class OperationContext;
 
 // Ordered map from the max for each chunk to an entry describing the chunk
-using ChunkMap = BSONObjIndexedMap<std::shared_ptr<Chunk>>;
+using ChunkMap = std::map<std::string, std::shared_ptr<Chunk>>;
 
 // Map from a shard is to the max chunk version on that shard
 using ShardVersionMap = std::map<ShardId, ChunkVersion>;
@@ -169,6 +170,25 @@ public:
     }
 
     /**
+     * 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
+     * valid shard key, the behaviour is undefined.
+     */
+    bool keyBelongsToShard(const BSONObj& shardKey, const ShardId& shardId) const;
+
+    /**
+     * Returns true if any chunk owned by the shard with the given "shardId" overlaps "range".
+     */
+    bool rangeOverlapsShard(const ChunkRange& range, const ShardId& shardId) const;
+
+    /**
+     * Given a shardKey, returns the first chunk which is owned by shardId and overlaps or sorts
+     * after that shardKey. The returned iterator range always contains one or zero entries. If zero
+     * entries are returned, this means no such chunk exists.
+     */
+    ConstRangeOfChunks getNextChunkOnShard(const BSONObj& shardKey, const ShardId& shardId) const;
+
+    /**
      * Given a shard key (or a prefix) that has been extracted from a document, returns the chunk
      * that contains that key.
      *
@@ -256,9 +276,10 @@ private:
 
         ChunkRange range;
         ShardId shardId;
+        std::string ksMax;
     };
 
-    using ChunkRangeMap = BSONObjIndexedMap<ShardAndChunkRange>;
+    using ChunkRangeMap = std::vector<ShardAndChunkRange>;
 
     /**
      * Contains different transformations of the chunk map for efficient querying
@@ -277,16 +298,25 @@ private:
     /**
      * Does a single pass over the chunkMap and constructs the ChunkMapViews object.
      */
-    static ChunkMapViews _constructChunkMapViews(const OID& epoch, const ChunkMap& chunkMap);
+    static ChunkMapViews _constructChunkMapViews(const OID& epoch,
+                                                 const ChunkMap& chunkMap,
+                                                 Ordering shardKeyOrdering);
 
     ChunkManager(NamespaceString nss,
-                 boost::optional<UUID>,
+                 boost::optional<UUID> uuid,
                  KeyPattern shardKeyPattern,
                  std::unique_ptr<CollatorInterface> defaultCollator,
                  bool unique,
                  ChunkMap chunkMap,
                  ChunkVersion collectionVersion);
 
+    std::string _extractKeyString(const BSONObj& shardKeyValue) const;
+
+    ChunkRangeMap::const_iterator _rangeMapUpperBound(const BSONObj& key) const;
+
+    std::pair<ChunkRangeMap::const_iterator, ChunkRangeMap::const_iterator> _overlappingRanges(
+        const BSONObj& min, const BSONObj& max, bool isMaxInclusive) const;
+
     // The shard versioning mechanism hinges on keeping track of the number of times we reload
     // ChunkManagers.
     const unsigned long long _sequenceNumber;
@@ -300,6 +330,8 @@ private:
     // The key pattern used to shard the collection
     const ShardKeyPattern _shardKeyPattern;
 
+    const Ordering _shardKeyOrdering;
+
     // Default collation to use for routing data queries for this collection
     const std::unique_ptr<CollatorInterface> _defaultCollator;