Separate functions for locating documents vs locating points in the shard-key space

9 files changed, 69 insertions, 61 deletions

diff --git a/src/mongo/s/balance.cpp b/src/mongo/s/balance.cpp
index 248b3e4d8d5..f91d059fb41 100644
--- a/src/mongo/s/balance.cpp
+++ b/src/mongo/s/balance.cpp
@@ -52,13 +52,13 @@ namespace mongo {
             ChunkManagerPtr cm = cfg->getChunkManager( chunkInfo.ns );
             verify( cm );
 
-            ChunkPtr c = cm->findChunk( chunkInfo.chunk.min );
+            ChunkPtr c = cm->findIntersectingChunk( chunkInfo.chunk.min );
             if ( c->getMin().woCompare( chunkInfo.chunk.min ) || c->getMax().woCompare( chunkInfo.chunk.max ) ) {
                 // likely a split happened somewhere
                 cm = cfg->getChunkManager( chunkInfo.ns , true /* reload */);
                 verify( cm );
 
-                c = cm->findChunk( chunkInfo.chunk.min );
+                c = cm->findIntersectingChunk( chunkInfo.chunk.min );
                 if ( c->getMin().woCompare( chunkInfo.chunk.min ) || c->getMax().woCompare( chunkInfo.chunk.max ) ) {
                     log() << "chunk mismatch after reload, ignoring will retry issue " << chunkInfo.chunk.toString() << endl;
                     continue;
@@ -79,7 +79,7 @@ namespace mongo {
                 // reload just to be safe
                 cm = cfg->getChunkManager( chunkInfo.ns );
                 verify( cm );
-                c = cm->findChunk( chunkInfo.chunk.min );
+                c = cm->findIntersectingChunk( chunkInfo.chunk.min );
                 
                 log() << "forcing a split because migrate failed for size reasons" << endl;
                 
diff --git a/src/mongo/s/chunk.cpp b/src/mongo/s/chunk.cpp
index 773978014dc..56ab992b423 100644
--- a/src/mongo/s/chunk.cpp
+++ b/src/mongo/s/chunk.cpp
@@ -90,17 +90,13 @@ namespace mongo {
         return _manager->getns();
     }
 
-    bool Chunk::contains( const BSONObj& obj ) const {
-        return
-            _manager->getShardKey().compare( getMin() , obj ) <= 0 &&
-            _manager->getShardKey().compare( obj , getMax() ) < 0;
+    bool Chunk::containsPoint( const BSONObj& point ) const {
+        return getMin().woCompare( point ) <= 0 && point.woCompare( getMax() ) < 0;
     }
 
-    bool ChunkRange::contains(const BSONObj& obj) const {
+    bool ChunkRange::containsPoint( const BSONObj& point ) const {
         // same as Chunk method
-        return
-            _manager->getShardKey().compare( getMin() , obj ) <= 0 &&
-            _manager->getShardKey().compare( obj , getMax() ) < 0;
+        return getMin().woCompare( point ) <= 0 && point.woCompare( getMax() ) < 0;
     }
 
     bool Chunk::minIsInf() const {
@@ -410,7 +406,7 @@ namespace mongo {
                 }
 
                 ChunkManagerPtr cm = _manager->reload(false/*just reloaded in mulitsplit*/);
-                ChunkPtr toMove = cm->findChunk(min);
+                ChunkPtr toMove = cm->findIntersectingChunk(min);
 
                 if ( ! (toMove->getMin() == min && toMove->getMax() == max) ){
                     LOG(1) << "recently split chunk: " << range << " modified before we could migrate " << toMove << endl;
@@ -472,10 +468,7 @@ namespace mongo {
     }
 
     bool Chunk::operator==( const Chunk& s ) const {
-        return
-            _manager->getShardKey().compare( _min , s._min ) == 0 &&
-            _manager->getShardKey().compare( _max , s._max ) == 0
-            ;
+        return _min.woCompare( s._min ) == 0 && _max.woCompare( s._max ) == 0;
     }
 
     void Chunk::serialize(BSONObjBuilder& to,ShardChunkVersion myLastMod) {
@@ -1028,14 +1021,12 @@ namespace mongo {
         _version = ShardChunkVersion( 0, version.epoch() );
     }
 
-    ChunkPtr ChunkManager::findChunk( const BSONObj & obj ) const {
-        BSONObj key = _key.extractKey(obj);
-
+    ChunkPtr ChunkManager::findIntersectingChunk( const BSONObj& point ) const {
         {
             BSONObj foo;
             ChunkPtr c;
             {
-                ChunkMap::const_iterator it = _chunkMap.upper_bound(key);
+                ChunkMap::const_iterator it = _chunkMap.upper_bound( point );
                 if (it != _chunkMap.end()) {
                     foo = it->first;
                     c = it->second;
@@ -1043,14 +1034,14 @@ namespace mongo {
             }
 
             if ( c ) {
-                if ( c->contains( key ) ){
-                    dassert(c->contains(key)); // doesn't use fast-path in extractKey
+                if ( c->containsPoint( point ) ){
+                    dassert( c->containsPoint( point ) ); // doesn't use fast-path in extractKey
                     return c;
                 }
 
                 PRINT(foo);
                 PRINT(*c);
-                PRINT(key);
+                PRINT( point );
 
                 reload();
                 massert(13141, "Chunk map pointed to incorrect chunk", false);
@@ -1058,7 +1049,12 @@ namespace mongo {
         }
 
         msgasserted( 8070 ,
-                     str::stream() << "couldn't find a chunk which should be impossible: " << key );
+                     str::stream() << "couldn't find a chunk which should be impossible: " << point );
+    }
+
+    ChunkPtr ChunkManager::findChunkForDoc( const BSONObj& doc ) const {
+        BSONObj key = _key.extractKey( doc );
+        return findIntersectingChunk( key );
     }
 
     ChunkPtr ChunkManager::findChunkOnServer( const Shard& shard ) const {
@@ -1165,11 +1161,11 @@ namespace mongo {
 
     bool ChunkManager::compatibleWith( const Chunk& other ) const {
 
-        // Do this first, b/c findChunk asserts if the key isn't similar
+        // Do this first, b/c findIntersectingChunk asserts if the key isn't similar
         if( ! this->_key.hasShardKey( other.getMin() ) ) return false;
         // We assume here that chunks will have consistent fields in min/max
 
-        ChunkPtr myChunk = this->findChunk( other.getMin() );
+        ChunkPtr myChunk = this->findIntersectingChunk( other.getMin() );
 
         if( other.getMin() != myChunk->getMin() ) return false;
         if( other.getMax() != myChunk->getMax() ) return false;
@@ -1320,8 +1316,8 @@ namespace mongo {
                 verify(max != _ranges.end());
                 verify(min == max);
                 verify(min->second->getShard() == chunk->getShard());
-                verify(min->second->contains( chunk->getMin() ));
-                verify(min->second->contains( chunk->getMax() ) || (min->second->getMax() == chunk->getMax()));
+                verify(min->second->containsPoint( chunk->getMin() ));
+                verify(min->second->containsPoint( chunk->getMax() ) || (min->second->getMax() == chunk->getMax()));
             }
 
         }
diff --git a/src/mongo/s/chunk.h b/src/mongo/s/chunk.h
index 5fd01c5abe4..56700deae04 100644
--- a/src/mongo/s/chunk.h
+++ b/src/mongo/s/chunk.h
@@ -77,7 +77,12 @@ namespace mongo {
         bool minIsInf() const;
         bool maxIsInf() const;
 
-        bool contains( const BSONObj& obj ) const;
+        // Returns true if this chunk contains the given point, and false otherwise
+        //
+        // Note: this function takes an extracted *key*, not an original document
+        // (the point may be computed by, say, hashing a given field or projecting
+        //  to a subset of fields).
+        bool containsPoint( const BSONObj& point ) const;
 
         string genID() const;
         static string genID( const string& ns , const BSONObj& min );
@@ -186,6 +191,8 @@ namespace mongo {
         string toString() const;
 
         friend ostream& operator << (ostream& out, const Chunk& c) { return (out << c.toString()); }
+
+        // chunk equality is determined by comparing the min and max bounds of the chunk
         bool operator==(const Chunk& s) const;
         bool operator!=(const Chunk& s) const { return ! ( *this == s ); }
 
@@ -235,7 +242,12 @@ namespace mongo {
         const BSONObj& getMax() const { return _max; }
 
         // clones of Chunk methods
-        bool contains(const BSONObj& obj) const;
+        // Returns true if this ChunkRange contains the given point, and false otherwise
+        //
+        // Note: this function takes an extracted *key*, not an original document
+        // (the point may be computed by, say, hashing a given field or projecting
+        //  to a subset of fields).
+        bool containsPoint( const BSONObj& point ) const;
 
         ChunkRange(ChunkMap::const_iterator begin, const ChunkMap::const_iterator end)
             : _manager(begin->second->getManager())
@@ -355,7 +367,25 @@ namespace mongo {
 
         int numChunks() const { return _chunkMap.size(); }
 
-        ChunkPtr findChunk( const BSONObj& obj ) const;
+        /** Given a document, returns the chunk which contains that document.
+         *  This works by extracting the shard key part of the given document, then
+         *  calling findIntersectingChunk() on the extracted key.
+         *
+         *  See also the description for findIntersectingChunk().
+         */
+        ChunkPtr findChunkForDoc( const BSONObj& doc ) const;
+
+        /** Given a key that has been extracted from a document, returns the
+         *  chunk that contains that key.
+         *
+         *  For instance, to locate the chunk for document {a : "foo" , b : "bar"}
+         *  when the shard key is {a : "hashed"}, you can call
+         *      findChunkForDoc() on {a : "foo" , b : "bar"}, or
+         *      findIntersectingChunk() on {a : hash("foo") }
+         */
+        ChunkPtr findIntersectingChunk( const BSONObj& point ) const;
+
+
         ChunkPtr findChunkOnServer( const Shard& shard ) const;
 
         void getShardsForQuery( set<Shard>& shards , const BSONObj& query ) const;
diff --git a/src/mongo/s/commands_admin.cpp b/src/mongo/s/commands_admin.cpp
index c155e25066d..0a03798aec7 100644
--- a/src/mongo/s/commands_admin.cpp
+++ b/src/mongo/s/commands_admin.cpp
@@ -740,7 +740,7 @@ namespace mongo {
                 }
 
                 ChunkManagerPtr info = config->getChunkManager( ns );
-                ChunkPtr chunk = info->findChunk( find );
+                ChunkPtr chunk = info->findChunkForDoc( find );
                 BSONObj middle = cmdObj.getObjectField( "middle" );
 
                 verify( chunk.get() );
@@ -835,7 +835,7 @@ namespace mongo {
                 tlog() << "CMD: movechunk: " << cmdObj << endl;
 
                 ChunkManagerPtr info = config->getChunkManager( ns );
-                ChunkPtr c = info->findChunk( find );
+                ChunkPtr c = info->findChunkForDoc( find );
                 const Shard& from = c->getShard();
 
                 if ( from == to ) {
diff --git a/src/mongo/s/commands_public.cpp b/src/mongo/s/commands_public.cpp
index b23eebd2915..082d4289d8e 100644
--- a/src/mongo/s/commands_public.cpp
+++ b/src/mongo/s/commands_public.cpp
@@ -706,7 +706,7 @@ namespace mongo {
                 BSONObj filter = cmdObj.getObjectField("query");
                 uassert(13343,  "query for sharded findAndModify must have shardkey", cm->hasShardKey(filter));
 
-                ChunkPtr chunk = cm->findChunk(filter);
+                ChunkPtr chunk = cm->findChunkForDoc(filter);
                 ShardConnection conn( chunk->getShard() , fullns );
                 BSONObj res;
                 bool ok = conn->runCommand( conf->getName() , cmdObj , res );
@@ -1140,7 +1140,7 @@ namespace mongo {
             ChunkPtr insertSharded( ChunkManagerPtr manager, const char* ns, BSONObj& o, int flags, bool safe ) {
                 // note here, the MR output process requires no splitting / migration during process, hence StaleConfigException should not happen
                 Strategy* s = SHARDED;
-                ChunkPtr c = manager->findChunk( o );
+                ChunkPtr c = manager->findChunkForDoc( o );
                 LOG(4) << "  server:" << c->getShard().toString() << " " << o << endl;
                 s->insert( c->getShard() , ns , o , flags, safe);
                 return c;
@@ -1451,7 +1451,7 @@ namespace mongo {
                         verify( size < 0x7fffffff );
 
                         // key reported should be the chunk's minimum
-                        ChunkPtr c =  cm->findChunk(key);
+                        ChunkPtr c =  cm->findIntersectingChunk(key);
                         if ( !c ) {
                             warning() << "Mongod reported " << size << " bytes inserted for key " << key << " but can't find chunk" << endl;
                         } else {
diff --git a/src/mongo/s/request.cpp b/src/mongo/s/request.cpp
index fdb1fe0e0f5..ef83277365e 100644
--- a/src/mongo/s/request.cpp
+++ b/src/mongo/s/request.cpp
@@ -103,7 +103,7 @@ namespace mongo {
         if ( _chunkManager ) {
             if ( _chunkManager->numChunks() > 1 )
                 throw UserException( 8060 , "can't call primaryShard on a sharded collection" );
-            return _chunkManager->findChunk( _chunkManager->getShardKey().globalMin() )->getShard();
+            return _chunkManager->findIntersectingChunk( _chunkManager->getShardKey().globalMin() )->getShard();
         }
         Shard s = _config->getShard( getns() );
         uassert( 10194 ,  "can't call primaryShard on a sharded collection!" , s.ok() );
diff --git a/src/mongo/s/shardkey.cpp b/src/mongo/s/shardkey.cpp
index 8b768c0e8dd..d7521c91510 100644
--- a/src/mongo/s/shardkey.cpp
+++ b/src/mongo/s/shardkey.cpp
@@ -42,16 +42,6 @@ namespace mongo {
         gMax = max.obj();
     }
 
-    int ShardKeyPattern::compare( const BSONObj& lObject , const BSONObj& rObject ) const {
-        BSONObj L = extractKey(lObject);
-        uassert( 10198 , str::stream() << "left object ("  << lObject << ") doesn't have full shard key (" << pattern << ')',
-                L.nFields() == (int)patternfields.size());
-        BSONObj R = extractKey(rObject);
-        uassert( 10199 , str::stream() << "right object (" << rObject << ") doesn't have full shard key (" << pattern << ')',
-                R.nFields() == (int)patternfields.size());
-        return L.woCompare(R);
-    }
-
     bool ShardKeyPattern::hasShardKey( const BSONObj& obj ) const {
         /* this is written s.t. if obj has lots of fields, if the shard key fields are early,
            it is fast.  so a bit more work to try to be semi-fast.
@@ -229,10 +219,9 @@ namespace mongo {
 
             BSONObj k1 = BSON( "key" << 5 );
 
-            verify( k.compare( min , max ) < 0 );
-            verify( k.compare( min , k1 ) < 0 );
-            verify( k.compare( max , min ) > 0 );
-            verify( k.compare( min , min ) == 0 );
+            verify( min < max );
+            verify( min < k.extractKey( k1 ) );
+            verify( max > min );
 
             hasshardkeytest();
             verify( k.hasShardKey( k1 ) );
@@ -241,7 +230,7 @@ namespace mongo {
             BSONObj a = k1;
             BSONObj b = BSON( "key" << 999 );
 
-            verify( k.compare(a,b) < 0 );
+            verify( k.extractKey( a ) <  k.extractKey( b ) );
 
             // add middle multitype tests
 
diff --git a/src/mongo/s/shardkey.h b/src/mongo/s/shardkey.h
index 02f6b5b18d3..133f53ad435 100644
--- a/src/mongo/s/shardkey.h
+++ b/src/mongo/s/shardkey.h
@@ -52,13 +52,6 @@ namespace mongo {
             return isGlobalMin( k ) || isGlobalMax( k );
         }
 
-        /** compare shard keys from the objects specified
-           l < r negative
-           l == r 0
-           l > r positive
-         */
-        int compare( const BSONObj& l , const BSONObj& r ) const;
-
         /**
            @return whether or not obj has all fields in this shard key pattern
            e.g.
diff --git a/src/mongo/s/strategy_shard.cpp b/src/mongo/s/strategy_shard.cpp
index e0acb4a0455..08f2147856e 100644
--- a/src/mongo/s/strategy_shard.cpp
+++ b/src/mongo/s/strategy_shard.cpp
@@ -397,7 +397,7 @@ namespace mongo {
                 // Many operations benefit from having the shard key early in the object
                 if( manager ){
                     o = manager->getShardKey().moveToFront(o);
-                    insertsForChunks[manager->findChunk(o)].push_back(o);
+                    insertsForChunks[manager->findChunkForDoc(o)].push_back(o);
                 }
                 else{
                     insertsForChunks[ empty ].push_back(o);
@@ -711,7 +711,7 @@ namespace mongo {
             verify( manager );
             if( ! shardKey.isEmpty() ){
 
-                chunk = manager->findChunk( shardKey );
+                chunk = manager->findIntersectingChunk( shardKey );
                 shard = ShardPtr( new Shard( chunk->getShard() ) );
                 return;
             }