Ile git sha jest * ogólnie * uważane za niezbędne do jednoznacznego zidentyfikowania zmiany w danej bazie kodu?


212

Jeśli zamierzasz zbudować, powiedzmy, strukturę katalogów, w której katalog jest nazwany dla zatwierdzenia w repozytorium Git, i chcesz, aby był on wystarczająco krótki, aby twoje oczy nie krwawiły, ale wystarczająco długie, aby szansa na kolizję byłoby nieistotne, jaka część podciągów SHA jest na ogół wymagana?

Powiedzmy, że chcę jednoznacznie zidentyfikować tę zmianę: https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

Mogę użyć zaledwie pierwszych czterech znaków: https://github.com/wycats/handlebars.js/commit/e629

Ale czuję, że byłoby to ryzykowne. Ale biorąc pod uwagę bazę kodu, która przez kilka lat może mieć - powiedzmy - 30k zmian, jakie są szanse na kolizję, jeśli użyję 8 znaków? 12? Czy istnieje liczba, która jest ogólnie uważana za akceptowalną dla tego rodzaju rzeczy?


Odpowiedzi:


230

Odpowiedź na to pytanie znajduje się w rozdziale 7 książki Pro Git :

Zasadniczo od ośmiu do dziesięciu znaków jest więcej niż wystarczających, aby być wyjątkowym w ramach projektu. Jeden z największych projektów Git, jądro Linuksa, zaczyna potrzebować 12 znaków z możliwych 40, aby pozostać wyjątkowym.

7 cyfr jest domyślną wartością Gita dla krótkiej SHA, więc jest to w porządku dla większości projektów. Zespół Kernela kilkakrotnie zwiększył swój, jak wspomniano, ponieważ ma kilkaset tysięcy zobowiązań. Tak więc dla twoich ~ 30 000 zatwierdzeń 8 lub 10 cyfr powinno być idealnie w porządku.


38
Zauważ też, że gitjest dość mądry, jeśli chodzi o to. Możesz ustawić skrót na krótki, powiedzmy na 4, i gitużyje 4 cyfr dla tylu skrótów, ile może, ale przełącz się na 5 lub więcej, gdy wie, że skrót nie jest unikalny ...
twalberg

31
Pamiętaj jednak, że to oczywiście dotyczy tylko momentu wydrukowania SHA przez Git. Jeśli „zapiszesz” skróty SHA (np. W dziennikach, wiadomościach e-mail, wiadomościach błyskawicznych itp.) I użyjesz ich później, aby odnieść się do zatwierdzeń, mogą one już nie być unikalne! Chociaż na pewno nie jest to normalne dla normalnych długości, takich jak 7-12 znaków, jeśli zejdziesz do 4 lub 5 i otrzymasz kilka dziesięciu tysięcy nowych obiektów (lub zatwierdzeń, w zależności od kontekstu), to może rzeczywiście powrócić, by cię ugryźć.
Nevik Rehnel

140

Uwaga: możesz poprosić git rev-parse --shorto najkrótszy i jednocześnie unikalny SHA1.
Zobacz „ git dostaje krótki skrót od zwykłego skrótu

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

Jak widać w moim przykładzie, SHA1 ma długość 5, nawet jeśli określiłem długość 4.


W przypadku dużych transakcji repo 7 nie wystarczy od 2010 r., A sam dce9648 sam Linus Torvalds (git 1.7.4.4, paź 2010):

Domyślna wartość 7 pochodzi z dość wczesnego rozwoju gita, kiedy siedem cyfr szesnastkowych było dużo (obejmuje około 250 milionów wartości skrótu).
Wtedy myślałem, że 65 000 wersji było dużo (to właśnie mieliśmy trafić w BK), a każda wersja zawiera około 5-10 nowych obiektów, więc milion obiektów to duża liczba.

(BK = BitKeeper)

Obecnie jądro nie jest nawet największym projektem git, a nawet jądro ma około 220 000 wersji ( znacznie większych niż kiedykolwiek było drzewo BK), a my zbliżamy się do dwóch milionów obiektów.
W tym momencie siedem cyfr szesnastkowych jest wciąż unikatowych dla wielu z nich, ale kiedy mówimy o tylko dwóch rzędach wielkości różnicy między liczbą obiektów a rozmiarem skrótu, wystąpią kolizje w obciętych wartościach skrótu.
Nie jest już nawet nierealne - zdarza się to cały czas.

Powinniśmy zarówno zwiększyć domyślny skrót, który był nierealistycznie mały, jak i dodać sposób, w jaki ludzie mogą ustawić własny domyślny projekt w pliku konfiguracyjnym git .

core.abbrev

Ustaw długość nazw obiektów, które są skracane.
Jeśli nie jest określony, wiele poleceń skraca się do 7 cyfr szesnastkowych, co może nie wystarczyć, aby skrócone nazwy obiektów pozostały unikalne przez wystarczająco długi czas.

environment.c:

int minimum_abbrev = 4, default_abbrev = 7;

Uwaga: Jak skomentował poniżej przez marco.m , core.abbrevLengthzostał przemianowany na core.abbrevw tym samym Git 1.7.4.4 w popełnić a71f09f

Zmień nazwę z core.abbrevlengthpowrotem nacore.abbrev

W --abbrev=$nkońcu odpowiada opcji wiersza poleceń.


Niedawno, Linus dodane popełnić e6c587c (dla Git 2.11, Q4 2016)
(jak wspomniano w Matthieu Moy „s odpowiedzi )

W dość wczesnych dniach w jakiś sposób postanowiliśmy skrócić nazwy obiektów do 7-heksdigitów, ale wraz z rozwojem projektów coraz bardziej prawdopodobne jest, że tak krótkie nazwy obiektów powstają we wcześniejszych dniach i są zapisywane w komunikatach dziennika jako niepowtarzalne.

Obecnie projekt jądra Linuksa potrzebuje 11 do 12 heksdigitów, podczas gdy sam Git potrzebuje 10 hexdigitów, aby jednoznacznie zidentyfikować posiadane obiekty, podczas gdy wiele mniejszych projektów wciąż może być w porządku z oryginalną wartością domyślną 7-hexdigit. Jeden rozmiar nie pasuje do wszystkich projektów.

Wprowadź mechanizm, w którym szacujemy liczbę obiektów w repozytorium przy pierwszym żądaniu skrócenia nazwy obiektu z ustawieniem domyślnym i wymyślenia rozsądnego ustawienia domyślnego dla repozytorium. W oparciu o oczekiwanie, że zobaczymy kolizję w repozytorium z 2^(2N)obiektami przy użyciu nazw obiektów skróconych do pierwszych N bitów, użyj wystarczającej liczby heksdigitów, aby pokryć liczbę obiektów w repozytorium.
Każdy hexdigit (4 bity), który dodajemy do skróconej nazwy, pozwala nam mieć cztery razy (2 bity) tyle obiektów w repozytorium.

Zobacz commit e6c587c (01 października 2016) autorstwa Linusa Torvaldsa ( torvalds) .
Zobacz commit 7b5b772 , commit 65acfea (01 października 2016) autor: Junio ​​C Hamano ( gitster) .
(Połączone przez Junio ​​C Hamano - gitster- w commit bb188d0 , 03 października 2016)

Ta nowa właściwość (odgadnięcie rozsądnej wartości domyślnej wartości skrótu SHA1) ma bezpośredni wpływ na sposób, w jaki Git oblicza własny numer wersji do wydania .


3
Ta odpowiedź pozwala sprawdzić, jaki jest najdłuższy „skrócony” skrót w jednym repozytorium: stackoverflow.com/a/32406103/1858225
Kyle Strand

1
Uwaga, core.abbrevLengthktórej nazwa została zmieniona na core.abbrev.
marco.m

@ marco.m Dziękujemy. Odpowiednio zmieniłem odpowiedź. I powiązałem z zatwierdzeniem Git, które rejestruje nową nazwę core.abbrev.
VonC,

Dodam tylko, że możesz uruchomić, git rev-parse --short=10 --verify HEADaby wygenerować 10 znaków. Wcześniej korzystaliśmy git log -1 --format=%h, ale wygenerowało to tylko 7 znaków i doszło do kolizji.
grayaii 11.04.17

Dzięki za wyjaśnienie, dokumenty ( git-scm.com/docs/git-rev-parse ) są nieaktualne.
André Werlang

36

Jest to znane jako problem urodzinowy.

Dla prawdopodobieństw mniejszych niż 1/2 prawdopodobieństwo zderzenia można oszacować jako

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

Gdzie n jest liczbą elementów, a m jest liczbą możliwości dla każdej pozycji.

Liczba możliwości łańcucha szesnastkowego wynosi 16 c, gdzie c jest liczbą znaków.

Tak więc dla 8 znaków i 30 000 zatwierdzeń

30 K ~ = 2 15

P ~ = (n = 2 ) / (2M) ~ = ((2 15 ) 2 ) / (2 * 16 : 8 ) = 2 30 /2 33 = ⅛

Zwiększenie go do 12 znaków

P ~ = (n = 2 ) / (2M) ~ = ((2 15 ) 2 ) / (2 * 16 : 12 ) = 2 30 /2 49 = 2 -19


Dokładnie pytanie, które próbowałem rozwiązać, dziękuję! Pomocna jest również tabela prawdopodobieństwa połączona z odpowiedzią @ Messy.
Kyle Chadha,

doskonale, nie potrzebujemy nic więcej, tylko więcej, wyjaśnij to nie tylko co to jest, ale także jak to się dzieje ...
workplaylifecycle

13

Odpowiedź na to pytanie, ale dla każdego, kto szuka matematyki za nią - nazywa się to Problemem urodzin ( Wikipedia ).

Chodzi o prawdopodobieństwo, że 2 (lub więcej) osób z grupy N osób będzie miało urodziny tego samego dnia w roku. Który jest analogiczny do prawdopodobnie 2 (lub więcej) zatwierdzeń git z repozytorium posiadających łącznie N zatwierdzeń o tym samym prefiksie skrótu o długości X.

Spójrz na tabelę prawdopodobieństwa . Na przykład dla haszującego ciągu szesnastkowego o długości 8 prawdopodobieństwo wystąpienia kolizji osiąga 1%, gdy repozytorium zawiera tylko około 9300 elementów (git commits). Dla 110 000 zatwierdzeń prawdopodobieństwo wynosi 75%. Ale jeśli masz hash hex hex o długości 12, prawdopodobieństwo kolizji w 100 000 commits wynosi poniżej 0,1%.


2

Wersja Git 2.11 (a może 2.12?) Będzie zawierała funkcję, która dostosowuje liczbę znaków używanych w krótkich identyfikatorach (np. git log --oneline) Do wielkości projektu. Gdy użyjesz takiej wersji Git, odpowiedzią na twoje pytanie może być „wybierz git log --oneline, jaką długość daje Git , jest to wystarczająco bezpieczne”.

Aby uzyskać więcej informacji, zobacz Zmienianie wartości domyślnej dla „core.abbrev”? dyskusja w Git Rev News wydanie 20 i zatwierdzenie bb188d00f7 .

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.