{"thread":{"id":"19770","subject":"Mercurial on BigTable","startedAt":"2009-06-10T19:15:49Z","lastAt":"2009-06-12T07:14:14Z","messageCount":8,"participants":["Scott Chacon","Sverre Rabbelier","Andreas Ericsson","Jakub Narebski","Sitaram Chamarty","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"116027","messageId":"d411cc4a0906101215t313b2037k713aa1ce974c30cc@mail.gmail.com","threadId":"19770","inReplyTo":null,"subject":"Mercurial on BigTable","fromName":"Scott Chacon","fromEmail":"schacon@gmail.com","sentAt":"2009-06-10T19:15:49Z","receivedAt":"2009-06-10T19:15:49Z","isPatch":false,"sender":{"key":"schacon@gmail.com","avatar":"https://gravatar.com/avatar/9b13a8a078e1dcf8588c4eea9554445d51ebed6c41b51f56f4d96738130b05c6?d=mp&s=160"},"body":"Has anyone watched this yet?\n\nhttp://code.google.com/events/io/sessions/MercurialBigTable.html\n\nIt's kind of interesting - a Googler talks about getting Mercurial\nrunning on BigTable. What fascinates me is that if I'm not horribly\nmistaken, it seems like they just threw out the revlog format entirely\nand just store the data in a key-value store as sort of a Git-like\ncontent addressable filesystem. I had thought they were taking\nadvantage of the revlog structure somehow, but it appears like they\nbasically just changed the underlying data format to be much more like\nGit and rewrote ah Hg speaking server on top of that. They even\nexplicitly store the head values like refs instead of reading\nchildless nodes out of the revlog, which is what I thought Hg did.\n\nDoes anyone know how they do the graph walking efficiently with this\nstructure? He mentioned it was about half as fast as native Hg, but\nthat seemed to be acceptable. Curious if anyone had any thoughts or\ninformation on this. Shawn, are there technical reasons why this\nworks well the way they're doing it for Hg but would not for Git (like\nin the repo MINA based server)? It looks like the data structure and\nprotocol exchange are incredibly similar after they threw away all the\nrevlog stuff. Or is it just that they're fine with the speed loss and\nthe Android project would not be?\n\nScott\n"},{"id":"116029","messageId":"fabb9a1e0906101223o31f4adf3o863ff380be4b1465@mail.gmail.com","threadId":"19770","inReplyTo":"d411cc4a0906101215t313b2037k713aa1ce974c30cc@mail.gmail.com","subject":"Re: Mercurial on BigTable","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-06-10T19:23:49Z","receivedAt":"2009-06-10T19:23:49Z","isPatch":false,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Wed, Jun 10, 2009 at 21:15, Scott Chacon wrote:\n> in the repo MINA based server)?  It looks like the data structure and\n> protocol exchange are incredibly similar after they threw away all the\n> revlog stuff.  Or is it just that they're fine with the speed loss and\n> the Android project would not be?\n\nThere's one explanation for that, git's lack of a decent HTTP\nprotocol, no? The speed loss of http:// vs git:// is still huge :(.\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"116056","messageId":"4A3065C5.3070203@op5.se","threadId":"19770","inReplyTo":"d411cc4a0906101215t313b2037k713aa1ce974c30cc@mail.gmail.com","subject":"Re: Mercurial on BigTable","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2009-06-11T02:02:45Z","receivedAt":"2009-06-11T02:02:45Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Scott Chacon wrote:\n> Has anyone watched this yet?\n> \n> http://code.google.com/events/io/sessions/MercurialBigTable.html\n> \n> It's kind of interesting - a Googler talks about getting Mercurial\n> running on BigTable. What fascinates me is that if I'm not horribly\n> mistaken, it seems like they just threw out the revlog format entirely\n> and just store the data in a key-value store as sort of a Git-like\n> content addressable filesystem.\n\nIt does indeed seem like that, yes. Would have been fun to be there to\ncongratulate him on implementing something that's already existed for\nabout three years ;-)\n\n> I had thought they were taking\n> advantage of the revlog structure somehow, but it appears like they\n> basically just changed the underlying data format to be much more like\n> Git and rewrote ah Hg speaking server on top of that. They even\n> explicitly store the head values like refs instead of reading\n> childless nodes out of the revlog, which is what I thought Hg did.\n> \n\nWell, storing the head values as refs is the only thing that makes\nsense if you're using a database to track things, since you'd otherwise\nhave to map in too much data to get any sort of performance at all\nout of it.\n\n> Does anyone know how they do the graph walking efficiently with this\n> structure? He mentioned it was about half as fast as native Hg, but\n> that seemed to be acceptable.\n\nYes, so they don't. DAG walking means they have to look up several\nchangesets in a linear fashion, but if they don't know the order\nup front they'll have to suffer the penalty of actually fetching\neach commit from the bigtable database over the network. It would\nbe similar to storing git objects in a database on a different\nhost, which would also be quite a lot slower than just hitting an\nmmap()'ed file in binary form.\n\n> Curious if anyone had any thoughts or\n> information on this. Shawn, are there technical reasons why this\n> works well the way they're doing it for Hg but would not for Git (like\n> in the repo MINA based server)? It looks like the data structure and\n> protocol exchange are incredibly similar after they threw away all the\n> revlog stuff. Or is it just that they're fine with the speed loss and\n> the Android project would not be?\n> \n\nI'm more curious as to why they didn't choose git. The only explanation\nthat was actually true is that hg works well over HTTP (if you can call\n3 network requests per not-up-to-date head \"well\"). Since I can't imagine\nthem not doing proper research before launching a project that almost\ncertainly cost quite a lot of money, and I personally think that the\n\"http rules all\" explanation sounded weak, I'm guessing there were other\nreasons as to why they didn't go with git instead, and I'm fairly curious\nto hear them. If I was to take a guess, I'd say git is written in a pretty\nunfriendly way for implementing other storage engines.\n\nAh well. In a year or two they'll probably support git as well. One can\nhope at least ;-)\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"116062","messageId":"m34oun41pz.fsf@localhost.localdomain","threadId":"19770","inReplyTo":"4A3065C5.3070203@op5.se","subject":"Re: Mercurial on BigTable","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2009-06-11T08:24:48Z","receivedAt":"2009-06-11T08:24:48Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Andreas Ericsson writes:\n\n> I'm more curious as to why they didn't choose git. The only explanation\n> that was actually true is that hg works well over HTTP (if you can call\n> 3 network requests per not-up-to-date head \"well\"). Since I can't imagine\n> them not doing proper research before launching a project that almost\n> certainly cost quite a lot of money, and I personally think that the\n> \"http rules all\" explanation sounded weak, I'm guessing there were other\n> reasons as to why they didn't go with git instead, and I'm fairly curious\n> to hear them. If I was to take a guess, I'd say git is written in a pretty\n> unfriendly way for implementing other storage engines.\n\nWell, Google App Engine was in Python, so it follows that the crew\nwould have it easier understanding Mercurial code (which is written in\nPython with parts in C for performance), and in moving it to BigTable.\nAdding Java to Gogle App Engine is, as far as I know, fairly recent;\nadditionally JGit (git implementation in Java) is not yet full\nimplementation.\n\nI don't know if Git would be easy to implement on BigTable, and\nwhether it wouldn't be better for performance to try to implement it\non top of underlying Google File System (GFS) and Chubby Lock Service\n_directly_...\n\n\nSidenote: lack of good HTTP protocol support (there are some numbers\nat the bottom of comparison[1], but not enough detail to satisfy) as a\nreason is especially strange now that there was quite long discussion\ndesigning git-over-HTTP (\"smart\" HTTP protocol); cleaning warts in git\npack protocol, working around HTTP being stateless, ensuring backward\ncompatibility, ensuring that it would work well with HTTP caches...\n\nBut that is the problem with detailed research for \"fast moving\ntarget\". Good research takes time, and by the time you finished it its\nresults are already obsolete...\n\n[1] http://code.google.com/p/support/wiki/DVCSAnalysis\n\n> \n> Ah well. In a year or two they'll probably support git as well. One can\n> hope at least ;-)\n\nLet's hope to that...\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"116072","messageId":"slrnh325l3.rh5.sitaramc@sitaramc.homelinux.net","threadId":"19770","inReplyTo":"4A3065C5.3070203@op5.se","subject":"Re: Mercurial on BigTable","fromName":"Sitaram Chamarty","fromEmail":"sitaramc@gmail.com","sentAt":"2009-06-11T14:37:23Z","receivedAt":"2009-06-11T14:37:23Z","isPatch":false,"sender":{"key":"sitaramc@gmail.com","avatar":"https://avatars.githubusercontent.com/u/43316?v=4"},"body":"On 2009-06-11 02:02:45, Andreas Ericsson wrote:\n> \"http rules all\" explanation sounded weak, I'm guessing there were other\n> reasons as to why they didn't go with git instead, and I'm fairly curious\n> to hear them. If I was to take a guess, I'd say git is written in a pretty\n> unfriendly way for implementing other storage engines.\n\nerr, umm...\n\nhttp://permalink.gmane.org/gmane.comp.version-control.git/117588\n"},{"id":"116119","messageId":"20090612034645.GO16497@spearce.org","threadId":"19770","inReplyTo":"m34oun41pz.fsf@localhost.localdomain","subject":"Re: Mercurial on BigTable","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-06-12T03:46:45Z","receivedAt":"2009-06-12T03:46:45Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jakub Narebski wrote:\n> Andreas Ericsson writes:\n> \n> > I'm more curious as to why they didn't choose git. The only explanation\n> > that was actually true is that hg works well over HTTP \n> \n> Well, Google App Engine was in Python, so it follows that the crew\n> would have it easier understanding Mercurial code (which is written in\n> Python with parts in C for performance), and in moving it to BigTable.\n\nThis has nothing to do with Google AppEngine. GAE has CPU and\nbandwidth limitations in place that make running a source code server\nlike Hg on it impossible. E.g. the maximum size you could download\nin a single HTTP request was 1 MB, now its up to 10 MB (IIRC).\nThe Hg hosting runs in a different cluster than the GAE hosting does,\nand are managed by different teams.\n\n> Adding Java to Gogle App Engine is, as far as I know, fairly recent;\n\nTrue, yes, GAE Java support is fairly new.\n\n> additionally JGit (git implementation in Java) is not yet full\n> implementation.\n\nJGit implements sufficient parts of Git to be a full server, and\ncould power a hosting site... indeed it powers Gerrit Code Review,\nwhich some companies do use as their entire Git server solution,\nrather than e.g. Gitosis.\n \n-- \nShawn.\n"},{"id":"116120","messageId":"20090612041428.GP16497@spearce.org","threadId":"19770","inReplyTo":"d411cc4a0906101215t313b2037k713aa1ce974c30cc@mail.gmail.com","subject":"Re: Mercurial on BigTable","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-06-12T04:14:28Z","receivedAt":"2009-06-12T04:14:28Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Scott Chacon wrote:\n> Has anyone watched this yet?\n> \n> http://code.google.com/events/io/sessions/MercurialBigTable.html\n\nI hadn't seen that yet, thanks.\n \n> It's kind of interesting - a Googler talks about getting Mercurial\n> running on BigTable. What fascinates me is that if I'm not horribly\n> mistaken, it seems like they just threw out the revlog format entirely\n> and just store the data in a key-value store as sort of a Git-like\n> content addressable filesystem.\n\nAlmost... but not quite. If you look at the way they store files\nthey embed the file path as part of the BigTable key. This makes it\ncheap to return all revisions between X and Y for any given file, as\nits just a range scan over the keys. Git doesn't do this normally.\n\nIn Hg, and in their implementation of it on BigTable, if a file\ncontent is copied between two paths (same blob in git terms) they\nactually duplicate the data, once under each path. We could do\nsomething like that in Git... and just pay the price on copy, and\nthen you can get a storage layout like they do, and have it scale\nwell onto a larger system. But... pack size will suffer in what\nthe client receives, it will be bigger.\n\n> Does anyone know how they do the graph walking efficiently with this\n> structure? He mentioned it was about half as fast as native Hg, but\n> that seemed to be acceptable. Curious if anyone had any thoughts or\n> information on this. Shawn, are there technical reasons why this\n> works well the way they're doing it for Hg but would not for Git (like\n> in the repo MINA based server)? It looks like the data structure and\n> protocol exchange are incredibly similar after they threw away all the\n> revlog stuff.\n\nI think they also added more pointers and data caches that don't\nexist in Hg normally, but exist in their BigTable backend. Like\nprecomputing pointers from a commit to the most recent ancestor\nthat is a merge, i think that was mentioned in the talk.\n\nThe JGit/MINA based servers run git \"well enough\", but that's off\nlocal disk, and we do pay a good price compared to C Git. E.g.\nwe really need a revcache to accelerate the object enumeration phase,\nthat takes ages in JGit. And indexing a pushed pack is rather slow\ncompared to C Git, a large push could take up to a minute or two\nto fully index and fsck.\n\n> Or is it just that they're fine with the speed loss and\n> the Android project would not be?\n\nWhat does Android have to do with Hg? Android went with Git for\na lot of reasons, none of them having to do with the performance\nor availability of Hg on code.google.com. All of them had to do\nwith Git being a really solid DVCS that has a very bright future.\n\n-- \nShawn.\n"},{"id":"116127","messageId":"200906120914.16185.jnareb@gmail.com","threadId":"19770","inReplyTo":"20090612034645.GO16497@spearce.org","subject":"Re: Mercurial on BigTable","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2009-06-12T07:14:14Z","receivedAt":"2009-06-12T07:14:14Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Fri, 12 June 2009, Shawn O. Pearce wrote:\n> Jakub Narebski wrote:\n> > Andreas Ericsson writes:\n> > \n> > > I'm more curious as to why they didn't choose git. The only explanation\n> > > that was actually true is that hg works well over HTTP \n> > \n> > Well, Google App Engine was in Python, so it follows that the crew\n> > would have it easier understanding Mercurial code (which is written in\n> > Python with parts in C for performance), and in moving it to BigTable.\n> \n> This has nothing to do with Google AppEngine. GAE has CPU and\n> bandwidth limitations in place that make running a source code server\n> like Hg on it impossible. E.g. the maximum size you could download\n> in a single HTTP request was 1 MB, now its up to 10 MB (IIRC).\n> The Hg hosting runs in a different cluster than the GAE hosting does,\n> and are managed by different teams.\n> \n> > Adding Java to Gogle App Engine is, as far as I know, fairly recent;\n> \n> True, yes, GAE Java support is fairly new.\n\nI didn't wanted to say that support for Mercurial (or other DVCS) in\nGoogle Code had anything to do with Google AppEngine. Rather I wanted\nto imply that what might have mattered when choosing between Mercurial\nand Git was the fact that there was large pool of people who are \nproficient in Python (and later in Java) _and_ with web application(s).\n\nBut I don't quite see how lack of good over HTTP support should matter;\nif they are rewriting Mercurial[1] (and earlier Subversion) to use \nBigTable, couldn't they add \"smart\" HTTP protocol support to Git \n(which I think would be easier)?\n\n[1] Mercurial is not AGPLv3 licensed...\n\n> \n> > additionally JGit (git implementation in Java) is not yet full\n> > implementation.\n> \n> JGit implements sufficient parts of Git to be a full server, and\n> could power a hosting site... indeed it powers Gerrit Code Review,\n> which some companies do use as their entire Git server solution,\n> rather than e.g. Gitosis.\n\nBy \"not full implementation\" I meant here that as far as I know JGit\ndoesn't have yet support for _creating_ (as opposed to simply reusing)\ndeltas in packfiles.\n\n\nP.S. On the other hand, Mercurial support for multiple branches is\nnot so good[2], and the way tags got implemented seems iffy to me...\n\n[2] http://schacon.github.com/2008/11/24/on-mercurial.html\n\n-- \nJakub Narebski\nPoland\n"}]}