Por que a pasta Git .git / objects / é subdividida em muitas pastas com prefixo SHA?

21

O Git armazena objetos internamente (Blobs, árvores) na .git/objects/pasta. Cada objeto pode ser referenciado por um hash SHA1 que é calculado a partir do conteúdo do objeto.

No entanto, os objetos não são armazenados .git/objects/diretamente na pasta. Em vez disso, cada objeto é armazenado dentro de uma pasta que começa com o prefixo de seu hash SHA1. Portanto, um objeto com o hash b7e23ec29af22b0b4e41da31e868d57226121c84seria armazenado em.git/objects/b7/e23ec29af22b0b4e41da31e868d57226121c84

Por que o Git subdivide seu armazenamento de objetos dessa maneira?

Os recursos que eu pude encontrar, como a página no interior do Git no git-scm, apenas explicaram como , não o porquê .

Qqwy
fonte

Respostas:

33

É possível colocar todos os arquivos em um diretório, embora às vezes isso possa se tornar um pouco grande. Muitos sistemas de arquivos têm um limite . Deseja colocar um repositório git em uma unidade formatada em FAT32 em um pendrive? Você pode armazenar apenas 65.535 arquivos em um único diretório. Isso significa que é necessário subdividir a estrutura de diretório para que seja menos provável o preenchimento de um único diretório.

Isso até se tornaria um problema com outros sistemas de arquivos e repositórios git maiores. Um repositório Git relativamente pequeno que eu tenho (cerca de 360MiB) e tem 181.546 objetos para arquivos 11k. Puxe o repositório Linux e você terá 4.374.054 objetos. Se você colocasse tudo isso em um diretório, seria impossível verificar e travar (por algum significado de 'travar') o sistema de arquivos.

Tão? Você o divide por byte. Abordagens semelhantes são feitas com aplicativos como o FireFox:

~/Li/Ca/Fi/Pr/7a/Cache $ ls
0/           4/           8/           C/           _CACHE_001_
1/           5/           9/           D/           _CACHE_002_
2/           6/           A/           E/           _CACHE_003_
3/           7/           B/           F/           _CACHE_MAP_

Além disso, também vai para uma questão de desempenho. Considere o desempenho NTFS com vários nomes de arquivos longos :

O Windows NT leva muito tempo para executar operações de diretório em unidades formatadas pelo sistema de arquivos Windows NT (NTFS) que contêm um grande número de arquivos com nomes longos (nomes que não estão em conformidade com a convenção 8.3) em um único diretório.

Quando o NTFS enumera arquivos em um diretório, ele deve procurar os nomes 8.3 associados aos nomes longos dos arquivos. Como um diretório NTFS é mantido em um estado classificado, os nomes longos correspondentes do arquivo e os nomes 8.3 geralmente não estão próximos um do outro na lista de diretórios. Portanto, o NTFS usa uma pesquisa linear do diretório para todos os arquivos presentes. Como resultado, a quantidade de tempo necessária para executar uma listagem de diretório aumenta com o quadrado do número de arquivos no diretório. Para um pequeno número de arquivos (menos de algumas centenas), o atraso é insignificante. Porém, à medida que o número de arquivos em um diretório aumenta para vários milhares, o tempo necessário para executar uma listagem pode aumentar para minutos, horas ou até dias. O problema é agravado se os nomes de arquivos longos forem muito semelhantes - diferindo apenas nos últimos caracteres.

Com arquivos nomeados após as somas de verificação SHA1, essa pode ser uma receita para um desastre e um desempenho péssimo.

Embora o acima seja de uma nota técnica do Windows NT 3.5 (e NTFS 1.2 - comumente usada de 1995 ao início dos anos 2000), isso também pode ser visto em coisas como EXT3, com implementações do sistema de arquivos vinculadas a listas que exigem pesquisa de O (n) . E mesmo com essa mudança de árvore B:

Embora o algoritmo HTree melhore significativamente os tempos de pesquisa, ele pode causar algumas regressões de desempenho para cargas de trabalho que usaram readdir () para executar alguma operação de todos os arquivos em um diretório grande.
...
Uma solução potencial para mitigar esse problema de desempenho, sugerida por Daniel Phillips e Andreas Dilger, mas ainda não implementada, envolve o kernel escolhendo inodes livres cujos números de inode atendem a uma propriedade que agrupa os inodes pelo hash do nome do arquivo. Daniel e Andreas sugerem alocar o inode de um intervalo de inodes com base no tamanho do diretório e, em seguida, escolher um inode livre desse intervalo com base no hash do nome do arquivo. Em teoria, isso deve reduzir a quantidade de thrashing resultante ao acessar os inodes referenciados no diretório na ordem readdir. No entanto, não está claro que essa estratégia resulte em uma aceleração; na verdade, isso poderia aumentar o número total de blocos de inodes que talvez precisassem ser referenciados e, assim, piorar o desempenho das cargas de trabalho readdir () + stat (). Claramente,

Aliás, esse pouco sobre como melhorar o desempenho foi de 2005, no mesmo ano em que o git foi lançado.

Como visto no Firefox e em muitos outros aplicativos que possuem muitos arquivos em cache de hash, o design de dividir o cache por byte. Ele tem um custo insignificante de desempenho e, quando usado em várias plataformas com sistemas que podem ser um pouco antigos, pode muito bem ser a diferença entre o programa funcionando ou não.

Comunidade
fonte
1
Você notou que o artigo de desempenho do NTFS de que você cita se aplica ao NT 3.5, lançado em 1994, certo?
Avner Shahar-Kashtan
1
@ AvnerShahar-Kashtan sim. O Git foi lançado em 2005. Eu sei o que estava usando sistemas de arquivos baseados em NTFS v1.2 em um ambiente corporativo até o início dos anos 2000 (em uma empresa de tecnologia, no entanto). Certamente há sobreposição entre os requisitos do git e os sistemas de arquivos nos sistemas geralmente disponíveis no momento.
Talvez seja mais claro se você afirmou que este pode ser um artefato histórico do estado da tecnologia quando o git foi introduzido, porque, como está, para uma pergunta feita em 2015, citando uma limitação técnica de vinte anos (aceitar a resposta) ) parece confuso.
Avner Shahar-Kashtan
Para ser justo, gito sistema de "pacote" atenua muitos desses problemas. Teoricamente, gitpoderia estar usando apenas um diretório e apenas reembalar quando o número de arquivos nesse diretório exceder um determinado limite (possivelmente dependente de FS).
Nneonneo 1/11
5
@ AvnerShahar-Kashtan, se você ler o artigo do SO vinculado, poderá ver que lidar com diretórios contendo um grande número de arquivos é problemático em vários sistemas de arquivos e sistemas operacionais, não apenas no NT 3.5. Limites de arquivo à parte, mesmo listar os arquivos pode resultar em uma grande quantidade de sobrecarga.
8

Há duas razões pelas quais isso é desejável.

Diretórios não podem ser arbitrariamente grandes. Por exemplo, alguns sistemas de arquivos (razoavelmente modernos!) Estão limitados a 32000 entradas em um único diretório. O número de confirmações no kernel do Linux é nessa ordem de magnitude. Subdividir as confirmações pelos dois primeiros dígitos hexadecimais limita o tamanho de nível superior a 256 entradas. Os subdiretórios serão muito menores para repositórios git típicos.

Diretórios são verificados linearmente. Em alguns sistemas de arquivos (por exemplo, a família Ext *), um diretório é uma lista ou tabela de entradas vinculada. Para procurar um arquivo, a lista inteira é verificada até que um nome de arquivo correspondente seja encontrado. Claramente, isso é indesejável para desempenho. Muitos sistemas de arquivos modernos usam adicionalmente tabelas de hash ou árvores B para pesquisa rápida, mas nem todo mundo pode tê-las. Manter cada diretório pequeno significa tempos de acesso rápidos.

amon
fonte
1
"alguns sistemas de arquivos (razoavelmente modernos!) estão limitados a 32000 entradas em um único diretório." Se essa é a limitação mais rigorosa que o Git está cumprindo, não seria melhor o Git ter usado os três primeiros caracteres do hash, em vez dos dois primeiros ? Isso significaria que o objectsdiretório poderia conter até 4096 subdiretórios, em vez de limitar-se a 256, atendendo ao requisito acima, mas com a vantagem adicional de que esses subdiretórios teriam 16 vezes menos probabilidade de acabar contendo> 32000 arquivos.
Sampablokuper 11/09/16
1

Esses 256 blocos permitem ao git armazenar repositórios maiores em sistemas de arquivos que limitam os arquivos numéricos em um diretório e fornecem desempenho descendente em sistemas de arquivos que se tornam mais lentos com diretórios contendo muitos arquivos.

Kasper van den Berg
fonte
1

Existem alguns sistemas de arquivos e / ou implementações de sistema de arquivos e / ou libc em que o desempenho diminui com um grande número de entradas de diretório.

Jörg W Mittag
fonte