public class DecayingHashSet
Double buffered hash set.
Since DecayingBloomFilter was instantiated 4 times for a total memory usage
of 8MB, it seemed like we could do a lot better, given these usage stats
on a class L router:
32 bytes, peak 10 entries in 1m
(320 peak entries seen on fast router)
4 bytes, peak 150 entries in 10s
(1600 peak entries seen on fast router)
8 bytes, peak 1K entries in 2m
(36K peak entries seen on fast router)
16 bytes, peak 15K entries in 10m
If the ArrayWrapper object in the HashSet is 50 bytes, and BloomSHA1(23, 11) is 1MB,
then for less than 20K entries this is smaller.
And this uses space proportional to traffic, so it doesn't penalize small routers
with a fixed 8MB.
So let's try it for the first 2 or 3, for now.
Also, DBF is synchronized, and uses SimpleTimer.
Here we use a read/write lock, with synchronization only
when switching double buffers, and we use SimpleTimer2.
Yes, we could stare at stats all day, and try to calculate an acceptable
false-positive rate for each of the above uses, then estimate the DBF size
required to meet that rate for a given usage. Or even start adjusting the
Bloom filter m and k values on a per-DBF basis. But it's a whole lot easier
to implement something with a zero false positive rate, and uses less memory
for almost all bandwidth classes.
This has a strictly zero false positive rate for <= 8 byte keys.
For larger keys, it is 1 / (2**64) ~= 5E-20, which is better than
DBF for any entry count greater than about 14K.
DBF has a zero false negative rate over the period
2 * durationMs. And a 100% false negative rate beyond that period.
This has the same properties.
This performs about twice as fast as DBF in the test below.