PrefixSet as an alternate to BloomFilter for safe-browsing.

PrefixSet as an alternate to BloomFilter for safe-browsing.

The safe-browsing prefix data is uniformly distributed across the
32-bit integer space.  When sorted, the average delta between items is
about 8,000, which can be encoded in a 16-bit integer.  PrefixSet
takes advantage of this to compress the prefixes into a structure
which is relatively efficient to query.

The current CL adds the new structure, but continues to use the bloom
filter to control things.  Histograms are logged to track differences
in results.

BUG=71832
TEST=none

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=74487

[Scott Hess - ex-Googler, 2011-02-03 01:43:33]

Awhile back I did some experimentation with different ways this could be stored.
 On Tuesday, for no apparent reason, I had an idea, this being the result.

For my current safe-browsing database, there are almost 650k unique prefixes. 
Under the bloom filter these require 1.93M of memory.  PrefixSet needs 1.27M and
has no false positives.  Timing in ContainsURL using TimeTicks indicates that
PrefixSet::Exists() takes about 3.5x as long as BloomFilter::Exists() when the
maximum run is set to 100 items.

[lzheng, 2011-02-05 01:03:42]

looks good. I haven't take a look at the test yet, I will take spend sometime on
that. I want to think more about the memory consumption model too.

In theory, bloom filter has the advantage of being fast and saving memory. If we
don't see the memory saving part, I wonder if our false positive rate bar is too
low because backends don't want to handle more load.

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
File chrome/browser/safe_browsing/prefix_set.cc (right):

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
chrome/browser/safe_browsing/prefix_set.cc:42: unsigned delta = sorted[i] -
prev_prefix;
unsigned int32?

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
File chrome/browser/safe_browsing/prefix_set.h (right):

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
chrome/browser/safe_browsing/prefix_set.h:66: // Top-level index of prefix to
offset in |deltas_|.  Each pair
You might want to give an example. It is a little bit hard to only rely on the
comments,

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
File chrome/browser/safe_browsing/safe_browsing_database.cc (right):

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
chrome/browser/safe_browsing/safe_browsing_database.cc:199: enum PrefixSetEvent
{
I found we've never record how many look ups we encountered. Should we do that?
Otherwise, we never know the actual false positive rate is encountered by bloom
filter.

[Scott Hess - ex-Googler, 2011-02-05 01:28:42]

On 2011/02/05 01:03:42, lzheng wrote:
> looks good. I haven't take a look at the test yet, I will take spend sometime
on
> that. I want to think more about the memory consumption model too.
> 
> In theory, bloom filter has the advantage of being fast and saving memory. If
we
> don't see the memory saving part, I wonder if our false positive rate bar is
too
> low because backends don't want to handle more load.

If you assume the rightness of
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html , then we have k
== 20 (hash keys) and m/n == 25 (m is total bits, n is prefix count), so our
false-positive rate is worse than 6.27e-06.  I say "worse than" because the
optimal k for our m/n is actually 17 (false positive rate 6.08e-06).

At m/n == 16, optimal k == 11, and the false-positive rate is .000459, 75x as
high (as 6.08E-06).  I believe that this would fall right through to our 204
requests (204 requests would be 75x higher if we set the bit ratio to 16).

I had a change to calculate the right k given the prefix count and the matrix
size, accounting for the size being capped, plus code to adjust the slow of
memory growth past a certain point, but it's not worthwhile if we can change the
implementation.  The advantage of that change is that it would improve the
false-positive rate slightly as we start restricting the bitmap size, but it
wouldn't improve it a ton, really.  Free improvement, though!

All in all, I don't think this is hugely surprising.  A more standard use of a
bloom filter would be to store a dictionary before hitting disk, where you'd be
saving the storage overhead of a bunch of variably-sized text strings.  I think
the win there is pretty clear.  Why I was looking at this awhile back was
because the current bloom filter is only a 22% space savings versus just storing
the 32-bit prefixes in an array.  That's hardly worth the complexity.  Saving
~50% - epsilon is more reasonable (epsilon is around 2% with run-length of 100).

-scott

[Scott Hess - ex-Googler, 2011-02-07 19:20:23]

OK, I'm done changing things.

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
File chrome/browser/safe_browsing/prefix_set.cc (right):

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
chrome/browser/safe_browsing/prefix_set.cc:42: unsigned delta = sorted[i] -
prev_prefix;
On 2011/02/05 01:03:42, lzheng wrote:
> unsigned int32?

Why?  The uint16 in the deltas is needed because that's the entire point of the
structure.  But this value can be 32-bit or 64-bit depending on platform with no
problem.  uint32 suffices because SBPrefix is an int32, but that's not hugely
relevant.

[Unless I'm missing something, of course!]

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
File chrome/browser/safe_browsing/prefix_set.h (right):

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
chrome/browser/safe_browsing/prefix_set.h:66: // Top-level index of prefix to
offset in |deltas_|.  Each pair
On 2011/02/05 01:03:42, lzheng wrote:
> You might want to give an example. It is a little bit hard to only rely on the
> comments, 

Adding a comment in the file header.

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
File chrome/browser/safe_browsing/safe_browsing_database.cc (right):

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
chrome/browser/safe_browsing/safe_browsing_database.cc:199: enum PrefixSetEvent
{
On 2011/02/05 01:03:42, lzheng wrote:
> I found we've never record how many look ups we encountered. Should we do
that?
> Otherwise, we never know the actual false positive rate is encountered by
bloom
> filter. 

It should be a couple orders of magnitude higher than the other values, so it
might blow out the metrics.

This specific histogram is to make sure that PrefixSet matches the results of
BloomFilter as expected.  It should go away when the BloomFilter goes away.  So
we could add another histogram, but probably somewhere else.

I _think_ SB2.FilterCheck might be sufficient already.  It histograms
time-to-check, but the dashboard also shows number of records.  For 2/2/11,
SB2.FilterCheck shows 3700x as many hits as SB2.GetHash200+SB2.GetHash204, which
seems like a reasonable number.

[lzheng, 2011-02-08 01:18:11]

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
File chrome/browser/safe_browsing/prefix_set.cc (right):

http://codereview.chromium.org/6286072/diff/3001/chrome/browser/safe_browsing...
chrome/browser/safe_browsing/prefix_set.cc:42: unsigned delta = sorted[i] -
prev_prefix;
I was thinking to use uint32 because prefixes are 4bytes, but it is true that
64bits has no problem. 

On 2011/02/07 19:20:23, shess wrote:
> On 2011/02/05 01:03:42, lzheng wrote:
> > unsigned int32?
> 
> Why?  The uint16 in the deltas is needed because that's the entire point of
the
> structure.  But this value can be 32-bit or 64-bit depending on platform with
no
> problem.  uint32 suffices because SBPrefix is an int32, but that's not hugely
> relevant.
> 
> [Unless I'm missing something, of course!]

[lzheng1, 2011-02-08 02:12:47]

Good analysis. Indeed, we should choose the best k based on m/n ratio. If we
stick with a high k when m/n is small, we fill more bits that will cause
more false positives.

I wonder if we should do an analysis to see where the time is spent for the
prefixset solution. Isn't it suppose to be a binary search for the
upper_bound and then another short loop for the delta? I assume this should
not be too much slower than the bloomfilter lookup.

Lei

On Fri, Feb 4, 2011 at 5:28 PM, <shess@chromium.org> wrote:

> On 2011/02/05 01:03:42, lzheng wrote:
>
>> looks good. I haven't take a look at the test yet, I will take spend
>> sometime
>>
> on
>
>> that. I want to think more about the memory consumption model too.
>>
>
>  In theory, bloom filter has the advantage of being fast and saving memory.
>> If
>>
> we
>
>> don't see the memory saving part, I wonder if our false positive rate bar
>> is
>>
> too
>
>> low because backends don't want to handle more load.
>>
>
> If you assume the rightness of
> http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html , then we
> have k
> == 20 (hash keys) and m/n == 25 (m is total bits, n is prefix count), so
> our
> false-positive rate is worse than 6.27e-06.  I say "worse than" because the
> optimal k for our m/n is actually 17 (false positive rate 6.08e-06).
>
> At m/n == 16, optimal k == 11, and the false-positive rate is .000459, 75x
> as
> high (as 6.08E-06).  I believe that this would fall right through to our
> 204
> requests (204 requests would be 75x higher if we set the bit ratio to 16).
>
> I had a change to calculate the right k given the prefix count and the
> matrix
> size, accounting for the size being capped, plus code to adjust the slow of
> memory growth past a certain point, but it's not worthwhile if we can
> change the
> implementation.  The advantage of that change is that it would improve the
> false-positive rate slightly as we start restricting the bitmap size, but
> it
> wouldn't improve it a ton, really.  Free improvement, though!
>
> All in all, I don't think this is hugely surprising.  A more standard use
> of a
> bloom filter would be to store a dictionary before hitting disk, where
> you'd be
> saving the storage overhead of a bunch of variably-sized text strings.  I
> think
> the win there is pretty clear.  Why I was looking at this awhile back was
> because the current bloom filter is only a 22% space savings versus just
> storing
> the 32-bit prefixes in an array.  That's hardly worth the complexity.
>  Saving
> ~50% - epsilon is more reasonable (epsilon is around 2% with run-length of
> 100).
>
> -scott
>
>
>
> http://codereview.chromium.org/6286072/
>

[Scott Hess - ex-Googler, 2011-02-08 05:10:30]

Originally, the speedup from using the BloomFilter was that you didn't
have to hit the disk.  Nowadays it's that you don't have to hit the
server.  The PrefixSet code is slower than the BloomFilter code, but
not slow, if you see what I mean.

AFAICT, the linear search accumulating the deltas is what drives most
of the time for the PrefixSet.  Making the maximum run size small
brings things more in line, but at the cost of increasing the memory
overhead.  I think there might be a little room for improvement by
scanning for all prefixes in a batch - if the number of items to match
is high enough relative to index_.size(), a linear scan might be
faster than a bunch of binary searches.

It's possible that there's something subtle about the PrefixSet which
makes it slowed.  My intuition was that BloomFilter's key generation
would all happen close to the CPU and OOO executed around the "is this
bit set" checks, and that those random accesses would cap performance.
 PrefixSet should be better because it would tend to process multiple
sequential cache lines.  BUT, it may be that the BloomFilter code is
simple enough that it can do OOO scheduling across multiple probes,
and thus get a bunch of memory accesses in-flight at once, whereas
PrefixSet is stuck with just the one at a time.

All that said, the current PrefixSet code is pretty simple.  I'm not
sure it's worth complexifying.

-scott


On Mon, Feb 7, 2011 at 5:45 PM, Lei Zheng <lzheng@google.com> wrote:
> Good analysis. Indeed, we should choose the best k based on m/n ratio. If we
> stick with a high k when m/n is small, we fill more bits that will cause
> more false positives.
> I wonder if we should do an analysis to see where the time is spent for the
> prefixset solution. Isn't it suppose to be a binary search for the
> upper_bound and then another short loop for the delta? I assume this should
> not be too much slower than the bloomfilter lookup.
> Lei
>
> On Fri, Feb 4, 2011 at 5:28 PM, <shess@chromium.org> wrote:
>>
>> On 2011/02/05 01:03:42, lzheng wrote:
>>>
>>> looks good. I haven't take a look at the test yet, I will take spend
>>> sometime
>>
>> on
>>>
>>> that. I want to think more about the memory consumption model too.
>>
>>> In theory, bloom filter has the advantage of being fast and saving
>>> memory. If
>>
>> we
>>>
>>> don't see the memory saving part, I wonder if our false positive rate bar
>>> is
>>
>> too
>>>
>>> low because backends don't want to handle more load.
>>
>> If you assume the rightness of
>> http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html , then we
>> have k
>> == 20 (hash keys) and m/n == 25 (m is total bits, n is prefix count), so
>> our
>> false-positive rate is worse than 6.27e-06.  I say "worse than" because
>> the
>> optimal k for our m/n is actually 17 (false positive rate 6.08e-06).
>>
>> At m/n == 16, optimal k == 11, and the false-positive rate is .000459, 75x
>> as
>> high (as 6.08E-06).  I believe that this would fall right through to our
>> 204
>> requests (204 requests would be 75x higher if we set the bit ratio to 16).
>>
>> I had a change to calculate the right k given the prefix count and the
>> matrix
>> size, accounting for the size being capped, plus code to adjust the slow
>> of
>> memory growth past a certain point, but it's not worthwhile if we can
>> change the
>> implementation.  The advantage of that change is that it would improve the
>> false-positive rate slightly as we start restricting the bitmap size, but
>> it
>> wouldn't improve it a ton, really.  Free improvement, though!
>>
>> All in all, I don't think this is hugely surprising.  A more standard use
>> of a
>> bloom filter would be to store a dictionary before hitting disk, where
>> you'd be
>> saving the storage overhead of a bunch of variably-sized text strings.  I
>> think
>> the win there is pretty clear.  Why I was looking at this awhile back was
>> because the current bloom filter is only a 22% space savings versus just
>> storing
>> the 32-bit prefixes in an array.  That's hardly worth the complexity.
>>  Saving
>> ~50% - epsilon is more reasonable (epsilon is around 2% with run-length of
>> 100).
>>
>> -scott
>>
>>
>> http://codereview.chromium.org/6286072/
>
>

[lzheng, 2011-02-08 18:19:56]

LGTM.