Design a URL shortening service (like bit.ly)

You need to create a service that takes a long URL and converts it into a shorter one, which can be used to access the same page. The shortened URL should be unique and the service should be scalable to handle millions of requests.
What data structures will you use, what algorithms will you implement, and describe the database schema.
Explain how you will handle collision and how you will design for high availability.
---
Consider the security of the service and access control for shortened URLs.