system design

You’re building a URL shortener that needs to generate 10,000 unique, non-sequential, 6-character IDs per second. A simple counter is predictable and a random generator might have collisions at scale. How do you design the ID generation service?