기억 파편

• 사용자는 모바일 앱에서 주변 친구를 확인
• 낮은 지연시간: 30초마다 갱신
• 결과적 일관성:
• 1억 DAU
• 동시접속 10% = 천만
• 30초마다 자기 위치를 시스템에 전홍
• QPS = 천만/30 = 334,000

• 로드밸런서: restful api서버, 양뱡향 유상태 ws서버 앞단에서 부하를 고르게 분산
• restful api 서버: 무상태, 친구 추가/삭제, 사용자 갱신 등
• ws 서버: 친구 위치 정보 전송, 커넥션 유지
  • 기존 서버 제거 시 기존 연결을 종료하고 진행(LB에서 상태를 연결 종료 중으로 변경)
• 레디스 위치 정보 캐시: 최근 위치 캐시, ttl 설정 필요(갱신 혹은 비활성화)
  • 사용자 아이디 - 위도/경도/시각 json
  • 영속성 보장 필요 없음
  • 메모리는 괜찮은데 QPS 감당하려면 캐시서버 샤딩 필요
  • HA를 위해 복제
• 사용자 디비: 친구 관계 정보 저장(RDB, nosql)
  • 사용자 상세정보; 친구 관계 데이터
  • RDB사용 시 사용자 아이디 기준으로 샤딩
  • 디비 직접 직의하지 말고 API 서버 호출
• 위치 이동 이력 디비: 사용자의 위치 변동 이력
  • 사용자 아이디, 위도, 경도, 타임스탬프
  • 막대한 쓰기 연산 부하를 감당하며 수평적 규모 확장 가능한 디비: 카산드라
  • RDB사용할 경우 사용자 아이디를 기반으로 샤딩 필요..
• 레디스 펍/섭(메세지 버스): 채널(토픽)만드는 비용이 저렴; 위치 변경 메시지의 라우팅 계층
  • 사용자의 위치가 변경되면 변경 이벤트를 발행하고 친구들이 구독하여 모든 친구의 웹소켓 연결 핸들러가 호출됨. 이벤트를 기반으로 검색 반경 등 계산 후 조건을 만족하면 친구의 앱으로 전송 
  • 채널을 유지하기 위해 구독자 관계를 추적하기 위한 해시 테이블과 연결 리스트가 필요한데 아주 소량의 메모리를 사용한다.
  • 오프라인 사용자라 어떤 변경도 없는 채널의 경우 생성된 이후에 CPU자원은 전혀 사용하지 않는다.
  • 주변 친구 기능을 이용하는 모든 사용자에게 채널 하나씩 부여
  • 사용자는 초기화 시 친구 상태 상관없이 모든 친구와 구독 관계 설정
  • 병목은 메모리가 아니라 CPU사용량
• 분산 레디스 펍섭 클러스터
  • service discovery사용
  • 해시 링에 활성화된 레디스 서버 보관

주기적 위치 갱신

1. 위치 변경 사실을 LB에 전송
2. LB는 변경 내역을 이미 연결을 유지하고 있는 ws로 보냄
3. ws는 해당 이벤트를 위치 이동 이력 디비에 저장
4. ws는 새 위치를 캐시에 보관, ttl 갱신
5. 레디스 내의 해당 사용자 전용 채널에 새 위치를 발행, 3~5의 과정은 병렬로 진행
6. 발행된 새 이벤트는 모든 구독자에게 브로드캐스드
7. 받은 친구의 웹소켓 핸들러는 새 위치와 친구의 위치 사이 거리를 새로 계산한다. 검색 반경 내에 있다면 갱신 시각을 타임스탬프를 앱으로 전송하고 아니면 보내지 않는다.

Redis Pub/Sub(Publish-Subscribe)

Redis Pub/Sub은 실시간 메시징을 위한 Redis의 기능입니다. **발행자(Publisher)**가 메시지를 특정 채널에 발행하면, 해당 채널을 구독(Subscriber) 중인 모든 클라이언트에게 메시지가 전달됩니다.

작동 방식

1. 채널 생성 및 구독: 구독자는 하나 이상의 채널에 구독 요청을 보냅니다.
2. 메시지 발행: 발행자는 특정 채널에 메시지를 보냅니다.
3. 메시지 전달: Redis는 메시지를 해당 채널에 구독 중인 모든 구독자에게 즉시 전송합니다.

Pub/Sub 특징

1. 실시간 메시징: Redis는 메시지를 즉시 구독자에게 전달합니다.
2. 단순 구조: 메시지를 직접 큐에 저장하지 않고 바로 전송합니다.
3. 비동기 통신: 발행자는 구독자의 상태를 신경 쓸 필요가 없습니다.
4. 패턴 구독 지원: 특정 패턴에 맞는 채널 이름을 구독할 수 있습니다.

제약 사항

• 메시지 내구성 없음: 메시지는 발행 시점에 구독자가 없으면 소멸됩니다.
• 확장성 제한: 수많은 구독자가 있는 경우 성능 저하 가능성
• 수평 확장 어려움(클러스터 모드에서 제한적)

Redis Pub/Sub 특징

• 메시지 휘발성: 구독자가 없으면 메시지는 즉시 소멸합니다.
• 빠른 실시간 통신: 짧은 수명의 이벤트나 알림에 적합합니다.
• 단순한 구조로 설정과 사용이 쉽습니다.
• 단점: 내구성 부족, 대규모 확장에 한계가 있음.

Kafka 특징

• 내구성 보장: 메시지를 디스크에 저장하여 장애 복구가 가능합니다.
• 확장성: 클러스터링으로 대량 데이터 처리가 가능합니다.
• 높은 안정성: 정확히 한 번 처리(Exactly Once Processing) 모델 지원.
• 적용 분야: 대규모 데이터 스트리밍, 로그 수집, 이벤트 중심 아키텍처에 적합.

해시 링(Hash Ring)

1. 개념

일관성 해싱을 원형(topology) 구조로 시각화한 표현입니다. 해시 값을 0에서 최대값까지 원형 형태로 배치하고 노드와 데이터 키를 이 링 위에 매핑합니다. 해시 링(Hash Ring)은 데이터 분산 및 노드 추가/제거를 효율적으로 관리하기 위해 사용되는 분산 시스템 기법입니다. 데이터 노드를 원형(ring) 형태로 배치하고, 해싱을 통해 데이터를 특정 노드에 매핑합니다.

2. 동작 방식

1. 모든 노드와 데이터 키에 대해 동일한 해시 함수(예: SHA-1)를 사용하여 해시 값을 계산합니다.
2. 해시 값은 0부터 최대 값까지 이어지는 원형 공간(Ring) 상에 매핑됩니다.
3. 데이터의 해시 값에 가장 가까운 시계 방향 노드가 해당 데이터를 담당합니다.

3. 해시 링의 특징

• 확장성: 노드를 추가하거나 제거할 때 전체 데이터 재배치 비용이 최소화됩니다.
• 부하 분산: 데이터가 노드에 고르게 분산됩니다.
• 내결함성: 특정 노드 장애 발생 시 데이터를 인접 노드로 쉽게 재분배합니다.

4. 장점

1. 노드 추가/제거에 따른 재배치 비용 감소
   기존 해싱 방식에서는 노드를 추가하면 모든 데이터의 재분배가 필요하지만, 해시 링에서는 평균적으로 전체 데이터의 1/n만 재분배됩니다.
2. 노드 장애 시 데이터 손실 최소화
   특정 노드가 장애가 나더라도 인접 노드가 데이터를 처리하므로 손실이 줄어듭니다.

사용 사례

1. 분산 캐시 시스템:
   • Redis Cluster
   • Memcached
2. 분산 데이터 저장소:
   • Amazon DynamoDB
   • Apache Cassandra
3. 분산 메시지 큐
   • Kafka 파티션 데이터 분배

Consistent Hashing (일관성 해싱)

Consistent Hashing은 분산 시스템에서 데이터 분배와 부하 분산을 효율적으로 관리하기 위해 사용되는 해싱 기법입니다. 노드 추가/삭제 시 전체 데이터가 아닌 일부 데이터만 재배치되도록 하여 성능을 개선합니다.

작동 원리

1. 해시 공간의 원형 구조 (Hash Ring)
   • 해시 값이 0부터 최대값까지 연결된 원형 링 형태의 해시 공간을 형성합니다.
2. 노드와 키의 매핑
   • 각 노드(서버)는 해시 함수에 의해 링의 특정 위치에 할당됩니다.
   • 각 데이터 키도 같은 해시 함수로 링 상에 위치합니다.
   • 특정 키는 해시 링에서 **가장 가까운 노드(시계 방향)**에 할당됩니다.
3. 노드 추가/삭제
   • 기존 분배된 대부분의 키는 유지되며, 소수의 키만 재배치되므로 효율적입니다.

분산 레디스 펍섭 서버 클러스터

웹소켓 서버는 해시 링을 참조하여 메시지를 발행할 레디스 서버를 선정

웹소켓 서버는 해당 서버가 관리하는 사용자 채널에 위치 정보 변경 내역을 발행

레디스 펍섭서버는 각 채널의 구독자 목록을 들고 있기 때문에 유상태 서버. 제거 시 채널을 다른 서버로 옮기고 모든 구독자들에게 알려줘야 한다. 보통 유상태 서버 클러스터 규모를 늘리거나 줄이는 것은 큰 운영 부담으로 보통은 여유를 두고 오버 프로비저닝한다. 

펍섭서버를 늘리면 대규모 채널 재조정(재구독)이 일어나기 때문에 CPU부하가 올라간다.

기존 서버를 교체하는 것은 채널 재조정 작업이 없기에 더 안전하다.. 교체하면 교체사실은 웹소켓 서버에게 통지되고 새 펍섭서버의 채널을 다시 구독하도록 알린다. 

친구 추가 삭제 시: 친구의 펍섭 채널을 구독하거나 구독 취소한다.

친구가 많은 사용자? 친구에 상한선이 있고(5000명) 많은 웹소켓 서버에 분산되어 있으니 핫스팟 문제는 발생하지 않을 것.. 

주변의 임의의 사용자? 지오 해시별로 펍섭채널을 두어 사용자의 위치가 변경되면 지오해시 아이디를 계산한 후 해당 지오해시 아이디를 담당하는 채널에 새 위치를 전송한다. 근방에 있는 사용자 중 해당 채널을 구독하는 사용자2는 사용자의 위치가 변경되었다는 메시지를 수신한다.

얼랭으로 확장

웹소켓 서비스는 얼랭으로 구현하고 레디스 펍섭클러스터는 아예 분산 얼랭 애플리케이션으로 대체. 이 애플리케이션에서 각 사용자는 얼랭 프로세스로 표현. 이 사용자 프로세스는 클라이언트가 전송하는 갱신된 사용자 위치를 웹소켓 서버를 통해 수신. 또한 친구의 얼랭 프로세스와 구독 관계를 설정하고 변경 내역을 수신한다..

Erlang의 주요 특징

1. 동시성 (Concurrency)

• 수천만 개의 경량 프로세스(lightweight processes)를 동시에 관리
• 프로세스 간 비동기 메시지 전달 기반 아키텍처
• Actor Model 기반으로 상태 공유 없이 독립된 프로세스 실행
  • Actor Model은 동시성(concurrency) 프로그래밍을 위한 추상화 모델입니다. 이 모델에서는 Actor(액터)가 기본 단위로 동작하며, 서로 독립적으로 실행되고 비동기 메시지 전달을 통해 통신합니다.

2. 고가용성 (High Availability)

• 핫 스왑(Hot Code Swapping) 지원: 실행 중인 시스템에서 코드 변경 가능
• 장애 복구 메커니즘: 프로세스가 실패하더라도 시스템 전체에 영향을 주지 않음

3. 분산 처리 (Distributed Systems)

• 여러 노드를 클러스터링하여 네트워크 기반 분산 시스템 지원
• 노드 간 메시지 전달과 동기화가 자동으로 이루어짐

4. 내장 장애 복구 (Fault Tolerance)

• 프로세스가 죽으면 이를 감시하는 Supervisor가 자동으로 복구

5. 함수형 프로그래밍 (Functional Programming)

• 부수 효과(Side Effect)를 줄이는 방식으로 오류를 예방
• 순수 함수(Pure Functions)와 패턴 매칭(Pattern Matching) 지원

포인트

• 3차원 -> 2차원: 메르카토르 도법의 변형
• 지오코딩: 주소를 위/경도로 변환
• 지오해싱: 2차원의 평면 공간으로 표현된 지리적 위치
• 지도 확대/축소: 사이즈 별로 타일 준비해서 붙여서 보여줌. 완전 줌아웃된 건 지도 한 장으로 가능(이미지)
• 확대 수준이 증가함에 따라 4장씩 사진이 더 필요하다고 하면 0~21확대 수준까지 대략 440PB만큼 필요한데.. 인간이 살지 않는 지구의 90% 지역은 압축을 할 수 있으므로 지도이미지에 대략 50PB가 필요하다. 추가정보까지 하면 약 100PB가 필요하다.
• 경로 안내 알고리즘: 교차로를 노드; 도로는 선. 성능은 그래프의 크기에 민감하기 때문에 세계를 작은 격자로 나누고 각 격자 안의 도로망을 노드와 선으로 구성된 그래프 자료구조로 변환한다. 이 때 각 격자는 routing tile이라고 부른다. 각 타일은 도로로 연결된 다른 타일에 대한 참조를 가지고 있다. 이렇게 타일로 분할해 놓으면 메모리 요구량을 낮출 수 있고 한 번에 처리하는 경로의 양이 줄어 성능이 좋아진다.
• routing tile은 구체성에 따라 상/중/하로 나누어 준비

위치 서비스

• 사용자의 위치를 기록
• 사용자가 주기적으로 위치 정보를 전송
• 해당 데이터 스트림을 활용하여 시스템을 개선, 실시간 교통 모니터링, 새로만들어진 도로, 폐쇄된 도로 탐지 가능
• 위치정보가 실시간에 가까우므로 ETA를 더 정확하게 산출할 수 있고 교통상황에 따라 다른 길을 안내할 수 있다.
• 위치 갱신의 경우 1초마다 서버로 현재 좌표를 보낼수도 있지만 이 요청을 클라이언트에서 모았다가 15초마다 한 번씩 보내 쓰기 QPS를 낮춘다. 몇 초마다 갱신하는지는 사용자의 현재 상태에 따라 달라진다.
• 쓰기에 최적화되고 규모 확장이 용이한 카산드라와 같은 디비가 필요
  • 사용자 위치는 계속 변화하기 때문에 일관성보다는 가용성이 더 중요
  • CAP 정리: 가용성과 분할 내성 두 가지 만족시키도록
• 카프카와 같은 스트림 처리 엔친으로 위치 데이터를 로깅하는 게 좋다
• 프로토콜은 http keep alive로
• 데이터: 유저아이디(파티션 키), 타임스탬프(컬러스터링 키), 위도, 경도, 사용자 모드

지도 표시

• 현재 위치와 인접한 지도 타일을(지오 해싱 기반) url로 준비해 두고 CDN으로 제공
• 맵 타일 인코딩(지오 해싱)이 바뀌거나 할 때를 대비하여
• 위/경도 확대 수준을 던지면(새로운 위치로 이동하거나 확대 수준을 변경하면) 필요한 타일들을 결정하여 타일 url을 생성하는 서비스를 별도로 두어 운영 유연성을 높일 수도 있다. 표시할 1개의 타일과 주변 8개의 타일이 포함된다.
• 최적화 필요 시 벡터 사용; webGL 자바스크립트 사용

경로 안내 서비스

1. 지오코딩 서비스: 주소 -> 위도/경도로 표현
2. 경로 계획 서비스: 최적화 된 경로 제안
3. 최단 경로 서비스: 출발지/목적지 위도/경도받아서 k개의 경로 반환; 교통이나 도로 상황 고려하지 않고 도로 구조에만 의존하여 계산
4. 출발지 타일부터 시작하여 그래프 자료 구조를 탐색해 나가면서 주변 타일을 저장소에서 가져와 연결하여 그래프를 탐색한다.
5. 예상 도착 시간(ETA) 서비스: 위 결과에 대해 각 경로에 대한 소요 시간 추정치를 구한다. 머신러닝 활용하여 현재/과거 이력에 근거하여 예상 도착 시간을 계산한다. 미래 예측에 대한 것은 알고리즘 차원에서 풀어야 한다.
6. 순위 결정 서비스: ETA를 구한 후 사용자가 정의한 필터링 조건(무료도로, 고속도로 제외 등)을 적용, 소요시간 순으로 정렬하여 top k 개를 구한 후 반환
7. 위 서비스들은 카프카 위치 데이터 스트림을 구독하고 있다가 비동기로 데이터를 업데이트하여 그 상태를 항상 최신으로 유지한다.
8. 적응형 ETA 경로 변경: 활성화 사태 유저의 위치 데이터 스트림에서 상황정보를 추출하여 실시간 교통상황에 반영; 이용가능한 경로의 ETA를 주기적으로 재계산하여 더 짧은 ETA를 갖는 경로가 발견되면 알림
9. 전송 프로토콜: 롱폴링, 웹소켓, SSE 가능하나 양방향 통신이 필요한 경우도 있어 웹소켓 사용

1. 롱폴링 (Long Polling)

동작 방식

• 요청-응답 사이클:
  1. 클라이언트가 서버에 HTTP 요청을 보냅니다.
  2. 서버는 즉시 응답하지 않고, 새로운 데이터가 발생할 때까지 연결을 열어둡니다.
  3. 데이터가 준비되면 응답을 보내고, 클라이언트는 응답을 수신한 후 즉시 다음 요청을 보내는 식으로 주기적으로 연결을 갱신합니다.

주요 특징

• 비동기/동기 구현 가능:
  • 기본 HTTP 요청-응답 메커니즘을 사용하므로, 서버와 클라이언트 모두 블로킹 I/O 방식으로 구현할 수 있지만, 비동기 방식으로도 구현이 가능합니다.
• 지속 연결 유지:
  • 각 요청이 데이터가 도착할 때까지 장시간 열려 있으므로, 풀이나 스레드가 해당 연결에 묶입니다.
• 단점:
  • 매번 새로운 요청을 보내야 하기 때문에 HTTP 헤더 등 오버헤드가 발생합니다.
  • 많은 클라이언트가 동시에 접속할 경우 서버의 커넥션/스레드 리소스가 빠르게 소진될 수 있습니다.

사용 사례

• 간단한 실시간 알림이나 업데이트가 필요한 경우
• 서버에서 데이터가 불규칙하게 발생할 때

2. 웹소켓 (WebSocket)

동작 방식

• 초기 핸드셰이크:
  • 클라이언트가 HTTP 업그레이드 요청을 보내고, 서버가 이를 승인하면 HTTP 연결이 웹소켓 프로토콜로 전환됩니다. ws://
• 전이중 통신:
  • 연결이 성립된 후, 클라이언트와 서버는 서로 자유롭게 데이터를 주고받을 수 있습니다.
  • 한 번 연결이 만들어지면, 양방향 통신을 위해 지속적으로 연결을 유지합니다.

주요 특징

• 양방향 통신(Full-Duplex):
  • 클라이언트와 서버 모두 언제든지 데이터를 전송할 수 있어 채팅, 실시간 게임, 협업 도구 등에 적합합니다.
• 낮은 오버헤드:
  • 초기 연결 설정 후에는 별도의 HTTP 요청/응답 없이 데이터 프레임만 주고받으므로, 반복적인 헤더 전송이 없습니다.
• 리소스 관리:
  • 비동기 I/O (예: Netty, Undertow 등)를 사용하면, 한정된 스레드로도 많은 연결을 효과적으로 처리할 수 있습니다.
• 단점:
  • 서버와 클라이언트 모두 웹소켓 프로토콜을 지원해야 하며, 방화벽이나 프록시 환경에서 제약이 있을 수 있습니다.
  • 초기 설정이 다소 복잡할 수 있습니다.

사용 사례

• 실시간 채팅, 게임, 협업 툴 등 양방향 데이터 교환이 필요한 애플리케이션

3. 서버 전송 이벤트 (SSE, Server-Sent Events)

동작 방식

• 단방향 스트리밍:
  • 클라이언트가 HTTP 요청을 보내고, 서버는 해당 연결을 통해 이벤트(텍스트 기반 데이터)를 지속적으로 스트리밍합니다.
  • 연결은 단방향으로 유지되며, 서버 → 클라이언트로 데이터만 전송합니다.
  • Last-Event-ID 헤더와 id 필드를 활용하여 중단된 연결 복구가 가능합니다.
  • SSE는 텍스트 기반 프로토콜이므로 이진 데이터 전송이 필요한 경우 Base64로 인코딩하거나 WebSocket 사용을 고려해야 합니다.
• 자동 재연결:
  • 연결이 끊어질 경우 클라이언트 측에서 자동으로 재연결을 시도하는 기능이 내장되어 있습니다.

주요 특징

• 단방향 통신:
  • 클라이언트에서 서버로 데이터를 보내려면 별도의 요청(예: AJAX)이 필요합니다.
• 구현 단순성:
  • HTTP 기반이므로 기존 인프라와 호환성이 좋고 구현이 비교적 간단합니다.
• 리소스 효율성:
  • 비동기 HTTP 클라이언트(예: Spring WebFlux의 WebClient, EventSource 등)를 사용하면 많은 연결을 효율적으로 관리할 수 있습니다.
• 단점:
  • 양방향 통신이 불가능하므로, 서버에서 클라이언트로만 데이터를 보내야 하는 경우에 한정됩니다.
  • 일부 브라우저(특히 오래된 버전)에서 지원이 제한적일 수 있습니다.

사용 사례

• 실시간 뉴스 업데이트, 주식 가격 모니터링, 알림 시스템 등 서버 → 클라이언트 단방향 데이터 스트리밍

1일 = 24시간 * 60분 * 60초 = 86,400초 = 10^5초

QPS query per second 1초에 검색 수

위도는 적도를 기준으로 북이 + 경도는 본초자오선(그리니치 천문대) 동쪽이 + 

위도/경도/반경을 넘기면 주변 사업장을 알 수 있는 서비스

읽기 연산이 자주 수행되고 쓰기 연산 빈도는 낮음

읽기 연산이 압도적인 시스템에는 RDB가 유리

• 사업장 테이블은 사업자 아이디로 샤딩
• 지리 정보 테이블은(지오해시 기반) 지오해시 - 사업장 아이디로 n개 넣음(두 개를 모두 pk로 잡아서 락없이 추가 삭제 가능)
  • 지리 데이터는 총 1.7G 정도라 샤딩할 필욘 없고 읽기 연산을 위해 replica를 만든다.

주어진 반경 안의 사업장 검색?

위도와 경도에 인덱스를 둬도 인덱스는 오직 한 차원의 검색 속도만 개선하지 교집합을 구할 때는 효율적이지 않다.

지도를 작은 영역으로 분할하고 고속 검색이 가능하도록 색인을 만든다.

지오해시 geo hash 

지오해시는 위도(latitude)와 경도(longitude)를 이진수로 변환하고 이를 문자 코드(알파벳+숫자)로 압축하여 지리적 위치를 표현하는 기법

1. 경도(longitude)와 위도(latitude) 범위 설정

• 경도 범위: [-180°, 180°]
• 위도 범위: [-90°, 90°]

2. 이진 구간 분할

• 경도와 위도를 각각 이진 구간 분할(Binary Subdivision)
• 예시: 경도 [-180, 180]
  • 첫 비트가 1이면 오른쪽 절반 [0, 180],
  • 첫 비트가 0이면 왼쪽 절반 [-180, 0].
• 이 과정을 반복하여 점점 더 좁은 구간을 설정

3. 이진수 결합

• 경도와 위도의 이진수를 교차 결합(Interleaving)
  • 경 -> 위 -> 경 -> 위.. 순으로 나열 
  • 예: 경도 101, 위도 011이면 결합 결과는 100111.

4. 문자 변환(Base32 인코딩)

• 이진수를 Base32 문자(0~9, a~z 중 일부)를 사용해 문자열로 변환
• 예시: 이진수 11010 -> 문자 t
• 100111 -> 10011 + 1 0000 (5자리를 맞추기 위해 뒤에 0 4개로 패딩) -> 19 + 16 -> mh

지오해시 문자열 길이는 위치의 정밀도를 결정

• 1자리: 약 5,000km
• 2자리: 약 1,200km
• 3자리: 약 150km
• 6자리: 약 610m
• 9자리: 약 2m

지오해시 길이가 길어질수록 더 작은 영역을 나타냄

격자 가장자리 이슈

지오해시는 인접한 모든 격자가 공통 prefix를 갖도록 한다 다만 아래 케이스는 예외이다.

• 적도 가장자리 놓일 때
• 자오선상 반대쪽에 놓일 때 

1. 경계 값 문제 (Boundary Values):
   • 지오해시는 격자 기반의 위치 인코딩 시스템이므로, 각 격자의 경계에서 인코딩 된 값들이 인접한 다른 격자와 겹치는 경우가 발생할 수 있다. 예를 들어, 한 격자의 북쪽, 남쪽, 동쪽, 서쪽 끝에 위치한 좌표가 동일한 해시 값을 가지면, 그 점들이 실제로는 다른 격자에 속해 있어야 할 수도 있다.
2. 정확도 부족 (Precision):
   • 지오해시는 좌표를 고정된 비트 수로 인코딩하므로, 격자 크기가 정해져 있다. 이로 인해, 격자의 가장자리 근처에 위치한 좌표들이 부정확할 수 있다. 특히, 정밀도가 낮을수록 큰 격자에서 가장자리 문제를 겪기 쉽다.
3. 경계 면을 넘는 경우:
   • 위도와 경도가 극한값 (북극, 남극, 극한의 경도)에서 격자 경계를 넘는 좌표는 정상적으로 인코딩 되지 않거나 예상치 못한 해시 값으로 변환될 수 있다. 예를 들어, 위도 90도는 북극을 나타내는데, 이 주변의 지오해시 값은 정확하게 분리되지 않을 수 있다.
4. 지리적 불일치 (Geographic Mismatch):
   • 격자 경계가 곡선이 아닌 직선으로 표현되기 때문에, 실제 지리적 경계에서 작은 불일치가 발생할 수 있다. 예를 들어, 대륙 간 경계나 섬과 같은 지리적 특징이 정확하게 격자와 일치하지 않을 수 있다.

해결 방법:

1. 더 높은 정밀도 사용:
   • 가장자리 이슈를 줄이기 위해, 지오해시의 비트 수를 늘려 더 작은 격자를 사용하면 경계 인식이 더 정확해진다. 예를 들어, 5 비트의 해시값보다는 6 비트 이상의 값을 사용하여 정확도를 높일 수 있다.
2. 경계에 대한 예외 처리:
   • 격자의 경계에서 발생할 수 있는 예외를 처리하는 로직을 추가할 수 있다. 예를 들어, 특정 좌표가 경계를 넘어서는 경우, 이를 적절히 인식하고 인접 격자로 조정한다.
3. 경계 분할 알고리즘 개선:
   • 더 정밀한 경계 계산을 위해 알고리즘을 개선할 수 있다. 예를 들어, 격자의 경계에 인접한 다른 격자들을 미리 계산하고, 해당 격자에서 제외되는 좌표들이나 범위 값을 처리하는 방법을 도입할 수 있다.
4. 지오해시의 확장 사용:
   • 지오해시 외에도, 다른 격자 시스템을 함께 사용하거나, 지오해시를 보완할 수 있는 다른 데이터 포맷 (예: 하플릭스 공간 또는 비트맵)을 사용할 수도 있다

표시할 사업장이 충분치 않으면 검색 반경을 키운다. 지오해시 값의 마지막 비트를 삭제하여 얻은 새 지오해시 값을 사용해 주변 사업장을 검색한다.

쿼드트리(QuadTree)의 구조:

• 2차원 공간을 효율적으로 분할하고 관리하기 위해 사용되는 트리 자료 구조
• 쿼드트리는 각 노드가 4개의 자식 노드를 가질 수 있는 트리로 2차원 공간을 네 개의 사각형 영역으로 분할하여 데이터를 관리
• 일반적으로 한 노드는 특정 공간을 대표하고, 그 공간이 더 세분화될 필요가 있으면 4개의 자식 노드를 생성하여 해당 영역을 분할
• 트리구조를 메모리 안에 만드는 것. 이 자료구조는 각각 LBS 서버에 존재해야 하며 서버가 시작될 때 구축된다.

1. 분할:
   • 공간을 네 개의 사각형(혹은 직사각형) 영역으로 분할. 이때, 각 자식 노드는 상위 노드의 공간을 4등분하여 맡게 되며 분할된 각 자식 노드는 해당 영역 내의 데이터를 관리
   • 어떤 노드의 사업장도 100개를 넘기지 않도록 재귀적으로 분할
2. 리프 노드와 내부 노드:
   • 리프 노드: 더 이상 분할할 필요가 없는 공간으로 데이터를 저장하는 노드
   • 내부 노드: 해당 공간을 더 세분화할 필요가 있을 때 자식 노드를 가진 노드
3. 데이터 저장:
   • 데이터는 리프 노드에 저장. 각 노드는 공간 내에서 특정 데이터를 가지고 있으며, 해당 데이터를 저장할 위치를 찾기 위해 트리를 탐색
4. 공간의 분할 방식:
   • 사각형 또는 직사각형 공간을 네 개의 자식 노드로 분할. 분할된 각 자식 노드는 부모 노드의 영역을 차지
   • 공간의 크기가 충분히 작을 때까지 분할하며, 공간에 저장될 수 있는 데이터가 많은 경우 리프 노드로 저장

쿼드트리 전부를 저장하는데 드는 메모리 약 1.7GB. 서버 한 대에 충분히 올릴 수 있다.

다만 읽기 연산 양이 많아지면 여러 쿼드 트리로 분산시켜야 할 것..

고려사항

• 서버를 시작하는 순간에 쿼드트리를 구축하면 서버 시작 시작이 길어진다. downtime 고려
• 한 번에 모든 서버가 동시 시작하면 많은 양의 데이터를 디비에서 읽게 되므로 부하가 발생한다.
• 따라서 순차적으로 갱신하도록 해야 한다.
• 사업장이 추가/삭제될 경우 트리를 갱신해야 하는데 루트노드부터 말단노드까지 트리를 순회해야 한다. O(logN)
• 밤 사이 캐시를 일괄 갱신(수많은 키가 한 번에 무효되면 캐시 서버에 막대한 부하가 생긴다)
• 쿼드 트리를 실시간 갱신하려면 동시 접근하지 않도록 락을 걸어야 한다(멀티 스레드에서도).
• 말단 노드에 새로운 사업장을 추가할 수 없다면 rebalancing이 필요한데 이는 복잡하다.
• 검색반경에 상관없이 가장 가까운 k개 검색 시 적합
• 인구 밀도에 따라 격자 크기를 동적으로 저장 가능

구글 S2 라이브러리의 주요 개념:

S2는 2D 공간을 효율적으로 처리하고, 특히 구체적이고 세밀한 공간 분할을 가능하게 하는 기하학적 알고리즘을 제공. 주로 구면 좌표계에서의 계산을 다루며, Google 지도에서의 공간 계산에 많이 사용

1. 구면 좌표계와 다각형 처리:
   • S2는 구면 좌표계(Spherical Geometry)를 기준으로 공간을 다루며, 구면 위의 점들을 다루는 방식으로, 지구와 같은 구형 물체에서의 좌표 계산에 유리
2. 공간 분할 (S2 Cell):
   • S2는 공간을 셀(Cell)이라는 단위로 나누어 데이터를 처리. 각 셀은 구면을 사각형 모양의 격자 형태로 나눈 것으로 이 셀들은 더 작은 하위 셀로 계속 분할될 수 있음
   • S2의 셀은 기하학적 정확성을 유지하면서도, 작은 셀을 통해 정확한 공간 계산을 가능
3. S2 Cell ID:
   • S2는 셀을 고유하게 식별할 수 있는 S2 Cell ID를 부여하여 셀을 식별. 이 ID는 공간에 따라 다른 값으로 매핑되며, 이를 이용해 빠르게 공간을 검색하고 위치 기반 쿼리를 수행할 수 있다.
4. 계층적 공간 분할:
   • S2는 계층적으로 공간을 분할한다. 상위 셀은 더 큰 지역을 나타내며, 하위 셀은 더 작은 지역을 나타낸다. 이렇게 계층적으로 분할된 셀들을 사용하여, 특정 지역을 검색할 때 효율성을 높일 수 있다.
5. 효율적인 범위 쿼리:
   • S2는 범위 쿼리를 매우 효율적으로 처리할 수 있다. 예를 들어, 특정 반경 내의 점들을 찾거나, 주어진 다각형 내의 점들을 찾는 데 매우 효율적이다.
6. 고정밀 좌표 계산:
   • S2는 구면에 대한 고정밀 계산을 수행하므로, 위도/경도 등의 지리적 데이터를 매우 정밀하게 처리할 수 있다. 이를 통해 대규모 지리 데이터셋을 정확하게 분석할 수 있다.

캐시

• 서버 하나에 다 올라가는(상대적으로 양이 적은) 데이터는 메모리에서 처리하는 것과 비슷하여 굳이 캐시를?
• 상대적으로 덜 바뀌는 지오해시-사업장 아이디는 캐시해도 좋다.
• 캐시에서 조회하고 없으면 디비에서 조회한 후 캐싱
• 사업장 정보를 추가/편집/삭제 시에는 디비를 갱신하고 캐시를 invalidate 해야 한다. 이 연산의 빈도는 상대적으로 낮아서 락을 사용할 필요 없다.
• 필요한 레디스 용량은 약 5G 정도라 한대로도 충분하지만 HA를 보장하고 지역별 traffic latency를 위해 클러스터를 전 세계/지역별로 두고 동일 데이터를 각 지역에 중복하여 저장해야 한다. 
• 사업자 아이디에 따른 각 상세 정보도 캐시 해둔다.

추가 필터링이 필요하다면 작은 격자 안의 모든 사업장 아이디를 확보 -> 상세정보를 가져와서 필터링

1. 위도, 경도, 검색반경을 LB로 보낸다

2. LB는 LBS로 요청을 보낸다

3. LBS는 검색 요건을 만족하는 지오해시 길이를 계산한다. (반경 500미터의 경우 6)

4. LBS는 인접한 지오해시를 계산하여 목록에 추가한다

리스트 = [현재 지오해시, 인접한 8개 지오해시]

5. 리스트에 있는 지오해시 각각에 대해 레디스 서버를 호출하여 해당 지오해시에 대응하는 모든 사업장 ID를 추출한다. 이때 지오해시별로 병렬처리한다.

6.  반환된 사업장 아이디들과 사업장 정보 레디스를 조회하여 상세 정보를 취득한다. 레디스에 없다면 디비를 조회한다. 상세 정보에 의거하여 사업장과 사용자 간 거리를 확실하게 계산하고 우선순위를 매긴 다음 클라이언트에 반환한다.

7. 추가/삭제/갱신되는 사업장 정보는 우선 디비에 저장하고 배치로 레디스에 올려 캐싱한다. 

포인트

• 탑 10 표시
• 특정 유저의 등수
• 특정 유저 +-4등
• 점수 업데이트는 실시간

점수 갱신 시 다른 곳에서도 사용되거나 여러 기능을 지원해야 한다면 2번에 카프카를 넣을 수도 있다.

• 분석 서비스, 푸시 알림 서비스 등

데이터모델

RDB

규모 확장성이 중요하지 않고 사용자 수가 많지 않다면 (유저아이디-점수)

레코드가 수백만 개로 많아지면 성능이 너무 나빠진다.

인덱스를 걸어도 결국 순위를 알려면 기본적으로 전체 테이블을 훑어야 하므로 성능이 떨어진다.

레디스

메모리 기반 키-값 저장소, sortedSet 이용

탑 10에 해당하는 유저의 추가 정보는 hash로 올려주면 순위표 작성 시 수월

개념

• Redis의 Sorted Set(ZSET)은 유니크한 값(value)과 함께 각 값에 대응하는 점수(score)를 저장하는 데이터 구조
• 데이터는 점수(score) 기준으로 정렬되어 저장되며, 동일한 점수일 경우 삽입 순서에 따라 유지됨
• 내부적으로 hash table과 skip list라는 두 자료구조 사용
  • skip list: sorted singly linked list 에 다단계 색인(아래 그림)을 두는 구조; 대량 데이터에서 특정 범위 검색에 효과적

구성 요소

• Key: Sorted Set의 이름
  • leaderboard_feb_2024
• Value: 유일한 요소(데이터)
  • user id
• Score: 실수(double) 형태의 정렬 기준 값
  • 1
• zincrby leaderboard_feb_2024 'nancy1234' 1       //점수 +1
• zrevrange leaderboard_feb_2024 0 9 withscores //탑 10
• zrevrange leaderboard_feb_2024 'nancy1234'     //특정 유저 등수 :234가 나왔다면
• zrevrance leaderboard_feb_2024 234-4 234+4   //+- 4등 유저

저장소 요구사항

• 메모리
  • ID 24자 문자열, 점수가 16비트 -> 한 항목당 26바이트 -> 26바이트 * 2500만 명 = 6억 5000만 바이트 = 650mb
  • 이런 식으로 대충 계산해서 메모리 할당 가능한지 확인
• CPU & IO사용량
  • 최대 QPS 2500/초 -> 한대로도 감당가능
• 영속성
  • 레디스 replica 두어 ha 대비
  • 탑 10 정도는 캐시

일반적인 세팅

AWS 사용

게이트웨이 + 람다

• 람다는 서버리스 컴퓨팅 플랫폼
• 서버를 준비하거나 관리하지 않고 코드를 실행할 수 있음. 필요할 때만 실행되며 트래픽에 따라 그 규모가 자동으로 확장됨.
• api gw가 호출되면 게이트웨이는 적절한 람다 함수를 호출한다. 람다 함수는 스토리지 계층을 호출하고 그 결과를 게이트웨이에 반환한다.

레디스 샤딩

고정 파티션

• 점수 범위별로 샤드를 나눠(0~100점, 100~200점 등)
• 점수가 고르게 분포되었을 때 유리
• 점수가 증가하면 다른 샤드로 옮겨야 함
• 사용자가 어떤 샤드에 알기 위해 mysql에 현재 점수를 저장하거나 2차 캐시를 사용해야 한다

해시 파티션

• 사용자 점수가 몰려있을 경우
• Redis 클러스터는 데이터 분산을 위해 해시 슬롯(Hash Slots)을 사용하여 클러스터 내 여러 노드에 데이터를 효율적으로 분배

해시 슬롯 구조

• Redis 클러스터는 0부터 16383까지의 해시 슬롯(총 16384개)으로 구성
• 각 슬롯은 특정 키 범위를 담당하며, 여러 노드에 균등하게 분배

SLOT = CRC16(key) % 16384

데이터 분배

• 클러스터에 노드가 추가되면 슬롯들이 여러 노드에 나누어 배정
• 예: 3개의 노드로 구성된 클러스터 → 각 노드는 약 5461개 슬롯을 담당
  • Node A → 슬롯 0 ~ 5460
  • Node B → 슬롯 5461 ~ 10922
  • Node C → 슬롯 10923 ~ 16383

해시 태그(Hash Tag)

• 특정 키들을 같은 슬롯에 저장하려면 중괄호 {}를 사용
• 예를 들어, "user:{123}:name"와 "user:{123}:email"은 같은 해시 슬롯에 저장
  • 이유: 해시 계산 시 중괄호 안의 문자열인 123만 사용

데이터 접근 방식

1. 클라이언트는 요청할 키에 대해 해시 슬롯을 계산
2. 해당 해시 슬롯에 연결된 노드로 요청이 라우팅
3. 노드 장애 시 복제본 노드(Replica)가 활성화되어 고가용성 보장

Redis 클러스터 운영 예시

• 노드 A 장애 → 자동으로 슬롯 재분배 및 복제본 승격
• 새로운 노드 추가 → 슬롯 자동 이동
• 노드가 추가되거나 제거되면 Redis는 슬롯 재배정을 통해 데이터를 균등하게 분산
• 분배는 항상 균등성을 지향
• 하지만 수동 설정이 가능하므로 특정 노드에 더 많은 슬롯을 할당할 수도 있음

장점

• 데이터 자동 분산
• 확장성 증가
• 장애 복구 기능(Replication)

단점

• 설정 및 운영 복잡성
• 일부 명령어(KEYS, MULTI, EXEC) 제한

위 방법에서 탑 10을 추리려면 각 샤드에서 탑 10 뽑아서 애플리케이션 단에서 재정렬하여 추려야 한다. 샤드가 많으면 시간이 지연됨

쓰기가 많은 애플리케이션에서는 장애에 대비해 스냅숏을 찍을 때 모든 쓰기 연산을 감당해야 하기 때문.. 보통 메모리를 두 배 더 할당하는 것이 안전하다.

레디스 성능 벤치마킹을 위해 redis-benchmark를 사용하여 초당 얼마나 많은 요청을 처리할 수 있을지 시뮬 해보는 것도 필요하다.

레디스 클러스터에도 레디스 데이터가 유실되는 경우를 대비해 Mysql에 시간과 함께 로그를 저장해 주면 해당 값을 다시 레디스로 옮기는 script를 사용하여 복구 가능하다.

NoSQL

쓰기 연산 최적화, 같은 파티션의 항목을 정렬

• 아마존 dynamoDB, mongo..

레디스 대신 dynamo로 바꾸면,, 비정규화 데이터를 담어야 하고

파티션 키를 game_name#{year-month}로 잡고 점수를 정렬 키로 잡는 게 좋다.

파티션 키가 최근 달이라 hot partition이 될 거고 부하가 높으면 문제다.

한 달을 n개 파티션으로 분할하고 userId % n으로 샤딩 할 수 있다. 읽기/쓰기 모두 복잡해진다.

n은 쓰기 볼륨이나 daily active user 수를 고려해서 정하면 된다.

탑 10을 고를때 각 파티션별로 탑10 골라서 애플리케이션 단에서 최종 탑10을 선정한다(분산-수집 법)

개인의 정확한 등수를 구하는 것보다 상위 x% 인지 알려주는 게 더 나을 수 있다.

아마존 S3 저장소

restful api로 이용 가능한 객체 저장소

블록저장소, 파일저장소, 객체저장소

1. 블록 저장소 (Block Storage) - 초기 기술
   • 등장 배경: 가장 기본적인 데이터 저장 방식으로, 물리적인 디스크를 논리적인 블록 단위로 분할하여 데이터를 저장.
   • 이유: 초기 컴퓨터 시스템에서는 데이터를 빠르고 효율적으로 관리하기 위해 디스크의 저수준 접근 방식이 필요했음.
   • 특징: 파일 시스템이 없었고, 데이터를 단순히 블록 단위로 읽고 쓰는 구조.
2. 파일 저장소 (File Storage) - 블록 저장소 기반
   • 등장 배경: 사용자가 데이터를 더 쉽게 관리할 수 있는 고수준 인터페이스가 필요.
   • 이유: 디렉터리 구조와 파일 경로를 통해 사용자가 데이터를 논리적으로 구분하고 접근할 수 있도록 하기 위해 블록 저장소 위에 파일 시스템을 개발.
   • 특징: 블록 저장소를 기반으로 동작하며, 데이터를 파일 단위로 관리.
3. 객체 저장소 (Object Storage) - 현대적 기술
   • 등장 배경: 클라우드 컴퓨팅 및 대규모 데이터 관리의 요구 증가.
   • 이유: 메타데이터를 포함한 객체 단위의 저장과 확장성을 제공하기 위해 파일 저장소의 한계를 극복.
   • 특징: HTTP API를 통해 접근하며, 데이터 불변성과 확장성이 강조됨.

객체 저장소는 디스크 용량이나 초당 디스크 IO가 병목이 될 가능성이 높다.

• 객체 불변성: 변경 불가능하고 삭제 후 새 객체로 대체해야
  • 저장은 한번만 읽기는 여러 번
• 다양한 크기의 객체를 문제없이 저장
• 키-값 저장소: URI-데이터로 연결됨
• 메타데이터와 객체의 실제 데이터를 분리; 메타데이터는 가변; 실제 데이터는 불변
• 객체는 버킷 안에 두어야 한다: 버킷 생성 -> 객체 생성 (요청 각각)
• 버킷은 디렉터리 같은 계층 구조를 지원하지 않지만 버킷 이름과 객체이름을 연결하여 폴더 구조를 흉내 내는 논리적 계층을 만들 수 있다.

placement service와 consensus protocol

데이터 저장소를 다중화할 때 이 데이터를 어디에 저장할지 선정하는 placement service는 모든 데이터 노드와 heartbeat을 주고 받으며 상태를 모니터링한다. 매우 중요한 서비스이기에 5-7개의 노드를 갖고 을 사용하여 구축할 것을 권장한다. 

• 데이터 일관성 (Consistency)
  • 모든 참여 노드가 동일한 데이터에 동의.
• 내결함성 (Fault Tolerance)
  • 일부 노드가 장애를 일으키거나 악의적으로 동작해도 시스템이 안정적으로 작동.
• 결정성 (Deterministic Agreement)
  • 합의가 끝나면 모든 노드가 동일한 결과를 갖도록 보장.

main하나와 다수의 replica 노드가 존재할 때 모든 replica에 복사되는 것을 모두 기다릴지 일부만 기다릴지에는 데이터 일관성과 지연시간 사이에 trade off가 있다. 어쨌건 모두 결과적 일관성(eventual consistency)은 보장된다.

데이터를 저장할 때는 작은 객체들은 모아서 처리. 이미 존재하는 파일에 추가하는 방식. 용량 한계치에 도달하면 읽기 전용 파일로 변경하고 새로운 파일을 만든다. 멀티 코어인 경우 코어별로 읽기/쓰기 파일을 두어야 blocking 되지 않는다.

uuid로 객체 찾기

관련 정보는 한번 쓰면 수정하지 않고 읽기만 하므로 읽기 성능이 좋은 RDB가 좋다. 이 디비는 노드마다 두면 된다. 

데이터 내구성

Erasure Coding (EC) 의미

• Erasure Coding은 데이터를 다수의 블록으로 분할하고 복구를 위한 패리티 블록을 생성하는 데이터 보호 방식
• 일부 데이터 블록이 손실되더라도 남은 데이터와 패리티 블록을 이용해 데이터를 복구할 수 있음
• 분산 시스템, 클라우드 저장소(Amazon S3, Ceph) 등에서 스토리지 효율성과 장애 복구 능력을 위해 활용

예시: EC(4,2)는 4개의 데이터 블록과 2개의 패리티 블록을 포함하며, 전체 6개의 블록 중 최소 4개만 있어도 데이터 복구가 가능

Parity 의미

• Parity(패리티)는 데이터를 검증하거나 복구하기 위해 계산된 검사 코드
• 주로 XOR 연산을 통해 데이터 블록 값을 합성하여 패리티 블록을 생성
• 패리티 블록은 오류가 발생한 데이터 블록을 역으로 계산하여 복구할 수 있음

응답 지연은 높아지지만 내구성은 향상되고 저장소 비용은 낮아진다

응답 지연이 중요하면 다중화가 좋고 저장소 비용이 중요하면 소거 코드가 좋다.

정확성 검증

데이터 훼손 문제는 디스크에 국한되지 않으며 메모리의 데이터가 망가지고 한다.

원본의 체크섬(해쉬)을 계산하고 전송받은 데이터의 체크섬과 비교하여 정확성을 검증한다. 파일이 읽기 전용으로 전환되기 전에 전체 파일의 체크섬을 파일 말미에 둔다. 

메타 데이터 저장소

버켓 테이블은 replica를 마련

객체 테이블은 샤딩; 균등하게 분포하기 위해 샤딩 키를 버킷이름과 객체 이름을 결합하여 사용(URI에서 사용되는 값)

이러면 객체 목록 출력 시 전체 객체를 불러와서 페이징 할 때 번거롭다(union & paging..). 목록 데이터를 비정규화 하여 이 테이블만으로 리스트를 내리게 설계할 수도 있다.

파일 버저닝

덮어쓰지 않고 새로운 버전의 파일을 추가

삭제도 바로 하지 않고 마킹으로 

큰 파일 업로드 성능 최정화

멀티파트: 객체를 작게 쪼개서 독립적으로 업로드한 후(etag사용) 그 조각을 모아서 원본 객체를 복원

복원이 끝나야 성공 메시지 반환. 복원 끝나면 조각을 사제하여 저장 용량 확보해야

GC(압축)

객체의 지연 삭제: 삭제 표시된 객체

갈 곳 없는 데이터: 반만 업로드되거나 취소된 데이터

훼손된 데이터: 체크섬 검증 실패

바로 지우지 않고 정리 메커니즘을 주기적으로 실행하여 지운다. main-replica 모두 적용해야 한다.

보통 객체를 새로 복사하면서 삭제할 거 제외하고 복사하며 이때 메타데이터 테이블의 fileName, offset 등을 한 트랜젝션 내에서 수정한다.

포인트

• 안정성: 데이터는 소실되면 안됨
• 가용성: 이메일과 사용자 데이터를 여러 노드에 복제하여 계속 동작하게
• 확장성: 사용자 수가 늘어나도 성능 저하 안되게
• 막대한 저장 용량 필요

구 프로토콜과 방식

저장소는 파일 시스템의 디렉터리 but 수십억 개의 이메일을 검색하고 백업하기엔 디스크 IO가 병목이 되고 서버 장애 등 안정적이지 못함

단일 장비 위에서만 동작하도록 설계

분산 메일 서버 아키텍쳐

보낼 때

외부 전송 큐에 보관되는 모든 메시지에는 이메일을 생성하는데 필요한 모든 메타데이터가 포함되어 있음

위 5번 과정으로 인해 외부 SMTP규모를 독립적으로 조정할 수 있게 된다.

외부 전송 큐에 오래 남아 있으면 확인 필요

1. 이메일을 보낼 큐의 소비자를 추가

2. 받는 서버에 장애 발생: 재전송 필요; 지수적 백오프

받을 때

디비는? 완벽한 디비는 없음..

RDB? 데이터 크기가 작을 때 적합. BLOB 써도 접근할 때마다 많은 디스크 IO발생

분산 객체 저장소나 Nosql은 키워드 검색이나 읽음 표시 등의 기능을 제공하기 어려움

• 강력한 데이터 일관성 보장
• 디스크 IO 최소화
• 가용성 아주 높아야 하고 일부 장애를 감냉해야
• incremental backup이 쉬워야

유저 키를 파티션키로 사용하여 같은 샤드에 저장

파티션키: 데이터를 여러 노드에 분산하는 역할; 데이터가 모든 노드에 균등하게 분배되도록(유저 키)

클러스터키: 같은 파티션에 속한 데이터를 정렬하는 역할(폴더)

noSQL 기반으로 할 경우 파티션키/클러스터키 외의 필터링을 어플리케이션에서 하거나 쿼리로 하기보단

테이블을 비정규화해서 테이블 자체를 나눠버리는 게 질의 성능을 향상시켜야 하는 대규모 서비스에 더 맞다.

일관성을 위해 replica 필요

• 장애가 발생하면 클라이언트는 main이 복원될 때까지 동기화/갱신 작업을 완료할 수 없음
• 일관성을 위해 가용성을 희생해야
• 가용성을 위해서는 여러 지역의 데이터 센터에 다중화하고 일반적으로는 가까운 데이터센터에서 통신하다 장애가 났을 때 타 지역 데이터센터에 보관된 메시지를 이용한다.

이메일 스레딩

JWZ 알고리즘의 주요 목적

• 이메일 간 Reply-To 관계를 파악해 계층적 트리 구조를 만듦
• 이메일 클라이언트에서 스레드 형태로 메시지를 표시하기 위해 사용.
• 이메일 그룹화를 통해 사용자에게 논리적이고 직관적인 대화 흐름을 제공.

알고리즘 작동 원리

1. 헤더 정보 수집
   • Message-ID: 각 이메일의 고유 식별자.
   • In-Reply-To: 답장 대상 이메일의 Message-ID.
   • References: 해당 이메일이 참조한 이전 이메일의 Message-ID 목록.
2. 이메일 헤더의 아래 정보를 기반으로 스레드 관계를 결정합니다:
3. 스레드 생성 과정
   1. 모든 이메일의 Message-ID와 **Reply 관계(In-Reply-To, References)**를 분석.
   2. 이메일을 **노드(Node)**로 보고, Message-ID를 키로 하여 초기 노드 목록을 생성.
   3. 각 이메일의 In-Reply-To 및 References를 순회하며 부모-자식 관계를 설정.
   4. 스레드 트리를 형성하며, 루트 노드(시작 이메일)부터 트리가 확장됨.
4. 루트 노드와 고아 처리
   • 루트 노드: Reply 관계가 없는 독립된 이메일로, 새로운 스레드의 시작점이 됨.
   • 고아 메시지: 부모가 없는 이메일. (헤더 정보가 손상되거나 누락된 경우 발생)
     • 별도의 루트 노드로 처리하거나, 관련성이 가장 높은 메시지에 병합.
5. 정렬
   • 시간 순서(예: 날짜/시간) 또는 논리적 Reply 순서에 따라 트리를 정렬.

이메일 검색을 위해

• elastic search 활용하거나 자체 개발할 솔루션
• 디스크 I/O 병목 주의
• 색인을 구축하는 프로세스는 다량의 쓰기 연산을 발생시키므로 LSM(Log Structured Merge) 트리를 사용하여 디스크에 저장되는 색인을 구조화하는 것이 바람직

LSM 트리가 색인 구축에 적합한 이유

1. 쓰기 연산의 효율성
   • LSM 트리는 데이터를 먼저 메모리(RAM) 내의 MemTable에 기록하고, 특정 조건(예: 크기 초과)이 충족되면 이를 **정렬된 SSTable(파일 단위)**로 디스크에 순차적으로 저장합니다.
   • 디스크에 순차 쓰기가 이루어지므로 디스크 I/O 비용이 감소하고, 색인을 구축할 때 발생하는 다량의 쓰기 작업을 효율적으로 처리할 수 있습니다.
2. 쓰기 병목 현상 완화
   • 기존의 B-트리와 같은 데이터 구조는 **랜덤 쓰기(Random Write)**가 많아지는 단점이 있습니다.
   • 반면, LSM 트리는 랜덤 쓰기를 최소화하고, 데이터를 버퍼링 후 배치 처리하여 쓰기 병목을 완화합니다.
3. 색인 업데이트의 성능 향상
   • 색인을 업데이트할 때, 기존 데이터를 즉시 덮어쓰지 않고 새로운 데이터를 추가한 뒤 Compaction(압축) 과정을 통해 병합합니다.
   • 이를 통해 쓰기와 병합 작업이 분리되어 성능이 향상됩니다.
4. 다량의 색인 생성
   • 색인을 구축하는 도중에 읽기 연산이 발생하더라도, LSM 트리는 메모리 내 데이터와 디스크 데이터를 병합하여 읽기 요청을 처리할 수 있습니다.
   • 색인 작업 도중에도 안정적으로 데이터를 처리할 수 있는 구조를 제공합니다.

LSM 트리 작동 과정

1. MemTable: 데이터를 메모리에 기록 (쓰기 연산 집중).
2. Flush: MemTable이 가득 차면, 이를 디스크에 **SSTable(Sorted String Table)**로 기록.
3. Compaction: 여러 개의 SSTable을 병합하여 디스크 공간을 최적화하고 읽기 성능을 향상.

포인트

• 동시성은 높으나 초당 예약 건수는 높지 않음
• 약간의 지연시간 가능

데이터베이스로 RDB 선택

• 인덱스 등을 사용하여 읽기가 압도적인 흐름을 잘 지원(no sql은 쓰기에 빠름)
• ACID 보장(이중 청구, 이중 예약, 잔액 마이너스 등 방지)
• 데이터 모델링(호텔, 객실 등) 가능
• 7,300만 개 정도의 데이터는 하나의 데이터베이스로 저장하기에 충분하지만 SPOF가능성이 있어 replica를 두는 게 좋다.
• 데이터가 많아진다면 현재 및 향후 데이터만 저장하고 나머지는 cold storage에 옮기거나
• 데이터 베이스를 호텔 키를 기반으로 샤딩한다.

동시성; 이중 예약 문제

• 멱등성 api; 주문 키를 디비 pk로 사용하여 두 번 저장되지 않게
• 서로 다른 사용자의 동시 디비 접근을 막기 위해 디비 락
  • 비관락 select for update 충돌이 있을 것이라 가정하고 미리 락; 모든 연산을 직렬화; 데이터에 대한 경합이 심할 때; 교착 상태 빠질 수, 성능 낮아짐
  • 낙관락: 테이블에 버저닝, 락을 걸지 않아 비관락보다 빠름 하지만 동시성 수준이 높으면 성능이 급격히 나빠짐
  • constraint(디비 제약조건); 낙관락과 유사, 제약 조건 맞으면 롤백; 디비별로 지원하지 않을 수도

규모 확장

• 호텔 아이디를 기반으로 한 데이터베이스 샤딩
• 예약 서비스는 잔여 객실 질의는 캐시에다 하고 갱신은 디비에다 한다. 디비에 갱신이 일어나면 비동기로 캐시 데이터를 갱신한다.
• 캐시: 낡은 데이터 소멸되도록 TTL 설정; 레디스를 두고 잔여 객실 질의할 때 캐시를 쓸 수 있게
  • 키: hotelId_roomtypeId_yyyymmdd
  • 값: 잔여 객실 수
• 캐시 갱신: 비동기로
  • 갱신은 어플리케이션 단에서 할 수도 있고 카프카 소스 커넥터 + 디비지움(CDC)를 사용하여 디비 변경 사항을 감지하여 캐시에 반영하게 한다.

MSA 일관성

여러 개의 단일 트랜젝션을 어떻게 일치시킬까

2PC: 여러 노드에 걸친 하나의 트랜젝션

한 노드에 장애 나면 중단; 트랜젝션 참여 노드가 많아질수록 통신 오버헤드와 응답 지연 증가

1단계: 준비 단계 (Prepare Phase)

• 코디네이터(또는 트랜잭션 관리자)가 트랜잭션에 참여하는 모든 노드에 Prepare 명령
• 각 노드는 트랜잭션을 수행할 준비가 되었는지 확인하고, 로컬에서 트랜잭션의 상태를 저장(로그 기록)한 뒤, 코디네이터에게 승인(YES) 또는 거부(NO)를 응답
  • 응답이 YES이면 해당 작업을 커밋할 준비가 되었다는 의미.
  • 응답이 NO이면 트랜잭션을 중단해야 한다는 의미.

2단계: 커밋 또는 롤백 단계 (Commit or Rollback Phase)

• 모든 노드가 YES를 응답하면 코디네이터는 트랜잭션을 커밋(Commit)
• 한 노드라도 NO를 응답하면 코디네이터는 트랜잭션을 롤백(Rollback)
• 각 노드는 코디네이터의 명령에 따라 커밋 또는 롤백을 수행한 뒤 결과를 다시 코디네이터에게 알림

사가: SAGA 트랜잭션은 분산 시스템에서 장기 실행 트랜잭션을 관리하기 위한 설계 패턴으로, 분산 트랜잭션의 일관성을 보장하면서도 2PC의 성능 및 확장성 문제를 해결하기 위해 고안

• 데이터의 최종적 일관성(Eventual Consistency)을 보장.
• 보상 작업(Compensating Transaction)을 통해 롤백 대신 이전 상태로 복구.
• 분산 락(Distributed Lock)을 사용하지 않아 확장성과 성능이 뛰어남.
• 네트워크 및 시스템 장애에 대한 복원력을 높임.

1. Choreography (코레오그래피)
   • 각 서비스가 다른 서비스로 직접 이벤트를 발행하고 구독.
   • 중앙 제어 지점이 없음.
   • 유연성이 높지만, 서비스 간 결합도가 증가할 수 있음.
   • 예시:
     • A 서비스가 작업 완료 후 이벤트를 발행 → B 서비스가 이벤트를 받아 다음 작업 수행 → C 서비스도 같은 방식으로 진행.
2. Orchestration (오케스트레이션)
   • 중앙 컨트롤러(오케스트레이터)가 각 서비스를 호출하고 트랜잭션을 제어.
   • 서비스 간 결합도는 낮지만, 중앙 집중식 제어가 필요.
   • 예시:
     • 중앙 오케스트레이터가 A, B, C 서비스를 순차적으로 호출하고 결과에 따라 보상 작업 수행.

SAGA 트랜잭션의 기본 흐름

1. 각 단계(Step)는 독립적인 로컬 트랜잭션으로 실행되고 커밋.
2. Step 중 하나가 실패하면 이전 단계에서 실행된 트랜잭션을 보상 작업으로 되돌림.
3. 전체 작업이 성공하거나 보상 작업이 완료될 때까지 진행.

2024.02.29 - [architecture/micro service] - [arch] EDA, event sourcing, saga, 2pc

포인트

• 광고 클릭시 로그 쌓음
  • 광고 아이디 시간 유저 국가 등
• 집계 필요
  • 특정 광고에 대한 지난 n분간의 클릭 이벤트 수
  • 지난 x분간 가장 많이 클릭된 광고 y개
• 광고 클릭 QPS = 10,000
• 최대 광고 클릭은 50,000로 가정
• 클락 하나당 0.1kb 저장 용량 필요하다고 가정; 하루 100기가; 월간 3테라

방식

• 로그에 정형화되게 남기면 1분마다 집계하여 저장해두고 요청이 오면 집계데이터를 filter하거나 sum하거나 등 가공하여 내림
  • 원시 데이터도 저장하고 집계 데이터도 저장하고
  • 원시 데이터를 통한 재집계 지원
  • 질의는 집계된 데이터에만 
  • 시간이 지나면 원시 데이터는 아애 옮겨버려
• 원시 데이터는 쓰기양이 많으므로 시계열 데이터에 유리한 influxDB나 카산드라 추천

집계 서비스

로그가 들어오면 메세지 큐에 쌓이고 큐에서 원시 데이터 저장소에 저장하고 집계 서비스로 흘러간다

mapReduce 프레임워크 사용; mapReduce 프레임워크에 좋은 모델은 DAG(directed acyclic graph)모델

1. MapReduce Framework

• 개요: MapReduce는 대규모 데이터를 분산 환경에서 처리하기 위한 프로그래밍 모델.
  • Map 단계: 데이터를 키-값 쌍으로 매핑.
  • Reduce 단계: 동일한 키를 가진 값을 집계 및 계산.
• 작업 처리 흐름:
  • 데이터는 Map 단계에서 병렬 처리되고, Shuffle/Sort 과정을 통해 Reduce 단계로 전달.
  • Reduce 단계에서 최종 결과를 생성.
• 제약:
  • 단순한 작업 흐름으로 인해 복잡한 작업 간 의존성을 표현하거나 최적화하기 어렵다.
  • 한 번에 단일 Map → Reduce 작업만 가능하므로 다중 스테이지 워크플로우는 비효율적.

2. DAG 모델

• 개요: DAG는 작업 간 의존성을 표현하기 위해 사용되는 방향성 비순환 그래프.
  • 각 노드: 개별 작업(예: Map, Reduce, 기타 연산).
  • 각 간선: 작업 간의 데이터 의존성을 나타냄.
  • "비순환(Acyclic)": 작업이 완료되면 되돌아가지 않음(순환 없음).
• 특징:
  • 복잡한 작업 워크플로우를 시각적으로 표현 가능.
  • 병렬로 실행 가능한 작업을 식별하여 최적화 가능.
  • 작업 실행 순서를 명확히 정의.

3. 카프카 스트림즈 사용

• 카프카 토픽으로 들어오는 데이터를 소비하며 시간 기반의 집계 처리

StreamsBuilder builder = new StreamsBuilder();
KStream<String, String> input = builder.stream("input-topic");
input
    .groupByKey()
    .windowedBy(TimeWindows.of(Duration.ofMinutes(1)))
    .count()
    .toStream()
    .to("output-topic");
KafkaStreams streams = new KafkaStreams(builder.build(), props);
streams.start();

1분 단위 데이터 처리 흐름

1. 데이터 수집

• 예를 들어, Kafka의 프로듀서가 데이터를 지속적으로 전송하고, Spark/Flink/Kafka Streams가 이를 소비합니다.

2. 윈도우에 데이터 저장

• 데이터는 버퍼 또는 임시 저장소에 저장됩니다.
  • Spark Streaming: RDD 내부에 데이터가 임시 저장됨.
  • Flink: State Backend(예: RocksDB)에서 상태 관리.
  • Kafka Streams: 내부 상태 저장소를 통해 관리.

3. 1분 타이머 완료 시 처리

• 타이머가 1분에 도달하면:
  • 데이터를 sum, count, average 등으로 집계.
  • 집계 결과를 특정 주체로 전달.

4. 데이터 삭제

• 1분 타이머가 종료되면 해당 윈도우의 데이터는 메모리에서 삭제되거나 다음 처리 단계로 넘깁니다.
  • Spark: 새로운 마이크로 배치를 시작하며 이전 데이터는 삭제.
  • Flink/Kafka Streams: 윈도우 종료와 함께 상태를 정리.

스트리밍 vs 일괄 처리

람다 아키텍처의 주요 구성

배치와 스트리밍을 동시에 지원하는 시스템 아키텍쳐

1. Batch Layer (배치 레이어):
   • 역할: 대규모의 정적 데이터(이력 데이터)를 처리하고 정확한 분석 결과를 제공합니다.
   • 1분 동안 수집된 데이터를 주기적으로 처리해 정확한 집계 결과 생성.
   • 특징:
     • 주기적으로 데이터를 처리.
     • 데이터의 **불변성(Immutable)**을 보장하여 과거 데이터를 다시 분석하거나 복구가 가능.
   • 주요 기술:
     • Hadoop, Spark, Hive 등.
   • 산출물:
     • 주기적으로 계산된 배치 뷰(Batch View).
2. Speed Layer (스피드 레이어):
   • 역할: 실시간으로 들어오는 데이터를 빠르게 처리하여 최신 정보를 제공합니다.
   • 실시간 데이터 스트림을 활용해 1분 이내의 최신 데이터를 반영.
   • 특징:
     • 지연(latency)을 최소화.
     • 데이터를 임시 저장하거나 간단한 처리를 수행.
   • 주요 기술:
     • Apache Kafka, Storm, Flink, Spark Streaming 등.
   • 산출물:
     • 최신 상태를 반영한 실시간 뷰(Realtime View).
3. Serving Layer (서빙 레이어):
   • 역할: 배치 뷰와 실시간 뷰를 결합해 최종 데이터를 사용자에게 제공.
   • 배치 결과와 실시간 데이터를 통합해 최종 집계 데이터를 제공.
   • 특징:
     • 두 레이어의 결과를 통합하여 질의(Query)에 응답.
     • 읽기 요청에 최적화된 시스템.
   • 주요 기술:
     • Elasticsearch, Cassandra, HBase 등.

람다 아키텍처의 데이터 처리 흐름

1. 데이터 수집:
   • 데이터를 Batch Layer와 Speed Layer에 동시에 전달.
2. Batch Layer:
   • 데이터 전체를 처리해 정확한 배치 뷰를 생성.
   • 처리 속도가 느릴 수 있지만, **정확성(Accuracy)**이 핵심.
3. Speed Layer:
   • 실시간 데이터를 처리하여 최신 상태를 반영한 실시간 뷰를 생성.
   • 처리 속도가 빠르지만, 최종적으로 정합성이 보장되지 않을 수 있음.
4. Serving Layer:
   • 배치 뷰와 실시간 뷰를 통합해 사용자에게 최신 데이터 제공.

장점

1. 실시간성과 정확성:
   • 배치 처리의 정확성과 실시간 처리의 신속성을 동시에 제공.
2. 확장성:
   • 배치 레이어와 스피드 레이어 모두 분산 시스템 기반으로 확장 가능.
3. 유연성:
   • 과거 데이터를 보존해 언제든 재처리가 가능.

단점

1. 복잡성 증가:
   • 두 개의 레이어를 유지관리해야 하므로 운영이 복잡.
2. 데이터 중복 처리:
   • 배치와 실시간 레이어에서 동일 데이터를 중복 처리.
3. 비용 문제:
   • 두 레이어를 운영하므로 인프라 비용 증가.

사용 사례

• 소셜 미디어 분석:
  • 실시간으로 트렌드를 파악(Speed Layer).
  • 장기적인 사용자 행동 분석(Batch Layer).
• 금융 데이터 처리:
  • 실시간 거래 감시(Speed Layer).
  • 전체 거래 기록 분석(Batch Layer).

카파 아키텍처의 주요 개념

실시간 데이터 스트림 처리를 중심으로 구성되며, 배치 처리 레이어를 없애고 단일 스트림 처리 파이프라인으로 모든 데이터를 처리

1. 단일 데이터 파이프라인:
   • 모든 데이터 처리를 스트림 기반으로 수행.
   • 배치와 실시간 처리를 동일한 데이터 처리 엔진을 사용해 통합.
2. 이벤트 소싱(Event Sourcing):
   • 데이터를 이벤트 로그로 기록하며, 재처리(replay)를 통해 필요한 분석 작업 수행.
   • Kafka Topics 같은 로그 기반 저장소를 활용.
3. 일관성(Consistency) 및 유연성:
   • 데이터의 재처리를 통해 정합성을 유지하고, 새로운 처리 로직 적용 가능.
4. 재처리(Replay):
   • 데이터 로그를 다시 읽어 과거 데이터를 재분석하거나, 새롭게 정의된 처리 방식으로 기존 데이터를 처리.

카파 아키텍처의 주요 구성 요소

1. 데이터 소스:
   • 데이터는 실시간으로 수집되어 로그 저장소로 들어갑니다.
   • 예: IoT 센서, 웹 클릭 로그, 트랜잭션 기록 등.
2. 로그 저장소:
   • 데이터의 단일 진실 소스(Single Source of Truth)로 사용됩니다.
   • 예: Apache Kafka, Pulsar.
   • 로그 저장소는 데이터를 소비자가 원하는 속도로 읽고 처리할 수 있도록 지원.
3. 스트림 처리 엔진:
   • 실시간 데이터 처리를 수행하며, 배치와 실시간 처리를 동일한 방식으로 처리합니다.
   • 예: Apache Flink, Kafka Streams, Apache Beam.
4. 저장 및 조회 시스템:
   • 처리된 데이터를 저장하고 사용자 쿼리에 응답합니다.
   • 예: Elasticsearch, Cassandra, HBase.

카파 아키텍처의 데이터 처리 흐름

1. 데이터 생성 및 수집:
   • 데이터 소스에서 이벤트를 수집하여 로그 저장소에 저장.
2. 로그 저장소:
   • 모든 이벤트는 Kafka Topic과 같은 로그에 저장됩니다.
   • 이 데이터는 소비자(Consumer)가 처리할 때까지 유지.
3. 스트림 처리:
   • 스트림 처리 엔진이 데이터를 실시간으로 처리.
   • 재처리가 필요할 경우 로그 저장소를 다시 읽어 과거 데이터를 처리.
4. 결과 저장:
   • 처리된 데이터를 데이터베이스나 검색 시스템에 저장.
   • 결과는 사용자 요청에 따라 즉시 제공.

장점

1. 단순화:
   • 배치와 실시간 처리를 통합해 관리 복잡성 감소.
2. 유연성:
   • 로그 저장소에서 데이터를 재처리할 수 있어 새로운 요구사항에 적응 가능.
3. 확장성:
   • 로그 기반 시스템(Kafka)은 대규모 데이터를 효율적으로 처리하고 확장 가능.
4. 신뢰성:
   • 로그 저장소를 통해 데이터 유실 방지.

단점

1. 재처리 비용:
   • 로그 저장소에서 과거 데이터를 읽어 재처리하는 데 시간이 오래 걸릴 수 있음.
2. 기술 의존성:
   • Kafka, Flink와 같은 특정 기술에 크게 의존.
3. 성능 병목:
   • 실시간 스트림 처리 엔진이 데이터 처리 속도를 제한할 가능성.

집계 기준 시각

• 이벤트 발생 시각
  • 클라이언트/요청 시간 기준 -> 정확한 집계가 가능하지만 시간 조작 가능성도 있음
• 처리 시각
  • 서버 도착 시간 기준 -> 안정적이지만 지연되는 이벤트는 부정확함
• 이벤트 발생 시각 + 워터마크 기법

워터마크의 개념

워터마크(Watermark)는 데이터 스트림 처리에서 이벤트 시간(Event Time)을 기반으로 지연 데이터를 처리하는 중요한 개념입니다.
주로 실시간 집계 및 윈도우 연산에서 사용되며, 늦게 도착한 데이터를 효율적으로 다룰 수 있도록 설계되었습니다.

• 이벤트 시간(Event Time): 데이터가 실제로 생성된 시간을 의미. (예: 로그의 타임스탬프)
• 처리 시간(Processing Time): 스트림 처리 엔진이 데이터를 처리하는 실제 시간.
• 데이터 스트림 환경에서는 네트워크 지연이나 시스템 병목으로 인해 이벤트 시간이 비정상적으로 늦게 도착하는 경우가 있습니다. 이를 지연 데이터(Late Data)라고 합니다.

워터마크(Watermark)는 이런 지연 데이터를 다루기 위해 특정 시점까지 기다렸다가 더 이상 이벤트가 도착하지 않는다고 가정하는 기준점입니다.

워터마크의 동작 방식

1. 윈도우 연산 수행:
   • 데이터를 특정 기간(예: 1분)으로 그룹화하여 집계.
   • 예: 09:00:00 ~ 09:01:00까지의 데이터를 집계.
2. 지연 허용 시간 설정:
   • 워터마크는 지정된 허용 지연 시간 뒤에 도착하는 데이터는 무시하거나 별도로 처리합니다.
   • 예: 지연 허용 시간 = 10초 → 09:01:10 이후 도착한 데이터는 늦은 데이터로 간주.
3. 워터마크 생성:
   • 스트림 처리 엔진이 워터마크를 주기적으로 생성.
   • 워터마크는 데이터의 이벤트 시간 기준으로 현재까지의 처리 상태를 나타냄.
   • 예: "현재 이벤트 시간은 09:01:05이며, 이 시점 이후에 도착한 데이터는 늦은 데이터로 처리."
4. 윈도우 종료:
   • 워터마크가 윈도우의 종료 시간을 초과하면 해당 윈도우의 데이터를 닫고 결과를 출력.
5. 워터마크가 짧으면 데이터 정확도는 떨어지지만 시스템 응답 지연은 낮아진다. 워터마크를 사용하면 데이터의 정확도는 높아지지만 대기 시간이 늘어나 전반적인 지연 시간은 늘어난다.

집계 윈도

• 텀블링 윈도우: 데이터를 고정된 간격으로 집계하며 중복 데이터는 처리하지 않음. 단순하지만 중간 데이터 손실 가능.
• 고정 윈도우: 텀블링과 동일하지만 구현 방식에 따라 다르게 표현될 수 있음.
• 호핑 윈도우: 고정된 크기의 윈도우를 지정된 간격으로 중첩해 이동. 주기적인 데이터 분석에 적합.
• 슬라이딩 윈도우: 작은 간격으로 데이터를 집계해 연속적으로 처리. 실시간 분석에 적합하나 계산량이 많음.
• 세션 윈도우: 이벤트 간의 비활성 시간을 기준으로 유동적으로 윈도우 종료를 결정. 사용자 활동 및 비정기적 이벤트 추적에 유리.

전달 보장

• 카프카; 정확히 한 번
• 중복 집계 되지 않도록 오프셋 관리 철처하게
• 오프셋은 외부 파일 저장소에 기록
• 아래 4~6 단계의 작업을 하나의 분산 트랜젝션에 넣어야 한다.

집계 서비스의 규모 확장/핫스팟 문제 시

보통 규모 확장을 위해 추가 서버 투입, 다중 프로세스, 다중 노드로 처리

집계 서비스의 fault tolerance를 위해

스냅 샷을 찍어서 그 후로 복구(집계 데이터 포함)

모니터링

• 지연 시간: 각 단계마다 timestamp 추적이 가능하도록
• 메세지 큐 크기: 카프카의 record lag 등으로 집계 서비스 노드 추가 투입 판단
• 시스템 자원: cpu, jvm, 디스크
• 조정: 배치 결과랑 실시간 결과랑 비교해서 데이터 무결성 검증

시계열 데이터

시간에 따라 변화하는 데이터를 다루는 데이터 유형으로, 주로 시간 순서가 중요한 데이터

시계열 데이터 저장소

• 많은 양의 쓰기 연산 부하
• 읽기 연산의 부하는 잠시 급증하는 정도

1. 쓰기 연산이 항상 많은 경우

문제점

1. 관계형 데이터베이스 (RDBMS):
   • 트랜잭션 처리 오버헤드:
     • RDBMS는 ACID 특성을 보장하기 위해 쓰기 작업마다 트랜잭션을 처리합니다. 이로 인해 데이터 삽입 속도가 느림
   • 스키마 설계 제약:
     • 시계열 데이터는 빠르게 증가하기 때문에, 인덱스가 방대해지고 조인 연산이 많아지면 쓰기 성능이 저하
   • 확장성 부족:
     • 수평 확장(Sharding)이 어렵기 때문에, 데이터 양이 급격히 증가하면 확장 비용이 높음
2. NoSQL:
   • 쓰기 성능의 제약:
     • NoSQL(예: MongoDB, Cassandra)은 쓰기 성능이 좋지만, 대량의 쓰기 작업에서 인덱싱 비용이 높음
   • 디스크 I/O 증가:
     • 대량 쓰기 작업 시 디스크 I/O가 병목이 되어 성능 저하를 초래할 수도

2. 읽기가 특정 시간에 몰리는 경우

문제점

1. 관계형 데이터베이스 (RDBMS):
   • 읽기 병목:
     • 복잡한 질의
     • join
   • 인덱스 비효율성:
     • 대규모 시계열 데이터에서 시간 기반 쿼리(예: WHERE timestamp BETWEEN ...)는 범위 검색이 많아져 인덱스 성능이 저하될 수 있습니다.
     • 인덱스를  검색하려는 모든 값에 걸 수 없음
     • 튜닝 한계
2. NoSQL:
   • 읽기 쿼리 제약:
     • 시계열 데이터를 읽을 때, 복잡한 필터링 및 집계 작업이 필요하면 NoSQL 시스템에서는 추가적인 애플리케이션 레벨의 처리가 필요
   • 읽기 집중 시 과부하:
     • MongoDB와 같은 NoSQL 시스템은 읽기 요청이 급증할 경우, 캐싱 및 클러스터 확장이 충분하지 않으면 병목이 발생할 수도

시계열 데이터베이스(TSDB)(예: InfluxDB, TimescaleDB)는 쓰기/읽기 최적화, TTL, 시간 기반 쿼리 등 시계열 특화 기능으로 적합

시계열 데이터베이스(TSDB)가 적합한 이유

1. 쓰기 최적화:
   • TSDB는 쓰기 작업을 빠르게 처리하도록 설계
   • 압축 기술: 데이터 크기를 줄이고 저장 효율을 높임.
   • Batch Writing: 쓰기 작업을 배치 처리로 최적화.
2. 읽기 최적화:
   • 시간 기반 쿼리 최적화: 타임스탬프 기반 필터링 및 집계가 빠르게 동작.
   • 전용 인덱스: 시계열 데이터를 효율적으로 검색하도록 설계된 고유 인덱스 구조.
     • 레이블(태그) 별로 인덱스
3. 자동 데이터 관리:
   • Retention Policy(TTL): 오래된 데이터를 자동으로 삭제하여 저장 공간을 관리.
   • Downsampling: 오래된 데이터를 요약 데이터로 변환(예: 1초 단위 -> 1시간 평균).
4. 확장성:
   • TSDB는 수평 및 수직 확장이 용이하며, 대량의 데이터를 처리하는 데 최적화됨.
5. 예: InfluxDB, TimescaleDB, Prometheus, OpenTSDB

풀 vs 푸시

• 풀: 지표수집기가 주기적으로 지표를 요청하여 데이터를 가져옴
  • 서비스 디스커버리를 사용하여 수집해야 할 서버정보와 메타 데이터를 관리
  • 지표 수집기가 서비스 디스커버리로부터 목록을 확보하여 http로 데이터를 가져옴
  • 지표 수집기도 여러대(서버풀)준비해야 할텐데 여러 지표 수집기가 같은 서버를 찌르지 않도록 consistent hash ring 구조로 담당 서버를 지정하면 특정 서버 지표는 항상 하나의 수집 서버가 처리함을 보장할 수  있다.
  • 프로메테우스
• 푸시: 서버기 지표 수집기를 호출하여 데이터 전송
  • 푸시 모델의 지표 수집기가 밀려드는 지표 데이터를 제 때 처리하지 못하면 일시적으로 버퍼(메모리/디스크 등)에 저장하여 재전송할 수도 있겠지만 서버가 동적으로 추가/삭제되는 과정에서 데이터가 소실될 수 있다.
  • 따라서 지표 수집기 클러스터 자체도 자동 규모 확장이 가능하게 구성하고 그 앞에 로드밸러서를 두는게 좋다.

카프카를 통한 규모 확장

• 시계열 데이터 베이스 앞에 카프카를 두어 디비가 죽어도 데이터가 소실되지 않게 함
• 지표의 태그/레이블에 따라 토픽/파티션으로 세분화 가능

집계(통계화) 시점

• 데이터 저장 전에 집계한다면 스트림 프로세싱 엔진이 필요할거고 저장양이 줄긴하지만 원본데이터를 저장하지 않으니 유연성이 좋지 않다
• 저장하고 조회 시 집계한다면 전체 대상으로 계산해야해서 속도가 느리다

질의 서비스

• 캐시 고려
• 질의 서비스를 안두고 바로 시계열 디비와 연동하는 경우도 있음

저장소

• 저장 용량 최적화 필요
• 데이터 인코딩 및 압축
• 다운 샘플링: 기간별 해상도를 낮춰서 보관
  • 예를 들어 2주는 원본 한달이내 1분단위로 집계한 데이터 1년 이내 1시간으로 집계한 데이터 등..(해상도를 낮춘다고 표현)
• cold storage: 저장 위치를 아애 옮겨버림 nas 같은 곳으로..

경보 시스템

• 경보 규칙을 설정파일로 저장하고 캐시화
• 규칙에 따라 질의 서비스 호출해서 계산하고 설정 임계값을 위반하면 경보 이벤트 생성
• 경보 저장소: 키-값 저장소; 모든 경보의 상태 저장; 알림이 적어도 한번은 전달되도록 보장
• 경보 이벤트는 카프카로
• 해당 메세지를 읽어 다양한 채널로 알림 전송

메시지 큐 사용 이유

• 컴포넌트 사이의 강한 결합 완화
• producer/consumer을 독립적으로 확장 가능
• 특정 컴포넌트 장애 발생해도 다른 컴포넌트는 작업 가능
• 비동기 통신을 통한 성능 개선

메시지큐 vs 이벤트 스트리밍 플랫폼

• 메세지 큐: rabbit mq
• 이벤트 스트리밍 플랫폼: 카프카
• 메세지큐 + 데이터 장기보관, 반복 소비, 스트리밍 기능 = 이벤트 스트리밍 플랫폼

큐?

• producer가 메시지를 큐에 보내고 consumer는 큐를 구독하고 구독한 메시지를 소비
• producer/consumer 는 모두 클라이언트고 서버 역할을 하는 것은 메세지 큐
• 일대일 모델
  • 메세지는 오직 한 소비자만 가져갈 수 있음; 소비되면 삭제됨
  • 한 큐에 여러 소비자가 붙으면 큐의 병렬처리
• 발행 구독 모델
  • 토픽: 고유한 이름을 가진; 메시지를 보내고 받을 때 토픽에 보내고 받음
  • 해당 토픽을 구독하는 모든 소비자에게 전달

메시지 큐가 서버인 이유

메시지 큐는 시스템의 중심에서 메시지를 저장하고 관리하며, 전달을 책임지는 역할을 하기 때문에 서버로 간주됩니다. 다음과 같은 이유가 있습니다:

(1) 중앙 관리 역할

메시지 큐는 모든 메시지를 중앙에서 관리합니다.

• Producer는 메시지를 큐에 넣기만 하고,
• Consumer는 큐에서 꺼내오기만 합니다.
  즉, 메시지의 저장, 전달, 보관 등 모든 복잡한 작업은 메시지 큐가 처리합니다. 이 중앙 관리 기능은 전형적인 서버의 역할입니다.

(2) 요청/응답 모델

• Producer는 메시지를 큐에 요청(Request)으로 전송합니다.
• Consumer는 큐에 요청(Request)을 보내 메시지를 가져옵니다.
• 메시지 큐는 이 요청들을 처리하고 응답(Response)하거나, 메시지를 전달하는 서버 역할을 수행합니다.

(3) 리소스 제공자

메시지 큐는 Producer와 Consumer 사이에서 리소스를 제공하는 역할을 합니다. 예를 들어:

• 메시지의 내구성(Durability)과 순서 보장(Order Guarantee)을 관리합니다.
• 특정 Consumer가 일시적으로 작동하지 않아도 메시지를 보관하여 이후에 전달합니다.
  Producer와 Consumer는 메시지 큐에 의존하여 이 서비스를 이용하므로 클라이언트로 간주됩니다.

Producer와 Consumer가 클라이언트인 이유

Producer와 Consumer는 메시지 큐를 사용하는 사용자로 동작하기 때문에 클라이언트로 간주됩니다.

(1) 요청을 보냄

• Producer는 메시지를 큐로 보내는 요청을 보냅니다.
• Consumer는 메시지를 큐에서 가져오라는 요청을 보냅니다.
  요청(Request)을 보내는 주체는 일반적으로 클라이언트로 간주됩니다.

(2) 큐에 의존

Producer와 Consumer는 메시지 큐가 없다면 서로 직접 통신해야 합니다. 그러나 메시지 큐를 사용함으로써:

• Producer는 큐에 메시지를 보내는 데만 집중합니다.
• Consumer는 큐에서 메시지를 가져오는 데만 집중합니다. 결국 이 둘은 큐가 제공하는 서비스(메시지 저장 및 전달)에 의존하는 클라이언트로 동작합니다.

토픽, 파티션, 브로커

• 메시지는 토픽에 보관
• 토픽에 보관되는 데이터 양이 많으면? 파티션 사용(샤딩 기법)
• 토픽을 여러 파티션으로 분할하여 메시지를 나눠 보냄
• 파티션은 메세지 큐 클러스터 내의 서버에 고르게 분산 배치
• 파티션을 유지하는 서버: 브로커
• 파티션을 브로커에 분산하여 높은 확장성 달성; 토픽 용량 확장 시 파티션 개수 증가
• 각 파티션은 FIFO 큐; 한 파티션 안에서는 순서 유지; 위치=offset
• 파티션 키; 같은 키를 가진 모든 메시지는 같은 파티션으로 없으면 무작위로 보내짐
• 소비자 그룹: 토픽을 구독하는 소비자가 여럿인 경우 각 구독자는 해당 토픽을 구성하는 파티션의 일부를 담당
  • 같은 그룹 내 소비자는 메시지를 병렬로 소비, 그러면 같은 파티션 안의 메세지를 순서대로 소비할 수는 없다
  • 어떤 파티션은 한 그룹 안에서 한 소비자만 읽게 하여 순서 보장
  • 그룹 내 소비자의 수가 구독하는 토픽의 파티션 수보다 크면 어떤 소비자는 해당 토픽에서 데이터를 읽을 수 없음
  • 처리량을 늘리려면 소비자를 추가

데이터를 저장하는 큐를..

• 디비?
  • 읽기 쓰기가 대규모로 빈번하게는 부적합
• 쓰기 우선 로그(write ahead log WAL)?
  • 지속성
  • 읽기/쓰기 모두 순차적 -> 디스크
  • 파일 하나에 계속 쓰면 관리가 힘드므로 여러 세그먼트로 분리

생산자 작업 흐름

producer는 메시지를 producer 내부의 라우팅 계층에 보내 어떤 브로커(의 파티션)로 보내야하는지 파악하고 전송할 메세지를 버퍼 메모리에 잠시 보관했다가 목적지로 일괄 전송(배치 양을 늘리면 응답 속도가 느려짐)하여 대역폭을 넓힌다. 리더 브로커가 받아서 저장하고 replica가 일정 수 만들어지면 데이터가 소비 가능해지며 producer에게 완료회신을 보낸다.

소비자 작업 흐름

consumer는 특정 파티션의 오프셋의 위치에서부터 이벤트를 묶어 가져온다.

푸시 vs 풀

• 푸시: 브로커가 데이터를 consumer에게 보냄
  • 낮은 지연: 바로 보냄 하지만 consumer 속도가 느리면 부하가 걸림
• 풀: consumer가 브로커에게 가져감
  • 소비 속도는 consumer가 알아서 조절. 만약 큐가 쌓이면 소비자를 추가하거나 기다리거나
  • 다음 오프셋부터 한 번에 가져가 배치 처리 가능
  • 단, 데이터가 없어도 시도 -> 롱 폴링으로 consumer 통신 횟수 감소 가능(가져갈 게 없어도 일정시간 기다림)

소비자 그룹(Consumer Group)이란?

• 소비자 그룹(Consumer Group)은 Kafka에서 메시지를 읽어가는 Consumer의 논리적인 묶음입니다.
• 같은 그룹에 속한 Consumer들은 특정 토픽의 파티션을 분배받아 메시지를 처리합니다.
• 소비자 그룹 ID를 기준으로 그룹이 구분됩니다.

특징:

1. 같은 그룹 내의 Consumer는 같은 메시지를 읽지 않습니다.
   • 파티션 하나는 소비자 그룹 내에서 단일 Consumer만 처리합니다.
   • 이를 통해 메시지 처리가 병렬로 이루어집니다.
2. 다른 소비자 그룹은 독립적으로 동작합니다.
   • 서로 다른 소비자 그룹은 동일한 메시지를 중복으로 처리할 수 있습니다.
   • 예: groupA와 groupB는 동일한 토픽을 구독할 수 있으며, 각각 모든 메시지를 독립적으로 처리합니다.

브로커와 소비자 그룹의 관계

Kafka 브로커와 소비자 그룹은 메시지의 생산(Producer)부터 소비(Consumer)까지의 흐름에서 중요한 관계를 형성합니다.

(1) 브로커는 메시지를 저장하고 제공

• 브로커는 토픽과 파티션을 기반으로 메시지를 저장하고 관리합니다.
• Producer는 메시지를 브로커에 전송하고, 브로커는 이를 적절한 파티션에 저장합니다.

(2) 소비자 그룹은 메시지를 병렬로 처리

• 각 소비자 그룹은 특정 토픽의 메시지를 구독(subscribe)합니다.
• 그룹 내의 Consumer들은 토픽의 파티션을 나누어 처리합니다.
  • 예: 토픽에 6개의 파티션이 있고, 소비자 그룹 내에 Consumer가 3명 있으면 각 Consumer는 2개의 파티션을 담당합니다.

(3) 파티션 할당 전략

• Kafka는 소비자 그룹 내에서 파티션을 동적으로 할당합니다.
  • Round-Robin 또는 Range와 같은 기본 전략이 사용되며, 커스텀 전략도 구현 가능합니다.
• 새로운 Consumer가 그룹에 추가되거나 제거되면 리밸런싱(Rebalancing)이 발생하여 파티션이 다시 분배됩니다.
  • consumer rebalancing: 코디네이터(소비자들과 통신하는 브로커 노드; heatbeat, offset 정보 관리) 필요

(4) 소비자 오프셋 관리

• 소비자 그룹은 오프셋(Offset)을 관리하여 메시지를 어디까지 처리했는지 추적합니다.
  • Kafka는 이 오프셋 정보를 브로커 내부의 __consumer_offsets라는 내부 토픽에 저장합니다.
  • 이를 통해 Consumer는 중단 후에도 이어서 처리할 수 있습니다.

주키퍼

• 브로커의 상태 저장소
  • 각 소비자 그룹/소비자의 오프셋
  • 읽기와 쓰기가 잦고 데이터 일관성이 중요
• 토픽 설정, 파티션 수, 메시지 보관 기간 등의 메타 데이터 저장소
  • 자주 변경되지 않고 일관성 중요
• 분산 시스템의 key value 저장소

선정된 리더가(소비자 그룹이건, 파티션의 리더이건) replica 계획, 파티션 배치 계획 등을 정해서 코디네이터로 보내주면 코디네이터가 그걸 전파하는 방식

사본 동기화

ISR(in sync replicas) 리더와 동기화된 사본. 리더는 항상 ISR

몇 개가 동기화될 때 까지 기다릴지 설정 가능; 성능과 영속성을 고려해야 함

• ACK = all : 전체가 다 동기화 될 때까지 기다림, 영속성 중요할 경우
• ACK = 1 : 리더가 저장하면 다음으로. 응답 지연은 개선되나 리더가 장애 생기면 복제가 안될 수 있어 소실됨
• ACK = 0 : 생산자는 메시지만 던지고 다음으로. 재시도도 하지 않음. 메세지 손실을 감수할 때

메세지 전달 방식

• 최대 한 번
  • 메시지가 소실되어도 재전달하지 않음(ack = 0)
  • consumer가 메시지를 읽고 처리하기 전에 오프셋부터 갱신(갱신하고 죽으면 메시지는 다시 소비될 수 없음)
• 최소 한 번
  • acl = 0; ack = all 메시지가 브로커에게 전달되었음을 반드시 확인
  • 소비자가 데이터를 성공적으로 처리한 뒤에 오프셋 갱신(갱신하지 못하고 죽으면 중복처리)
  • 멱등성 중요(고유 키 중복처리 ㄴㄴ)
• 정확히 한 번
  • 복잡

메세지 필터링

주문 토픽에 발행하는데 지불 시스템이 가져간다면? 일부만 필요

지불 토픽을 별도로 만들어서 주문 데이터르 중복 발행?

생산자와 소비자 결합이 높아져서 ㄴㄴ

-> 필터링으로 해결

다 읽고 필요 없는 걸 버리자니 성능이 저하

브로커카(메시지 큐가) 많은 일을 하면 안 된다(데이터 추출 등)

메시지의 메타 데이터에 태그를 두어 태그를 필터링하도록 하고 태그를 구독..

2024.09.25 - [서버 세팅 & tool/rabbitmq] - [rabbitMq] 하나의 메세지를 여러 소비자에게 동등하게 보낼 때.. 그럼 카프카는?