The Insert method in cuckoofilter behave unexpected when the filter is full. In general, insert method should return true when it can store the element, and return false when it can't store. But when the cuckoo filter is full, insert method will store the element, and withdraw a random one inside filter while returning false.
I make a simple test about this:
func TestExhausted(t *testing.T){
ckflter := seiflotfy_filter.NewFilter(10000)
var cached [maxNumForBenchmark]bool
elementList := make([]int,0)
var lastElement int
isFinish := false
for !isFinish{
randNum := rand.Intn(maxNumForBenchmark)
for cached[randNum]{
randNum = rand.Intn(maxNumForBenchmark)
}
finish := ckflter.Insert([]byte(strconv.Itoa(randNum)))
if !finish{
t.Logf("Last element is %v",randNum)
lastElement = randNum
isFinish = true
break
}else{
cached[randNum] = true
elementList = append(elementList,randNum)
}
}
for i:=0;i<len(elementList);i++{
isInside := ckflter.Lookup([]byte(strconv.Itoa(elementList[i])))
if !isInside{
t.Errorf("%v should inside but not",elementList[i])
}
}
isInside := ckflter.Lookup([]byte(strconv.Itoa(lastElement)))
t.Logf("%v should not inside but got %v",lastElement,isInside)
}
The output of code above is
=== RUN TestExhausted
--- FAIL: TestExhausted (0.00s)
standardCuckooFilter_test.go:308: Last element is 1776
standardCuckooFilter_test.go:321: 16055 should inside but not
standardCuckooFilter_test.go:325: 1776 should not inside but got true
FAIL
Process finished with exit code 1
My solution of this is adding a backup array for all buckets in cuckoo filter, and recover when insertion failure. But this costs a lot when insertion doesn't fail.
The
Insertmethod in cuckoofilter behave unexpected when the filter is full. In general, insert method should return true when it can store the element, and return false when it can't store. But when the cuckoo filter is full, insert method will store the element, and withdraw a random one inside filter while returning false.I make a simple test about this:
The output of code above is
My solution of this is adding a backup array for all buckets in cuckoo filter, and recover when insertion failure. But this costs a lot when insertion doesn't fail.