¿Cuánto de un git sha se considera * generalmente * necesario para identificar de manera única un cambio en una base de código dada?

212

Si va a construir, digamos, una estructura de directorio donde se nombra un directorio para una confirmación en un repositorio de Git, y desea que sea lo suficientemente corto como para que sus ojos no sangren, pero lo suficientemente largo como para que la posibilidad de que choque sería insignificante, ¿cuánto de la subcadena SHA generalmente se requiere?

Digamos que quiero identificar de manera única este cambio: https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

Puedo usar tan poco como los primeros cuatro caracteres: https://github.com/wycats/handlebars.js/commit/e629

Pero siento que eso sería arriesgado. Pero suponiendo una base de código que, durante un par de años, podría tener, digamos, 30 mil cambios, ¿cuáles son las posibilidades de colisión si uso 8 caracteres? 12? ¿Hay un número que generalmente se considera aceptable para este tipo de cosas?

git github sha Jun-Dai Bates-Kobashigawa
fuente
Relacionado: stackoverflow.com/questions/32405922/…
jub0bs

Respuestas:

230

Esta pregunta se responde realmente en el Capítulo 7 del libro Pro Git :

En general, de ocho a diez caracteres son más que suficientes para ser únicos dentro de un proyecto. Uno de los mayores proyectos de Git, el kernel de Linux, está comenzando a necesitar 12 caracteres de los 40 posibles para mantenerse único.

7 dígitos es el valor predeterminado de Git para un SHA corto, por lo que está bien para la mayoría de los proyectos. El equipo de Kernel ha aumentado el suyo varias veces, como se mencionó, porque tienen varios cientos de miles de confirmaciones. Entonces, para sus confirmaciones de ~ 30k, 8 o 10 dígitos deberían estar perfectamente bien.

Nevik Rehnel
fuente
38
También tenga en cuenta que gites bastante inteligente cuando se trata de esto. Puede establecer la abreviatura corta, digamos a 4, y gitva a utilizar 4 dígitos para el mayor número de hashes que puede, pero el interruptor a 5 o más cuando se sabe que la abreviatura no es única ...
twalberg
31
Sin embargo, tenga en cuenta también que, por supuesto, esto solo se aplica por el momento en que Git imprime el SHA. Si "guarda" los SHA abreviados (por ejemplo, en registros, correos electrónicos, mensajes instantáneos, etc.) y los usa más adelante para referirse a las confirmaciones, es posible que ya no sean únicos. Si bien es poco probable que tenga longitudes normales como 7-12 caracteres, si baja a 4 o 5, y obtiene unos diez mil objetos nuevos (o confirmaciones, según el contexto), esto podría volver a morderlo.
Nevik Rehnel
140

Nota: puede solicitar git rev-parse --shortel SHA1 más corto y único.
Consulte " git get hash corto de hash regular "

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

Como puede ver en mi ejemplo, el SHA1 tiene una longitud de 5 incluso si especifiqué una longitud de 4.

Para repositorios grandes, 7 no es suficiente desde 2010, y comete dce9648 por el propio Linus Torvalds (git 1.7.4.4, oct 2010):

El valor predeterminado de 7 proviene bastante temprano en el desarrollo de git, cuando siete dígitos hexadecimales eran mucho (cubre más de 250 millones de valores hash).
En aquel entonces, pensé que 65k revisiones eran muchas (era lo que estábamos a punto de alcanzar en BK), y cada revisión tiende a ser de 5 a 10 objetos nuevos más o menos, por lo que un millón de objetos era un gran número.

(BK = BitKeeper)

En estos días, el núcleo ni siquiera es el proyecto git más grande, e incluso el núcleo tiene alrededor de 220k revisiones ( mucho más grande que el árbol BK) y nos estamos acercando a dos millones de objetos.
En ese punto, siete dígitos hexadecimales siguen siendo únicos para muchos de ellos, pero cuando hablamos de solo dos órdenes de diferencia de magnitud entre el número de objetos y el tamaño del hash, habrá colisiones en valores de hash truncados.
Ya no es casi irreal: sucede todo el tiempo.

Ambos deberíamos aumentar la abreviatura predeterminada que era irrealmente pequeña, y agregar una forma para que las personas establezcan su propio valor predeterminado por proyecto en el archivo de configuración de git .

core.abbrev

Establezca la longitud a la que se abrevian los nombres de objeto.
Si no se especifica, muchos comandos abrevian a 7 dígitos hexadecimales, lo que puede no ser suficiente para que los nombres abreviados de objetos permanezcan únicos durante un tiempo suficientemente largo.

environment.c:

int minimum_abbrev = 4, default_abbrev = 7;

Nota: Como se comenta a continuación por marco.m , core.abbrevLengthse renombró core.abbreven ese mismo Git 1.7.4.4 en commit a71f09f

Cambiar el nombre core.abbrevlengthacore.abbrev

Corresponde a la --abbrev=$nopción de línea de comando después de todo.

Más recientemente, Linus agregó en commit e6c587c (para Git 2.11, Q4 2016):
(como se menciona en la respuesta de Matthieu Moy )

En los primeros días, de alguna manera decidimos abreviar los nombres de los objetos a 7 dígitos hexadecimales, pero a medida que los proyectos crecen, es cada vez más probable ver nombres de objetos tan cortos hechos en días anteriores y registrados en los mensajes de registro que ya no son únicos.

Actualmente, el proyecto de kernel de Linux necesita de 11 a 12 dígitos hexadecimales, mientras que Git necesita 10 dígitos hexadecimales para identificar de forma exclusiva los objetos que tienen, mientras que muchos proyectos más pequeños pueden estar bien con el valor predeterminado original de 7 dígitos hexadecimales. Un tamaño no se adapta a todos los proyectos.

Introduzca un mecanismo, donde estimamos el número de objetos en el repositorio en la primera solicitud para abreviar el nombre de un objeto con la configuración predeterminada y llegar a un valor predeterminado sensato para el repositorio. Según la expectativa de que veríamos una colisión en un repositorio con 2^(2N)objetos al usar nombres de objetos acortados a los primeros N bits, use un número suficiente de dígitos hexadecimales para cubrir el número de objetos en el repositorio.
Cada dígito hexadecimal (4 bits) que agregamos al nombre abreviado nos permite tener cuatro veces (2 bits) tantos objetos en el repositorio.

Ver commit e6c587c (01 oct 2016) por Linus Torvalds ( torvalds) .
Ver commit 7b5b772 , commit 65acfea (01 Oct 2016) por Junio ​​C Hamano ( gitster) .
(Fusionada por Junio ​​C Hamano - gitster- en commit bb188d0 , 03 oct 2016)

Esa nueva propiedad (adivinar un valor predeterminado razonable para el valor abreviado SHA1) tiene un efecto directo sobre cómo Git calcula su propio número de versión para su lanzamiento .

VonC
fuente
3
Esta respuesta proporciona una forma de verificar cuál es el hash "acortado" más largo en un único repositorio: stackoverflow.com/a/32406103/1858225
Kyle Strand
1
Tenga en cuenta que se core.abbrevLengthha cambiado el nombre a core.abbrev.
marco.m
@ marco.m Gracias. He modificado la respuesta en consecuencia. Y me he vinculado al Git commit que registra ese nuevo nombre core.abbrev.
VonC
Solo agregaré a esto que puedes ejecutar git rev-parse --short=10 --verify HEADpara generar 10 caracteres. ESTAMOS utilizando git log -1 --format=%h, pero eso solo generó 7 caracteres y tuvimos una colisión.
grayaii
Gracias por la explicación, los documentos ( git-scm.com/docs/git-rev-parse ) están obsoletos.
André Werlang
36

Esto se conoce como el problema del cumpleaños.

Para probabilidades menores a la mitad, la probabilidad de una colisión puede ser aproximada como

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

Donde n es el número de elementos ym es el número de posibilidades para cada elemento.

El número de posibilidades para una cadena hexadecimal es 16 c donde c es el número de caracteres.

Entonces, para 8 personajes y 30K confirmaciones

30K ~ = 2 15

p ~ = (n 2 ) / (2m) ~ = ((2 15 ) 2 ) / (2 * 16 8 ) = 2 30 /2 33 = ⅛

Incrementándolo a 12 caracteres

p ~ = (n 2 ) / (2m) ~ = ((2 15 ) 2 ) / (2 * 16 12 ) = 2 30 /2 49 = 2 -19

lavado
fuente
Exactamente la pregunta que estaba tratando de resolver, ¡gracias! La tabla de probabilidad vinculada en la respuesta de @ Messa también es útil.
Kyle Chadha
excelente, no necesitamos nada más sino más como esto, explíquelo no solo qué es sino también cómo llega ...
workplaylifecycle
13

Esta pregunta ha sido respondida, pero para cualquiera que busque las matemáticas detrás, se llama problema de cumpleaños ( Wikipedia ).

Se trata de la probabilidad de que 2 (o más) personas del grupo de N personas cumplan años el mismo día del año. Lo cual es analógico a la probabilidad de 2 (o más) confirmaciones git del repositorio que tienen N confirmaciones en total que tienen el mismo prefijo hash de longitud X.

Mira la tabla de probabilidad . Por ejemplo, para la cadena hexadecimal hash de longitud 8, la probabilidad de tener una colisión alcanza el 1% cuando el repositorio tiene aproximadamente 9300 elementos (git commits). Para 110 000 commits, la probabilidad es del 75%. Pero si tiene una cadena hexadecimal hash de longitud 12, la probabilidad de colisión en 100.000 confirmaciones es inferior al 0.1%.

Messa
fuente
2

La versión 2.11 de Git (¿o quizás 2.12?) Contendrá una función que adapte el número de caracteres utilizados en los identificadores cortos (por ejemplo git log --oneline) al tamaño del proyecto. Una vez que use dicha versión de Git, la respuesta a su pregunta puede ser "elija la longitud que le dé Git git log --oneline, es lo suficientemente seguro".

Para obtener más detalles, consulte ¿Cómo cambiar el valor predeterminado para "core.abbrev"? discusión en Git Rev News edición 20 y commit bb188d00f7 .

Matthieu Moy
fuente