{"thread":{"id":"30012","subject":"GSoC - Designing a faster index format","startedAt":"2012-03-20T23:10:04Z","lastAt":"2012-04-07T08:29:49Z","messageCount":33,"participants":["elton sky","Nguyen Thai Ngoc Duy","Thomas Rast","Jakub Narebski","Shawn Pearce","David Barr","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"187368","messageId":"CAKTdtZm3qfG1rcoashDoMoqtD34JJDUDtDruGqGn9bSMzQTcFA@mail.gmail.com","threadId":"30012","inReplyTo":null,"subject":"GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-20T23:10:04Z","receivedAt":"2012-03-20T23:10:04Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hello everyone,\n\nI am not sure if this is the right way to apply GSoC or if this\nproject is still available?  I just subscribed a few hours ago, don't\nblame me :)\n\nI am interested with \"Designing a faster index format\" project.\n\nI am new to git, only started using git yesterday.\n\nThe reasons for applying this is:\n1. I like C\n2. I like doing optimization\n3. I want to contribute to a open source project - to git, a plus\n\nFrom the idea, I realize the problem is that index is verified and\nrewritten on any operations which is unnecessary sometimes. And the\nobjective is to reduce the number of operations to below logN.  As I\nam new to git, I  I couldn't give a detailed plan to this for now. I\nshould have gonna through more documents or codes but there's only one\nweek for application. So I have to jump up from nowhere :P\n\nI got questions like: how each operations affect index? how cache tree\ndata and index is stored?\nMaybe you can point me how I should catch up quickly. I went through\nthe article \"git-for-computer-scientists\", that quite makes sense.\n\nAbout me:\n\nMy name is Elton Tian, I am from China. I have been living in\nAustralia for quite a few years. I am currently a Master student from\nAustralia National University. I have lots of experience in C during\nmy undergraduate: socket, RPC, pthread, etc.. After graduate I worked\nwith linux based web development for 2.5 years. We used tcl, apache\nand cvs. Last year, as a student project, I had chance to benchmark\nand modify hadoop distributed file system and mapreduce on a small\ncluster. I have to configure and maintain the cluster by myself.\n\nMy IRC nick is \"eltonsky\".\n\n\nRegards,\nElton\n"},{"id":"187374","messageId":"CACsJy8C8Ds04Gr35xBgdjX+Wpm6vQB_qu4XYBz0_e+ugmNj1vA@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZm3qfG1rcoashDoMoqtD34JJDUDtDruGqGn9bSMzQTcFA@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-21T01:18:58Z","receivedAt":"2012-03-21T01:18:58Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Mar 21, 2012 at 6:10 AM, elton sky wrote:\n> From the idea, I realize the problem is that index is verified and\n> rewritten on any operations which is unnecessary sometimes. And the\n> objective is to reduce the number of operations to below logN.  As I\n> am new to git, I  I couldn't give a detailed plan to this for now. I\n> should have gonna through more documents or codes but there's only one\n> week for application. So I have to jump up from nowhere :P\n\nUnderstanding current index format would be a good start, I think:\nDocumentation/technical/index-format.txt. For reading index code, look\nat read_index_from() in read-cache.c (many if not all index\nmanipulation are in this file)\n\n> I got questions like: how each operations affect index?\n\nFor writing part, commands that call refresh_index() can update stat\ninfo for many many entries. git-add, git-update, git-mv and git-rm can\nadd/remove entries from the index. Merge/checkout oeprations\n(git-reset, git-checkout, git-merge..) can rewrite the whole index. I\nthink this proposal aims to speed up refresh_index and add/remove\noperations, not the last one.\n\nTo speed up reading part (you can grep read_cache() to see how many\ncommands read index), you may need to do something with index\nintegrity check. Currently it calculates SHA-1 of the entire index,\nthen checks against the stored value at the end of index. Calculating\nSHA-1 can be really expensive on big index.\n\n> how cache tree data and index is stored?\n\nCache tree is stored as an optional index extension. It's also\ndocumented in index-format.txt. Or you can look at cache-tree.[ch]\n-- \nDuy\n"},{"id":"187388","messageId":"87aa3aw5z8.fsf@thomas.inf.ethz.ch","threadId":"30012","inReplyTo":"CAKTdtZm3qfG1rcoashDoMoqtD34JJDUDtDruGqGn9bSMzQTcFA@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-21T11:25:47Z","receivedAt":"2012-03-21T11:25:47Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"elton sky writes:\n\n> I got questions like: how each operations affect index? how cache tree\n> data and index is stored?\n> Maybe you can point me how I should catch up quickly. I went through\n> the article \"git-for-computer-scientists\", that quite makes sense.\n\nIn addition to what Nguyen Thai Ngoc Duy said, check out the\n(sub)threads\n\n http://thread.gmane.org/gmane.comp.version-control.git/190016/focus=190132\n [origins of the GSoC project idea]\n\n http://thread.gmane.org/gmane.comp.version-control.git/192014/focus=192025\n [perspectives of core developers in reply to the idea]\n\n http://thread.gmane.org/gmane.comp.version-control.git/186244/focus=186282\n http://thread.gmane.org/gmane.comp.version-control.git/186357\n [the last few discussions about cache-tree]\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"187389","messageId":"CAKTdtZkGP3KbMGf88yW7zcCjemUyEy_4CVNkLD0SV=Lm7=Kveg@mail.gmail.com","threadId":"30012","inReplyTo":"87aa3aw5z8.fsf@thomas.inf.ethz.ch","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-21T12:01:58Z","receivedAt":"2012-03-21T12:01:58Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hi Nguyen, Thomas\n\nThanks for the points &clues. Processing them...\n\n-Elton\n\nOn Wed, Mar 21, 2012 at 10:25 PM, Thomas Rast wrote:\n> elton sky writes:\n>\n>> I got questions like: how each operations affect index? how cache tree\n>> data and index is stored?\n>> Maybe you can point me how I should catch up quickly. I went through\n>> the article \"git-for-computer-scientists\", that quite makes sense.\n>\n> In addition to what Nguyen Thai Ngoc Duy said, check out the\n> (sub)threads\n>\n>  http://thread.gmane.org/gmane.comp.version-control.git/190016/focus=190132\n>  [origins of the GSoC project idea]\n>\n>  http://thread.gmane.org/gmane.comp.version-control.git/192014/focus=192025\n>  [perspectives of core developers in reply to the idea]\n>\n>  http://thread.gmane.org/gmane.comp.version-control.git/186244/focus=186282\n>  http://thread.gmane.org/gmane.comp.version-control.git/186357\n>  [the last few discussions about cache-tree]\n>\n> --\n> Thomas Rast\n> trast@{inf,student}.ethz.ch\n"},{"id":"187522","messageId":"CAKTdtZmYc=xz4zCPQiuSTUvdmbLRKXNWNL3N6_4Bj0gujYmRvw@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZkGP3KbMGf88yW7zcCjemUyEy_4CVNkLD0SV=Lm7=Kveg@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-22T20:32:08Z","receivedAt":"2012-03-22T20:32:08Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Got a few questions:\n\n1. index is used for building next commit, so it should only include\nfiles created/modified/deleted. But I see it has all entries for\ncurrent working dir. why?\n\n2. From read_index_from() I see the whole index is read into mem, and\nwrite one by one (entry/ext) back to disk. This makes sense. But why\nwe have to compute Sha1 for all entries, especially unchanged entries?\n\n3. how does git track updated files? Does it compare the ts between\nworking dir and index ? Or they are recorded somewhere?\n\n4. When does git insert to cache tree? and when it retrieve from it?\n\n\nSome early thoughts for the tree format:\n\nWe can use B tree like format. Keep the header in the beginning of the\nfile as is, but add file length (4bytes) and the pointer to extensions\n(8bytes) into header.\nEntry list follows the header. The entry starts with number of\nchildren offsets (1 byte) followed by list of offsets (4 bytes each).\nWe can limit the number for balance. Other fields leave as is.\nExtensions can locate in between entries.\n\nUse Sha1 , rather than the path, as the key for each entry node. This\nbeats the case like 1000 files in a dir which breaks the balance of\nthe tree, as Thomas mentioned. If a file is updated, the old Sha1 can\nbe found in object dir. This also gives flexibility. We may use splay\ntree, in order to move updated nodes close to the root. The downside\nis full path has to be stored in entry.\n\nRegards,\nElton\n\nOn Wed, Mar 21, 2012 at 11:01 PM, elton sky wrote:\n> Hi Nguyen, Thomas\n>\n> Thanks for the points &clues. Processing them...\n>\n> -Elton\n>\n> On Wed, Mar 21, 2012 at 10:25 PM, Thomas Rast wrote:\n>> elton sky writes:\n>>\n>>> I got questions like: how each operations affect index? how cache tree\n>>> data and index is stored?\n>>> Maybe you can point me how I should catch up quickly. I went through\n>>> the article \"git-for-computer-scientists\", that quite makes sense.\n>>\n>> In addition to what Nguyen Thai Ngoc Duy said, check out the\n>> (sub)threads\n>>\n>>  http://thread.gmane.org/gmane.comp.version-control.git/190016/focus=190132\n>>  [origins of the GSoC project idea]\n>>\n>>  http://thread.gmane.org/gmane.comp.version-control.git/192014/focus=192025\n>>  [perspectives of core developers in reply to the idea]\n>>\n>>  http://thread.gmane.org/gmane.comp.version-control.git/186244/focus=186282\n>>  http://thread.gmane.org/gmane.comp.version-control.git/186357\n>>  [the last few discussions about cache-tree]\n>>\n>> --\n>> Thomas Rast\n>> trast@{inf,student}.ethz.ch\n"},{"id":"187551","messageId":"m3obrob0vk.fsf@localhost.localdomain","threadId":"30012","inReplyTo":"CAKTdtZmYc=xz4zCPQiuSTUvdmbLRKXNWNL3N6_4Bj0gujYmRvw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2012-03-23T00:46:09Z","receivedAt":"2012-03-23T00:46:09Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"elton sky writes:\n\n> Got a few questions:\n> \n> 1. index is used for building next commit, so it should only include\n> files created/modified/deleted. But I see it has all entries for\n> current working dir. why?\n\nBecause git is snapshot based, not changeset based. Ecah commit\nstores state of repository in the form of 'tree' object, which is\nbuild out of index.\n \nAlso index stores extra information, like mtime, about all files\nto make operations faster (skip unchanged files). The index was\noriginally at the very beginning named dircache.\n\n[...]\n-- \nJakub Narebski\n"},{"id":"187553","messageId":"CACsJy8AYs5bzRnhRj_R33qTt-2gPh-rJaO0=1iTva9n14wHB4w@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZmYc=xz4zCPQiuSTUvdmbLRKXNWNL3N6_4Bj0gujYmRvw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-23T01:30:16Z","receivedAt":"2012-03-23T01:30:16Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Mar 23, 2012 at 3:32 AM, elton sky wrote:\n> Got a few questions:\n>\n> 1. index is used for building next commit, so it should only include\n> files created/modified/deleted. But I see it has all entries for\n> current working dir. why?\n\nJakub has answered this question.\n\n> 2. From read_index_from() I see the whole index is read into mem, and\n> write one by one (entry/ext) back to disk. This makes sense. But why\n> we have to compute Sha1 for all entries, especially unchanged entries?\n\nTo catch disk corruption. If a bit is flipped anywhere in the index\nand we do not detect it, we may end up creating broken commits.\n\n> 3. how does git track updated files? Does it compare the ts between\n> working dir and index ? Or they are recorded somewhere?\n\nCheck out refresh_cache_ent. At the beginning of most commands, they\ncall refresh_index() or refresh_cache(), which checks a file's mtime\nagainst one stored in index (different means updated). In the worst\nscenario, refresh_cache_ent may call ce_compare_data(), which computes\nSHA-1 of the specified file and compare it with one stored in index.\n\n> 4. When does git insert to cache tree? and when it retrieve from it?\n\ncache-tree is built from scratch in some cases, when we know HEAD (or\nsome tree) matches index exactly (e.g. reset --hard). Usually it's\nonly built up at commit time (update_main_cache_tree in\nbuiltin/commit.c).\n-- \nDuy\n"},{"id":"187563","messageId":"CAKTdtZk4FJD9qXEybpN01+S=5fOm=4AbOp8trFr5c6Uxbfykkg@mail.gmail.com","threadId":"30012","inReplyTo":"CACsJy8AYs5bzRnhRj_R33qTt-2gPh-rJaO0=1iTva9n14wHB4w@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-23T10:27:32Z","receivedAt":"2012-03-23T10:27:32Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hi Nguyen, Jakub\n\nThank you for your explanations.\n\nJust clarify question about track updated files:\n\nOn Fri, Mar 23, 2012 at 12:30 PM, Nguyen Thai Ngoc Duy\n wrote:\n> On Fri, Mar 23, 2012 at 3:32 AM, elton sky wrote:\n>> Got a few questions:\n>>\n>> 1. index is used for building next commit, so it should only include\n>> files created/modified/deleted. But I see it has all entries for\n>> current working dir. why?\n>\n> Jakub has answered this question.\n>\n>> 2. From read_index_from() I see the whole index is read into mem, and\n>> write one by one (entry/ext) back to disk. This makes sense. But why\n>> we have to compute Sha1 for all entries, especially unchanged entries?\n>\n> To catch disk corruption. If a bit is flipped anywhere in the index\n> and we do not detect it, we may end up creating broken commits.\n>\n>> 3. how does git track updated files? Does it compare the ts between\n>> working dir and index ? Or they are recorded somewhere?\n>\n> Check out refresh_cache_ent. At the beginning of most commands, they\n> call refresh_index() or refresh_cache(), which checks a file's mtime\n> against one stored in index (different means updated). In the worst\n> scenario, refresh_cache_ent may call ce_compare_data(), which computes\n> SHA-1 of the specified file and compare it with one stored in index.\n>\n\nThis means working dir will compare each entry in index on mtime\nfield, to find out if it's updated. The complexity for this operation\nis O(nlogn). I assume the way of this checking is: it loops through\nentries in the index, for each entry, it searches in working dir and\ncompare the mtime.\n\nBecause current index is a single steam of file, when it writes back\nit has to write back everything sequentially. So we have to do\nchecksum for every entry. And I suppose this process is more time\nconsuming than previous step.\n\nIf we use a tree format, still, when looking for updated files, time\ncomplexity is O(nlogn), i.e. we traverse the index entries and for\neach entry we refer back to working dir. However, when we write index\nback, we only need to recompute and write updated file nodes, but not\nall entries. Total processing time benefit from here.\n\nPlease correct me if I am wrong.\n\n-Elton\n\n\n>> 4. When does git insert to cache tree? and when it retrieve from it?\n>\n> cache-tree is built from scratch in some cases, when we know HEAD (or\n> some tree) matches index exactly (e.g. reset --hard). Usually it's\n> only built up at commit time (update_main_cache_tree in\n> builtin/commit.c).\n> --\n> Duy\n"},{"id":"187565","messageId":"CACsJy8CU_q+3ROO9z5nHe8NZDjTD4mvnEUP7C0+T3u3bRD11rQ@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZk4FJD9qXEybpN01+S=5fOm=4AbOp8trFr5c6Uxbfykkg@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-23T11:24:28Z","receivedAt":"2012-03-23T11:24:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Mar 23, 2012 at 5:27 PM, elton sky wrote:\n> On Fri, Mar 23, 2012 at 12:30 PM, Nguyen Thai Ngoc Duy\n> wrote:\n>> On Fri, Mar 23, 2012 at 3:32 AM, elton sky wrote:\n>>> 3. how does git track updated files? Does it compare the ts between\n>>> working dir and index ? Or they are recorded somewhere?\n>>\n>> Check out refresh_cache_ent. At the beginning of most commands, they\n>> call refresh_index() or refresh_cache(), which checks a file's mtime\n>> against one stored in index (different means updated). In the worst\n>> scenario, refresh_cache_ent may call ce_compare_data(), which computes\n>> SHA-1 of the specified file and compare it with one stored in index.\n>>\n>\n> This means working dir will compare each entry in index on mtime\n> field, to find out  if it's updated. The complexity for this operation\n> is O(nlogn). I assume the way of this checking is: it loops through\n> entries in the index, for each entry, it searches in working dir and\n> compare the mtime.\n>\n> Because current index is a single steam of file, when it writes back\n> it has to write back everything sequentially. So we have to do\n> checksum for every entry. And I suppose this process is more time\n> consuming than previous step.\n\nThe previous step is pretty fast on Linux in hot cache case. I don't\nthink we need to care about that. Some commands only care a\nsubdirectory (for example \"git diff -- path/to/here\") and only refresh\nentries within that subdirectory, which further reduces refresh cost.\n\nWhich reminds me, we cannot abandon current index format. Users should\nbe allowed to choose which format to use. It may be hard to keep the\ncode support two formats while still taking advantage of the new one.\nMaybe you could internally convert old format to new one in memory so\nthat git code only has to deal with one format, but that adds more\ncost on using old format. I don't know..\n\n> If we use a tree format, still, when looking for updated files, time\n> complexity is O(nlogn), i.e. we traverse the index entries and for\n> each entry we refer back to working dir. However, when we write index\n> back, we only need to recompute and write updated file nodes, but not\n> all entries. Total processing time benefit from here.\n\nYes. And if you compute checksum per-entry, not as a whole file, then\nwhen you read an entry, you only need to verify checksum of that entry\n(and index header of course). That reduces reading cost. But that\nincreases space (20-byte per entry if you stick with SHA-1). Maybe we\ncould do checksum per group (or tree) instead as a trade off between\nspace/time.\n-- \nDuy\n"},{"id":"187631","messageId":"CACsJy8C=4WaN4MZrZMaD3FqZrF2jCP5sm0F0SpDvzQnYfka9Ew@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZmLOzAgG0uCDcVr+O41XPX-XnoVZjsZWPN-BLjq2oG-7A@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-24T08:58:46Z","receivedAt":"2012-03-24T08:58:46Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 24, 2012 at 2:50 PM, elton sky wrote:\n> Thanks again Nguyen,\n>\n>> Which reminds me, we cannot abandon current index format. Users should\n>> be allowed to choose which format to use. It may be hard to keep the\n>> code support two formats while still taking advantage of the new one.\n>> Maybe you could internally convert old format to new one in memory so\n>> that git code only has to deal with one format, but that adds more\n>> cost on using old format. I don't know..\n>\n> I understand we should allow user to switch between old & new format.\n> But I guess that should only happens when user init a working dir,\n> isn't it? Otherwise I have to transform them back n forth. If a user\n> chooses to use old format, I assume their repository is not large, so\n> there should not be big delay for new format.\n\nUsers may choose to stick with old format because other git tools rely\non that (or they want to use older git versions at the same time).\nNote that current index works \"fine\" with ~50k files in working\ndirectory. Not huge, but not small either. Overhead on old format\nshould be reasonable.\n-- \nDuy\n"},{"id":"187718","messageId":"CAKTdtZkx+7iU5T4oBNDEx-A5cgZCLU9ocdXmC9jRbD39J1zb3Q@mail.gmail.com","threadId":"30012","inReplyTo":"CACsJy8D85thmK_5jLC7MxJtsitLr=zphKiw2miwPu7Exf7ty=Q@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-26T12:36:59Z","receivedAt":"2012-03-26T12:36:59Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hi Nguyen,\n\nOn Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy\n wrote:\n> (I think this should be on git@vger as there are many experienced devs there)\n>\n> On Sun, Mar 25, 2012 at 11:13 AM, elton sky wrote:\n>> About the new format:\n>>\n>> The index is a single file. Entries in the index still stored\n>> sequentially as old format. The difference is they are grouped into\n>> blocks. A block contains many entries and they are ordered by names.\n>> Blocks are also ordered by the name of the first entry. Each block\n>> contains a sha1 for entries in it.\n>\n> If I remove an entry in the first block, because blocks are of fixed\n> size, you would need to shift all entries up by one, thus update all\n> blocks?\n>\n\nWe need some GC here. I am not moving all blocks. Rather I would\nconsider merge or recycle the block. In a simple case if a block\nbecomes empty, I ll change the offset of new block in the header point\nto this block, and make this block points to the original offset of\nnew block. In this way, I keep the list of empty blocks I can reuse.\nIf a block is not empty but not full, we better merge it with adjacent\nblock for efficiency. But I don't know an light way to handle that\nwhen refreshing index. But we can always run a background thread to\nrebuild the index, at some stage, while system is quiet.\n\n> Also note the sequence format means duplication because we always\n> store full path.\n\nYou are right, this keeps the size of the index as current system. Use\na tree will save disk space for sure. Need think more about this.\n\n> --\n> Duy\n\nAttach my previous email here:\n\nThe goal of this project is :\n1. verify checksum for only necessary part of index\n2. keep the time complexity of most git-app below logn\n\nAbout the new format:\n\nThe index is a single file. Entries in the index still stored\nsequentially as old format. The difference is they are grouped into\nblocks. A block contains many entries and they are ordered by names.\nBlocks are also ordered by the name of the first entry. Each block\ncontains a sha1 for entries in it.\nFor using a binary search to locate the block for an entry, the\noffsets of blocks are stored in the header of the index. We reserve\n100 spaces for block offsets in the header. More offsets are stored in\na meta block (see below) afterwards. An offset of the first meta block\nis stored.\nThe checksum is computed on block. After we locate the block, the\nchecksum is recomputed for the block. And only the this block will be\nread and write back later. As the block is read into ram, it is easy\nto do a binary search for entries in a block when they are in ram.\nWhen the index doesn't have many entries, it works very similar with\ncurrent format. When more entries git-added, blocks will come into\nplay.\n\nFormat:\n\nHead:\n* 4-byte signature\n* 4-byte version num\n* 4-byte num of entries blocks\n* 4-byte offset for new block\n* list of offsets for blocks (e.g. 96, 14096, 8192, ..) : For binary\nsearch. Each offset is 8 bytes, we reserve 100 x 4 = 400 bytes for\nfirst 100 blocks. More offsets (if applicable) will be stored in a\nmeta blocks.\n* 4-byte offset to the first meta block\n* 20-byte sha1 for above and meta blocks\n\nList of Blocks:\n* sha1 for all entries\n* list of entries\n\nMeta block:\n* offset to next meta block\n* list of offsets\n\nExtensions:\n      TBD. Have not hacked cache tree yet. Need more knowledge of cache tree...\n\n\nBlock Split & Delete:\n      TBD.\n\n\n-Elton\n"},{"id":"187719","messageId":"CAKTdtZnsiP9VO2Us6dF760SFnEbpVgsAhcuOjOxuzBZxDODizQ@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZkx+7iU5T4oBNDEx-A5cgZCLU9ocdXmC9jRbD39J1zb3Q@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-26T12:41:32Z","receivedAt":"2012-03-26T12:41:32Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"As the previous email is hidden in the trimmed area, just resend it:\n\n\nAbout the new format:\n\nThe index is a single file. Entries in the index still stored\nsequentially as old format. The difference is they are grouped into\nblocks. A block contains many entries and they are ordered by names.\nBlocks are also ordered by the name of the first entry. Each block\ncontains a sha1 for entries in it.\nFor using a binary search to locate the block for an entry, the\noffsets of blocks are stored in the header of the index. We reserve\n100 spaces for block offsets in the header. More offsets are stored in\na meta block (see below) afterwards. An offset of the first meta block\nis stored.\nThe checksum is computed on block. After we locate the block, the\nchecksum is recomputed for the block. And only the this block will be\nread and write back later. As the block is read into ram, it is easy\nto do a binary search for entries in a block when they are in ram.\nWhen the index doesn't have many entries, it works very similar with\ncurrent format. When more entries git-added, blocks will come into\nplay.\n\nFormat:\n\nHead:\n- 4-byte signature\n- 4-byte version num\n- 4-byte num of entries blocks\n- 4-byte offset for new block\n- list of offsets for blocks (e.g. 96, 14096, 8192, ..) : For binary\nsearch. Each offset is 8 bytes, we reserve 100 x 4 = 400 bytes for\nfirst 100 blocks. More offsets (if applicable) will be stored in a\nmeta blocks.\n- 4-byte offset to the first meta block\n- 20-byte sha1 for above and meta blocks\n\nList of Blocks:\n- sha1 for all entries\n- list of entries\n\nMeta block:\n- offset to next meta block\n- list of offsets\n\nExtensions:\n      TBD. Have not hacked cache tree yet. Need more knowledge of cache tree...\n\n\nBlock Split & Delete:\n      TBD.\n\nRegards,\nElton\n"},{"id":"187723","messageId":"87iphrjv23.fsf@thomas.inf.ethz.ch","threadId":"30012","inReplyTo":"CAKTdtZkx+7iU5T4oBNDEx-A5cgZCLU9ocdXmC9jRbD39J1zb3Q@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-03-26T14:28:20Z","receivedAt":"2012-03-26T14:28:20Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"elton sky writes:\n\n> On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy\n> wrote:\n>> (I think this should be on git@vger as there are many experienced devs there)\n>>\n>> On Sun, Mar 25, 2012 at 11:13 AM, elton sky wrote:\n>>> About the new format:\n>>>\n>>> The index is a single file. Entries in the index still stored\n>>> sequentially as old format. The difference is they are grouped into\n>>> blocks. A block contains many entries and they are ordered by names.\n>>> Blocks are also ordered by the name of the first entry. Each block\n>>> contains a sha1 for entries in it.\n>>\n>> If I remove an entry in the first block, because blocks are of fixed\n>> size, you would need to shift all entries up by one, thus update all\n>> blocks?\n>\n> We need some GC here. I am not moving all blocks. Rather I would\n> consider merge or recycle the block. In a simple case if a block\n> becomes empty, I ll change the offset of new block in the header point\n> to this block, and make this block points to the original offset of\n> new block. In this way, I keep the list of empty blocks I can reuse.\n[...]\n\nDoesn't that venture into database land?\n\nIf we go that far, wouldn't it be better to use a proper database\nlibrary? All other things being equal, writing such complex code from\nscratch is probably not a good idea.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"187727","messageId":"CACsJy8CsdZpQUQ7ydM1fOpSomm6+LyACCR83ccncVtUk+HbLKA@mail.gmail.com","threadId":"30012","inReplyTo":"87iphrjv23.fsf@thomas.inf.ethz.ch","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-26T15:25:59Z","receivedAt":"2012-03-26T15:25:59Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast wrote:\n> elton sky writes:\n>\n>> On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy\n>> wrote:\n>>> (I think this should be on git@vger as there are many experienced devs there)\n>>>\n>>> On Sun, Mar 25, 2012 at 11:13 AM, elton sky wrote:\n>>>> About the new format:\n>>>>\n>>>> The index is a single file. Entries in the index still stored\n>>>> sequentially as old format. The difference is they are grouped into\n>>>> blocks. A block contains many entries and they are ordered by names.\n>>>> Blocks are also ordered by the name of the first entry. Each block\n>>>> contains a sha1 for entries in it.\n>>>\n>>> If I remove an entry in the first block, because blocks are of fixed\n>>> size, you would need to shift all entries up by one, thus update all\n>>> blocks?\n>>\n>> We need some GC here. I am not moving all blocks. Rather I would\n>> consider merge or recycle the block. In a simple case if a block\n>> becomes empty, I ll change the offset of new block in the header point\n>> to this block, and make this block points to the original offset of\n>> new block. In this way, I keep the list of empty blocks I can reuse.\n> [...]\n>\n> Doesn't that venture into database land?\n>\n> If we go that far, wouldn't it be better to use a proper database\n> library?  All other things being equal, writing such complex code from\n> scratch is probably not a good idea.\n\nIf there's a library that fits our needs (including linking\nstatically). I think we've come close to sqlite file format [1]. But\nsqlite comes with sql engine, transactional updates... that we don't\nneed. Another obvious source for inspiration is file systems, but I\ndare not go that way.\n\n[1] http://www.sqlite.org/fileformat2.html\n-- \nDuy\n"},{"id":"187730","messageId":"CAJo=hJsPgUZi2qMc5aDUn0+o5=9n7pBS+yWBASfqtov8WuFBRA@mail.gmail.com","threadId":"30012","inReplyTo":"CACsJy8CsdZpQUQ7ydM1fOpSomm6+LyACCR83ccncVtUk+HbLKA@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-03-26T16:08:12Z","receivedAt":"2012-03-26T16:08:12Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Mar 26, 2012 at 08:25, Nguyen Thai Ngoc Duy wrote:\n> On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast wrote:\n>> elton sky writes:\n>>\n>>> On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy\n>>> wrote:\n>>>> (I think this should be on git@vger as there are many experienced devs there)\n>>>>\n>>>> On Sun, Mar 25, 2012 at 11:13 AM, elton sky wrote:\n>>>>> About the new format:\n>>>>>\n>>>>> The index is a single file. Entries in the index still stored\n>>>>> sequentially as old format. The difference is they are grouped into\n>>>>> blocks. A block contains many entries and they are ordered by names.\n>>>>> Blocks are also ordered by the name of the first entry. Each block\n>>>>> contains a sha1 for entries in it.\n>>>>\n>>>> If I remove an entry in the first block, because blocks are of fixed\n>>>> size, you would need to shift all entries up by one, thus update all\n>>>> blocks?\n>>>\n>>> We need some GC here. I am not moving all blocks. Rather I would\n>>> consider merge or recycle the block. In a simple case if a block\n>>> becomes empty, I ll change the offset of new block in the header point\n>>> to this block, and make this block points to the original offset of\n>>> new block. In this way, I keep the list of empty blocks I can reuse.\n>> [...]\n>>\n>> Doesn't that venture into database land?\n>>\n>> If we go that far, wouldn't it be better to use a proper database\n>> library?  All other things being equal, writing such complex code from\n>> scratch is probably not a good idea.\n>\n> If there's a library that fits our needs (including linking\n> statically). I think we've come close to sqlite file format [1]. But\n> sqlite comes with sql engine, transactional updates... that we don't\n> need. Another obvious source for inspiration is file systems, but I\n> dare not go that way.\n>\n> [1] http://www.sqlite.org/fileformat2.html\n\nOr use LevelDb[2]. Its BSD license. Uses an immutable file format, but\nwrites updates to new smaller files and eventually collapses\neverything back together into a bigger file. This can be a\ndramatically simpler approach than dealing with your own free block\nsystem inside of a single file. Its only real downside is needing to\nperiodically pay a penalty to rewrite the whole index. But this\nrewrite is going to be faster than the time it takes to rewrite the\npack files for the same repository, which git gc or git repack\nhandles. So I don't think its actually a problem for the index.\n\nYou might even be able to take a two level approach to compacting the\nLevelDb database (or something like it). In a minor compaction you\ncompact all of the files except the huge base file, leaving you with 2\nfiles. A huge base file that contains the first tree the user checked\nout, and a second smaller file containing any differences they have\nsince the initial checkout (this may just be updated stat data for a\nhandful of files that differed across two branches as they switched\nback and forth). During a git gc or git repack, add a new stage to\ncollapse the base file and everything else into a single new base file\nas a major compaction.\n\n[2] http://code.google.com/p/leveldb/\n"},{"id":"187733","messageId":"CACsJy8AqQdWO4E2oYTMLbpYhxobH8iXE-jXPoj2BcEGtfh+T=Q@mail.gmail.com","threadId":"30012","inReplyTo":"87iphrjv23.fsf@thomas.inf.ethz.ch","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-26T16:19:36Z","receivedAt":"2012-03-26T16:19:36Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast wrote:\n> Doesn't that venture into database land?\n\nHow about this (a bit like memory management). Maybe it's simpler than\na database and fits us better.\n\nThe header consists of crc32 and three uint32_t, one points to the\nroot tree, one the first extension block, the last one the free list\nat the end of the file. The rest of the file contains sizable blocks.\nThere can be free space between them. Free spaces (offset and size)\nare recorded at the end of the file, pointed in header. The header's\ncrc32 covers the header and free list.\n\nWhen we need a new block, we look up in free list. If we cannot find a\nsuitable space, we append to the end of the file (moving free list\nfurther to keep it always the end of the file). Removing a block means\nmarking it in free list. We only truncate if there is free space at\nthe end. Operations that we know will scratch the whole index are our\nopportunity to rewrite the index and make it compact again. No random\ngarbage collection (iow disk is cheap).\n\nA block starts with a signature (a tree block, or an extension...). A\ntree block consists of:\n\n - uint32_t tree object's size\n - sha-1 of tree object\n - crc32 of the rest of the block except tree object\n - maybe reference counter of a block can be refered by many blocks??\n - tree object (i.e. something that tree-walk.c can parse)\n - other index attributes, stored separately in the same order as in\ntree object above, uint32_t block offset of subdirectories.\n\nAn extension block basically consists of what we have now in an\nextension plus uint32_t offset to the next extension block, so we can\nkeep track of all extensions. crc32 is used for extension blocks.\n\nThis way we only need to verify checksum of the header (and free list)\nand blocks we visit. We don't need cache-tree extension because it's\npart of the format. There will be headache with unpack-trees.c because\nof entry order change. But in the end we would use the same order tree\nobjects are using now, much simpler for us.\n-- \nDuy\n"},{"id":"187805","messageId":"CAKTdtZngYaTCwd5cri=XjUu3-o44ECjDotrDBNxqYL-Kcsosnw@mail.gmail.com","threadId":"30012","inReplyTo":"CAJo=hJsPgUZi2qMc5aDUn0+o5=9n7pBS+yWBASfqtov8WuFBRA@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-27T02:49:26Z","receivedAt":"2012-03-27T02:49:26Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Thanks Shawn,\n\n> Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but\n> writes updates to new smaller files and eventually collapses\n> everything back together into a bigger file. This can be a\n> dramatically simpler approach than dealing with your own free block\n> system inside of a single file. Its only real downside is needing to\n> periodically pay a penalty to rewrite the whole index. But this\n> rewrite is going to be faster than the time it takes to rewrite the\n> pack files for the same repository, which git gc or git repack\n> handles. So I don't think its actually a problem for the index.\n>\n> You might even be able to take a two level approach to compacting the\n> LevelDb database (or something like it). In a minor compaction you\n> compact all of the files except the huge base file, leaving you with 2\n> files. A huge base file that contains the first tree the user checked\n> out, and a second smaller file containing any differences they have\n> since the initial checkout (this may just be updated stat data for a\n> handful of files that differed across two branches as they switched\n> back and forth). During a git gc or git repack, add a new stage to\n> collapse the base file and everything else into a single new base file\n> as a major compaction.\n>\n> [2] http://code.google.com/p/leveldb/\n\nI don't know leveldb, but like to have a look.\nJust realize this solution is kinda popular. HDFS also uses the\nsimilar image file with edit file format for its file block index.\n"},{"id":"187807","messageId":"CAKTdtZnxSRffZ5xAq+SgW6fmy+b3P2Fu3AZmBB1jmGca6HmJAw@mail.gmail.com","threadId":"30012","inReplyTo":"CACsJy8AqQdWO4E2oYTMLbpYhxobH8iXE-jXPoj2BcEGtfh+T=Q@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-03-27T03:20:07Z","receivedAt":"2012-03-27T03:20:07Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hi Nguyen,\n\nThanks for the idea. just a few questions\n\nOn Tue, Mar 27, 2012 at 3:19 AM, Nguyen Thai Ngoc Duy wrote:\n> On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast wrote:\n>> Doesn't that venture into database land?\n>\n> How about this (a bit like memory management). Maybe it's simpler than\n> a database and fits us better.\n>\n> The header consists of crc32 and three uint32_t, one points to the\n> root tree, one the first extension block, the last one the free list\n> at the end of the file. The rest of the file contains sizable blocks.\n> There can be free space between them. Free spaces (offset and size)\n> are recorded at the end of the file, pointed in header. The header's\n> crc32 covers the header and free list.\n\nHow do you record free spaces at the end of file? Are you gonna have a\nfixed size for the index and reserve space for free spaces offsets.\n\n>\n> When we need a new block, we look up in free list. If we cannot find a\n> suitable space, we append to the end of the file (moving free list\n> further to keep it always the end of the file). Removing a block means\n> marking it in free list. We only truncate if there is free space at\n> the end. Operations that we know will scratch the whole index are our\n> opportunity to rewrite the index and make it compact again. No random\n> garbage collection (iow disk is cheap).\n>\n\nI agree with you. Maybe we just ignore free spaces in the index and\nlet a background thread to compact it.\n\n> A block starts with a signature (a tree block, or an extension...). A\n> tree block consists of:\n>\n>  - uint32_t tree object's size\n>  - sha-1 of tree object\n>  - crc32 of the rest of the block except tree object\n>  - maybe reference counter of a block can be refered by many blocks??\n>  - tree object (i.e. something that tree-walk.c can parse)\n\nDo you mean each block contains a tree and all its blobs? So the tree\nobject here, effectively a dir, also contains files in the dir ? In\nthis way, some blocks can be very big.\n\n>  - other index attributes, stored separately in the same order as in\n> tree object above, uint32_t block offset of subdirectories.\n\nThere can be many sub dirs some times. But maybe not a prob.\n\nAs tree object and  offset of subdirectories are variables, how do you\nmake a block resizable?\n\n>\n> An extension block basically consists of what we have now in an\n> extension plus uint32_t offset to the next extension block, so we can\n> keep track of all extensions. crc32 is used for extension blocks.\n>\n> This way we only need to verify checksum of the header (and free list)\n> and blocks we visit. We don't need cache-tree extension because it's\n> part of the format. There will be headache with unpack-trees.c because\n> of entry order change. But in the end we would use the same order tree\n> objects are using now, much simpler for us.\n> --\n> Duy\n\nCheers,\nElton\n"},{"id":"187810","messageId":"CAFfmPPM_GOkOp6-tE2=YxdrZq6TL3s4EgOjXdRKf8+ffMD29xg@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZngYaTCwd5cri=XjUu3-o44ECjDotrDBNxqYL-Kcsosnw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"David Barr","fromEmail":"davidbarr@google.com","sentAt":"2012-03-27T03:34:44Z","receivedAt":"2012-03-27T03:34:44Z","isPatch":false,"sender":{"key":"davidbarr@google.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"On Tue, Mar 27, 2012 at 1:49 PM, elton sky wrote:\n> Thanks Shawn,\n>\n>> Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but\n>> writes updates to new smaller files and eventually collapses\n>> everything back together into a bigger file. This can be a\n>> dramatically simpler approach than dealing with your own free block\n>> system inside of a single file. Its only real downside is needing to\n>> periodically pay a penalty to rewrite the whole index. But this\n>> rewrite is going to be faster than the time it takes to rewrite the\n>> pack files for the same repository, which git gc or git repack\n>> handles. So I don't think its actually a problem for the index.\n>>\n>> You might even be able to take a two level approach to compacting the\n>> LevelDb database (or something like it). In a minor compaction you\n>> compact all of the files except the huge base file, leaving you with 2\n>> files. A huge base file that contains the first tree the user checked\n>> out, and a second smaller file containing any differences they have\n>> since the initial checkout (this may just be updated stat data for a\n>> handful of files that differed across two branches as they switched\n>> back and forth). During a git gc or git repack, add a new stage to\n>> collapse the base file and everything else into a single new base file\n>> as a major compaction.\n>>\n>> [2] http://code.google.com/p/leveldb/\n>\n> I don't know leveldb, but like to have a look.\n> Just realize this solution is kinda popular. HDFS also uses the\n> similar image file with edit file format for its file block index.\n\nAnother implementation in this general class is TinyCDB[1].\nIt is <1600 lines of plain C. Too few to be complete?\nIt is a derivative of DJB's CDB[2].\n\n[1] http://www.corpit.ru/mjt/tinycdb.html\n[2] http://cr.yp.to/cdb.html\n--\nDavid Barr\n"},{"id":"187833","messageId":"CACsJy8BZVFKZvd1=jz8PoCvTKjX6LorRidJgTxsjFUGfBUai+w@mail.gmail.com","threadId":"30012","inReplyTo":"CAJo=hJsPgUZi2qMc5aDUn0+o5=9n7pBS+yWBASfqtov8WuFBRA@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-27T06:31:54Z","receivedAt":"2012-03-27T06:31:54Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Mar 26, 2012 at 11:08 PM, Shawn Pearce wrote:\n>> [1] http://www.sqlite.org/fileformat2.html\n>\n> Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but\n> writes updates to new smaller files and eventually collapses\n> everything back together into a bigger file. This can be a\n> dramatically simpler approach than dealing with your own free block\n> system inside of a single file. Its only real downside is needing to\n> periodically pay a penalty to rewrite the whole index. But this\n> rewrite is going to be faster than the time it takes to rewrite the\n> pack files for the same repository, which git gc or git repack\n> handles. So I don't think its actually a problem for the index.\n\nCool. I had an experiment with it. A database is created where are\nkeys `git ls-files` on linux-2.6. A few things after the experiment:\n\n - we need to link to libstdc++.so. I still hope to avoid any new\nruntime dependencies\n - I use gettimeofday to time some operations. On linux-2.6,\nread_cache() costs 27ms. leveldb_open() alone takes 90ms. Iterating\nover all keys takes ~200ms.\n\nPerformance wise it does not look very good but maybe I'm just not\ndoing it right.\n\n> [2] http://code.google.com/p/leveldb/\n-- \nDuy\n"},{"id":"187834","messageId":"CACsJy8BfCpH3jtfaOyyAgjH3P5fv4FYjboqjoFYF2GiG44TmoA@mail.gmail.com","threadId":"30012","inReplyTo":"CAFfmPPM_GOkOp6-tE2=YxdrZq6TL3s4EgOjXdRKf8+ffMD29xg@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-27T06:33:33Z","receivedAt":"2012-03-27T06:33:33Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 27, 2012 at 10:34 AM, David Barr wrote:\n> Another implementation in this general class is TinyCDB[1].\n> It is <1600 lines of plain C. Too few to be complete?\n> It is a derivative of DJB's CDB[2].\n>\n> [1] http://www.corpit.ru/mjt/tinycdb.html\n\n\"CDB is a constant database, that is, it cannot be updated at a\nruntime, only rebuilt.\". It does not sound promising to me. I have not\nread the description carefully though.\n\n> [2] http://cr.yp.to/cdb.html\n-- \nDuy\n"},{"id":"187835","messageId":"CACsJy8BjYLAKqFDeGRyUj+SDKOTRbjW8shomhnhORM082HM9yw@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZnxSRffZ5xAq+SgW6fmy+b3P2Fu3AZmBB1jmGca6HmJAw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-03-27T06:43:27Z","receivedAt":"2012-03-27T06:43:27Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 27, 2012 at 10:20 AM, elton sky wrote:\n> On Tue, Mar 27, 2012 at 3:19 AM, Nguyen Thai Ngoc Duy wrote:\n>> The header consists of crc32 and three uint32_t, one points to the\n>> root tree, one the first extension block, the last one the free list\n>> at the end of the file. The rest of the file contains sizable blocks.\n>> There can be free space between them. Free spaces (offset and size)\n>> are recorded at the end of the file, pointed in header. The header's\n>> crc32 covers the header and free list.\n>\n> How do you record free spaces at the end of file? Are you gonna have a\n> fixed size for the index and reserve space for free spaces offsets.\n\nA list of (offset,size) with (0,0) to terminate. No index can shrink\nor expand at will. Free list is always at the end of the index.\n\n>> A block starts with a signature (a tree block, or an extension...). A\n>> tree block consists of:\n>>\n>>  - uint32_t tree object's size\n>>  - sha-1 of tree object\n>>  - crc32 of the rest of the block except tree object\n>>  - maybe reference counter of a block can be refered by many blocks??\n>>  - tree object (i.e. something that tree-walk.c can parse)\n>\n> Do you mean each block contains a tree and all its blobs? So the tree\n> object here, effectively a dir, also contains files in the dir ? In\n> this way, some blocks can be very big.\n\nNo, the tree object contains pathname, mode and SHA-1 of its entries,\none level only (try \"git ls-tree HEAD\"). If an entry is a directory\nand we have not built it yet, we won't have its sha-1, so it will be\nzero (similar to invalid cache-tree).\n\n>>  - other index attributes, stored separately in the same order as in\n>> tree object above, uint32_t block offset of subdirectories.\n>\n> There can be many sub dirs some times. But maybe not a prob.\n>\n> As tree object and  offset of subdirectories are variables, how do you\n> make a block resizable?\n\nIf there are free space right after it, it can be expanded. Otherwise\nwe need to move the block elsewhere and update its parent about its\nnew offset, then mark where the block was as free space.\n-- \nDuy\n"},{"id":"188048","messageId":"20120329094554.GA11603@sigill.intra.peff.net","threadId":"30012","inReplyTo":"CACsJy8BfCpH3jtfaOyyAgjH3P5fv4FYjboqjoFYF2GiG44TmoA@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-03-29T09:45:54Z","receivedAt":"2012-03-29T09:45:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 27, 2012 at 01:33:33PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> On Tue, Mar 27, 2012 at 10:34 AM, David Barr wrote:\n> > Another implementation in this general class is TinyCDB[1].\n> > It is <1600 lines of plain C. Too few to be complete?\n> > It is a derivative of DJB's CDB[2].\n> >\n> > [1] http://www.corpit.ru/mjt/tinycdb.html\n> \n> \"CDB is a constant database, that is, it cannot be updated at a\n> runtime, only rebuilt.\". It does not sound promising to me. I have not\n> read the description carefully though.\n\nNo, you are right. I did some work with cdb many years ago. It optimizes\nfor lookup by spending time building an optimal hash table at generation\ntime. There is no way to add or modify an entry short of rewriting the\ncomplete contents of the database, which is exactly what we are trying\nto get away from with the current index format.\n\n-Peff\n"},{"id":"188305","messageId":"CAKTdtZkSEs7Z+0NrfEaFDt-LJEPCLg5FhHgSGAsF32gqQB+DCg@mail.gmail.com","threadId":"30012","inReplyTo":"CACsJy8BjYLAKqFDeGRyUj+SDKOTRbjW8shomhnhORM082HM9yw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-04-02T11:50:53Z","receivedAt":"2012-04-02T11:50:53Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hi Nguyen,\n\nStill have some questions on your idea:\n\nOn Tuesday, March 27, 2012, Nguyen Thai Ngoc Duy wrote:\n>\n> On Tue, Mar 27, 2012 at 10:20 AM, elton sky wrote:\n> > On Tue, Mar 27, 2012 at 3:19 AM, Nguyen Thai Ngoc Duy wrote:\n> >> The header consists of crc32 and three uint32_t, one points to the\n> >> root tree, one the first extension block, the last one the free list\n> >> at the end of the file. The rest of the file contains sizable blocks.\n> >> There can be free space between them. Free spaces (offset and size)\n> >> are recorded at the end of the file, pointed in header. The header's\n> >> crc32 covers the header and free list.\n> >\n> > How do you record free spaces at the end of file? Are you gonna have a\n> > fixed size for the index and reserve space for free spaces offsets.\n>\n> A list of (offset,size) with (0,0) to terminate. No index can shrink\n> or expand at will. Free list is always at the end of the index.\n>\n> >> A block starts with a signature (a tree block, or an extension...). A\n> >> tree block consists of:\n> >>\n> >>  - uint32_t tree object's size\n> >>  - sha-1 of tree object\n> >>  - crc32 of the rest of the block except tree object\n> >>  - maybe reference counter of a block can be refered by many blocks??\n> >>  - tree object (i.e. something that tree-walk.c can parse)\n> >\n> > Do you mean each block contains a tree and all its blobs? So the tree\n> > object here, effectively a dir, also contains files in the dir ? In\n> > this way, some blocks can be very big.\n>\n> No, the tree object contains pathname, mode and SHA-1 of its entries,\n> one level only (try \"git ls-tree HEAD\"). If an entry is a directory\n> and we have not built it yet, we won't have its sha-1, so it will be\n> zero (similar to invalid cache-tree).\n>\n\nCorrect me if I am wrong, I assume:\n* Although you only listed attributes in tree block, in index, we have\nboth tree and blob block.\n* Sha1 of a tree block is computed by hashing all the Sha1s of blobs\nand sub trees in the directory.\n* Like cache tree struct, each tree object contains list of offsets to\nchildren blocks.\n\nHow do you store blob blocks ? Is each blob object a block? just like\na tree object is a block? If so, each blob contains a sha1, the\noverhead is high?\n\nIf we compute hash for a tree, and this tree happen to have 500\nchildren do I have to access all 500 blocks to get their Sha1s?\n\n\n>\n> >>  - other index attributes, stored separately in the same order as in\n> >> tree object above, uint32_t block offset of subdirectories.\n> >\n> > There can be many sub dirs some times. But maybe not a prob.\n> >\n> > As tree object and  offset of subdirectories are variables, how do you\n> > make a block resizable?\n>\n> If there are free space right after it, it can be expanded. Otherwise\n> we need to move the block elsewhere and update its parent about its\n> new offset, then mark where the block was as free space.\n> --\n> Duy\n\n\n\nAlso I ran some quick test on git-add over kernel 2.6. When I do \"time\ngit add .\":time git add .\n\ncmd_add: validate_pathspec takes : 0 ms\nread_index_from: xmmap&close takes : 0 ms\nread_index_from: verify_hdr takes : 26 ms\nread_index_from: create inmem struct takes : 4 ms\nread_index: read_index_from takes : 31 ms\nread_directory: qsort takes : 0 ms\nfill_directory: read_directory takes : 97 ms\ncmd_add: prune dir takes : 0 ms\ncmd_add: add_files_to_cache takes : 37 ms\ncmd_add: add_files takes : 0 ms\n\nreal 0m0.172s\nuser 0m0.120s\nsys 0m0.050s\n\nAnd when I ran \"time git add arch/ia64\" :\n\ncmd_add: validate_pathspec takes : 0 ms\nread_index_from: xmmap&close takes : 0 ms\nread_index_from: verify_hdr takes : 20 ms\nread_index_from: create inmem struct takes : 4 ms\nread_index: read_index_from takes : 25 ms\nread_directory: read_directory_recursive takes : 10 ms\nread_directory: qsort takes : 0 ms\nfill_directory: read_directory takes : 10 ms\ncmd_add: fill_directory takes : 10 ms\ncmd_add: prune dir takes : 0 ms\ncmd_add: add_files_to_cache takes : 1 ms\n\nreal 0m0.043s\nuser 0m0.040s\nsys 0m0.000s\n\nIn both cases, the time for sha1 is quite stable (~20ms).\nfill_directory drops as I specify a sub directory, which make sense.\nAs Junio suggested, the sha1 time (verify_hdr) is a mix a read and\nsha1. And this part is our focus to optimize, isn't it? But, as growth\nof the whole repo, the processing time is getting dominated by\nfill_directory (if we use '.', it takes 97ms) rather than verify_hdr.\nIn current system, The time complexity for fill_directory is nlogn (n\nis number of objects). git recursively go thru sub directories and\nfiles in it and check against current index. When searching index, it\nuses binary search which makes it lg(n). If this is the case, will use\na producer/consumer model help?\n\nCheers,\nElton\n"},{"id":"188306","messageId":"20120402123146.GA24813@do","threadId":"30012","inReplyTo":"CAKTdtZkSEs7Z+0NrfEaFDt-LJEPCLg5FhHgSGAsF32gqQB+DCg@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-02T12:31:46Z","receivedAt":"2012-04-02T12:31:46Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Apr 02, 2012 at 09:50:53PM +1000, elton sky wrote:\n> Hi Nguyen,\n> \n> Still have some questions on your idea:\n> \n> On Tuesday, March 27, 2012, Nguyen Thai Ngoc Duy wrote:\n> > >> A block starts with a signature (a tree block, or an extension...). A\n> > >> tree block consists of:\n> > >>\n> > >>  - uint32_t tree object's size\n> > >>  - sha-1 of tree object\n> > >>  - crc32 of the rest of the block except tree object\n> > >>  - maybe reference counter of a block can be refered by many blocks??\n> > >>  - tree object (i.e. something that tree-walk.c can parse)\n> > >\n> > > Do you mean each block contains a tree and all its blobs? So the tree\n> > > object here, effectively a dir, also contains files in the dir ? In\n> > > this way, some blocks can be very big.\n> >\n> > No, the tree object contains pathname, mode and SHA-1 of its entries,\n> > one level only (try \"git ls-tree HEAD\"). If an entry is a directory\n> > and we have not built it yet, we won't have its sha-1, so it will be\n> > zero (similar to invalid cache-tree).\n> >\n> \n> Correct me if I am wrong, I assume:\n> * Although you only listed attributes in tree block, in index, we have\n> both tree and blob block.\n\nIn current index, tree is implied in path names. We only store blob sha-1.\n\n> * Sha1 of a tree block is computed by hashing all the Sha1s of blobs\n> and sub trees in the directory.\n> * Like cache tree struct, each tree object contains list of offsets to\n> children blocks.\n> \n> How do you store blob blocks ? Is each blob object a block? just like\n> a tree object is a block? If so, each blob contains a sha1, the\n> overhead is high?\n> \n> If we compute hash for a tree, and this tree happen to have 500\n> children do I have to access all 500 blocks to get their Sha1s?\n\nWe don't store blobs in index. We only need their sha-1, which is\ncomputed and content stored in object database at \"git add\".\n\nBy the way, I revised my new index format a little bit, see the end of\nthis email. It may work, or may not. Food for thoughts.\n\n> Also I ran some quick test on git-add over kernel 2.6. When I do \"time\n> git add .\":time git add .\n> \n> cmd_add: validate_pathspec takes : 0 ms\n> read_index_from: xmmap&close takes : 0 ms\n> read_index_from: verify_hdr takes : 26 ms\n> read_index_from: create inmem struct takes : 4 ms\n> read_index: read_index_from takes : 31 ms\n> read_directory: qsort takes : 0 ms\n> fill_directory: read_directory takes : 97 ms\n> cmd_add: prune dir takes : 0 ms\n> cmd_add: add_files_to_cache takes : 37 ms\n> cmd_add: add_files takes : 0 ms\n> \n> real 0m0.172s\n> user 0m0.120s\n> sys 0m0.050s\n> \n> And when I ran \"time git add arch/ia64\" :\n> \n> cmd_add: validate_pathspec takes : 0 ms\n> read_index_from: xmmap&close takes : 0 ms\n> read_index_from: verify_hdr takes : 20 ms\n> read_index_from: create inmem struct takes : 4 ms\n> read_index: read_index_from takes : 25 ms\n> read_directory: read_directory_recursive takes : 10 ms\n> read_directory: qsort takes : 0 ms\n> fill_directory: read_directory takes : 10 ms\n> cmd_add: fill_directory takes : 10 ms\n> cmd_add: prune dir takes : 0 ms\n> cmd_add: add_files_to_cache takes : 1 ms\n> \n> real 0m0.043s\n> user 0m0.040s\n> sys 0m0.000s\n> \n> In both cases, the time for sha1 is quite stable (~20ms).\n> fill_directory drops as I specify a sub directory, which make sense.\n> As Junio suggested, the sha1 time (verify_hdr) is a mix a read and\n> sha1. And this part is our focus to optimize, isn't it?\n\nI think so. But until we can read just parts of index, we still have\nto verify integrity for the whole index, which takes more or less the\nsame amount of time you see and should be proportional to index size\n(or the number of entries in index). Either we shrink the index, or go\nwith cheaper checksum, or both.\n\n> But, as growth\n> of the whole repo, the processing time is getting dominated by\n> fill_directory (if we use '.', it takes 97ms) rather than verify_hdr.\n\n{read,fill}_directory is not always used (for example, \"git diff\" does\nnot need it). Meanwhile, as working directory grows, index size grows,\nverify_hdr() will take longer.\n\n> In current system, The time complexity for fill_directory is nlogn (n\n> is number of objects). git recursively go thru sub directories and\n> files in it and check against current index. When searching index, it\n> uses binary search which makes it lg(n). If this is the case, will use\n> a producer/consumer model help?\n\nI think fill_directory is dominated by kernel time (read_dir,\nstat...), there's little thing we can do there. Anyway I'm pretty sure\nfill_directory is out of scope. It's just one of the code that uses\nindex.\n\n-- 8< --\nGIT index format\n================\n\nThis format replaces the old \"DIRC\" format. Compared to the old\nformat, which is essentially a sorted list of pathnames, this one:\n\n - is tree-based\n - use crc32 as checksum\n - only verify integrity on parts that git accesses, instead of whole\n file\n - append changes to the end\n - allow index versioning\n\nUpdates can be made directly to the index by appending to the end. The\nindex traversed by locating the root tree block from the trailer. When\na path is updated, all related tree blocks are updated and appended to\nthe end, then a new trailer (with generation increased by one) is\nwritten to conclude the index.\n\nThe index size will increase continuously. At some point, we will need\nto repack it. Let assume a tree block is 64k on average and a path\ngenerally consists of 3 path components. That means an entry update\nadds 192k and we can do about 80 updates before index reaches 16M (in\naddition to initial index size).\n\nAt 16M or when trailer generation hits a limit (the limit can be\nconfigurable), we rewrite the index to reduce its size. Some heavy\noperations can also be used to rewrite index, such as checkout or\nreset.\n\nThe index integrity is verified by crc32. One crc32 covers header and\ntrailer. Each block has its own crc32. When the index is found\ncorrupt, we could try to roll back to latest good version by looking\nfor trailers from bottom up. Even when the index is not corrupt, users\ncan still look back this way for older index versions.\n\n= The git index file has the following format\n\n - A 8-byte header consisting of\n\n 4-byte signature:\n The signature is { 'T', 'R', 'E', 'E' }\n\n 4-byte version number:\n The current supported versions are 1.\n\n - A number of blocks of variable size\n\n 1-byte block type\n\n 3-byte content size in byte\n\n block content\n\n 4-byte crc32 of all above\n\n - A 18-byte trailer consisting of\n\n 4-byte trailer signature:\n The signature is { 'R', 'O', 'O', 'T' }\n\n 2-byte generation:\n The first trailer is 0, the second 1 and so on.\n\n 4-byte root block offset\n\n 4-byte extension table offset:\n Zero means no extension\n\n 4-byte checksum:\n CRC32 of the header and the trailer (excluding this field)\n\n== Tree block\n\n A tree block contains a (maybe invalid) tree object and extra\n information of its companion in working directory. Tree block has\n block type 'T'.\n\n Tree block content is basically the list of non-recursive entries in\n specified path, with all attributes we store in the index now. There\n are a few changes though to intergrate cache-tree and allow\n bsearch() on mmap'd block.\n\n A tree block content consists of\n\n - 4-byte tree object size\n\n - 20-byte SHA-1 of the cached tree object\n\n - a list attributes corresponding to tree object's item, in the same\n order. These attributes are the same as in DIRC entry format\n except that entry name is removed, and a tree block offset is\n added in case the item is a directory.\n\n 32-bit ctime seconds, the last time a file's metadata changed\n this is stat(2) data\n \n 32-bit ctime nanosecond fractions\n this is stat(2) data\n \n 32-bit mtime seconds, the last time a file's data changed\n this is stat(2) data\n \n 32-bit mtime nanosecond fractions\n this is stat(2) data\n \n 32-bit dev\n this is stat(2) data\n \n 32-bit ino\n this is stat(2) data\n \n 32-bit mode, split into (high to low bits)\n \n 4-bit object type\n valid values in binary are 1000 (regular file), 1010 (symbolic link)\n and 1110 (gitlink)\n \n 3-bit unused\n \n 9-bit unix permission. Only 0755 and 0644 are valid for regular files.\n Symbolic links and gitlinks have value 0 in this field.\n \n 32-bit uid\n this is stat(2) data\n \n 32-bit gid\n this is stat(2) data\n \n 32-bit file size\n This is the on-disk size from stat(2), truncated to 32-bit.\n \n 160-bit SHA-1 for the represented object if blobs or the offset\n to another tree block if trees\n\n A 32-bit 'flags' field split into (high to low bits)\n \n 1-bit assume-valid flag\n \n 1-bit extended flag (must be zero in version 2)\n \n 2-bit stage (during merge)\n \n 12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n is stored in this field.\n \n 1-bit skip-worktree flag (used by sparse checkout)\n \n 1-bit intent-to-add flag (used by \"git add -N\")\n\n 14-bit unused, must be zero\n\n A 16-bit offset, relative to the beginning of this block, to the\n pathname of this entry. FIXME: make it 32-bit, relative to the\n beginning of the file, so that we can reuse pathnames from other\n (old) blocks?\n\n - a list of NUL-terminated pathnames, pointed to from the 16-bit offset\n above. This list does not have to be of the same order as the attribute\n list. The reason this is separated from the attribute list is to make\n attribute list fixed size, searchable using bsearch().\n\n== Extension table block\n\n Extension table has block type 'X'. It consists of a series of 4-byte\n extension block offset.\n\n== Extension block\n\n Extension block has block type 'E'. Extension content is the same as\n in the old format.\n-- 8< --\n--\nDuy\n"},{"id":"188307","messageId":"CAJo=hJuVZiik6J0nhO4jpzWYenerRQoREHLMmJoFY8W0bZR+5A@mail.gmail.com","threadId":"30012","inReplyTo":"20120402123146.GA24813@do","subject":"Re: GSoC - Designing a faster index format","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2012-04-02T14:27:47Z","receivedAt":"2012-04-02T14:27:47Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Apr 2, 2012 at 08:31, Nguyen Thai Ngoc Duy wrote:\n> -- 8< --\n> GIT index format\n> ================\n>\n> This format replaces the old \"DIRC\" format. Compared to the old\n> format, which is essentially a sorted list of pathnames, this one:\n>\n>  - is tree-based\n>  - use crc32 as checksum\n>  - only verify integrity on parts that git accesses, instead of whole\n>   file\n>  - append changes to the end\n>  - allow index versioning\n>\n> Updates can be made directly to the index by appending to the end. The\n> index traversed by locating the root tree block from the trailer. When\n> a path is updated, all related tree blocks are updated and appended to\n> the end, then a new trailer (with generation increased by one) is\n> written to conclude the index.\n>\n> The index size will increase continuously. At some point, we will need\n> to repack it. Let assume a tree block is 64k on average and a path\n> generally consists of 3 path components.  That means an entry update\n> adds 192k and we can do about 80 updates before index reaches 16M (in\n> addition to initial index size).\n\nOnly 3 path components? Java sources can easily have 8-10 with a long\nMaven and Java package implied prefix. This will increase the\nfrequency of rewrites of the index file.\n\n> At 16M or when trailer generation hits a limit (the limit can be\n> configurable), we rewrite the index to reduce its size. Some heavy\n> operations can also be used to rewrite index, such as checkout or\n> reset.\n>\n> The index integrity is verified by crc32. One crc32 covers header and\n> trailer. Each block has its own crc32. When the index is found\n> corrupt, we could try to roll back to latest good version by looking\n> for trailers from bottom up. Even when the index is not corrupt, users\n> can still look back this way for older index versions.\n\nHow do you deal with a partially written append to the index file?\nE.g. if a prior update crashes or the filesystem doesn't write\neverything out before power failure, you need to find the last good\ntrailer block in the file.\n\n> = The git index file has the following format\n>\n>   - A 8-byte header consisting of\n>\n>     4-byte signature:\n>       The signature is { 'T', 'R', 'E', 'E' }\n>\n>     4-byte version number:\n>       The current supported versions are 1.\n\nWhy not DIRC version 4?\n\n>   - A number of blocks of variable size\n>\n>      1-byte block type\n>\n>      3-byte content size in byte\n>\n>      block content\n\nSo you are limiting the size of a canonical tree now? Currently there\nis no limit on the size a tree. But here the entire index structure\nplus set of names must be under 16 MiB. Granted no project probably\nhits that limit, but you are painting us into a corner with an upper\nlimit here that doesn't look like it will be easy to increase.\n\n>      4-byte crc32 of all above\n>\n>   - A 18-byte trailer consisting of\n>\n>      4-byte trailer signature:\n>        The signature is { 'R', 'O', 'O', 'T' }\n>\n>      2-byte generation:\n>         The first trailer is 0, the second 1 and so on.\n>\n>      4-byte root block offset\n>\n>      4-byte extension table offset:\n>        Zero means no extension\n>\n>      4-byte checksum:\n>        CRC32 of the header and the trailer (excluding this field)\n\nSee above my question about how to find the last good trailer if the\nlast append attempt was incomplete.\n\n> == Tree block\n>\n>  A tree block contains a (maybe invalid) tree object and extra\n>  information of its companion in working directory. Tree block has\n>  block type 'T'.\n>\n>  Tree block content is basically the list of non-recursive entries in\n>  specified path, with all attributes we store in the index now. There\n>  are a few changes though to intergrate cache-tree and allow\n>  bsearch() on mmap'd block.\n>\n>  A tree block content consists of\n>\n>  - 4-byte tree object size\n>\n>  - 20-byte SHA-1 of the cached tree object\n>\n>  - a list attributes corresponding to tree object's item, in the same\n>    order.  These attributes are the same as in DIRC entry format\n>    except that entry name is removed, and a tree block offset is\n>    added in case the item is a directory.\n>\n>    32-bit ctime seconds, the last time a file's metadata changed\n>      this is stat(2) data\n>\n>    32-bit ctime nanosecond fractions\n>      this is stat(2) data\n>\n>    32-bit mtime seconds, the last time a file's data changed\n>      this is stat(2) data\n>\n>    32-bit mtime nanosecond fractions\n>      this is stat(2) data\n>\n>    32-bit dev\n>      this is stat(2) data\n>\n>    32-bit ino\n>      this is stat(2) data\n>\n>    32-bit mode, split into (high to low bits)\n>\n>      4-bit object type\n>        valid values in binary are 1000 (regular file), 1010 (symbolic link)\n>        and 1110 (gitlink)\n>\n>      3-bit unused\n>\n>      9-bit unix permission. Only 0755 and 0644 are valid for regular files.\n>      Symbolic links and gitlinks have value 0 in this field.\n>\n>    32-bit uid\n>      this is stat(2) data\n>\n>    32-bit gid\n>      this is stat(2) data\n>\n>    32-bit file size\n>      This is the on-disk size from stat(2), truncated to 32-bit.\n>\n>    160-bit SHA-1 for the represented object if blobs or the offset\n>      to another tree block if trees\n>\n>    A 32-bit 'flags' field split into (high to low bits)\n>\n>      1-bit assume-valid flag\n>\n>      1-bit extended flag (must be zero in version 2)\n>\n>      2-bit stage (during merge)\n>\n>      12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>      is stored in this field.\n>\n>      1-bit skip-worktree flag (used by sparse checkout)\n>\n>      1-bit intent-to-add flag (used by \"git add -N\")\n>\n>      14-bit unused, must be zero\n>\n>    A 16-bit offset, relative to the beginning of this block, to the\n>      pathname of this entry. FIXME: make it 32-bit, relative to the\n>      beginning of the file, so that we can reuse pathnames from other\n>      (old) blocks?\n\n16 bit offset doesn't work well in a block that can be as large as 2^24.\n\nIf you reuse a path name list at the start of the file, how do you\nhandle new names?\n"},{"id":"188309","messageId":"CACsJy8B6EODKzfLxQJWvDCrspF8zxvYw4Kx8ZPbedO-CQZawGw@mail.gmail.com","threadId":"30012","inReplyTo":"CAJo=hJuVZiik6J0nhO4jpzWYenerRQoREHLMmJoFY8W0bZR+5A@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-02T15:12:20Z","receivedAt":"2012-04-02T15:12:20Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Apr 2, 2012 at 9:27 PM, Shawn Pearce wrote:\n> On Mon, Apr 2, 2012 at 08:31, Nguyen Thai Ngoc Duy wrote:\n>> The index size will increase continuously. At some point, we will need\n>> to repack it. Let assume a tree block is 64k on average and a path\n>> generally consists of 3 path components.  That means an entry update\n>> adds 192k and we can do about 80 updates before index reaches 16M (in\n>> addition to initial index size).\n>\n> Only 3 path components? Java sources can easily have 8-10 with a long\n> Maven and Java package implied prefix. This will increase the\n> frequency of rewrites of the index file.\n\nYes, but in java case, users could adjust the rewrite limits to make\nit less often. The index will be bigger, but because we mmap it and\nonly access parts of it, index size does not matter much.\n\n>> At 16M or when trailer generation hits a limit (the limit can be\n>> configurable), we rewrite the index to reduce its size. Some heavy\n>> operations can also be used to rewrite index, such as checkout or\n>> reset.\n>>\n>> The index integrity is verified by crc32. One crc32 covers header and\n>> trailer. Each block has its own crc32. When the index is found\n>> corrupt, we could try to roll back to latest good version by looking\n>> for trailers from bottom up. Even when the index is not corrupt, users\n>> can still look back this way for older index versions.\n>\n> How do you deal with a partially written append to the index file?\n> E.g. if a prior update crashes or the filesystem doesn't write\n> everything out before power failure, you need to find the last good\n> trailer block in the file.\n\nBy looking for the trailer signature \"ROOT\" from bottom up, then\nverify if it's still good (i.e. verifying all trees) from there.\nRepeat until we find a good one.\n\n>> = The git index file has the following format\n>>\n>>   - A 8-byte header consisting of\n>>\n>>     4-byte signature:\n>>       The signature is { 'T', 'R', 'E', 'E' }\n>>\n>>     4-byte version number:\n>>       The current supported versions are 1.\n>\n> Why not DIRC version 4?\n\nI thought of that, but because I don't keep header format the same as\nv3, I thought signature should change too. But this is really not\nimportant at this stage.\n\n>>   - A number of blocks of variable size\n>>\n>>      1-byte block type\n>>\n>>      3-byte content size in byte\n>>\n>>      block content\n>\n> So you are limiting the size of a canonical tree now? Currently there\n> is no limit on the size a tree. But here the entire index structure\n> plus set of names must be under 16 MiB. Granted no project probably\n> hits that limit, but you are painting us into a corner with an upper\n> limit here that doesn't look like it will be easy to increase.\n\nWe can introduce a new block type, not a nice approach though. Not\nsaving block size is probably ok too. We would need something to mark\nend-of-block. I wanted to save block size to do crc32 quickly without\nparsing the block, but instead, we could make block parsing faster and\nnot worry about it.\n\n>> == Tree block\n>>\n>>  A tree block contains a (maybe invalid) tree object and extra\n>>  information of its companion in working directory. Tree block has\n>>  block type 'T'.\n>>\n>>  Tree block content is basically the list of non-recursive entries in\n>>  specified path, with all attributes we store in the index now. There\n>>  are a few changes though to intergrate cache-tree and allow\n>>  bsearch() on mmap'd block.\n>>\n>>  A tree block content consists of\n>>\n>>  - 4-byte tree object size\n>>\n>>  - 20-byte SHA-1 of the cached tree object\n>>\n>>  - a list attributes corresponding to tree object's item, in the same\n>>    order.  These attributes are the same as in DIRC entry format\n>>    except that entry name is removed, and a tree block offset is\n>>    added in case the item is a directory.\n>>\n>> ...\n>>\n>>    A 16-bit offset, relative to the beginning of this block, to the\n>>      pathname of this entry. FIXME: make it 32-bit, relative to the\n>>      beginning of the file, so that we can reuse pathnames from other\n>>      (old) blocks?\n>\n> 16 bit offset doesn't work well in a block that can be as large as 2^24.\n\nNo it doesn't. That's the implication of using 16-bit offsets.\n\n> If you reuse a path name list at the start of the file, how do you\n> handle new names?\n\nWe don't drop this part even if we reuse a few path names elsewhere.\nNew path names can be put here. But I'm not really sure if reusing\nnames gains us anything because at least it breaks locality and\ncomplicates handling code. We already save quite a bit by not\nduplicating parent prefix.\n-- \nDuy\n"},{"id":"188475","messageId":"CAKTdtZm4JFkWOq7D=tHC-t8C5yd=AG6MEkKD46z5D7fCRDEfZQ@mail.gmail.com","threadId":"30012","inReplyTo":"20120402123146.GA24813@do","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-04-04T08:26:21Z","receivedAt":"2012-04-04T08:26:21Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hi Nguyen,\n\nA few questions,\n\n> -- 8< --\n> GIT index format\n> ================\n>\n> This format replaces the old \"DIRC\" format. Compared to the old\n> format, which is essentially a sorted list of pathnames, this one:\n>\n>  - is tree-based\n>  - use crc32 as checksum\n>  - only verify integrity on parts that git accesses, instead of whole\n>   file\n>  - append changes to the end\n>  - allow index versioning\n>\n> Updates can be made directly to the index by appending to the end. The\n> index traversed by locating the root tree block from the trailer. When\n> a path is updated, all related tree blocks are updated and appended to\n> the end, then a new trailer (with generation increased by one) is\n> written to conclude the index.\n>\n> The index size will increase continuously. At some point, we will need\n> to repack it. Let assume a tree block is 64k on average and a path\n> generally consists of 3 path components.  That means an entry update\n> adds 192k and we can do about 80 updates before index reaches 16M (in\n> addition to initial index size).\n>\n> At 16M or when trailer generation hits a limit (the limit can be\n> configurable), we rewrite the index to reduce its size. Some heavy\n> operations can also be used to rewrite index, such as checkout or\n> reset.\n>\n> The index integrity is verified by crc32. One crc32 covers header and\n> trailer. Each block has its own crc32. When the index is found\n> corrupt, we could try to roll back to latest good version by looking\n> for trailers from bottom up. Even when the index is not corrupt, users\n> can still look back this way for older index versions.\n>\n\nI am not sure how the trailer works.\nI assume there can be multiple trailers, each update will generate a\nnew one. Every trailer will point to the root tree (i.e. all trailers\npoint to the same block?). So if there are some changes to root, like\nrename, trailers all point to the latest root block?\n\nIs the index looks like :\n| HEADER | TREE BLOCKS | TRAILER |  TREE BLOCKS | TRAILER | TREE\nBLOCKS | TRAILER | ...\n\nBlocks and trailers are interleaved. The index starts from a few\nblocks (git add file1 file2 file3 ..) and expands as it goes. If file1\nis updated, the tree block containing file1 is updated and appended.\n(At this point, 2 versions of tree blocks containing file is in index\n?) How do you organize these 2 block in a tree ?\n\nAppended blocks are also a tree or just a list. If it's a list, it\nneeds O(n) read time. If it's like a sub tree, I assume it's small,\nbecause I guess there won't be many changes each time. If it's too\nsmall then lgn -> n, and in total read time -> n.\n\n> = The git index file has the following format\n>\n>   - A 8-byte header consisting of\n>\n>     4-byte signature:\n>       The signature is { 'T', 'R', 'E', 'E' }\n>\n>     4-byte version number:\n>       The current supported versions are 1.\n>\n>   - A number of blocks of variable size\n>\n>      1-byte block type\n>\n>      3-byte content size in byte\n>\n>      block content\n>\n>      4-byte crc32 of all above\n>\n>   - A 18-byte trailer consisting of\n>\n>      4-byte trailer signature:\n>        The signature is { 'R', 'O', 'O', 'T' }\n>\n>      2-byte generation:\n>         The first trailer is 0, the second 1 and so on.\n>\n>      4-byte root block offset\n>\n>      4-byte extension table offset:\n>        Zero means no extension\n>\n>      4-byte checksum:\n>        CRC32 of the header and the trailer (excluding this field)\n>\n> == Tree block\n>\n>  A tree block contains a (maybe invalid) tree object and extra\n>  information of its companion in working directory. Tree block has\n>  block type 'T'.\n>\n>  Tree block content is basically the list of non-recursive entries in\n>  specified path, with all attributes we store in the index now. There\n>  are a few changes though to intergrate cache-tree and allow\n>  bsearch() on mmap'd block.\n>\n>  A tree block content consists of\n>\n>  - 4-byte tree object size\n>\n>  - 20-byte SHA-1 of the cached tree object\n>\n>  - a list attributes corresponding to tree object's item, in the same\n>    order.  These attributes are the same as in DIRC entry format\n>    except that entry name is removed, and a tree block offset is\n>    added in case the item is a directory.\n>\n>    32-bit ctime seconds, the last time a file's metadata changed\n>      this is stat(2) data\n>\n>    32-bit ctime nanosecond fractions\n>      this is stat(2) data\n>\n>    32-bit mtime seconds, the last time a file's data changed\n>      this is stat(2) data\n>\n>    32-bit mtime nanosecond fractions\n>      this is stat(2) data\n>\n>    32-bit dev\n>      this is stat(2) data\n>\n>    32-bit ino\n>      this is stat(2) data\n>\n>    32-bit mode, split into (high to low bits)\n>\n>      4-bit object type\n>        valid values in binary are 1000 (regular file), 1010 (symbolic link)\n>        and 1110 (gitlink)\n>\n>      3-bit unused\n>\n>      9-bit unix permission. Only 0755 and 0644 are valid for regular files.\n>      Symbolic links and gitlinks have value 0 in this field.\n>\n>    32-bit uid\n>      this is stat(2) data\n>\n>    32-bit gid\n>      this is stat(2) data\n>\n>    32-bit file size\n>      This is the on-disk size from stat(2), truncated to 32-bit.\n>\n>    160-bit SHA-1 for the represented object if blobs or the offset\n>      to another tree block if trees\n>\n>    A 32-bit 'flags' field split into (high to low bits)\n>\n>      1-bit assume-valid flag\n>\n>      1-bit extended flag (must be zero in version 2)\n>\n>      2-bit stage (during merge)\n>\n>      12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>      is stored in this field.\n>\n>      1-bit skip-worktree flag (used by sparse checkout)\n>\n>      1-bit intent-to-add flag (used by \"git add -N\")\n>\n>      14-bit unused, must be zero\n>\n>    A 16-bit offset, relative to the beginning of this block, to the\n>      pathname of this entry. FIXME: make it 32-bit, relative to the\n>      beginning of the file, so that we can reuse pathnames from other\n>      (old) blocks?\n>\n\nIt's nice to enable it for bsearch in a block by separate pathname.\nIf all names are shared by all blocks, this pathname tree will be\nloaded for every operation. I guess the load&hash is expensive.\n\n>  - a list of NUL-terminated pathnames, pointed to from the 16-bit offset\n>    above. This list does not have to be of the same order as the attribute\n>    list. The reason this is separated from the attribute list is to make\n>    attribute list fixed size, searchable using bsearch().\n>\n> == Extension table block\n>\n>  Extension table has block type 'X'. It consists of a series of 4-byte\n>  extension block offset.\n>\n> == Extension block\n>\n>  Extension block has block type 'E'. Extension content is the same as\n>  in the old format.\n> -- 8< --\n> --\n> Duy\n\n-Elton\n"},{"id":"188483","messageId":"CACsJy8A+0GxePYPSJh9g_N83QXY8cf8HHGT65M_eNGBeAs-5uQ@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZm4JFkWOq7D=tHC-t8C5yd=AG6MEkKD46z5D7fCRDEfZQ@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-04-04T12:20:47Z","receivedAt":"2012-04-04T12:20:47Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Apr 4, 2012 at 3:26 PM, elton sky wrote:\n> I am not sure how the trailer works.\n> I assume there can be multiple trailers, each update will generate a\n> new one. Every trailer will point to the root tree (i.e. all trailers\n> point to the same block?). So if there are some changes to root, like\n> rename, trailers all point to the latest root block?\n\nEach trailer points to the whole new tree. Because trees are\nimmutable, changing in a tree meangs creating a new one and will also\nmake a new parent tree (to point to the updated tree because old\nparent will always point to old tree). This eventually leads to root\ntree change, recorded by the trailer.\n\n> Is the index looks like :\n> | HEADER | TREE BLOCKS | TRAILER |  TREE BLOCKS | TRAILER | TREE\n> BLOCKS | TRAILER | ...\n>\n> Blocks and trailers are interleaved. The index starts from a few\n> blocks (git add file1 file2 file3 ..) and expands as it goes. If file1\n> is updated, the tree block containing file1 is updated and appended.\n> (At this point, 2 versions of tree blocks containing file is in index\n> ?) How do you organize these 2 block in a tree ?\n\nI leave them where they are. They will be indirectly referenced by two\ndifferent roots. At that point we have to new full trees, sharing many\nsubtrees except the one that contains file1 and its ancestors. This\nmakes it possible to access an old index version by traversing from an\nolder trailer. Heavy \"add -p\" users may like this.\n\n> Appended blocks are also a tree or just a list. If it's a list, it\n> needs O(n) read time. If it's like a sub tree, I assume it's small,\n> because I guess there won't be many changes each time. If it's too\n> small then lgn -> n, and in total read time -> n.\n\nIt's trees all the way down. I'm not sure why read time is related\nhere. You read it by traversing from root tree to leaves, no matter\nold or new root. Appended trees may push trees farther away and\nincrease seek time. Other than that, I don't see significant read\nperformance degradation (really crowded trees may degrade a little bit\nbecause we need to read trees in addition to leaves, but I don't think\nit's a big problem).\n-- \nDuy\n"},{"id":"188493","messageId":"CAKTdtZkyLfjsqzoVNA0VocWBf+wh3YDtTwx_x4tFTxnr1fJyAw@mail.gmail.com","threadId":"30012","inReplyTo":"CACsJy8A+0GxePYPSJh9g_N83QXY8cf8HHGT65M_eNGBeAs-5uQ@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-04-04T16:22:10Z","receivedAt":"2012-04-04T16:22:10Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Hello,\n\nSome updates for Nguyen's index:\n\nOn Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy wrote:\n> On Wed, Apr 4, 2012 at 3:26 PM, elton sky wrote:\n>> I am not sure how the trailer works.\n>> I assume there can be multiple trailers, each update will generate a\n>> new one. Every trailer will point to the root tree (i.e. all trailers\n>> point to the same block?). So if there are some changes to root, like\n>> rename, trailers all point to the latest root block?\n>\n> Each trailer points to the whole new tree. Because trees are\n> immutable, changing in a tree meangs creating a new one and will also\n> make a new parent tree (to point to the updated tree because old\n> parent will always point to old tree). This eventually leads to root\n> tree change, recorded by the trailer.\n>\n>> Is the index looks like :\n>> | HEADER | TREE BLOCKS | TRAILER |  TREE BLOCKS | TRAILER | TREE\n>> BLOCKS | TRAILER | ...\n>>\n\nOnce an update happened to a block, all parent blocks to root will be\ncopied to the end of the index. And the updated block will be at leaf\nof the new tree. Finding this path costs logn time anyway. This is no\nharm for read for the whole tree. But in order to find all previous\nchanges to a block, we have to go through all trailers and trees.\n\nOtherwise, just modify the original tree. Let the parent points to the\nupdated block and let the updated block points to the old block:\n\nparent\n   |\n  V\nupdated            old                  old\nblock (v3)  -->   block(v2)  -->  block (v1)\n   |\n  V\nchild\nblocks\n\nA version number in a tree block is used to track the changes.\nIn this way, there's still no harm to read, and it's more easy to\ntrace the change history of a block. Also, we don't need to create\ninterleaved blocks and trailers. There's only one trailer in the end\nof file. We also need to add another offset points to previous\nversion.\n\nTrailer is kept at the end of index, as its size is variable. It\ncontains offset to root and list of free spaces.\n\nChanges to format:\n\n> = The git index file has the following format\n\nAs is, except there's only one trailer now. And trailer contains list\nof free spaces.\n\n>- A 18-byte trailer consisting of\n>\n>      4-byte trailer signature:\n>        The signature is { 'R', 'O', 'O', 'T' }\n>\n>      2-byte generation:\n>         The first trailer is 0, the second 1 and so on.\n>\n>      4-byte root block offset\n>\n>      4-byte extension table offset:\n>        Zero means no extension\n>\n       list of free spaces\n       - 4 byte offset\n       - 2 byte length\n\n>      4-byte checksum:\n>        CRC32 of the header and the trailer (excluding this field)\n\nFree space list is read/written in whole for each operation, together\nwith trailer.\n\n>\n> == Tree block\n> ...\n\nAbove as is.\n\n- 1 byte version num\n\n- 4 byte offset to previous version block\n\n>\n>    160-bit SHA-1 for the represented object if blobs or the offset\n>      to another tree block if trees\n>\n>    A 32-bit 'flags' field split into (high to low bits)\n>\n>      1-bit assume-valid flag\n>\n>      1-bit extended flag (must be zero in version 2)\n>\n>      2-bit stage (during merge)\n>\n>      12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>      is stored in this field.\n>\n>      1-bit skip-worktree flag (used by sparse checkout)\n>\n>      1-bit intent-to-add flag (used by \"git add -N\")\n>\n>      14-bit unused, must be zero\n>\n>    A 16-bit offset, relative to the beginning of this block, to the\n>      pathname of this entry. FIXME: make it 32-bit, relative to the\n>      beginning of the file, so that we can reuse pathnames from other\n>      (old) blocks?\n>\n\n-Elton\n"},{"id":"188624","messageId":"CAKTdtZmzGyH+BUPjBPLxSTJp5OPr+uKAeu_No9VSoTgUAH2SEw@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZkyLfjsqzoVNA0VocWBf+wh3YDtTwx_x4tFTxnr1fJyAw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-04-06T03:13:34Z","receivedAt":"2012-04-06T03:13:34Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"Thank you everyone for ideas, clues, explanations and questions.\nCollectively I wrote my proposal. This one is mostly based on Duy's\nsuggestion with minor changes.\n\n\nProblem:\nCurrent index store all files in a list. This implies that:\n1. Each operation has to read the whole index and write the whole index back.\n2. computing the checksum for the whole index.\nThese become expensive when the repo is large.\n\nRequirement:\nSuppose n is the number objects in a repo\n-Keep the read/write time <= O(logn).\n-Keep the checksum computed against only necessary objects.\n-New format is easy to parse.\n-Backward compatible.\n-Potentially use faster hash method.\n\nProposed solution:\n\nStore the repo structure in a canonical tree. Each directory is a tree\nblock. A tree block contains blobs and offsets to sub directories. It\nhas its own checksum. A read/write will be done on tree block base. A\ntree block also contains an offset points to its previous version (if\nthere's one).\n\nThe root of offset is stored in trailer, which stays at the end of\nfile. Each update creates a new trailer which points to the new tree.\n(details below)\n\nTo save the pain of modify a tree block and track the free spaces in\nthe index, changed blocks are appended at the end. Based on the\nassumption that user won't change too many files each time, for an\nupdated file, all its parent blocks to Root was copied and appended to\nindex. In other words, all traversed blocks are copied. The offset of\nprevious version of the updated block is stored in the new block. A\nnew generation number is stored in copied and updated blocks. Other\nblocks are not copied. They are referenced by offsets. After update a\nnew trailer is created at the end. In this way, there's no harm to\nread, and makes write fast.\n\nTrailer stores the offset of previous trailer. It makes tracking old\nversions easy.\n\nEach operation will load and rewrite the header and visited trailer .\n\nChecksum for non identifier purpose will use crc32. Otherwise it uses sha1.\n\nFor compatibility, old format of index will be transformed to new\nformat in the first operation.\n\n==\nIndex format:\n\n- A 8-byte header consisting of\n\n 4-byte signature:\n The signature is { 'T', 'R', 'E', 'E' }\n\n 4-byte version number:\n The current supported versions are 4.\n\n - A number of blocks of variable size\n\n 1-byte block type\n\n 3-byte content size in byte\n\n block content\n\n 4-byte crc32 of all above\n\n - A 20-byte trailer consisting of\n\n 4-byte trailer signature:\n The signature is { 'R', 'O', 'O', 'T' }\n\n 4-byte root block offset\n\n 4-byte extension table offset:\n Zero means no extension\n\n 4-byte offset to previous trailer\n\n 4-byte checksum:\n CRC32 of the header and the trailer (excluding this field)\n\n==\nTree block:\n\nTree block content is basically the list of entries in a specified\npath, with all attributes we store in the index now. This entry list\nis sorted by pathname. For doing a bsearch in the list, pathnames are\nstored at the end of block, which makes the size of entry fixed. The\npathname is pointed from each entry with 2 byte offset (relative to a\nblock). This should not be problem as a block is never modified.\n\nIt stores the generation number and the offset to old block. It also\nintegrates the content of cache-tree.\n\nA tree block content consists of\n\n - 4-byte tree object size\n\n - 20-byte SHA-1 of the cached tree object\n\n- checkpoint : interleave with items in the block, 1 for every 100 items\n\t4-byte offset to next checkpoint\n\t\n - a list attributes corresponding to tree object's item, in the same\n order. These attributes are the same as in DIRC entry format\n except that entry name is removed, and a tree block offset is\n added in case the item is a directory.\n\n 32-bit ctime seconds, the last time a file's metadata changed\n this is stat(2) data\n\n 32-bit ctime nanosecond fractions\n this is stat(2) data\n\n 32-bit mtime seconds, the last time a file's data changed\n this is stat(2) data\n\n 32-bit mtime nanosecond fractions\n this is stat(2) data\n\n 32-bit dev\n this is stat(2) data\n\n 32-bit ino\n this is stat(2) data\n\n 32-bit mode, split into (high to low bits)\n\n 4-bit object type\n valid values in binary are 1000 (regular file), 1010 (symbolic link)\n and 1110 (gitlink)\n\n 3-bit unused\n\n 9-bit unix permission. Only 0755 and 0644 are valid for regular files.\n Symbolic links and gitlinks have value 0 in this field.\n\n 32-bit uid\n this is stat(2) data\n\n 32-bit gid\n this is stat(2) data\n\n 32-bit file size\n This is the on-disk size from stat(2), truncated to 32-bit.\n\n 160-bit SHA-1 for the represented object if blobs or the offset\n to another tree block if trees\n\n A 32-bit 'flags' field split into (high to low bits)\n\n 1-bit assume-valid flag\n\n 1-bit extended flag (must be zero in version 2)\n\n 2-bit stage (during merge)\n\n 12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n is stored in this field.\n\n 1-bit skip-worktree flag (used by sparse checkout)\n\n 1-bit intent-to-add flag (used by \"git add -N\")\n\n 14-bit unused, must be zero\n\n A 16-bit offset, relative to the beginning of this block, to the\npathname of this entry\n\n- 2-byte generation number, starts from 1\n\n- 4-byte previous version offset\n\n - a list of NUL-terminated pathnames, pointed to from the 16-bit offset\n above\n\n== Extension table block\n\nExtension table has block type 'X'. It consists of a series of 4-byte\nextension block offset.\n\n== Extension block\n\nExtension block has block type 'E'. Extension content is the same as\nin the old format.\n\n\n\nTime line:\n\n24/04 ~ 21/05: get familiar with code base and revise proposal\nbenchmark with linux kernel on major operations\nwrite prototype to prove feasibility of proposed solution\nconsult mailing list & irc\n\n22/05 ~ 25/06 write code, test and benchmark\n\tmodify tree lib\n\tmodify index format operations\n\tmodify git operations\n\ttransform from old to new\n\n26/06 ~ 30/07 revise things according to benchmark\n\n31/07 ~ 13/08 update documentation\n\t\n\nAbout me\n\nMy name is Elton Tian, I am from China. I have been living in\nAustralia for quite a few years. I am currently a Master student from\nAustralia National University. After graduate I worked on linux based\nweb development (using tcl) for 2.5 years. I have been programming\nwith c, c#, java, tcl, php, javascript and shell script. But I prefer\nc, which gives me the feeling of full control over the program. I am\ninterested in data intensive computing. I played with hadoop and\nmapreduce since 2010. I maintained my 3 node cluster behind my desk.\nAs linus hates cvs with a passion, I still want to mention I was using\ncvs in work, don't like it though. And I guess this is the good chance\nto get over it.\n\nOn Thu, Apr 5, 2012 at 2:22 AM, elton sky wrote:\n> Hello,\n>\n> Some updates for Nguyen's index:\n>\n> On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy wrote:\n>> On Wed, Apr 4, 2012 at 3:26 PM, elton sky wrote:\n>>> I am not sure how the trailer works.\n>>> I assume there can be multiple trailers, each update will generate a\n>>> new one. Every trailer will point to the root tree (i.e. all trailers\n>>> point to the same block?). So if there are some changes to root, like\n>>> rename, trailers all point to the latest root block?\n>>\n>> Each trailer points to the whole new tree. Because trees are\n>> immutable, changing in a tree meangs creating a new one and will also\n>> make a new parent tree (to point to the updated tree because old\n>> parent will always point to old tree). This eventually leads to root\n>> tree change, recorded by the trailer.\n>>\n>>> Is the index looks like :\n>>> | HEADER | TREE BLOCKS | TRAILER |  TREE BLOCKS | TRAILER | TREE\n>>> BLOCKS | TRAILER | ...\n>>>\n>\n> Once an update happened to a block, all parent blocks to root will be\n> copied to the end of the index. And the updated block will be at leaf\n> of the new tree. Finding this path costs logn time anyway. This is no\n> harm for read for the whole tree. But in order to find all previous\n> changes to a block, we have to go through all trailers and trees.\n>\n> Otherwise, just modify the original tree. Let the parent points to the\n> updated block and let the updated block points to the old block:\n>\n> parent\n>    |\n>   V\n> updated            old                  old\n> block (v3)  -->   block(v2)  -->  block (v1)\n>    |\n>   V\n> child\n> blocks\n>\n> A version number in a tree block is used to track the changes.\n> In this way, there's still no harm to read, and it's more easy to\n> trace the change history of a block. Also, we don't need to create\n> interleaved blocks and trailers. There's only one trailer in the end\n> of file. We also need to add another offset points to previous\n> version.\n>\n> Trailer is kept at the end of index, as its size is variable. It\n> contains offset to root and list of free spaces.\n>\n> Changes to format:\n>\n>> = The git index file has the following format\n>\n> As is, except there's only one trailer now. And trailer contains list\n> of free spaces.\n>\n>>- A 18-byte trailer consisting of\n>>\n>>      4-byte trailer signature:\n>>        The signature is { 'R', 'O', 'O', 'T' }\n>>\n>>      2-byte generation:\n>>         The first trailer is 0, the second 1 and so on.\n>>\n>>      4-byte root block offset\n>>\n>>      4-byte extension table offset:\n>>        Zero means no extension\n>>\n>        list of free spaces\n>        - 4 byte offset\n>        - 2 byte length\n>\n>>      4-byte checksum:\n>>        CRC32 of the header and the trailer (excluding this field)\n>\n> Free space list is read/written in whole for each operation, together\n> with trailer.\n>\n>>\n>> == Tree block\n>> ...\n>\n> Above as is.\n>\n> - 1 byte version num\n>\n> - 4 byte offset to previous version block\n>\n>>\n>>    160-bit SHA-1 for the represented object if blobs or the offset\n>>      to another tree block if trees\n>>\n>>    A 32-bit 'flags' field split into (high to low bits)\n>>\n>>      1-bit assume-valid flag\n>>\n>>      1-bit extended flag (must be zero in version 2)\n>>\n>>      2-bit stage (during merge)\n>>\n>>      12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>>      is stored in this field.\n>>\n>>      1-bit skip-worktree flag (used by sparse checkout)\n>>\n>>      1-bit intent-to-add flag (used by \"git add -N\")\n>>\n>>      14-bit unused, must be zero\n>>\n>>    A 16-bit offset, relative to the beginning of this block, to the\n>>      pathname of this entry. FIXME: make it 32-bit, relative to the\n>>      beginning of the file, so that we can reuse pathnames from other\n>>      (old) blocks?\n>>\n>\n> -Elton\n"},{"id":"188625","messageId":"CAKTdtZm9THdFaSjAONStmOdbs_QxHK5ZWc6_sVaySufKJ6CgEw@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZmzGyH+BUPjBPLxSTJp5OPr+uKAeu_No9VSoTgUAH2SEw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-04-06T03:15:44Z","receivedAt":"2012-04-06T03:15:44Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":"NOTE:\nPlease ignore the\n\n>- checkpoint : interleave with items in the block, 1 for every 100 items\n>       4-byte offset to next checkpoint\n\nThat's irrelevant.\n\nCheers,\nElton\n\nOn Fri, Apr 6, 2012 at 1:13 PM, elton sky wrote:\n> Thank you everyone for ideas, clues, explanations and questions.\n> Collectively I wrote my proposal. This one is mostly based on Duy's\n> suggestion with minor changes.\n>\n>\n> Problem:\n> Current index store all files in a list. This implies that:\n> 1. Each operation has to read the whole index and write the whole index back.\n> 2. computing the checksum for the whole index.\n> These become expensive when the repo is large.\n>\n> Requirement:\n> Suppose n is the number objects in a repo\n> -Keep the read/write time <= O(logn).\n> -Keep the checksum computed against only necessary objects.\n> -New format is easy to parse.\n> -Backward compatible.\n> -Potentially use faster hash method.\n>\n> Proposed solution:\n>\n> Store the repo structure in a canonical tree. Each directory is a tree\n> block. A tree block contains blobs and offsets to sub directories. It\n> has its own checksum. A read/write will be done on tree block base. A\n> tree block also contains an offset points to its previous version (if\n> there's one).\n>\n> The root of offset is stored in trailer, which stays at the end of\n> file. Each update creates a new trailer which points to the new tree.\n> (details below)\n>\n> To save the pain of modify a tree block and track the free spaces in\n> the index, changed blocks are appended at the end. Based on the\n> assumption that user won't change too many files each time, for an\n> updated file, all its parent blocks to Root was copied and appended to\n> index. In other words, all traversed blocks are copied. The offset of\n> previous version of the updated block is stored in the new block. A\n> new generation number is stored in copied and updated blocks. Other\n> blocks are not copied. They are referenced by offsets. After update a\n> new trailer is created at the end. In this way, there's no harm to\n> read, and makes write fast.\n>\n> Trailer stores the offset of previous trailer. It makes tracking old\n> versions easy.\n>\n> Each operation will load and rewrite the header and visited trailer .\n>\n> Checksum for non identifier purpose will use crc32. Otherwise it uses sha1.\n>\n> For compatibility, old format of index will be transformed to new\n> format in the first operation.\n>\n> ==\n> Index format:\n>\n> - A 8-byte header consisting of\n>\n>    4-byte signature:\n>      The signature is { 'T', 'R', 'E', 'E' }\n>\n>    4-byte version number:\n>      The current supported versions are 4.\n>\n>  - A number of blocks of variable size\n>\n>     1-byte block type\n>\n>     3-byte content size in byte\n>\n>     block content\n>\n>     4-byte crc32 of all above\n>\n>  - A 20-byte trailer consisting of\n>\n>     4-byte trailer signature:\n>       The signature is { 'R', 'O', 'O', 'T' }\n>\n>     4-byte root block offset\n>\n>     4-byte extension table offset:\n>       Zero means no extension\n>\n>     4-byte offset to previous trailer\n>\n>     4-byte checksum:\n>       CRC32 of the header and the trailer (excluding this field)\n>\n> ==\n> Tree block:\n>\n> Tree block content is basically the list of entries in a specified\n> path, with all attributes we store in the index now. This entry list\n> is sorted by pathname. For doing a bsearch in the list, pathnames are\n> stored at the end of block, which makes the size of entry fixed. The\n> pathname is pointed from each entry with 2 byte offset (relative to a\n> block). This should not be problem as a block is never modified.\n>\n> It stores the generation number and the offset to old block. It also\n> integrates the content of cache-tree.\n>\n> A tree block content consists of\n>\n>  - 4-byte tree object size\n>\n>  - 20-byte SHA-1 of the cached tree object\n>\n> - checkpoint : interleave with items in the block, 1 for every 100 items\n>        4-byte offset to next checkpoint\n>\n>  - a list attributes corresponding to tree object's item, in the same\n>   order. These attributes are the same as in DIRC entry format\n>   except that entry name is removed, and a tree block offset is\n>   added in case the item is a directory.\n>\n>   32-bit ctime seconds, the last time a file's metadata changed\n>     this is stat(2) data\n>\n>   32-bit ctime nanosecond fractions\n>     this is stat(2) data\n>\n>   32-bit mtime seconds, the last time a file's data changed\n>     this is stat(2) data\n>\n>   32-bit mtime nanosecond fractions\n>     this is stat(2) data\n>\n>   32-bit dev\n>     this is stat(2) data\n>\n>   32-bit ino\n>     this is stat(2) data\n>\n>   32-bit mode, split into (high to low bits)\n>\n>     4-bit object type\n>       valid values in binary are 1000 (regular file), 1010 (symbolic link)\n>       and 1110 (gitlink)\n>\n>     3-bit unused\n>\n>     9-bit unix permission. Only 0755 and 0644 are valid for regular files.\n>     Symbolic links and gitlinks have value 0 in this field.\n>\n>   32-bit uid\n>     this is stat(2) data\n>\n>   32-bit gid\n>     this is stat(2) data\n>\n>   32-bit file size\n>     This is the on-disk size from stat(2), truncated to 32-bit.\n>\n>   160-bit SHA-1 for the represented object if blobs or the offset\n>     to another tree block if trees\n>\n>   A 32-bit 'flags' field split into (high to low bits)\n>\n>     1-bit assume-valid flag\n>\n>     1-bit extended flag (must be zero in version 2)\n>\n>     2-bit stage (during merge)\n>\n>     12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>     is stored in this field.\n>\n>     1-bit skip-worktree flag (used by sparse checkout)\n>\n>     1-bit intent-to-add flag (used by \"git add -N\")\n>\n>     14-bit unused, must be zero\n>\n>      A 16-bit offset, relative to the beginning of this block, to the\n> pathname of this entry\n>\n> - 2-byte generation number, starts from 1\n>\n> - 4-byte previous version offset\n>\n>  - a list of NUL-terminated pathnames, pointed to from the 16-bit offset\n>   above\n>\n> == Extension table block\n>\n> Extension table has block type 'X'. It consists of a series of 4-byte\n> extension block offset.\n>\n> == Extension block\n>\n> Extension block has block type 'E'. Extension content is the same as\n> in the old format.\n>\n>\n>\n> Time line:\n>\n> 24/04 ~ 21/05: get familiar with code base and revise proposal\n> benchmark with linux kernel on major operations\n> write prototype to prove feasibility of proposed solution\n> consult mailing list & irc\n>\n> 22/05 ~ 25/06 write code, test and benchmark\n>        modify tree lib\n>        modify index format operations\n>        modify git operations\n>        transform from old to new\n>\n> 26/06 ~ 30/07 revise things according to benchmark\n>\n> 31/07 ~ 13/08 update documentation\n>\n>\n> About me\n>\n> My name is Elton Tian, I am from China. I have been living in\n> Australia for quite a few years. I am currently a Master student from\n> Australia National University. After graduate I worked on linux based\n> web development (using tcl) for 2.5 years. I have been programming\n> with c, c#, java, tcl, php, javascript and shell script. But I prefer\n> c, which gives me the feeling of full control over the program. I am\n> interested in data intensive computing. I played with hadoop and\n> mapreduce since 2010. I maintained my 3 node cluster behind my desk.\n> As linus hates cvs with a passion, I still want to mention I was using\n> cvs in work, don't like it though. And I guess this is the good chance\n> to get over it.\n>\n> On Thu, Apr 5, 2012 at 2:22 AM, elton sky wrote:\n>> Hello,\n>>\n>> Some updates for Nguyen's index:\n>>\n>> On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy wrote:\n>>> On Wed, Apr 4, 2012 at 3:26 PM, elton sky wrote:\n>>>> I am not sure how the trailer works.\n>>>> I assume there can be multiple trailers, each update will generate a\n>>>> new one. Every trailer will point to the root tree (i.e. all trailers\n>>>> point to the same block?). So if there are some changes to root, like\n>>>> rename, trailers all point to the latest root block?\n>>>\n>>> Each trailer points to the whole new tree. Because trees are\n>>> immutable, changing in a tree meangs creating a new one and will also\n>>> make a new parent tree (to point to the updated tree because old\n>>> parent will always point to old tree). This eventually leads to root\n>>> tree change, recorded by the trailer.\n>>>\n>>>> Is the index looks like :\n>>>> | HEADER | TREE BLOCKS | TRAILER |  TREE BLOCKS | TRAILER | TREE\n>>>> BLOCKS | TRAILER | ...\n>>>>\n>>\n>> Once an update happened to a block, all parent blocks to root will be\n>> copied to the end of the index. And the updated block will be at leaf\n>> of the new tree. Finding this path costs logn time anyway. This is no\n>> harm for read for the whole tree. But in order to find all previous\n>> changes to a block, we have to go through all trailers and trees.\n>>\n>> Otherwise, just modify the original tree. Let the parent points to the\n>> updated block and let the updated block points to the old block:\n>>\n>> parent\n>>    |\n>>   V\n>> updated            old                  old\n>> block (v3)  -->   block(v2)  -->  block (v1)\n>>    |\n>>   V\n>> child\n>> blocks\n>>\n>> A version number in a tree block is used to track the changes.\n>> In this way, there's still no harm to read, and it's more easy to\n>> trace the change history of a block. Also, we don't need to create\n>> interleaved blocks and trailers. There's only one trailer in the end\n>> of file. We also need to add another offset points to previous\n>> version.\n>>\n>> Trailer is kept at the end of index, as its size is variable. It\n>> contains offset to root and list of free spaces.\n>>\n>> Changes to format:\n>>\n>>> = The git index file has the following format\n>>\n>> As is, except there's only one trailer now. And trailer contains list\n>> of free spaces.\n>>\n>>>- A 18-byte trailer consisting of\n>>>\n>>>      4-byte trailer signature:\n>>>        The signature is { 'R', 'O', 'O', 'T' }\n>>>\n>>>      2-byte generation:\n>>>         The first trailer is 0, the second 1 and so on.\n>>>\n>>>      4-byte root block offset\n>>>\n>>>      4-byte extension table offset:\n>>>        Zero means no extension\n>>>\n>>        list of free spaces\n>>        - 4 byte offset\n>>        - 2 byte length\n>>\n>>>      4-byte checksum:\n>>>        CRC32 of the header and the trailer (excluding this field)\n>>\n>> Free space list is read/written in whole for each operation, together\n>> with trailer.\n>>\n>>>\n>>> == Tree block\n>>> ...\n>>\n>> Above as is.\n>>\n>> - 1 byte version num\n>>\n>> - 4 byte offset to previous version block\n>>\n>>>\n>>>    160-bit SHA-1 for the represented object if blobs or the offset\n>>>      to another tree block if trees\n>>>\n>>>    A 32-bit 'flags' field split into (high to low bits)\n>>>\n>>>      1-bit assume-valid flag\n>>>\n>>>      1-bit extended flag (must be zero in version 2)\n>>>\n>>>      2-bit stage (during merge)\n>>>\n>>>      12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>>>      is stored in this field.\n>>>\n>>>      1-bit skip-worktree flag (used by sparse checkout)\n>>>\n>>>      1-bit intent-to-add flag (used by \"git add -N\")\n>>>\n>>>      14-bit unused, must be zero\n>>>\n>>>    A 16-bit offset, relative to the beginning of this block, to the\n>>>      pathname of this entry. FIXME: make it 32-bit, relative to the\n>>>      beginning of the file, so that we can reuse pathnames from other\n>>>      (old) blocks?\n>>>\n>>\n>> -Elton\n"},{"id":"188725","messageId":"CAKTdtZnWen9+E=XBupRPUWhEy+1pfX4SRdbgZKS-11K-Gxy0hQ@mail.gmail.com","threadId":"30012","inReplyTo":"CAKTdtZm9THdFaSjAONStmOdbs_QxHK5ZWc6_sVaySufKJ6CgEw@mail.gmail.com","subject":"Re: GSoC - Designing a faster index format","fromName":"elton sky","fromEmail":"eltonsky9404@gmail.com","sentAt":"2012-04-07T08:29:49Z","receivedAt":"2012-04-07T08:29:49Z","isPatch":false,"sender":{"key":"eltonsky9404@gmail.com","avatar":null},"body":".... just realize I have to register and submit my proposal on gsoc\nwebsite, rather than here.\n\nI stupidly missed that ...\n\nsilly enough..\n\nOn Fri, Apr 6, 2012 at 1:15 PM, elton sky wrote:\n> NOTE:\n> Please ignore the\n>\n>>- checkpoint : interleave with items in the block, 1 for every 100 items\n>>       4-byte offset to next checkpoint\n>\n> That's irrelevant.\n>\n> Cheers,\n> Elton\n>\n> On Fri, Apr 6, 2012 at 1:13 PM, elton sky wrote:\n>> Thank you everyone for ideas, clues, explanations and questions.\n>> Collectively I wrote my proposal. This one is mostly based on Duy's\n>> suggestion with minor changes.\n>>\n>>\n>> Problem:\n>> Current index store all files in a list. This implies that:\n>> 1. Each operation has to read the whole index and write the whole index back.\n>> 2. computing the checksum for the whole index.\n>> These become expensive when the repo is large.\n>>\n>> Requirement:\n>> Suppose n is the number objects in a repo\n>> -Keep the read/write time <= O(logn).\n>> -Keep the checksum computed against only necessary objects.\n>> -New format is easy to parse.\n>> -Backward compatible.\n>> -Potentially use faster hash method.\n>>\n>> Proposed solution:\n>>\n>> Store the repo structure in a canonical tree. Each directory is a tree\n>> block. A tree block contains blobs and offsets to sub directories. It\n>> has its own checksum. A read/write will be done on tree block base. A\n>> tree block also contains an offset points to its previous version (if\n>> there's one).\n>>\n>> The root of offset is stored in trailer, which stays at the end of\n>> file. Each update creates a new trailer which points to the new tree.\n>> (details below)\n>>\n>> To save the pain of modify a tree block and track the free spaces in\n>> the index, changed blocks are appended at the end. Based on the\n>> assumption that user won't change too many files each time, for an\n>> updated file, all its parent blocks to Root was copied and appended to\n>> index. In other words, all traversed blocks are copied. The offset of\n>> previous version of the updated block is stored in the new block. A\n>> new generation number is stored in copied and updated blocks. Other\n>> blocks are not copied. They are referenced by offsets. After update a\n>> new trailer is created at the end. In this way, there's no harm to\n>> read, and makes write fast.\n>>\n>> Trailer stores the offset of previous trailer. It makes tracking old\n>> versions easy.\n>>\n>> Each operation will load and rewrite the header and visited trailer .\n>>\n>> Checksum for non identifier purpose will use crc32. Otherwise it uses sha1.\n>>\n>> For compatibility, old format of index will be transformed to new\n>> format in the first operation.\n>>\n>> ==\n>> Index format:\n>>\n>> - A 8-byte header consisting of\n>>\n>>    4-byte signature:\n>>      The signature is { 'T', 'R', 'E', 'E' }\n>>\n>>    4-byte version number:\n>>      The current supported versions are 4.\n>>\n>>  - A number of blocks of variable size\n>>\n>>     1-byte block type\n>>\n>>     3-byte content size in byte\n>>\n>>     block content\n>>\n>>     4-byte crc32 of all above\n>>\n>>  - A 20-byte trailer consisting of\n>>\n>>     4-byte trailer signature:\n>>       The signature is { 'R', 'O', 'O', 'T' }\n>>\n>>     4-byte root block offset\n>>\n>>     4-byte extension table offset:\n>>       Zero means no extension\n>>\n>>     4-byte offset to previous trailer\n>>\n>>     4-byte checksum:\n>>       CRC32 of the header and the trailer (excluding this field)\n>>\n>> ==\n>> Tree block:\n>>\n>> Tree block content is basically the list of entries in a specified\n>> path, with all attributes we store in the index now. This entry list\n>> is sorted by pathname. For doing a bsearch in the list, pathnames are\n>> stored at the end of block, which makes the size of entry fixed. The\n>> pathname is pointed from each entry with 2 byte offset (relative to a\n>> block). This should not be problem as a block is never modified.\n>>\n>> It stores the generation number and the offset to old block. It also\n>> integrates the content of cache-tree.\n>>\n>> A tree block content consists of\n>>\n>>  - 4-byte tree object size\n>>\n>>  - 20-byte SHA-1 of the cached tree object\n>>\n>> - checkpoint : interleave with items in the block, 1 for every 100 items\n>>        4-byte offset to next checkpoint\n>>\n>>  - a list attributes corresponding to tree object's item, in the same\n>>   order. These attributes are the same as in DIRC entry format\n>>   except that entry name is removed, and a tree block offset is\n>>   added in case the item is a directory.\n>>\n>>   32-bit ctime seconds, the last time a file's metadata changed\n>>     this is stat(2) data\n>>\n>>   32-bit ctime nanosecond fractions\n>>     this is stat(2) data\n>>\n>>   32-bit mtime seconds, the last time a file's data changed\n>>     this is stat(2) data\n>>\n>>   32-bit mtime nanosecond fractions\n>>     this is stat(2) data\n>>\n>>   32-bit dev\n>>     this is stat(2) data\n>>\n>>   32-bit ino\n>>     this is stat(2) data\n>>\n>>   32-bit mode, split into (high to low bits)\n>>\n>>     4-bit object type\n>>       valid values in binary are 1000 (regular file), 1010 (symbolic link)\n>>       and 1110 (gitlink)\n>>\n>>     3-bit unused\n>>\n>>     9-bit unix permission. Only 0755 and 0644 are valid for regular files.\n>>     Symbolic links and gitlinks have value 0 in this field.\n>>\n>>   32-bit uid\n>>     this is stat(2) data\n>>\n>>   32-bit gid\n>>     this is stat(2) data\n>>\n>>   32-bit file size\n>>     This is the on-disk size from stat(2), truncated to 32-bit.\n>>\n>>   160-bit SHA-1 for the represented object if blobs or the offset\n>>     to another tree block if trees\n>>\n>>   A 32-bit 'flags' field split into (high to low bits)\n>>\n>>     1-bit assume-valid flag\n>>\n>>     1-bit extended flag (must be zero in version 2)\n>>\n>>     2-bit stage (during merge)\n>>\n>>     12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>>     is stored in this field.\n>>\n>>     1-bit skip-worktree flag (used by sparse checkout)\n>>\n>>     1-bit intent-to-add flag (used by \"git add -N\")\n>>\n>>     14-bit unused, must be zero\n>>\n>>      A 16-bit offset, relative to the beginning of this block, to the\n>> pathname of this entry\n>>\n>> - 2-byte generation number, starts from 1\n>>\n>> - 4-byte previous version offset\n>>\n>>  - a list of NUL-terminated pathnames, pointed to from the 16-bit offset\n>>   above\n>>\n>> == Extension table block\n>>\n>> Extension table has block type 'X'. It consists of a series of 4-byte\n>> extension block offset.\n>>\n>> == Extension block\n>>\n>> Extension block has block type 'E'. Extension content is the same as\n>> in the old format.\n>>\n>>\n>>\n>> Time line:\n>>\n>> 24/04 ~ 21/05: get familiar with code base and revise proposal\n>> benchmark with linux kernel on major operations\n>> write prototype to prove feasibility of proposed solution\n>> consult mailing list & irc\n>>\n>> 22/05 ~ 25/06 write code, test and benchmark\n>>        modify tree lib\n>>        modify index format operations\n>>        modify git operations\n>>        transform from old to new\n>>\n>> 26/06 ~ 30/07 revise things according to benchmark\n>>\n>> 31/07 ~ 13/08 update documentation\n>>\n>>\n>> About me\n>>\n>> My name is Elton Tian, I am from China. I have been living in\n>> Australia for quite a few years. I am currently a Master student from\n>> Australia National University. After graduate I worked on linux based\n>> web development (using tcl) for 2.5 years. I have been programming\n>> with c, c#, java, tcl, php, javascript and shell script. But I prefer\n>> c, which gives me the feeling of full control over the program. I am\n>> interested in data intensive computing. I played with hadoop and\n>> mapreduce since 2010. I maintained my 3 node cluster behind my desk.\n>> As linus hates cvs with a passion, I still want to mention I was using\n>> cvs in work, don't like it though. And I guess this is the good chance\n>> to get over it.\n>>\n>> On Thu, Apr 5, 2012 at 2:22 AM, elton sky wrote:\n>>> Hello,\n>>>\n>>> Some updates for Nguyen's index:\n>>>\n>>> On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy wrote:\n>>>> On Wed, Apr 4, 2012 at 3:26 PM, elton sky wrote:\n>>>>> I am not sure how the trailer works.\n>>>>> I assume there can be multiple trailers, each update will generate a\n>>>>> new one. Every trailer will point to the root tree (i.e. all trailers\n>>>>> point to the same block?). So if there are some changes to root, like\n>>>>> rename, trailers all point to the latest root block?\n>>>>\n>>>> Each trailer points to the whole new tree. Because trees are\n>>>> immutable, changing in a tree meangs creating a new one and will also\n>>>> make a new parent tree (to point to the updated tree because old\n>>>> parent will always point to old tree). This eventually leads to root\n>>>> tree change, recorded by the trailer.\n>>>>\n>>>>> Is the index looks like :\n>>>>> | HEADER | TREE BLOCKS | TRAILER |  TREE BLOCKS | TRAILER | TREE\n>>>>> BLOCKS | TRAILER | ...\n>>>>>\n>>>\n>>> Once an update happened to a block, all parent blocks to root will be\n>>> copied to the end of the index. And the updated block will be at leaf\n>>> of the new tree. Finding this path costs logn time anyway. This is no\n>>> harm for read for the whole tree. But in order to find all previous\n>>> changes to a block, we have to go through all trailers and trees.\n>>>\n>>> Otherwise, just modify the original tree. Let the parent points to the\n>>> updated block and let the updated block points to the old block:\n>>>\n>>> parent\n>>>    |\n>>>   V\n>>> updated            old                  old\n>>> block (v3)  -->   block(v2)  -->  block (v1)\n>>>    |\n>>>   V\n>>> child\n>>> blocks\n>>>\n>>> A version number in a tree block is used to track the changes.\n>>> In this way, there's still no harm to read, and it's more easy to\n>>> trace the change history of a block. Also, we don't need to create\n>>> interleaved blocks and trailers. There's only one trailer in the end\n>>> of file. We also need to add another offset points to previous\n>>> version.\n>>>\n>>> Trailer is kept at the end of index, as its size is variable. It\n>>> contains offset to root and list of free spaces.\n>>>\n>>> Changes to format:\n>>>\n>>>> = The git index file has the following format\n>>>\n>>> As is, except there's only one trailer now. And trailer contains list\n>>> of free spaces.\n>>>\n>>>>- A 18-byte trailer consisting of\n>>>>\n>>>>      4-byte trailer signature:\n>>>>        The signature is { 'R', 'O', 'O', 'T' }\n>>>>\n>>>>      2-byte generation:\n>>>>         The first trailer is 0, the second 1 and so on.\n>>>>\n>>>>      4-byte root block offset\n>>>>\n>>>>      4-byte extension table offset:\n>>>>        Zero means no extension\n>>>>\n>>>        list of free spaces\n>>>        - 4 byte offset\n>>>        - 2 byte length\n>>>\n>>>>      4-byte checksum:\n>>>>        CRC32 of the header and the trailer (excluding this field)\n>>>\n>>> Free space list is read/written in whole for each operation, together\n>>> with trailer.\n>>>\n>>>>\n>>>> == Tree block\n>>>> ...\n>>>\n>>> Above as is.\n>>>\n>>> - 1 byte version num\n>>>\n>>> - 4 byte offset to previous version block\n>>>\n>>>>\n>>>>    160-bit SHA-1 for the represented object if blobs or the offset\n>>>>      to another tree block if trees\n>>>>\n>>>>    A 32-bit 'flags' field split into (high to low bits)\n>>>>\n>>>>      1-bit assume-valid flag\n>>>>\n>>>>      1-bit extended flag (must be zero in version 2)\n>>>>\n>>>>      2-bit stage (during merge)\n>>>>\n>>>>      12-bit name length if the length is less than 0xFFF; otherwise 0xFFF\n>>>>      is stored in this field.\n>>>>\n>>>>      1-bit skip-worktree flag (used by sparse checkout)\n>>>>\n>>>>      1-bit intent-to-add flag (used by \"git add -N\")\n>>>>\n>>>>      14-bit unused, must be zero\n>>>>\n>>>>    A 16-bit offset, relative to the beginning of this block, to the\n>>>>      pathname of this entry. FIXME: make it 32-bit, relative to the\n>>>>      beginning of the file, so that we can reuse pathnames from other\n>>>>      (old) blocks?\n>>>>\n>>>\n>>> -Elton\n"}]}