check_keyspace.js

/* Check for gaps or duplicates in keyspace */

function check_keyspace(ns) { 
    print("Checking: " + ns);
    str = JSON.stringify
    forwardCount=0;
    reverseCount=0;
    min = db.chunks.find(ns).pretty().sort({min: 1}).limit(1)[0]
    max = db.chunks.find(ns).pretty().sort({min:-1}).limit(1)[0]
    current = min

    //walk forwards
    while(++forwardCount && current  && str(current) != str(max)){
        current = db.chunks.find({ns:ns, min:current.max })[0];
    }

    //walk backwards
    while(++reverseCount && current && str(current) != str(min)){
        current = db.chunks.find({ns:ns, max:current.min})[0];
    }

    //compare forward & backward walk 
    assert.eq(forwardCount, reverseCount,             "Chunk mismatch: " + ns);
    assert.eq(forwardCount, db.chunks.count({ns:ns}), "Chunk mismatch: " + ns);
    print("Valid: " + ns)
}

db.chunks.distinct("ns").forEach(function(ns){ check_keyspace(ns)});

Hi Achille. I had case with a chunks table of 160,000+. In that situation the reverse walk took forever, because a full table scan is needed every iteration due the lack of an index on {ns: 1, max: 1}.

I made a faster alternative, but it's quite a different algorithm. This one merges the chunk ranges - if the chunk boundaries are right you're left with just one - Min key to max key in the ascending list and vice versa in the descending list. Other than that shows a problem.

function confirmChunkRangeContinuity(ns) {
  var debugCtr = 0;
  var pq = {}; //Map of min vals to max vals
  var qp = {}; //Map of max vals to min vals
  db.chunks.find({"ns": ns}).sort({"ns": 1, "min": 1}).forEach(function(d) {
    minStr = tojsononeline(d.min, '');
    maxStr = tojsononeline(d.max, '');
    debugCtr++;
    //if (debugCtr % 5000 == 0) { print("iteration " + debugCtr); }
    if (minStr in qp) { //merge this range with another 'below'
      pq[qp[minStr]] = maxStr;
      qp[maxStr] = qp[minStr];
      delete qp[minStr];
      no_merge = false;
    } else {
      pq[minStr] = maxStr;
      qp[maxStr] = minStr;
    }
  });

  print("Contiguous ranges. Should only be one either way. I.e. One with { MinKeyValue: MaxKeyValue} and one with { MaxKeyValue: MinKeyValue }");
  print("Ascending direction:");
  printjson(pq);
  print("Descending direction:");
  printjson(qp);
}