Re: Bloom filters for have/want negotiation

[Michael Haggerty <mhagger@alum.mit.edu>]

On 09/12/2015 07:16 AM, Shawn Pearce wrote:
> On Fri, Sep 11, 2015 at 2:13 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
>> I have been thinking about Wilhelm Bierbaum's talk at the last GitMerge
>> conference [1] in which he describes a scheme for using Bloom filters to
>> make the initial reference advertisement less expensive.
> ...
>> But it got me thinking about how the client could use a Bloom filter in
>> a later stage of the negotiation, when telling the server what objects
>> it already has, while preserving 100% reliability.
> ...
>> I don't have a gut feeling about the cost of this phase of the
>> negotiation, so I don't know whether this would be a net savings, let
>> alone one that is worth the added complexity. But I wanted to document
>> the idea in case somebody thinks it has promise. (I have no plans to
>> pursue it.)
> 
> Maybe I can help... it just so happens that I have Git servers at
> $DAY_JOB instrumented in the smart HTTP negotiate code. They do "many"
> fetch requests. :)
> [...]
> 
> Ergo, if this is all working correctly on smart HTTP, clients can
> fetch from a server they already "know" with decent efficiency, and
> smaller than your 2 KiB Bloom filter estimate for git.git at 1% error
> rate.

Thanks for the awesome data, Shawn. Your data do indeed seem to prove
that there would be no benefit to using Bloom filters in this part of
the negotiation.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu