실시간 대용량 데이터에서 사용되는 알고리즘(Reservoir Sampling, HLL, CMS,Bloom Filter)들에 대해 알아보자

스트리밍 시스템에서 모은 많은 데이터들은 시스템 안에서 효율적으로 분석되고 집계되어야합니다.

아무래도 실시간이고 방대한 데이터를 대상으로 하는 만큼 '확률적인 알고리즘'이 많이 사용됩니다.

또 대량의 데이터에 대해서 랜덤 추출, 카더널리티, 빈도, 이전 유입 여부를 확인하는 4개의 알고리즘들에 알아보겠습니다.

무작위 샘플 데이터 추출 - 레저부아 샘플링(Reservior Sampling)

스트림 데이터에서 무작위로 샘플 데이터 추출이 필요할 때가 있습니다.

만약 시스템에서 분당 1,000만 건의 로그가 들어온다고 했을 때, 우리는 모든 로그를 다 메모리에 저장해서 빠르게 분석할수는 없습니다.

이런 상황에서는 랜덤 표본 데이터를 추출해서 원하는 비즈니스 결과를 만들 수 있습니다.

 

레저부아 샘플링 알고리즘은 스트림 데이터 중 무작위 k개를 동일한 확률로 선택하는 알고리즘 입니다.

즉 전체 데이터를 모두 확인하지 않아도 공평하게 샘플을 확인 할 수 있습니다.

 

핵심 개념은 이렇습니다.

k개의 데이터를 저장 할 수 있는 저장소 '레저부아'를 가지고 있고, '레저부아'가 가득 찬 상태에서 새로운 데이터가 도착하면 그 데이터를 '풀' 안에 데이터로서 추가, 즉 교채할 것인지, 추가하지 않을 것인지를 결정합니다.

 

n번째 데이터가 들어오면 "k/n" 확률로 레저부아 풀에 저장 여부를 결정합니다.

k는 풀의 크기, n의 n번째로 들어온 데이터입니다.

위 그림과 같은 상황이라면 15/16확률입니다.

이 확률을 확인하기 위해 0과 1사이 난수를 생성합니다. 만약 n/k 미만이라면 저장소에 저장하고, 저장소의 데이터 중 하나를 랜덤으로 결정해 내보내고, n번째 데이터를 풀에 넣습니다.

 

레저부아 샘플링을 사용하면 어떤 데이터든 저장소에서 추출될 확률이 1/n이 되는데,

이에 대한 수학적 증명은 이렇습니다.

• $k$: Reservoir 크기
• $n$: 전체 데이터 수
• $A_1, A_2, \dots, A_n$: 입력 데이터
• $P_j$: $A_j$가 최종 Reservoir에 남을 확률

j번째 데이터  $A_j$가 저장소에 저장될 확률은 아래와 같습니다.

    $$
    P_{\text{select}}(j) =
    \begin{cases}
    1 & \text{if } j \le k \\
    \frac{k}{j} & \text{if } j > k
    \end{cases}
    $$

​

이후 데이터는 계속해서 저장소에 들어오게되는데,

$A_j$ 이후에 들어오는 모든 데이터 $j+1, j+2, \dots, n$번째 데이터에 들어와도 $A_j$가 유지될 확률을 구합니다.

 

$t > j$ 라고 했을 때,

$t$번째 데이터가 들어오면 $\quad \frac{k}{t}$ 확률로 레저부아 저장소 중 하나의 데이터를 교체하고 그 중 $\quad \frac{1}{k}$ 확률로 $A_j$가 선택합니다.

따라서 $A_j$가 $t$에서 교체될 확률은 아래와 같습니다.

$$ \frac{k}{t} \cdot \frac{1}{k} = \frac{1}{t} $$

 

즉 $A_j$가 에서 살아남을 확률은 아래와 같습니다.
$$
1 - \frac{1}{t}
$$

 

결국 $A_j$가 이후 모든 단계 $t = j+1$ 부터 $n$까지 저장소에서 교체되지 않고 유지될 확률은 아래와 같이 계산 할 수 있습니다.
$$
P_{\text{keep}}(j) = \prod_{t = j+1}^{n} \left(1 - \frac{1}{t} \right)
$$

 

최종적으로 따라서 $A_j$가 저장소에 남을 확률은 이렇게 계산 할 수 있고

$$
P_j = P_{\text{select}}(j) \times P_{\text{keep}}(j)
$$

즉, $j > k$일 때 

$$
P_j = \frac{k}{j} \cdot \left(1 - \frac{1}{j+1}\right) \cdot \left(1 - \frac{1}{j+2}\right) \cdots \left(1 - \frac{1}{n}\right)
$$

이후 이를 전개하면 

$$
P_j = \frac{k}{j} \cdot \frac{j}{j+1} \cdot \frac{j+1}{j+2} \cdots \frac{n-1}{n} = \frac{k}{n}
$$

결국 모든 $j \in \{1, 2, \dots, n\}$ 에 대하여 아래와 같은 공식을 얻을 수 있습니다.

$$
P_j = \frac{k}{n}
$$

카더널리티 구하기 - HyperLogLog(HLL) 알고리즘

스트림 데이터의 카더널리티를 카운트하는 기능은 시스템에서 필요합니다.

거의 실시간 환경에서 수많은 로그를 비교적 정확하게 카운트하려면 확률적 알고리즘을 적용해야하고,

그 중 비트 패턴 기반(Bit-pattern based) 알고리즘 HyperLogLog이 일반적으로 많이 사용되고 있습니다.

 

HyperLog++알고리즘이라고도 합니다.

적은 메모리를 사용해서 카너럴리티를 빠르게 근사 추정하는 알고리즘입니다.

동작 방식은 이렇습니다.

1. 데이터의 id를 해시함수로 해시 데이터를 만듭니다.

2. 이후 그렇게 나온 해시 데이터를 이진수 값으로 변경하고 정해둔 최하위 몇자리 비트(m)를 10진수 변환하여 인덱스로 사용합니다.

3. 이진수의 앞자리부터 1이 나올때 까지의 0의 수 (leading zeros) 를 새고 그 값을 idx로 하여 레지스터[idx],value 를 대상으로 max연산을 사용해 큰 값을 레지스터에 넣습니다.

 

위 그림처럼 만약 값이 '0000101100010'이고 m=4로 한다면 인덱스는 '0010', 배열의 인덱스는 '2'가 되고

인덱스에 들어갈 데이터는 0이 연속된 횟수 + 1 즉, (leading zeros) +1, 즉 5가 됩니다.

0으로 시작하지 않는 데이터의 (leading zeros)값은 1이 됩니다.

 

레지스터에 높은 값들이 들어 있다면 높은 (leading zeros) 값이 나온 데이터라는 의미고, 엄청나게 많은 유니크 값들이 시스템에 들어왔다는 의미가 됩니다.

이후 배열의 조화평균을 구하여 전체 데이터의 카더널리티의 근사치를 알 수 있습니다.

 

Java의 HashSet으로 10MB의 메모리가 필요한 계산이 있을때, HLL을 사용하면 결과는 정확한 값과 3%의 차이가 있지만 HashSet이 필요로 하는 메모리 크기의 1/2,500인 512바이트만 사용해서 구현할 수 있다고 합니다.

추가로 HLL의 논문에 따르면 1.5kb의 메모리 만으로 2%이내의 상대 오차로 10억개의 구별되는 데이터 개수를 계산 할 수 있다고 합니다.

HLL에서 m값이 커질수록 정밀도는 높아지지만 메모리 사용량도 커집니다.

 

HLL의 동작원리는 간단하지만 어떻게 "저 방식이 카더널리티를 확인 할 수 있다는거지?"라는 생각이 듭니다.

여기서부터 궁금한 부분 하나씩 해결해보려 합니다.

왜 leading zeros가 높다고 많은 데이터가 들어왔다고 하는걸까?

어떤 수의 (leading-zeros)값이 k가 될 확률은 $10^L$

hash함수를 통해 이진수로 변경된 수를 기준으로 계산하면 $2^L$ 입니다.

HLL의 레지스터에 높은 값들이 들어 있다면 높은 (leading-zeros) 값이 나온 데이터라는 의미고, 즉 엄청나게 많은 유니크 값들이 시스템에 들어왔다는 의미가 됩니다.

이 개념이 HLL알고리즘의 기본적인 뼈대가 되는 Flajolet-Martin Algorithm 이며, HLL알고리즘은 Flajolet-Martin Algorithm의 틀을 가지고 문제점을 개선한 알고리즘입니다.

Flajolet-Martin Algorithm

앞서 잠깐 설명하였듯이 Flajolet-Martin Algorithm은 데이터를 해시하고, 그 결과를 이진값으로 변경한 뒤, 해당 값에서의 (leading-zeros) 값(L)을 읽어 레지스터에 저장하면서 들어온 데이터들의 카더널리티를 판별하는 알고리즘입니다.

 

이 결과는 $2^L$이 되는데,

이렇게 계산한 $2^L$은 이론상으로는 균등하지만 현실적으로는 데이터 수가 너무 적으면 (L)값이 편향이 생긴다는걸 통계를 통해 발견했습니다.

그래서 보정값 $\phi \approx 0.77351$을 나누어 최종적으로 Flajolet-Martin Algorithm에서 통해 집합의 카더널리티를 구하는 공식은 아래와 같습니다.

$$
\\{Cardinality}_{\text{Flajolet-Martin}} = \frac{2^L}{\phi}
$$

LogLog Algorithm

Flajolet-Martin Algorithm에서 발생하는 이상치 문제를 더 개선한 알고리즘입니다.

HLL과 이제 조금 유사해지는데, 배열에 (L)값을 저장합니다.

이진수의 앞의 몇자리(b)를 잘라 십진수로 변환 후 배열의 인덱스로 사용하고, 나머지 이진수의 값에서 (leading-zeros) 값을 구합니다.

 

배열의 길이(m)는 앞에서 자르는 수 b을 활용합니다.

$$m = 2^b$$

 

이후 배열에서 가장 값이 큰 (leading-zeros)들의 평균 (L) 을 낸 다음 (m)을 곱해 카더널리티(k)를 구할 수 있습니다.

$$ \text{Cardinality}_{\text{LogLog}} = m2^L$$

이제 보정상수를 추가해서 최종적인 수식을 만듭니다.

표준 오차는 1.3/√m 입니다.

$$
\text{Cardinality}_{\text{LogLog}} = m \cdot \frac{2^L}{\phi}
$$

SuperLogLog Algorithm

LogLog보다 더 개선된 알고리즘입니다.

배열의 값들의 평균(L)을 내기 전에 가장 큰  (leading-zeros) 값들을 제외하면 더 정확한 카더널리티를 추출 할 수 있음을 발견했습니다.

그래서 SuperLogLog는 평균(L)을 계산할 때 하위 70%까지의 값들 만을 사용해서 평균을 내고 단순한 보정 상수 (0.7)을 곱해서 계산합니다.

$$
\text{Cardinality}_{\text{SuperLogLog}} = 0.7m \cdot \frac{2^L}{\phi},  \quad L = \text{Avg}(\text{Smallest } 70\% \text{ of } L)
$$

 

이렇게 해서 개선된 SuperLogLog의 표준 오차는 1.05/√m 입니다.

HyperLogLog Algorithm

HLL알고리즘은 SuperLogLog

HLL알고리즘에서는 배열의 데이터들에 대해 조화평균(H)이 사용됩니다.

조화평균은 큰 이상치 (outlier)를 처리하기에 유용합니다.

\[
H = \frac{n}{\displaystyle\sum_{i=1}^{n} \frac{1}{x_i}}
\]

HLL 수식은 배열의 값들의 평균(L)에 대해 조화평균을 구한 값을 사용합니다.

$$
\text{Cardinality}_{\text{HyperLogLog}} = m \cdot \frac{\text{Harmonic Mean}\left(2^{L_i}\right)}{\phi}
$$

 

m은 12~14의 값으로 권장된다고 하며, 상대 오차 (Relative Error) 는 1.04/√m로 개선되었습니다.

빈도 추정 - Count-Min Sketch (CMS) 알고리즘

스트림 시스템에서는 어떤 범위에서 특정 데이터가 몇번 발생했는지 아는것은 중요합니다.

요구사항을 만족하기 위해 일반적으로는 Count-Min Sketch (CMS) 알고리즘을 사용합니다.

CMS는 적은 메모리를 사용해서 데이터에서 빈도를 측정하는 알고리즘입니다.

HLL처림 확률적 알고리즘이고, 약깐의 오차는 있을 수 있지만 과소추정은 하지않는다는 특징이 있습니다.

 

CMS 알고리즘을 사용하면 아래와 같은 기능을 구현할 수 있습니다.

• 포인트 쿼리(Point Query) : 특정 데이터가 얼마나 많이 존재하는지
• 레인지 쿼리(Range Query): 주어진 범위에서 데이터 빈도를 알고 싶은 경우
• 이너 프로덕트 쿼리(Inner Product Query) : 두 스케치 알고리즘의 결합을 알고 싶은 경우

동작 과정은 이렇습니다.

 

들어온 데이터를 각 해시함수에 넣어 정수값을 각각 추출하고 그 정수값을 인덱스로하여 행에 +1을 합니다.

같은 데이터가 들어오면 같은 방식으로 계속해서 배열에 값을 증가시킵니다.

데이터가 들어온 수를 조회할때는 데이터를 추가할때 사용했던 동일한 해시함수(h1,h2,h3,h4)를 사용해서 해당 데이터의 인덱스 값들을 찾습니다.

그렇게 찾은 인덱스를 통해 카운터 안의 값들 중 가장 작은 값을 해당 횟수 데이터가 들어온 근사치로 취급합니다.

즉, 위의 사진과 같은 상황에서는 해당 데이터가 들어온 횟수는 '4'회가 됩니다.

논문에 따르면 배열의 길이가 128인 배열 8개를 사용할 때 상대 오차는 약 1.5%이고 추정치가 정확할 확률은 99.6%라고 합니다.

유입된 데이터 확인  - 블룸 필터 (Bloom Filter)

'이전에 유입된 데이터 인지' 확인하는 요구사항이 있을 수 있습니다.

하지만 수많은 스트림 데이터들에 모두 id를 지정하는건 힘든일이고 id를 이용해서 데이터가 이전에 들어왔었는지, 확인하는것은 더욱 더 어려운 일입니다.

이를 위해 '블룸 필터'를 사용합니다.

 

볼룸 필터의 특징은 블룸 필터를 통해 들어온 데이터가 '이전에 입수된 적 있다'는 응답이 100% 믿을 수 없다는 것 입니다. 

하지만 '이전에 입수된 적 있다'는 응답은 100% 믿을 수 있습니다.

즉 긍정오류(False Positive)는 가능하지만 부정오류(Flase negative)는 불가능하다고 할 수 있습니다.

 

크롬에서 악성URL을 판별하거나 CDN에서 cache hit여부를 확인하는데도 블룸 필터가 쓰인다고 합니다!

지금 설명하는 아주 기본적인 블룸 필터입니다.

 

전체적인 동작 방식은 비교적 간단합니다.

먼저 블룸 필터는 길이가 m인 이진수 배열과 k개의 독립적인 해시 함수가 필요합니다.

데이터가 들어오면 각 해시 함수를 통해 해시값을 추출 후,

추출된 해시값을 인덱스로 하여 이진수 배열에 값이 0이면 1을 더하고 이미 1이라면 변경하지 않습니다.

 

그림처럼 데이터의 해시 값이 2,5,7,9가 나온다면 각 인덱스의 값을 1로 변경합니다.

만약 이후 같은 데이터가 들어오면 동일하게 해시값이 나오게 되고, 그 해시 값들의 인덱스가 모두 1이라면 해당 데이터는 이전에 들어온 적 있다고 판단하고, 아니라면 해당 데이터는 들어온적 없는 데이터라고 판단합니다.

 

그렇기에 배열의 크기 (m)을 결정하는게 아주 중요합니다.

m은 아래와 같은 공식으로 정할 수 있으며 bit 크기를 의미합니다.

여기서 n은 삽입할 예상 데이터 수, p는 허용 가능한 오차입니다.

$$
m = - \frac{n \cdot \ln p}{(\ln 2)^2}
$$

 

k는 m을 이용해 구합니다.

$$
k = \frac{m}{n} \cdot \ln 2
$$

만약 1,000,000개 데이터에 대해 1% 허용 오차를 만들고 싶으면 아래와 같이 데이터를 넣습니다.

그리고 그 결과물을 8로 나누어 byte 배열 크기로 만들면 약 1.15가 나옵니다.

이 알고리즘을 통해 아주 작은 리소스로 유입 데이터 여부를 효율적으로 확인 할 수 있습니다.

$$
m = - \frac{1,000,000 \cdot \ln(0.01)}{(\ln 2)^2} \approx 9,585,058 \text{ bits}
$$
$$
\frac{9,585,058}{8 \times 1024 \times 1024} \approx 1.15 \text{ MB}
$$

 

 

참조

• 실시간 데이터 파이프라인 아키텍쳐
• https://chengweihu.com/hyperloglog