Active-Active 데이터베이스의 HyperLogLog

Active-Active 데이터베이스의 HyperLogLog (HyperLogLog in Active-Active databases) (hyperloglog)

Redis 공식 문서의 hyperloglog 페이지를 한국어로 풀어드릴게요. 옆에서 하나씩 설명해 드리는 느낌으로 읽으시면 돼요.

출처: Redis 공식 문서 — hyperloglog

Active-Active 데이터베이스에서 HyperLogLog(HLL)를 다루는 방법을 알려드릴게요. 먼저 HLL이 뭔지, 그리고 Active-Active 환경에서 일반 Redis와 어떻게 다른지 하나씩 살펴볼게요.

HyperLogLog란 무엇인가요?

HyperLogLog는 집합의 고유 원소 개수(cardinality)를 세는 count-distinct 문제를 다루는 알고리즘이에요. 집합에 있는 항목 수를 근사해서 알려주죠. 집합의 정확한 cardinality를 구하려면 집합 크기에 비례하는 메모리가 필요해요. 하지만 HyperLogLog는 확률적으로 추정하기 때문에 훨씬 합리적인 메모리만으로 동작해요.

Redis에서의 HyperLogLog

Redis 오픈소스는 HyperLogLog(HLL)를 기본 데이터 구조로 구현하고 있어요.

단순 쓰기 예시

시간 Replica 1 Replica 2
t1 PFADD hll x
t2 --- sync ---
t3 PFADD hll y
t4 --- sync ---
t5 PFCOUNT hll --> 2 PFCOUNT hll --> 2

동시 추가 예시

시간 Replica 1 Replica 2
t1 PFADD hll x PFADD hll y
t2 PFCOUNT hll --> 1 PFCOUNT hll --> 1
t3 --- sync ---
t4 PFCOUNT hll --> 2 PFCOUNT hll --> 2

DEL-wins 접근 방식

Redis-CRDT 구현의 다른 컬렉션들은 충돌을 해결할 때 observed remove 방식을 써요. 하지만 CRDT-HLL은 DEL-wins 방식을 사용해요. HLL 키에 대해 DEL 요청이 다른 요청(ADD/MERGE/EXPIRE)과 동시에 도착하면, replica들은 일관되게 키를 삭제하는 방향으로 수렴해요.

Active-Active 데이터베이스의 HLL vs Redis 오픈소스의 HLL

Active-Active 데이터베이스에서는 Redis 구현을 기반으로 CRDT 안에 HLL을 구현했는데, 몇 가지 예외가 있어요.

  • Redis는 HLL 데이터 구조를 인코딩된 string 객체로 유지해서, HLL이 들어있는 키에 어떤 string 요청이든 실행할 수 있어요. 하지만 CRDT에서는 HLL에 대해 get과 set만 지원해요.
  • CRDT에서 HLL로 인코딩된 값을 가진 키에 SET을 하면 값은 계속 HLL로 남아요. 값이 HLL로 인코딩되지 않았다면 register로 취급돼요.

더 알아보기 (Learn more)

Active-Active 데이터베이스의 데이터 타입에 대해 더 알아보고 싶다면 아래를 확인해 보세요.