A canonical key id is the lowest integer key id that maps to
        a particular shard. The mapping to canonical key ids depends on the
        number of shards.

        Returns a dictionary mapping from shard number to canonical key id.

        This method will throw an exception if it fails to compute all of
        the canonical key ids.

def compute_canonical_key_ids(self, search_amplifier=100):
        """
        A canonical key id is the lowest integer key id that maps to
        a particular shard. The mapping to canonical key ids depends on the
        number of shards.

        Returns a dictionary mapping from shard number to canonical key id.

        This method will throw an exception if it fails to compute all of
        the canonical key ids.
        """
        canonical_keys = {}
        num_shards = self.num_shards()
        # Guarantees enough to find all keys without running forever
        num_iterations = (num_shards**2) * search_amplifier
        for key_id in range(1, num_iterations):
            shard_num = self.get_shard_num_by_key(str(key_id))
            if shard_num in canonical_keys:
                continue
            canonical_keys[shard_num] = str(key_id)
            if len(canonical_keys) == num_shards:
                break

        if len(canonical_keys) != num_shards:
            raise ValueError("Failed to compute enough keys. " +
                             "Wanted %d, got %d (search_amp=%d).".format(
                                 num_shards, len(canonical_keys),
                                 search_amplifier))

        return canonical_keys