How Instagram checks 1 billion usernames and tells you in milliseconds if yours is free

You type rahul_07 on a signup page. Before you finish, it says "This username isn't available." Now imagine 1 billion users and a check on every keystroke. Sending every check to the database creates