Inflearn コミュニティ Q&A

@Slf4j
@SpringBootTest
class SplitBloomFilterRedisHandlerTest extends RedisTestContainerSupport {

    @Autowired
    SplitBloomFilterRedisHandler splitBloomFilterRedisHandler;

    @Test
    void mightContain() {
        SplitBloomFilter splitBloomFilter = SplitBloomFilter.create("testId", 1000, 0.01);

        List<String> values = IntStream.range(0, 1000).mapToObj(idx -> "value" + idx).toList();
        for (String value : values) {
            splitBloomFilterRedisHandler.add(splitBloomFilter, value);
        }

        for (String value : values) {
            boolean result = splitBloomFilterRedisHandler.mightContain(splitBloomFilter, value);
            assertThat(result).isTrue();
        }

        for (int i = 0; i < 1000; i++) {
            String value = "notAddedValue" + i;
            boolean result = splitBloomFilterRedisHandler.mightContain(splitBloomFilter, value);
            if (result) {
                log.info("value={}", value);
            }
        }
    }
}

위 코드는 SplitBloomFilterRedisHandlerTest 인데요.

강의 중 코드입니다

1000 크기에 0.01 오차율의 Bloom Filter 를 만들고

1000개의 데이터를 넣고 False Positive 까지 검증해보는 코드인데요.

질문입니다
Split 전략을 배우기 전에
순수한 Bloom Filter 구현 강의에서도 위와 동일한 테스트 코드가 있는데요

이 때, 순수한 Bloom Filter 의 한계로써
생성한 Bloom Filter 크기를 초과하여 데이터를 넣으면 비트 1이 많아져 오차율이 증가하고
그로 인해 False Positive 데이터가 많이 조회되는 현상을 살펴보거든요.

그리고 그 해결책으로
처음부터 큰 Bloom Filter 를 만드는 것 이외에
Split / Sharding / Sub Filter 전략이라고 말씀하시는데요

근데 위 Split 전략의 테스트 코드에서

BloomFilter 크기는 1000으로 만들고

데이터를 훨씬 초과하여 2000개 만들어 넣어보면
순수한 Bloom Filter 때처럼 False Positive 데이터가 많이 조회됩니다.

저는 PC 가 느려서 False Positive 를 1000번으로 조회하였고
오차율 (0.01) 에 의하면 약 10개의 False Positive 가 나와야 하는데

데이터 1000개를 저장했을 때는 오차율에 맞게 8개로 떨어지는데
데이터 2000개를 저장했을 때는 오차율을 훨씬 넘어갑니다

제가 코드를 잘못 따라 친건지.. Split 도 원래 그런건지..
제 질문 의미가 전달될지는 모르겠지만.. 명확하게 개념 정리가 되지 않아 질문드립니다