Either your system is happy enough to route every new entity through "one DB at scale" so it can let your "one DB at scale" be in charge of an auto-incrementing long, or it isn't.
A common method is to have a small app (which can quite easily be HA) that hands out sequential chunks to each shard, interleaving and/or gapping as necessary.
This launches into the other debate about PKs: using UUIDs rather than sequential keys.