310 votes

Quelle partie d'un sha de git est *généralement* considérée comme nécessaire pour identifier de manière unique un changement dans une base de code donnée?

Si vous envisagez de construire, disons, une structure de répertoire où un répertoire est nommé d'après un commit dans un dépôt Git, et que vous voulez qu'il soit assez court pour éviter que vos yeux saignent, mais suffisamment long pour que les chances de collision soient négligeables, combien de caractères du sous-ensemble SHA sont généralement requis ?

Disons que je veux identifier de manière unique ce changement : https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

Je peux utiliser aussi peu que les quatre premiers caractères : https://github.com/wycats/handlebars.js/commit/e629

Mais je pense que ce serait risqué. Mais en supposant une base de code qui, sur quelques années, pourrait avoir—disons—30k changements, quelles sont les chances de collision si j'utilise 8 caractères ? 12 ? Y a-t-il un nombre généralement considéré comme acceptable pour ce genre de chose ?

335voto

Nevik Rehnel Points 5446

Cette question est en fait répondue dans le Chapitre 7 du livre Pro Git:

Généralement, huit à dix caractères sont plus que suffisants pour être uniques dans un projet. Un des plus grands projets Git, le noyau Linux, commence à avoir besoin de 12 caractères sur les 40 possibles pour rester unique.

7 chiffres sont le défaut Git pour un court SHA, donc c'est très bien pour la plupart des projets. L'équipe du Kernel a augmenté le leur plusieurs fois, comme mentionné car ils ont plusieurs centaines de milliers de commits. Donc pour vos ~30k commits, 8 ou 10 chiffres devraient être parfaitement suffisants.

214voto

VonC Points 414372

Note: you can ask git rev-parse --short pour obtenir le SHA1 le plus court et pourtant unique.
Voir "git obtenir un hachage court à partir d'un hachage régulier"

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

Comme vous pouvez le voir dans mon exemple, le SHA1 a une longueur de 5 même si j'ai spécifié une longueur de 4.


Pour les grands dépôts, 7 n'est pas suffisant depuis 2010, et commit dce9648 par Linus Torvalds lui-même (git 1.7.4.4, oct 2010) :

La valeur par défaut de 7 provient des premiers stades de développement de git, quand sept chiffres héxadécimaux représentait beaucoup (cela couvre environ 250+ millions de valeurs de hachage).
À l'époque, je pensais que 65k révisions étaient beaucoup (c'était ce que nous étions sur le point d'atteindre dans BK), et chaque révision tend à être d'environ 5-10 nouveaux objets environ, donc un million d'objets était un grand nombre.

(BK = BitKeeper)

De nos jours, le noyau n'est même pas le plus grand projet git, et même le noyau a environ 220k révisions (beaucoup plus grand que l'arbre BK n'a jamais été) et nous approchons de deux millions d'objets.
À ce stade, sept chiffres héxadécimaux sont encore uniques pour beaucoup d'entre eux, mais quand nous parlons d'une différence de seulement deux ordres de grandeur entre le nombre d'objets et la taille du hachage, il y aura des collisions dans les valeurs de hachage tronquées.
Ce n'est plus du tout irréaliste - cela arrive tout le temps.

Nous devrions à la fois augmenter l'abrégé par défaut qui était irréaliste petit, et ajouter un moyen pour les gens de définir leur propre valeur par défaut par projet dans le fichier de configuration de git.

core.abbrev

Définir la longueur à laquelle les noms des objets sont abrégés.
Si non spécifiée, de nombreuses commandes abrègent à 7 chiffres héxadécimaux, ce qui peut ne pas être suffisant pour que les noms d'objets abrégés restent uniques pendant suffisamment longtemps.

environment.c:

int minimum_abbrev = 4, default_abbrev = 7;

Note: Comme commenté ci-dessous par marco.m, core.abbrevLength a été renommé en core.abbrev dans ce même Git 1.7.4.4 dans commit a71f09f

Renommer core.abbrevlength en core.abbrev

Cela correspond à l'option en ligne de commande --abbrev=$n après tout.


Plus récemment, Linus a ajouté dans commit e6c587c (pour Git 2.11, T4 2016) :
(comme mentionné dans la réponse de Matthieu Moy ici)

Dans les premiers jours, nous avons décidé d'abréger les noms d'objets en 7 chiffres héxadécimaux, mais à mesure que les projets grandissent, il est de plus en plus probable de voir des noms d'objets aussi courts fabriqués dans les premiers jours et enregistrés dans les messages de journal ne sont plus uniques.

Actuellement, le projet du noyau Linux a besoin de 11 à 12 chiffres héxadécimaux, tandis que Git lui-même a besoin de 10 chiffres héxadécimaux pour identifier de manière unique les objets qu'ils possèdent, tandis que de nombreux projets plus petits peuvent encore être satisfaits par la valeur par défaut de 7 chiffres héxadécimaux originales. Une seule taille ne convient à tous les projets.

Introduire un mécanisme, où nous estimons le nombre d'objets dans le dépôt à la première demande d'abréviation d'un nom d'objet avec le réglage par défaut et définir une valeur par défaut raisonnable pour le dépôt. Basé sur l'idée que nous verrions des collisions dans un dépôt avec 2^(2N) objets en utilisant des noms d'objets raccourcis sur les premiers N bits, utiliser un nombre suffisant de chiffres héxadécimaux pour couvrir le nombre d'objets dans le dépôt.
Chaque chiffre héxadécimal (4 bits) que nous ajoutons au nom abrégé nous permet d'avoir quatre fois (2 bits) autant d'objets dans le dépôt.

Voir le commit e6c587c (01 Oct 2016) par Linus Torvalds (torvalds).
Voir commit 7b5b772, commit 65acfea (01 Oct 2016) par Junio C Hamano (gitster).
(Fusionné par Junio C Hamano -- gitster -- dans commit bb188d0, 03 Oct 2016)

Cette nouvelle propriété (deviner une valeur d'abrégé raisonnable pour les valeurs SHA1) a un effet direct sur la façon dont Git calcule sa propre numéro de version pour la publication.

69voto

plugwash Points 795

Cela est connu sous le nom de problème d'anniversaire.

Pour des probabilités inférieures à 1/2, la probabilité d'une collision peut être approximée par

p ≈ (n2)/(2m)

Où n est le nombre d'éléments et m est le nombre de possibilités pour chaque élément.

Le nombre de possibilités pour une chaîne hexadécimale est de 16c où c est le nombre de caractères.

Donc pour 8 caractères et 30K commits

30K ≈ 215

p ≈ (n2)/(2m) ≈ ((215)2)/(2*168) = 230/233 = ⅛

En l'augmentant à 12 caractères

p ≈ (n2)/(2m) ≈ ((215)2)/(2*1612) = 230/249 = 2-19

17voto

Messa Points 5988

Cette question a été répondue, mais pour ceux qui cherchent les mathématiques derrière - cela s'appelle le problème d'anniversaire (Wikipedia).

Il s'agit de la probabilité qu'il y ait 2 (ou plus) personnes d'un groupe de N personnes ayant leur anniversaire le même jour de l'année. Ce qui est analogue à la probabilité que 2 (ou plus) confirmations git d'un dépôt ayant N confirmations au total aient le même préfixe de hachage de longueur X.

Regardez la table de probabilités. Par exemple, pour une chaîne hexadécimale de longueur 8, la probabilité d'avoir une collision atteint 1 % lorsque le dépôt contient environ 9300 éléments (confirmations git). Pour 110 000 confirmations, la probabilité est de 75 %. Mais si vous avez une chaîne hexadécimale de longueur 12, la probabilité de collision dans 100 000 confirmations est inférieure à 0,1 %.

2voto

Matthieu Moy Points 5947

La version Git 2.11 (ou peut-être 2.12?) contiendra une fonctionnalité qui adapte le nombre de caractères utilisés dans les identifiants courts (par exemple git log --oneline) à la taille du projet. Une fois que vous utilisez cette version de Git, la réponse à votre question peut être "choisissez la longueur que Git vous donne avec git log --oneline, c'est suffisamment sécurisé".

Pour plus de détails, consultez la discussion sur le changement par défaut de "core.abbrev" dans Git Rev News édition 20 et le commit bb188d00f7.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X