Aren't UUIDs the a priori collision-free index of choice ?
The problem is which version? Also does the cluster index need to be embedded? Or shard index? Or whatever you are using to track the storage of the record? Should we care?
a nice way to solve this is a hash ring and put it in the ID. you can re-shard the ring as you need to, and can route to where the object lives easily.