Eu me deparei com esse problema muito na minha vida profissional. Usamos timestamp + número aleatório e tivemos sérios problemas quando nossos aplicativos aumentaram (mais clientes, mais servidores, mais solicitações). É verdade que usamos (estupidamente) apenas 4 dígitos e depois mudamos para 6, mas você ficaria surpreso com a frequência com que os erros ainda acontecem.

Durante um período de tempo suficientemente longo, você está garantido para obter erros de chave duplicados. Nosso aplicativo é de missão crítica e, portanto, mesmo a menor chance de falhar devido ao comportamento inerentemente aleatório era inaceitável. Começamos a usar UUIDs para evitar esse problema e gerenciamos cuidadosamente sua criação.

Usando UUIDs, o tamanho do índice aumentará e um índice maior resultará em desempenho inferior (talvez imperceptível, mas ainda assim inferior). No entanto, o MySQL suporta um tipo UUID nativo (nunca use varchar como chave primária !!), e pode lidar com indexação, pesquisa, etc. de maneira bastante eficiente, mesmo em comparação com bigint. O maior impacto no desempenho do seu índice é quase sempre o número de linhas indexadas, em vez do tamanho do item que está sendo indexado (a menos que você queira indexar em um texto longo ou algo ridículo assim).

Para responder à sua pergunta:Bigint (com números aleatórios anexados) ficará bem se você não planeja dimensionar seu aplicativo/serviço significativamente. Se seu código puder lidar com a mudança sem muita alteração e seu aplicativo não explodir se ocorrer um erro de chave duplicada, vá em frente. Caso contrário, morda a bala e vá para a opção mais substancial.

Você sempre pode implementar uma mudança maior mais tarde, como mudar para um back-end totalmente diferente (que estamos enfrentando agora... :P)