6 ms·

> GIT is already best model for keeping history of textual changes No it’s not. Git isn’t a model of textual changes. It’s just a model of textual snapshots co

> GIT is already best model for keeping history of textual changes No it’s not. Git isn’t a model of textual changes. It’s just a model of textual snapshots connected over time. If I were building a replacement for git, it would store character by character changes instead - though for that to work properly you’d want editor integration. Then the same tool could act as both a version control system and as a platform for realtime collaborative editing (via CRDTs). You can still have commits - they’re essentially just tags. And I’d keep the concept of branches. Most of the algorithmic work has already been done - at least from the CS research side. Combine my work in diamond types with some of Martin Kleppmann’s work on BFT CRDTs & automerge. There’s a few more tricks needed. For example, you don’t want a hash on disk per keystroke. I’ve figured out a nice answer for that but haven’t written it up yet. Deleting data is an unsolved problem. For example, if someone accidentally pastes in a password you need a way to prune it from the history. And async merges probably want to emit conflicts - which nobody has done on top of CRDTs yet as far as I know. If I were building it, I’d also throw in a simple crdt based data store, synced over the same protocol. Then we could also store GitHub issues and other stuff inside the repository itself (a la fossil). CRDTs resolve conflicts better than git ever will, because they have access to more information than git does about what happened. It’d be a pretty cool model. Definitely worthy as a successor to git in my opinion.

sillysaurusx 3y ago
Why?
jerf 3y ago
I can see why in your head that may look like a successor to git, but the... news... be it good news or bad news for you... is that everything you've described is actually almost entirely orthogonal to git. When researching the question of "Why did X occur?", I absolutely, positively, beyond a shadow of a doubt, do not want to filter through literally hours of keystroke-by-keystroke data. I need some sort of indication as to what states are worth looking at. Those are commits. Whatever further thing you may want to say about them, like "well, whenever the tests all pass we'll add a checkpoint", well, you can do that today. If you don't, it's either because you haven't thought of it, or the resulting multiplicity of commits is already too much to deal with. Moreover, just having a CRDT history of keystrokes is an inadequate data structure for many things people do in git all the time. Merging a branch based on keystrokes is crazy; all you end up with is more opportunities for conflicts than the current system has. You think more information is good, I suspect in practice it would actually be bad. Git has no problem merging things where five people were working on a given repo at the same physical time, but on different things; a CRDT model would have to do weird things to have a sensible merged view after that, because a CRDT system is concerned with creating the final document; a source control system needs a human-meaningful history as well. (You can't just interleave their work, because the result moment-by-moment view would never make any sense. You can keep track by a branching mechanism where you can only go down one of their work path, but the natural implementation of that would have to not have the other branches available either. The problems go on; you actually end up with a much less flexible approach to slicing & dicing code without a lot more work, which is quite likely PhD-level work, assuming it's even possible.) Rebasing, if you are OK with it, effectively breaks CRDTs as you observe (it's the same basic issue as deleting something). CRDTs may effectively handle offline work getting merged back into the "main" online view but what CRDT setup is designed for browsing through history, and potentially pulling things back out of it? I think if you actually tried to manifest this as the root level of a version control system you'd rapidly find it is full of problems, both theoretical and practical. However, you could adjoin these capabilities to something like Git (or Fossil or Mercurial or whatever, I don't much care which). It's just instead of trying to build a single CRDT history that goes all the way back to the beginning of the repo, you adjoin a CRDT representation to commits, but allow each commit to serve as the base of a series of CRDT transactions on its own terms. So a merged or rebased commit could still be traced back to its original, which would contain all your information that you're looking for, but the general manipulations of commits would still look like a current system. IIRC, git allows you to stick arbitrary metadata on to commits which can themselves be blobs, so if you have an editoring system that can emit CRDT information from an edit stream, you could prototype this right now with a bit of wrapping around Git (or, again, any other source control that has that capability) that adds the CRDT stream as metadata to the commit. Get a feel for how it works, see if it is as useful as you think, and then if it is, you can go forth to prove the rest of my message wrong by trying to build something where it's the base abstraction instead of an adjunct. I would also encourage you with the fact that Linus wrote the first, useful version of git very quickly. A slick, polished source control system is a big task, but a source control system, one that mostly works, may ignore some corner cases, doesn't have any handling for symlinks, punts on file system case differences, probably has O(n^2) algorithms that break if you try to stuff it full of gigabytes, is covered with disclaimers to store no real data in it yet because it may break, etc., is actually not too hard. Proving my skepticism wrong via prototype is not necessarily that difficult.
- jajko 3y ago
  Man, just a polite friendly advice, whatever message you are trying to convey would be 10x more efficient if you cut word count to maybe 10%. Few want to read small novels in discussions.
- lowercased 3y ago
  > I need some sort of indication as to what states are worth looking at. Those are commits. I would welcome some tool that could guess/infer where some commit points should be, even if I didn't explicitly commit at those points. I often tend to jump about between files when debugging/tracing a problem, making some changes here and there, then... when it's fixed... I don't always have a good frame of mind to commit as cleanly as I'd like. Something that could try to group changes together - by function, or type of change, etc - and propose those commits would be helpful. I've not tried some of the coding AI tools in that respect - maybe they do that now? I've only ever read about "they can write good commit messages for you!" as a selling point.
- josephg 3y ago
  As I said above, I imagine keeping commits. Think of them like checkpoints in a race. Any typed character will be between two commits - so git log and git blame can still work just fine. They just operate on a different data structure internally. Merging is also fine. How do you think CRDTs work? You know merging is the entire point, right? I agree that the system needs to handle both synchronous edits (peer programming) and asynchronous edits (the kind of editing we do now with git). CRDTs can handle separate concurrent branches just fine. It’s just none of the existing crdt libraries support branches. You’re right that rebase is weird in CRDTs, but I think we can still build it if we need to. Rebase is mostly used in git to work around one of git’s design flaws: Git is never sure if commits should represent the actual history of changes, or the semantic history of merged tickets. But a better system could just separate those ideas anyway. Yes, it is a PhD level problem right now. But so was diff-match-patch a few years ago. I’m an expect in this field. And I believe we now know how to solve all the sub problems here - all but one: how do we actively generate conflicts from asynchronous edits in a crdt? That needs to be figured out first.
  - 3y ago
taeric 3y ago
Character by character changes is almost certainly too low level. I understand wanting symbol by symbol. Heck, I even understand pulling it up the abstraction ladder and look at it at the semantic level. Having a diff of the form, "variable name changed, conditional added, etc" looks magical. I recall seeing some good demos of tools that could do this. Unfortunately, none of these efforts have ever panned out. I cannot claim that they are unable to work, but they have not done so, yet. And I'm not clear on why that we think they will. From evidence I have seen, there is no magic data structure that can help resolve conflicts. Pretty much period. The only algorithm that always works is to bounce it back to a user. With LLMs gaining in power, I suppose you could lean on one of them for the first non-mechanical pass? Which sucks, because quite frankly CRDT and friends are fun data structures. But, they make the easy and trivial cases much much harder. Which is why a series of snapshots is far more effective. Those snapshots are not for the convenience of the tool tracking changes. They are for the convenience of every other tool that you are using.
- josephg 3y ago
  > From evidence I have seen, there is no magic data structure that can help resolve conflicts. Pretty much period. CRDTs (and similar algorithms) can do a whole lot better than git does today. They simply have more information to work with about what changed, and where. Git has to reconstruct that from re-diffing snapshots - which is always a lossy process. It hasn’t been done because until recently (the last few years), CRDTs were considered too slow for practical use. It’s just recently that we as a species figured out how to make them fast and lightweight.
  - taeric 3y ago
    I feel you are slightly cheating on this, though. I'll explain. If you are only storing snapshots, I worry that you actually cannot do better. If you are willing to store the snapshots as either a list of operations from the last state, or you can decompose state changes to something coherent, then you can maybe do better. That is, the cheat, I feel, is that most of what anyone does with anything from source control, is to work with the snapshot. Building a diff between trees is surprisingly rarely done. Yes, you see the reconstruction of one every time you run `git log -p`, but by and large, that is not what you work with. (And this is ignoring that you often want to see the diff between two tree heads...) Now, you seem to be pushing to change this and to have people always work with the CRDT for everything they do? Does this not push it so that the source control now becomes something that every editing tool in use has to also work with it? Aside, I'm also not at all clear that CRDTs have gotten to the point that they can do octopus merges at a reliable rate. More, I'm not clear on what merges actually look like with CRDTs, in a source control sense. Happy to see any reading, if you have a link.
riskable 3y ago
> If I were building a replacement for git... The biggest problem with git is anything that isn't just text (e.g. binary files). What's needed is a source control system that understands binary file formats well enough that it is capable of producing a user (developer) friendly diff. For example, if git understood PNG you could do a diff on two versions of that PNG and it would show you that e.g. a color was changed or a TM symbol was added or similar. I think git will be with us for a long time but whatever replaces it will be able to handle binary diffs in an intelligent way. Probably with AI-generated summaries. Even then it might still be git... Just an improved version.
- andrewla 3y ago
  Agreed -- the problem with binary files is twofold; one is a storage issue and the other is a presentation issue. Both are solvable without having to violate git's fundamental data structures. If a png is stored in a repository and changed, then logically the repository contains two snapshots identified by hash. When a user tool (or git itself) wants to display the diff, it can be as creative as it wants in figuring out how to render that diff, including understanding file formats. When git itself wants to store the two images, it has to do so with bitwise fidelity. Nonetheless, as with text files, it is totally possible for it to represent it internally as a delta-compressed view of the file, which, for an image file format, might be more compactly represented than by looking at the binary difference between the files. So long as this can be done deterministically and reproducibly, this is something that can make storage of large files more compact over time.
ozim 3y ago
I don’t see how character by character changes are an improvement. The same with handling image files. Both of these “downsides” don’t make sense for me. I make set of changes that make sense, if character change makes sense to be historically relevant I make a commit. Yes it is a lot of work but I make choice what is relevant and what is not and put it in a commit. (changing text layout and white paces can be relevant on its own ;)) On the other hand I fail to see how bit level changes of an image makes a difference. Image is all or nothing the same executable file. Patching parts is 99% of time not relevant or simply not something people do or care about.
andrewla 3y ago
Logically, yes, git is a list of snapshots over time. There are two issues that you touch on here, though. One is data storage. There is nothing stopping git from storing those snapshots as deltas from previous snapshots, so long as it is able to reproduce the tree at any point in time with bitwise fidelity. Already, internally, git will store deltas to compress the store instead of storing content for each changed file. And at display time, it can make inferences about what has changed between two snapshots. So over time history gets "better" as it tracks file and line moves better just by making better heuristics around how to present changes to the user. The main defect you point out is the immutability of history, especially when it comes to deleting history. I don't really have an answer for that, and I'm not sure that this is a solvable problem when you have a distributed version control system -- no matter how much you try to purge something, someone somewhere can have a copy of the unpurged repository so the idea of a definitive "delete" sounds incompatible with a distributed vcs.

sillysaurusx 3y ago

Why?

jerf 3y ago

I can see why in your head that may look like a successor to git, but the... news... be it good news or bad news for you... is that everything you've described is actually almost entirely orthogonal to git. When researching the question of "Why did X occur?", I absolutely, positively, beyond a shadow of a doubt, do not want to filter through literally hours of keystroke-by-keystroke data. I need some sort of indication as to what states are worth looking at. Those are commits. Whatever further thing you may want to say about them, like "well, whenever the tests all pass we'll add a checkpoint", well, you can do that today. If you don't, it's either because you haven't thought of it, or the resulting multiplicity of commits is already too much to deal with. Moreover, just having a CRDT history of keystrokes is an inadequate data structure for many things people do in git all the time. Merging a branch based on keystrokes is crazy; all you end up with is more opportunities for conflicts than the current system has. You think more information is good, I suspect in practice it would actually be bad. Git has no problem merging things where five people were working on a given repo at the same physical time, but on different things; a CRDT model would have to do weird things to have a sensible merged view after that, because a CRDT system is concerned with creating the final document; a source control system needs a human-meaningful history as well. (You can't just interleave their work, because the result moment-by-moment view would never make any sense. You can keep track by a branching mechanism where you can only go down one of their work path, but the natural implementation of that would have to not have the other branches available either. The problems go on; you actually end up with a much less flexible approach to slicing & dicing code without a lot more work, which is quite likely PhD-level work, assuming it's even possible.) Rebasing, if you are OK with it, effectively breaks CRDTs as you observe (it's the same basic issue as deleting something). CRDTs may effectively handle offline work getting merged back into the "main" online view but what CRDT setup is designed for browsing through history, and potentially pulling things back out of it? I think if you actually tried to manifest this as the root level of a version control system you'd rapidly find it is full of problems, both theoretical and practical. However, you could adjoin these capabilities to something like Git (or Fossil or Mercurial or whatever, I don't much care which). It's just instead of trying to build a single CRDT history that goes all the way back to the beginning of the repo, you adjoin a CRDT representation to commits, but allow each commit to serve as the base of a series of CRDT transactions on its own terms. So a merged or rebased commit could still be traced back to its original, which would contain all your information that you're looking for, but the general manipulations of commits would still look like a current system. IIRC, git allows you to stick arbitrary metadata on to commits which can themselves be blobs, so if you have an editoring system that can emit CRDT information from an edit stream, you could prototype this right now with a bit of wrapping around Git (or, again, any other source control that has that capability) that adds the CRDT stream as metadata to the commit. Get a feel for how it works, see if it is as useful as you think, and then if it is, you can go forth to prove the rest of my message wrong by trying to build something where it's the base abstraction instead of an adjunct. I would also encourage you with the fact that Linus wrote the first, useful version of git very quickly. A slick, polished source control system is a big task, but a source control system, one that mostly works, may ignore some corner cases, doesn't have any handling for symlinks, punts on file system case differences, probably has O(n^2) algorithms that break if you try to stuff it full of gigabytes, is covered with disclaimers to store no real data in it yet because it may break, etc., is actually not too hard. Proving my skepticism wrong via prototype is not necessarily that difficult.

jajko 3y ago
Man, just a polite friendly advice, whatever message you are trying to convey would be 10x more efficient if you cut word count to maybe 10%. Few want to read small novels in discussions.
lowercased 3y ago
> I need some sort of indication as to what states are worth looking at. Those are commits. I would welcome some tool that could guess/infer where some commit points should be, even if I didn't explicitly commit at those points. I often tend to jump about between files when debugging/tracing a problem, making some changes here and there, then... when it's fixed... I don't always have a good frame of mind to commit as cleanly as I'd like. Something that could try to group changes together - by function, or type of change, etc - and propose those commits would be helpful. I've not tried some of the coding AI tools in that respect - maybe they do that now? I've only ever read about "they can write good commit messages for you!" as a selling point.
josephg 3y ago
As I said above, I imagine keeping commits. Think of them like checkpoints in a race. Any typed character will be between two commits - so git log and git blame can still work just fine. They just operate on a different data structure internally. Merging is also fine. How do you think CRDTs work? You know merging is the entire point, right? I agree that the system needs to handle both synchronous edits (peer programming) and asynchronous edits (the kind of editing we do now with git). CRDTs can handle separate concurrent branches just fine. It’s just none of the existing crdt libraries support branches. You’re right that rebase is weird in CRDTs, but I think we can still build it if we need to. Rebase is mostly used in git to work around one of git’s design flaws: Git is never sure if commits should represent the actual history of changes, or the semantic history of merged tickets. But a better system could just separate those ideas anyway. Yes, it is a PhD level problem right now. But so was diff-match-patch a few years ago. I’m an expect in this field. And I believe we now know how to solve all the sub problems here - all but one: how do we actively generate conflicts from asynchronous edits in a crdt? That needs to be figured out first.
- 3y ago

taeric 3y ago

Character by character changes is almost certainly too low level. I understand wanting symbol by symbol. Heck, I even understand pulling it up the abstraction ladder and look at it at the semantic level. Having a diff of the form, "variable name changed, conditional added, etc" looks magical. I recall seeing some good demos of tools that could do this. Unfortunately, none of these efforts have ever panned out. I cannot claim that they are unable to work, but they have not done so, yet. And I'm not clear on why that we think they will. From evidence I have seen, there is no magic data structure that can help resolve conflicts. Pretty much period. The only algorithm that always works is to bounce it back to a user. With LLMs gaining in power, I suppose you could lean on one of them for the first non-mechanical pass? Which sucks, because quite frankly CRDT and friends are fun data structures. But, they make the easy and trivial cases much much harder. Which is why a series of snapshots is far more effective. Those snapshots are not for the convenience of the tool tracking changes. They are for the convenience of every other tool that you are using.

josephg 3y ago
> From evidence I have seen, there is no magic data structure that can help resolve conflicts. Pretty much period. CRDTs (and similar algorithms) can do a whole lot better than git does today. They simply have more information to work with about what changed, and where. Git has to reconstruct that from re-diffing snapshots - which is always a lossy process. It hasn’t been done because until recently (the last few years), CRDTs were considered too slow for practical use. It’s just recently that we as a species figured out how to make them fast and lightweight.
- taeric 3y ago
  I feel you are slightly cheating on this, though. I'll explain. If you are only storing snapshots, I worry that you actually cannot do better. If you are willing to store the snapshots as either a list of operations from the last state, or you can decompose state changes to something coherent, then you can maybe do better. That is, the cheat, I feel, is that most of what anyone does with anything from source control, is to work with the snapshot. Building a diff between trees is surprisingly rarely done. Yes, you see the reconstruction of one every time you run `git log -p`, but by and large, that is not what you work with. (And this is ignoring that you often want to see the diff between two tree heads...) Now, you seem to be pushing to change this and to have people always work with the CRDT for everything they do? Does this not push it so that the source control now becomes something that every editing tool in use has to also work with it? Aside, I'm also not at all clear that CRDTs have gotten to the point that they can do octopus merges at a reliable rate. More, I'm not clear on what merges actually look like with CRDTs, in a source control sense. Happy to see any reading, if you have a link.

riskable 3y ago

> If I were building a replacement for git... The biggest problem with git is anything that isn't just text (e.g. binary files). What's needed is a source control system that understands binary file formats well enough that it is capable of producing a user (developer) friendly diff. For example, if git understood PNG you could do a diff on two versions of that PNG and it would show you that e.g. a color was changed or a TM symbol was added or similar. I think git will be with us for a long time but whatever replaces it will be able to handle binary diffs in an intelligent way. Probably with AI-generated summaries. Even then it might still be git... Just an improved version.

andrewla 3y ago
Agreed -- the problem with binary files is twofold; one is a storage issue and the other is a presentation issue. Both are solvable without having to violate git's fundamental data structures. If a png is stored in a repository and changed, then logically the repository contains two snapshots identified by hash. When a user tool (or git itself) wants to display the diff, it can be as creative as it wants in figuring out how to render that diff, including understanding file formats. When git itself wants to store the two images, it has to do so with bitwise fidelity. Nonetheless, as with text files, it is totally possible for it to represent it internally as a delta-compressed view of the file, which, for an image file format, might be more compactly represented than by looking at the binary difference between the files. So long as this can be done deterministically and reproducibly, this is something that can make storage of large files more compact over time.

ozim 3y ago

I don’t see how character by character changes are an improvement. The same with handling image files. Both of these “downsides” don’t make sense for me. I make set of changes that make sense, if character change makes sense to be historically relevant I make a commit. Yes it is a lot of work but I make choice what is relevant and what is not and put it in a commit. (changing text layout and white paces can be relevant on its own ;)) On the other hand I fail to see how bit level changes of an image makes a difference. Image is all or nothing the same executable file. Patching parts is 99% of time not relevant or simply not something people do or care about.

andrewla 3y ago

Logically, yes, git is a list of snapshots over time. There are two issues that you touch on here, though. One is data storage. There is nothing stopping git from storing those snapshots as deltas from previous snapshots, so long as it is able to reproduce the tree at any point in time with bitwise fidelity. Already, internally, git will store deltas to compress the store instead of storing content for each changed file. And at display time, it can make inferences about what has changed between two snapshots. So over time history gets "better" as it tracks file and line moves better just by making better heuristics around how to present changes to the user. The main defect you point out is the immutability of history, especially when it comes to deleting history. I don't really have an answer for that, and I'm not sure that this is a solvable problem when you have a distributed version control system -- no matter how much you try to purge something, someone somewhere can have a copy of the unpurged repository so the idea of a definitive "delete" sounds incompatible with a distributed vcs.