Quanto de um git sha é * geralmente * considerado necessário para identificar exclusivamente uma alteração em uma determinada base de código?

Se você for criar, digamos, uma estrutura de diretório em que um diretório seja nomeado para um commit em um repositório Git, e você desejar que ele seja curto o suficiente para fazer com que seus olhos não sangrem, mas longo o suficiente para que a chance de colidir seria insignificante, quanto da substring SHA é geralmente necessária?

Digamos que desejo identificar exclusivamente essa alteração: https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

Posso usar apenas os quatro primeiros caracteres: https://github.com/wycats/handlebars.js/commit/e629

Mas sinto que isso seria arriscado. Mas, assumindo uma base de código que, ao longo de alguns anos, pode ter, digamos, 30 mil alterações, quais são as chances de colisão se eu usar 8 caracteres? 12? Existe um número geralmente considerado aceitável para esse tipo de coisa?

Esta pergunta é realmente respondida no capítulo 7 do livro Pro Git :

Geralmente, oito a dez caracteres são mais que suficientes para serem únicos em um projeto. Um dos maiores projetos Git, o kernel do Linux, está começando a precisar de 12 caracteres dos 40 possíveis para permanecer único.

7 dígitos é o padrão do Git para um SHA curto, o que é bom para a maioria dos projetos. A equipe do Kernel aumentou os deles várias vezes, como mencionado, porque eles têm várias centenas de milhares de confirmações. Portanto, para seus commits de ~ 30k, 8 ou 10 dígitos devem estar perfeitamente bem.

Nota: você pode solicitar git rev-parse --shorto SHA1 mais curto e único.
Veja " git obter hash curto do hash regular "

git rev-parse --short=4 921103db8259eb9de72f42db8b939895f5651489
92110

Como você pode ver no meu exemplo, o SHA1 tem um comprimento de 5, mesmo que eu tenha especificado um comprimento de 4.

Para grandes repositórios, 7 não é suficiente desde 2010 e confirma o dce9648 pelo próprio Linus Torvalds (git 1.7.4.4, outubro de 2010):

O padrão 7 vem do início do desenvolvimento do git, quando havia sete dígitos hexadecimais (ele abrange mais de 250 milhões de valores de hash).
Naquela época, eu achava que 65k revisões eram muito (era o que estávamos prestes a atingir em BK), e cada revisão tende a ter entre 5 e 10 novos objetos, mais ou menos, portanto, um milhão de objetos era um grande número.

(BK = BitKeeper)

Hoje em dia, o kernel não é nem o maior projeto git, e até o kernel tem cerca de 220k de revisões ( muito maiores do que a árvore do BK) e estamos nos aproximando de dois milhões de objetos.
Nesse ponto, sete dígitos hexadecimais ainda são únicos para muitos deles, mas quando falamos de apenas duas ordens de diferença de magnitude entre o número de objetos e o tamanho do hash, haverá colisões nos valores de hash truncados.
Não é mais nem mesmo irrealista - acontece o tempo todo.

Devemos aumentar a abreviação padrão que é irrealisticamente pequena e adicionar uma maneira de as pessoas definirem seu próprio padrão por projeto no arquivo de configuração git .

core.abbrev

Defina o comprimento dos nomes dos objetos aos quais é abreviado.
Se não especificado, muitos comandos abreviam para 7 hexadígitos, o que pode não ser suficiente para nomes de objetos abreviados permanecerem exclusivos por um período de tempo suficiente.

environment.c:

int minimum_abbrev = 4, default_abbrev = 7;

Nota: Conforme comentado abaixo por marco.m , core.abbrevLengthfoi renomeado no core.abbrevmesmo Git 1.7.4.4 no commit a71f09f

Renomeie de core.abbrevlengthvolta paracore.abbrev

--abbrev=$nAfinal, corresponde à opção da linha de comando.

Mais recentemente, Linus adicionado em cometer e6c587c (para Git 2.11, Q4 2016):
(como mencionado no Matthieu Moy 's resposta )

Nos primeiros dias, decidimos, de alguma forma, abreviar nomes de objetos para 7 hexadígitos, mas à medida que os projetos crescem, é cada vez mais provável que nomes de objetos tão curtos sejam criados nos dias anteriores e registrados nas mensagens de log não sejam mais exclusivos.

Atualmente, o projeto do kernel do Linux precisa de 11 a 12 hexdigits, enquanto o próprio Git precisa de 10 hexdigits para identificar exclusivamente os objetos que eles têm, enquanto muitos projetos menores ainda podem ser compatíveis com o padrão original de 7 hexdigits. O tamanho único não serve para todos os projetos.

Introduzir um mecanismo, em que estimamos o número de objetos no repositório após a primeira solicitação para abreviar um nome de objeto com a configuração padrão e criar um padrão sadio para o repositório. Com base na expectativa de que 2^(2N)veríamos uma colisão em um repositório com objetos ao usar nomes de objetos reduzidos para os primeiros N bits, use número suficiente de hexdigits para cobrir o número de objetos no repositório.
Cada hexdigit (4 bits) que adicionamos ao nome abreviado nos permite ter quatro vezes (2 bits) quantos objetos no repositório.

Veja commit e6c587c (01/10/2016) por Linus Torvalds ( torvalds) .
Consulte commit 7b5b772 , commit 65acfea (01 out 2016) por Junio ​​C Hamano ( gitster) .
^{(Mesclado por Junio ​​C Hamano - gitster- in commit bb188d0 , 03 de outubro de 2016)}

Essa nova propriedade (adivinhando um padrão razoável para o valor abreviado do SHA1) afeta diretamente como o Git calcula seu próprio número de versão para liberação .

Isso é conhecido como o problema do aniversário.

Para probabilidades inferiores a 1/2, a probabilidade de uma colisão pode ser aproximada como

p ~ = (n ² ) / (2 m)

Onde n é o número de itens e m é o número de possibilidades para cada item.

O número de possibilidades para uma sequência hexadecimal é 16 ^c, onde c é o número de caracteres.

Então, para 8 caracteres e 30K confirma

30K ~ = 2 ¹⁵

P ~ = (n ² ) / (2m) ~ = ((2 ¹⁵ ) ² ) / (2 * 16 ⁸ ) = 2 ^{30 de} / 2 ³³ = ⅛

Aumentando para 12 caracteres

P ~ = (n ² ) / (2m) ~ = ((2 ¹⁵ ) ² ) / (2 * 16, ¹² ) = 2 ^{30 de} / 2 ⁴⁹ = 2 ^-19

Esta pergunta foi respondida, mas para quem procura a matemática por trás - chama-se Problema de aniversário ( Wikipedia ).

É sobre a probabilidade de ter 2 (ou mais) pessoas do grupo de N pessoas para fazer aniversário no mesmo dia do ano. O que é analógico para provavelmente 2 (ou mais) confirmações git do repositório com N confirmações no total com o mesmo prefixo hash de comprimento X.

Veja a tabela de probabilidades . Por exemplo, para uma sequência hexadecimal de hash de comprimento 8, a probabilidade de ter uma colisão atinge 1% quando o repositório possui apenas cerca de 9300 itens (o git confirma). Para 110.000 confirmações, a probabilidade é de 75%. Mas se você tiver uma sequência hexadecimal de hash de comprimento 12, a probabilidade de colisão em 100.000 confirmações será inferior a 0,1%.

A versão 2.11 do Git (ou talvez 2.12?) Conterá um recurso que adapta o número de caracteres usados ​​em identificadores curtos (por exemplo git log --oneline) ao tamanho do projeto. Depois de usar essa versão do Git, a resposta para sua pergunta pode ser "escolha o tamanho que o Git fornecer git log --oneline, é seguro o suficiente".

Para mais detalhes, consulte Alterando o padrão para "core.abbrev"? discussão na edição 20 do Git Rev News e confirme bb188d00f7 .