Comment by brendoncarroll
4 years ago
This is a very similar to one of my projects "Got".
The algorithms it uses are superior to rsync and git in a few ways. It comes short on features, especially for software development compared to Git. The motivation is more for personal file storage.
I notice you're using Go and AGPL licensed, so you could borrow any of Got's libraries without issue. (Got is GPL licensed.) Definitely reach out in a GitHub issue.
"The algorithms it uses are superior to rsync and git in a few ways." - Would you mind explaining this?
Sure, Git stores data in a trie. Each file is one blob identified by hash, and directories (called trees in Git) are blobs where each line is a directory entry with a name and the hash of a file or another tree. This means that modifying an object /down/a/long/path/like/this.txt has to create copies of all the trees on the way up. The technical term for this is "write amplification", and in Git it is affected by path length among other things.
Got stores data in a probabilistic tree (GotKV[0]). The number of nodes before you get to data will scale logarithmically with the size of the entire filesystem, not the depth of a specific object.
Then there is the issue of large files. A file in Git is always 1 blob. Syncing a large blob is not easy because if you are interrupted and have to restart, you have lost all your progress. You can't verify the hash of a blob until you have the whole thing. Got has a maximum blob size, so you'll only be buffering <2MB at a time before you can verify that the blob is correct. If a transfer is interrupted, the most you'll have to repeat is one blobs worth, plus any tree nodes above that blob.
Compared to rsync, Got uses variable size chunks and a faster content defined chunking algorithm, recently featured here on HN[1]. I haven't thought about if variable vs fixed chunks is better for file transfer, but for version control, the higher chance of convergence is important. It means you have better deduplication.
[0] https://news.ycombinator.com/item?id=34303497
I've not heard the term "probabilistic tree" and I've having difficulty pulling up references. I suspect it's implemented by subpackage ptree[0]. Could you explain what makes probabilistic trees different from hash tables or other similar data structures?
[0] https://github.com/gotvc/got/tree/master/pkg/gotkv/ptree
5 replies →
This is the awesome content I still come to HN for. Thanks for the post and good luck with Got.
Thank you for such a detailed response!
FYI: "got" is also the name of the OpenBSD re-implementation of git (supposedly, an acronym, "game of trees"): https://gameoftrees.org/
in the game of trees you either live, or branch
Ah awesome! I'll check this out
Took a look and this is really cool. Will definitely keep this is mind. One major difference and area I'm focused on in this project is hosting. I would argue that there are currently much better VCS options for projects than Git (like yours and Fossil) but the reason these haven't taken off is that Github and Gitlab offer unmatched hosting and collaboration tools for these projects. Would be curious to know your thoughts/approach to this!
My approach to hosting with Got has been to make it easy and secure for users to host from any machine.
INET256 solves that problem nicely. If you have access to an INET256 network, then all you have to do is swap addresses and two Got instances can communicate.
https://github.com/inet256/inet256
Also, end-to-end encryption is table stakes. Any data that leaves the user needs to be encrypted in transit, and if it hangs around away from the user, at rest.