DEVOCEAN

실시간 접속자 관리를 위한 효율적인 데이터 구조 : Cuckoo Filter 소개

실시간 접속자 관리의 필요성

A.(에이닷)과 같은 대규모 사용자 시스템에서는 접속 중인 사용자의 정보를 실시간으로 파악하는 것이 매우 중요합니다.

이러한 정보는 사용자에게 적절한 추천을 제공하거나 필요한 조치를 취할 때 지연을 최소화하는 데 필수적입니다.

이 글에서는 실시간 접속자 관리를 위한 데이터 구조 설계 방법을 소개하고, 특히 확률형 자료구조인 Cuckoo Filter를 활용한 접근법을 알아보도록 하겠습니다.

실시간 접속자 관리의 어려움

A.(에이닷)과 같은 서비스에서는 수많은 사용자가 동시에 접속해 있으며, 이들을 효율적으로 관리하는 것은 시스템 성능에 중요한 영향을 미칩니다.

모든 사용자의 접속 정보를 저장하고 관리하기 위해서는 상당한 메모리와 자원이 필요하며, 이 과정에서 성능 저하를 초래할 수 있습니다.

• 메모리 사용량 증가: 사용자가 늘어남에 따라 접속 여부를 확인하고 이를 저장하는 데 필요한 메모리 사용량이 급격히 증가합니다.

  이 경우, 메모리 사용량은 O(n)으로 증가하며, 이는 작은 규모에서는 문제가 없을 수 있지만 대규모 사용자 기반에서는 심각한 성능 저하를 야기할 수 있습니다.

• 실시간 처리의 부하: 사용자의 접속 여부를 실시간으로 처리하려면 지속적인 계산과 데이터 업데이트가 필요합니다.

  이 과정에서 시스템은 상당한 계산 자원과 처리 능력을 요구하게 되며, 특히 피크 시간대에는 서버의 부하가 급격히 증가할 수 있습니다.

  이는 결국 시스템의 응답 속도 저하와 전체적인 성능 저하로 이어질 수 있습니다.

  
  

확률형 자료구조의 도입: Bloom Filter와 그 한계

이러한 문제를 해결하기 위해 확률형 자료구조의 도입을 고려할 수 있습니다.

확률형 자료구조란 대용량 데이터를 효율적으로 처리하기 위해 정확성을 일부 희생하는 자료구조입니다. 어떻게 동작하는 것일까요?

대표적인 확률형 자료구조인 Bloom Filter의 작동원리를 통해 알 수 있습니다.

Bloom Filter란?

집합 내에 특정 원소가 존재하는지를 검사하는데 사용할 수 있는 자료구조입니다. 구조를 도식화 해보면 다음과 같습니다.

출처 : https://systemdesign.one/bloom-filters-explained/

저장할 값인 value를 n개의 Hash Function을 거치게 하고, 각각의 Hash Function의 결과로 나온 인덱스의 bitmap값을 1로 설정해줍니다.

모든 값에 대해 이 과정을 거치면 원소들의 존재유무를 저장하고 있는 bitmap이 만들어집니다.

데이터를 확인하는 과정은 저장하는 과정과 비슷합니다.

존재유무를 확인할 value를 동일한 Hash Function에 넣어주고, bitmap의 인덱스 값이 모두 1이면 집합 내에 존재한다고 판단하는 구조입니다.

많은 데이터가 있어도 bitmap으로 값을 저장할 수 있기 때문에 저장공간을 엄청나게 아낄 수 있습니다.

하지만 Hash Function의 특성상 다른 value임에도 동일한 bitmap 인덱스를 반환할 수 있습니다.

즉, hash collision이 일어나 없는 값을 있다고 말하는 경우도 발생합니다. 이는 False Positive(거짓 양성)의 원인이 됩니다.

하지만, 곧 설명드릴 특성으로 인해 삭제가 불가능하므로, False Negative(거짓 음성) 오류가 발생하지 않는다는 점이 보장됩니다.

거짓 양성(False Positive) : 없는데 있다고 판단하는 오류

거짓 음성(False Negative) : 있는데 없다고 판단하는 오류

Hash Function의 개수와 bitmap 사이즈를 조절함으로써 False Positive 비율을 낮출 수 있지만,

특정 비율 이하로는 낮출 수 없기 때문에 정확도를 일부 희생해야하는 trade-off(어느 한편을 늘리면 다른 한편은 그 만큼 줄어드는 것)가 있습니다.

그럼에도 대용량 시스템에서 1차적으로 데이터의 범위를 줄여주는데 Bloom Filter를 효율적으로 사용할 수 있습니다.

예를 들어 블랙리스트 URL을 관리한다고 하면, 사용자가 URL을 입력했을 때 페이지 로드 전 아래와 같이 플로우를 타면 효율적입니다.

1. 주기적으로 관리해야할 블랙리스트 URL을 Bloom FIlter에 저장

2. 사용자가 URL을 입력 시, Bloom Filter로 빠르게 검사 (정상 URL임에도 블랙리스트로 검출될 가능성 ← False Positive)

3. Bloom Filter로 걸러진 블랙리스트 의심 URL을 다시 검사하는 방식으로 데이터 범위 축소

이렇게 Bloom Filter는 메모리 효율적으로 데이터를 저장하고 빠르게 조회가 가능하지만, 또 다른 문제는 삭제가 불가능하다는 것입니다.

Hash Function 특성 상 다른 value(같은 bitmap 인덱스)를 삭제하게될 수도 있기 때문입니다.

이로 인해 실시간으로 접속하고 연결이 끊기는 접속자 정보를 관리하는 데에는 한계가 있습니다.

Bloom Filter는 다양한 분야에서 널리 사용되며, 직접 구현하거나 라이브러리를 활용해 쉽게 사용할 수 있습니다.

또한, redis-stack에서도 이 자료구조를 지원합니다.

Cuckoo Filter: Bloom Filter의 대안

데이터의 삭제가 불가능한 Bloom Filter의 한계를 보완할 수 있는 Cuckoo Filter를 알아보기에 앞서 각 자료구조의 차이점을 비교해보겠습니다.

Cuckoo Filter vs Bloom Filter

Cuckoo Filter와 Bloom Filter는 모두 확률형 자료구조로서, 메모리를 효율적으로 사용하면서도 대량의 데이터를 처리할 수 있는 장점을 가지고 있지만 몇 가지 중요한 차이점이 있습니다.

Bloom Filter와 Cuckoo Filter는 각각의 특성과 장단점이 있기 때문에, 특정 상황에 따라 적절한 자료구조를 선택하는 것이 중요합니다.

정적 데이터의 빠른 존재 확인이 주된 목적이라면 Bloom Filter가 적합할 수 있으며, A.(에이닷)과 같이 실시간으로 변동하는 데이터를 관리해야 한다면 Cuckoo Filter가 더 나은 선택이 될 것입니다.

Cuckoo Filter란?

Bloom Filter의 장점을 유지하면서도 데이터의 삭제가 가능한 확률형 자료구조입니다.

이는 Cuckoo Hashing(뻐꾸기 해싱) 기법을 기반으로 하며, 이 때문에 'Cuckoo'라는 이름이 붙게 되었습니다.

Cuckoo Hashing을 간략히 설명하자면 ,두 개의 hash table을 기반으로 evict 과정을 반복하는 방식으로 해시 충돌을 해결하는 기법입니다.

Cuckoo Hashing

출처 : https://levelup.gitconnected.com/cuckoo-hashing-a-beginners-guide-e010288bf05d

[1] key = new_key
[2] h(key) = i 를 계산하여, htable[i]에 key를 저장
[3] if key가 저장된 원소가 비어있으면:
        삽입을 종료
[4] else: // key가 저장되면서 그 자리에 있던 키를 evict한 경우
        // key 때문에 evict된 키를 old_key라고 하자.
        [5] if old_key가 있었던 테이블이 htable이면:
                d(old_key) = j 를 계산하여 dtable[j]에 old_key를 저장
        [6] else: // old_key가 있었던 테이블이 dtable이면
                h(old_key) = j를 계산하여, htable[j]에 old_key를 저장
        [7] key = old_key, go to step[3]

두 개의 Hash 함수 h(x), d(x)와 그에 따른 두 개의 hash table(htable, dtable)을 사용하며,

각각 h(x) → htable, d(x) → dtable에 key가 위치하게 됩니다.

해시 충돌이 날 경우, Cuckoo Hashing에서는 중복 값을 유지하는 것이 아닌 evict 과정을 통해 기존에 있던 값을 다른 위치로 옮기고,

그 자리를 확보하여 새로운 값을 삽입하는 방식으로 충돌을 해결합니다.

Cuckoo Filter는 이러한 알고리즘을 통해 효율적인 삭제가 가능하며,

아래에서 다룰 fingerprint의 크기 조정 등의 방식으로 구조적 유연성을 가져 안전하게 데이터를 삭제할 수 있게됩니다.

Cuckoo Hashing Visualization 사이트에서 Cuckoo Hashing을 직접 시뮬레이션 해보며 작동 원리를 보다 직관적으로 파악할 수 있습니다.

Cuckoo Filter의 구조와 작동 방식

그럼 이 Cuckoo Hashing을 Cuckoo FIlter에서 어떻게 적용하고 있을까요?

Cuckoo Filter에서는 hash table을 여러개 사용하여 해시 충돌이 일어날 확률을 더욱 낮추고,

위 예시에서 알파벳으로 표현된 데이터를 bit string인 fingerprint로 저장하여 공간 소비를 최소화 하고있습니다.

다음 구조도를 살펴보면 더욱 직관적인 이해가 가능합니다.

출처 : https://www.researchgate.net/figure/Illustration-of-a-cuckoo-filter-checking-an-element-x_fig2_364297290

Fingerprints

• 해시 함수를 거쳐 Cuckoo Filter에 들어가게 되는 bit-string

Buckets

• fingerprint가 저장되는 위치의 묶음 (hash table)

Two Hash Functions

• h1 함수 : fingerprint가 들어갈 위치(bucket)를 계산해주는 함수.

• h2 함수 : H1 함수로 계산된 위치에 충돌이 날 경우 들어갈 pair location(pair bucket)을 계산해주는 함수

삽입할 값인 X가 두 개의 Hash Function을 통해 들어갈 Bucket 위치(Bucket 1, Bucket K)가 정해집니다.

해시 함수인 fpx(x)로 만들어진 fingerprint(fpx)는 두 개의 Bucket 중 무작위로 선택되어 Bucket K에 들어가게 됩니다.

추가로 Filter Capacity가 8인 이유는, 위 예시의 경우 두 개의 hash function으로 나올 수 있는 가능한 위치가 최대 8개(bucket의 entry 개수 * 2)이기 때문입니다.

이로 인해 pair bucket의 entry가 모두 찬 경우 더 이상 삽입이 불가능하고, Cuckoo Filter를 재배치해줘야하기 때문에 이를 예상하여 Cuckoo Filter를 설계하는 것이 중요합니다.

Cuckoo Filter Operations

위 두 개의 Hash Function (h1, h2)를 사용해 삽입, 조회, 삭제 기능을 수행합니다.

두 Hash Function의 주된 역할은 fingerprint가 들어갈 bucket 위치를 정하는 것으로, 다음과 같이 작동합니다.

• h1, h2 함수를 통해 bucket 위치를 계산

• h2 함수는 계산된 Key값의 fingerprint를 활용해서 pair bucket 위치를 계산해, original Key 값을 참조할 필요 없음

• xor연산을 통해 pair bucket 위치의 무작위성을 부여하고, pair bucket 사이의 상관관계를 가지게 함(하나의 bucket 주소를 알면 다른 하나의 bucket 주소 연산 가능)

  
  

1. 삽입

1. key를 fingerprint로 변환

2. h1으로 first bucket, h2로 second bucket 위치 계산

3. first bucket이 비어있다면 fingerprint 삽입

4. first bucket이 모두 차있다면, second bucket에 삽입

만약 second bucket도 차있다면 Cuckoo Hashing을 활용하여,

first bucket과 second bucket 중 하나를 무작위로 선택하여 해당 버킷에 있는 fingerprint를 무작위로 evict하고, 그 자리에 새로운 fingerprint를 배치합니다.

다음 그림은 Key = 98의 fingerprint가 h1, h2로 계산된 두 개의 버킷 주소중 첫 번째에 들어가는 예시(1~3번 과정)입니다.

같은 fingerprint를 가진 값을 넣는 것은 상관없지만, bucket size * 2 만큼 넣으면 Cuckoo Filter가 overload 되기 때문에 개수 제한이 있습니다.

2. 조회

조회하는 과정은 비교적 간단합니다. key의 해시 값과 fingerprint 값을 구한 후, 해당 위치에 fingerprint가 있다면 True 반환해줍니다.

3. 삭제

key의 해시 값과 fingerprint 값을 구한 후 해당 위치의 fingerprint 삭제합니다.

새로운 fingerprint 삽입으로 밀려난 fingerprint는 i2함수를 통해 fingerprint 기반으로 새로운 bucket으로 밀리기 때문에,

삭제할 bucket을 탐색하고자 할 때 정확한 bucket 위치를 찾을 수 있습니다.

즉 key는 h1, h2 해시 함수로 정해지는 bucket에만 저장되기 때문에, 안전하게 삭제할 수 있는 것입니다.

장점과 한계

Cuckoo Filter는 살펴본 바와 같이 효율적인 데이터 삽입, 삭제, 검색을 지원하는 자료구조입니다.

마지막으로 Cuckoo Filter의 주요 장점과 한계를 정리해보겠습니다.

장점

1. 삭제 가능

2. 조회 연산 속도의 빠름 - 블룸필터와 다르게 한 개의 특정 버킷 entry에 데이터가 존재하기 때문에 여러 위치 확인할 필요 없음

3. False Positive(거짓 양성)의 가능성이 적음

한계

• 충돌이 발생했을 때 fingerprint를 여러번 재배치 해야할수도 있기 때문에 연산 시간이 길어질 수 있음

마치며

에이닷과 같은 대규모 시스템에서 실시간 접속자 관리를 위해 효율적인 자료구조를 선택하는 것은 매우 중요합니다.

Cuckoo Filter는 Bloom Filter의 한계를 극복하며, 실시간 데이터 관리에 적합한 솔루션을 제공하고있습니다.

시스템의 성능 최적화를 위해, Cuckoo Filter와 같은 효율적인 데이터 구조를 도입하는 것을 고려해볼 만합니다.

보다 자세한 내용은 Cuckoo Filter 소개하고 있는 논문을 참고해주세요.

이 글을 통해 확률형 자료구조와 Cuckoo Filter에 대해 이해하고, 보다 효율적이고 안정적인 서비스를 설계하는데 도움이 되길 바랍니다.