📚 지식 노트

채팅

요구와 규모

일대일과 그룹 대화, 접속 상태 표시, "보냄·받음·읽음" 표시, 여러 기기 동기화가 필요하다. 하루 활성 사용자 5천만 명이 하루 40통씩 보내고, 한 통은 메타데이터를 합쳐 200바이트라고 하자.

• 메시지: 5천만 × 40 = 하루 20억 통, 20억 ÷ 86,400 ≈ 초당 2만 3천 통. 저장은 하루 20억 × 200B = 400GB, 1년이면 약 146TB다.
• 연결: 저녁에 1천만 명이 동시에 접속해 있다면 연결 1천만 개를 늘 열어 둬야 한다. 서버 한 대가 5만 연결을 든다고 보면 게이트웨이만 200대다. 메시지 처리량보다 열린 연결 수가 서버 대수를 정한다.

핵심 설계

HTTP는 클라이언트가 묻고 서버가 답하는 구조라, 서버가 먼저 "새 메시지 왔다"고 말하려면 다른 길이 필요하다. 짧은 주기로 묻는 폴링은 대부분 빈 응답이고, 응답을 붙잡아 두는 롱 폴링은 메시지마다 연결을 다시 맺는다. WebSocket(RFC 6455)은 HTTP로 시작해 연결을 업그레이드한 뒤 양쪽이 아무 때나 프레임을 보내는 상태 있는 연결이다. 그래서 채팅 서버는 둘로 나뉜다. 연결을 붙잡고 있는 게이트웨이(상태 있음)와, 메시지를 저장하고 누구에게 보낼지 정하는 채널 서버·API다. 게이트웨이는 연결만 들고 판단은 하지 않아서, 배포할 때 연결을 천천히 옮기는 것 말고는 단순하게 유지된다.

순서는 채널마다 한 곳에서 매긴다. 서버 시계로 순서를 정하면 서버마다 시계가 조금씩 어긋나 순서가 뒤집힌다. 채널 하나를 채널 서버 하나가 맡아(채널 ID를 일관된 해싱으로 배정) 그 안에서 1씩 늘어나는 순번을 매기면, 채널 안의 모든 사람이 같은 순서를 본다. 채널 사이의 순서는 보장하지 않는데, 사람이 느끼기에 필요 없기 때문이다. 순번과 별개로 보내는 앱이 만든 ID를 붙여 두면, 응답을 잃어 다시 보낸 메시지를 서버가 알아보고 한 번만 저장한다. 시간과 순서의 일반론은 일관성과 시간 노트에 있다.

어려운 점과 선택지

• 접속 상태: 앱이 몇십 초마다 하트비트를 보내고, 일정 시간 오지 않으면 오프라인으로 본다. 연결이 끊기는 순간마다 상태를 바꾸면 엘리베이터에 탄 사람이 친구 목록에서 깜빡거린다. 상태 변화를 친구 모두에게 밀어 주면 큰 그룹에서는 변화 하나가 수천 건의 알림이 되므로, 화면에 보이는 사람의 상태만 구독하게 한다.
• 저장소: 메시지는 쓰기가 많고 대개 최근 것을 채널 단위로 읽는다. 그래서 (채널, 시간 구간)을 파티션 키로, 순번을 정렬 키로 둔 와이드 컬럼 저장소가 잘 맞는다. 큰 채널의 파티션이 한없이 커지지 않게 시간 구간으로 자른다.
• 오프라인 사용자: 받는 사람이 접속해 있지 않으면 게이트웨이로 밀 수 없다. 이때는 푸시 알림을 보내고(웹 서비스 사례 노트의 알림 시스템), 다시 접속하면 기기가 마지막으로 받은 순번을 대고 그 뒤를 받아 간다.
• 큰 그룹: 1만 명 채널에 메시지 하나가 오면 1만 번 밀어야 한다. 사람 대신 게이트웨이가 채널을 구독하게 하면, 같은 게이트웨이에 붙은 사람이 많을수록 서버 사이 전송이 줄어든다.

실제 사례

Slack은 Real-time Messaging에서 이 구조를 공개했다. 채널 ID를 일관된 해싱으로 나눠 맡는 메모리 기반 채널 서버, 여러 지역에 흩어져 WebSocket 연결과 구독을 드는 게이트웨이 서버, 접속 상태만 따로 맡는 프레즌스 서버가 있고, 메시지는 채널 서버에서 구독 중인 게이트웨이들로 퍼진다. 저장소 쪽은 Discord가 잘 보여 준다. How Discord Stores Billions of Messages는 메시지를 (채널, 고정 시간 구간)으로 파티션해 Cassandra에 넣은 이유를, 후속 글 How Discord Stores Trillions of Messages는 Cassandra 177대를 ScyllaDB 72대로 옮기고, 같은 행을 동시에 여러 사용자가 요청하면 DB에는 한 번만 묻는 요청 합치기(request coalescing) 계층을 둔 이야기를 한다.

검색어 자동완성

요구와 규모

글자를 칠 때마다 그 접두사로 시작하는 인기 검색어 몇 개를 수십 밀리초 안에 보여 준다. 하루 활성 사용자 2천만 명이 하루 네 번 검색하고, 입력을 잠깐 멈출 때만 요청하도록(debounce) 해서 검색 한 번에 요청이 여섯 번 나간다고 하자.

• 2천만 × 4 × 6 = 하루 4.8억 요청, ÷ 86,400 ≈ 초당 5,600건. 출퇴근 시간에 세 배로 몰리면 초당 약 1만 7천 건이다.
• 사람이 지연을 느끼지 않으려면 응답이 타자 간격(대략 100~200ms)보다 빨라야 한다. 네트워크를 빼면 서버 몫은 몇십 ms라, 매 요청마다 정렬하거나 디스크를 읽을 여유가 없다.

핵심 설계

접두사 찾기에는 트라이가 맞는다. 다만 "tr"로 시작하는 검색어를 모두 모아 매번 정렬하면 접두사가 짧을수록 느려진다. 그래서 노드마다 상위 k개를 미리 계산해 저장한다. 질의는 접두사 길이만큼 내려가 저장된 목록을 그대로 돌려주는 일이 되어, 검색어 수와 상관없이 빠르다. 대신 메모리를 더 쓰고, 검색 횟수가 바뀌면 여러 노드의 목록을 고쳐야 한다.

그래서 쓰기와 읽기를 떼어 낸다. 검색 기록은 로그로 쌓고, 한 시간이나 하루마다 배치 작업이 검색어별 횟수를 세어 트라이를 통째로 새로 만든다. 만든 트라이는 직렬화해 저장소에 올리고, 서빙 서버는 새 판을 내려받아 메모리에서 바꿔 끼운다. 서빙 쪽은 읽기 전용이라 잠금이 없고, 접두사 첫 글자 범위로 샤딩해 여러 대로 나눈다. 배치와 스트림의 선택은 배치와 스트림 처리 노트에 있다.

어려운 점과 선택지

• 신선도: 하루 배치로는 방금 터진 사건의 검색어가 늦게 뜬다. 최근 몇 시간을 따로 세는 작은 스트림 집계를 두고 큰 트라이의 결과와 섞거나, 최근 횟수에 가중치를 더 준다.
• 샤딩의 치우침: 첫 글자로 나누면 영어에서는 s나 c로 시작하는 쪽이 훨씬 무겁다. 글자 대신 실제 검색량을 보고 경계를 정한다.
• 걸러 내기: 혐오 표현, 개인 정보, 위험한 검색어는 상위 목록에 들어가도 보여 주면 안 된다. 만들 때 금지 목록으로 거르고, 긴급하게 막을 수 있는 필터를 서빙 앞에도 둔다.
• 개인화와 언어: 한글은 자모 단위 입력 중간 상태("ㅎ", "하", "한")를 어떻게 접두사로 볼지 정해야 하고, 개인 기록을 섞으면 공용 트라이와 개인 목록을 합치는 단계가 붙는다.

실제 사례

Elasticsearch의 completion suggester는 자동완성 전용 자료구조를 메모리에 둔다. 공식 문서는 이것이 조회는 빠르지만 만드는 비용이 크고 메모리에 상주한다고 설명한다. 일반 검색 색인과 따로 두는 이유가 위의 "읽기용으로 미리 만든 구조"와 같다.

근처 장소 찾기

요구와 규모

내 위치에서 반경 안의 식당이나 가게를 찾는다. 장소 정보는 자주 바뀌지 않고, 검색은 많다. 장소 3천만 곳, 하루 활성 사용자 1천만 명이 하루 세 번 검색한다고 하자.

• 검색: 3천만 ÷ 86,400 ≈ 초당 350건, 점심시간에 다섯 배면 초당 1,700건.
• 색인 크기: 장소마다 ID 8바이트, 위도·경도 16바이트, 공간 키 8바이트면 32바이트, 3천만 × 32B ≈ 1GB. 색인 전체가 서버 한 대 메모리에 들어가므로 샤딩보다 복제로 읽기를 늘리면 된다. 장소 상세 정보는 따로 DB와 캐시에 둔다.

핵심 설계

"위도 사이, 그리고 경도 사이"를 묻는 질의는 B-트리 색인 둘로는 잘 풀리지 않는다. 하나로 범위를 좁혀도 다른 하나는 띠 전체를 훑어야 한다. 그래서 2차원을 1차원 키로 접는다. 지오해시는 경도와 위도를 번갈아 반씩 나눈 비트를 이어 붙이고 다섯 비트를 한 글자로 쓴다. 같은 접두사를 가진 장소는 같은 칸에 있으므로, 접두사 범위 질의가 곧 공간 질의가 된다. 사분 트리는 칸에 장소가 너무 많으면 넷으로 나누기를 되풀이해, 도심은 잘게, 시골은 크게 나눈다.

어려운 점과 선택지

• 경계: 지오해시에서 가까운 두 점이 칸 경계를 사이에 두면 접두사가 전혀 다를 수 있다. 그래서 가운데 칸만이 아니라 이웃 여덟 칸을 함께 찾고, 결과를 실제 거리로 다시 거른다.
• 칸 크기 고르기: 지오해시는 글자 수로 칸 크기를 고른다. 반경이 작으면 긴 접두사, 크면 짧은 접두사를 쓰고, 찾은 수가 모자라면 한 글자 줄여 넓힌다. 사분 트리는 데이터에 맞춰 크기가 정해지지만, 메모리 안 구조라 서버를 띄울 때 다시 만들고 장소가 바뀌면 트리를 고쳐야 한다.
• 극지와 날짜 변경선: 위도·경도를 그대로 쪼개면 극으로 갈수록 칸이 가늘어진다. 구 위에서 칸 크기를 고르게 하려는 것이 S2와 H3다.

실제 사례

Google의 S2 Geometry는 구를 정육면체 여섯 면에 투영하고 면마다 사분 트리로 나눈 뒤, 칸을 힐베르트 곡선 순서로 이어 64비트 셀 ID를 준다. 가까운 칸이 ID에서도 가까워서, 원이나 다각형을 셀 ID 범위 몇 개로 덮어 일반 범위 색인으로 찾는다. Uber의 H3는 육각형 칸을 쓴다. 육각형은 이웃 여섯이 모두 같은 거리에 있어, 수요와 공급을 칸 단위로 세고 이웃으로 퍼뜨리는 계산에 편하다. 가장 가벼운 선택은 Redis의 지리 명령이다. 위도·경도를 52비트 지오해시로 바꿔 정렬 집합의 점수로 저장하고, 반경 질의를 점수 범위 질의로 푼다.

근처 친구

요구와 규모

위치 공유를 켠 친구 중 몇 km 안에 있는 사람을 보여 주고, 움직이면 몇십 초 안에 갱신한다. 장소 찾기와 달리 찾는 대상이 계속 움직인다. 동시에 위치를 공유하는 사람이 300만 명이고 20초마다 위치를 보내며, 친구는 평균 150명 중 20%가 공유 중이라고 하자.

• 위치 갱신: 3,000,000 ÷ 20초 = 초당 15만 건.
• 갱신 하나는 공유 중인 친구 150 × 0.2 = 30명에게 퍼진다. 15만 × 30 = 초당 450만 건의 전달이다. 쓰기보다 퍼뜨리기가 훨씬 크다.

핵심 설계

위치를 DB에 쓰고 친구들이 주기적으로 읽어 가게 하면 초당 450만 번의 읽기가 된다. 대신 발행·구독(pub/sub)으로 민다. 사람마다 채널을 하나 두고, 내 위치가 바뀌면 내 채널에 발행한다. 내 친구가 접속하면 그 친구가 붙은 WebSocket 서버가 내 채널을 구독한다. 발행된 위치를 받은 서버가 받는 친구와의 거리를 계산해, 반경 안이면 전하고 아니면 버린다.

현재 위치는 TTL을 둔 캐시에 둔다. 공유를 끄거나 앱이 죽어 갱신이 끊기면 저절로 사라져 "오래된 위치"를 보여 주지 않는다. 처음 접속했을 때 친구들의 지금 위치는 이 캐시에서 한 번에 읽고, 그 뒤로는 구독으로 받는다. 위치 기록이 필요하면 따로 비동기로 쌓는다.

어려운 점과 선택지

• pub/sub 서버의 규모: 채널 수가 공유 중인 사람 수만큼, 구독은 그 수십 배다. 채널 이름을 일관된 해싱으로 여러 pub/sub 서버에 나누고, 서버를 늘리고 줄일 때 옮겨지는 채널이 적게 한다. 이 서버들은 메시지를 저장하지 않으므로, 서버가 죽으면 구독을 다시 맺기만 하면 된다.
• 친구가 아닌 근처 사람: "근처의 아무나"로 넓히면 친구 목록이 없으니 지오해시 칸마다 채널을 두고, 내 칸과 이웃 칸의 채널을 구독하는 방식으로 바꾼다.
• 배터리: 20초 주기는 서버보다 휴대폰에 비싸다. 움직이지 않으면 주기를 늘리고, 아무도 보고 있지 않으면 보내지 않는 식으로 클라이언트가 함께 줄인다.

실제 사례

Redis의 Pub/Sub이 이 구조에 그대로 맞는 부품이다. 공식 문서가 밝히듯 전달은 최대 한 번(at-most-once)이라, 구독자가 잠시 끊겼다 돌아오면 그 사이 메시지는 잃는다. 위치는 몇십 초 뒤 새 값이 오므로 잃어도 괜찮고, 저장하지 않아 빠르다. 같은 이유로 결제처럼 하나도 잃으면 안 되는 일에는 쓰지 않는다. 받는 쪽에 WebSocket을 쓰는 모습은 MDN의 WebSocket API에 있다.

지도와 길 안내

요구와 규모

지도를 그리고, 출발지에서 목적지까지 길을 찾고, 도착 예정 시각(ETA)을 알려 주며, 가는 동안 막히면 다시 찾는다. 길 안내 중인 운전자가 동시에 100만 명이고 5초마다 위치를 보낸다고 하자.

• 위치 보고: 1,000,000 ÷ 5초 = 초당 20만 건. 이 흐름이 실시간 교통 정보의 원료다.
• 지도 타일: 확대 단계 z에서 세계는 2^z × 2^z장이다. 18단계면 4¹⁸ ≈ 687억 장이라, 모든 타일을 미리 만들어 두기보다 자주 보는 곳만 미리 만들고 나머지는 요청이 올 때 만든다.

핵심 설계

서비스는 세 갈래다. 타일: 지도를 확대 단계별로 정사각형 조각으로 잘라 CDN으로 나눈다. 같은 타일을 모두가 받으므로 캐시 효율이 좋다. 요즘은 그림 대신 도형과 속성을 담은 벡터 타일을 내려보내고 앱이 그린다. 용량이 작고, 회전·글자 크기·다크 모드를 앱이 바꿀 수 있다. 길 찾기: 도로망은 교차로가 노드, 도로 구간이 간선인 가중 그래프다. ETA: 간선 가중치를 거리 대신 "지금 이 구간을 지나는 데 걸리는 시간"으로 두고, 실시간 위치 보고와 과거 패턴으로 그 시간을 예측한다.

어려운 점과 선택지

• 대륙 크기의 그래프: 노드가 수억인 그래프에서 매번 다익스트라를 돌리면 느리다. 중요도가 낮은 노드를 차례로 "접어" 지름길 간선을 미리 만들어 두는 Contraction Hierarchies나, 그래프를 여러 층의 구역으로 나누는 방법을 쓴다. 미리 계산하는 양과 교통 정보가 바뀌었을 때 다시 계산하는 비용 사이의 선택이다. 그래프 탐색 자체는 그래프 노트에 있다.
• 지도 갱신: 도로가 새로 나거나 막히면 타일과 그래프를 함께 고쳐야 한다. 타일은 바뀐 구역의 모든 확대 단계를 다시 만들고 CDN에서 무효화해야 한다.
• 다시 찾기: 경로 안내 중에 사고가 나면 영향을 받는 사람에게만 새 경로를 밀어 준다. 이 부분은 근처 친구의 발행·구독과 비슷하다.

실제 사례

타일 주소 규칙은 OpenStreetMap 위키의 Slippy map tilenames가 표준처럼 쓰이고, 벡터 타일 형식은 Mapbox Vector Tile 명세가 공개되어 있다. 오픈 소스 길 찾기 엔진 OSRM은 Contraction Hierarchies와 다층 다익스트라(MLD)를 고를 수 있게 한다. ETA 쪽에서는 Google Maps와 DeepMind가 그래프 신경망으로 교통을 예측한 사례를 공개했다. 붐비는 인접 도로 구간을 묶은 "슈퍼세그먼트" 단위로 이동 시간을 예측해, 도시에 따라 ETA의 틀린 정도를 크게 줄였다고 한다.