{"thread":{"id":"40334","subject":"Bloom filters for have/want negotiation","startedAt":"2015-09-11T21:13:25Z","lastAt":"2015-09-14T03:40:53Z","messageCount":6,"participants":["Michael Haggerty","Junio C Hamano","Shawn Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"269796","messageId":"55F343F5.6010903@alum.mit.edu","threadId":"40334","inReplyTo":null,"subject":"Bloom filters for have/want negotiation","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-09-11T21:13:25Z","receivedAt":"2015-09-11T21:13:25Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"I have been thinking about Wilhelm Bierbaum's talk at the last GitMerge\nconference [1] in which he describes a scheme for using Bloom filters to\nmake the initial reference advertisement less expensive.\n\nIn his scheme (if I understand correctly) the client starts off the\nconversation by passing the server a Bloom filter that indicates what\n(refname, SHA-1) pairs the client already has. This makes it unnecessary\nfor the server to advertise those references, thereby reducing the cost\nof incremental fetches dramatically if the server has very many references.\n\nBecause Bloom filters have false positives, this scheme is not 100%\nreliable. Therefore I don't think we would want Git to depend on it.\n\nBut it got me thinking about how the client could use a Bloom filter in\na later stage of the negotiation, when telling the server what objects\nit already has, while preserving 100% reliability.\n\nThe idea is to use connectivity information to correct mistakes caused\nby reliance on the Bloom-filter:\n\n1. The server advertises the references that it has in the way that it\nis currently done.\n2. The client advertises the objects that it has (or some subset of\nthem; see below) via a Bloom filter.\n3. The server sends the client the packfile that results from assuming\nthat the Bloom filter is giving correct answers. (This might mean that\ntoo few objects are sent to the client.)\n4. The client does a connectivity check on the packfile. If any objects\nare missing, it asks the server for them via a reliable\n(non-Bloom-filter-based) request.\n\nHow would one construct the Bloom filter for step 2? (Remember that a\nproperly-configured Bloom filter requires about 5 bits of space per\nvalue stored for each factor of 0.1 in the false-positive rate. So, for\nexample, to store 5000 values with a 1% false-positive rate, the Bloom\nfilter would need to be approximately 5000 * 10 bits = 6.2 kB in size.)\n\nHere are some possible schemes:\n\n* Record *all* objects in the Bloom filter. The Git repo has\napproximately 200k objects, so, supposing that we could live with a 10%\nfalse-positive rate (see below), the Bloom filter would need to be about\n125 kB.\n\n* Record all commit objects in the Bloom filter. For the Git repo that\nis about 40k commits, so for a 10% error rate the Bloom filter would\nhave to be about 25 kB.\n\n* Record some subset of commits; for example, all unique branch and tag\ntips, the peeled tags, plus some sparse subsets of commits deeper in the\nhistory. The ls-remote for the Git repo lists 1730 unique SHA-1s, so,\nsupposing we choose 10x that number with a 1% error rate, the Bloom\nfilter would be about 20 kB.\n\n* Record only the branch and tag tips and peeled tags. Please note that\nfor situations where the client has fetched from the server before and\nstill has the remote-tracking references from that fetch, this scheme\nmight work surprisingly well. For the Git repository, with a 1% error\nrate, this would be about 2 kB.\n\nFor the first two schemes, we could tolerate a pretty high error rate\nbecause the server could perform additional consistency checks to reduce\nthe error rate. For example, if the Bloom filter reports that the client\nhas commit X, but that the client does *not* have a parent of X, then\nthe server can assume that the check of X was a false positive and\ndiscard it. Such consistency checks would not be possible with the third\nor fourth schemes, so I have chosen lower false-positive rates for those\nschemes.\n\nAdditional points:\n\n* The client can decide what to include in the Bloom filter. For\nexample, if it has done a recent fetch from the server, it might want to\nsend only the remote-tracking branch tips. But if it has never fetched\nfrom this server before, it might want to send all commits.\n\n* A Bloom filter could be computed at repack time rather than at each\nfetch. On fetch, the precomputed Bloom filters could be loaded, any\nloose objects added to it, and the result sent to the server.\n\nI don't have a gut feeling about the cost of this phase of the\nnegotiation, so I don't know whether this would be a net savings, let\nalone one that is worth the added complexity. But I wanted to document\nthe idea in case somebody thinks it has promise. (I have no plans to\npursue it.)\n\nMichael\n\n[1] http://git-merge.com/videos/scaling-git-at-twitter-wilhelm-bierbaum.html\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"269798","messageId":"xmqqfv2kzl91.fsf@gitster.mtv.corp.google.com","threadId":"40334","inReplyTo":"55F343F5.6010903@alum.mit.edu","subject":"Re: Bloom filters for have/want negotiation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-09-11T21:42:02Z","receivedAt":"2015-09-11T21:42:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> 1. The server advertises the references that it has in the way that it\n> is currently done.\n> 2. The client advertises the objects that it has (or some subset of\n> them; see below) via a Bloom filter.\n> 3. The server sends the client the packfile that results from assuming\n> that the Bloom filter is giving correct answers. (This might mean that\n> too few objects are sent to the client.)\n\nWouldn't this end up sending objects the server has (perhaps\nreachable from a branch that is not advertised to the client) that\nis not reachable from the tips the client asked upon a false hit?\nIf so, that has security ramifications for servers who restrict what\nyou can download based on who you are (and which branches are\nsupposed to be visible to you).\n\nUsing bloom filter (perhaps invertible ones) to identify what the\nreceiving end lacks is certainly an intriguing approach, though.\n"},{"id":"269814","messageId":"CAJo=hJstD8c2RPUAj2OznFSCuyJsKFmvymsQMHOPhGdaqPgyvg@mail.gmail.com","threadId":"40334","inReplyTo":"55F343F5.6010903@alum.mit.edu","subject":"Re: Bloom filters for have/want negotiation","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-09-12T05:16:54Z","receivedAt":"2015-09-12T05:16:54Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Fri, Sep 11, 2015 at 2:13 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> I have been thinking about Wilhelm Bierbaum's talk at the last GitMerge\n> conference [1] in which he describes a scheme for using Bloom filters to\n> make the initial reference advertisement less expensive.\n...\n> But it got me thinking about how the client could use a Bloom filter in\n> a later stage of the negotiation, when telling the server what objects\n> it already has, while preserving 100% reliability.\n...\n> I don't have a gut feeling about the cost of this phase of the\n> negotiation, so I don't know whether this would be a net savings, let\n> alone one that is worth the added complexity. But I wanted to document\n> the idea in case somebody thinks it has promise. (I have no plans to\n> pursue it.)\n\nMaybe I can help... it just so happens that I have Git servers at\n$DAY_JOB instrumented in the smart HTTP negotiate code. They do \"many\"\nfetch requests. :)\n\nThe average client is only sending 16 have lines; at 50 bytes/line\nthis is 800 bytes.\n\nThe worst case is due to a bug in the negotiation. With nothing\ncommon, the client just goes on forever until it reaches roots\n(something is wrong with MAX_IN_VAIN). We saw 56,318 have lines ... a\n2.6 MiB section. But smart HTTP gzips, so this may be only 1.3 MiB on\nthe wire.\n\nBut average/worst doesn't tell the entire picture. Bucketing requests\nby have lines gives us more:\n\n  %req | have_lines\n  -----|-----------\n  100%   56,318\n   99%       88\n   98%       52\n   97%       35\n   96%       31\n   95%       26\n\n95% of requests have <= 26 have lines, or ~650 bytes after gzip on smart HTTP.\n99% of requests have <= 88 have lines, like 2.15 KiB after gzip.\n\nThe smart HTTP client with nodone extension is allowed to send up to\n1024 have lines in a single round trip; if the server can make an\nefficient graph cut using only that batch, it can immediately return\nthe pack in that same round trip.\n\nErgo, if this is all working correctly on smart HTTP, clients can\nfetch from a server they already \"know\" with decent efficiency, and\nsmaller than your 2 KiB Bloom filter estimate for git.git at 1% error\nrate.\n\n\nIn practice this is not what always happens. The client isn't making\ngreat decisions about what to send on smart HTTP. For example I have\nobserved a fetch session where the client sends:\n\n  req #1:  16 haves\n  req #2:  26 haves\n  req #3:  45 haves\n  req #4:  70 haves ... and done\n\nSo that is 4 round trips. It started out with 16; waited for common\nACKs. I guess 10 were common but no clean graph cut was made so the\nclient send another 16 to make 26. Again no clean cut so it added more\nto send 45, then finally at 70 we found the cut point.\n\nReading fetch-pack.c, the first flush is at 16 lines. On the 2nd\nrequest my intent was to double to 32 lines, but its not because count\nis not reset to 0. So flush_at starts at 16, doubles to 32, but count\nstays at 16 and only 16 new lines can be sent in the next packet, when\nthe intent was to try probing 32 on the second round. IOW fetch-pack.c\nis not expanding the have window as quickly as I wanted.\n\nIn reality the above session probably sent:\n\n  16 new,  0 state = 16 haves\n  16 new, 10 state = 26 haves\n  32 new, 13 state = 45 haves\n  ?? new, ?? state = 70 haves\n\nMaybe 120 unique have lines.\n\n\nLooking at my request data and your Bloom filter \"budget\" of 2 KiB ..\nwe could just update fetch-pack.c to send 88 have lines in the first\nrequest burst. 90+-ish% of my user's traffic might be served in just 1\nround trip on smart HTTP, instead of 4.\n\n\nThis smart HTTP study also applies to the traditional bi-directional\nprotocol. With multi_ack the sends a 2nd batch while waiting for reply\nfrom the server. With data moving in both directions on the wire total\nround-trips becomes less important and its just data volume. But again\nwe are talking about 120 unique have lines, so 5.9 KiB (no\ncompression).\n\nThe have lines are very verbose in text format. Just using a binary\nSHA-1 would nearly halve the negotiation to ~3 KiB. Binary SHA-1 have\nline extension to upload-pack extension is far simpler than a Bloom\nfilter.\n\nI do wonder if we are stuffing the pipe deep enough with multi_ack on\nInternet links. Git doesn't need very long to walk 16 commits,\ncertainly less than the 200 ms RTT a user might have talking to a\nserver on the other side of the US. It is possible both sides are\nspending most of their time waiting for data transfer of the batches\nin flight.\n"},{"id":"269832","messageId":"xmqqtwqzxy09.fsf@gitster.mtv.corp.google.com","threadId":"40334","inReplyTo":"CAJo=hJstD8c2RPUAj2OznFSCuyJsKFmvymsQMHOPhGdaqPgyvg@mail.gmail.com","subject":"Re: Bloom filters for have/want negotiation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-09-12T19:01:42Z","receivedAt":"2015-09-12T19:01:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce <spearce@spearce.org> writes:\n\n> The worst case is due to a bug in the negotiation. With nothing\n> common, the client just goes on forever until it reaches roots\n> (something is wrong with MAX_IN_VAIN). We saw 56,318 have lines ... a\n> 2.6 MiB section. But smart HTTP gzips, so this may be only 1.3 MiB on\n> the wire.\n\nThis one is interesting.\n\n> But average/worst doesn't tell the entire picture. Bucketing requests\n> by have lines gives us more:\n>\n>   %req | have_lines\n>   -----|-----------\n>   100%   56,318\n>    99%       88\n>    98%       52\n>    97%       35\n>    96%       31\n>    95%       26\n\nSo is this.  From this observation, at least for your audience, it\nis expected that we would usually not need a very long back and\nforth session to discover where the history diverges.\n\nBut that is kind of expected.  Because the current protocol, in\nwhich the upload-pack speaks first and advertises all tips it has,\nallows the fetcher to omit what is known to be common very early and\nto concentrate on sending the \"have\"s from the branches the fetcher\nhas worked on since the last time it fetched.  The amount of \"have\"s\nneeded is expected to be small in an \"everybody meets at the same\ncentral place and pushes into and fetches out of there\" workflow,\nbecause the amount of work done by a single fetcher since the last\nfetch will by definition be a lot smaller than what happened in the\ncentral meeting place.\n\nI wonder how flipping the \"who speaks first\" would affect that\nequation, though.\n\n> Ergo, if this is all working correctly on smart HTTP, clients can\n> fetch from a server they already \"know\" with decent efficiency, and\n> smaller than your 2 KiB Bloom filter estimate for git.git at 1% error\n> rate.\n\nIsn't this part a bit of oranges and apples comparison?  If I\nunderstand the motivation of Michael's looking into Bloom filter or\nsome other techniques correctly, it is to find a way to address the\ninitial advertisement from the sender.  Your analysis is about the\namount of \"have\", which is an orthogonal issue.\n\n> I do wonder if we are stuffing the pipe deep enough with multi_ack on\n> Internet links. Git doesn't need very long to walk 16 commits,\n> certainly less than the 200 ms RTT a user might have talking to a\n> server on the other side of the US. It is possible both sides are\n> spending most of their time waiting for data transfer of the batches\n> in flight.\n\nYes, this is a very useful insight.  An experiment or two with\nlarger amount of data in flight may be an interesting thing to try.\nDo we still have the deadlock possibility caused by our implicit\nreliance on the fact that a single batch was expected to fit in a\npipe buffer, by the way, or have we addressed that issue already?\n"},{"id":"269834","messageId":"CAJo=hJucwWJWBDXay8ZmxVGYyM3GmpN5fnmyq8MMubo+1GRMEA@mail.gmail.com","threadId":"40334","inReplyTo":"xmqqtwqzxy09.fsf@gitster.mtv.corp.google.com","subject":"Re: Bloom filters for have/want negotiation","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2015-09-12T19:21:42Z","receivedAt":"2015-09-12T19:21:42Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Sat, Sep 12, 2015 at 12:01 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Shawn Pearce <spearce@spearce.org> writes:\n>\n>> The worst case is due to a bug in the negotiation. With nothing\n>> common, the client just goes on forever until it reaches roots\n>> (something is wrong with MAX_IN_VAIN). We saw 56,318 have lines ... a\n>> 2.6 MiB section. But smart HTTP gzips, so this may be only 1.3 MiB on\n>> the wire.\n>\n> This one is interesting.\n>\n>> But average/worst doesn't tell the entire picture. Bucketing requests\n>> by have lines gives us more:\n>>\n>>   %req | have_lines\n>>   -----|-----------\n>>   100%   56,318\n>>    99%       88\n>>    98%       52\n>>    97%       35\n>>    96%       31\n>>    95%       26\n>\n> So is this.  From this observation, at least for your audience, it\n> is expected that we would usually not need a very long back and\n> forth session to discover where the history diverges.\n>\n> But that is kind of expected.  Because the current protocol, in\n> which the upload-pack speaks first and advertises all tips it has,\n> allows the fetcher to omit what is known to be common very early and\n> to concentrate on sending the \"have\"s from the branches the fetcher\n> has worked on since the last time it fetched.  The amount of \"have\"s\n> needed is expected to be small in an \"everybody meets at the same\n> central place and pushes into and fetches out of there\" workflow,\n> because the amount of work done by a single fetcher since the last\n> fetch will by definition be a lot smaller than what happened in the\n> central meeting place.\n\nCorrect... this was based around a very central meeting place.\n\nLinus pulling from lieutenants likely has very different behavior.\nDuring the merge window, Linus' repo probably has hundreds of commits\nnot in the peer he is currently pulling from. The have line\ntransmission may take some time to find a common base.\n\n>> Ergo, if this is all working correctly on smart HTTP, clients can\n>> fetch from a server they already \"know\" with decent efficiency, and\n>> smaller than your 2 KiB Bloom filter estimate for git.git at 1% error\n>> rate.\n>\n> Isn't this part a bit of oranges and apples comparison?  If I\n> understand the motivation of Michael's looking into Bloom filter or\n> some other techniques correctly, it is to find a way to address the\n> initial advertisement from the sender.  Your analysis is about the\n> amount of \"have\", which is an orthogonal issue.\n\nNo, I think you confused parts of the thread.\n\nMichael started this thread with a lead-in about ref advertisement\nthen punted and went to a discussion about the have negotiation. The\nBloom filter estimates he was writing were for the client to explain\nhis current state to the server, replacing the \"have\" negotiation.\n\n>> I do wonder if we are stuffing the pipe deep enough with multi_ack on\n>> Internet links. Git doesn't need very long to walk 16 commits,\n>> certainly less than the 200 ms RTT a user might have talking to a\n>> server on the other side of the US. It is possible both sides are\n>> spending most of their time waiting for data transfer of the batches\n>> in flight.\n>\n> Yes, this is a very useful insight.  An experiment or two with\n> larger amount of data in flight may be an interesting thing to try.\n> Do we still have the deadlock possibility caused by our implicit\n> reliance on the fact that a single batch was expected to fit in a\n> pipe buffer, by the way, or have we addressed that issue already?\n\nWe still deadlock if the pipe buffer is smaller than the batch size.\n\nI was thinking last night this could be reworked in fetch-pack.c to be\na select() based process.\n\nInstead of immediately writing each have line to the socket, queue\nthem in a strbuf like we do with stateless_rpc. If the strbuf length\nis > 0 add the socket to the writeable FD_SET. Run select() with 0\ntimeout every 5 commit iterations to see if the remote side is\nreadable or writeable.\n\nIf its readable, read the replies from the server and see how that\nleaves the client state. If we are done we can break out, discard our\nbuffered strbuf, and send \"done\" to begin the pack stream. If not we\nkeep running the loop.\n\nIf its writeable, attempt to send out the current strbuf, trimming off\nthe prefix of whatever was successfully written.\n\nfetch-pack can put its own cap on the amount of data its willing to\nstore in that strbuf, Maybe its 100,000 have lines, which is about 5\nMiB of data. If the strbuf is exceeding that we stop queuing and just\npump the select() loop.\n\nWhen sending \"done\" there may still be \"NAK\" or \"ACK\" lines coming\nback from the peer due to the deeper buffering. The client would have\nto consume those off before it finds the PACK header. We can handle\nthat by keeping track of how many flush-pkts were written but have not\nyet been NAKed by the peer. When breaking out to send \"done\" we read\nuntil the remaining number of NAK lines were consumed.\n\n\nThe nice part is we can do an improvement strictly in fetch-pack.c.\nupload-pack is not affected and wouldn't care. So we may be able to\nexperiment with clients, and users who want more aggressive\nnegotiation could upgrade.\n"},{"id":"269899","messageId":"55F641C5.2020007@alum.mit.edu","threadId":"40334","inReplyTo":"CAJo=hJstD8c2RPUAj2OznFSCuyJsKFmvymsQMHOPhGdaqPgyvg@mail.gmail.com","subject":"Re: Bloom filters for have/want negotiation","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-09-14T03:40:53Z","receivedAt":"2015-09-14T03:40:53Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 09/12/2015 07:16 AM, Shawn Pearce wrote:\n> On Fri, Sep 11, 2015 at 2:13 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>> I have been thinking about Wilhelm Bierbaum's talk at the last GitMerge\n>> conference [1] in which he describes a scheme for using Bloom filters to\n>> make the initial reference advertisement less expensive.\n> ...\n>> But it got me thinking about how the client could use a Bloom filter in\n>> a later stage of the negotiation, when telling the server what objects\n>> it already has, while preserving 100% reliability.\n> ...\n>> I don't have a gut feeling about the cost of this phase of the\n>> negotiation, so I don't know whether this would be a net savings, let\n>> alone one that is worth the added complexity. But I wanted to document\n>> the idea in case somebody thinks it has promise. (I have no plans to\n>> pursue it.)\n> \n> Maybe I can help... it just so happens that I have Git servers at\n> $DAY_JOB instrumented in the smart HTTP negotiate code. They do \"many\"\n> fetch requests. :)\n> [...]\n> \n> Ergo, if this is all working correctly on smart HTTP, clients can\n> fetch from a server they already \"know\" with decent efficiency, and\n> smaller than your 2 KiB Bloom filter estimate for git.git at 1% error\n> rate.\n\nThanks for the awesome data, Shawn. Your data do indeed seem to prove\nthat there would be no benefit to using Bloom filters in this part of\nthe negotiation.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"}]}