Ray`s Tech Lab

※ 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2권 - 챕터 4의 내용과 개인적으로 추가 공부한 내용들을 정리한 글입니다.

들어가며

현대적인 소프트웨어 아키텍쳐들은 각자만의 인터페이스를 갖고 분리된 여러 컴포넌트들로 구성됩니다. 메시지큐는 이 컴포넌트 사이에서의 통신을 담당하는 컴포넌트로, 각 컴포넌트들이 기존에 sync 방식으로 통신하던 것을 async 방식으로 쉽게 통신할 수 있도록 돕는 역할을 합니다. 메시지 큐 사용 시 다음과 같은 이점들이 있습니다.

1. 결합도 완화 : 각 컴포넌트 사이에 통신을 담당하는 컴포넌트를 두는 것이므로, 기존 컴포넌트 간의 결합도가 낮아지게 됩니다. 이를 통해 좀 더 유연한 설계 및 각 컴포넌트의 독립적인 갱신이 가능합니다.
2. 확장성 증가 : 메시지 큐를 사용하는 컴포넌트는 데이터를 생산하는 생산자(producer)와 소비자(consumer)로 분류 가능합니다. 결합도가 완화된 것을 통해, 시스템 부하에 맞춰 각 컴포넌트의 규모를 독립적으로 늘릴 수 있습니다. (트래픽이 더 몰려 더 많은 데이터가 생산되면 소비자를 증설 등)
3. 가용성 개선 : 특정 컴포넌트에 장애가 생겨도 다른 컴포넌트는 메시지 큐와 상호작용 가능합니다.
4. 성능 개선 : 메시지 큐는 각 컴포넌트들이 async 통신을 쉽게 할 수 있도록 합니다. 생산자는 소비자가 어떻게 처리하든 메시지큐에 데이터를 밀어넣어주면 되고, 소비자는 메시지큐에 있는 데이터를 긁어가서 처리하면 됩니다. 이를 통해 sync 방식에서 생기던 문제점들(ex : 자원을 비효율적으로 사용 등)을 개선할 수 있습니다

물론 장점들만 있는 건 아닙니다. 메시지 큐라는 컴포넌트를 추가 운영하면서 생기는 공수도 있을 것이고, 컴포넌트 간의 통신이 메시지 큐라는 컴포넌트를 거쳐 발생하므로 네트워크 문제로 인한 추가 지연이 발생 가능한 것 등의 단점들도 있습니다. 그럼에도 메시지큐는 기존 컴포넌트들간의 결합도를 낮추면서 얻을 수 있는 이점들이 많기 때문에 많은 시스템에서 사용하는 컴포넌트이기도 합니다(해외에서는 메시지큐를 이미 성숙된 기술이라고도 표현합니다).

메시지큐는 대표적으로 RabbitMQ등의 서비스가 있으며 Apache Kafka 등의 이벤트 브로커도 많이 쓰입니다. 이 글에서는 분산 메시지 큐를 설계하는 방법과 필요한 지식 등을 소개하겠습니다.

※ 참고 : 메시지 큐 vs 메시지 브로커 vs 이벤트 브로커

1) 메시지 큐

• 컴포넌트 간의 메시지를 전달하기 위한 컴포넌트
• 메시지를 저장하는 역할

2) 메시지 브로커

• 메시지 큐의 기능을 포함
• 추가적으로 메시지 라우팅(pub/sub 패턴 등을 통해..), 메시지 변환 등도 해줌

• 메시지 브로커의 기능을 포함
• 추가적으로 메시지(이벤트) 보관 등의 기능을 할 수 있음

※ 설계 범위

이 설계에서 메시지는 텍스트만 가정하며, KB수준으로 가정합니다.

1) 기능적 요구사항

• 생산자는 메시지 큐에 메시지를 보낼 수 있어야 합니다.
• 소비자는 메시지 큐에서 메시지를 소비할 수 있어야 합니다.
• 메시지는 생산된 순서대로 소비자에게 전달되어야 합니다.
• 메시지 큐에 넣어진 메시지는 설정에 따라 소비자가 반복적으로 소비할 수도 있고, 한 번만 소비할 수도 있어야 합니다.
• 메시지는 2주까지만 보관합니다.
• 메시지 전달은 최소 한 번, 최대 한 번, 정확히 한 번 중에 설정 가능해야 합니다.

2) 비기능적 요구사항

• 높은 대역폭 제공 / 낮은 전송 지연 중 하나를 설정할 수 있어야 합니다.
• 메시지 양이 급증해도 처리할 수 있도록 확장성있는 설계가 필요합니다.
• 데이터는 디스크에 지속적으로 보관해야 하며 여러 노드에 복제되어야 합니다.

참고) 아래에서 좀 더 설명하겠지만, 높은 대역폭을 제공하려면 메시지를 버퍼링하다가 일괄로 처리해야 하나 이는 메시지들이 즉시 전달되는게 아니므로 전송 지연이 높아지게 되므로 높은 대역폭과 낮은 전송 지연을 만족시키는 것은 힘듭니다.

메시지큐의 구성 요소와 개략적인 설계

메시지 큐의 핵심 구성 요소와 간략한 흐름도는 다음과 같습니다.

1. 생산자가 메시지를 메시지큐에 발행
2. 소비자는 큐를 구독하고 있고, 구독한 메시지를 소비하게 됨

이를 기반으로 한 메시지 모델들은 다음과 같습니다.

메시지 모델

1) 일대일 모델

메시지를 소비하는 소비자가 여러 명일 수 있는데, 일대일 모델은 생산자가 메시지 큐에 발행한 메시지는 오직 한 소비자만 가져갈 수 있는 모델을 말합니다.

2) 발행-구독 모델

관련있는 메시지들을 토픽이라는 논리적인 그룹으로 묶어 메시지들을 주제별로 관리하게 한 다음, 이 토픽으로 메시지를 보내고 받는 모델입니다. 토픽에 전달된 메시지는 해당 토픽을 구독하는 모든 구독자들에게 전달됩니다. 

메시지 큐 컴포넌트의 구성 요소들은 다음과 같습니다.

토픽, 파티션, 브로커

• 토픽 : 메시지 큐에서 데이터를 주고받는 주제 또는 채널의 개념으로, 관련있는 메시지들을 토픽으로 묶어 주제별로 관리합니다.
• 파티션 : 토픽을 샤딩하여 만든 분할된 각 단위를 파티션이라 부릅니다. 토픽의 확장성과 병렬성을 위해 사용하며, 덕분에 토픽에 데이터가 몰려서 부하가 커지는 것을 방지할 수 있습니다. 파티션은 다수의 메시지 큐 컴포넌트들이 구성하는 클러스터에 고르게 분산 배치됩니다.
• 브로커 : 파티션들을 유지하는, 즉 파티션들이 있는 서버를 브로커라고 부릅니다. 

생산자가 보내는 메시지는 보내질 토픽의 파티션 중 하나로 보내지며, 메시지에 키 값을 설정하여 같은 키 값을 가진 메시지들은 같은 파티션으로만 보내지도록 설정할 수도 있습니다.

같은 토픽을 구독하는 소비자가 여러 명이면 각 구독자는 해당 토픽의 파티션들을 분담해서 처리하게 됩니다. 즉 이 경우 모든 소비자들에 구독한 토픽에 발행되는 모든 메시지를 처리하는 게 아니라 서로가 분담해서 처리하는 것으로 이해할 수 있습니다. 이 소비자들을 소비자 그룹이라고 부릅니다.

소비자 그룹

소비자 그룹의 소비자들은 앞서 설명했듯 특정 토픽의 메시지들을 서로 분담해서 처리합니다(즉 서로 협력하는 구조). 같은 토픽에 여러 소비자 그룹이 있을 수 있고, 하나의 소비자 그룹이 여러 토픽을 처리하고 있을 수도 있습니다.

ex 1) 주문 토픽을 구독하면서 결제를 담당하는 그룹과 재고 차감을 담당하는 그룹이 있을 수 있습니다.

ex 2) 사용자 활동 토픽, 주문 토픽를 둘 다 구독하고 있는 분석용 그룹이 있을 수 있습니다.

또한 다음 그림과 같이 특정 소비자 그룹 내의 소비자들이 같은 파티션에 붙으면 어떻게 될지도 생각해볼 필요가 있습니다. 

이 경우, 같은 파티션에 있는 메시지들을 두 개 이상의 소비자가 병렬로 읽게 되므로 대역폭 측면에선 좋겠으나 메시지를 순서대로 소비하는 것이 보장되지 않습니다(병렬처리이므로 순서보장이 어려움). 이 문제는 직관적으로 "한 파티션은 한 소비자 그룹에선 한 소비자만 담당하게 하기"로 해소가 가능합니다. 다만 파티션 수 < 소비자 수 일 때 일부 소비자들은 유휴 현상이 발생 가능하다는 단점이 있습니다. 

개략적 설계

설명드린 것들을 바탕으로, 분산 메시지 큐 시스템을 개략적으로 다음처럼 설계 가능합니다.

• 생산자 : 메시지를 특정 토픽으로 보내는 역할
• 소비자(소비자 그룹) : 토픽을 구독하고 발행된 메시지를 소비하는 역할
• 브로커 : 토픽을 샤딩(즉 분할)한 단위인 파티션들이 있는 서버
• 상태 저장소 : 각 브로커별로 갖고 있는 파티션의 상태 정보들(각 소비자 그룹이 마지막으로 가져간 메시지의 오프셋 등)을 저장
• 메타데이터 저장소 : 토픽 설정과 속성 정보들(토픽별 파티션 수, 메시지 보관 기간 등).. 즉 브로커들이 공통적으로 참조하는 메타데이터들을 저장
• 조정 서비스(Coordination Service) : 브로커들의 상태 모니터링, 리더 선출(분산 시스템들이 master - slave 구조일 때 master가 다운되면 누가 master가 될지를 선출하는 것) 등을 담당

상세 설계

파티션(데이터 저장소) 설계

1) 파티션에서의 메시지 저장 방식

메시지들은 토픽에 저장되며, 토픽은 파티션이라는 단위로 샤딩된다고 말씀드렸습니다. 이 파티션에 데이터를 어떻게 저장해볼지를 생각해봐야 하는데요, 대표적으로 DB에 저장하는 것과 파일 형태로 디스크에 저장하는 방식을 생각해볼 수 있습니다. 분산 메시지 큐는 시스템 특성 상 메시지라는 데이터를 write(생산)하고 read(소비)하는 연산이 빈번하게 발생하므로 DB에 저장해 관리하는 것은 한계가 있습니다(대규모의 읽기와 쓰기가 모두 능한 DB는 설계가 어려움). 근데 메시지를 생산하고 소비하는 과정을 보면 읽기/쓰기 모두 메시지에 대한 액세스 패턴이 순차적이므로, 로그파일 형태로 디스크에 저장하도록 설계하면 좋은 효과를 기대할 수 있습니다.

2) 파티션 복제 (파티션 사본)

또한 파티션들을 복제하여 높은 가용성을 제공하도록 할 수 있습니다. 토픽을 여러 파티션으로 분할한 뒤, 각 브로터들이 다음과 같이 파티션들의 사본도 갖도록 구성할 수 있습니다.

DB도 master에만 write를 하면 사본들로 복제가 되는 것처럼, 생산자가 메시지를 발행할 때도 1번 파티션에 발행해야 한다면 리더역할을 하는 파티션에 발행하도록 한 뒤  사본 파티션들은 리더에서 지속적으로 메시지들을 가져와 동기화하도록 구성할 수 있습니다. 이때 파티션 별로 사본을 어떻게 분산할 지에 대해 기술하는 것을 사본 분산 계획(replica distribution plan)이라 부르며 다음과 같이 요약할 수 있습니다.

• 주문 토픽의 1번 파티션 사본 분산 계획 : 파티션 총 2개. 리더는 1번 브로커, 사본은 2번 브로커에 배치
• 주문 토픽의 2번 파티션 사본 분산 계획 : 파티션 총 2개. 리더는 2번 브로커, 사본은 1번 브로커에 배치

파티션의 리더는 조정 서비스를 통해 브로커 노드 중 하나가 선출되도록 합니다. 해당 브로커가 사본 분산 계획을 만들고 메타데이터 저장소로 저장하도록 합니다. (조정 서비스에 대한 내용은 밑에서 소개하겠습니다).

3) 파티션 사본 동기화

DB에서 복제본을 구성할 때, 동기식 / 비동기식 / 반동기식으로 복제 방법을 구성할 수 있습니다. 동기식은 master에 데이터가 쓰인 후 복제본까지 데이터가 쓰인 후에 ack를 보내는 거고, 비동기는 master노드에만 데이터를 쓴 뒤 ack를 보내는 거고, 반동기는 master에 데이터를 쓴 후 복제본으로 데이터 변경에 대한 로그 작성이 끝난 것만 확인한 뒤 ack를 보내는 것을 의미합니다. 앞서 설명한 것처럼 파티션의 동기화도 리더 파티션에 발행된 메시지를 사본 파티션들이 가져가게끔 구성하는데, 메시지 발행에 대한 ack를 어떻게 보내는지 설정해주는 것을 통해 영속성의 정도를 조절할 수 있습니다.

이 때 ISR(In-Sync Replicas)이란 개념이 사용됩니다. 리더 파티션과 동기화된 사본 파티션을 일컫는 말이며, 이때 "동기화됐다"의 기준은 토픽 설정에 따라 달라집니다. 리더 파티션의 메시지 개수와 사본 파티션의 메시지 개수는 차이가 날 수도 있는데, 설정된 특정 개수 이하로 차이난다면 "동기화됐다"라고 취급할 수 있습니다. 만약 메시지 차이가 2개 이하면 ISR로 취급한다고 할 경우, 다음 상황에선 사본 1과 2가 ISR입니다.

리더 파티션에 새로운 메시지가 발행된 후, ISR 상태인 파티션들에게까지 메시지가 전달된 뒤 ack를 보내는 것을 ACK=all이라 합니다. 리더 파티션에 메시지가 발행된 후(즉 메시지가 저장된 후) ack를 보내면 ACK=1, 리더 파티션에 메시지를 전달한 후 ack를 보내는 것을 ACK=0(즉 메시지가 저장됐는지는 관심사가 아님)이라고 합니다. 설정이 높을수록 영속성을 높게 가져가는 것이고, 설정이 낮을수록 낮은 지연을 기대할 수 있습니다.

생산자, 소비자 작업 흐름 설계 및 일괄 처리

보통 반복되는 작업을 일괄 처리(batching)하면 네트워크 I/O 또는 디스크 I/O를 줄이게 되며 성능을 개선시킬 수 있습니다(다만 데이터들을 모았다가 한 번에 처리하는 것이므로 개별 데이터의 지연은 높아질 수 있음). 분산 메시지 큐에서는 다음과 같이 생산자와 소비자의 작업 흐름을 구성하며 일괄 처리 도입도 설계해볼 수 있습니다.

1) 생산자에서의 작업 흐름 및 일괄 처리 설계

우선 일괄 처리를 배제하고 생각해보겠습니다. 생산자가 새 메시지를 발행할 경우 리더 파티션이 있는 브로커로 메시지를 보내야 합니다. 이때 해당 파티션을 유지하는 브로커로 연결하기 위해 별도의 라우팅용 컴포넌트를 두는 방안을 고려할 수 있으나, 다음과 같이 라우팅 계층을 생산자 내부로 편입시키는 구조를 설계해볼 수 있습니다.

라우팅 컴포넌트를 별도로 두면 그에 따른 네트워크 지연을 감수해야 하지만, 이렇게하면 거치는 컴포넌트가 하나 더 적으니 전송 지연이 줄어드는 효과를 줍니다. 또한 생산자 입장에서는 전송할 메시지를 버퍼에 모으다 목적지로 일괄 전송하게끔 처리하여 대역폭을 높일 수 있다는 장점을 가져올 수 있습니다.

2) 소비자에서의 작업 흐름 및 일괄 처리 설계

소비자의 작업 흐름 설계 시, 데이터를 Push / Pull 중 어떤 방식으로 가져올 것인지를 고려해야 합니다.

• Push : 브로커에서 소비자로 직접 데이터를 밀어주는 방식. 메시지가 발행되자마자 소비자에게 밀어줄 수 있으니 지연이 낮다는 장점이 있으나, 데이터 공급의 주도권이 브로커에게 있는 만큼 소비자가 감당 가능한 양 이상으로 데이터를 넣어줄 수 있는 단점이 있습니다.
• Pull : 소비자가 브로커에서 직접 데이터를 가져오는 방식. 데이터 공급의 주도권이 소비자에게 있으니 자신의 속도에 맞게 브로커로부터 데이터를 가져올 수 있고, 일괄 처리에 적합하다는 장점이 있습니다. 반면 브로커에 메시지가 없어도 소비자가 데이터를 가져가려 시도할 수 있으며 이는 컴퓨팅 자원의 낭비(하지 않아도 되는데 하는 것이므로)가 된다는 단점이 있습니다.

참고로 레디스 pub / sub은 Push 방식을, kafka는 Pull 방식을 사용합니다. Pull 방식 사용 시 컴퓨팅 자원이 낭비될 수 있는 부분은 롱 폴링(서버에 요청을 보내고 서버가 새로운 데이터가 있을 때까지 응답을 지연시키는 방식)을 통해 어느 정도 해소가 가능해 대부분의 메시지 큐는 Pull 방식을 많이 지원합니다. 해당 방식의 작업 흐름을 도식화하면 다음과 같습니다.

소비자 입장에서는 내가 어느 파티션에 붙어서 데이터를 읽고 써야 할지를 알아야 하는데, 이걸 알려주는 역할을 해당 소비자 그룹의 코디네이터 브로커가 해주며 소비자 그룹 이름의 해시값에 매핑되는 브로커가 담당합니다. 즉 서로 다른 소비자 그룹에 대해 같은 브로커가 두 그룹의 코디네이터 역할을 할 수도 아닐 수도 있습니다. 코디네이터 브로커를 통해 어떤 파티션에 붙어야 하는지를 알게 됐다면, 해당 파티션의 오프셋으로부터 메시지를 묶어서 가져오는 식으로 일괄 처리를 설계할 수 있습니다.

참고로 소비자 그룹의 코디네이터 브로커는 신규 소비자에 대한 파티션 지정 외에도 그룹 내 소비자들의 상태 감시(heart beat를 통해), 소비자 탈퇴 및 장애 발생 시 파티션 재분배 등의 역할도 담당합니다.

상태 저장소 & 메타데이터 저장소 & 조정 서비스 설계

브로커가 유저하는 타피션에 대한 상태 정보를 관리하는 저장소와 토픽의 메타데이터를 관리하는 저장소, 그리고 조정 서비스를 어떻게 설계할 지도 살펴봐야 합니다. 이때 Apache Zookeeper라는 서비스를 사용해볼 수 있습니다. 분산 메시지 큐를 비롯한 여러 분산 시스템에선 각 시스템들의 상태를 모니터링할 수 있는 환경, 범용적으로 사용 가능한 중앙 집중식 데이터 저장소가 등이 필요합니다. 물론 이를 직접 구현할 수 있겠으나, Apache에서 분산 시스템들이 공통적으로 가지는 요구사항들을 해결하기 위해 Zookeeper라는 서비스를 개발했다고 이해할 수 있습니다. 대표적으로 다음 기능들을 제공합니다.

1. 시스템들이 공유하는 공유 상태의 저장 & 관리
2. 각 시스템 상태 모니터링
3. 리더 선출 (분산 시스템들이 master - slave 구조일 때 leader가 다운되면 누가 leader가 될지를 선출하는 거. 이거 위해서 주키퍼는 노드 수를 홀수로 맞춘다고 합니다)

이를 통해 상태 저장소, 메타데이터 저장소, 조정 서비스의 역할을 Zookeeper가 담당하면서 다음 형태의 설계가 가능합니다.

※ 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2권 - 챕터 3을 읽고 정리한 글입니다.

들어가며

위치 기반 서비스 설계에 대한 마지막 장으로, 구글 맵처럼 지도 탐색이나 경로 안내 등이 가능한 웹 기반의 지도 서비스를 설계해봅니다. 지도 이미지를 어떤 식으로 보여주도록 설계할 수 있는지, 경로 안내를 어떤 식으로 보여주도록 설계할 수 있는지 등에 대해 살펴보겠습니다. 

다음과 같은 기능적 요구사항을 가정합니다.

• 주기적으로 사용자의 현재 위치를 갱신시킬 수 있어야 합니다.
• 출발지와 목적지가 주어졌을 때 경로 안내를 할 수 있어야 합니다.
• 지도 표시를 할 수 있어야 하며, 사업장들의 위치나 사진은 표시하지 않아도 됩니다.

다음과 같은 비기능적 요구사항도 가정합니다.

• 사용자에게 잘못된 경로를 안내하면 안 됩니다.
• 클라이언트는 가능한 한 최소한의 데이터와 배터리를 사용해야 합니다.
• 일반적으로 널리 통용되는 가용성과 확정성을 갖춰야 합니다.

개략적인 규모 추정

다음과 같이 가정합니다.

1. 일간 활성 사용자(DAU) : 10억 명
2. 일별 경로 안내 기능 사용 시간 : 50억 분 (각 사용자가 주당 35분 이 기능 사용)
3. QPS : 20만으로 가정 (경로 안내 기능 사용 중에 사용자 위치 갱신)
4. 최대 QPS :평균치의 5배 = 100만으로 가정

그리고 기본적으로 다음 4가지의 데이터를 보유한 상태로 시작해야 합니다.

1. 세계 지도 이미지 : 하나의 커다란 이미지를 표시하는 대신 작은 타일들로 쪼갠 뒤 클라이언트는 필요한 영역의 타일들만 이어붙여 보도록 할 수 있습니다. 확대 수준에 따라 이미지 세트를 여러 개 준비해야 하며, 여기서는 총 100PB가 소요된다고 가정합니다.
2. 메타데이터 : 각 지도 이미지들의 메타데이터로, 크기가 아주 작으므로 신경쓰지 않아도 됩니다.
3. 도로 데이터 : 경로 안내에 사용되며 수 TB 수준의 raw data를 미리 확보해 둔 상태로 가정합니다. 경로 안내를 위해 그래프 형태의 자료구조로 변환할 필요가 있으나 변환 결과의 용량도 비슷하다고 유추할 수 있습니다.
4. 위도 경도 페어 : 책에는 안 나와있으나.. 경로 안내를 위해 출발지 목적지를 위도 경도 페어로 바꿔야 하는데 이 데이터들을 지오코딩DB에 저장합니다. 하나의 레코드에 66Byte가 든다고 가정(주소 50, 위도 8, 경도 8)하고 전 세계의 주소를 20억 개(추정..)로 한다면 러프하게 132GB 정도의 용량이 필요합니다.

개략적인 설계안 제시

이 시스템은 위치 갱신 기능, 도로 데이터를 통한 경로 안내 기능, 세계 지도 이미지를 통한 지도 표시 기능을 제공해야 합니다. 개략적으로 다음과 같은 설계안을 제시할 수 있습니다.

1) 위치 서비스의 개략적 설계

사용자의 위치를 기록하는 역할을 담당합니다. 클라이언트가 t초 간격으로 자기 위치를 전송하게 할 수 있으며, 해당 데이터 스트림을 활용해 실시간 교통 상황 감지(정체되는 구간 분석 등), 사용자 행동 양태 분석 등에 활용 가능합니다.

그렇다고 사용자 위치가 바뀔 때마다 서버로 위치 기록 요청을 보내면 부하가 상당합니다(책에선 하루에 50억 분을 경로 안내에 사용한다고 말하며, 그 시간 동안 위치 기록이 이루어집니다). 이때 클라이언트가 위치 변경을 15초 정도 버퍼링하다가 일괄로 위치 기록을 요청하는 식으로 구현하면 부하를 크게 줄일 수 있습니다. 그러나 여전히 부하가 크고 특히 쓰기 연산이 많이 일어날 것이므로, 쓰기 성능이 탁월(메모리에 데이터를 모으다가 한 번에 디스크로 쓰는 방식을 통해 디스크 I/O가 적음)한 카산드라DB를 사용 가능합니다. 

2) 경로 안내 서비스의 개략적 설계

출발지에서 목적지로 가는 빠른 경로를 찾아주는 역할을 합니다. 문자열 주소로 주어지는 목적지와 출발지를 각각 알맞은 위도 경도 페어로 바꾸고(이를 지오코딩이라 함), 이를 통해 목적지까지 가는 경로를 찾아 사용자에게 반환합니다.

지오코딩용 DB는 읽기 연산 위주의 DB이고, 각 주소에는 하나의 위도 경도 페어만 대응되므로 레디스 등의 인메모리 키-밸류 DB를 사용하는 것이 성능 차원에서 유리합니다. 개략적 규모 추정에서 살펴봤듯 132GB의 데이터를 담고 있어야 하므로, 샤딩을 통한 데이터 분배를 고려할 수 있습니다.

앞서 설명했듯 도로 데이터는 수 TB를 raw data로 가지고 있다고 가정하고 있으므로 이를 그래프 형태의 자료구조로 변환하여 경로 안내에 사용해야 합니다. 그러나 전세계 도로망을 하나의 그래프로 표현하면 메모리 + 성능 차원에서 비효율적이므로 여러 그래프로 분리한 다음 필요한 그래프만 가져와서 연산하는 것이 효율적입니다. 이를 위해 2차원 공간을 여러 격자로 나누고(지오해싱 등 사용 가능), 각 격자별로 그래프를 관리하게 할 수 있습니다. 또한 각 격자(타일)들이 도로로 연결된 다른 타일에 대한 참조를 가지게 하고, 효과적인 경로 안내를 위해 계층적으로 타일을 구성시킬 수 있습니다. 참고로 이런 그래프 데이터는 메모리에 인접 리스트 형태로 두는 것이 일반적이나 이 시스템에선 수 TB 수준으로 양이 상당하므로, S3같은 객체 저장소에 두고 캐싱을 활용하게 하는 것이 좋습니다.

3) 지도 표시의 개략적 설계

개략적인 규모 추정에서 언급했듯이 지도 이미지는 총 100PB가 존재하므로, 이를 클라이언트가 다 가지게 한 뒤에 필요한 부분만 너희가 알아서 렌더링해서 보라고 하는 것은 실용적이지 않습니다. 클라이언트가 보고 있는 위치와 확대 수준에 따라 필요한 영역의 이미지만 가져오는 접근법이 실용적입니다. 이때 미리 지도 타일들을 만들어 저장해두고 필요한 영역의 타일 집합들을 요청(지오해싱 등을 활용)해서 해당 타일들을 받아오도록 할 수 있습니다. 

지도 이미지의 양이 상당하고 이 서비스는 글로벌 서비스를 가정(DAU가 10억)하므로, CDN을 통해 지도 이미지를 서비스하도록 구성할 수 있습니다. CDN 사용은 사용자들이 자신과 가까운 곳으로부터 컨텐츠를 받아볼 수 있으므로 지연속도가 빨라진다는 장점 등이 있으며, 다음 순서대로 동작하게 됩니다.

1. 클라이언트가 지도 타일 요청을 CDN에 보냄
2. 해당 이미지가 CDN을 통해 서비스된 적 없다면 지정된 원본 서버에서 해당 이미지를 가져와서 캐싱하고 사용자에게 반환
3. CDN을 통해 서비스된 적 있다면 바로 사용자에게 반환

또한 잠깐 말했듯이 지도 이미지 요청 시 지오해시 값을 계산하여 요청할 수 있는데, 이때 클라이언트가 직접 지오해시를 계산하는 방법을 사용한다면 여러 클라이언트(웹, 앱 등)를 따로 관리해야 하는 불편함이 생길 수 있습니다. 따라서 지오해시 값을 계산하는 서비스를  별도로 분리하면 좀 더 유연성을 가져갈 수 있습니다.

상세 설계

1) 위치 서비스의 상세 설계

앞서 살펴봤듯 쓰기 연산이 많이 일어나는 서비스이므로 카산드라같이 쓰기 성능에 좋은 DB를 고려할 수 있습니다. 카산드라는 키-밸류 데이터베이스이므로 (사용자 식별자, 위치 변경 타임스탬프)를 키로, 위도 경도 페어를 밸류로 기록하게끔 설계할 수 있습니다. 이때 사용자 식별자를 파티션 키(데이터를 어떤 노드에 저장할지 결정하는 데 사용)로 설정하고 타임스탬프를 클러스터링 키(동일한 파티션 내에서 데이터를 정렬하는 데 사용)로 설정한다면 특정 사용자의 특정 기간 내 위치를 효율적으로 읽도록 할 수 있습니다.

사용자 위치를 DB에 기록하는 것과 별개로, 카프카같은 데이터 스트리밍 플랫폼을 통해 실시간 교통 상황 서비스 등의 개별 서비스로 위치 데이터 스트림을 전달하도록 설계할 수 있습니다.

2) 경로 안내 서비스의 상세 설계

개략적인 설계에서 좀 더 세분화하여 다음과 같이 여러 역할을 가진 컴포넌트들로 설계할 수 있습니다.

경로 안내 서비스가 지오코딩 서비스를 호출하여 출발지와 목적지의 위도 경도 페어를 가져온 뒤 경로 계획 서비스를 호출하게 하고, 경로 계획 서비스는 현재 교통 상황이나 도로 상황에 입각해 이동 시간 측면에서 가장 최적화된 경로를 안내하도록 합니다.

a) 최단 경로 서비스

출발지와 목적지의 위도 경도 페어와 객체 저장소에 저장된 경로 안내 타일들을 활용해 특정 개수만큼의 최단 경로들을 반환하게 합니다. 즉 교통 상황은 고려 대상이 아닙니다. 경로 안내 타일에 쓰이는 그래프 데이터는 거의 정적인 데이터이므로 캐시를 적극 활용하는 것도 고려할 수 있습니다. 

b) 예상 도착 시간 서비스

최단 경로 서비스가 반환한 경로 목록들에 대한 소요 시간 추정치를 구하게 합니다. 이 서비스는 머신 러닝을 통해 과거의 교통 상황을 근거로 한 도착 시간들을 학습하고, 현재의 교통 상황을 입력으로 하여 예상 도착 시간을 계산하도록 설계할 수 있습니다.

c) 순위 결정 서비스

최단 경로 서비스가 구한 경로들에 대해 예상 도착 시간 서비스가 경로별로 예상 도착 시간들까지 구했다면, 순위 결정 서비스를 통해 사용자가 정의한 필터링 조건(도보로만 가기 등)을 적용한 경로들을 얻게끔 합니다. (책에서는 예상 도착 시간들을 구한 뒤 필터링을 적용하나, 개인적으론 필터링을 먼저 적용한 뒤 남은 경로들에 대해 예상 도착 시간을 구하는 것이 연산 횟수가 더 적을 것 같다는 생각이 듭니다.)

분산 시스템의 설계 이론을 말하는 것으로, 시스템이 Consistency (일관성), Availability (가용성), Partition Tolerance (분할 내성) 이 세 가지를 모두 동시에 완벽히 충족할 수 없다는 것을 말합니다. 이 3가지를 모두 만족시킬 수는 없으니, 시스템이 요구하는 것이 무엇인지에 따라 한 가지는 어느 정도 포기해야 한다는 이론입니다.

각 항목별 구체적인 설명은 다음과 같습니다.

1. 일관성 (Consistency)

• 어떤 노드에 연결하든 모든 클라이언트가 동시에 동일한 데이터를 볼 수 있어야 함을 의미합니다. (일종의 정확성)
• 어떤 데이터가 갱신됐다고 치면, 해당 데이터를 조회할 때 어떤 노드에서 조회하든 모든 노드가 동일한 값을 반환해야 합니다.
• 데이터가 한 노드에 기록될 때마다 쓰기가 '성공'된 것으로 간주되기 전에 다른 모든 노드에 데이터를 즉시 전달하거나 복제해야 합니다. 

2. 가용성 (Availability)

• 모든 요청(읽기 및 쓰기)에 대해 항상 응답할 수 있어야 함을 의미합니다. 즉 언제든지 서비스가 가용해야 한다는 뜻입니다.
• 데이터를 요청하는 모든 클라이언트가 하나 이상의 노드가 다운된 경우에도 응답을 받을 수 있어야 합니다.
• 즉, 분산 시스템의 모든 작업 노드가 예외 없이 모든 요청에 대해 유효한 응답을 반환해야 합니다.
• 시스템 일부가 장애를 겪더라도 다른 노드가 요청을 처리하여 응답해야 합니다.

3. 분할 내성(파티션 허용성이라고도 부름, Partition Tolerance)

• 시스템에 분할이 생겨도 여전히 시스템은 동작해야 함을 의미합니다.
• 즉 네트워크 단절(Network Partition, 예를 들면 일부 노드 간 통신 불가) 상황에서도 시스템은 계속 작동할 수 있어야 합니다.

단일 노드 시스템이라면 분할 내성은 고려하지 않아도 됩니다. 하지만 분산 시스템은 시스템의 요구사항이 어떻든 네트워크 장애가 언제든 발생할 수 있으므로, 분할 내성은 반드시 챙겨가야 합니다. 따라서 일관성과 가용성 중 시스템에 요구사항에 맞춰 하나를 고르는 형태로 시스템을 설계하게 됩니다. 

그럼 이때 왜 일관성과 가용성을 모두 챙길 수 없다는 것일까요? 일관성을 지켜려면 데이터 복제를 기다리는 것이 필요한데, 이 부분이 가용성을 해치는 요소가 되기 때문입니다. 예를 들어 네트워크 장애가 생겼을 때 데이터 일관성(어떤 노드에서 조회하든 같은 데이터가 조회되는 것)을 지키는 것은 상당히 어렵습니다. 이 때 일관성을 챙기겠다고 하면 잠시 요청 처리를 중단하고 중단된 노드가 재실행될 때까지 기다릴 수 있는데, 그 시간 동안 서비스를 정상적으로 이용하지 못 하는 것이니 가용성은 희생됐다고 볼 수 있습니다. 반면 가용성을 챙기겠다고 하면 정상적으로 요청은 처리하게 되지만 정확한 데이터가 전달된다는 보장은 없으니 데이터의 일관성은 희생하게 된 것이라고 볼 수 있겠습니다.

형태에 따라 CP, AP 시스템으로 다음처럼 분류 가능합니다.

1. CP 시스템 (Consistency + Partition Tolerance)

• 일관성과 분할 내성은 허용, 가용성은 희생하는 구조
• 만약 데이터 쓰기 중 네트워크 장애가 발생하면, 모든 노드가 동일한 데이터를 반환할 때가지 쓰기나 읽기를 지연시킴
• 즉 최신 데이터를 보장하나, 특정 시점엔 요청을 처리하지 못하는 상황(가용성 희생에 따른..)이 발생 가능

2. AP 시스템 (Availability + Partition Tolerance)

• 가용성과 분할 내성은 허용, 일관성은 희생
• 네트워크 장애 시에도 시스템은 항상 가용하나, 최신 데이터가 아닌 오래된 데이터를 반환할 수도 있음
• 네트워크 장애 시에도 쓰기/읽기 요청을 허용하며, 노드 간 동기화는 나중에 처리

참고한 레퍼런스

https://www.ibm.com/kr-ko/topics/cap-theorem

https://onduway.tistory.com/106

※ 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2권 - 챕터 1을 읽고 정리한 글입니다.

들어가며

아키텍처에 정답은 없으나, 내 주변 맛집 찾기 서비스와 같이 정적인 위치에 대한 서비스를 설계할 때는 이 공간 데이터들을 DB에 적재해둔 다음 지오해시나 쿼드트리와 같은 공간 데이터 검색을 위한 인덱스를 활용하는 형태의 아키텍처를 구상해볼 수 있습니다. 그러나 내 친구들의 현재 위치와 같이 자주 바뀌는 동적인 위치에 대해 다룰 때는 조금 다른 형태의 아키텍처를 고려할 필요가 있습니다. 이번에는 페이스북처럼 인근에 있는 친구들의 목록을 보여주는 서비스를 위한 아키텍처를 설계해봅니다. 

냅다 무대뽀로 설계하면 고려할 것이 많으므로.. 다음과 같은 기능적 요구사항을 가정하겠습니다.

1. 본인과 친구들의 직선거리를 기준으로, 특정 거리 이하의 친구들의 목록을 볼 수 있어야 합니다.
2. 목록의 각 항목엔 그 친구까지의 거리, 해당 정보가 갱신된 시각을 표기해야 합니다.
3. 이 친구 목록은 친구들의 몇 초마다(=친구들의 위치가 바뀔 때마다로 해석) 갱신되어야 합니다.
4. 10분 이상 비활성 상태인 친구들은 목록에 포함하지 않습니다.
5. 유저들의 위치 히스토리도 별도로 기록해야 합니다.

다음과 같은 비기능적 요구사항도 가정하겠습니다.

1.  각 사용자들의 위치 정보는 30초마다 갱신된다고 하겠습니다. 이때 이들의 위치 변화가 반영되는 데 오랜 시간이 걸리지 않아야 합니다. (책에선 낮은 지연성 = low latency로 표현됩니다)
2. 일부 데이터가 유실돼도 괜찮습니다.
3. 위치 데이터에 강한 일관성은 요구하지 않아도 됩니다. 이 말은 복제본을 사용할 경우 복제본과 원본 DB의 데이터가 순간 달라지는 현상이 발생해도 몇 초까지는 눈감아준다는 말입니다.

혼자 생각해보기 - HTTP 폴링 기반의 설계

우선 사용자들의 기본적인 정보와 사용자간 친구 관계를 가지는 사용자 DB를 두는 것을 생각해볼 수 있고, 위치 히스토리는 쓰기 위주의 요청을 많이 받게 될 것이므로 위치 히스토리 DB도 따로 두는 것을 생각해볼 수 있습니다. 사용자들의 현재 위치 정보만 갖고 있는 캐시 서버를 별도로 구축할 수 있고, TTL을 10분으로 설정하면 "해당 캐시 서버에 위치 정보가 있는 사용자 = 활성 상태 사용자"로 취급할 수 있으므로 해당 캐시 서버를 활성 상태인 주변 친구들을 검색하는 데 활용할 수 있습니다.

"사용자들의 위치 변화가 반영되는 데 오랜 시간이 걸리지 않아야 한다"라는 비기능적 요구사항으로 인해, 책에서는 웹소켓을 사용해 친구들의 위치 변화를 실시간에 가깝게 처리하는 아키텍처를 선보입니다. 만약 해당 요구사항이 없었다면 개인적으론 30초마다 HTTP 요청을 보내는 방식을 사용하는 아키텍처를 설계할 수 있다고 생각합니다. 이 경우 다음과 같은 개략적인 설계가 가능해보입니다. (사실 시스템 설계를 해본 경험이 없다시피 하다보니.. HTTP를 쓴다면 어떻게 할 수 있을지를 생각해볼 겸 설계해봤습니다.)

1. 모바일 클라이언트가 30초마다 자신의 위치 정보를 담아 로드밸런서로 HTTP 요청을 보냅니다.
2. 로드밸런서가 URL을 보고 인근 친구 검색 서버로 요청을 전달합니다.
3. "유저별 현재 위치"를 담는 캐시 서버에 내 위치를 갱신하고, 위치 히스토리에 타임스탬프와 내 위치를 기록합니다. 이 작업들은 병렬로 수행합니다.
4. 캐시 서버로부터 내 친구 목록을 조회합니다. 없으면 원본 DB에서 캐싱해옵니다.
5. 내 친구 목록과 "유저별 현재 위치"를 담는 캐시 서버를 활용해 친구들의 현재 위치를 조회하고, 특정 거리 이하인 애들만 필터링하여 클라이언트에게 응답합니다.

책에서는 사용자들이 서버로 보내는 위치 정보 변경 전달에 대한 QPS가 334,000 정도의 상황임을 가정하고 있으니, 그에 따른 추가적인 설계가 덧붙여져야 할 것 같습니다. 암튼 이렇게 하면 30초마다 인근에 있는 내 친구들의 목록을 받을 수는 있지만, 그들의 위치 변화가 내 모바일 기기로 실시간으로 전송되는 것은 아닙니다. 책에서는 친구들의 위치 변화를 내 모바일 기기로 실시간에 가깝게 전송할 것을 요구하므로 그에 맞춘 설계안을 살펴보겠습니다.

설계

1) 개략적인 설계

친구들의 위치 변화를 내 기기로 실시간에 가깝게 받으려면 각 기기들을 P2P로 직접 통신하도록 이을 수 있으나, 모바일 기기 특성 상 통신 연결 상태가 좋지 않을 수 있고 일반적인 경우엔 가용한 전력이 한정되어 있음을 고려해야 합니다. 각 기기들이 직접 통신하게 하는 것보다는 중간에 공용 백엔드를 두고 해당 서버를 통해 각자의 위치 정보를 전달하는 방안을 고려할 수 있겠습니다.

즉, (1)특정 유저가 본인의 위치를 백엔드로 전달하면 (2)해당 서버가 다른 유저들에게 그 유저의 위치 변화를 전달해야 합니다. HTTP는 요청이 와야 응답을 주는 프로토콜이므로 (1)은 HTTP로 처리가 가능하나 (2)는 처리가 힘듭니다. 이때 전이중 통신이 가능한 웹소켓 프로토콜을 사용하도록 서버를 구성한다면 (1)과 (2)를 비교적 쉽게 처리할 수 있습니다.

이때 내 위치 변화를 내 친구들한테만 전달하면 되므로, 나와 친구들 사이에 pub / sub 기반의 메시징 기능을 사용하는 것을 고려할 수 있습니다. 대표적으로 Redis pub / sub을 다음과 같이 사용할 수 있습니다.

웹소켓 서버로수신된 사용자의 위치 정보에 대한 이벤트를 해당 사용자의 채널에 발행(publish)하면, 그 채널을 구독(subscribe)하고 있는 친구들에게 위치 정보 변경이 전달됩니다. 위치 정보 변경을 수신한 친구들이 활성 상태라면 거리를 다시 계산하고, 새로 계산된 거리가 유효 거리라면 웹소켓 연결을 통해 해당 친구의 모바일 기기 단말로 새 위치와 갱신 시각을 보내는 방식으로 설계할 수 있습니다.

또한 웹소켓 서버가 스케일 아웃되면 나랑 내 친구가 웹소켓 연결을 맺고 있는 서버가 달라지는 상황도 발생할 수 있는데요. Redis pub / sub 서버를 사용할 경우 내 위치 정보 변경이 내 친구와 웹소켓 연결을 맺고 있는 서버로도 전달될 수 있으므로 해당 상황에 대한 대응이 가능합니다.

결국 개략적으로 다음 형태의 아키텍처를 고려할 수 있겠습니다.

1. 모바일 클라이언트가 30초마다 자신의 위치 정보를 담아 로드밸런서로 요청을 보냅니다.
2. 로드밸런서는 해당 클라이언트가 연결을 맺고 있는 웹소켓 서버로 해당 요청을 전달합니다.
3. 웹소켓 서버는 수신받은 위치 정보를 위치 히스토리 DB에 저장합니다.
4. 웹소켓 서버는 수신받은 위치 정보를 유저별 현재 위치를 담는 캐시 서버에 갱신하고, 웹소켓 연결 핸들러 안의 변수에 해당 위치를 반영합니다.
5. 웹소켓 서버는 수신받은 위치 정보를 Redis pub / sub 서버의 사용자 채널에 발행합니다. 3 ~ 5까지의 작업은 병렬 수행합니다.
6. Redis pub / sub에 발행된 위치 변경 이벤트는 모든 구독자들에게 브로드캐스트됩니다. 
7. 6에서 발생된 위치 변경 이벤트를 받은 웹소켓 연결 핸들러가 있는 웹소켓 서버들은 해당 정보를 바탕으로 새 거리를 계산합니다.
8. 7에서 계산한 거리가 유효한 거리라면 타임스탬프와 함께 해당 구독자의 모바일 기기로 웹소켓 프로토콜을 통해 전송합니다.

5 ~ 8까지의 과정을 도식화해서 살펴보면 다음과 같습니다.

2) 위치 히스토리 DB

위치 히스토리가 이 서비스에서 주요한 기능은 아니나, 어떤 DB에 저장할 지는 고려하는 것이 좋습니다. 우선 어떤 데이터를 저장할 지를 생각해보면 사용자 식별자와 위도 경도 정보, 타임스탬프값을 저장하면 될 것입니다. 책에서는 QPS가 334,000이므로, 막대한 쓰기 연산을 감당할 수 있어야 하며 대규모의 데이터 저장이 예상되는 만큼 수평적 확장이 가능해야 할 것입니다. 카산드라(Cassandra)는 데이터 쓰기 시 메모리에 먼저 데이터들을 저장하다가 한 번에 디스크로 flush하는 구조라 쓰기 성능이 좋고, 스케일 아웃이 용이하므로 이 요구사항에 적합합니다. 관계형 DB도 사용할 수는 있으나 대규모의 데이터가 예상되는만큼 이 경우는 샤딩을 고려해야겠습니다.

상세 설계

1) API 서버의 확장성

친구 추가, 사용자 정보 상세 조회 등을 담당하는 API 서버는 무상태 서버이므로, CPU 사용률 등에 따라 동적으로 서버 수를 늘리거나 줄이도록 설정할 수 있습니다.

2) 웹소켓 서버의 확장성

웹소켓 서버는 유상태 서버로, 특정 사용자와 연결을 맺으면 사용자와의 통신은 연결을 맺은 서버와만 이루어진다는 특징을 고려하여 확장/축소를 생각해야 합니다. 확장의 경우 API 서버와 마찬가지로 사용률 등에 따라 서버를 늘릴 수 있고, 로드밸런서에서 부하 분산 알고리즘으로 Least-Connections를 사용하면 각 웹소켓 서버들에 맺힌 연결의 개수를 어느 정도 균등히 유지할 수 있습니다. 다만 서버의 규모를 축소시킬 때는 해당 서버에 있던 연결들이 종료될 수 있도록 주의할 필요가 있습니다. 이때 해당 서버를 로드밸런서가 draining(연결 종료 중)으로 인식하도록 설정하면, 해당 서버로는 더 이상 웹소켓 연결이 맺어지지 않도록 할 수 있습니다. 참고로 이를 인플라이트 요청(현재 활성화된 요청)들만 처리하도록 설정한다고도 표현합니다. 암튼.. 그 상태로 충분한 시간이 흐른 뒤 연결들이 모두 종료되면 서버를 제거할 수 있습니다.

참고로 서버 제거 시 draining을 설정하는 것은 웹소켓 서버에만 국한된 얘기가 아니며, AWS에선 다음과 같이 300초를 디폴트로 draining이 설정되어 있습니다.

3) 클라이언트 초기화

모바일 기기에서 주변 친구 서비스를 최초 사용할 경우, 웹소켓 클러스터에 있는 서버 가운데 하나와 연결을 맺게 됩니다. 최초 연결 시 모바일 기기에서 사용자의 위치 정보를 송신하게 되면 웹소켓 서버는 구체적으로 다음과 같은 작업을 하도록 설계할 수 있습니다.

1. 위치 정보 캐시에 해당 사용자의 위치 갱신하고 해당 위치를 웹소켓 연결 핸들러 내의 변수에 저장합니다
2. 사용자 DB로부터 해당 사용자의 친구 목록을 가져옵니다.
3. 위치 정보 캐시로부터 2번에서 가져온 친구들의 위치를 가져옵니다. 위치 정보 캐시에는 TTL을 10분으로 하여 위치 정보들이 저장되므로, 비활성화된 유저들의 위치 정보는 가져오지 않게 됩니다.
4. 각각의 친구 위치들에 대해 거리를 계산하고, 유효한 거리라면 모바일 기기로 전달합니다.
5. 2번에서 가져온 모든 친구들에 대해 Redis pub / sub 채널을 구독합니다. 물론 비활성화 친구에 대한 채널을 유지하는 것은 메모리가 필요하나, 극소량인 데다가 활성화 상태로 전환되기 전까진 CPU나 I/O를 이용하지 않으니 크게 고려하지 않아도 됩니다.
6. 사용자의 현재 위치를 Redis pub / sub 채널에 발행합니다.

4) 위치 정보 캐시

각 사용자들의 현재 위치 정보를 TTL을 통해 일정 기간 만큼만 보관하므로, 아무리 많아도 "사용자 전체 수 X 위치 정보를 저장하는 데 필요한 공간"이 메모리 사용량의 최대 한도로 유지됩니다. 다만 QPS가 334,000으로 가정된 상황이므로 Redis 서버 한 대가 이를 모두 감당하는 것은 상당히 부담될 수 있습니다. 그러나 사용자별 위치 정보 데이터는 사용자 식별자를 기준으로 비교적 쉽게 샤딩할 수 있고, 가용성을 높이고 싶다면 각 샤드에 보관하는 위치 정보를 standby 노드에 복제하는 방식을 활용할 수 있습니다.

5) Redis pub / sub 서버

이 아키텍처에서 Redis pub / sub 서버는 사용자의 위치 정보 변경을 사용자의 친구들에게 보낼 때의 라우팅 계층으로서 활용되고 있습니다. 주변 친구 기능을 활용하는 모든 사용자에게 채널이 하나씩 부여되며, 단순한 설계를 위해 모바일 기기는 최초 연결 시 활성화 여부와는 상관없이 모든 친구의 채널을 구독합니다. 이 경우 메모리 사용량과 CPU 사용량을 다음과 같이 고려해 볼 수 있습니다.

(a) 메모리 사용량

Redis pub / sub은 메모리에 해시 테이블과 링크드 리스트를 통해 채널과 그 채널의 구독자들을 관리합니다. 구독자 한 명에 대해 20Byte의 용량을 사용하고, 주변 친구 기능의 사용자가 1억 명이고 모두에게 채널 하나씩을 할당한다고 한 뒤 각 사용자의 친구들 중 100명만 활성화 상태들이라고 가정하겠습니다. 그러면 1억 X 20Byte X 100명 = 약 200GB의 메모리를 사용하게 되는 것이며, 100GB의 메모리가 있는 서버를 사용할 경우 Redis pub / sub 서버는 2대 정도만 있으면 되겠습니다.

(b) CPU 사용량

책에서는 사용자들이 위치 정보 변경을 서버로 전달하는 QPS가 334,000인 상황으로, 각 사용자들이 400명 정도의 친구를 가지고 그들 중 10%인 40명이 활성화 상태라고 가정(즉 웹소켓 서버에 그 사용자의 웹소켓 연결 핸들러가 물려있는 상태)하면 Redis pub / sub 서버는 초당 1,400만 건의 위치 정보 변경 이벤트를 전달하게 됩니다. Redis pub / sub 서버 한 대로는 처리하기 힘든 양입니다.. 기가비트 네트워크 카드를 탑재했다고 해도 보수적인 관점에서 1초에 처리 가능한 구독자 수를 100,000 정도로 추정할 수 있다고 하는데(책에서 이렇게 말하는 명확한 근거는 모르겠습니다만..), 그렇다고 해도 1,400만 건 / 10만 = 140대의 서버가 필요합니다. 즉 Redis pub / sub 서버에서 병목이 생기면 메모리가 아닌 CPU 사용량에서 그 이유를 찾을 수 있고, 이에 대한 해결책으로 분산 Redis pub / sub 클러스터를 고려할 수 있습니다.

6) 분산 Redis pub / sub 클러스터

Redis pub / sub 클러스터를 구성하여 각 사용자들이 저마다 하나씩 가지는 pub / sub 채널들을 분산시킬 수 있고, 각 채널들은 서로 독립적이므로 사용자 식별자를 기준으로 어떤 서버에 배정될지 정할 수 있습니다. 이때 Redis pub / sub 클러스터의 규모를 확대 또는 축소시키는 경우도 고려를 해야 하는데, 그러기 위해서는 Redis pub / sub 서버의 성격이 "무상태"인지 아니면 "유상태"인지를 짚어봐야 합니다.

우선 pub / sub 채널에 전송되는 메시지는 구독자들에게 전송된 후 바로 삭제된다는 관점에서는 무상태라고 볼 수 있습니다. 그러나 각 pub / sub 서버들은 자신들이 가지는 채널에 대한 상태 정보(ex : 각 채널의 구독자 목록)을 보관하고 있다는 관점에서 보면 유상태라고 볼 수 있습니다. 그래서 특정 채널을 담당하던 서버가 없어질 경우 그 채널에 매달려있던 구독자 정보들이 없어질 수 있습니다. 

즉 Redis pub / sub 클러스터는 유상태 서버 클러스터로 취급하여 관리할 필요가 있습니다. 현재 가용한 pub / sub 서버들의 목록을 유지하고 이 서버들에서 발행한 변경 내역들을 구독할 수 있는 기능을 가진 컴포넌트를 별도로 두는 것을 고려할 수 있고, 대표적으론 주키퍼라는 분산 코디네이션 서비스를 쓸 수 있습니다. 이때 가용한 pub / sub 서버들을 해시 링 형태로 보관하고, 메시지를 발행할 채널 또는 구독할 채널이 있는 pub / sub 서버를 정해야 할 때 이 링을 참조하도록 할 수 있습니다. (이 글의 제일 하단에서 다루겠습니다). 이를 통해 웹소켓 서버가 특정한 채널에 위치 정보 변경을 발행하는 과정을 다음과 같이 나타낼 수 있습니다.

1. 웹소켓 서버는 해시 링을 참조해 메시지를 발행할 pub / sub 서버를 결정합니다. 이 과정에서 주키퍼를 활용하나, 성능을 높이고 싶다면 해시 링 사본을 웹소켓 서버 자체에 캐시하는 방법을 사용 가능합니다(즉 주키퍼를 참조하는 네트워크 i/o가 없어짐). 그러나 이 경우는 해시 링 원본에 구독 관계를 설정, 사본의 상태를 항상 원본과 동일하게 유지하도록 추가 설계가 필요합니다.
2. 웹소켓 서버가 해당 pub / sub 서버가 관리하는 채널에 메시지를 발행합니다.

그럼에도.. Redis pub / sub 클러스터와 같은 유상태 서버 클러스터의 규모를 확대하거나 축소하는 것은 운영 부담과 위험이 큰 작업인 것은 여전합니다. 따라서.. 어지간하면 처음부터 큼지막하게 오버 프로비저닝을 하는 것이 보통입니다.  그러나 정말 어쩔 수 없이 규모 변경을 불가피하게 진행해야 할 경우 시스템 부하가 가장 낮은 때(ex : 새벽..)에 하는 것이 좋습니다.

※ Consistent Hashing와 Hash ring

위에서 pub / sub 채널들은 서로 독립적이므로 사용자 식별자 등을 기준으로 어떤 서버에 채널을 배정해야 할 지 정할 수 있다고 했습니다. 이와 같이 분산 시스템에서 특정한 값이 해시값에 따라 어느 노드로 갈지 정하는 경우 대표적으로 모듈러 연산을 활용 가능합니다.

ex) 3으로 나눈 나머지에 따라 노드를 배정한다고 하면..

1. 1번 : 1번 노드에 배정
2. 2번 : 2번 노드에 배정
3. 3번 : 0번 노드에 배정
4. 4번 : 1번 노드에 배정..

하지만 이 방법은 노드의 수가 변하면 특정 노드에 있던 데이터들이 여전히 그 노드에 남아있을지는 보장되지 않으므로 기존 데이터들을 재분배해야 하는 문제가 있습니다. 이때 안정 해시(Consistent Hashing)을 사용하면 노드 수가 변해도 재분배해야 하는 데이터를 적은 수로 가져갈 수 있으며, 대표적인 방법이 해시 링입니다.

해시 링은 이미지처럼 각 노드("키"로도 이해 가능하며 이미지에선 A, B, C)와 데이터(Jane, Kate 등)를 특정 해시값으로 변환해 링 위에 배치하고, 데이터들이 놓인 위치(해시값 범위)에 따라 어느 노드에 배정될지를 결정하는 방식입니다. 만약 위 이미지에서 C가 사라진다고 하면 C에 붙어있던 John과 Steve만 A로 붙여주면 되고, 특정 노드가 추가된다고 하면 해당 범위에 있는 애들만 다시 붙여주면 됩니다. 따라서 노드 수에 변화가 생겼을 때 모든 데이터를 재분배하지 않고 특정 범위에 해당하는 데이터들만 재분배해줄 수가 있게 됩니다.

다만 단점도 있는데요. 데이터를 균등히 저장하지 못할 수 있다는 단점(해시 특성상 어쩔 수 없다고 생각됩니다)과 노드가 삭제되는 순간에는 인접한 다른 노드로 삭제된 노드에 붙어있던 데이터들이 달라붙게 되어 그 노드에 대한 부하가 커질 수 있고, 최악의 경우 이게 연쇄적인 노드 죽이기(?)가 될 수 있다는 단점이 있습니다. 이는 실제 노드가 여러 개의 논리적인 virtual node들을 만들고, 얘네들을 링 위에 무작위하게 뿌리는 방식으로 어느 정도 보완 가능합니다.

※ 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2권 - 챕터 1을 읽고 정리한 글입니다.

들어가며

근접성 서비스(Proximity Service)란 특정 위치를 기반으로 가까운 시설을 찾는 서비스를 의미합니다. 예를 들어 주변 맛집 찾기 서비스를 설계한다고 할 때, 2차원 형태(위도, 경도)로 표현되는 공간 데이터를 빠르게 검색하는 기술에 대한 이해를 바탕으로 아키텍쳐를 설계할 필요가 있습니다. 공간 데이터를 검색하는 기술들을 설펴보고, 그 중 지오해시(Geohash)를 기반으로 한 아키텍처 설계 방법에 대해 소개하겠습니다.

공간 데이터 검색 기술

다음과 같이 특정 위치와 반경을 기반으로 주변의 시설들을 검색하는 방법들에 대해 살펴보겠습니다.

1) 가장 단순한 공간 데이터 검색 : 2차원 검색

가장 단순한 방법입니다. 주어진 반경값을 토대로 검색해야 하는 위도와 경도의 범위를 계산하여 검색에 활용하는 방법입니다. 그러나 별도의 인덱스 설정이 없으면 테이블 전체를 풀 스캔해야 하는 단점이 있습니다. 위도와 경도에 인덱스를 달아둔다고 해도, 각 인덱스를 통해 얻어낸 두 집합의 교집합을 구해야 하는 데서 많은 비용이 발생합니다. 이런 문제들은 기본적으론 DB 인덱스가 한 차원의 검색 속도를 개선시키는 것에서 비롯되므로, 2차원의 공간 데이터에 대한 인덱스 생성 방법을 고려할 필요가 있습니다.

공간 데이터에 대해 인덱스를 만드는 방법은 다음과 같이 분류 가능합니다.

• Hash 기반
  1. 균등 격자 (even grid)
  2. 지오해시 (Geohash)
  3. 카르테시안 계층 (Cartesian tiers)
• 트리 기반
  1. 쿼드트리 (Quadtree)
  2. 구글 S2
  3. R-tree

각 기술들의 세부 구현 방법은 서로 다르지만, 기본적으로는

1. 공간을 여러 작은 영역들로 분할
2. 공간 데이터들을 분할된 영역들로 매핑 (2차원 데이터가 1차원 데이터로 매핑되는 효과)
3. "분할된 영역"들을 빠르게 검색 

하는 형태로 인덱스가 활용된다고 보면 됩니다. 여기서는 균등 격자와 지오 해시, 쿼드 트리 및 R-tree에 대해 소개하겠습니다.

2) Hash 기반 공간 데이터 검색 : 균등 격자

2차원 공간을 다음과 같이 균일한 크기를 가진 격자로 나누는 접근법입니다.

각 격자들에 1부터 시작하는 식별자 번호를 할당할 수 있고, 공간 데이터들을 각 격자들로 매핑시켜 활용할 수 있게 됩니다. 그러나 뒤에서 소개할 다른 방법들과는 달리 격자 식별자를 할당하는 방법에 명확한 체계가 있는 방식은 아니기 때문에, 특정 격자 주변에 있는 격자를 찾는 것이 어렵다는 단점이 있습니다. 우리의 목적인 "특정 위치와 반경을 기반으로 주변의 시설을 검색하기"를 위해서는 인접한 격자를 쉽게 찾을 수 있어야 하지만 그 부분에 제약이 걸리는 것으로 볼 수 있습니다. 또한 각 격자별로 갖는 공간 데이터들의 분포가 균등하지 않다는 단점도 있습니다.

3) Hash 기반 공간 데이터 검색 : 지오해시

균등 격자와 비슷하게 2차원 공간을 균일한 크기를 가진 격자로 나누고 격자들에 식별자를 할당합니다. 다만 식별자 할당에 체계가 있다는 차이점이 있습니다. 

2차원 공간을 그림처럼 4개로 나눈 후, 위도 경도의 범위를 기준으로 4개 영역에 비트값을 할당합니다. 다시 각 격자를 4개로 나눈 후, 각 영역에 비트값을 추가하는 과정을 원하는 정밀도(즉 격자의 크기)가 나올 때까지 반복합니다. 이렇게 나온 비트값을 base 32 표현법으로 인코딩해 나온 문자열을 지오해시라고 부릅니다. 

ex) 비트값이 "1001 11010 01001 10001 11111 11110" 이면 지오해시는 "9q9hvu"

지오해시의 길이가 길수록 정밀도가 높은 것(사이즈가 작은 격자들로 분할된 것)을 의미하며, 지오해시의 길이에 따라 총 12 레벨로 분류할 수 있습니다. 길이 1짜리인 1레벨은 지구 전체에 해당(즉 격자 1개)하고 길이 12짜리인 12레벨은 격자 하나의 사이즈가 3.7cm X 1.9cm입니다. 일반적인 경우 4 ~ 6레벨을 사용하며, 사용자가 지정한 반경으로 그린 원을 덮는 최소 크기 격자를 만드는 지오해시 길이를 최적 정밀도로 계산할 수 있습니다.

ex) 지정한 반경이 1km일 때, 지오해시 레벨이 5인 격자의 크기가 4.9km X 4.9km으로 지정된 반경으로 그린 원을 덮을 수 있는 최소 크기 격자가 됩니다. 레벨 6짜리 격자의 크기는 1.2km X 0.6km입니다. 

앞서 살펴봤듯이, 지오해시는 격자를 4개로 나눈 후 원래 가지던 비트값 뒤에 01, 11, 00, 10을 추가하는 식으로 식별자 할당이 진행됩니다. 따라서 이 비트값들을 base 32로 인코딩한 지오해시값들은 비슷할 수밖에 없고, 이를 통해 "공통접두어가 긴 격자들은 인접해있다"를 도출할 수 있습니다. 또한 뒤에 붙어있는 비트값을 떼주면, 해당 격자를 포함하는 좀 더 넓은 격자로 범위를 확장시킬 수 있습니다. 따라서 지오해시는 이 점들을 활용해 범위 기반 지역 검색을 쉽게 할 수 있게 됩니다. 

다만 하나의 격자만 볼 때는 균등 격자와 마찬가지로 각 격자별로 갖는 공간 데이터들의 분포가 균등하지 않다는 단점은 남아있으며, 공통접두어가 긴 격자들은 인접하다라는 명제는 성립하나 "인접한 격자들은 공통접두어가 같다"는 성립하지 않음에 유의해야 합니다. 이유는 다음 그림과 같이 인접한 격자임에도 비트값들은 서로 완전히 다를 수 있기 때문입니다.

4) 트리 기반 공간 데이터 검색 : 쿼드트리

지오해시는 격자들에 할당된 식별자들을 DB에 저장해 가지는 방식이었다면, 쿼드트리는 격자를 재귀적으로 4개로 쪼개가며 만든 트리를 메모리에 둔 채로 활용하는 방식입니다. 구체적으로는 트리의 리프노드들에 담긴 공간 데이터가 내가 원하는 수(k) 이하가 될 때까지 분할하며, 리프노드에는 해당 격자에 포함된 공간 데이터의 정보들을 갖도록 구성합니다.

모든 격자를 균일한 사이즈로 해야했던 지오해시와는 달리, 쿼드트리는 맘만 먹으면 원하는 영역에 대해 세밀하게 격자를 분할하는 것이 쉽습니다. 또한 트리 구성 시 특정 숫자(k)를 기준으로 만들어 나가는 점을 활용해 "현재 내 위치에서 가까운 공간 데이터 x개 찾기"를 쉽게 할 수 있게 됩니다. 하지만 트리 구조인 만큼 공간 데이터 추가 / 삭제로 인한 인덱스 변경이 좀 더 까다롭고, 서버 시작 시 트리를 구축해서 메모리에 둬야 하기 때문에 서버 시작 시간이 길어질 수 있음을 유의해야 합니다.

설계

위에서 살펴본 기술 중, 지오해시를 사용할 때의 일반적인 설계 방법에 대해 살펴보겠습니다. 특정 위치와 반경을 기준으로 주변 시설을 조회하는 기능과 특정 시설의 상세 정보를 제공하는 서비스로, 다음과 같은 기능적 요구사항이 있다고 가정합니다.

1. 사용자의 경도와 위도, 반경에 매치되는 시설 목록을 반환해야 함
2. 시설 정보가 추가/갱신/삭제될 수 있으나 실시간으로 반영될 필요는 없음
3. 시설의 상세 정보를 조회할 수 있어야 함

그리고 주변 시설을 빠르게 검색 가능해야 하고 트래픽이 급증해도 감당할 수 있어야 한다는 비기능적 요구사항이 있다고 하겠습니다. 또한  1초에 5,000번 정도의 검색이 발생하는 읽기 연산 위주의 시스템으로 가정하며, 다음과 같은 API들이 있다고 하겠습니다.

1) 서버  및 로드밸런서 설계

해당 시스템을 위치 기반으로 시설들을 검색하는 서비스(LBS)와 시설 서비스(시설 상세조회, 등록 등을 담당)로 구분할 수 있습니다. 사용자가 보내는 요청들을 각각의 알맞는 서비스로 전달하기 위해 로드밸런서에서 URL 경로를 분석해 다음과 같이 설정해줄 수 있습니다.

또한 LBS와 시설 서비스는 이전 요청의 상태나 데이터를 유지하지 않는 무상태 서비스이므로 확장성이 좋습니다. 따라서 트래픽이 몰릴 때는 서버를 추가하여 대응하고, 트래픽이 줄어들면 서버를 삭제하도록 유연하게 구성할 수 있습니다. 또한, 클라우드에 시스템을 띄운다면 여러 지역 또는 여러 가용 영역에 둠으로써 고가용성도 확보할 수 있겠습니다. 여러 지역에 둘 경우 DNS 라우팅을 통해 사용자와 가까운 서버에서 트래픽을 처리하도록 하여 응답 시간을 줄이는 효과 등을 기대할 수 있으며, 한 지역 안에서도 여러 가용 영역을 활용한 부하 분산을 기대할 수 있습니다.

2) 데이터베이스 설계

이 시스템은 앞서 가정한대로 읽기 연산이 많이 발생하는 특징이 있습니다. 따라서 데이터베이스를 master-slave 형태로 구성하여 master가 쓰기 요청을, slave가 읽기 연산을 처리하도록 구성하여 부하를 어느 정도 분산시키도록 구성할 수 있습니다.

그리고 테이블을 위치 정보 관련 연산의 효율을 위해 시설의 상세 정보를 담는 테이블(business 테이블)과 공간 인덱스 테이블(지오해시값과 시설id만 가지는)로 분리할 수 있습니다.

먼저 business 테이블의 경우 시설 데이터가 방대하다면 한 서버에 담기지 못할 수 있으므로, 샤딩을 통해 수평적으로 분리 확장시킬 수 있겠습니다.

공간 인덱스 테이블은 서버 한 대에 충분히 수용 가능할 것으로 예상되나, 읽기 연산이 많은 경우 가용한 리소스(CPU, 네트워크 대역폭 등)의 한계가 있으므로 부하 분산이 필요할 수 있는데요. 보통 부하 분산이 필요한 경우 Replica를 늘리는 것과 샤딩을 고려할 수 있으나,  지오해시는 격자별 공간 데이터 분포가 고르지 않아 샤딩이 까다롭고 공간 인덱스 테이블은 서버 한 대에 충분히 수용 가능할 것으로 예상되므로 Replica를 활용하는 것이 더 나은 방안이 될 수 있습니다.

3) 캐시 설계

다중 서버 환경이므로 로컬 캐시보다는 캐시 서버를 구축하는 형태의 글로벌 캐시를 사용하는 것이 좋습니다. 가장 직관적으로 떠올릴 수 있는 캐시 키는 사용자의 위도 경도입니다. 그러나 위도 경도는 사용자가 조금만 움직여도 달라지기 때문에, 캐시 키로 설정할 경우 캐시 히트가 발생하길 기대하기가 매우 어렵습니다. 이때 아까 배웠던 지오해시나 쿼드트리 등을 사용한다면 같은 격자 내의 시설들이 같은 격자 식별자 값을 갖도록 만들 수 있으므로 이 문제를 효과적으로 해결 가능합니다.

구체적으로 다음 데이터들을 캐시에 보관하도록 할 수 있습니다.

특정 지오해시에 대응되는 시설 목록을 요청받은 경우, 다음과 같이 설계할 수 있겠습니다.

1. 캐시 먼저 조회
2. 없으면 DB에서 해당 지오해시에 대응되는 시설 id 목록 가져와서 캐싱

시설 서비스를 통해 시설의 상세 정보를 조회하는 경우도 위 플로우대로 설계할 수 있겠습니다. 새로운 시설을 추가하거나 기존 시설 정보를 편집 또는 삭제하는 경우, DB를 그에 맞춰 갱신하고 캐시에 보관된 항목은 무효화시킬 수 있습니다. 만약 검색 반경으로 가능한 값들이 정해진 경우, 각 반경에 맞춘 적절한 지오해시 레벨들을 계산 가능하므로 해당하는 레벨에 대한 검색 결과들을 미리 캐싱해둘 수도 있겠습니다. 또한 고가용성 보장을 위해 캐시 서버도 클러스터를 구성하는 것을 고려할 수 있으며, 서버들을 여러 지역에 둔 것과 마찬 가지로 캐시 서버 클러스터를 각 지역별로 구성하여 가까운 캐시 서버를 사용하도록 구성할 수 있겠습니다.

4) 최종 설계도

앞서 설명한 것들을 토대로 다음과 같은 아키텍처를 설계할 수 있게 됩니다.

해당 아키텍처에서의 플로우는 다음과 같이 설계할 수 있습니다.

a) 주변 시설들을 검색하는 경우

1. 클라이언트는 위치(위도, 경도)와 검색 반경을 로드밸런서로 전송합니다.
2. 로드밸런서는 URL을 보고 해당 요청을 LBS로 보냅니다.
3. LBS는 요청에 포함된 위치와 반경 정보를 토대로 최적 정밀도를 갖는 지오해시 길이를 계산합니다.
4. LBS는 사용자의 위치를 담는 지오해시와 인접한 지오해시들을 계산하여 목록으로 가집니다.
5. LBS는 목록에 있는 각 지오해시값에 대해, 글로벌 캐시 서버로부터 해당 지오해시에 매핑된 시설들의 id목록을 가져옵니다. 만약 캐싱된 게 없다면 DB의 공간 인덱스 테이블에서 가져와서 캐싱합니다.
6. 각 시설id들에 대해, 글로벌 캐시 서버로부터 해당 id에 매핑된 상세 정보들을 가져옵니다. 만약 캐싱된 게 없다면 DB의 business 테이블에서 가져와서 캐싱합니다.

b) 시설의 상세정보를 조회하는 경우

1. 클라이언트는 조회할 시설의 id를 로드밸런서로 전송합니다.
2. 로드밸런서는 URL을 보고 해당 요청을 시설 서비스 서버로 보냅니다.
3. 시설 서비스 서버는 글로벌 캐시 서버로부터 해당 시설id에 대한 상세 정보를 가져옵니다. 만약 캐싱된 게 없다면 DB의 business테이블에서 가져와서 캐싱합니다.

시설 정보가 추가/갱신/삭제된 경우, 해당 정보가 실시간으로 반영될 필요는 없음을 처음에 가정했으므로 캐시에 보관된 시설 정보의 갱신은 밤 사이에 배치를 수행하는 방식으로 처리할 수 있습니다.