Improved random destination cache.