엘라스틱서치 스터디를 하던 중 HyperLogLog에 대한 이야기가 나왔다.
HyperLogLog에 대해 이야기하기 전에 일단 왜 HyperLogLog가 나왔는지에 대해서부터 알아야 한다.
엘라스틱서치에서는 집계 쿼리를 이용하여 통계 데이터를 만든다. 이러한 통계 데이터를 만드는 종류 중에 필드의 유니크한 수를 만들기 위한 데이터를 만들 수가 있다. 그런데, 내가 써놓고서도 필드의 유니크한 수가 뭔지 모르겠다. 필드의 유니크한 수....??? 필드의 유니크한 수..
필드의 유니크한 수는 바로 중복된 값을 제외한 데이터의 수를 말한다.
예를 들어, 필드에 월/화/수/목/금/월/화/수/목/금/토/일 데이터가 있다면 여기서 중복된 값을 제외하면 월/화/수/목/금/토/일이 나오게 된다. 원래 12개의 필드가 중복 값을 제외하고 7이 되는 것이다.
즉 필드의 유니크한 수는 7이 되는 것이다.
자 이제 필드의 유니크한 수를 알았다. 그러면 필드의 유니크한 수를 만들기 위해서는 엘라스틱 서치에서는 어떤 집계 함수를 써야 할까?
위의 그림과 같이 cardinality 집계를 사용하며 precision-threshold에 값을 넣어 요청을 하면 된다.
precision_threshold는 정확도 값이다.
그런데 precision_threshold는 무엇일까?
우리는 precision_threshold를 알기 전에 우리의 주인공 HyperLogLog를 우선 알아야 한다.
일단 이거 하나만 알고 있어도 충분히 이해를 할 수 있다 cardinality 집계는 HyperLogLog 알고리즘을 사용한다. 그래서 중복된 키 값을 제외한 유니크한 키 값을 얻을 수가 있다.
이 HyperLogLog라는 녀석의 변천사는 LogLog -> SupperLogLog -> HyperLogLog로 점점 진화한 아주 무서운 주인공이다.
마치 포켓몬스터에서 파이리가 리자드가 되고 리자몽이 되는 과정을 볼 수가 있다.
포켓몬스터를 적으니깐 빵 먹고 싶어서 포켓몬빵 먹었더니 원하던 리자몽은 안 나오고 깨비참이 나왔다.😭 그래도 고오스 빵은 맛있었으니 다행
진화 과정이 매우 중요하다. 하지만 요번에는 리자몽만 설명하고 싶어졌다.
즉 요번 글에서는 HyperLogLog만 설명하려고 한다.
HyperLogLog는 매우 적은 메모리로 집합의 원소 개수를 모을 수 있는 알고리즘이다. 그런데 매우 적은 메모리로 집합의 원소 개수를 모을 수 있는 알고리즘이라고 설명을 한다면, 대부분 이해를 못 할 것이다.
집합의 원소 개수는 RDB에서 distinct로도 충분히 구할 수 있는데요?라는 말이 나올 수도 있고, 자바 Stream distinct로도 구할 수가 있어요?라고 태클이 들어올게 뻔하다.
여기서 이제 추가적으로 이러한 말이 들어가야 한다.
HyperLogLog는 매우 적은 메모리로 너무 많은 데이터가 들어가 있는 집합의 원소 개수를 정확하지 않지만 최대한 정확한 원소 개수를 모을 수 있는 알고리즘이다.라고 말이다.
너무 많은 데이터, 정확하지 않지만 최대한 정확함이 키워드이다.
즉, HyperLogLog는 너무 많은 데이터를 가진 집합의 원소에 대해 값을 일일이 정확히 개수를 구하고자 하면 많은 메모리가 들기 때문에 해당 알고리즘을 통하여 최대한 정확한 값을 얻어낼 정도로만 메모리를 사용하는 알고리즘이다.
12340230520352350235개의 데이터가 있다면 이러한 개수를 구하는 것은 너무 많은 메모리가 들고, 많은 시간이 들어 HyperLogLog를 사용하여 120000000000000개 있어!라고 가장 가까운 근삿값을 구한다. 더 정확하게 구하고 싶다면 HyperLogLog에게 더 많은 메모리를 주면 된다고 한다.
매우 멋지지 않은가!
자세한 건 우리의 네이버 형님이 알려줄 것입니다. GO GO!
확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog
HyperLogLog에 대해서 세줄로 정리하자면
1. HyperLogLog는 적은 메모리로 정확하지 않지만 최대한 정확한 원소 개수를 모을 수 있는 알고리즘이다.
2. HyperLogLog는 elasticsearch의 cadinality 집계에서 사용하고 있다. 추가로 Redis에서도 사용하고 있다.
3. 최대한 정확한 값을 얻어내기 위해서는 더 많은 데이터를 주면 된다.
자 이제 hyperloglog를 알아봤으니, 이제 precision_threshold를 알아봐야 한다.
precision_threshold는 결과에 대한 정확도를 더 높이기 위하여 사용한다. 일단은, 정확도를 높이기 위해서는 precision_threshold에 대한 값을 카디널리티보다 높게 잡으면 된다.
참고로 elasitcsearch는 precision_threshold에 대한 값이 default 3000이며 최대가 40000이라고 한다. 즉, 정확도 값을 40000 이상으로 넣으면 아무리 큰 값을 넣어도 정확해지지가 않는다.
하지만 precision_threshold가 카디널리티보다 작다면, 유사한 근사치를 알려준다.
예를 들어 카디널리티가 7인 필드에 대해서 precision_threshold를 5를 넣으면 카디널리티가 더 크기 때문에 그에 유사한 근사치인 8을 얻을 수도 있다.
엘라스틱서치에서는 거의 95퍼 이내의 근삿값을 준다고한다.
7인 필드에 대해서 정확하게 만들려면 precision_threshold를 7보다 더 크게 잡으면 된다. 하지만 이러한 precision_threshold도 너무 높게 잡아버리면 안 된다. 왜냐하면 precision_threshold 하나당 8바이트에 대한 메모리를 잡아먹기 때문이다.
precision_htreshold에 대해 3줄로 정리하자면,
1. precision_threshold는 정확도를 높이기 위하여 사용한다.
2. precision_threshold가 카디널리티보다 작다면, 유사한 근사치를 알려준다.
3. precision_threshold가 카디널리티보다 높으면 높은 정확도를 가지나, 하나당 8바이트에 대한 메모리를 잡아먹기 때문에 주의해서 써야 한다.
precision_threshold, HyperLogLog를 정리함으로써 이제 엘라스틱서치의 cardinality도 3줄로 설명이 가능하다.
1. cardinality는 필드에 대한 유니크한 값을 구하는 엘라스틱서치 집계이다.
2. 하지만 유니크한 값들에 대해 정확한 값을 구하기에는 너무 많은 메모리를 써야 하기 때문에 엘라스틱 서치는 HyperLogLog 알고리즘을 사용한다.
3. 이러한 HyperLogLog에서 써야 할 메모리를 할당해주는 것이 바로 precision_threshold이다.
자 이제 모든 개념을 알아냈다. 다시 질문으로 돌아가자. ☺️
여기서 미리 말하겠다. 나의 질문에 대해서 답해주신 분이 너무나도 고맙다고 생각합니다. 그래서 저도 이 질문을 가지고 좀 더 깊게 생각할 수 있을 것 같아서 요번 글을 쓰게 되는 거니까 말이죠!
여기서 나온 질문에서 내가 궁금했던 점은 바로 "HLL(HyperLogLog) 알고리즘에 사용되는 레지스터 수가 정확도 값(precision_threshold)과 연관이 있지 않을까 하는 생각입니다."였다.
정말로 레지스터 수가 정확도 값(precision_threshold)과 연관이 있을까!? 가 나의 궁금증이다.🤔
나는 관련 있다고 생각한다. 왜냐하면 결국에는 HyperLogLog에서 써야 할 메모리를 주는 것은 precision_threshold이기 때문이다.
그렇지만, HyperLogLog는 레지스터를 만들기 위하여 비트로 따진다. 하지만 precision_threshold는 바이트 단위이다.
왜 이렇게 큰 값을 precision_threshold에게 주는 것일까라고 생각을 해봤는데, 결국에는 엘라스틱서치는 lucene으로 돌아가고 있고, lucene는 세그먼트 단위로 항상 돌아가고 있다. 하나의 샤드만 있다면 하나의 세그먼트만 돌아가겠지만, 여러 샤드가 있다면 다수의 세그먼트가 hyperLogLog알고리즘을 돌릴 것이다.
여러 샤드가 있다는 것에 가정하에 하나의 세그먼트를 위한 바이트 단위인 값을 주는 게 아닌 여러 세그먼트들에게 메모리 값을 주어 근삿값을 구하도록 만들도록 하는 게 아닌가 한다.
여기서 여러 세그먼트들에게 메모리 값을 주어 근사값을 구하도록 만들도록 하는게 아닌가?라는 새로운 의문이 나왔지만, 아직까지 관련 아티클을 찾지 못했다.
더 찾아봐야 될 것 같아서 일단 열린 결말로 이 포스팅을 끝내려고 한다.
확실하게 답할 수 있는 시기가 있지 않을까..? 고수분들이 나와서 알려줬으면 좋겠다!
'ELK > ELK 개발부터 운영까지' 카테고리의 다른 글
| Logstash config directory 위치(brew 설치 시) (0) | 2022.03.22 |
|---|---|
| 로그스태시(LogStash) (0) | 2022.03.21 |
| 엘라스틱서치(elasticsearch) 집계 (0) | 2022.03.09 |
| 엘라스틱서치(elasticSearch) 검색 - 2부 (0) | 2022.03.02 |
| 엘라스틱서치(elasticSearch) 검색 - 1부 (0) | 2022.03.01 |