SERVER-9365 make forced halfway split work with chunks with many docs

Additional test fixes.

6 files changed, 147 insertions, 10 deletions

diff --git a/jstests/sharding/count1.js b/jstests/sharding/count1.js
index 1b338883c31..8d36cd5f6f5 100644
--- a/jstests/sharding/count1.js
+++ b/jstests/sharding/count1.js
@@ -54,7 +54,9 @@ assert.eq( 6 , db.foo.find().count() , "basic count" );
 // part 2
 s.adminCommand( { split : "test.foo" , find : { name : "joe" } } ); // [Minkey -> allan) , * [allan -> ..)
 s.adminCommand( { split : "test.foo" , find : { name : "joe" } } ); // * [allan -> sara) , [sara -> Maxkey)
-s.adminCommand( { split : "test.foo" , find : { name : "joe" } } ); // [alan -> joe) , [joe -> sara]
+s.adminCommand( { split : "test.foo" , find : { name : "joe" } } ); // [alan -> eliot) , [eliot -> sara]
+
+// MINKEY->allan,bob->eliot,joe,mark->sara,MAXKEY
 
 s.printChunks()
 
@@ -63,7 +65,7 @@ assert.eq( 6 , db.foo.find().count() , "basic count after split " );
 assert.eq( 6 , db.foo.find().sort( { name : 1 } ).count() , "basic count after split sorted " );
 
 // part 4
-s.adminCommand( { movechunk : "test.foo" , find : { name : "allan" } , to : secondary.getMongo().name , _waitForDelete : true } );
+s.adminCommand( { movechunk : "test.foo" , find : { name : "eliot" } , to : secondary.getMongo().name , _waitForDelete : true } );
 
 assert.eq( 3 , primary.foo.find().toArray().length , "primary count" );
 assert.eq( 3 , secondary.foo.find().toArray().length , "secondary count" );
diff --git a/jstests/sharding/key_many.js b/jstests/sharding/key_many.js
index 75a9784096f..2246f01b504 100644
--- a/jstests/sharding/key_many.js
+++ b/jstests/sharding/key_many.js
@@ -98,7 +98,7 @@ for ( var i=0; i<types.length; i++ ){
     s.adminCommand( { split : longName , find : makeObjectDotted( curT.values[3] ) } );
     s.adminCommand( { split : longName , find : makeObjectDotted( curT.values[3] ) } );
 
-    s.adminCommand( { movechunk : longName , find : makeObjectDotted( curT.values[0] ) , to : secondary.getMongo().name, _waitForDelete : true } );
+    s.adminCommand( { movechunk : longName , find : makeObjectDotted( curT.values[2] ) , to : secondary.getMongo().name, _waitForDelete : true } );
     
     s.printChunks();
     
diff --git a/jstests/sharding/key_string.js b/jstests/sharding/key_string.js
index 990b0456665..f2c0ca209b3 100644
--- a/jstests/sharding/key_string.js
+++ b/jstests/sharding/key_string.js
@@ -24,7 +24,7 @@ s.adminCommand( { split : "test.foo" , find : { name : "joe" } } ); // [Minkey -
 s.adminCommand( { split : "test.foo" , find : { name : "joe" } } ); // * [allan -> sara) , [sara -> Maxkey)
 s.adminCommand( { split : "test.foo" , find : { name : "joe" } } ); // [alan -> joe) , [joe -> sara]
 
-s.adminCommand( { movechunk : "test.foo" , find : { name : "allan" } , to : seconday.getMongo().name, _waitForDelete : true, _waitForDelete : true } );
+s.adminCommand( { movechunk : "test.foo" , find : { name : "eliot" } , to : seconday.getMongo().name, _waitForDelete : true, _waitForDelete : true } );
 
 s.printChunks();
 
@@ -42,7 +42,7 @@ assert.eq( "sara,mark,joe,eliot,bob,allan" ,  db.foo.find().sort( { name : -1 }
 // make sure we can't foce a split on an extreme key
 // [allan->joe) 
 assert.throws( function(){ s.adminCommand( { split : "test.foo" , middle : { name : "allan" } } ) } );
-assert.throws( function(){ s.adminCommand( { split : "test.foo" , middle : { name : "joe" } } ) } );
+assert.throws( function(){ s.adminCommand( { split : "test.foo" , middle : { name : "eliot" } } ) } );
 
 s.stop();
 
diff --git a/jstests/sharding/split_with_force.js b/jstests/sharding/split_with_force.js
new file mode 100644
index 00000000000..9033abc2402
--- /dev/null
+++ b/jstests/sharding/split_with_force.js
@@ -0,0 +1,60 @@
+//
+// Tests autosplit locations with force : true
+//
+
+var options = { separateConfig : true, 
+                chunksize : 1, // MB
+                mongosOptions : { noAutoSplit : "" }
+              };
+
+var st = new ShardingTest({ shards : 1, mongos : 1, other : options });
+st.stopBalancer();
+
+var mongos = st.s0;
+var admin = mongos.getDB( "admin" );
+var config = mongos.getDB( "config" );
+var shardAdmin = st.shard0.getDB( "admin" );
+var coll = mongos.getCollection( "foo.bar" );
+
+assert( admin.runCommand({ enableSharding : coll.getDB() + "" }).ok );
+assert( admin.runCommand({ shardCollection : coll + "", key : { _id : 1 } }).ok );
+assert( admin.runCommand({ split : coll + "", middle : { _id : 0 } }).ok );
+
+jsTest.log( "Insert a bunch of data into a chunk of the collection..." );
+
+for ( var i = 0; i < (250 * 1000) + 10; i++ ) {
+    coll.insert({ _id : i });
+}
+assert.eq( null, coll.getDB().getLastError() );
+
+jsTest.log( "Insert a bunch of data into the rest of the collection..." );
+
+for ( var i = 1; i <= (250 * 1000); i++ ) {
+    coll.insert({ _id : -i });
+}
+assert.eq( null, coll.getDB().getLastError() );
+
+jsTest.log( "Get split points of the chunk using force : true..." );
+
+var maxChunkSizeBytes = 1024 * 1024;
+
+var splitKeys = shardAdmin.runCommand({ splitVector : coll + "",
+                                        keyPattern : { _id : 1 },
+                                        min : { _id : 0 },
+                                        max : { _id : MaxKey },
+                                        force : true
+                                      }).splitKeys;
+
+printjson( splitKeys );
+printjson( coll.stats() );
+st.printShardingStatus();
+
+jsTest.log( "Make sure our split is approximately in half..." );
+
+assert.eq( splitKeys.length, 1 );
+var splitKey = splitKeys[0]._id;
+
+assert.gt( splitKey, ((250 * 1000) / 2) - 50 );
+assert.lt( splitKey, ((250 * 1000) / 2) + 50 );
+
+st.stop();
diff --git a/jstests/sharding/split_with_force_small.js b/jstests/sharding/split_with_force_small.js
new file mode 100644
index 00000000000..02abfe6230e
--- /dev/null
+++ b/jstests/sharding/split_with_force_small.js
@@ -0,0 +1,68 @@
+//
+// Tests autosplit locations with force : true, for small collections
+//
+
+var options = { separateConfig : true, 
+                chunksize : 1, // MB
+                mongosOptions : { noAutoSplit : "" }
+              };
+
+var st = new ShardingTest({ shards : 1, mongos : 1, other : options });
+st.stopBalancer();
+
+var mongos = st.s0;
+var admin = mongos.getDB( "admin" );
+var config = mongos.getDB( "config" );
+var shardAdmin = st.shard0.getDB( "admin" );
+var coll = mongos.getCollection( "foo.bar" );
+
+assert( admin.runCommand({ enableSharding : coll.getDB() + "" }).ok );
+assert( admin.runCommand({ shardCollection : coll + "", key : { _id : 1 } }).ok );
+assert( admin.runCommand({ split : coll + "", middle : { _id : 0 } }).ok );
+
+jsTest.log( "Insert a bunch of data into the low chunk of a collection," +
+            " to prevent relying on stats." );
+
+var data128k = "x";
+for ( var i = 0; i < 7; i++ ) data128k += data128k;
+
+for ( var i = 0; i < 1024; i++ ) {
+    coll.insert({ _id : -(i + 1) });
+}
+assert.eq( null, coll.getDB().getLastError() );
+
+jsTest.log( "Insert 32 docs into the high chunk of a collection" );
+
+for ( var i = 0; i < 32; i++ ) {
+    coll.insert({ _id : i });
+}
+assert.eq( null, coll.getDB().getLastError() );
+
+jsTest.log( "Split off MaxKey chunk..." );
+
+assert( admin.runCommand({ split : coll + "", middle : { _id : 32 } }).ok );
+
+jsTest.log( "Keep splitting chunk multiple times..." );
+
+st.printShardingStatus();
+
+for ( var i = 0; i < 5; i++ ) {
+    assert( admin.runCommand({ split : coll + "", find : { _id : 0 } }).ok );
+    st.printShardingStatus();
+}
+
+// Make sure we can't split further than 5 (2^5) times
+assert( !admin.runCommand({ split : coll + "", find : { _id : 0 } }).ok );
+
+var chunks = config.chunks.find({ 'min._id' : { $gte : 0, $lt : 32 } }).sort({ min : 1 }).toArray();
+printjson( chunks );
+
+// Make sure the chunks grow by 2x (except the first)
+var nextSize = 1;
+for ( var i = 0; i < chunks.size; i++ ) {
+    assert.eq( coll.count({ _id : { $gte : chunks[i].min._id, $lt : chunks[i].max._id } }), 
+               nextSize );
+    if ( i != 0 ) nextSize += nextSize;
+}
+
+st.stop();
diff --git a/src/mongo/s/d_split.cpp b/src/mongo/s/d_split.cpp
index 332a6300014..d28f3f5d90b 100644
--- a/src/mongo/s/d_split.cpp
+++ b/src/mongo/s/d_split.cpp
@@ -290,13 +290,14 @@ namespace mongo {
                 // 'force'-ing a split is equivalent to having maxChunkSize be the size of the current chunk, i.e., the
                 // logic below will split that chunk in half
                 long long maxChunkSize = 0;
-                bool force = false;
+                bool forceMedianSplit = false;
                 {
                     BSONElement maxSizeElem = jsobj[ "maxChunkSize" ];
                     BSONElement forceElem = jsobj[ "force" ];
                     
                     if ( forceElem.trueValue() ) {
-                        force = true;
+                        forceMedianSplit = true;
+                        // This chunk size is effectively ignored if force is true
                         maxChunkSize = dataSize;
                         
                     }
@@ -366,7 +367,8 @@ namespace mongo {
                     while ( cc->ok() ) {
                         currCount++;
                         
-                        if ( currCount > keyCount ) {
+                        if ( currCount > keyCount && !forceMedianSplit ) {
+
                             BSONObj currKey = bc->prettyKey( c->currKey() ).extractFields(keyPattern);
                             // Do not use this split key if it is the same used in the previous split point.
                             if ( currKey.woCompare( splitKeys.back() ) == 0 ) {
@@ -404,10 +406,15 @@ namespace mongo {
                         }
                     }
                     
-                    if ( splitKeys.size() > 1 || ! force )
+                    if ( ! forceMedianSplit )
                         break;
                     
-                    force = false;
+                    //
+                    // If we're forcing a split at the halfway point, then the first pass was just
+                    // to count the keys, and we still need a second pass.
+                    //
+
+                    forceMedianSplit = false;
                     keyCount = currCount / 2;
                     currCount = 0;
                     log() << "splitVector doing another cycle because of force, keyCount now: " << keyCount << endl;