{"thread":{"id":"37007","subject":"Tackling Git Limitations with Singular Large Line-seperated Plaintext files","startedAt":"2014-06-27T08:45:16Z","lastAt":"2014-08-10T21:45:34Z","messageCount":10,"participants":["Jarrad Hope","Shawn Pearce","Junio C Hamano","Linus Torvalds","Jason Pyeron","Jakub Narębski","Øyvind A. Holm"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"245060","messageId":"CAJoVafc1LMxmvCiWci3N+AuAZBsABR3Wb3c6c3stw93OJZ7Scw@mail.gmail.com","threadId":"37007","inReplyTo":null,"subject":"Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Jarrad Hope","fromEmail":"me@jarradhope.com","sentAt":"2014-06-27T08:45:16Z","receivedAt":"2014-06-27T08:45:16Z","isPatch":false,"sender":{"key":"me@jarradhope.com","avatar":null},"body":"Hello,\n\nAs a software developer I've used git for years and have found it the\nperfect solution for source control.\n\nLately I have found myself using git in a unique use-case - modifying\nDNA/RNA sequences and storing them in git, which are essentially\nsoftware/source code for cells/life. For Bacteria and Viruses the\nrepo's are very small <10mb & compress nicely.\n\nHowever on the extreme end of the spectrum a human genome can run in\nat 50gb or say ~1gb per file/chromosome.\n\nNow, this is not the binary problem and it is not the same as storing\nmedia inside git - I have reviewed the solutions that exist for the\nbinary problem, such as git-annex, git-media & bup. But they don't\nprovide the featureset of git and the data i'm storing is more like\nplaintext sourcecode with relatively small edits per commit.\n\nI have googled and asked in #git which discussion mostly revolved\naround these tools.\n\nThe only project that holds interest is a 2009 project, git-bigfiles -\nhowever it is abit dated & the author is not interested in reviving\nthis project - referring me to git-annex. Unfortunately.\n\nWith that background;\nI wanted to discuss the problems with git and how I can contribute to\nthe core project to best solve them.\n\n>From my understanding the largest problem revolves around git's delta\ndiscovery method, holding 2 files in memory at once - is there a\nreason this could not be adapted to page/chunk the data in a sliding\nwindow fashion ?\n\nAre there any other issues I need to know about, is anyone else\nworking on making git more capable of handling large source files that\nI can collaborate with?\n\nThanks for your time,\nJarrad\n"},{"id":"245076","messageId":"CAJo=hJtJCy96SRYmOxEpEMoEVcaegv0SCG0_AH2u0=bSrHZi_A@mail.gmail.com","threadId":"37007","inReplyTo":"CAJoVafc1LMxmvCiWci3N+AuAZBsABR3Wb3c6c3stw93OJZ7Scw@mail.gmail.com","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2014-06-27T15:45:02Z","receivedAt":"2014-06-27T15:45:02Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Jun 27, 2014 at 1:45 AM, Jarrad Hope wrote:\n> As a software developer I've used git for years and have found it the\n> perfect solution for source control.\n>\n> Lately I have found myself using git in a unique use-case - modifying\n> DNA/RNA sequences and storing them in git, which are essentially\n> software/source code for cells/life. For Bacteria and Viruses the\n> repo's are very small <10mb & compress nicely.\n>\n> However on the extreme end of the spectrum a human genome can run in\n> at 50gb or say ~1gb per file/chromosome.\n\nInteresting. Unfortunately not everything is used like source code. :)\n\nGit does source code well. I don't know enough to judge if DNA/RNA\nsequence storage is similar enough to source code to benefit from\nthings like `git log -p` showing deltas over time, or if some other\nalgorithm would be more effective.\n\n> From my understanding the largest problem revolves around git's delta\n> discovery method, holding 2 files in memory at once - is there a\n> reason this could not be adapted to page/chunk the data in a sliding\n> window fashion ?\n\nDuring delta discovery Git holds like 11 files in memory at once. One\nT is the target file that you are trying to delta compress. The other\n10 are in a window and Git compares T to each one of them in turn,\nselecting the file that produces the smallest delta instruction\nsequence to recreate T.\n\nBecause T is compared to 10ish other files (the window size is\ntuneable), Git needs a full copy of T in memory for the entire compare\nstep. For any single compare, T is scanned through only once. If you\nwere doing a single compare (window size of \"1\"), T could be \"on disk\"\nand paged through sequentially.\n\nThe files in the window need to be held entirely in memory, along with\na matching index. The actual delta compression algorithm is a\nRabin-Karp sliding window hash function. Copies can be made from any\npart of the source file with no regard to ordering. This makes\npaging/chunking the source file at both compression and decompression\ntime nearly impossible. Git jumps around the source file many times,\nbut it allows for efficient storage for movement of long sequences\nwithin a file (e.g. move function foo() later in the file).\n\nMaybe if you limited the window to 1 and limited the hash function to\navoid backing up in the source file so it could be paged, you can get\nsomewhere.\n\n\nBut you mentioned the files are O(1 GiB). Just buy more RAM? Modern\nworkstations have pretty good memory capacity.\n"},{"id":"245082","messageId":"xmqqegya2qgu.fsf@gitster.dls.corp.google.com","threadId":"37007","inReplyTo":"CAJo=hJtJCy96SRYmOxEpEMoEVcaegv0SCG0_AH2u0=bSrHZi_A@mail.gmail.com","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-27T17:48:49Z","receivedAt":"2014-06-27T17:48:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Git does source code well. I don't know enough to judge if DNA/RNA\n> sequence storage is similar enough to source code to benefit from\n> things like `git log -p` showing deltas over time, or if some other\n> algorithm would be more effective.\n>\n>> From my understanding the largest problem revolves around git's delta\n>> discovery method, holding 2 files in memory at once - is there a\n>> reason this could not be adapted to page/chunk the data in a sliding\n>> window fashion ?\n>\n> During delta discovery Git holds like 11 files in memory at once....\n\nEven though the original question mentioned \"delta discovery\", I\nthink what was being asked is not \"delta\" in the Git sense (which\nyour answer is about) but is \"can we diff two long sequences of text\n(that happens to consist of only 4-letter alphabet but that is a\nirrelevant detail) without holding both in-core in their entirety?\",\nwhich is a more relevant question/desire from the application point\nof view.\n\n\"Is there a reason this could not be adapted?\" No, there is no\nparticular reason why this \"could not\". I think that the only\nreason we only do in-core diff is because \"adapting to page/chunk\"\nhasn't been anybody's high priority list of itches to scratch.\n"},{"id":"245093","messageId":"CA+55aFx6vFyZvpyQot_3Ym7wsCZ06abjNx_hEKkza-N856jMnw@mail.gmail.com","threadId":"37007","inReplyTo":"xmqqegya2qgu.fsf@gitster.dls.corp.google.com","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2014-06-27T19:38:49Z","receivedAt":"2014-06-27T19:38:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, Jun 27, 2014 at 10:48 AM, Junio C Hamano wrote:\n>\n> Even though the original question mentioned \"delta discovery\", I\n> think what was being asked is not \"delta\" in the Git sense (which\n> your answer is about) but is \"can we diff two long sequences of text\n> (that happens to consist of only 4-letter alphabet but that is a\n> irrelevant detail) without holding both in-core in their entirety?\",\n> which is a more relevant question/desire from the application point\n> of view.\n\n.. even there, there's another issue. With enough memory, the diff\nitself should be fairly reasonable to do, but we do not have any sane\n*format* for diffing those kinds of things.\n\nThe regular textual diff is line-based, and is not amenable to\ncomparing two long lines. You'll just get a diff that says \"the two\nreally long lines are different\".\n\nThe binary diff option should work, but it is a horrible output\nformat, and not very helpful. It contains all the relevant data (\"copy\nthis chunk from here to here\"), but it's then shown in a binary\nencoding that isn't really all that useful if you want to say \"what\nare the differences between these two chromosomes\".\n\nI think it might be possible to just specify a special diff algorithm\n(git already supports that, obviously), and just introduce a new \"use\nbinary diffs with a textual representation\" model.\n\nBut it also sounds like there might be some actual performance problem\nwith these 1GB file delta-calculations. Which I wouldn't be surprised\nabout at all.\n\nJarrad - is there any public data you could give as an example and for\npeople to play with?\n\n Linus\n"},{"id":"245094","messageId":"CA+55aFwFne6gj6P_Vm+uGffbF--vd-yke0899k==iVgHkb+gWQ@mail.gmail.com","threadId":"37007","inReplyTo":"CA+55aFx6vFyZvpyQot_3Ym7wsCZ06abjNx_hEKkza-N856jMnw@mail.gmail.com","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2014-06-27T19:47:12Z","receivedAt":"2014-06-27T19:47:12Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, Jun 27, 2014 at 12:38 PM, Linus Torvalds\n wrote:\n>\n> I think it might be possible to just specify a special diff algorithm\n> (git already supports that, obviously), and just introduce a new \"use\n> binary diffs with a textual representation\" model.\n\nAnother model would be to just insert newlines in the data, and use\nthe regular textual diff on that \"preprocessed\" format.\n\nThe problem of *where* to insert the newlines is somewhat interesting,\nsince the stupid approaches (\"chunk it up in 64-byte lines\") don't\nwork with data insertion/deletion (all the lines will now be different\njust because the data is offset), but there are algorithms that handle\nthat reasonably well, like breaking lines at certain well-defined\npatterns (the patterns can then be defined either explicitly or\nalgorithmically - like calculating a hash/crc over the last rolling N\ncharacters and breaking if the result matches some modulo\ncalculation).\n\n Linus\n"},{"id":"245095","messageId":"57F015EB50E54211BF29FE1F6DE05CF4@black","threadId":"37007","inReplyTo":"CA+55aFx6vFyZvpyQot_3Ym7wsCZ06abjNx_hEKkza-N856jMnw@mail.gmail.com","subject":"RE: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Jason Pyeron","fromEmail":"jpyeron@pdinc.us","sentAt":"2014-06-27T19:55:59Z","receivedAt":"2014-06-27T19:55:59Z","isPatch":false,"sender":{"key":"jpyeron@pdinc.us","avatar":"https://gravatar.com/avatar/c2e53452caa53d940768a1ffc9cf76196d851b9b534b7a39cd39852a70a0508f?d=mp&s=160"},"body":"> -----Original Message-----\n> From: Linus Torvalds\n> Sent: Friday, June 27, 2014 15:39\n> \n> On Fri, Jun 27, 2014 at 10:48 AM, Junio C Hamano \n> wrote:\n> >\n> > Even though the original question mentioned \"delta discovery\", I\n> > think what was being asked is not \"delta\" in the Git sense (which\n> > your answer is about) but is \"can we diff two long sequences of text\n> > (that happens to consist of only 4-letter alphabet but that is a\n> > irrelevant detail) without holding both in-core in their entirety?\",\n> > which is a more relevant question/desire from the application point\n> > of view.\n> \n> .. even there, there's another issue. With enough memory, the diff\n> itself should be fairly reasonable to do, but we do not have any sane\n> *format* for diffing those kinds of things.\n> \n> The regular textual diff is line-based, and is not amenable to\n> comparing two long lines. You'll just get a diff that says \"the two\n> really long lines are different\".\n> \n> The binary diff option should work, but it is a horrible output\n> format, and not very helpful. It contains all the relevant data (\"copy\n> this chunk from here to here\"), but it's then shown in a binary\n> encoding that isn't really all that useful if you want to say \"what\n> are the differences between these two chromosomes\".\n> \n> I think it might be possible to just specify a special diff algorithm\n> (git already supports that, obviously), and just introduce a new \"use\n> binary diffs with a textual representation\" model.\n> \n> But it also sounds like there might be some actual performance problem\n> with these 1GB file delta-calculations. Which I wouldn't be surprised\n> about at all.\n> \n> Jarrad - is there any public data you could give as an example and for\n> people to play with?\n\nUntil Jarrad replies see sample here:\nhttp://www.genomatix.de/online_help/help/sequence_formats.html\n\nThe issue will be, if we talk about changes other than same length substitutions\n(e.g. Down's Syndrome where it has an insertion of code) would require one code\nper line for the diffs to work nicely.\n\n-Jason\n\n--\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n- -\n- Jason Pyeron PD Inc. http://www.pdinc.us -\n- Principal Consultant 10 West 24th Street #100 -\n- +1 (443) 269-1555 x333 Baltimore, Maryland 21218 -\n- -\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\nThis message is copyright PD Inc, subject to license 20080407P00.\n"},{"id":"245096","messageId":"CA+55aFyaQJDq4dvPyS3oLJp57J_zEmqbXA5UxzL8fdgAaHpJOA@mail.gmail.com","threadId":"37007","inReplyTo":"57F015EB50E54211BF29FE1F6DE05CF4@black","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2014-06-27T20:13:57Z","receivedAt":"2014-06-27T20:13:57Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, Jun 27, 2014 at 12:55 PM, Jason Pyeron wrote:\n>\n> The issue will be, if we talk about changes other than same length substitutions\n> (e.g. Down's Syndrome where it has an insertion of code) would require one code\n> per line for the diffs to work nicely.\n\nNot my area of expertise, but depending on what you are interested in\n- like protein encoding etc, I really think you don't need to do\nthings character-per-character. You might want to break at interesting\nsequences (TATA box, and/or known long repeating sequences).\n\nSo you could basically turn the \"one long line\" representation into\nmultiple lines, by just looking for particular known interesting (or\nknown particularly *UN*interesting) patterns, and whenever you see the\npattern you create a new line, describing the pattern (\"TATAAA\" or\n\"run of 128 U\"), and then continue on the next line.\n\nThen you diff those \"semantically enriched\" streams instead of the raw data.\n\nBut it probably depends on what you are looking for and at. Sometimes\nyou might be looking at individual base pairs. And sometimes maybe you\nwant to look at the codons, and consider condons that transcribe to\nthe same amino acid to be the same, and not show up as a difference.\nSo I could well imagine that you might want to have multiple different\nways to generate these diffs. No?\n\n Linus\n"},{"id":"245117","messageId":"CAJoVafdyFWjnaKbz47n12ykLAn28TSFDxLvbWfT51Rim7SXLsA@mail.gmail.com","threadId":"37007","inReplyTo":"CA+55aFyaQJDq4dvPyS3oLJp57J_zEmqbXA5UxzL8fdgAaHpJOA@mail.gmail.com","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Jarrad Hope","fromEmail":"me@jarradhope.com","sentAt":"2014-06-28T06:51:07Z","receivedAt":"2014-06-28T06:51:07Z","isPatch":false,"sender":{"key":"me@jarradhope.com","avatar":null},"body":"Thank-you all for replying,\n\nIt's just as Jason suggests - Genbank, FASTA & EMBL are more or less\nthe defacto standards, I suspect FASTA will be phased out because (to\nmy knowledge) it does not support gene annotation, nevertheless, they\nare all text based.\n\nThese formats usually insert linebreaks around 80 characters (a\ncultural/human readability relic, whatever terminal output they had\nthe time)\n\nI tried to find a Penguin genome sequence for you, The best I can find\nis the complete penguin mitochrondrian dna, as you can see, fairly\nsmall.\nhttp://www.ncbi.nlm.nih.gov/nuccore/558603183?report=fasta\nhttp://www.ncbi.nlm.nih.gov/nuccore/558603183?report=genbank\n\nIf you would like to checkout the source for a Human, please see\nftp://ftp.ensembl.org/pub/current_fasta/homo_sapiens/dna/\nDon't ask me for a Makefile :) in near future you'll be able to print\nsequences of this length, today we're limited to small sequences (such\nas bacteria/virus) at ~30cents per basepair\n\nEach chromosome packs quite well ~80MB packed, ~240MB unpacked\nHowever these formats allow you to repesent multiple sequences in one file\nftp://ftp-trace.ncbi.nih.gov/1000genomes/ftp/technical/reference/human_g1k_v37.fasta.gz\n<- ~850MB packed\n\nSidenote, Humans aren't that particulary more complicated than Rice\n(in terms of genome size)\nhttp://www.plantgdb.org/XGDB/phplib/download.php?GDB=Os\n\nOther animal sequences - http://www.ensembl.org/index.html\n\nGit is already being used very successfully for SBML, Synthetic\nBiology Markup Language, an XML dialect for cell modelling.\n\nI would show an example git repo of some open source cancer treatments\n(various oncolytic viruses) I've been working on, unfortunately it's\nnot finished yet, but you can imagine something the size of penguin\nmitochrondrial dna with essentially just text being deleted (gene\ndeletions) as commits.\n\nI hope that helps - With the advancement of Synthetic and Systems\nBiology, I really see these sequences benefiting from git.\n\n\nOn Sat, Jun 28, 2014 at 3:13 AM, Linus Torvalds\n wrote:\n> On Fri, Jun 27, 2014 at 12:55 PM, Jason Pyeron wrote:\n>>\n>> The issue will be, if we talk about changes other than same length substitutions\n>> (e.g. Down's Syndrome where it has an insertion of code) would require one code\n>> per line for the diffs to work nicely.\n>\n> Not my area of expertise, but depending on what you are interested in\n> - like protein encoding etc, I really think you don't need to do\n> things character-per-character. You might want to break at interesting\n> sequences (TATA box, and/or known long repeating sequences).\n>\n> So you could basically turn the \"one long line\" representation into\n> multiple lines, by just looking for particular known interesting (or\n> known particularly *UN*interesting) patterns, and whenever you see the\n> pattern you create a new line, describing the pattern (\"TATAAA\" or\n> \"run of 128 U\"), and then continue on the next line.\n>\n> Then you diff those \"semantically enriched\" streams instead of the raw data.\n>\n> But it probably depends on what you are looking for and at. Sometimes\n> you might be looking at individual base pairs. And sometimes maybe you\n> want to look at the codons, and consider condons that transcribe to\n> the same amino acid to be the same, and not show up as a difference.\n> So I could well imagine that you might want to have multiple different\n> ways to generate these diffs. No?\n>\n> Linus\n"},{"id":"245181","messageId":"53B15E64.9030005@gmail.com","threadId":"37007","inReplyTo":"CA+55aFx6vFyZvpyQot_3Ym7wsCZ06abjNx_hEKkza-N856jMnw@mail.gmail.com","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2014-06-30T12:56:04Z","receivedAt":"2014-06-30T12:56:04Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Linus Torvalds wrote:\n> On Fri, Jun 27, 2014 at 10:48 AM, Junio C Hamano wrote:\n>>\n>> Even though the original question mentioned \"delta discovery\", I\n>> think what was being asked is not \"delta\" in the Git sense (which\n>> your answer is about) but is \"can we diff two long sequences of text\n>> (that happens to consist of only 4-letter alphabet but that is a\n>> irrelevant detail) without holding both in-core in their entirety?\",\n>> which is a more relevant question/desire from the application point\n>> of view.\n>\n> .. even there, there's another issue. With enough memory, the diff\n> itself should be fairly reasonable to do, but we do not have any sane\n> *format* for diffing those kinds of things.\n>\n> The regular textual diff is line-based, and is not amenable to\n> comparing two long lines. You'll just get a diff that says \"the two\n> really long lines are different\".\n>\n> The binary diff option should work, but it is a horrible output\n> format, and not very helpful. It contains all the relevant data (\"copy\n> this chunk from here to here\"), but it's then shown in a binary\n> encoding that isn't really all that useful if you want to say \"what\n> are the differences between these two chromosomes\".\n\nThere is also --word-diff[=] word-based textual diff,\nand I think one can abuse --word-diff-regex= for\ncharacter-based diff... or maybe not, as specifies\nword characters, not words or word separators.\n\n-- \nJakub Narębski\n"},{"id":"247569","messageId":"CAA787rkoX=aEf3cs5LpPmKKOfKeAUQZ+3KqckofRjOfCaNP-+g@mail.gmail.com","threadId":"37007","inReplyTo":"53B15E64.9030005@gmail.com","subject":"Re: Tackling Git Limitations with Singular Large Line-seperated Plaintext files","fromName":"Øyvind A. Holm","fromEmail":"sunny@sunbase.org","sentAt":"2014-08-10T21:45:34Z","receivedAt":"2014-08-10T21:45:34Z","isPatch":false,"sender":{"key":"sunny@sunbase.org","avatar":"https://avatars.githubusercontent.com/u/113445?v=4"},"body":"On 30 June 2014 14:56, Jakub Narębski wrote:\n> Linus Torvalds wrote:\n> > .. even there, there's another issue. With enough memory, the diff\n> > itself should be fairly reasonable to do, but we do not have any\n> > sane *format* for diffing those kinds of things.\n> >\n> > The regular textual diff is line-based, and is not amenable to\n> > comparing two long lines. You'll just get a diff that says \"the two\n> > really long lines are different\".\n> >\n> > The binary diff option should work, but it is a horrible output\n> > format, and not very helpful. It contains all the relevant data\n> > (\"copy this chunk from here to here\"), but it's then shown in a\n> > binary encoding that isn't really all that useful if you want to say\n> > \"what are the differences between these two chromosomes\".\n>\n> There is also --word-diff[=] word-based textual diff, and I\n> think one can abuse --word-diff-regex= for character-based\n> diff... or maybe not, as specifies word characters, not words\n> or word separators.\n\nYes, I have this alias defined:\n\n dww = diff --word-diff --word-diff-regex=.\n\nIt creates nice diffs on a character level. Sometimes specifying\n--patience to this helps.\n\n-- Øyvind\n"}]}