Estimating the number of elements in a set (w. hyperloglog)

What is Hyperloglog?

Hyperloglog 란 ?

https://d2.naver.com/helloworld/711301

 

 

Finding approximate number in redis using hyperloglog

Redis 에서 Hyperloglog 를 사용하여 count 에 대한 근사치 구하기

 

방문자 수를 카운팅 하는 예제

import com.jongyun.redission.config.BaseTest
import java.util.stream.LongStream
import kotlin.streams.toList
import org.junit.jupiter.api.Test
import org.redisson.client.codec.LongCodec
import reactor.core.publisher.Flux
import reactor.test.StepVerifier

class HyperLogLogTest : BaseTest() {

    @Test
    fun count() {
        val counter = this.client.getHyperLogLog<Long>("user:visit", LongCodec.INSTANCE)
        val longList = LongStream.rangeClosed(1, 25000)
            .boxed()
            .toList()

        val longList2 = LongStream.rangeClosed(25001, 50000)
            .boxed()
            .toList()

        val longList3 = LongStream.rangeClosed(1, 75000)
            .boxed()
            .toList()

        val longList4 = LongStream.rangeClosed(50000, 100_000)
            .boxed()
            .toList()

        val mono = Flux.just(longList, longList2, longList3, longList4)
            .flatMap { counter.addAll(it) }
            .then()

        StepVerifier.create(mono)
            .verifyComplete()

        counter
            .count()
            .doOnNext { println(it) }
            .subscribe()
    }
}

 

코드를 한줄 한줄 모두 이해할 필요는 없습니다.

Stream 을 통해 1 ~ 25000, 25001 ~ 50000, 1 ~ 75000 , 50000 ~ 100,000 의 값을 Redis hyperloglog 에 설정합니다.

Java HashSet 을 기준으로는 size 를 구했을때 10만 이라는 숫자가 나와야 합니다.

 

하지만 HyperLoglog 메모리 값을 고정하여 사용하는 만큼 오차범위를 허용합니다. 대략 (0.81)

 

대략 99562 라는 숫자를 볼 수 있습니다. 

 

예를 들어 어떤 검색 엔진의 하루 검색어 수를 계산할때 사용 할 수 있습니다.

메모리는 굉장히 적게 사용하면서 최대한의 오차범위를 허용할때 사용하면 좋을 것 같습니다.