TopN 구하기 (3)

지난 글에 이어서 서비스에서 TopN을 구하는 다른 방식을 이야기 해보고자 한다.

 

지난 글에서 생각했던 범위를 확장하 초당 10만 건의 요청이 오는데 TopN을 사용자에게 보여 줘야 하는 요구사항이 있다면 어떻게 해결해야 할까?

 

Redis의 한계

우선 지난 글에서 사용했던 Redis의 자료구조를 활용하는 부분은 요구사항을 맞추는데 어려워 보인다.

 

가장 먼저 단일 Redis가 처리할 수 있는 연산이 초당 8만건 정도라고 하는데 Sorted Set은 하나의 키를 사용해서 연산을 진행 하는 것 이므로 클러스터 모드를 통한 접근은 의미가 없으며, write 성능이 요구사항을 따라가지 못한다.

 

또한 동기화를 위한 집계 성능 또한 초당 10만 건을 처리하는 것은 무리가 있다.

 

따라서 기존과는 다른 접근이 필요하다.

 

 

데이터 분류

데이터 관점으로 접근했을 때 TopN을 구하는 데이터의 특성은 두 가지로 분류 할 수 있어보인다.

 

1. 정확하게 값이 일치해야 하는 데이터.

2. 정확하게 값이 일치하지 않아도 되는 데이터

 

 

정확하게 일치해야 하는 데이터

만약, 이전 데이터를 포함하여 실시간성으로 TopN을 집계해야 한다면, 람다 아키텍처를 주로 사용하는 것 같다.

 

간략히 요약하면, 실시간으로 집계하는 부분과 미리 집계하는 부분(대용량 집계)을 나눠 둘을 합쳐서 보여주는 방식이다.

 

하지만, 서비스에서 실시간성으로 TopN을 집계하는 것은 이전 데이터까지 포함하지는 않고 특정 시간동안의 TopN을 계산하는 방식이 대부분이다.

 

특정 시간동안의 집계는 Filnk 같은 스트림 프로세싱 어플리케이션과 kafka같은 메세지 큐를 활용해서 처리할 수 있어보인다.

 

정확하게 일치하지 않아도 되는 경우

실시간 검색어 랭킹과 같은 데이터에서 해당 검색어가 몇 번 입력 됐는지를 사용자들이 정확하게 알 필요는 없고, 집계에서도 오차 없이 정확하게 집계 할 필요가 없다.

 

여기서 활용할 수 있는 것이 '확률적 자료구조'이다.

  

확률적 자료구조

특정 시간동안  TopN을 집계한다고 가정했을 때 어떻게 할 수 있을까?

 

단순하게 생각하면 Map과 같은 자료구조를 통해서 들어오는 데이터들의 수량을 계산하고 추가로 Heap 자료구조를 통해서 상위 N개만 남기는 방식을 생각할 수 있을 것 같다.

 

간단하게 처리 한 것 처럼 보이지만, 데이터가 많은 경우 즉 Key에 해당하는 데이터가 많을 경우 메모리를 많이 쓰는 문제가 있다.

 

단순하게 생각해도 초당 100만건의 데이터가 들어온다고 하면, 편의상 저장하는 Entry가 1KB라고 하고 모두 Unique 하다고 가정하면 초당 125MB의 메모리가 늘어난다.

 

이는 메모리를 많이 사용하며, 메모리 사용량 측면에서도 불투명한 문제가 있다. 즉 어플리케이션이 언제 OOM으로 crash 될 지 모르며 메모리에 저장하는 것은 결국 어플리케이션이 다운 됐을 때 모든 데이터가 유실 된다는 것을 의미한다.

 

이를 해결하기 위해 메모리 사용량을 크게 줄여주는 '확률적 자료구조'가 사용된다.

 

물론, 컴퓨터 세계에서는 트레이드 오프가 있듯 집계에 오차가 존재 한다.

이 글에서는 간단하게 다루며, 궁금하다면 해당 링크를 통해 자세한 내용을 확인할 수 있다.

 

 

 

간략하게 특정 입력 값(집계 할 대상)을 여러 해시 함수를 통해 변환 후 변환 된 값에 해당하는 인덱스를 입력 값 만큼 증가시킨다.

 

각각의 해시 함수들은 다른 값을 연산 했을 때 해시 충돌이 일어날 수 있기 때문에 해시 함수의 결과중 가장 낮은 값을 찾아서 응답하면 해당 입력 값의 집계 연산 값의 근사 값을 추정할 수 있다.

 

이 부분에 있어서는 해시 함수 5개를 사용하고 위의 index의 갯수를 늘려주면 99.32%까지 근접하게 측정할 수 있다고 한다.

 

TopN 부분은 추가로 Heap 자료구조를 사용하여 Count-Min Sketch를 통해 갱신 되는 값을 넣어주고 N개만큼만 유지해주면 된다.

 

즉 메모리 사용 부분은 해시 함수 5개를 사용하고 index의 갯수를 16000개 정도 사용을 한다면 1MB도 사용을 안 하는 것을 확인 할 수 있으며 이는 위에서 문제점으로 확인 한 안정성 측면에서 안정적 이라고 할 수 있다.

 

대량의 데이터이기 때문에 안정성 측면에서 요청을 메세지 큐를 통해서 publish 하고 consume 해서 aggregate하는 비동기 통신 방식이 적절해 보인다. (생산자가 너무 빨리 보낸다면 API를 통한 HTTP 통신 방식에서는 안정성이 떨어짐)

 

정리

대용량의 트래픽이 발생하는 상황에서 TopN을 구해야 하는 요건이 있고, 데이터의 특성상 정확하게 집계를 하지 않아도 되는 데이터라면 비용적인 측면에서 '확률적 자료구조'를 고려해 보는 것도 좋다.

 

 

참고

• https://d2.naver.com/helloworld/799782
• https://stackoverflow.com/a/67960493