Thuật toán khác biệt nhị phân git (lưu trữ delta) có được chuẩn hóa không?

Question

Git sử dụng nén đồng bộ để lưu trữ các đối tượng tương tự nhau.

Thuật toán này có được chuẩn hóa và sử dụng trong các công cụ khác không? Có tài liệu mô tả định dạng không? Có tương thích với xdelta/VCDIFF/RFC 3284 không?

Answer 1

Tôi nghĩ rằng algo khác được sử dụng cho pack files được liên kết với một trong số delta encoding trên mạng: initially (2005) xdelta và sau đó libXDiff.
Nhưng sau đó, như chi tiết bên dưới, nó chuyển sang triển khai tùy chỉnh.

Dù sao, như mentioned here:

Git làm deltification chỉ trong packfiles.
Nhưng khi bạn đẩy thông qua SSH git sẽ tạo ra một tập tin gói với cam kết phía bên kia không có, và những gói là gói mỏng, vì vậy họ cũng có deltas ... nhưng phía xa sau đó thêm cơ sở cho những mỏng gói làm cho chúng độc lập.

(lưu ý:. Tạo nhiều packfiles, hoặc lấy thông tin trong packfile khổng lồ là tốn kém, và giải thích lý do tại sao git không xử lý file cũng lớn hoặc repo khổng lồ
Xem thêm tại "git with large files")

This thread cũng nhắc nhở chúng ta:

Trên thực tế packfiles và deltification (LibXDiff, không xdelta) là, từ những gì tôi nhớ và u nderstand, ban đầu do băng thông mạng (tốn kém hơn nhiều so với dung lượng đĩa) và Hiệu suất I/O sử dụng tệp mmapped đơn lẻ thay vì số lượng lớn các đối tượng lỏng lẻo.

LibXDiff được đề cập trong số 2008 thread này.

Tuy nhiên, kể từ đó, các algo đã phát triển, có lẽ trong một tùy chỉnh một, như 2011 thread illustrates này, và như tiêu đề của diff-delta.c chỉ ra:

Vì vậy, nói đúng ra, các mã hiện trong Git không có bất kỳ sự tương đồng nào với mã libxdiff cả.
Tuy nhiên, thuật toán cơ bản đằng sau cả hai triển khai là giống nhau.
Nghiên cứu phiên bản libxdiff có lẽ dễ dàng hơn để hiểu được cách thức hoạt động của phiên bản này.

/* 
* diff-delta.c: generate a delta between two buffers 
* 
* This code was greatly inspired by parts of LibXDiff from Davide Libenzi 
* http://www.xmailserver.org/xdiff-lib.html 
* 
* Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007 
*/ 

Thông tin thêm về các packfiles the Git Book:

Answer 2

Git mã hóa đồng bằng là sao chép/chèn dựa.

Điều này có nghĩa là tệp dẫn xuất được mã hóa dưới dạng chuỗi mã có thể đại diện cho các hướng dẫn sao chép (ví dụ: sao chép từ byte cơ sở y byte bắt đầu từ offset x vào bộ đệm đích) hoặc chèn hướng dẫn (ví dụ: chèn x byte tiếp theo vào bộ đệm đích).

Như một ví dụ rất đơn giản (lấy từ 'Hỗ trợ File System cho Delta Compression' giấy), hãy xem xét mà chúng tôi muốn tạo ra một bộ đệm đồng bằng để chuyển đổi văn bản "proxy     bộ nhớ cache" vào "bộ nhớ cache     Proxy ". Các hướng dẫn kết quả nên là:

1. Sao chép 5 byte từ bù đắp 7 ('Cache' bản sao từ đệm cơ sở)
2. Chèn hai không gian
3. Sao chép 5 byte từ offset 0 (bản sao 'proxy' từ cơ sở đệm)

nào dịch sang của git mã hóa trở thành:

(byte 1-3 đại diện cho hướng dẫn đầu tiên)

• 0x91 (10.010.001), được chia thành
  • 0x80 (10000000) (bit thiết lập quan trọng nhất làm cho điều này 'bản sao từ cơ sở để đầu ra' hướng dẫn)
  • 0x01 (00000001) (có nghĩa là 'trước một byte và sử dụng nó như là cơ sở bù đắp)
  • 0x10 (00.010.000) (trước một byte và sử dụng nó như chiều dài)
• 0x07 (offset)
• 0x05 (chiều dài)

(byte 4-6 đại diện cho hướng dẫn thứ hai)

• 0x02 (từ MSB không được thiết lập, điều này có nghĩa 'chèn hai byte tiếp theo vào đầu ra')
• 0x20 (không gian)
• 0x20 (không gian)

(byte 7-8 đại diện cho hướng dẫn cuối cùng)

• 0x90 (10010000), được chia thành
  • 0x80 (10000000) (có nghĩa là 'bản sao')
  • 0x10 (00.010.000) (trước một byte và sử dụng nó như chiều dài)
• 0x05 (chiều dài)

Chú ý rằng trong hướng dẫn bản sao cuối cùng không chỉ định một bù đắp có nghĩa là bù đắp 0. bit khác trong opcode bản cũng có thể được thiết lập khi offsets lớn hơn/độ dài là cần thiết.Bộ đệm delta kết quả có trong ví dụ này có 8 byte, không nhiều nén vì bộ đệm đích có 12 byte, nhưng khi mã hóa này áp dụng cho tệp văn bản lớn, nó có thể tạo sự khác biệt lớn.

Gần đây tôi đã đẩy node.js library vào github thực hiện cả hai chức năng diff/patch sử dụng mã hóa git delta. code phải dễ đọc hơn và được nhận xét hơn so với mã nguồn git, được tối ưu hóa nhiều.

Tôi cũng đã viết một số tests giải thích các opcodes đầu ra được sử dụng trong mỗi ví dụ có định dạng tương tự như trên.

Answer 3

Thuật toán này có được chuẩn hóa và sử dụng trong các công cụ khác không?

Định dạng gói là một phần của API công khai: giao thức truyền được sử dụng cho hoạt động đẩy và tìm nạp sử dụng nó để gửi ít dữ liệu hơn qua mạng.

Chúng được triển khai trong ít nhất hai triển khai Git chính khác ngoài tham chiếu: JGit và libgit2.

Do đó, rất ít khả năng sẽ có các thay đổi không tương thích ngược với định dạng và có thể được coi là "chuẩn hóa" theo nghĩa đó.

này tập tin tuyệt vời từ các tài liệu mô tả các công nghệ tự động sử dụng trong thuật toán gói như một lời bình luận hài hước trong email Linus: https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics.txt