As @RagingNerdoholic@lemmy.ml 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.
I'm sure you know this, but getting progressively larger servers is not the only way, why not scale horizontally?
I say this as someone with next to no idea how Lemmy works.