[독서 기록] 가상 면접 사례로 배우는 대규모 시스템 설계 기초

1장 사용자 수에 따른 규모 확장성

로드 밸런서

부하 분산 집합에 또 하나의 웹 서버를 추가하고 나면 장애를 자동복구하지 못하는 문제(no failover)는 해소되며, 웹 계층의 가용성(availability)은 향상된다. 좀 더 구체적으로 살펴보면 다음과 같다.

• 서버 1이 다운되면 모든 트래픽은 서버 2로 전송된다. 따라서 웹 사이트 전체가 다운되는 일이 방지된다. 부하를 나누기 위해 새로운 서버를 추가할 수도 있다.
• 웹사이트로 유입되는 트래픽이 가파르게 증가하면 두 대의 서버로 트래픽을 감당할 수 없는 시점이 오는데, 로드밸런서가 있으므로 우아하게 대처할 수 있다. 웹 서버 계층에 더 많은 서버를 추가하기만 하면 된다. 그러면 로드밸런서가 자동적으로 트래픽을 분산하기 시작할 것이다.

데이터베이스 다중화

위키피디아에 따르면, "많은 데이터베이스 관리 시스템이 다중화를 지원한다. 보통은 서버 사이에 주(master)-부(slave) 관계를 설정하고 데이터 원본은 주 서버에, 사본은 부 서버에 저장하는 방식이다."

쓰기 연산은 마스터에서만 지원한다. 부 데이터베이스는 주 데이터베이스로부터 그 사본을 전달받으며, 읽기 연산만을 지원한다. 데이터베이스를 변경하는 명령어들, 가령 insert, delete, update 등은 주 데이터베이스로만 전달되어야 한다. 대부분의 애플리케이션은 읽기 연산의 비중이 쓰기 연산보다 훨씬 높다. 따라서 통상 부 데이터베이스의 수가 주 데이터베이스의 수보다 많다.

데이터베이스 서버 가운데 하나가 다운되면 무슨일이 벌어지는가?

• 부 서버가 한 대 뿐인데 다운된 경우라면, 읽기 연산은 한시적으로 모두 주 데이터베이스로 전달될 것이다. 또한 즉시 새로운 부 데이터베이스 서버가 장애 서버를 대체할 것이다. 부 서버가 여러 대인 경우에 읽기 연산은 나머지 부 데이터베이스 서버들로 분산될 것이며, 새로운 부 데이터베이스 서버가 장애 서버를 대체할 것이다.
• 주 데이터베이스 서버가 다운되면, 한대의 부 데이터베이스만 있는 경우 해당 부 데이터베이스 서버가 새로운 주 서버가 될 것이며, 모든 데이터베이스 연산은 일시적으로 새로운 주 서버상에서 수행될 것이다. 그리고 새로운 부 서버가 추가될 것이다. 프로덕션 환경에서 벌어지는 일은 이것보다는 사실 더 복잡한데, 부 서버에 보관된 데이터가 최산 상태가 아닐 수 있기 때문이다. 없는 데이터는 복구 스크립트를 돌려서 추가해야 한다. 다중 마스터나 원형 다중화 방식을 도입하면 이런 상황에 대처하는 데 도움이 될 수도 있지만 해당 구성은 훨씬 복잡...

• 사용자는 DNS로부터 로드밸런서의 공개 IP 주소를 받는다.
• 사용자는 해당 IP 주소를 사용해 로드밸런서에 접속한다.
• HTTP 요청은 서버 1이나 서버 2로 전달된다.
• 웹 서버는 사용자의 데이터를 부 데이터베이스 서버에서 읽는다.
• 웹 서버는 데이터 변경 연산은 주 데이터베이스로 전달한다. 데이터 추가, 삭제, 갱신 연산 등이 이에 해당한다.

응답 시간은 캐시를 붙이고 정적 콘텐츠를 콘텐츠 전송 네트워크(CDN)로 옮기면 개선할 수 있다.

캐시

애플리케이션의 성능은 데이터베이스를 얼마나 자주 호출하느냐에 크게 좌우되는데, 캐시는 그런 문제를 완화할 수 있다.

캐시 계층

요청을 받은 웹 서버는 캐시에 응답이 저장되어 있는지를 본다. 만일 저장되어 있다면 해당 데이터를 클라이언트에게 반환한다. 없는 경우에는 데이터베이스 질의를 통해 데이터를 찾아 캐시에 저장한 뒤 클라이언트에 반환한다. 이러한 캐시 전략을 읽기 주도형 캐시 전략이라고 부른다. 이것 이외에도 다양한 캐시 전략이 있는데, 캐시할 데이터 종류, 크기, 엑세스 패턴에 맞는 캐시 전략을 선택하면 된다.

캐시 사용 시 유의할 점

• 캐시는 어떤 상황에 바람직한가? 데이터 갱신은 자주 일어나지 않지만 참조는 빈번하게 일어난다면 고려해볼 만하다.
• 어떤 데이터를 캐시에 두어야 하는가? 캐시는 데이터를 휘발성 메모리에 두므로, 영속적으로 보관할 데이터를 캐시에 두는 것은 바람직하지 않다.
• 캐시에 보관된 데이터는 어떻게 반료되는가?
• 일관성은 어떻게 유지되는가? 일관성은 데이터 저장소의 원본과 캐시 내의 사본이 같은지 여부다. 저장소의 원본을 갱신하는 연산과 캐시를 갱신하는 연산이 단일 트랜잭션으로 처리되지 않는 경우 이 일관성은 깨질 수 있다.
• 장애에는 어떻게 대처할 것인가? 캐시 서버를 한 대만 두는 경우 해당 서버는 단일 장애 지점(Single Point of Failure, SPOF)이 되어버릴 가능성이 있다. 위키피디아에 따르면 단일 장애 지점의 정의는 다음과 같다. "어떤 특정 지점에서의 장애가 전체 시스템의 동작을 중단시켜버릴 수 있는 경우, 우리는 해당 지점을 단일 장애 지점이라고 부른다." 결과적으로, SPOF를 피하려면 여러 지역에 걸쳐 캐시 서버를 분산시켜야 한다.
• 캐시 메모리는 얼마나 크게 잡을 것인가? 캐시 메모리가 너무 작으면 액세스 패턴에 따라서는 데이터가 너무 자주 캐시에서 밀려나버려(eviction) 캐시의 성능이 떨어지게 된다. 이를 막을 한 가지 방법은 캐시 메모리를 과할당(overprivision)하는 것이다. 이렇게 하면 캐시에 보관될 데이터가 갑자기 늘어났을 때 생길 문제도 방지할 수 있게 된다.
• 데이터 방출(eviction) 정책은 무엇인가? -> LRU, LFU,

컨텐츠 전송 네트워크

CDN은 정적 콘텐츠를 전송하는 데 쓰이는, 지리적으로 분산된 서버의 네트워크이다. 이미지, 비디오, CSS, JavaScript 파일 등을 캐시할 수 있다.

CDN이 어떻게 동작하는지를 개략적으로만 살펴보면 다음과 같다. 어떤 사용자가 웹사이트를 방문하면, 그 사용자에게 가장 가까운 CDN 서버가 정적 콘텐츠를 전달하게 된다. 직관적으로도 당연하겠지만, 사용자가 CDN 서버로부터 멀면 멀수록 웹사이트는 천천히 로드될 것이다. 예를 들어, CDN 서버가 샌프란시스코에 있다면 LA에 있는 사용자는 유럽 사용자보다 빠른 웹 사이트를 보게 될 것이다.

CDN 사용 시 고려해야 할 사항

• 비용: CDN은 보통 제3 사업자에 의해 운영되며, 여러분은 CDN으로 들어가고 나가는 데이터 전송 양에 따라 요금을 내게 된다. 자주 사용되지 않는 컨텐츠를 캐싱하는 것은 이득이 크지 않으므로, CDN에서 빼는 것을 고려하도록 하자.
• 적절한 만료 시한 설정: 시의성이 중요한(time-sensitive) 콘텐츠의 경우 만료 시점을 잘 정해야 한다. 너무 길지도 않고 짧지도 않아야 하는데, 너무 길면 콘텐츠의 신선도는 떨어질 것이고, 너무 짧으면 원본 서버에 빈번히 접속하게 되어서 좋지 않다.
• CDN 장애에 대한 대처 방안: CDN 자체가 죽었을 경우 웹사이트/애플리케이션이 어떻게 동작해야 하는지 고려해야 한다. 가령 일시적으로 CDN이 응답하지 않을 경우, 해당 문제를 감지하여 원본 서버로부터 직접 콘텐츠를 가져오도록 클라이언트를 구성하는 것이 필요할 수도 있다.
• 콘텐츠 무효화 방법: 아직 만료되지 않은 콘텐츠라 하더라도 아래 방법 가운데 하나를 쓰면 CDN에서 제거할 수 있다.
  • CDN 서비스 사업자가 제공하는 API를 이용하여 콘텐츠 무효화
  • 콘텐츠의 다른 버전을 서비스하도록 오브젝트 버저닝 이용. 콘텐츠의 새로운 버전을 지정하기 위해서는 URL 마지막에 버전 번호를 인자로 주면 된다. 예를 들어, image.png?v=2와 같은 식이다.

무상태 웹 계층

이제 웹 계층을 수평적으로 확장하는 방법을 고민해 볼 순서다. 이를 위해서는 상태 정보(사용자 세션 데이터와 같은)를 웹 계층에서 제거하여야 한다. 바람직한 전략은 상태 정보를 관계형 데이터베이스나 NoSQL 같은 지속성 저장소에 보관하고, 필요할 때 가져오도록 하는 것이다. 이렇게 구성된 웹 계층을 부상태 웹 계층이라 부른다.

상태 정보 의존적인 아키텍처

상태 정보를 보관하는 서버와 그렇지 않은 서버 사이에는 몇 가지 중요한 차이가 있다. 상태 정보를 보관하는 서버는 클라이언트 정보, 즉 상태를 유지하여 요청들 사이에 공유되도록 한다. 무상태 서버에는 그런 장치가 없다.

사용자 A의 세션 정보나 프로파일 이미지 같은 상태 정보는 서버 1에 저장된다. 사용자 A를 인증하기 위해 HTTP 요청은 반드시 서버 1로 전송되어야 한다. 요청이 서버 2로 저장되면 인증은 실패할 것인데, 서버 2에 사용자 A에 관한 데이터는 보관되어 있지 않기 때문이다.

무상태 아키텍처

이 구조에서 사용자로부터의 HTTP 요청은 어떤 웹 서버로도 전달될 수 있다. 웹 서버는 상태 정보가 필요할 경우 공유 저장소로부터 데이터를 가져온다. 따라서 상태 정보는 웹 서버로부터 물리적으로 분리되어 있다. 이런 구조는 단순하고, 안정적이며, 규모 확장이 쉽다.

데이터베이스의 규모 확장

데이터베이스의 규모를 확장하는 데는 두 가지 접근법이 있다. 하나는 수직적 규모 확장법이고 다른 하나는 수평적 규모 확장법이다.

수직적 확장

스케일 업이라고도 부르는 수직적 규모 확장법은 기존 서버에 더 많은, 또는 고성능의 자원을 증설하는 방법이다. 가령 아마존 AWS의 RDS는 24TB RAM을 갖춘 서버도 상품으로 제공하고 있다. 이 정도 수준의 고성능 데이터베이스 서버는 많은 양의 데이터를 보관하고 처리할 수 있다. 예를 들어 스택오버플로는 2013년 한 해 동안 방문한 천만 명의 사용자 전부를 단 한 대의 마스터 데이터베이스로 처리하였다. 하지만 이러한 수직적 접근법에는 몇 가지 심각한 약점이 있다.

• 데이터베이스 서버 하드웨어에는 한계가 있으므로 CPU, RAM 등을 무한 증성할 수는 없다.
• SPOF로 인한 위험성이 크다
• 비용이 많이 든다.

수평적 확장

데이터베이스의 수평적 확장은 샤딩이라고도 부르는데 더 많은 서버를 추가함으로써 성능을 향상시킬 수 있도록 한다.

샤딩은 대규모 데이터베이스를 샤드라고 부르는 작은 단위로 분할하는 기술을 일컫는다. 모든 샤드는 같은 스키마를 쓰지만 샤드에 보관되는 데이터 사이에는 중복이 없다.

샤딩 전략을 구현할 때 고려해야 할 가장 중요한 것은 샤딩 키를 어떻게 정하느냐 하는 것이다. 샤딩 키는 파티션 키라고도 부르는데, 데이터가 어떻게 분산될지 정하는 하나 이상의 칼럼으로 구성된다.

• 데이터의 재 샤딩: 재 샤딩은 다음과 같은 경우에 필요하다. (1) 데이터가 너무 많아져서 하나의 샤드로는 더 이상 감당하기 어려울 때. (2) 샤드 간 데이터 분포가 균등하지 못하여 어떤 샤드에 할당된 공간 소모가 다른 샤드에 비해 빨리 진행될 때. 샤드 소진이라고도 부르는 이런 현상이 발생하면 샤드 키를 계산하는 함수를 변경하고 데이터를 재배치하여야 한다.
• 유명인사(celebrity) 문제: 핫스팟 키 문제라고도 부르는데, 특정 샤드에 질의가 집중되어 서버에 과부하가 걸리는 문제다. 가령 케이티 페리, 저스틴 비버, 레이디 가가 같은 유명인사가 전부 같은 샤드에 저장되는 데이터베이스가 있다고 해 보자. 이 데이터로 사회 관계망 애플리케이션을 구축하게 되면 결국 해당 샤드에는 read 연산 때문에 과부하가 걸리게 될 것이다. 이 문제를 풀려면 위에 나열한 유명인사 각각에 샤드 하나씩을 할당해야 할 수도 있고, 심지어는 더 잘게 쪼개야 할 수도 있다.
• 조인과 비정규화: 일단 하나의 데이터베이스를 여러 샤드 서버로 쪼개고 나면, 여러 샤드에 걸친 데이터를 조인하기가 힘들어진다. 이를 해결하는 한 가지 방법은 데이터베이스를 비정규화하여 하나의 테이블에서 질의가 수행될 수 있도록 하는 것이다.

시스템 규모 확장을 위해 살펴봄 기범들을 다시 한번 정리해보면 다음과 같다.

• 웹 계층은 무상태 계층으로
• 모든 계층에 다중화 도입
• 가능한 한 많은 데이터를 캐시할 것
• 여러 데이터 센터를 지원할 것
• 정적 컨텐츠는 CDN을 통해 서비스할 것
• 데이터 계층은 샤딩을 통해 그 규모를 확장할 것
• 각 계층은 독립적 서비스로 분할할 것
• 시스템을 지속적으로 모니터링하고, 자동화 도구들을 활용할 것

2장 개략적인 규모 추정

2의 제곱수

제대로 된 계산 결과를 얻으려면 데이터 볼륨의 단위를 2의 제곱수로 표현하면 어떻게 되는지를 우선 알아야 한다. 최소 단위는 1바이트이고, 8비트로 구성된다. ASCII 문자 하나가 차지하는 메모리 크기가 1바이트이다.

2의 제곱	근사치	이름	축약형
10	1천	1킬로바이트	1KB
20	1백만	1메가바이트	1MB
30	10억	1기가바이트	1GB
40	1조	1테라바이트	1TB
50	1000조	1페타바이트	1PB

모든 프로그래머가 알아야 하는 응답지연 값

제시된 수치들을 분석하면 다음과 같은 결론이 나온다.

• 메모리는 빠르지만 디스크는 아직도 느리다.
• 디스크 탐색은 가능한 피하라.
• 단순한 압축 알고리즘은 빠르다.
• 데이터를 인터넷으로 전송하기 전에 가능하면 압축하라.
• 데이터 센터는 보통 여러 지역에 분산되어 있고, 센터들 간에 데이터를 주고받는 데는 시간이 걸린다.

가용성에 관계된 수치들

고가용성은 시스템이 오랜 시간 동안 지속적으로 중단 없이 운영될 수 있는 능력을 지칭하는 용어다. 고가용성을 표현하는 값은 퍼센트로 표현하는데, 100%는 시스템이 단 한 번도 중단된 적이 없었음을 의미한다. 대부분의 서비스는 99%에서 100% 사이의 값을 갖는다.

가정

• 월간 능동 사용자는 3억 명이다.
• 50%의 사용자가 트위터를 매일 사용한다.
• 평균적으로 각 사용자는 매일 2건의 트윗을 올린다.
• 미디어를 포함하는 튀읏은 10% 정도다.
• 데이터는 5년간 보관된다.

추정
QPS(Query Per Secodn) 추정치

• 일간 능동 사용자(Daily Active User, DAU) = 3억 x 50% = 1.5억
• QPS = 1.5억 x 2트윗 / 24 / 3600 초 = 약 3500
• 최대 QPS(Peek Qps) = 2 x QPS = 약 7000

미디어 저장을 위한 저장소 요구량

• 평균 트윗 크기
  • tweet_id에 64 바이트
  • 텍스트에 140 바이트
  • 미디어에 1MB
• 미디어 저장소 요구량: 1.5억 x 2 x 10% x 1MB = 30TB / 일
• 5년간 미디어를 보관하기 위한 저장소 요구량: 30TB x 365 x 5 = 약 55PB

3장 시스템 설계 면접 공략법

설계의 순수성에 집착한 나머지 타협적 결정(tradeoff)을 도외시하고 과도한 엔지니어링을 하고 마는 엔지니어들이 현업에도 많다. 그런 엔지니어들은 과도한 엔지니어링의 결과로 시스템 전반의 비용이 올라간다는 사실을 알아채지 못하는 일이 많은데, 그 결과로 상당수 회사들은 값비싼 대가를 치르고 있다.

엔지니어가 가져야 할 가장 중요한 기술 중 하나는 올바른 질문을 하는 것, 적절한 가정을 하는 것, 그리고 시스템 구축에 필요한 정보를 모으는 것이다.

그렇다면 어떤 질문을 해야 하나? 요구사항을 정확히 이해하는 데 필요한 질문을 하라. 아래와 같은 질문들을 생각해 볼 수 있다.

• 구체적으로 어떤 기능들을 만들어야 하나?
• 제품 사용자 수는 얼마나 되나?
• 회사의 규모는 얼마나 빨리 커지리라 예상하나? 석 달, 여섯 달, 일년 뒤의 규모는 얼마나 되리라 예상하는가?
• 회사가 주로 사용하는 기술 스택은 무엇인가? 설계를 단순화하기 위해 활용할 수 있는 기존 서비스로는 어떤 것들이 있는가?

예제

"뉴스 피드 시스템을 설계하라"는 질문을 그대로 활용하여, 개략적 설계는 어떻게 만들어 내는지 살펴보겠다.

개략적으로 보자면 이 설계는 두 가지 처리 플로(flow)로 나눠 생각해 볼 수 있다. 피드 발행(feed publishing)과 피드 생성(feed building)이 그것이다.

• 피드 발행: 사용자가 포스트를 올리면 관련된 데이터가 캐시/데이터베이스에 기록되고, 해당 사용자의 친구 뉴스 피드에 뜨게 된다.
• 피드 생성: 어떤 사용자의 뉴스 피드는 해당 사용자 친구들의 포스트를 시간 역순으로(최신 포스트부터 오래된 포스트 순으로) 정렬하여 만든다.

해야 할 것

• 질문을 통해 확인하라(clarification). 스스로 내린 가정이 옳다 믿고 진행하지 말라.
• 문제의 요구사항을 이해하라.
• 정답이나 최선의 답안 같은 것은 없다는 점을 명심하라. 스타트업을 위한 설계안과 수백만 사용자를 지원해야 하는 중견 기업을 위한 설계안이 같을 리 없다, 요구 사항을 정호가히 이해했는지 다시 확인하라.
• 면접관이 여러분의 사고 흐름을 이해할 수 있도록 하라. 면접관과 소통하라.
• 가능하다면 여러 해법을 함께 제시하라.
• 개략적 설계에 면접관이 동의하면, 각 컴포넌트의 세부사항을 설명하기 시작하라. 가장 중요한 컴포넌트부터 진행하라.
• 면접관의 아이디어를 이끌어 내라. 좋은 면접관은 여러분과 같은 팀원처럼 협력한다.
• 포기하지 말라.

4장 처리율 제한 장치의 설계

네트워크 시스템에서 처리율 제한 장치(rate limiter)는 클라이언트 또는 서비스가 보내는 트래픽의 처리율(rate)을 제어하기 위한 장치다. HTTP를 예로 들면 이 장치는 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한한다. API 요청 횟수가 제한 장치에 정의된 임계치를 넘어서면 추가로 도달한 모든 호출은 처리가 중단된다. 다음은 몇 가지 사례다.

• 사용자는 초당 2회 이상 새 글을 올릴 수 없다.
• 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없다.
• 같은 디바이스로는 주당 5회 이상 리워드를 요청할 수 없다.

이번 장에서는 바로 이 처리율 제한 장치를 설계한다. 설계에 앞서, API에 처리율 제한 장치를 두면 좋은 점을 살펴보자.

• Dos(Denial Of Service) 공격에 의한 자원 고갈을 방지할 수 있다. 대형 IT 기업들이 공개한 거의 대부분의 API는 어떤 형태로든 처리율 제한 장치를 갖고 있다. 예를 들어 트위터는 3시간 동안 300개의 트윗만 올릴 수 있도록 제한하고 있다. 구글 독스 API는 사용자당 분당 300회의 read 요청만 허용한다. 처리율 제한 장치는 추가 요청에 대해서는 처리를 중단함으로써 Dos 공격을 방지한다.
• 비용을 절감한다. 추가 요청에 대한 처리를 제한하면 서버를 많이 두지 않아도 되고, 우선순위가 높은 API에 더 많은 자원을 할당할 수 있다. 아울러 처리율 제한은 제3자 API에 사용료를 지불하고 있는 회사들에게는 아주 중요하다. 예를 들어, 신용을 확인하거나, 신용카드 결제를 하거나, 건강 상태를 확인하거나 하기 위해서는 호출하는 API에 대한 과금이 횟수에 따라 이루어진다면, 그 횟수를 제한할 수 있어야 비용을 절감할 수 있을 것이다.
• 서버 과부하를 막는다. 봇에서 오는 트래픽이나 사용자의 잘못도니 이용 패턴으로 유발된 트래픽을 걸러내는데 처리율 제한 장치를 활용할 수 있다.

1단계 문제 이해 및 설계 범위 확정

시스템 요구사항

• 설정된 처리율을 초과하는 요청은 정확하게 제한한다.
• 낮은 응답시간: 이 처리율 제한 장치는 HTTP 응답시간에 나쁜 영향을 주어서는 곤란하다.
• 가능한 한 적은 메모리를 써야 한다.
• 분산형 처리율 제한: 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 한다.
• 예외 처리: 요청이 제한되었을 때는 그 사실을 사용자에게 분명하게 보여주어야 한다.
• 높은 결함 감내성: 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주어서는 안 된다.

처리율 제한 장치는 어디에 둘 것인가?

• 클라이언트 측에 둔다면: 일반적으로 클라이언트는 처리율 제한을 안정적으로 걸 수 있는 장소가 못 된다. 클라이언트 요청은 쉽게 위변조가 가능해서다. 모든 클라이언트의 구현을 통제하는 것도 어려울 수 있다.
• 서버 측에 둔다면: 그림 4-1은 서버 측에 제한 장치를 두는 한 가지 방법을 보여준다.

처리율 제한 장치를 API 서버에 두는 대신, 처리율 제한 미들웨어를 만들어 해당 미들웨어로 하여금 API 서버로 가능 요청을 통제하도록 하는 것이다.

• 여러분의 설계가 마이크로서비스에 기반하고 있고, 사용자의 인증이나 IP 허용목록 관리 등을 처리하기 위해 API 게이트웨이를 이미 설계에 포함시켰다면 처리율 제한 기능 또한 게이트웨이에 포함시켜야 할 수도 있다.

처리율 제한 알고리즘

• 토큰 버킷
• 누출 버킷
• 고정 윈도 카운터
• 이동 윈도 로그
• 이동 윈도 카운터

토큰 버킷 알고리즘

• 토큰 버킷은 지정된 용량을 갖는 컨테이너다. 이 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워진다. 토큰이 꽉 찬 버킷에는 더 이상의 토큰은 추가되지 않는다. 버킷이 가득차면 추가로 공급된 토큰은 버려진다.
• 각 요청은 처리될 때마다 하나의 토큰을 사용한다. 요청이 도착하면 버킷에 충분한 토큰이 있는지 검사하게 된다.
  • 충분한 토큰이 있는 경우, 버킷에서 토큰 하나를 꺼낸 후 요청을 시스템에 전달한다.
  • 충분한 토큰이 없는 경우, 해당 요청은 버려진다.

버킷은 몇 개나 사용해야 하나? 공급 제한 규칙에 따라 달라진다. 다음 사례들을 살펴보자.

• 통상적으로, API 엔드포인트마다 별도의 버킷을 둔다. 예를 들어, 사용자마다 하루에 한 번만 포스팅을 할 수 있고, 친구는 150명까지 추가할 수 있고, 좋아요 버튼은 다섯 번까지만 누를 수 있다면 사용자마다 3개의 버킷을 두어야 할 것이다.
• IP 주소별로 처리율 제한을 적용해야 한다면 IP 주소마다 버킷을 하나씩 할당해야 한다.
• 시스템의 처리율을 초당 10,000개 요청으로 제한하고 싶다면, 모든 요청이 하나의 버킷으로 공유하도록 해야 할 것이다.

장점:

• 구현이 쉽다.
• 메모리 사용 측면에서도 효율적이다.
• 짧은 시간에 집중되는 트래픽도 처리 가능하다. 버킷에 남은 토큰이 있기만 하면 요청은 시스템에 전달될 것이다.

단점:

• 이 알고리즘은 버킷 크기와 토큰 공급률이라는 두 개 인자를 가지고 있는데, 이 값을 적절하게 튜닝하는 것은 까다로운 일이 될 것이다.

누출 버킷 알고리즘

누출 버킷 알고리즘은 토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다는 점이 다르다. 누출 버킷 알고리즘은 보통 FIFO 큐로 구현한다.

• 요청이 도착하면 큐가 가득 차 있는지 본다. 빈자리가 있는 경우에는 큐에 요청을 추가한다.
• 큐가 가득 차 있는 경우에는 새 요청은 버린다.
• 지정된 시간마다 큐에서 요청을 꺼내어 처리한다.

고정 윈도 카운터 알고리즘

• 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다.
• 요청이 접수될 때마다 이 카운터의 값은 1씩 증가한다.
• 이 카운터의 값이 사전에 설정된 임계치(threshold)에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려진다.

시스템은 초당 3개까지의 요청만을 허용한다. 매초마다 열리는 윈도에 3개 이상의 요청이 밀려오면 초과분은 그림 4-8에 보인 대로 버려진다.

장점

• 메모리 효율이 좋다.
• 이해하기 쉽다.
• 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합하다.

단점

• 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템의 처리 한도보다 많은 양의 요청을 처리하게 된다.

이동 윈도 로깅 알고리즘

고정 윈도 카운터 알고맂므에는 중대한 문제가 있다. 윈도 경계 부근에 트래픽이 집중되는 경우 시스템에 설정된 한도보다 많은 요청을 처리하게 된다는 것이다. 이동 윈도 로깅 알고리즘은 이 문제를 해결한다.

• 이 알고리즘은 요청의 타임스탬프를 추적한다. 타임스탬프 데이터는 보통 레디스의 정렬 집합(sorted set) 같은 캐시에 보관한다.
• 새 요청이 오면 만료된 타임스탠프는 제거한다. 만료된 타임스탬프는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 마랗ㄴ다.
• 새 요청의 타임스탬프를 로그에 추가한다.
• 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. 그렇지 않은 경우에는 처리를 거부한다.

이에 대한 구체적 사례

• 요청이 1:00:01에 도착하였을 때, 로그는 비어있는 상태다. 따라서 요청은 허용된다.
• 새로운 요청이 1:00:30에 도착한다. 해당 타임스탬프가 로그에 추가된다. 추가 직후 로그의 크기는 2이며, 허용한도보다 크지 않은 값이다. 따라서 요청은 시스템에 전달된다.
• 새로운 요청이 1:00:50에 도착한다. 해당 타임스탬프가 로그에 추가된다. 추가 직후 로그의 크기는 3으로, 허용 한도보다 큰 값이다. 따라서 타임스탬프는 로그에 남지만 요청은 거부된다.
• 새로운 요청이 1:01:40에 도착한다. [ 1:0040, 1:01:40) 범위 안에 있는 요청은 1분 윈도 안에 있는 요청이지만, 1:00:40 이전의 타임스탬프는 전부 만료된 값이다. 따라서 두 개의 만료된 타임스탬프 1:00:01과 1:00:30을 로그에서 삭제한다. 삭제 직후 로그의 크기는 2이다. 따라서 1:01:40 의 신규 요청은 시스템에 전달된다.

장점

• 이 알고리즘이 구현하는 처리율 제한 메커니즘은 아주 정교하다. 어느 순간의 윈도를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다.

단점

• 이 알고리즘은 다량의 메모리를 사용하는데, 거부된 요청의 타임스탬프도 보관하기 때문이다.

이동 윈도 카운터 알고리즘

이동 윈도 카운터 알고리즘은 고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것이다.

처리율 제한 장치의 한도가 분당 7개 요청으로 설정되어 있다고 하고, 이전 1분 동안 5개의 요청이, 그리고 현재 1분 동안 3개의 요청이 왔다고 해 보자. 현재 1분의 30% 시점에 도착한 새 요청의 경우, 현재 윈도에 몇 개의 요청이 온 것으로 보고 처리해야 할까? 다음과 같이 계산한다.

• 현재 1분 간의 요청 수 + 직전 1분 간의 요청 수 X 이동 윈도와 직전 1분이 겹치는 비율
• 이 공식에 따르면 현재 윈도에 들어 있는 요청은 3 + 5 X 70% = 6.5개다. 반올림해서 쓸 수도 있고 내림하여 쓸 수도 있는데, 본 예제에서는 내림하여 쓰겠다 따라서 그 값은 6이다.

본 예제의 경우 처리율 제한 한도가 분당 7개 요청이라고 했으므로, 현재 1분의 30%^ 시점에 도착한 신규 요청은 시스템으로 전달될 것이다. 하지만 그 직후에는 한도에 도달했으므로 더 이상의 요청은 받을 수 없을 것이다.

장점

• 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다.
• 메모리 효율이 좋다.

단점

• 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨하다.

데이터베이스는 디스크 접근 때문에 느리니까 사용하면 안 될 것이다. 메모리상에서 동작하는 캐시가 바람직한데, 빠른데다 시간에 기반한 만료 정책을 지원하기 때문이다.

• 클라이언트가 처리율 제한 미들웨어에게 요청을 보낸다.
• 처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와서 한도에 도달했는지 아닌지를 검사한다.
  • 한도에 도달했다면 요청은 거부된다.
• 한도에 도달하지 않았다면 요청은 API 서버로 전달된다. 한편 미들웨어는 카운터의 값을 증가시킨 후 다시 레디스에 저장한다.

처리율 한도 초과 트래픽의 처리

클라이언트는 자기 요청이 처리율 제한에 걸리고 있는지를(throttle) 어떻게 감지할 수 있나? 자기 요청이 처리율 제한에 걸리기까지 얼마나 많은 요청을 보낼 수 있는지 어떻게 알 수 있나? 답은 HTTP 응답 헤더(response header)에 있다.

• X-Ratelimit-Remaining: 윈도 내에 남은 처리 가능 요청의 수
• X-Ratelimit-Limit: 매 윈도마다 클라이언트가 전송할 수 있는 요청의 수
• X-Ratelimit-Retry-After: 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림

사용자가 너무 많은 요청을 보내면 429 too many requests 오류를 X-Ratelimit-Retry-After 헤더와 함께 반환하도록 한다.

• 클라이언트가 요청을 서버에 보내면 요청은 먼저 처리율 제한 미들웨어에 도달한다.
• 처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져온다. 아울러 카운터 및 마지막 요청의 타임스탬프를 레디스 캐시에서 가져온다. 가져온 값들에 근거하여 해당 미들웨어는 당므과 같은 결정을 내린다.
  • 해당 요청이 처리율 제한에 걸리지 않은 경우에는 API 서버로 보낸다.
  • 해당 요청이 처리율 제한에 걸렸다면 429 too many requests 에러를 클라이언트에 보낸다. 한편 해당 요청은 그대로 버릴 수도 있고 메시지 큐에 보관할 수도 있다.

경쟁 조건

처리율 제한 장치는 대략 다음과 같이 동작한다.

• 레디스에서 카운터의 값을 읽는다(counter).
• counter + 1의 값이 임계치를 넘는지 본다.
• 넘지 않는다면 레디스에 보관된 카운터 값을 1만큼 증가시킨다.

병행성이 심한 환경

레디스에 저장된 변수 counter의 값이 3이라고 하자. 그리고 두 개 요청을 처리하는 스레드가 각각 병렬로 counter 값을 읽었으며 그 둘 가운데 어느 쪽도 아직 변경된 값을 저장하지는 않은 상태라 해 보자. 둘 다 다른 요청의 처리 상태는 상관하지 않고 counter에 1을 더한 값을 레디스에 기록할 것이다. 그리고 counter의 값은 올바르게 변경되었다고 믿을 것이다. 하지만 사실 counter의 값은 5가 되어야 한다.

경쟁 조건 문제를 해결하는 가장 널리 알려진 해결책은 락이다. 하지만 락은 시스템의 성능을 상당히 떨어뜨린다는 문제가 있다. 위 설계의 경우에는 락 대신 쓸 수 있는 해결책이 두 가지 있는데, 하나는 루아 스크립트이고 다른 하나는 정렬 집합이라 불리는 레디스 자료구조를 쓰는 것이다.

동기화 이슈

수백만 사용자를 지원하려면 한 대의 처리율 제한 장치 서버로는 충분하지 않을 수 있다. 그래서 처리율 제한 장치 서버를 여러 대 두게 되면 동기화가 필요해진다.

클라이언트 1은 제한 장치 1에 요청을 보내고 클라이언트 2는 제한 장치 2에 요청을 보내고 있다. 다음 요청을 각기 다른 제한 장치로 보내게 될 수 있다.

이에 대한 한 가지 해결책은 고정 세션을 활용하여 같은 클라이언트로부터의 요청은 항상 같은 처리율 제한 장치 보낼 수 있도록 하는 것이다. 하지만 이 방법은 추천하고 싶지 않은데, 규모 면에서 확장 가능하지도 않고 유연하지도 않기 때문이다. 더 나은 해결책은 레디스와 같은 중앙 집중형 데이터 저장소를 쓰는 것이다.

마무리

• 경성(hard) 또는 연성(soft) 처리율 제한
  • 경성 처리율 제한: 요청의 개수는 임계치를 절대 넘어설 수 없다.
  • 연성 처리율 제한: 요청 개수는 잠시 동안은 임계치를 넘어설 수 있다.
• 다양한 계층에서의 처리율 제한
  • 이번 장에서는 애플리케이션 계층(OSI 기준 7번 계층)에서의 처리율 제한에 대해서만 살펴보았다. 하지만 다른 계층에서도 처리율 제한이 가능하다. 예를 들어, Iptables를 사용하면 Ip 주소 (IP는 OSI 기준으로 3번 계층)에 처리율 제한을 적용하는 것이 가능하다.
• 처리율 제한을 회피하는 방법, 클라이언트를 어떻게 설계하는 것이 최선인가?
  • 클라이언트 측 캐시를 사용하여 API 호출 횟수를 줄인다.
  • 처리율 제한의 임계치를 이해하고, 짧은 시간 동안 너무 많은 메시지를 보내지 않도록 한다.
  • 예외나 에러를 처리하는 노드를 도입하여 클라이언트가 예외적 상황으로부터 우아하게 복구될 수 있도록 한다.
  • 재시도 로직을 구현할 때는 충분한 백오프 시간을 둔다.

5장 시스템 설계 면접 공략법

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

해시 키 재배치(rehash) 문제

서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다. 예를 들어 1번 서버가 장애를 일으켜 동작을 중단했다고 하자. 그러면 서버 풀의 크기는 3으로 변한다. 그 결과로, 키에 대한 해시 값은 변하지 않지만 나머지(%) 연산을 적용하여 계산한 서버 인덱스 값은 달라질 것이다. 서버 수가 1만큼 줄어들어서다.

안정 해시

위키피디아에 따르면 "안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. 여기서 k는 키의 개수이고, n은 슬롯(slot)의 개수다. 이와는 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다."

가상 노드

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. 그림 5-12를 보면 서버 0과 서버 1은 3 개의 가상 노드를 갖는다. 여기서 숫자 3은 임의로 정한 것이며, 실제 시슽메에서는 그보다 훨씬 큰 값이 사용된다. 서버 0을 링에 배치하기 위해 s0 하나만 쓰는 대신, s0_0, s0_1, s0_2의 세 개 가상 노드를 사용하였다. 마찬가지로 서버 1을 링에 배치할 때는 s1_0, s1_1, s1_2의 세 개 가상 노드를 사용했다. 따라서 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 한다.

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다. 표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도다.

가상 노드의 개수를 더 늘리면 표준 편차의 값은 더 떨어진다. 그러나 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 될 것이다. 타협적 결정이 필요하다는 뜻이다.

요약

안정 해시의 이점

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
• 핫스팟 키 문제를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있다. 케이티 페리, 저스틴 비버, 레이디 가가 같은 유명인의 데이터가 전부 같은 샤드에 몰리는 상황을 생각해 보면 이해가 쉬울 것이다. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄인다.

안정 해시가 쓰이는 예시

• 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
• 아파치 카산드라 클러스터에서의 데이터 파티셔닝
• 디스코드 채팅 어플리케이션

6장 키-값 저장소 설계

키-값 쌍에서의 키는 유일해야 하며 해당 키에 매달린 값은 키를 통해서만 접근할 수 있다. 키는 일반 텍스트일 수도 있고 해시 값일 수도 있다. 성능상의 이유로, 키는 짧을수록 좋다. 아래는 키의 몇 가지 사례다.

• 일반 텍스트 키: "last_logged_in_at"
• 해키 키: 253DDEC4

다음 특성을 갖는 키-값 저장소를 설계해 보자.

• 키-값 쌍의 크기는 10KB 이하이다.
• 큰 데이터를 저장할 수 있어야 한다.
• 높은 가용성을 제공해야 한다. 따라서 시스템은 설사 장애가 있더라도 빨리 응답해야 한다.
• 높은 규모 확장성을 제공해야 한다. 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다.
• 데이터 일관성 수준은 조정이 가능해야 한다.
• 응답 지연시간이 짧아야 한다.

많은 데이터를 저장하려면 분산 키-값 저장소를 만들 필요가 있다.

분산 키-값 저장소

분산 키-값 저장소는 분산 해시 테이블이라고도 불린다. 키-값 쌍을 여러 서버에 분산시키는 탓이다. 분산 시스템을 설계할 때는 CAP 정리(Consistency, Availability, Partition Tolerance theorem)를 이해하고 있어야 한다.

CAP 정리

CAP 정리는 데이터 일관성, 가용성, 파티션 감내라는 세 가지 요구사항을 동시에 만족ㅎ하는 분산 시스템을 설계하는 것은 불가능하다는 정리다. 우선 각 요구사항의 의미부터 명확히 정리하고 넘어가자.

• 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.
• 가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
• 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다.

CAP 정리는 이들 가운데 어떤 두 가지를 충족핳려면 나머지 하나는 반드시 희생되어야 한다는 것을 의미한다.

키-값 저장소는 앞서 제싷한 세 가지 요구사항 가운데 어느 두 가지를 만족하느냐에 따라 다음과 같이 분류할 수 있다.

• CP 시스템: 일관성과 파티션 감내를 지웒하는 키-값 저장소. 가용성을 희생한다.
• AP 시스템: 가용성과 파티션 감내를 지웒하는 키-값 저장소. 데이터 일관성을 희생한다.
• CA 시스템: 일관성과 가용성을 지원하는 키-값 저장소. 파티션 감내는 지원하지 않는다. 그러나 통상 네트워크 장애는 피할 수 없는 일로 여겨지므로, 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 한다. 그러므로 실세계에 CA 시스템은 존재하지 않는다.

분산 시스템은 파티션 문제를 피할 수 없다. 그리고 파티션 문제가 발생하면 우리는 일관성과 가용성 사이에서 하나를 선택해야 한다. 그림 6-3은 n3에 장애가 발생하여 n1 및 n2와 통신할 수 없는 상황을 보여주고 있다. 클라이언트가 n1 또는 n2에 기록된 데이터는 n3에 전달되지 않는다. n3에 기록되었으나 아직 n1 및 n2로 전달되지 않은 데이터가 있다면 n1과 n2는 오래된 사본을 갖고 있을 것이다.

가용성 대신 일관성을 선택한다면(CP) 세 서버 사이에 생길 수 있는 데이터 불일치 문제를 피하기 위해 n1과 n2에 대해 쓰기 연산을 중단시켜야 하는데, 그렇게 하면 가용성이 깨진다. 은행권 시스템은 보통 데이터 일관성을 양보하지 않는다. 예를 들어, 온라인 뱅킹 시스템이 계좌 최신 정보를 출력하지 못한다면 큰 문제일 것이다.

일관성 대신 가용성을 선택한 시스템(AP)은 설사 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야 한다. 아울러 n1과 n2는 계속 쓰기 연산을 허용할 것이고, 파티션 문제가 해결된 뒤에 새 데이터를 n3에 전송할 것이다.

데이터 파티션

데이터를 파티션 단위로 나눌 때는 다음 두 가지 문제를 중요하게 따져봐야 한다.

• 데이터를 여러 서버에 고르게 분산할 수 있는가
• 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가

-> 안정 해시

• 규모 확장 자동화: 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있다.
• 다양성: 각 서버의 용량에 맞게 가상노드의 수를 조정할 수 있다.

데이터 다중화

데이터를 N개 서버에 비동기적으로 다중화(replication)할 필요가 있다.

노드를 선택할 때 같은 물리 서버를 중복 선택하지 않도록 해야 한다.

데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다. 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다.

• N = 사본 개수
• W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 한다.
• R = 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답을 받아야 한다.

W, R, N의 값을 정하는 것은 응답 지연과 데이터 일관성 사이의 타협점을 찾는 전형적인 과정이다. W=1 또는 R=1인 구성의 경우 중재나느 한 대 서버로부터의 응답만 받으면 되니 응답속도는 빠를 것이다. W나 R의 값이 1보다 큰 경우에는 시스템이 보여주는 데이터 일관성의 수준은 향상될 테지만 중재자의 응답 속도는 가장 느린 서버로부터의 응답을 기다려야 하므로 느려질 것이다.

• R=1, W=N: 빠른 읽기 연산에 최적화된 시스템
• W=1, R=N: 빠른 쓰기 연산에 최적화된 시스템
• W+R>N: 강한 일관성이 보장됨
• W+R<=N: 강한 일관성이 보장되지 않음

일관성 모델

• 강한 일관성: 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 다시 말해서 클라이언트는 절대로 낡은 데이터를 보지 못한다.
• 약한 일관성: 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.
• 최종 일관성: 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화)되는 모델이다.

강한 일관성을 달성하는 일반적인 방법은, 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금짛하는 것이다. 이 방법은 고가용성 시스템에는 적합하지 않다. 새로운 요청의 처리가 중단되기 때문이다.

최종 일관성 모델을 따를 경우 쓰기 연산이 병렬적으로 발생하면 시스템에 저장된 값의 일관성이 깨어질 수 있는데, 이 문제는 클라이언트가 해결해야 한다. 클라이언트 측에서 데이터의 버전 정보를 활용해 일관성이 깨진 데이터를 읽지 않도록 하는 기법.

비 일관성 해소 기법: 데이터 버저닝

버저닝은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미한다. 따라서 각 버전의 데이터는 변경 불가능하다.

벡터 시계는 [서버,버전]의 순서쌍을 데이터에 매단 것이다. 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는 데 쓰인다.

벡터 시계를 사용하면 어떤 버전 X가 버전 Y의 이전 버전인지(따라서 충돌이 없는지) 쉽게 판단할 수 있다. 버전 Y에 포함된 모든 구성요소의 값이 X에 포함된 모든 구성요소 값보다 같거나 큰지만 보면 된다. 예를 들어 벡터 시계 D([s0, 1])은 D([s0,1], [s1,2]의 이전 버전이다.

시스템 아키텍처 다이어그램

• 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, 즉 get(key) 및 put(key, value)와 통신한다.
• 중재자는 클라이언트에게 키-값 저장소에 대한 프락시(proxy) 역할을 하는 노드다.
• 노드는 안정 해시(consistent hash)의 해시 링(hash ring) 위에 분퐇한다.

쓰기 경로

1. 쓰기 요청이 커밋 로그 파일에 기록된다.
2. 데이터가 메모리 캐시에 기록된다.
3. 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도닳하면 데이터는 디스크에 있는 SSTable에 기록된다. SSTable은 Sorted-String Table의 약어로 <키,값>의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블이다.

읽기 경로

읽기 요청을 받은 노드는 데이터가 메모리 캐시에 있는지부터 살핀다. 있는 경우에는 해당 데이터를 클라이언트에게 반환한다.

데이터가 메모리에 없는 경우에는 디스크에서 가져와야 한다. 어느 SSTable에 찾는 키가 있는지 알아낼 효율적인 방법이 필요할 것이다. 이런 문제를 푸는 데는 블룸 필터가 흔히 사용된다.

1. 데이터가 메모리에 있는지 검사한다. 없으면 2로 간다.
2. 데이터가 메모리에 없으므로 블룸 필터를 검사한다.
3. 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아낸다.
4. SSTable에서 데이터를 가져온다.
5. 해당 데이터를 클라이언트에게 반환한다.

요약

목표/문제	기술
대규모 데이터 저장	안정 해시를 사용해 서버들에 부하 분산
읽기 연산에 대한 높은 가용성 보장	데이터를 여러 데이터센터에 다중화
쓰기 연산에 대한 높은 가용성 보장	버저닝 및 벡터 시계를 사용한 충돌 해소
데이터 파티션	안정 해시
점진적 규모 확장성	안정 해시
다양성	안정 해시
조절 가능한 데이터 일관성	정족수 합의
일시적 장애 처리	느슨한 정족수 프로포콜과 단서 후 임시 위탁
영구적 장애 처리	머클 트리
데이터 센터 장애 대응	여러 데이터 센터에 걸친 데이터 다중화

7장 분산 시스템을 위한 유일 ID 생성기 설계

이번 장에서는 분산 시스템에서 사용될 유일 ID 생성기를 설계해볼 것이다. 이 질문을 받았을 때 'auto_incrememt 속성이 설정된 관계형 데이터 베이스의 기본 키를 쓰면 되지 않을까?'하고 생각할지도 모르겠다. 하지만 분산 환경에서 이 접근법은 통하지 않을 텐데, 데이터베이스 서버 한 대로는 그 요구를 감당할 수 없을뿐더러, 여러 데이터베이스 서버를 쓰는 경우에는 지연 시간을 낮추기가 무척 힘들 것이기 때문이다.

• ID는 유일해야 한다.
• ID는 숫자로만 구성되어야 한다.
• ID는 64비트로 표현될 수 있는 값이어야 한다.
• ID는 발급 날짜에 따라 정렬 가능해야 한다.
• 초당 10,000개의 ID를 만들 수 있어야 한다.

다음과 같은 선택지가 있다.

• 다중 마스터 복제
• UUID
• 티켓 서버
• 트위터 스노플레이크 접근법

다중 마스터 복제

이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 것이다. 다만 ID의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킨다. 여기서 k는 현재 사용 중인 데이터베이스 서버의 수다.

이 방법은 다음과 같은 중대한 단점이 있다.

• 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
• ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수 없다.
• 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

UUID

UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다. UUID 값은 충돌 가능성이 지극히 낮다. 위키피디아를 인용하면 "중복 UUID가 1개 생길 확률을 50%로 끌어 올리려면 초당 10억 개의 UUID를 100년 동안 계속 만들어야 한다."

티켓 서버

티켓 서버는 유일성이 보장되는 ID를 만들어 내는 데 쓰일 수 있는 또 하나의 흥미로운 방법이다. 플리커는 분산 기본 키를 만들어 내기 위해 이 기술을 이용하였다.

이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.

트위터 스노플레이크 접근법

각개 격파 전략을 먼저 적용하는 것.

생성해야 하는 ID의 구조를 여러 절로 분할하는 것이다.

• 사인 비트: 1비트를 할당한다. 지금으로서는 쓰임새가 없지만 나중을 위해 유보해 둔다.
• 타임스탬프: 41비트를 할당한다.
• 데이터센터: 5비트를 할당한다. 따라서 2^5 =32개 데이터센터를 지원할 수 있다.
• 서버 ID: 5비트를 할당한다.
• 일련번호: 12비트를 할당한다.

8장 URL 단축기 설계

이 시스템의 기본적 기능은 아래와 같다.

1. URL 단축: 주어진 길 URL을 훨씬 짧게 줄인다.
2. URL 리디렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
3. 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨

개략적 추정

• 쓰기 연산: 매일 1억 개의 단축 URL 생성
• 초당 쓰기 연산: 1억/24/3600 = 1160
• 읽기 연산: 읽기 연산과 쓰기 연산 비율은 10:1이라고 하자. 그 경우 읽기 연산은 초당 11,600회 발생한다(1160x10 =11,600).
• URL 단축 서비스를 10년간 운영한다고 가정ㅎ하면 1억 365 x 10 = 1650억 개의 레코드를 보관해야 한다.
• 축약 전 URL의 평균 길이는 100이라 하자.
• 따라서 10년 동안 필요한 저장 용략은 3650억 x 100 바이트 = 36.5TB이다.

API 엔드포인트

1. URL 단축용 엔드포인트 -> POST -> 원래 URL을 받아서 단축된 URL을 반환
2. URL 리디렉션용 엔드포인트 -> GET -> 단축 URL을 받아서 원래 URL을 반환

URL 리디렉션

단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어 반환한다.

• 301 Permanently Moved: 이 응답은 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시한다. 따라서 추후 같은 단축 URL에 요청을 보낼 필요가 있을 때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
• 302 Found: 이 응답은 주어진 URL로의 요청이 '일시적으로' Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다. 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리디렉션 되어야 한다.

URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것이다. 해시 테이블에 <단축 URL, 원래 URL>의 쌍을 저장한다고 가정하면, URL 리디렉션은 다음과 같이 구현될 수 있을 것이다.

• 원래 URL = hashTable.get(단축 URL)
• 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송

URL 단축

단축 URL이 www.tinyurl.com/{hashValue} 같은 형태라고 해 보자. 결국 중요한 것은 긴 URL을 이 해시 값으로 대응시킬 해시 함수 fx를 찾는 일이 될 것이다.

이 해시 함수는 다음 요구사항을 만족해야 한다.

• 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 한다.
• 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.

데이터 모델

id, shortURL, longURL

해시 함수

해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다.

해시 함수가 만들 수 있는 URL의 개수 사이의 관계에서, n=7이면 3.5개의 URL을 만들 수 있다.

base-62 변환

진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다. 이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경유에 유용하다.

62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문이다.

해시 후 충돌 해소 전략과 base-62 변환 비교

해시 후 충돌 해소 전략	base-62 변환
단축 URL의 길이가 고정됨	단축 URL의 길이가 가변적. ID 값이 커지면 같이 길어짐
유일성이 보장되는 ID 생성기가 필요치 않음	유일성 보장 ID 생성기가 필요
충돌이 가능해서 해소 전략이 필요	ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능
ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능	ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 URL이 무엇인지 쉽게 알아내서 보안상 문제 소지 있음

URL 단축기 상세 설계

1. 입력으로 긴 URL을 받는다.
2. 데이터베이스에 해당 URL이 있는지 검사한다.
3. 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것이다. 따라서 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환한다.
4. 데이터베이스에 없는 경우에는 해당 URL은 새로 접수된 것이므로 유일한 ID를 생성한다. 이 ID는 데이터베이스의 기본 키로 사용된다.
5. 62진법 변환을 적용, ID를 단축 URL로 만든다.
6. ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에 전달한다.

URL 리디렉션 상세 설계

1. 사용자가 단축 URL을 클릭한다.
2. 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
3. 단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에게 전달한다.
4. 캐시에 해당 단축 URL이 없는 경우에는 데이터베이스에서 꺼낸다. 데이터베이스에 없다면 아마 사용자가 잘못된 단축 URL을 입력한 경우일 것이다.
5. 데이터베이스에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.

9장 웹 크롤러 설계

웹 크롤러의 기본 알고리즘은 간단하다.

1. URL 집합이 입력으로 주어지면, 해당 URL들이 가리키는 모든 웹 페이지를 다운로드한다.
2. 다운받은 웹 페이지에서 URL들을 추출한다.
3. 추출된 URL들을 다운로드할 URL 목록에 추가하고 위의 과정을 처음부터 반복한다.

매달 10억 개의 웹 페에지를 수집해야 한다고 했을 때,

개략적 규모 추정

• 매달 10억 개의 웹 페이지를 다운로드한다.
• QPS = 10억/30일/24시간/3600초 = 대략 400페이지/초
• 최대(Peak) QPS = 2 x QPS = 800
• 웹 페이지의 크기 평균은 500k라고 가정
• 10억 페이지 x 500k = 500TB/월.
• 1개월치 데이터를 보관하는 데는 500TB.

개략적 설계안

시작 URL 집합

시작 URL 집합은 웹 크롤러가 크롤링을 시작하는 출발점이다. 예를 들어, 어떤 대학 웹사이트로부터 찾아 나갈 수 있는 모든 웹 페이지를 크롤링하는 가장 직관적인 방법은 해당 대학의 도메인 이름이 붙은 모든 페이지의 URL을 시작 URL로 쓰는 것이다.

미수집 URL 저장소

대부분의 현대적 웹 크롤러는 크롤링 상태를 (1) 다운로드할 URL, 그리고 (2) 다운로드된 URL의 두 가지로 나눠 관리한다. 이 중 '다운로드할 URL'을 저장 관리하는 컴포넌트를 미수집 URL 저장소라고 부른다. FIFO 큐라고 생각하면 된다.

HTML 다운로더

HTML 다운로더는 인터넷에서 웹 페이지를 다운로드하는 컴포넌트다. 다운로드할 페이지의 URL은 미수집 URL 저장솨가 제공한다.

도메인 이름 변환기

웹 페이지를 다운받으려면 URL을 IP 주소로 변환하는 절차가 필요하다. HTML 다운로더는 도메인 이름 변환기를 사용하여 URL에 대응되는 IP 주소를 알아낸다.

컨텐츠 파서

웹 페이지를 다운로드 하려면 파싱과 검증 절차를 거쳐야 한다. 이상한 웹 페이지는 문제를 일으킬 수 있는데다 저장 공간만 낭비하게 되기 때문이다.

중복 콘텐츠인가?

두 HTML 문서를 비교하는 가장 간단한 방법은 그 두 문서를 문자열로 보고 비교하는 것이겠지만, 비교 대상 문서의 수가 10억에 닳하는 경우에는 느리고 비효율적이어서 적용하기 곤란할 것이다. 효과적인 방법은 웹 페이지의 해시 값을 비교하는 것이다.

콘텐츠 저장소

본 설계안의 경우 디스크와 메모리를 동시에 사용하는 저장소를 택할 것이다.

• 데이터 양이 너무 많으므로 대부분의 콘텐츠는 디스크에 저장한다.
• 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄일 것이다.

URL 추출기

URL 추출기는 HTML 페이지를 파싱하여 링크들을 골라내는 역할을 한다. 상대 경로 -> 절대 경로

URL 필터

URL 필터는 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속 시 오류가 발생하는 URL, 접근 제외 목록에 포함된 URL 등을 크롤링 대상에서 배제하는 역할을 한다.

이미 방문한 URL?

해당 자료 구조로는 블룸 필터나 해시 테이블이 널리 쓰인다.

URL 저장소

URL 저장소는 이미 방문한 URL을 보관하는 저장소다.

웹 크롤러 작업 흐름

1. 시작 URL들을 미수집 URL 저장소에 저장한다.
2. HTML 다운로더는 미수집 URL 저장소에서 URL 목록을 가져온다.
3. HTML 다운로더는 도메인 이름 변환기를 사용하여 URL의 IP 주소를 알아 내고, 해당 IP 주소로 접속하여 웹 페이지를 다운받는다.
4. 콘텐츠 파서는 다운된 HTML 페이지를 파싱하여 올바른 형식을 갖춘 페이지인지 검증한다.
5. 콘텐츠 파싱과 검증이 끝나면 중복 콘텐츠인지 확인하는 절차를 개시한다.
6. 중복 콘텐츠인지 확읺하기 위해서, 해당 페이지가 이미 저장소에 있는지 본다.
   • 이미 저장소 엤는 경우 처리하지 않고 버린다.
   • 저장소에 없는 콘텐츠인 경우에는 저장소에 저장한 뒤 URL 추출기로 전달한다.
7. URL 추출기는 해당 HTML 페이지에서 링크를 골라낸다.
8. 골라낸 링크를 URL 필터로 전달한다.
9. 필터링이 끝나고 남은 URL만 중복 URL 판별 단계로 전달한다.
10. 이미 처리한 URL 인지 확인하기 위하여, URL 저장소에 보관된 URL인지 살핀다. 이미 저장소에 있는 URL은 버린다.
11. 저장소에 없는 URL은 URL 저장소에 저장할 뿐 아니라 미수집 URL 저장소에도 전달한다.

상세 설계

DFS를 쓸 것인가, BFS를 쓸 것인가

DFS는 좋은 선택이 아닐 가능성이 높다. 그래프 크기가 클 경우 어느 정도로 깊숙이 가게 될지 가늠하기 어려워서다.

따라서 웹 크롤러는 보통 BFS를 사용한다. 큐를 이용한 구현 법에는 두 가지 문제점이 있다.

• 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다. 결국 크롤러는 같은 호스트에 속한 많은 링크를 다운받느라 바빠지게 되는데, 이때 링크들을 병렬로 처리하게 된다면 위키피디아 서버는 수많은 요청으로 과부하에 걸리게 될 것이다. 이런 크롤러는 보통 '예의 없는' 크롤러로 간주된다.
• 표준적 BFS 알고리즘은 URL 간에 우선순위를 두지 않는다. 처리 순서에 있어 모든 페이지를 공평하게 대우한다는 뜻이다. 하지만 모든 웹 페이지가 같은 수준의 품질, 같은 수준의 중요성을 갖니는 않는다. 그러니 페이지 순위, 사용자 트래픽 양, 업데이트 빈도 등 여러가지 척도에 비추어 처리 우선순위를 구별하는 것이 온당할 것이다.

미수집 URL 저장소

미수집 URL 저장소를 활용하면 이런 문제를 좀 쉽게 해결할 수 있다.

예의 바른 크롤러를 만드는 데 있어서 지켜야 할 한 가지 원칙은, 동일 웹 사이트에 대해서는 ㅎ한 번에 한 페이지만 요청한다는 것이다. 같은 웹 사이트의 페이지를 다운받는 태스트크는 시간차를 두고 실행하도록 하면 될 것이다. 이 요구사항을 만족시키려면 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다. 즉, 각 다운로드 스레드는 별도 FIFO 큐를 가지고 있어서, 해당 큐에서 꺼낸 URL만 다운로드 한다.

• 큐 라우터: 같은 호스트에 속한 URL은 언제나 같은 큐로 가도록 보장하는 역할을 한다.
• 매핑 테이블: 호스트 이름과 큐 사이의 관계를 보관하는 테이블
• FIFO 큐 : 같은 호스트에 속한 URL은 언제나 같은 큐에 보관된다.
• 큐 선택기: 큐 선택기는 큐들을 순회하면서 큐에서 URL을 꺼내서 해당 큐에서 나온 URL을 다운로드핳도록 지정된 작업 스레드에 전달하는 역할을 한다.
• 작업 스레드: 작업 스레드는 전달된 URL을 다운로드하는 작업을 수행한다. 전달된 URL은 순차적으로 처리될 것이며, 작업들 사이에는 일정한 지연시간을 둘 수 있다.

우선순위

유용성에 따라 URL의 우선순위를 나눌 때는 페이지랭크, 트래픽 양, 갱신 빈도 등 다양한 척도를 사용할 수 있을 것이다. 본 절에서 설명할 순위결정장치는 URL 우선순위를 정하는 컴포넌트다.

• 순위결정장치: URL을 입력으로 받아 우선순위를 계산한다.
• 큐: 우선순위별로 큐가 하나씩 할당된다. 우선순위가 높으면 선택될 확률도 올라간다.
• 큐 선택기: 임의 큐에서 처리할 URL을 꺼내는 역할을 담당한다.

두 개의 모듈로 프로세스를 진행한다.

• 전면 큐: 우선순위 결정 과정을 처리한다.
• 후면 큐: 크롤러가 예의 바르게 동작하도록 보증한다.

신선도

• 웹 페이지의 변경 이력 활용
• 우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집

미수집 URL 저장소를 윟한 지속성 저장장치

대부분의 URL은 디스크에 두지만 IO 비용을 줄이기 위해 메모리 버퍼에 큐를 두는 것이다. 버퍼에 있는 데이터는 주기적으로 디스크에 기록할 것이다.

HTML 다운로더

로봇 제외 프로토콜 - Robots.txt

로봇 제외 프로토콜이라고 부르기도 하는 Robots.txt는 웹사이트가 크롤러와 소통하는 표준적 방법이다. 이 파일에는 크롤러가 수집해도 되는 페이지 목록들이 들어 있다.

성능 최적화 방법

1. 분산 크롤링: 크롤링 작업을 여러 서버에 분산하는 방법. 각 서버는 여러 스레드를 돌려 다운로드 작업을 처맇한다.
2. 도메인이름 변환 결과 캐시: DNS 요청이 처리 되는 데는 보통 10ms에서 200ms가 소요된다. 크롤러 스레드 가운데 어느 하나라도 이 작업을 하고 있으면 다른 스레드의 DNS 요청은 전부 블록된다. 따라서 DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡을 돌려 주기적으로 갱신하도록 해 놓으면 성능을 효과적으로 높일 수 있다.
3. 지역성: 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법이다.
4. 짧은 타임아웃: 최대 얼마나 기다릴지를 미리 정해두는 것이다.

10장 알림 시스템 설계

알림 유형

• APNS -> IOS
• FCM -> 안드로이드
• SMS서비스 -> SMS
• 이메일 서비스 -> 이메일

개략적 설계안

• 1부터 N까지의 서비스 -> 알림 시스템 -> 제3자 서비스 -> 단말

이 설계의 문제점

• SPOF
• 규모 확장성: 한 대 서비스로 푸시 알림에 관계된 모든 것을 처리하므로 데이터베이스나 캐시 등 중요 컴포넌트의 규모를 개별적으로 늘릴 방법이 없다.
• 성능 병목: 알림을 처리하고 보내는 것은 자원을 많이 필요로 하는 작업일 수 있다.

개선 버전

• 데이터베이스와 캐시를 알림 시스템의 주 서버에서 분리한다.
• 알림 서버를 증설하고 자동으로 수평적 규모 확장이 이루어질 수 있도록 한다.
• 메시지 큐를 이용해 시스템 컴포넌트 사이의 강한 결합을 끊는다.

• 1부터 N까지의 서비스: 알림 시스템 서버의 API를 통해 알림을 보낼 서비스들
• 알림 서버: 다음 기능을 제공한다.
  • 알림 전송
  • 알림 검증
  • 데이터베이스 또는 캐시 질의
  • 알림 전송
• 캐시: 사용자 정보, 단말 정보, 알림 템플릿 등을 캐시
• 데이터베이스: 사용자, 알림, 설정 등 다양한 정보 저장
• 메시지 큐: 시스템 컴포넌트 간 의존성을 제거하기 위해 사용
• 작업 서버: 메시지 큐에서 전송할 알림을 꺼내서 제 3자 서비스로 전달하는 역할 담당
• 제 3자 서비스 및 단말

알림 전송 프로세스

1. API를 호출하여 알림 서버로 알림 보낸다.
2. 알림 서버는 사용자 정보, 단말 토큰, 알림 설정 같은 메타데이털르 캐시나 데이터베이스에서 가져온다.
3. 알림 서버는 전송할 알림에 맞는 이벤트를 만들어서 해당 이벤트를 위한 큐에 넣는다. 가령 iOS 푸시 알림 이벤트는 iOS 푸시 알림 큐에 넣어야 한다.
4. 작업 서버는 메시지 큐에서 알림 이벤트를 꺼낸다.
5. 작업 서버는 알림을 제3자 서비스로 보낸다.
6. 제3자 서비스는 사용자 단말로 알림을 전송한다.

안정성

데이터 손실 방지

사라지면 곤란하다 -> 알림 데이터를 데이터베이스에 보관하고 재시도 메커니즘을 구현해야 한다. 알림 로그 데이터베이스를 유지하는 것이 한 가지 방법이다.

알림 중복 전송 방지

같은 알림이 여러 번 반복되는 것을 완전히 막는 것은 가능하지 않다. 대부분의 경우 알림은 딱 한 번만 전송되겠지만, 분산 시스템의 특성상 가끔은 같은 알림이 중복되어 전송되기도 할 것이다. 그 빈도를 줄이려면 중복을 탐지하는 메커니즘을 도입하고, 오류를 신중하게 처리해야 한다.

• 보내야 할 알림이 도착하면 그 이벤트 ID를 검사하여 이전에 본 적이 있는 이벤트인지 살핀다. 중복된 이벤트라면 버리고, 그렇지 않으면 알림을 발송한다.

11장 뉴스 피드 시스템 설계

• 피드 발행: 사용자가 스토리를 포스팅하면 해당 데이터를 캐시와 데이터베이스에 기록한다. 새 포스팅은 친구의 뉴스 피드에도 전송된다.
• 뉴스 피드 생성: 지면 관계상 뉴스 피드는 모든 친구의 포스팅을 시간 흐름 역순으로 모아서 만든다고 가정한다.

피드 발행

• 사용자: 모바일 앱이나 브라우저에서 새 포스팅을 올리는 주체다. POST /v1/me/feed API를 사용한다.
• 로드밸런서: 트래픽을 웹 서버들로 분산한다.
• 웹서버: HTTP 요청을 내부 서비스로 중계하는 역할을 담당한다.
• 포스팅 저장 서비스: 새 포스팅을 데이터베이스와 캐시에 저장한다.
• 포스팅 전송 서비스: 새 포스팅을 친구의 뉴스 피드에 푸시한다. 뉴스 피드 데이터는 캐시에 보관하여 빠르게 읽어갈 수 있도록 한다.
• 알림 서비스: 친구들에게 새 포스팅이 올라왔음을 알리거나, 푸시 알림을 보내는 역할을 담당한다.

뉴스 피드 생성

• 사용자: 뉴스 피드를 읽는 주체다. GET /v1/me/feed API를 이용한다.
• 로드 밸런서: 트래픽을 웹 서버들로 분산한다.
• 웹 서버: 트래픽을 뉴스 피드 서비스로 보낸다.
• 뉴스 피드 서비스: 캐시에서 뉴스 피드를 가져오는 서비스
• 뉴스 피드 캐시: 뉴스 피드를 렌더링할 때 필요한 피드 ID를 보관한다.

포스팅 전송 (팬아웃) 서비스

포스팅 전송, 즉 팬아웃(fanout)은 어떤 사용자의 새 포스팅을 그 사용자와 친구 관계에 있는 모든 사용자에게 전달하는 과정이다. 팬아웃에는 두 가지 모델이 있는데 하나는 쓰기 시점에 팬아웃 하는 모델이고, 다른 하나는 읽기 시점에 팬아웃하는 모델이다.

쓰기 시점에 팬아웃하는 모델

이 접근법의 경우 새로운 포스팅을 기록하는 시점에 뉴스 피드를 갱신하게 된다. 다시 말해, 포스팅이 완료되면 바로 해당 사용자의 캐시에 해당 포스팅을 기록하는 것이다.

장점

• 뉴스 피드가 실시간으로 갱신되며 친구 목록에 있는 사용자에게 즉시 전송
• 새 포스팅이 기록되는 순간에 뉴스 피드가 이미 갱신되므로 뉴스 피드를 읽는 데 드는 시간이 짧아진다

단점

• 친구가 많은 사용자의 경우 친구 목록을 가져오고 그 목록에 있는 사용자 모두의 뉴스 피드를 갱신하는 데 많은 시간이 소요될 수 있다. 핫키라고 부르는 문제다.
• 서비스를 자주 이용하지 않는 사용자의 피드까지 갱신해야 하므로 컴퓨팅 자원이 낭비된다.

읽기 시점에 팬아웃하는 모델

피드를 읽어야 하는 시점에 뉴스 피드를 갱신한다. 따라서 요청 기반 모델이다. 사용자가 본인 홈페이지나 타임 라인을 로딩하는 시점에 새로운 포스트를 가져오게 된다.

장점

• 비활성화된 사용자, 또는 서비스에 거의 로그인하지 않는 사용자의 경우에 유리하다.
• 데이터를 친구 각각에 푸시하는 작업이 필요 없으므로 핫키 문제도 생기지 않는다.

단점

• 뉴시 피드를 읽는 데 많은 시간이 소요될 수 있다

본 설계안의 경우에는 이 두 가지 방법을 결합하여 장점은 취하고 단점은 버리는 전략을 취하도록 하겠다. 뉴스 피드를 빠르게 가져올 수 있도록 하는 것은 아주 중요하므로 대부분의 사용자에 대해서는 푸시 모델을 사용한다. 친구나 팔로어가 아주 많은 사용자의 경우에는 팔로어로 하여금 해당 사용자의 포스팅을 필요할 때 가져가도록 하는 풀 모델을 사용하여 시스템 과부하를 방지할 것이다. 아울러 안정 해시를 통해 요청과 데이터를 보다 고르게 분산하여 핫키 문제를 줄여볼 것이다.

팬아웃 서비스는 다음과 같이 동작한다.

1. 그래프 데이터베이스에서 친구 ID 목록을 가져온다. 그래프 데이터베이스는 친구 관계나 친구 추천을 관리하기 적합하다.
2. 사용자 정보 캐시에서 친구들의 정보를 가져온다. 그런 후에 사용자 설정에 따라 친구 가운데 일부를 걸러낸다. 예를 들어 여러분이 친구 중 누군가의 피드 업데이트를 무시하기로 결정했다면 친구 관계는 유지될지언정 해당 사용자의 새 스토리는 여러분의 뉴스 피드에 보이지 않아야 한다. 새로 포스팅된 스토리가 일부 사용자에게만 공유되도록 설정된 경우에도 비슷한 일이 벌어질 것이다.
3. 친구 목록과 새 스토리의 포스팅 ID를 메시지 큐에 넣는다.
4. 팬아웃 작업 서버가 메시지 큐에서 데이터를 꺼내어 뉴스 피드 데이터를 뉴스 피드 캐시에 넣는다. 뉴스피드 캐시는 <포스팅 ID, 사용자 ID>의 순서쌍을 보관하는 매핑 테이블이라고 볼 수 있다.

뉴스 피드 흐름 상세 설계

1. 사용자가 뉴스 피드를 읽으려는 요청을 보낸다. 요청은 /v1/me/feed로 전송될 것이다.
2. 로드밸런서가 요청을 웹 서버 가운데 하나로 보낸다.
3. 웹 서버는 피드를 가져오기 위해 뉴스 피드 서비스를 호출한다.
4. 뉴스 피드 서비스는 뉴스 피드 캐시에서 포스팅 ID 목록을 가져온다.
5. 뉴스 피드에 표시할 사용자 이름, 사용자 사진, 포스팅 콘텐츠, 이미지 등을 사용자 캐시와 포스팅 캐시에서 가져와 완전한 뉴스 피드를 만든다.
6. 생성된 뉴스 피드를 JSON 형태로 클라이언트에게 보낸다. 클라이언트는 해당 피드를 렌더링한다.

캐시 구조

캐시는 뉴스 피드 시스템의 핵심 컴포넌트다.

• 뉴스 피드: 뉴스 피드의 ID를 보관한다.
• 콘텐츠: 포스팅 데이터를 보관한다. 인기 콘텐츠는 따로 보관한다.
• 소셜 그래프: 사용자 간 관계 정보를 보관한다.
• 행동: 포스팅에 대한 사용자의 행위에 관한 정보를 보관한다. 포스팅에 대한 '좋아요', 답글 등등이 이에 해당한다.
• 횟수: '좋아요' 횟수, 응답 수, 팔로어 수, 팔로잉 수 등의 정보를 보관한다.

12장 채팅 시스템 설계

• 응답지연이 낮은 일대일 채팅 기능
• 최대 100명까지 참여할 수 있는 그룹 채팅 기능
• 사용자의 접속상태 표시 기능
• 다양한 단말 지원. 하나의 계정으로 여러 단말에 동시 접속 지원
• 푸시 알림
• 5천만 DAU

채팅 서비스는 아래 기능을 제공해야 한다.

• 클라이언트들로부터 메시지 수진
• 메시지 수신자 결정 및 전달
• 수신자가 접속 상태가 아닌 경우에는 접속할 때까지 해당 메시지 보관

대부분의 클라이언트/서버 애플리케이션에서 요청을 보내는 것은 클라이언트인데, 채팅 시스템의 경우도 마찬가지다. 메시지 송신 클라이언트(sender)가 이 역할을 한다. 송신 클라이언트는 수신 클라이언트에게 전달할 메시지를 채팅 서비스에 보낼 때, 오랜 세월 검증된 HTTP 프로토콜을 사용한다.

클라이언트는 채팅 서비스에 HTTP 프로토콜로 연결한 다음 메시지를 보내어 수신자에게 해당 메시지를 전달하라고 알린다. 채팅 서비스와의 접속에는 keep-alive 헤더를 사용하면 효율적인데, 클라이언트와 서버 사이의 연결을 끊지 않고 계속 유지할 수 있어서다. TCP 접속 과정에서 발생하는 핸드셰이크 횟수를 줄일 수 있음은 물론이다. HTTP는 메시지 전송 용도로는 괜찮은 선택이며, 페이스북 같은 많은 대중적 채팅 프로그램이 초기에 HTTP를 사용했다.

하지만 메시지 수신 시나리오는 이것보다 복잡하다. HTTP는 클라이언트가 연결을 만드는 프로토콜이며, 서버에서 클라이언트로 임의 시점에 메시지를 보내는 데는 쉽게 쓰일 수 없다. 서버가 연결을 만드는 것철머 동작할 수 있도록 하기 위해 많은 기법이 제안되어 왔는데, 폴링, 롱 폴링, 웹소켓 등이 그런 기술이다.

폴링

폴링은 클라이언트가 주기적으로 서버에게 새 메시지가 있느냐고 물어보는 방법이다. 폴링 비용은 폴링을 자주하면 할수록 올라간다. 답해줄 메시지가 없는 경우에는 서버 자원이 불필요하게 낭비된다는 문제도 있다.

롱 폴링

폴링은 여러 가지로 비효율적일 수 있어서 나온 기법이 롱 폴링이다.

롱 폴링의 경우 클라이언트는 새 메시지가 반환되거나 타임아웃 될 때까지 연결을 유지한다. 클라이언트는 새 메시지를 받으면 기존 연결을 종료하고 서버에 새로운 요청을 보내어 모든 절차를 다시 시작한다. 다음과 같은 약점이 있다.

• 메시지를 보내는 클라이언트와 수신하는 클라이언트가 같은 채팅 서버에 접속하게 되지 않을 수도 있다. HTTP 서버들은 보통 무상태 서버다. 로드밸런싱을 위해 라운드 로빈 알고리즘을 사용하는 경우, 메시지를 받은 서번느 해당 메시지를 수신할 클라이언트와의 롱 폴링 연결을 가지고 있지 않은 서버일 수 있는 것이다.
• 서버 입장에서는 클라이언트가 연결을 해제했는지 아닌지 알 좋은 방법이 없다.
• 여전히 비효율적이다. 메시지를 많이 받지 않는 클라이언트도 타임아웃이 일어날 때마다 주기적으로 서버에 다시 접속할 것이다.

웹소켓

웹소켓은 서버가 클라이언트에게 비동기 메시지를 보낼 때 가장 널리 사용하는 기술이다.

웹소켓 연결은 클라이언트가 시작한다. 한번 맺어진 연결은 항구적이며 양방향이다. 이 연결은 처음에는 HTTP 연결이지만 특정 핸드셰이크 절차를 거쳐 웹소켓 연결로 업그레이드 된다. 일단 이 항구적인 연결이 만들어지고 나면 서버는 클라이언트에게 비동기적으로 메시지를 전송할 수 있다. 웹소켓은 일반적으로 방화벽이 있는 환경에서도 잘 동작한다. 80이나 443처럼 HTTP 혹은 HTTPS 프로토콜이 사용하는 기본 포트번호를 그대로 쓰기 때문이다.

개략적 설계안

무상태 서비스

무상태 서비스는 로드밸런서 뒤에 위치한다. 로드밸런서가 하는 일은 요청을 그 경로에 맞는 서비스로 정확하게 전달하는 것이다. 로드밸런서 뒤에 오는 서비스는 모놀리틱 서비스일 수도 있고 마이크로서비스일 수도 있다. 이 서비스들 가운데 상당수가 시장에 완제품으로 나와 있어서 우리가 직접 구현하지 않아도 쉽게 사서 쓸 수 있다.

상태 유지 서비스

유일하게 상태 유지가 필요한 서비스는 채팅 서비스다. 각 클라이언트가 채팅 서버와 독립적인 네트워크 연결을 유지해야 하기 때문이다. 클라이언트는 보통 서버가 살아 있는 한 다른 서버로 연결을 변경하지 않는다.

제 3자 서비스 연동

새 메시지를 받았다면 설사 앱이 실행 중이지 않더라도 알림을 받아야 한다.

규모 확장성

트래픽 규모가 얼마 되지 않을 때는 방금 설명한 모든 기능을 서버 한 대로 구현할 수 있다. 우리가 지금 설계 중인 시스템의 경우처럼 대량의 트래픽을 처리해야 하는 경우에도 이론적으로는 모든 사용자 연결을 최신 클라우드 서버 한 대로 처리할 수 있기는 하다. 이때 따져봐야 할 것은 서버 한 대로 얼마나 많은 접속을 동시에 허용할 수 있느냐다. 이번 장에서 다루는 시스템의 경우에는 동시 접속자가 1M이라고 가정할 것인데, 접속당 10K의 서버 메모리가 필요하다고 본다면 10GB 메모리만 있으면 모든 연결을 다 처리할 수 있을 것이다.

• 채팅 서버는 클라이언트 사이에 메시지를 중계하는 역할을 담당한다.
• 접속상태 서버는 사용자의 접속 여부를 관리한다.
• API 서버는 로그인, 회원가입, 프로파일 변경 등 그 외 나머지 전부를 처리한다.
• 알림 서버는 푸시 알림을 보낸다.
• 키-값 저장소에는 채팅 이력을 보괂한다. 시스템에 접속한 사용자는 이전 채팅 이력을 전부 보게 될 것이다.

저장소

이제 서버도 준비되었고 제3자 서비스 연동도 끝났다고 하자. 이 기술 스택 깊은 곳에 데이터 계층이 있다. 데이터 계층을 올바르게 만드는 데는 노력이 필요하다. 중요한 것 하나는 어떤 데이터베이스를 쓰느냐다.

채팅 시스템이 다루는 데이터는 보통 두 가지다. 첫 번째는 사용자 프로파일, 설정, 친구 목록처럼 일반적인 데이터다. 이런 데이터는 안정성을 보장하는 관계형 데이터베이스에 보관한다. 다중화와 샤딩은 이런 데이터의 가용성과 규모확장성을 보증하기 위해 보편적으로 사용되는 기술이다.

두 번째 유형의 데이터는 채팅 시스템에 고유한 데이터로, 바로 채팅 이력이다. 이 데이터를 어떻게 보관할지 결정하려면 읽기/쓰기 연산 패턴을 이해해야 한다.

• 채팅 이력 데이터의 양은 엄청나다.
• 이 데이터 가운데 빈번하게 사용되는 것은 주로 최근에 주고받은 메시지다.
• 사용자는 대체로 최근에 주고받은 메시지 데이터만 보게 되는 것이 사실이나, 검색 기능을 이용하거나, 특정 사용자가 언급된 메시지를 보거나, 특정 메시지로 점프하거나 하여 무작위적인 데이터 접근을 하게 되는 일도 있다. 데이터 계층은 이런 기능도 지원해야 한다.
• 1:1 채팅 앱의 경우 읽기:쓰기 비율은 대략 1:1 정도다.

본 설계안의 경우에는 키-값 저장소를 추천할 것인데, 그 이유는 다음과 같다.

• 키-값 저장소는 수평적 규모확장이 쉽다.
• 키-값 저장소는 데이터 접근 지연시간이 낮다.
• 관계형 데이터베이스는 데이터 가운데 롱 테일에 해당하는 부분을 잘 처리하지 못하는 경향이 있다. 인덱스가 커지면 데이터에 대한 무작위적 접근을 처리하는 비용이 늘어난다.
• 이미 많은 안정적인 채팅 시스템이 키-값 저장소를 채택하고 있다. 페이스북 메신저나 디스코드가 그 사례다. 페이스북 메신저는 HBase를 사용하고 있고 디스코드는 카산드라를 이용하고 있다.

데이터 모델

1:1 채팅을 위한 메시지 테이블

message_id, message_from, message_to, content, created_at

그룹 채팅을 위한 메시지 테이블

channel_id, message_id, message_to, content, created_at

메시지 ID

message_id는 메시지들의 순서도 표현할 수 있어야 핳ㄴ다.

• message_id의 값은 고유해야 한다.
• ID 값은 정렬 가능해야 하며 시간 순서와 일치해야 한다. 즉, 새로운 ID는 이전 ID 보다 큰 값이어야 한다.

스노플레이크 or 지역적 순서 번호 생성기

여기서 지역적이라 함은, ID의 유일성은 같은 그룹 안에서만 보증하면 충분하다는 것이다. 이 방법이 통하는 이유는 메시지 사이의 순서는 같은 채널, 혹은 같은 1:1 채팅 세션 안에서만 유지되면 충분하기 때문이다.

메시지 흐름

1:1 채팅 메시지 처리 흐름

1. 사용자 A가 채팅 서버 1로 메시지 전송
2. 채팅 서버 1은 ID 생성기를 사용해 해당 메시지의 ID 결정
3. 채팅 서버 1은 해당 메시지를 메시지 동기화 큐로 전송
4. 메시지가 키-값 저장소에 보관됨
5. (a) 사용자 B가 접속 중인 경우 메시지는 사용자 B가 접속 중인 채팅 서버로 전송됨 (b) 사용자 B가 접속 중이 아니라면 푸시 알림 메시지를 푸시 알림 서버로 보냄
6. 채팅 서버 2는 메시지를 사용자 B에게 전송. 사용자 B와 채팅 서버 2 사이에는 웹소켓 연결이 있는 상태이므로 그것을 이용

여러 단말 사이의 메시지 동기화

사용자 A는 전화기와 랩톱의 두 대 단말을 이용하고 있다. 사용자 A가 전화기에서 채팅 앱에 로그인한 결과로 채팅 서버 1과 해당 단말 사이에 웹소켓연결이 만들어져 있고, 랩톱에서 로그인한 결과로 역시 별도 웹소켓이 채팅 서버 1에 연결되어 있는 상황이다.

각 단말은 cur_max_message_id 라는 변수를 유지하는데, 해당 단말에서 관측된 가장 최신 메시지의 ID를 추적하는 용도다. 아래 두 조건을 만족하는 메시지는 새 메시지로 간주한다.

• 수신자 ID가 현재 로그인한 사용자 ID와 같다.
• 키-값 저장소에 보관된 메시지로서, 그 ID가 cur_max_message_id보다 크다.

cur_max_messagge_id는 단말마다 별도로 유지 관맇하면 되는 값이라 키-값 저장소에서 새 메시지를 가져오는 동기화 작업도 쉽게 구현할 수 있다.

소규모 그룹 채팅에서의 메시지 흐름

1:1 채팅에 빟해 그룹 채팅에서의 메시지 흐름은 조금 더 복잡하다.

사용자 A가 그룹 채팅 방에서 메시지를 보냈을 때 어떤 일이 벌어지는지 보자. 해당 그룹에 3명의 사용자가 있다고 하자. 우선 사용자 A가 보낸 메시지가 사용자 B와 C의 메시지 동기화 큐에 복사된다. 이 큐를 사용자 각각에 할당된 메시지 수신함 같은 것으로 생각해도 무방할 것이다.

• 새로운 메시지가 왔는지 확인하려면 자기 큐만 보면 되니까 메시지 동기화 플로가 단순하다.
• 그룹이 크지 않으면 메시지를 수신자별로 복사해서 큐에 넣는 작업의 비용이 문제가 되지 않는다.

위챗이 이런 접근법을 쓰고 있으며, 그룹의 크기는 500명으로 제한하고 있다. 하지만 많은 사용자를 지원해야 하는 경우라면 똑같은 메시지를 모든 사용자의 큐에 복사하는 게 바람직하지 않을 것이다.

지금 설명한 메시지 흐름을 수신자 관점에서 살펴보면, 한 수신자는 여러 사용자로부터 오는 메시지를 수신할 수 있어야 한다. 따라서 각 사용자의 수신함, 즉 메시지 동기화 큐는 여러 사용자로부터 오는 메시지를 받을 수 있어야 한다.

접속상태 표시

클라이언트와 실시간 서비스 사이에 웹소켓 연결이 맺어지고 나면 접속상태 서버는 A의 상태와 last_active_at 타임스탬프 값을 키-값 저장소에 보관한다. 이 절차가 끝나고 나면 해당 사용자는 접속 중인 것으로 표시될 것이다.

로그아웃 -> 키-값 저장소에 보관된 사용자 상태가 online에서 offline으로 바뀌게 설정

접속 장애

온라인 상태의 클라이언트로 하여금 주기적으로 박동 이벤트를 접속상태 서버로 보내도록 하고, 마지막 이벤트를 받은지 x초 이내에 또 다른 박동 이벤트 메시지를 받으면 해당 사용자의 접속상태를 계속 온라인으로 유지하는 것이다. 그렇지 않을 경우에만 오프라인으로 바꾸는 것이다.

상태 정보의 전송

상태정보 서버는 발행-구독 모델을 사용하는데, 즉 각각의 친구관계마다 채널을 하나씩 두는 것이다. 가령 사용자 A의 접속상태가 변경되었다고 하자. 그 사실을 세 개 채널, 즉 A-B, A-C, A-D에 쓰는 것이다. 그리고 A-B는 사용자 B가 구독하고, A-C는 사용자 C가, 그리고 A-D는 사용자 D가 구독하도록 하는 것이다. 이렇게 하면 친구 관계에 있는 사용자가 상태정보 변화를 쉽게 통지받을 수 있게 된다. 클라이언트와 서버 사이의 통신에는 실시간 웹소켓을 사용ㅎ한다.

그룹 크기가 더 커지면 이런 식으로 접속상태 변화를 알려서는 비용이나 시간이 많이 들게 되므로 좋지 않다. 가령 그룹 하나에 100,000 사용자가 있다고 하자. 그러면 상태 변화 1건당 100,000 개의 이벤트 메시지가 발생하 것이다. 이런 성능 문제를 해소하는 한 가지 방법은 사용자가 그룹 채팅에 입장하는 순간에만 상태 정보를 읽어가게 하거나, 친구 리스트에 있는 사용자의 접속 상태를 갱신하고 싶으면 수동으로 하도록 유도하는 것이다.

13장 검색어 자동완성 시스템

• 빠른 응답 속도: 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빨리 표시되어야 한다. 페이스북 검색어 자동완성 시스템에 관한 문서를 보면 시스템 응답속도는 100밀리초 이내여야 한다.
• 연관성: 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 한다.
• 정렬: 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬되어 있어야 한다.
• 규모 확장성: 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 한다.
• 고가용성: 시스템의 일부에 장애가 발생하거나, 느려지거나, 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용 가능해야 한다.

계략적 규모 측정

• 일간 능동 사용자 천 만명
• 평균적으로 한 사용자가 매일 10건의 검색을 수행
• 질의할 때마다 평균적으로 20바이트의 데이터를 입력
• 검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다. 따라서 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다. 예를 들어 여러분이 검색창에 dinner라고 입력하면 다음의 6개 요청이 순차적으로 백엔드에 전송된다.

search?q=d
search?q=di
search?q=din
search?q=dinn
search?q=dinne
search?q=dinner

• 대략 초당 24,000건의 질의가 발생할 것이다.(=10,000,000사용자 x 10 질의 / 일 x 20자 / 24 시간 / 3600 초)
• 최대 QPS => 48,000
• 질의 가운데 20% 정도는 신규 검색어라고 가정할 것이다. 따라서 대략 0.4GB 정도다. 매일 0.4GB의 신규 데이터가 시스템에 추가된다는 뜻이다.

개략적 시스템

• 데이터 수집 서비스: 사용자가 입력한 질의를 실시간으로 수집하는 시스템이다.
• 질의 서비스: 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스이다.

데이터 수집 서비스

twitch, twitter, twitch, twillo를 순서대로 검색하면 -> 최종적으로 빈도가 1, 2, 1이 쌓임

질의 서비스

두 개의 필드가 있다.

• query: 질의문을 저장하는 필드
• frequency: 질의문이 사용된 빈도를 저장하는 필드

가장 많이 사용된 5개 검색어는 아래 SQL 질의문을 사용해 계산할 수 있다.

SELECT * FROM frequency_table
WHERE query Like `prefix%` 
ORDER BY frequency DESC
LIMIT 5 

상세 설계

트라이 자료구조

관계형 데이터베이스를 이용해 가장 인기 있었던 다섯 개 질의문을 골라내는 방안은 효율적이지 않다. 이 문제는 트라이(trie)를 사용해 해결할 것이다. 트라이가 시스템의 핵심적 부분이 될 것이므로, 충분한 시간을 할애하여 주어진 요구사항에 딱 맞는 트라이를 만들도록 할 것이다.

트라이는 문자열들을 간략하게 저장할 수 있는 자료구조다. 트라이라는 이름은 "retrieval"이라는 단어에서 온 것인데, 문자열을 꺼내는 연산에 초점을 맞추어 설계된 자료구조임을 미루어 짐작할 수 있다. 트라이 자료구조의 핵심 아이디어를 살펴보면 다음과 같다.

• 트라이는 트리 형태의 자료구조다.
• 이 트리의 루트 노드는 빈 문자열을 나타낸다.
• 각 노드는 글자 하나를 저장하며, 26개의 자식 노드를 가질 수 있다.
• 각 트리 노드는 하나의 단어, 또는 접두어 문자열을 나타낸다.

가장 많이 사용된 질의어 k개는 다음과 같이 찾을 수 있다.

• p: 접두어의 길이
• n: 트라이 안에 있는 노드 개수
• c: 주어진 노드의 자식 노드 개수
• 해당 접두어를 표현하는 노드를 찾는다. 시간 복잡도는 O(p)이다.
• 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다. 유효한 검색 문자열을 구성하는 노드가 유효 노드다. 시간 복잡도는 O(c)이다.
• 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾는다. 시간 복잡도는 O(clogc)이다.

노드에 인기 검색어 캐시

각 노드에 k개의 인기 검색어를 저장해 두면 전체 트라이를 검색하는 일을 방지할 수 있다. 5~10개 정도의 자동완성 제안을 표시하면 충분하므로, k는 작은 값이다.

각 노드에 이렇게 인기 질의어를 캐시하면 'top 5' 검색어를 질의하는 시간 복잡도를 엄청나게 낮출 수 있다. 하지만 각 노드에 질의어를 저장할 공간이 많이 필요하게 된다는 단점도 있다. 그러나 빠른 응답속도가 아주 중요할 때는 이 정도 저장공간도 희생할 만한 가치는 있다.

데이터 수집 서비스

지금까지 살펴본 설계안은 사용자가 검색창에 뭔가 타이핑을 할 때마다 실시간으로 데이터를 수정했다. 이 방법은 다음 두 가지 문제로 그다지 실용적이지 못하다.

• 매일 수천만 건의 질의가 입력될 텐데 그때마다 트라이를 갱신하면 질의 서비스는 심각하게 느려질 것이다.
• 일단 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 ㅇ낳을 것이다. 그러니 트라이는 그렇게 자주 갱신할 필요가 없다.

개선안:

데이터분석 서비스 로그 -> 로그 취합 서버 -> 취합된 데이터 -> 작업 서버 -> 매주 갱신 -> 트라이 데이터 베이스 -> 매주 데이터베이스의 상태를 스냅샷 -> 트라이 캐시

데이터 분석 서비스 로그

데이터 분석 서비스 로그에는 검색창에 입력된 질의에 관한 원본 데이터가 보관된다. 새로운 데이터가 추가될 뿐 수정은 이루어지지 않으며 로그 데이터에는 인덱스를 걸지 않는다.

로그 취합 서버

데이터 분석 서비스로부터 나오는 로그는 보통 그 양이 엄청나고 데이터 형식도 제각각인 경우가 많다. 따라서 이 데이터를 잘 취합하여 우리 시스템이 쉽게 소비할 수 있도록 해야 한다.

취합된 데이터

time 필드는 해당 주가 시작한 날짜
frequency 필드는 해당 질의가 해당 주에 사용된 횟수의 합

작업 서버

작업 서버는 주기적으로 비동기적 작업을 실행하는 서버 집합이다. 트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 담당한다.

트라이 캐시

트라이 캐시는 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽이 연산 성능을 높이는 구실을 한다. 매주 트라이 데이터베이스의 스냅샷을 떠서 갱신한다.

트라이 데이터베이스

선택지로 두 가지가 있다.

1. 문서 저장소: 새 트라이를 매주 만들 것이므로, 주기적으로 트라이를 직렬화하여 데이터베이스에 저장할 수 있다.
2. 키-값 저장소: 트라이는 아래 로직을 적용하면 해시 테이블 형태로 변환 가능하다.
   • 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
   • 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

14장 유튜브 설계

아래와 같은 기능을 갖는 비디오 스트리밍 서비스 설계

• 빠른 비디오 업로드
• 원활한 비디오 재생
• 재생 품질 선택 기능
• 낮은 인프라 비용
• 높은 가용성과 규모 확장성, 그리고 안정성
• 지원 클라이언트: 모바일 앱, 웹 브라우저, 그리고 스마트 TV

개략적 규모 추정

• DAU 5백만
• 한 사용자는 하루에 평균 5개의 비디오를 시청
• 10%의 사용자가 하루에 1비디오 업로드
• 비디오 평균 크기는 300MB
• 비디오 저장을 위해 매일 새로 요구되는 저장 용량 = 5백만 x 10% x 300MB = 150TB
• CDN 비용 : $150,000/일

개략적 설계안

• CDN: 비디오는 CDN에 저장한다. 재생 버튼을 누르면 CDN으로부터 스트리밍이 이루어진다.
• API 서버: 비디오 스트리밍을 제외한 모든 요청은 API 서버가 처리한다. 피드 추천, 비디오 업로드 URL 생성, 메타데이터 데이터베이스와 캐시 갱신, 사용자 가입 등등이 API 서버가 처리하는 작업이다.

비디오 업로드 절차

• 사용자: 컴퓨터나 모바일 폰, 혹은 스마트 TV를 통해 유튜브를 시청하는 이용자다.

• 로드밸런서: API 서버 각각으로 고르게 요청을 분산하는 역할

• API 서버: 비디오 스트리밍을 제외한 다른 모든 요청 처리

• 메타데이터 데이터베이스: 비디오의 메타데이터를 보관. 샤딩과 다중화를 적용하여 성능 및 가용성 충족

• 메타데이터 캐시: 성능을 높이기 위해 비디오 메타데이터와 사용자 객체는 캐시한다.

• 원본 저장소: 원본 비디오를 보관할 대형 이진 파일 저장소 시스템. BLOB 저장소는 "이진 데이터를 하나의 개체로 보과나는 데이터베이스 관리 시스템"이다.

• 트랜스코딩 서버: 비디오 트랜스코딩은 비디오 인코딩이라 부르기도 하는 절차로, 비디오의 포맷을 변환하는 절차다. 단말이나 대역폭 요구사항에 맞는 최적의 비디오 스트림을 제공하기 위해 필요하다.

• 트랜스코딩 비디오 저장소: 트랜스코딩이 완료된 비디오를 저장하는 BLOB 저장소다.

• CDN: 비디오를 캐시하는 역할 담당. 사용자가 재생 버튼을 누르면 비디오 스트리밍은 CDN을 통해 이뤄진다.

• 트랜스코딩 완료 큐: 비디오 트랜스코딩 완료 이벤트들을 보관할 메시지 큐다.

• 트랜스코딩 완료 핸들러: 트랜스코딩 완료 큐에서 이벤트 데이털르 꺼내어 메타데이터 캐시와 데이터베이스를 갱신할 작업 서버들

다음 두 프로세스가 병렬적으로 수행된다.

a. 비디오 업로드
b. 비디오 메타데이터 갱신. 메타데이터에는 비디오 URL, 크기, 해상도, 포맷, 사용자 정보가 포함된다.

프로세스 a: 비디오 업로드

1. 비디오를 원본 저장소에 업로드한다.
2. 트랜스코딩 서버는 원본 저장소에서 해당 비디오를 가져와 트랜스코딩을 시작한다.
3. 트랜스코딩이 완료되면 아래 두 절차가 병렬적으로 수행된다.
   • 3a. 완료된 비디오를 트랜스코딩 비디오 저장소로 업로드한다.
   • 3b. 트랜스코딩 완료 이벤트를 트랜스코딩 완료 큐에 넣는다.
   • 3a.1. 트랜스코딩이 끝난 비디오를 CDN에 올린다.
   • 3b.1. 완료 핸들러가 이벤트 데이터를 큐에서 꺼낸다.
   • 3b.1.a, 3b.1.b. 완료 핸들러가 메타데이터 데이터베이스와 캐시를 갱신한다.
4. API 서버가 단말에게 비디오 업로드가 끝나 스트리밍 준비가 되었음을 알린다.

프로세스 b: 메타데이터 갱신

원본 저장소에 파일이 업로드되는 동안, 단말은 병렬적으로 비디오 메타데이터 갱신 요청을 API 서버에 보낸다. 이 요청에 포함된 메타데이터에는 파일 이름, 크기, 포맷 등의 정보가 들어 있다. API 서버는 이 정보로 메타데이터 캐시와 데이터베이스를 업데이트한다.

비디오 스트리밍 절차

비디오는 CDN에서 바로 스트리밍된다. 사용자의 단말에 가장 가까운 CDN 에지 서버가 비디오 전송을 담당할 것이다.

16장 구글 드라이브 설계

개략적 설계안

아래와 같은 구성의 서버 한 대로 시작해 보자.

• 파일을 올리고 다운로드 하는 과정을 처리할 웹 서버
• 사용자 데이터, 로그인 정보, 파일 정보 등의 메타데이터를 보관할 데이터베이스
• 파일을 저장할 저장소 시스템. 파일 저장을 위해 1TB의 공간을 사용할 것이다.

기본적으로 세 가지 API가 필요하다.

1. 파일 업로드 API

• 단순 업로드: 파일 크기가 작을 때 사용한다
• 이어 올리기: 파일 사이즈가 크고 네트워크 문제로 업로드가 중단될 가능성이 높다고 생각되면 사용한다.

이어 올리기는 다음 세 단계 절차로 이루어진다.

• 이어 올리기 URL을 받기 위한 최초 요청 전송
• 데이터를 업로드하고 업로드 상태 모니터링
• 업로드에 장애가 발생하면 장애 발생시점부터 업로드를 재시작

2. 파일 다운로드 API

• 인자: path - 다운로드할 파일의 경로

3. 파일 갱신 히스토리 API

한대 서버의 제약 극복

업로드되는 파일이 많아지다 보면 결국에는 파일 시스템은 가득 차게 된다.

가장 먼저 떠오르는 해결책은 데이털르 샤딩하여 여러 서버에 나누어 저장하는 것이다.

결국 우리 서비스의 파일도 S3에 저장하기로 한다. S3는 다중화를 지원하는데, 같은 지역 안에서 다중화를 할 수도 있고 여러 지역에 걸쳐 다중화를 할 수도 있다.

• 로드밸런서: 네트워크 트래픽을 분산하기 위해 로드밸런서를 사용한다.
• 웹 서버: 로드밸런서를 추가하고 나면 더 많은 웹 서버를 손쉽게 추가할 수 있다.
• 메타데이터 데이터베이스: 데이터베이스를 파일 저장 서버에서 분리하여 SPOF를 회피한다.
• 파일 저장소: S3를 파일 저장소로 사용하고 가용성과 데이터 무손실을 보장하기 위해 두 개 이상의 지역에 데이터를 다중화한다.

동기화 충돌

구글 드라이브 같은 대형 저장소 시스템의 경우 때때로 동기화 충돌이 발생할 수 있다. 두 명 이상의 사용자가 같은 파일이나 폴더를 동시에 업데이트하려고 하는 경우다. 여기서는 다음 전략을 사용할 것이다. 먼저 처리되는 변경은 성공한 것으로 보고, 나중에 처리되는 변경은 충돌이 발생한 것으로 표시하는 것이다.

개략적 설계안

• 사용자 단말: 사용자가 이용하는 웹브라우저나 모바일 앱 등의 클라이언트

• 블록 저장소 서버: 파일 블록을 클라우드 저장소에 업로드하는 서버. 블록 저장소는 블록 수준 저장소라고도 하며, 클라우드 환경에서 데이터 파일을 저장하는 기술이다. 이 저장소는 파일을 여러 개의 블록으로 나눠 저장하며, 각 블록에는 고유한 해시값이 할당된다. 이 해시값은 메타데이터 데이터베이스에 저장된다. 각 블록은 독립적인 객체로 취급되며 클라우드 저장소 시스템에 보관된다. 파일을 재구성하려면 블록들을 원래 순서대로 합쳐야 한다.

• 클라우드 저장소: 파일은 블록 단위로 나눠져 클라우드 저장소에 보관된다.

• 아카이빙 저장소: 오랫동안 사용되지 않은 비활성 데이터를 저장하기 위한 컴퓨터 시스템

• 로드 밸런서: 요청을 모든 API 서버에 고르게 분산하는 구실

• API 서버: 파일 업로드 외에 거의 모든 것을 담당. 사용자 인증, 사용자 프로파일 관리, 파일 메타데이터 갱신 등.

• 메타데이터 데이터베이스: 사용자, 파일, 블록, 버전 등의 메타데이터 정보를 관리. 실제 파일은 클라우드에 보관하며, 이 데이터베이스에는 오직 메타데이터만 둔다는 점을 명심.

• 메타데이터 캐시: 성능을 높이기 위해 자주 쓰이는 메타데이터는 캐시.

• 알림 서비스: 특정 이벤트가 발생했음을 클라이언트에게 알리는데 쓰이는 발생/구독 프로토콜 기반 시스템이다. 예시 설계안의 경우에는 클라이언트에게 파일이 추가되었거나, 편집되었거나, 삭제되었음을 알려, 파일의 최신 상태를 확인하도록 하는 데 쓰인다.

• 오프라인 사용자 백업 큐: 클라이언트가 접속 중이 아니라서 파일의 최신 상태를 확인할 수 없을 때는 해당 정보를 이 큐에 두어 나중에 클라이언트가 접속했을 때 동기화할 수 있도록 한다.

블록 저장소 서버

네트워크 대역폭 최적화 하는 방안

• 델타 동기화 : 파일이 수정되면 전체 파일 대신 수정이 일어난 블록만 동기화
• 압축: 블록 단위로 압축해 두면 데이터 크기를 많이 줄일 수 있다.

높은 일관성 요구사항

이 시스템은 강한 일관성 모델을 기본으로 지원해야 한다. 같은 파일이 단말이나 사용자에 따라 다르게 보이는 것은 허용할 수 없다는 뜻이다. 메타데이터 캐시와 데이터베이스 계층에도 같은 원칙이 적용되어야 한다.

메모리 캐시는 보통 최종 일관성 모델을 지원한다. 따라서 강한 일관성을 달성하려면 다음 사항을 보장해야 한다.

• 캐시에 보관된 사본과 데이터베이스 원본 일치
• 데이터베이스에 보관된 원본에 변경 발생시 캐시에 있는 사본 무효화

업로드 절차

• 파일 메타데이터 추가

1. 클라이언트 1이 새 파일의 메타데이터를 추가하기 위한 요청 전송
2. 새 파일의 메타데이털르 데이터베이스에 저장하고 업로드 상태를 대기중으로 변경
3. 새 파일이 추가되었음을 알림 서비스에 통지
4. 알림 서비스는 관련된 클라이언트에게 팡리이 업로드되고 있음을 알림

• 파일을 클라우드 저장소에 업로드

2.1 클라이언트 1이 파일을 블록 저장소 서버에 업로드
2.2. 블록 저장소 서버는 파일을 블록 단위로 쪼갠 다음 압축하고 암호화한 다음에 클라우드 저장소에 전송
2.3. 업로드가 끝나면 클라우드 스토리지는 완료 콜백을 호출. 이 콜백 호출은 API 서버로 전송됨
2.4. 메타데이터 DB에 기록된 해당 파일의 상태를 완료로 변경
2.5. 알림 서비스에 파일 업로드가 끝났음을 통지
2.6. 알림 서비스는 관련된 클라이언트에게 파일 업로드가 끝났음을 알림

다운로드 절차

파일 다운로드는 파일이 새로 추가되거나 편집되면 자동으로 시작된다. 그렇다면 클라이언트는 다른 클라이언트가 파일을 편집하거나 추가했다는 사실을 어떻게 감지하는 것일까? 두 가지 방법을 사용한다.

• 클라이언트 A가 접속 중이고 다른 클라이언트가 파일을 변경하면 알림 서비스가 클라이언트 A에게 변경이 발생했으니 새 버전을 끌어가야 한다고 알린다.
• 클라이언트 A가 네트워크에 연결된 상태가 아닐 경우에는 데이터는 캐시에 보관될 것이다. 해당 클라이언트의 상태가 접속 중으로 바뀌면 그때 해당 클라이언트는 새 버전을 가져갈 것이다.

1. 알림 서비스가 클라이언트 2에게 누군가 파일을 변경했음을 알림
2. 알림을 확인한 클라이언트 2는 새로운 메타데이터를 요청
3. API 서버는 메타데이터 데이터베이스에게 새 메타데이터 요청
4. API 서버에게 새 메타데이터가 반환됨
5. 클라이언트 2에게 새 메타데이터가 반환됨
6. 클라이언트 2는 새 메타데이터를 받는 즉시 블록 다운로드 요청 전송
7. 블록 저장소 서버는 클라우드 저장소에서 블록 다운로드
8. 클라우드 저장소는 블록 서버에 요청된 블록 반환
9. 블록 저장소 서버는 클라이언트에게 요청된 블록 반환. 클라이언트 2는 전송된 블록을 사용하여 파일 재구성

알림 서비스

롱 폴링을 사용하는 이유

• 채팅 서비스와는 달리, 본 시스템의 경우에는 알림 서비스와 양방향 통신이 필요하지 않음
• 웹 소켓은 실시간 양방향 통신이 요구되는 채팅 같은 응용에 적합. 구글 드라이브의 경우 알림을 보낼 일은 그렇게 자주 발생하지 않으며, 알림을 보내야 하는 경우에도 단시간에 많은 양의 데이터를 보낼 일은 없음.