def guess_end_key(kind,
                    key_start,
                    probe_count=10,
                    split_rate=5):
    """Guess the end of a key range with a binary search of probe queries.

    When the 'key_start' parameter has a key hierarchy, this function will
    only determine the key range for keys in a similar hierarchy. That means
    if the keys are in the form:

      kind=Foo, name=bar/kind=Stuff, name=meep

    only this range will be probed:

      kind=Foo, name=*/kind=Stuff, name=*

    That means other entities of kind 'Stuff' that are children of another
    parent entity kind will be skipped:

      kind=Other, name=cookie/kind=Stuff, name=meep

    Args:
      key_start: The starting key of the search range. In most cases this
        should be id = 0 or name = '\0'.
      kind: String name of the entity kind.
      probe_count: Optional, how many probe queries to run.
      split_rate: Exponential rate to use for splitting the range on the
        way down from the full key space. For smaller ranges this should
        be higher so more of the keyspace is skipped on initial descent.

    Returns:
      datastore.Key that is guaranteed to be as high or higher than the
      highest key existing for this Kind. Doing a query between 'key_start' and
      this returned Key (inclusive) will contain all entities of this Kind.
    """
    app = key_start.app()
    full_path = key_start.to_path()
    for index, piece in enumerate(full_path):
      if index % 2 == 0:
        continue
      elif isinstance(piece, basestring):
        full_path[index] = u"\xffff"
      else:
        full_path[index] = 2**32

    key_end = datastore.Key.from_path(*full_path, **{"_app": app})
    split_key = key_end

    for i in xrange(probe_count):
      for j in xrange(split_rate):
        split_key = KeyRange.split_keys(key_start, split_key, 1)
      results = datastore.Query(
          kind,
          {"__key__ >": split_key},
          _app=app,
          keys_only=True).Get(1)
      if results:
        split_rate = 1
        key_start = split_key
        split_key = key_end
      else:
        key_end = split_key

    return key_end
Guess the end of a key range with a binary search of probe queries.

    When the 'key_start' parameter has a key hierarchy, this function will
    only determine the key range for keys in a similar hierarchy. That means
    if the keys are in the form:

      kind=Foo, name=bar/kind=Stuff, name=meep

    only this range will be probed:

      kind=Foo, name=*/kind=Stuff, name=*

    That means other entities of kind 'Stuff' that are children of another
    parent entity kind will be skipped:

      kind=Other, name=cookie/kind=Stuff, name=meep

    Args:
      key_start: The starting key of the search range. In most cases this
        should be id = 0 or name = ''.
      kind: String name of the entity kind.
      probe_count: Optional, how many probe queries to run.
      split_rate: Exponential rate to use for splitting the range on the
        way down from the full key space. For smaller ranges this should
        be higher so more of the keyspace is skipped on initial descent.

    Returns:
      datastore.Key that is guaranteed to be as high or higher than the
      highest key existing for this Kind. Doing a query between 'key_start' and
      this returned Key (inclusive) will contain all entities of this Kind.
    
mapreduce/lib/key_range/__init__.py