By encoding the original URL in the key you can look up to see if a URL has been shortened already, and serve that.

Thanks for the info re scan I'll have a look and check my version of redis.