A planned, forthcoming improvement to the above NOT_MY_VBUCKET handling approach is that membase will soon send an optional second map during the start of the Rebalance. This second map, called a "fast forward map", provides the final vbucket-to-server map that would represent the cluster at the end of the Rebalance. A client library can use the optional fast forward map during NOT_MY_VBUCKET errors to avoid linear probing of all servers and can instead just jump straight to talking with the eventual vbucket owner.

Please see the implementation in libvbucket that handles a fast-forward-map here.

The linear probing, however, should be retained by client library implementations as a good fallback, just-in-case error handling codepath.