As @RagingNerdoholic says, create a distributed index of usernames, and do not allow the same username to be registered twice.
I'd also propose at the same time to create a Discord style username system to avoid potential clashes - if this system is going to become large (mainstream) then eventually available usernames will be hard to choose from.