[System Design] Design Distributed Counter

Design Distributed Counter

Requirements

Spec

분산 카운터는 준 실시간으로 웹사이트에서 카운터를 표시
- 현재 접속중인 유저 수, 읽지 않은 메세지 수 등.. unique 한 값을 핸들링할 수 있어야 함
avg concurrent active user 100M
peak tps 300M
RW ratio is 10 : 1
minimum operational complexity
accurate distributed counter
low as possible storage usage

Functional Requirements

웹사이트 내에서 분산 카운터를 준 실시간으로 표시
감소 / 증가 연산 지원
카운터가 변경되면 사용자는 확인할 수 있어야함

Non Functional Requirements

Highly Available
Eventual Consistent
Accurate
Reliable
Scale
Low Latency

HLD

Probailistic Data Structures

단순한 접근 방법은 HashSet을 사용하는 방법이다. HashSet을 사용하면 메모리 사용량이 증가하는 대신 카디널리티를 가져오는데는 상수 시간이 소요된다. BitMap과 Hash Value를 조합하는 대안을 고려하는 것도 가능하다. HashSet보단 메모리 사용량이 감소하지만, 높은 카디널리티를 다루어야 할 때는 매우 높은 양의 메모리 사용량이 요구된다.

HyperLogLog와 같은 확률형 자료구조 또한 고려해볼 수 있다. 공간 효율적으로 부정확한 카운터에 대한 추적이 가능하지만 단점으로는 삭제 작업이 지원되지 않는다는 점이다. Count-Min sketch와 같은 자료구조도 대안으로 고려해볼 수 있다. 증가 / 감소 연산이 가능한 공간 효율적 자료구조이지만 마찬가지로 확률적 자료구조라는 점에서 요구사항에 적합하지는 않다.

RDS

카운터의 가장 간단한 구현은 단일 관계형 데이터베이스를 구축하는 것이다. 트래픽 요구사항이 낮은 경우에는 사용할 수 있는 옵션이다. 관계형 데이터베이스에서 카운터를 단순히 구현하려면 어떤 형태로든간에 잠금이 필요하게 된다. 비관적 잠금이나 낙관적 잠금이나 모두 동일하게 쓰기 요구사항이 극도로 높은 시스템에는 이 접근 방식에 대한 확장이 어렵다는 점이다.

서버의 로컬 캐시에서 이벤트 수를 집계해 qps를 줄이는 것도 대안이 될 수 있다. 서버는 주기적으로 데이터베이스에 일괄 업데이트를 수행하며 동시성과 멱등성을 낙관적 잠금으로 처리한다. 이 접근 방식은 대기 시간과 스토리지 비용을 줄여주지만 카운터 업데이트가 지연되어 부정확한 카운트가 발생한다는 점과, 데이터베이스에 쓰기 전에 서버가 충돌하면 정보가 유실되기 때문에 내결함성이 떨어진다는 문제가 있다. 또한 높은 트래픽에서는 여전히 잠금이 필요하므로 결과적으로 성능이 저하된다.

다른 대안으로는 개별 레코드에 대한 카운트 업데이트 이벤트를 유지하는 방식이다. 이 접근 방식은 잠금이 필요하지 않기 때문에 높은 동시성을 지원한다. 다만 카디널리티를 확인하기 위해 전체 테이블을 스캔해야 하는 문제로 읽기 쿼리 속도가 느려지고 스토리지 비용이 증가한다.

분산 카운터를 확장하려면 데이터베이스 샤딩이 불가피하다. Consistent Hashing과 같은 알고리즘을 사용해 분할할 수 있으며 데이터베이스를 분할하면 데이터베이스 인스턴스의 로드를 줄일 수 있다. 또한 고가용성을 위해 데이터베이스 인스턴스에 대한 복제 비용이 추가된다. 복제를 위해 리더-팔로워 복제 토폴로지를 도입할 수 있으며 데이터베이스의 읽기 / 쓰기 부하를 분리해 복제본간 균등한 부하 분산이 되도록 처리할 수 있다.

분산 시스템을 도입해 복잡성이 증가하는 대신 확장성과 고가용성을 챙길 수 있다. SPOF를 방지하기 위한 복제 토폴로지와 분할을 통해 잠금 충돌 가능성을 낮출 수 있다. 쓰기 성능이 향상되었음에도 불구하고 전체 카운트를 알기 위해선 모든 샤드를 쿼리해야 하기 때문에 읽기 속도가 느려진다. 이런 분산 및 수집 패턴은 데이터 액세스 볼륨이 상대적으로 낮은 경우에 최적이다. 다만 우리의 요구사항에서 매우 높은 동시성과 쓰기가 존재하기 때문에, RDS의 트랜잭션은 리더-팔로워 복제 토폴로지에서 복제 지연으로 인한 지연 시간 증가를 초래하고 최종적 일관성을 허용하는 요구사항에선 좋은 옵션이 아닐 수 있다. 또한 여러 데이터 센터에 걸쳐 카운트를 업데이트할 때 멱등성을 보장하는 것도 어려운 문제이다. 멱등성을 보장하기 위한 증가 / 감소 이벤트 레코드를 유지와, 전체 집계 카운트 숫자와 락을 결합한 레코드를 유지하는 것도 옵션이 될 수 있다. 이 경우 스토리지 비용과 트랜잭션 비용이 증가하며 높은 쓰기 트래픽에서, 높은 쓰기 지연이 발생하게 된다.

NoSQL

Apache Cassandra와 같은 오픈 소스 분산 NoSQL 데이터베이스를 선택하는 것도 옵션이다. 카산드라는 가십 프로토콜을 통해 서로 통신하며 Consistent Hashing을 사용한 데이터베이스 자동 파티셔닝을 지원한다. 또한 CAP 이론에 근거해 AP 시스템 모델을 지원하므로 가용성이 중요한 시스템에 적합하다. 그리고 leader less 복제로 데이터베이스 가용성이 높으며 LSM 트리를 사용한 고성능 쓰기를 지원하는 반면 늦은 읽기를 허용한다. 카산드라의 늦은 읽기는 분산 카운터에서 잠재적인 성능 병목이 발생할 수 있어 캐시 계층 도입을 검토해볼 수 있다. 이 접근 방식의 단점은 캐시와의 일관성을 보장하기 어렵다는 점이다. 가령 이종 기기간 트랜잭션을 구성하기 복잡하고, 캐시와 데이터베이스간 불일치가 발생할 수 있다.

카산드라의 counter data type을 통해 분산 카운터를 구축할 수 있다. 카산드라는 여러 데이터 센터에 걸쳐 로컬 대기 시간이 있는 경합 없는 카운터를 제공한다. 다만 Ably의 사례 연구에서 볼 수 있듯이 카산드라의 분산 카운터 성능이 저하된다는 내용을 확인할 수 있다. 또한 카운터 작업이 멱등하지 않다는 점도 단점으로 볼 수 있다.

Message Queue

메세지 큐는 클라이언트가 요청한 카운트 업데이트 이벤트를 버퍼링하는데 사용될 수 있다. 데이터베이스는 비동기적으로 업데이트되며, 고가용성과 내결함성을 위해 메세지 큐를 분산하고 복제해야 한다. 또한 흐름상의 내결함성을 향상시키기 위해 dead letter queue를 도입한다. 데이터베이스 서버를 사용할 수 없을 때 메세지는 dead letter queue에 유지된다.

메세지 큐의 카운트 업데이트 이벤트 버퍼링을 통한 데이터 집계는 데이터 센터 전체의 대역폭 사용량을 줄이고 서비스 처리량을 향상시킨다. 메세지 큐는 서버와 데이터베이스를 분리해 데이터베이스 부하를 줄이고 고가용성을 제공한다. 이런 pub sub 모델의 단점은 데이터의 비동기 처리로 인해 운영 복잡성이 증가하고 카운터가 부정확하다는 점이다. 또한 메세지 큐에서 exactly once를 구현하는 것은 어려운 영역이다.

Lambda Architecture

개별 카운트 업데이트와 집계 카운트 업데이트 두 가지 영역을 다루는 람다 아키텍처를 고려해볼 수 있다. 개별 카운트 업데이트에서 발생하는 이벤트의 경우 이는 이벤트의 source of truth로 간주할 수 있다. 일괄 처리는 Apache Spark로, 실시간 서비스는 Apache Flink와 같은 스트림 처리 서비스를 활용해 실시간으로 카운터를 계산할 수 있다. 실시간 분산 카운터는 일괄 서비스와 실시간 서비스의 결과를 병합하여 정확한 개수를 계산하는 방식으로 가져온다.

읽기 쿼리의 부하를 줄이고 대기 시간을 개선하기 위해 추가 캐시 계층을 배포할 수 있으며 람다 아키텍처는 확장성과 향상된 내결함성을 제공한다. 람다 아키텍처의 단점은 운영 복잡성 증가와 스토리지 비용 증가다.

Redis

레디스는 인메모리 데이터를 통해 매우 높은 성능과 처리량을 제공한다. 분산 카운터는 쓰기 집약적 작업이므로 Redis를 통해 분산 카운터 구축을 고려해볼 수 있다.

INCR 오퍼레이션은 카운터를 원자적으로 증가시키는데 사용되며, 내결함성 향상을 위해 Redis에 리더-팔로워 복제 토폴로지를 적용할 수 있다. 또한 내구성 향상을 위해 관계형 데이터베이스에 카운터를 비동기적으로 유지하는 write-behind 캐시 패턴을 사용할 수 있다. 또는 짧은 대기 시간과 고가용성을 위해 레디스를 액티브-액티브 토폴로지에 배포할 수 있다. 읽기 작업 시 모든 샤드를 쿼리해 개수를 집계하는 대신, 샤드는 가십 프로토콜을 사용해 서로 통신해 읽기 작업 오버헤드를 방지할 수 있다.

여러 데이터 센터에 충돌 없는 카운터 동기화를 위해서는 카운터 업데이트 작업이 멱등적이어야 한다. 기본 레디스를 사용할 때의 단점은 native data type의 연산은 멱등적이 아니며 네트워크 오류 중에 Redis에서 명령 실행이 성공했는지 여부를 확인하는 것도 간단하지 않다는 점이다. 네트워크 오류에 대한 대응책으로는 Lua 스크립트를 실행해 user id와 같은 데이터를 추가로 저장하거나 user id를 사용하는 Set을 사용할 수 있다는 점이다.

CRDT 분산 카운터

분산 카운터는 복제된 상태의 정수이다. 최종적 일관성 모델의 주요 이점은 네트워크 파티션에도 불구하고 데이터베이스를 지속적으로 사용할 수 있다는 점이다. 최종적 일관성 모델은 일반적으로 아래와 같은 방법으로 동시 쓰기 충돌을 처리한다.

갈등 해결	설명	트레이드오프
마지막 쓰기 승리( LWW )	타임스탬프 기반 동기화	시스템 시계를 동기화는 어려운 문제임
쿼럼 기반 최종 일관성	대다수의 복제본으로부터 승인을 기다림	네트워크 대기 시간 증가
병합 복제	병합 서비스는 충돌을 해결함	버그가 발생하기 쉽고 실시간 속도가 느림
충돌 없는 복제 데이터 유형( CRDT )	데이터 융합을 위한 수학적 특성	충돌 해결 의미 체계는 미리 정의되어 있으며 재정의할 수 없음

CRDT(Conflict-free Replicated Data Type)는 레디스 위에서 분산 카운터를 구현하기 위한 잠재적 옵션이다. CRDT는 작업이 항상 모든 복제본 노드 사이에서 일관된 상태로 수렴되도록 하는 복제된 데이터 유형이다. CRDT는 임의의 레플리카 노드의 분산 카운터에 대한 잠금 없는 동시 읽기 및 쓰기를 허용한다. CRDT는 자동적이고 결정적인 충돌 해결을 위해 수학적으로 입증된 규칙을 내부적으로 사용한다.

Property	Formula
교환법칙	a b = b a
결합법칙	a ( b c ) = ( a b ) c
멱등성	a * a = a

CRDT의 멱등성 속성은 복제에서 항목이 중복되는 것을 방지한다. CRDT의 교환 법칙이 경쟁 조건을 방지하기 때문에 복제 순서는 중요하지 않다. CRDT 기반 일관성은 CRDT가 높은 처리량, 읽기 및 쓰기에 대한 짧은 대기 시간을 제공하고 네트워크 파티션을 허용하기 때문에 멀티 리더 토폴로지에서 널리 사용되는 접근 방식이다. CRDT는 클러스터에서 연결이 끊어진 노드에 대한 쓰기도 허용할 수 있는데, 네트워크 연결이 다시 설정되면 데이터 업데이트가 결국 다른 노드와 병합되기 때문이다. 다음은 CRDT를 사용하여 분산 카운터를 구축할 때의 이점이다.

멀티 리더 복제를 통해 읽기 및 쓰기 작업에 대한 로컬 대기 시간 제공
자동적이고 결정적인 충돌 해결이 가능
네트워크 파티션에 대한 내성
복제본 노드 간 조정 없이 동시 개수 업데이트 허용
비동기식 데이터 업데이트를 통해 최종 일관성을 달성

Deep Dive

Fault Tolerance

분산 카운터에 대한 모니터링 및 상태 확인을 구현해야 한다. 다음 엔티티를 모니터링 해야 한다.

카운터 서비스 호출 횟수
CPU, 메모리 등 사용되는 하드웨어 자원

카오스 엔지니어링을 사용해 분산 카운터의 복원력을 테스트하고 SPOF를 식별할 수 있다. CRDT 데이터베이스는 분할된 네트워크 시나리오에 대해 테스트 되어야 한다. CRDT 데이터베이스의 분할된 네트워크에 대한 샘플 테스트 사례는 다음과 같다.

CRDT 데이터베이스 복제본을 분리한다.
여러 데이터 센터에 CRDT 카운터를 배포하고 모두 증가시킨다.
카운터를 중지하고 각 데이터 센터의 개별 카운터를 관찰한다.
카운터에는 로컬 증분만 표시되어야 한다.
네트워크를 다시 구축한다.
모든 데이터 센터의 분산 카운터에는 총 개수가 표시되어야 한다.

High Availablity

분산 카운터에 대한 전체 트래픽은 API 게이트웨이를 통해 라우팅된다. API 게이트웨이는 다음과 같은 문제를 처리한다.

응답 캐싱 및 로깅
허가 및 SSL 종료
회로 차단 및 속도 제한
로드 밸런싱

핫스팟을 방지하기 위해 consistent hashing을 통한 데이터베이스 분할을 고려할 수 있다. 인기있는 데이터가 많이 업데이트되는 핫키 문제는 키 뒤에 임의의 숫자(e.g. 2자리)를 추가해 쓰기 부하를 여러 파티션에 분산시킬 수 있다. 그러다 단점으로는 읽기 작업을 위해 서로 다른 파티션 키를 모두 쿼리해야 하고 이 데이터를 유지하기 위한 추가 오버헤드가 존재한다.

서비스는 state less이며 고가용성을 위해 복제되어야 한다. 기존 노드를 백업하고 이를 새 노드로 복원해 새 CRDT 노드를 클러스터에 동적으로 추가할 수 있다. CRDT 데이터베이스는 일부 CRDT 인스턴스가 실패하더라도 고가용성과 재해 복구를 제공해 계속 읽고 쓸 수 있다. 로컬 데이터 센터에 장애가 발생하면 사용자는 다른 데이터 센터로 전환될 수 있다.

Scalability

Redis 클러스터 토폴로지는 수평적으로 클러스터에 노드를 추가할 수 있도록 지원한다.

Concurrency

동시에 여러 클라이언트에서 쓰기 / 읽기 작업을 진행해야 할 때 일관성을 위해 잠금을 처리할 수 있다. 잠금은 매우 높은 동시성에서 성능 병목 현상을 일으킬 수 있으므로 잠금을 방지해야 한다. Redis는 단일 스레드이며 작업은 원자적이므로 분산 카운터 데이터를 다루는데 있어 잠금이나 동시성 문제가 없다.

Low Latency

CRDT 데이터베이스는 여러 데이터 센터에 배포된다. 짧은 대기 시간과 네트워크 트래픽 감소를 위해 클라이언트 연결은 로컬 데이터 센터로 라우팅되어야 한다.