{"thread":{"id":"26954","subject":"Proposed design of fast-export helper","startedAt":"2011-04-01T06:14:38Z","lastAt":"2011-04-08T06:47:41Z","messageCount":4,"participants":["Ramkumar Ramachandra","Jonathan Nieder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"164854","messageId":"20110401061434.GA4469@kytes","threadId":"26954","inReplyTo":null,"subject":"Proposed design of fast-export helper","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2011-04-01T06:14:38Z","receivedAt":"2011-04-01T06:14:38Z","isPatch":false,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Hi Jonathan,\n\n(+CC: Git List, Junio)\n\nThis is the proposed design for a new \"fast-export helper library\".\nNormally, this would be an RFC patch; however, I'm not happy with the\ndesign, and I'd like some input before starting off.\n\nThe Problem\n-----------\nsvn-fi, a program to convert a git-fast-import stream to\na Subversion dumpfile, has hit a dead-end [1]. This is because it\ndoesn't know how to handle any `` except 'inline' (this\nappears inside `filemodify`, `notemodify`, `ls` and `cat-blob`\ncommands).\n\nThe other two kinds of `` that exporters can produce are:\n1. A mark reference (`:`) set by a prior `blob` command\n2. A full 40-byte SHA-1 of an existing Git blob object.\n\nThe most naive solution will involve modifying svn-fi to persist blobs\nin-memory as soon as it sees one after a `blob` command (this is the\napproach that git2svn uses). However, this solution is both expensive\nin memory and highly unscalable. Also, svn-fi's job is lightweight\nparsing and conversion from one format to another- I don't want to\nclutter it up with this additional complexity.\n\nThe other alternative that svn-fi currently uses: --inline-blobs [2].\nThis is a modification to the git-fast-export so that it only ever\nproduces inlined blobs. However, this has severe drawbacks, the main\none being that every exporter must implement it for it to become\naccepted. You also pointed out another problem: One blob may be\nreferenced multiple times in the same stream, especially when dealing\nwith cherry-picks and rebases (when branch support is added to\nsvn-fi); writing it out explicitly that many times will pollute the\nstream unnecessarily large with a lot of redundant data. In the best\ncase, this can simply be a way to hint the git-fast-export to minimize\nthe work that the helper has to do.\n\nJunio suggested using a fast-import-filter that can convert a\nfast-import stream from the current format to one that contains only\ninlined blobs [3]. The final proposal for the implementation differs,\nbecause I don't like the idea of having to parse the data twice and do\nthe same error handling in two different places (svn-fi and the\nfast-import-filter).\n\nThe library's API\n-----------------\nI've thought of building a sort of library which applications can link\nto. The API is as follows:\nint write_blob(unit32_t, char *, size_t, FILE *);\nint fetch_blob_mark(unit32_t, struct strbuf *);\nint fetch_blob_sha1(char *sha1, struct strbuf *); /* sha1[20] */\n\nThe svn-fi parser should call write_blob when it encounters some data\nthat it wants to persist. The arguments are:\n\n1. A mark using which the blob can be recalled using fetch_blob_mark\n(optional: use 0 to omit).\n2. A terminator character in the case of delimited format. Should be\nNULL when the format is non-delimited.\n3. In the case of the delimited format, the size of the delimeter\nitself. Otherwise, the size of the blob itself.\n4. The FILE * to parse the blob from, which is already seeked to the\nright position and ready to parse.\n\nThe library then parses this data and dumps it into a storage backend\n(described later) after computing its SHA1.\n\nfetch_blob_mark and fetch_blob_sha1 can then be used to fetch blobs\nusing their mark or SHA1. Fetching blobs using their mark should be\nO(1), while locating the exact SHA1 will require a bisect of sorts:\nslightly better than O(log (n)).\n\nHow the library works\n---------------------\nIt maintains an sorted list of (SHA1, off_t, off_t) triplets in a\nbuffer along with a 256-entry fanout table (call this blob_index) --\nthis is mmap'ed, and only munmap'ed at the end of the program. When\nwrite_blob is invoked, the blob is read from the FILE, and its SHA1 is\ncomputed. Then it is written to another big buffer (call this\nblob_buffer) after an inexpensive zlib deflate along with its deflated\nsize, and its (SHA1, offset1, offset2) is written to the blob_index --\nthe first number refers to the blob_buffer number (there are many\nblob_buffers), and the second offset refers to the offset within that\nblob_buffer. No dobut, this is an expensive table to maintain, but we\ndon't have a choice in the matter -- there's nothing in the spec\npreventing a dataref from referring to blobs using their marks and\nSHA1s interchangably.\n\nFor marks, there is another marks_buffer which stores (uint32_t,\noff_t, off_t) triplets.\n\nSo, what do you think?\n\n-- Ram\n\n[1]: http://thread.gmane.org/gmane.comp.version-control.git/170290\n[2]: http://thread.gmane.org/gmane.comp.version-control.git/170290/focus=170292\n[3]: http://thread.gmane.org/gmane.comp.version-control.git/165237/focus=165289\n"},{"id":"165385","messageId":"20110407230249.GA20226@elie","threadId":"26954","inReplyTo":"20110401061434.GA4469@kytes","subject":"Re: Proposed design of fast-export helper","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-07T23:03:19Z","receivedAt":"2011-04-07T23:03:19Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nRamkumar Ramachandra wrote:\n\n> The other two kinds of `` that exporters can produce are:\n> 1. A mark reference (`:`) set by a prior `blob` command\n> 2. A full 40-byte SHA-1 of an existing Git blob object.\n\nThe above is very git-specific --- arbitrary foreign vcs-es are\nunlikely to all use 40-byte hashes as . So far I've been\nassuming that a is sufficiently \"nice\" (not containing\nspaces, NULs, quotation marks, or newlines nor starting with a colon).\n\nIt would be better to come up with a more formal rule and document it.\n\n> The most naive solution will involve modifying svn-fi to persist blobs\n> in-memory as soon as it sees one after a `blob` command (this is the\n> approach that git2svn uses). However, this solution is both expensive\n> in memory and highly unscalable.\n\nI suppose it also means trouble with large (>4 GiB) files on 32-bit\narchitectures. Of course git proper does not support those anyway.\n\n[...]\n> The other alternative that svn-fi currently uses: --inline-blobs [2].\n> This is a modification to the git-fast-export so that it only ever\n> produces inlined blobs. However, this has severe drawbacks\n[... explanation of drawbacks to relying on \"inline\" data only ...]\n> In the best\n> case, this can simply be a way to hint the git-fast-export to minimize\n> the work that the helper has to do.\n\nYes.\n\n> The library's API\n> -----------------\n> I've thought of building a sort of library which applications can link\n> to. The API is as follows:\n> int write_blob(unit32_t, char *, size_t, FILE *);\n> int fetch_blob_mark(unit32_t, struct strbuf *);\n> int fetch_blob_sha1(char *sha1, struct strbuf *); /* sha1[20] */\n\nHmm.\n\nWhat the first function does is not obvious without argument names.\nI had guessed it would write a blob to file. More nits:\n\n - the type of marks in fast-import is uintmax_t (yech) --- they're\n not restricted to 32-bit integers as far as I know.\n\n - missing \"const\" before char *. :)\n\n - lengths of subsets of files should be of type off_t, if we want\n to allow 64-bit lengths on 32-bit architectures. If this is\n git-specific, it would be more consistent to use \"unsigned long\".\n\n - the size that toggles between size of a delimiter and length of\n file seems strange to me. I'd rather have two separate functions.\n\n - this requires the frontend to think in terms of git blob object\n names, which doesn't fit well with most applications I'm thinking\n of (think: fast-import backends in C that if written in python\n would use python-fastimport).\n\nI assume the delimited format works as in fast-import's \"data\" command\n(and only supports blobs ending with LF)?\n\n[...]\n> The library then parses this data and dumps it into a storage backend\n> (described later) after computing its SHA1.\n\nRight, so a nice aspect of this exercise is that the nature of the\nkey/value store is hidden from the caller.\n\n> fetch_blob_mark and fetch_blob_sha1 can then be used to fetch blobs\n> using their mark or SHA1. Fetching blobs using their mark should be\n> O(1), while locating the exact SHA1 will require a bisect of sorts:\n> slightly better than O(log (n)).\n\nhttp://fanf.livejournal.com/101174.html\n\n> How the library works\n\nI wonder if it would be sensible to make it run as a separate process.\nThe upside: writing to and from pipes is easy in a variety of\nprogramming languages (including the shell), even easier than calling\nC code. So in particular that would make testing it easier. But\nperformance considerations might outweigh that.\n\nI also wonder if it is possible or makes sense to make the API less\ngit-specific. If the buffers were in-memory, something like\n\n\tset(key, value);\n\tvalue = get(key);\n\nwould do. Since they are not, maybe something vaguely like\n\n\tFILE *f = kvstore_fopen(key, O_WRONLY);\n\tfwrite(value, sz, 1, f);\n\tkvstore_fclose(f);\n\n\tFILE *f = kvstore_fopen(key, O_RDONLY);\n\tstrbuf_fread(&value, SIZE_MAX, f);\n\tkvstore_fclose(f);\n\nwould be something to aim for. For the getter case, fmemopen is\nportable (in case one wants to just put the value in memory) but\nfopencookie (in case one doesn't) is not, so the idea does not work as\nnicely as one might like. And it's not quite the right abstraction\n--- for a fast-import backend, I suppose the operations needed are:\n\n * get length\n * dump the value to a caller-specified FILE * or fd\n * let the caller read the value one chunk or line at a time to\n transform it (e.g., to escape special characters).\n\nIs there prior art that this could mimic or reuse (so we can learn\nfrom others' mistakes and make sure the API feels familiar)?\n\nHope that helps,\nJonathan\n"},{"id":"165399","messageId":"20110408053326.GA27332@kytes","threadId":"26954","inReplyTo":"20110407230249.GA20226@elie","subject":"Re: Proposed design of fast-export helper","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2011-04-08T05:33:32Z","receivedAt":"2011-04-08T05:33:32Z","isPatch":false,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Hi Jonathan,\n\nJonathan Nieder writes:\n> Ramkumar Ramachandra wrote:\n> > The other two kinds of `` that exporters can produce are:\n> > 1. A mark reference (`:`) set by a prior `blob` command\n> > 2. A full 40-byte SHA-1 of an existing Git blob object.\n> \n> The above is very git-specific --- arbitrary foreign vcs-es are\n> unlikely to all use 40-byte hashes as . So far I've been\n> assuming that a is sufficiently \"nice\" (not containing\n> spaces, NULs, quotation marks, or newlines nor starting with a colon).\n> \n> It would be better to come up with a more formal rule and document it.\n\nActually, we need to tighten this thing before we build\nanything else- it's a nightmare to handle a stream that refers to the\nsame blob using the mark the first time, the SHA1 the second time, and\nthe MD5 the third time. How is our store supposed to know how to\nindex and retrieve blobs?\n\nNext step: We should find out all the things can currently\nbe, by looking at existing frontend implementation. Then, we should\ncome tighten the spec so that it doesn't clobber any of those things.\nAlso, we should find a way to let the backend know \"how\" to index/\nretrieve a blob -- this is only straightforward in the case of marks.\n\n> I assume the delimited format works as in fast-import's \"data\" command\n> (and only supports blobs ending with LF)?\n\nYes. This is actually quite an ugly to support -- We should probably\ndrop support for this.\n\nSigned-off-by: Ramkumar Ramachandra \n\ndiff --git a/Documentation/git-fast-import.txt b/Documentation/git-fast-import.txt\nindex 2c2ea12..1fb71f7 100644\n--- a/Documentation/git-fast-import.txt\n+++ b/Documentation/git-fast-import.txt\n@@ -826,8 +826,8 @@ of the next line, even if `` did not end with an `LF`.\n Delimited format::\n \tA delimiter string is used to mark the end of the data.\n \tfast-import will compute the length by searching for the delimiter.\n-\tThis format is primarily useful for testing and is not\n-\trecommended for real data.\n+\tThis format is should only be used for testing; other\n+\tbackends are not required to support this.\n +\n ....\n \t'data' SP '<<' LF\n\n\n> > fetch_blob_mark and fetch_blob_sha1 can then be used to fetch blobs\n> > using their mark or SHA1. Fetching blobs using their mark should be\n> > O(1), while locating the exact SHA1 will require a bisect of sorts:\n> > slightly better than O(log (n)).\n> \n> http://fanf.livejournal.com/101174.html\n\nRight, but this discussion is now useless, since keys can be just\nabout anything.\n\n> > How the library works\n> \n> I wonder if it would be sensible to make it run as a separate process.\n> The upside: writing to and from pipes is easy in a variety of\n> programming languages (including the shell), even easier than calling\n> C code. So in particular that would make testing it easier. But\n> performance considerations might outweigh that.\n\nPerformance and portability considerations. Calling semantics will\nprobably be highly inelegant too, since full-blown bi-directional\ncommunication is necessary.\n\n> I also wonder if it is possible or makes sense to make the API less\n> git-specific. If the buffers were in-memory, something like\n> \n> \tset(key, value);\n> \tvalue = get(key);\n> \n> would do. Since they are not, maybe something vaguely like\n> \n> \tFILE *f = kvstore_fopen(key, O_WRONLY);\n> \tfwrite(value, sz, 1, f);\n> \tkvstore_fclose(f);\n> \n> \tFILE *f = kvstore_fopen(key, O_RDONLY);\n> \tstrbuf_fread(&value, SIZE_MAX, f);\n> \tkvstore_fclose(f);\n\nI don't like this. The caller should not have to know about whether\nblobs are persisted in-memory or on-disk. When there are a few small\nfrequently-used blobs, the key-value might decide to persist them in\nmemory, and we should allow for this kind of optimization.\n\n> would be something to aim for. For the getter case, fmemopen is\n> portable (in case one wants to just put the value in memory) but\n> fopencookie (in case one doesn't) is not, so the idea does not work as\n> nicely as one might like. And it's not quite the right abstraction\n> --- for a fast-import backend, I suppose the operations needed are:\n> \n> * get length\n> * dump the value to a caller-specified FILE * or fd\n> * let the caller read the value one chunk or line at a time to\n> transform it (e.g., to escape special characters).\n> \n> Is there prior art that this could mimic or reuse (so we can learn\n> from others' mistakes and make sure the API feels familiar)?\n\nKyoto Cabinet, or just any key-value store for that matter. All prior\ndiscussion related to SHA1 is useless then, because the key can be\njust about anything: the only option we have is to implement the\nhashtable as a data structure with a very high fanout value like a B+\ntree. Obviously, this will be less efficient than a store which keys\neverything using a fixed 20-byte SHA1 -- how much speed are we willing\nto trade off for the sake of this simplicity?\n\n-- Ram\n"},{"id":"165401","messageId":"20110408064741.GA22462@elie","threadId":"26954","inReplyTo":"20110408053326.GA27332@kytes","subject":"Re: Proposed design of fast-export helper","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-08T06:47:41Z","receivedAt":"2011-04-08T06:47:41Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi again,\n\nRamkumar Ramachandra wrote:\n\n> Next step: We should find out all the things can currently\n> be, by looking at existing frontend implementation.\n\nThere are only a few places a can come from.\n\n * marks (\":5\"-style datarefs and from the marks file)\n * output from the \"ls\" or \"cat\" command\n * out-of-band knowledge by the frontend about this specific backend\n (e.g., \"I know git fast-import supports git-style blob names, so I\n will use them\").\n\n> Then, we should\n> come tighten the spec so that it doesn't clobber any of those things.\n> Also, we should find a way to let the backend know \"how\" to index/\n> retrieve a blob -- this is only straightforward in the case of marks.\n\nIf this key/value store is specifically for use with fast-import\nbackends, I'd prefer it just deal with marks. Caching responses to\nlookup of blobs using a backend-specific format is a\ndifferent problem.\n\n>> I assume the delimited format works as in fast-import's \"data\" command\n>> (and only supports blobs ending with LF)?\n>\n> Yes. This is actually quite an ugly to support -- We should probably\n> drop support for this.\n>\n> Signed-off-by: Ramkumar Ramachandra \n>\n> diff --git a/Documentation/git-fast-import.txt b/Documentation/git-fast-import.txt\n> index 2c2ea12..1fb71f7 100644\n> --- a/Documentation/git-fast-import.txt\n> +++ b/Documentation/git-fast-import.txt\n> @@ -826,8 +826,8 @@ of the next line, even if `` did not end with an `LF`.\n> Delimited format::\n> \tA delimiter string is used to mark the end of the data.\n> \tfast-import will compute the length by searching for the delimiter.\n> -\tThis format is primarily useful for testing and is not\n> -\trecommended for real data.\n> +\tThis format is should only be used for testing; other\n> +\tbackends are not required to support this.\n\nThat would mean git's fast-import test suite couldn't be used with\narbitrary fast-import backends. The delimited format is also very\nconvenient for testing \"by hand\". I'm not convinced it's that hard to\nsupport.\n\n> Performance and portability considerations. Calling semantics will\n> probably be highly inelegant too, since full-blown bi-directional\n> communication is necessary.\n\nTakes command on stdin, writes response to stdout. Seems kind of\ntypical for helper programs, but you are right to mention that shell\nscripts do not deal so well with that when the helper process needs\nto handle multiple requests.\n\ne.g., see /usr/share/debconf/confmodule.\n\n> Jonathan Nieder writes:\n\n>> \tFILE *f = kvstore_fopen(key, O_WRONLY);\n>> \tfwrite(value, sz, 1, f);\n>> \tkvstore_fclose(f);\n>> \n>> \tFILE *f = kvstore_fopen(key, O_RDONLY);\n>> \tstrbuf_fread(&value, SIZE_MAX, f);\n>> \tkvstore_fclose(f);\n>\n> I don't like this. The caller should not have to know about whether\n> blobs are persisted in-memory or on-disk. When there are a few small\n> frequently-used blobs, the key-value might decide to persist them in\n> memory, and we should allow for this kind of optimization.\n\nA FILE * can have a pipe underlying it, or a memory area (with\nfmemopen). But I agree that using FILE * here would be a bad API\nafter all, for other reasons (the FILE * operations are just not quite\nright).\n\n>> Is there prior art that this could mimic or reuse (so we can learn\n>> from others' mistakes and make sure the API feels familiar)?\n>\n> Kyoto Cabinet\n\nYikes, its API is complicated. :) Does Kyoto Cabinet support values\nlonger than a size_t can describe? Maybe that's not worth supporting\nafter all (I guess it would be nice to have an example of a 4 GiB file\nin version control to motivate it first).\n\n> Obviously, this will be less efficient than a store which keys\n> everything using a fixed 20-byte SHA1\n\nSure, sticking to fixed-length, 20-byte keys could be reasonable if\nthat's what the application requires. Is this for caching or for\navoiding an internal marks table?\n"}]}