Friend search by player name in an online game

Your online game has 50 million player accounts. Each player has a unique name of 3 to 16 characters: English letters, digits and underscores. Upper and lower case count as the same letter, so "Kai_99" and "kai_99" cannot both exist. To add a friend, a player starts typing a name. After the third character, the game shows up to 10 names that start with what they typed, in alphabetical order.

At the evening peak, players make about 3,000 of these lookups a second, and each should answer within 100 ms. About 60,000 players sign up or change their name each day. A new name should show up within 1 minute, and an old one should stop showing. Banned players, about 2 million of them, must never show.

Where does the game look names up, and how does a typed prefix become 10 names?