4 ms·

A very interesting idea, GitTorrent, but I have one question which comes to me whenever I read about a delta-based distribution scheme: who is going to generate

A very interesting idea, GitTorrent, but I have one question which comes to me whenever I read about a delta-based distribution scheme: who is going to generate and share all those deltas? Some Linux distributions have experimented with delta-based package repositories, examples are deltup for Arch Linux and rpm-delta for RPM-based distros. Some of the known issues are: - choosing the number and spacing between deltas. Fine-grained deltas require more storage space, coarse-grained deltas require more download bandwidth. - retiring old deltas: periodically deleting all deltas older than a certain version, replacing them with the full package of that version. Again a trade-off between storage space and download bandwidth. For Git repositories, this would roughly translate to: - choosing the number, history spacing, and size of the Git packs per repository. - retiring old Git packs: periodically deleting Git packs older than a particular revision, replacing them with a bare repository at that revision.

pjc50 11y ago
Git is built out of deltas. You're already storing all of them.
- ackalker 11y ago
  The problem is not with deltas between revisions (i.e. the commits themselves) but with the Git packs spanning multiple revisions. At the time of a `git pull`, a user's repository can be at any revision between initial and latest. Who is going to seed (and keep seeding) packs for all of those possible revision intervals?
- deleted 11y ago
  [deleted]
- peterwaller 11y ago
  This is isn't quite how I would describe it. Git does do delta compression in packfiles, but the fundamental primitives lack deltas. It's just: * The contents of this directory is this list of of files whose contents have these SHAs. This is called a "tree". The SHA of a tree is also an object, and can appear in another tree. To see this for yourself, in any git repository run `git cat-file -p HEAD`. You'll see the (more or less) raw commit object for HEAD, which will point at a tree SHA. To see the contents of that tree-sha, run `git cat-file -p <the tree SHA>`. That tree object has a one-to-one correspondence with what you'll see on-disk in the objects directory, (if the object has not been put in a pack file). Above I have more or less fully described the contents of the files found in `.git/objects`. The delta'ing doesn't happen until later, if and when packfiles are constructed. But they're just a storage/bandwidth optimisation. AFAICT, these deltas have nothing to do with what you might think of as "git diff", which is just some fancy porcelain which looks at objects. The nice property of the construction is that given a large tree, even if nested, if you change a single file in that tree, you will only change as many trees as the file is deep in the tree, so computing changes between two nearby trees can usually be done quickly.
- qznc 11y ago
  Conceptually, git is built out of snapshots.
yellowapple 11y ago
My impression was that peers are generating the deltas on-the-fly based on which commits the requesting peer states it needs. The problem's therefore shoved onto git itself, with the seeder just cherry-picking a specific range of commits from its own copy of the repo and bundling them together.
- ackalker 11y ago
  Ah, okay, but that would imply that GitTorrent doesn't make any use of the swarming capability which makes BitTorrent special. Not using swarming brings back all of the old problems of NAT traversal, asymmetric upload/download bandwidth, throttling, censorship etc.
  - cjbprime 11y ago
    Not quite: the peer generates the pack and tells you its hash, and then you query the network for anyone who has that hash (them, for starters), and perform a swarming download of it. So git clones of popular repositories would usually swarm.
    - tottenhm 11y ago
      The probability of swarming would be influenced by multiple factors, eg * Higher popularity => More peers => Higher probability that multiple peers want the same packfiles. * Higher popularity => More commits => More permutations of packfiles => Lower probability that multiple peers want the same packfiles (and stronger trends toward small/inefficient packfiles). * More frequent synchronizations (peers always online) => More immediacy => Smaller packfiles => Higher probability that multiple peers want the same packfiles. * Less frequent synchronizations (peers go offline regularly) => Less immediacy => Bigger packfiles => Lower probability that multiple peers want the same packfiles. It would be really interesting to see how these competing pressures play-out (either by doing some math or randomized experiments). If the main goal here is strictly decentralization (without concern for performance or availability[F1]), then one might look at swarming as a nice-to-have behavior which only happens in some favorable circumstances. However, by latching onto the "torrent" brand, I think you setup some expectations for swarming/performance/availability. ([F1] Availability: If Seed-1 recommends a certain packfile, then the only peer which is guaranteed to have that packfile is Seed-1 -- even if there are many seeds with a full git history. If Seed-1 goes offline while transmitting that packfile, how could a leech continue the download from Seed-2? The #seeds wouldn't intuitively describe the reliability of the swarm... unless one adds some special-case logic to recover from unresolvable packfiles.) --- Could this be mitigated with some constraints on how peers delineate packfiles?

pjc50 11y ago

Git is built out of deltas. You're already storing all of them.

ackalker 11y ago
The problem is not with deltas between revisions (i.e. the commits themselves) but with the Git packs spanning multiple revisions. At the time of a `git pull`, a user's repository can be at any revision between initial and latest. Who is going to seed (and keep seeding) packs for all of those possible revision intervals?
deleted 11y ago
[deleted]
peterwaller 11y ago
This is isn't quite how I would describe it. Git does do delta compression in packfiles, but the fundamental primitives lack deltas. It's just: * The contents of this directory is this list of of files whose contents have these SHAs. This is called a "tree". The SHA of a tree is also an object, and can appear in another tree. To see this for yourself, in any git repository run `git cat-file -p HEAD`. You'll see the (more or less) raw commit object for HEAD, which will point at a tree SHA. To see the contents of that tree-sha, run `git cat-file -p <the tree SHA>`. That tree object has a one-to-one correspondence with what you'll see on-disk in the objects directory, (if the object has not been put in a pack file). Above I have more or less fully described the contents of the files found in `.git/objects`. The delta'ing doesn't happen until later, if and when packfiles are constructed. But they're just a storage/bandwidth optimisation. AFAICT, these deltas have nothing to do with what you might think of as "git diff", which is just some fancy porcelain which looks at objects. The nice property of the construction is that given a large tree, even if nested, if you change a single file in that tree, you will only change as many trees as the file is deep in the tree, so computing changes between two nearby trees can usually be done quickly.
qznc 11y ago
Conceptually, git is built out of snapshots.

yellowapple 11y ago

My impression was that peers are generating the deltas on-the-fly based on which commits the requesting peer states it needs. The problem's therefore shoved onto git itself, with the seeder just cherry-picking a specific range of commits from its own copy of the repo and bundling them together.

ackalker 11y ago
Ah, okay, but that would imply that GitTorrent doesn't make any use of the swarming capability which makes BitTorrent special. Not using swarming brings back all of the old problems of NAT traversal, asymmetric upload/download bandwidth, throttling, censorship etc.
- cjbprime 11y ago
  Not quite: the peer generates the pack and tells you its hash, and then you query the network for anyone who has that hash (them, for starters), and perform a swarming download of it. So git clones of popular repositories would usually swarm.
  - tottenhm 11y ago
    The probability of swarming would be influenced by multiple factors, eg * Higher popularity => More peers => Higher probability that multiple peers want the same packfiles. * Higher popularity => More commits => More permutations of packfiles => Lower probability that multiple peers want the same packfiles (and stronger trends toward small/inefficient packfiles). * More frequent synchronizations (peers always online) => More immediacy => Smaller packfiles => Higher probability that multiple peers want the same packfiles. * Less frequent synchronizations (peers go offline regularly) => Less immediacy => Bigger packfiles => Lower probability that multiple peers want the same packfiles. It would be really interesting to see how these competing pressures play-out (either by doing some math or randomized experiments). If the main goal here is strictly decentralization (without concern for performance or availability[F1]), then one might look at swarming as a nice-to-have behavior which only happens in some favorable circumstances. However, by latching onto the "torrent" brand, I think you setup some expectations for swarming/performance/availability. ([F1] Availability: If Seed-1 recommends a certain packfile, then the only peer which is guaranteed to have that packfile is Seed-1 -- even if there are many seeds with a full git history. If Seed-1 goes offline while transmitting that packfile, how could a leech continue the download from Seed-2? The #seeds wouldn't intuitively describe the reliability of the swarm... unless one adds some special-case logic to recover from unresolvable packfiles.) --- Could this be mitigated with some constraints on how peers delineate packfiles?