📖 가상면접 사례로 배우는 대규모 시스템 설계 기초

토의 스터디로 진행된 학습내용을 정리한 포스트입니다. github

Contents

1장. 사용자 수에 따른 규모 확장성 2장. 개략적인 규모 추정 3장. 시스템 설계 면접 공략법 4장. 처리율 제한 장치의 설계 5장. 안정 해시 설계 6장. 키-값 저장소 설계 7장. 분산시스템을 위한 유일 ID 생성기 설계 8장. URL 단축키 설계

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

최근에 정리한 백엔드 설계시 고려해야할 사항에 대한 포스팅과 유사한 부분이 많았습니다.

단일서버
만약 사용자가 도메인 주소를 입력하면, 어떻게 될까요?
DNS에서 해당하는 IP주소를 찾고 그 주소에 해당하는 웹서버에 HTTP 요청을 보내게 됩니다. 이 때, 웹서버는 요청에 따른 HTML 또는 JSON 데이터 정보를 사용자 단말에 보여주게 됩니다.

데이터베이스
HTTP 요청을 받은 웹서버는 데이터베이스를 통해 데이터를 얻게 됩니다. 데이터베이스는 관계형 데이터베이스인 MySQL, PostgreSQL 등이 있고, 비관계형 데이터베이스인 NoSQL에는 DynamoDB, Redis 등이 있습니다. NoSQL은 키-값 저장소, 그래프 저장소, 칼럼 저장소, 문서 저장소로 나눌 수 있습니다.
비관계형 데이터베이스는 비정형 데이터이거나 데이터를 단순히 직렬화, 역직렬화만 하면 되는 상황, 아주 낮은 지연 응답시간이 요구되는 상황에 적합합니다. 또는 아주 많은 양의 데이터를 저장할 필요가 있을 때 사용됩니다.

아주 많은 데이터를 저장한다는 것은 쓰기 연산이 요구되는 부분이 아닌가요?
기존에 NoSQL에 대해 공부할 때, 매번 데이터 조회를 RDBMS에서 하는 것이 아니라 Redis를 이용한 캐싱처리 방안을 모색한 적이 있습니다. 이 때는 읽기 연산을 위한 수단이었는데, 비휘발성 메모리에 많은 양의 데이터를 저장하기 위해 사용한다는 말이 이해되지 않았습니다.
저자의 의도를 생각해 보면, 데이터를 저장하는 과정에서 NoSQL에 먼저 저장해 두고, RDBMS에는 일정 시간마다 데이터 업데이를 진행하는 부분이라고 이해했습니다. 이렇게 하면 읽기 작업을 RDBMS로 진행한다고 했을 때, 특정 row를 읽기 위해 row lock 걸리는 상황에서도 많은 데이터의 일시 저장으로 인해 상당 시간 page lock이 걸리는 등의 경합이 발생하지 않을 수 있기 때문입니다.

수직적 규모 확장 vs 수평적 규모 확장
서버를 확장하는 방법은 수직적 규모 확장과 수평적 규모 확장으로 나눌 수 있습니다.
수직적 규모 확장은 scale-up이라고도 하며, 서버 자체의 CPU나 메모리를 증설하는 방법입니다. 하지만 서버 증설을 무한정할 수 없으며, 이 서버만 존재한다면, 장애 상황에서 자동복구나 다중화 방안을 제시하지 못한다는 점에서 한계를 가지고 있습니다.
수평적 확장은 scale-out이라고도 하며, 여러 서버를 두어 성능을 개선하는 방법을 말합니다. 이렇게 여러 서버를 가지고 가면, 로드밸런서로 서버 접속을 적절히 분산해 성능 향상과 부하를 방지할 수 있습니다. 로드밸런서는 보안을 위해 사설 IP 주소를 사용해 서버 간 통신을 하며, 요청을 먼저 받아 사설 IP 주소의 웹서버에 연결해줍니다.
그럼 데이터베이스의 다중화 처리는 어떨까요?
데이터베이스는 주 데이터베이스와 부 데이터베이스로 나누어 주로 애플리케이션에 많이 사용되는 읽기 작업은 여러 부 데이터베이스에서 하게 하고, 쓰기 작업은 주 데이터베이스에서 처리합니다.
부 데이터베이스 장애시, 주 데이터베이스 또는 새로운 부 데이터베이스에서 읽기 작업을 이어서 하게 됩니다. 주 데이터베이스 장애시에는 부 데이터베이스가 주 데이터베이스의 역할을 하게 됩니다. 그리고 보관 데이터가 최신 상태가 아닌 경우 복구 스크립트로 추가적인 해결이 필요합니다.

복구 스크립트를 이용한 추가해결이 가능할까?
이미 주 데이터베이스가 장애가 나서 부 데이터베이스를 주 데이터베이스로 승격하는 과정에서 필요한 부분은 쓰기 연산이 진행되는 주 데이터베이스의 데이터와의 일관성입니다. 따라서 주 데이터베이스의 데이터를 가지고 올 수 있다면, 부 데이터베이스에 주 데이터베이스 장애 바로 직전으로의 복구된 데이터를 가지고 올 수 있어야 합니다.

다중 마스터와 원형 다중화
다중 마스터는 여러 대의 마스터 장비가 하나의 슬레이브 장비를 제어하는 것을 말하며, 원형 다중화는 여러 대의 장비가 서로를 제어하는 것을 말합니다.

캐시
캐시는 값비싼 연산 결과 또는 자주 참조되는 데이터를 메모리에 두어 연이은 요청이 빨리 처리될 수 있도록 하는 저장소를 말합니다. 데이터베이스 조회보다 빠르게 데이터를 가지고 올 수 있습니다. 사용자가 요청을 보내면 캐시에 값이 있으면 그 데이터를 넘기고 없으면 데이터베이스에 조회해 캐시 저장 후 요청을 처리하게 됩니다.
캐시는 주로 참조 데이터에 사용하며, 만료시 데이터를 다시 데이터베이스에서 읽어와야 하므로 만료기간을 너무 짧게 두어선 안됩니다. 또 만료기간이 너무 길 경우에는 캐시와 데이터베이스 간의 일관성이 떨어집니다. 그리고 캐시 역시 단일 장애지점(Single Point of Failure, SPOF)가 되지 않도록 캐시 서버를 분산시켜야 합니다.

캐시 방출정책
Caching Strategies and How to Choose the Right One의 내용을 기반으로 정리했습니다.
어떤 캐싱전략을 사용하느냐는 어떤 데이터 접근 방식을 사용하는지에 따라 달라집니다. 쓰기작업이 한 번에 많이 이뤄지는지, 쓰기 연산의 작업 빈도가 높은지, 데이터가 unique한 값을 갖는지에 따라서 다릅니다.
Cache-Aside 방식은 애플리케이션에서 cache를 먼저 읽고, 데이터가 없으면(cache miss) 데이터베이스에서 읽어온 뒤에 cache에 데이터를 넣어줍니다. 이 방식은 모두 애플리케이션에서 핸들링하고 별도로 cache와 데이터베이스 간의 연결은 없습니다. 조회할 내용이 많은 경우로 Memcached와 Redis가 가장 많이 사용됩니다. Cache-Aside 방식은 일반적으로 주로 쓰기 작업에서 데이터베이스에 데이터를 직접 쓰기 때문에 캐시와 일치하지 않을 수 있습니다. 따라서 데이터 신선도를 적절히 유지해야 하는 경우 캐시 항목을 무효화하거나 적절한 TTL 설정이 필요합니다.
Read-Through 방식은 Cache-Aside 방식과 유사하지만, 캐시와 데이터베이스 데이터 모델이 다르지 않다는 점에서 차이가 있습니다. 대신 처음 로드되거나 캐싱처리하는 불필요한 캐싱이 발생하기 때문에 개발자는 수동으로 쿼리를 실행해 미리 워밍할 필요가 있습니다.
Write-Through 방식은 항상 쓰기 작업시 캐시에 쓰여지고 그 다음 데이터베이스에 쓰기 작업이 이뤄지는 경우를 말합니다. 일관성이 있으나 매번 2개의 쓰기 작업이 수행되기 때문에 대기시간이 발생합니다.
Write-Back 방식은 캐시에 기록된 데이터를 기본 데이터베이스에 비동기적으로 업데이트합니다. 쓰기 작업이 많은 경우 Write-Through 방식처럼 매번 수행하는 것이 아니라 반환 작업 전에 수행하므로 비용이 감소합니다. 하지만 캐시 오류 발생시 데이터가 영구적으로 손실될 수 있습니다.

캐시 일관성에 대한 페이스북 논문

R. Nishtala, “Facebook, Scaling Memcache at,” 10th USENIX Symposium on NetworkedSystems Design and Implementation (NSDI ’13)

콘텐츠 전송 네트워크 (CDN)
CDN은 정적 콘텐츠 전송에 쓰이는 네트워크로 가까운 CDN 서버를 통해 정적 콘텐츠를 얻고 해당 지리적 위치의 CDN에 소스가 없다면, 그 CDN에 원본 서버에서 가지고 온 정적 콘텐츠를 저장 후, 가지고 오게 됩니다. CDN을 사용할 때는 비용과 콘텐츠의 만료시점, 장애대처 방안 그리고 버전 관리를 이용한 콘텐츠 무효화 등을 고려해야 합니다.

무상태 웹 계층
사용자의 상태정보를 웹 서버에서 관리한다면, 그리고 웹 서버가 여러 개라면 로드밸런서는 해당 사용자를 상태를 가지고 있는 웹서버로만 연결해야 합니다. 물론 이를 돕기 위해 고정 세션(sticky session)을 이용하면 되자만, 이 경우 로드밸런서에 부담을 주게 됩니다.
따라서 무상태 웹 계층으로 아키텍처를 만들 필요가 있는데 이렇게 되면 사용자는 어떤 웹 서버에 요청을 보내든지 응답을 받을 수 있게 됩니다. 무상태 아키텍처에서는 상태 정보가 웹 서버에 있지 않아 규모의 축소/확장이 자유로워집니다.

데이터 센터
데이터 센터는 US-East, US-West와 같이 지리적 라우팅에 따라 geoDNS로 가까운 IP주소로 연결해주는 서비스입니다. 여러 개의 데이터 센터를 사용하고자 할 때는 각 데이터 센터의 위치에서 서비스가 잘 동작하는지 테스트할 필요가 있고, 각 데이터 센터별 데이터 일관성이 유지되는지 확인할 필요가 있습니다.

메시지 큐
메시지 큐는 무손실을 보장하는 비동기 통신을 지원하는 컴포넌트입니다. 발행자는 미리 메시지 큐를 만들어두고, 소비자가 소비할 때마다 큐에 있는 동작을 수행하게 됩니다. 생산자는 소비자의 프로세스가 없더라도 메시지를 발행할 수 있고, 소비자 역시 생산자가 가용한 상태가 아니여도 메시지를 수신할 수 있습니다. 각 컴포넌트가 느슨한 결합이 될 수 있도록 하고, 결함에 대한 내성을 높입니다.
책에서는 사진 보정 작업을 미리 메시지 큐로 만들어두고 비동기적으로 완료할 수 있도록 하는 프로세스를 예시로 들고 있습니다.

큐의 크기가 커지면 더 많은 작업 프로세스를 추가해야 처리 시간을 줄일 수 있습니다. 하지만 큐가 거의 항상 비어있는 상태라면 작업 프로세스의 수는 줄일 수 있을 것입니다.

When the size of the queue becomes large, more workers are added to reduce the processing time. However, if the queue is empty most of the time, the number of workers can be reduced.

이 부분의 말이 약간 어색해서 원어 버전을 찾아봤습니다.
생산자와 소비자는 독립적 확장이 가능한데 큐의 크기가 커지면 더 많은 작업 프로세스를 생산자를 추가할 수 있습니다.
거의 항상 비어 있는 상태라면 작업자의 수를 줄일 수 있습니다.

로그, 메트릭 그리고 자동화
시스템 규모가 커질수록 로그, 메트릭, 자동화는 중요합니다. 여기서 메트릭이란 사업 현황이나 시스템 현재 상태를 파악할 수 있는 중요한 도구입니다. 예를 들어, CPU, 메모리 등에 대한 호스트 단위 메트릭, 데이터베이스나 캐시 성능에 관한 종합 메트릭, 일별 능동사용자, 재방문 등과 같은 핵심 비즈니스 메트릭이 있습니다.

데이터베이스의 규모 확장
데이터베이스 규모 확장도 수직적, 수평적 규모 확장이 있습니다. 앞서 서버의 경우의 수직적 확장과 거의 유사한 단점을 가지고 있습니다.
여기서 눈여겨 봐야할 부분은 데이터베이스의 수평적 확장입니다. 데이터베이스의 수평적 확장은 샤딩이라고 하며, 샤드 단위로 분할해 중복이 없도록 관리합니다. 샤드를 분리하는 기준에 따라 분포가 균등하지 않을 수도 있고, 특정 데이터베이스에 핫스팟 키가 집중되어 서버 과부하가 발생할 수 있습니다. 따라서 이 경우에는 재 샤딩을 하거나 오히려 비정규화로 여러 샤드에서 조인하는 과정에서 오는 비효율을 방지하는 것 등을 고려해야 합니다.

백만 사용자, 그리고 그 이상
큰 규모의 시스템을 관리하기 위해서는 최적화하고 작은 단위로 서비스를 분할하는 등 확장성에 유리한 설계가 필요합니다.

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

2장. 개략적인 규모 추정

개략적인 규모 추정은 보편적으로 통용되는 성능 수치상에서 사고 실험을 행하여 보편적으로 통용되는 성능 수치상에서 사고 실험을 행하여 추정치를 계산하는 행위로서, 어떤 설계가 요구사항에 부합할 것인지 보기 위한 것
Jeff Dean, Lead of Google AI

2의 제곱수

응답지연 값

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

고가용성
시스템이 오랜 시간 동안 지속적으로 중단 없이 운영될 수 있는 능력을 지칭하는 용어입니다. (대부분 99% ~ 100%)
SLA(Service Level Agreement)
서비스 사업자가 보편적으로 사용하는 용어, 서비스 사업자와 고객 사이에 맺어진 합의

추정량 구하기
트위터 QPS와 저장소 요구량 추정 예시

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

추정치 계산을 위한 팁

1. 근사치를 이용해서 계산
2. 가정을 적어두자
3. 단위를 붙이자
4. QPS, 최대 QPS, 저장소 요구량, 캐시 요구량, 서버 수 문제를 익혀두자

• Uptime/SLA calculator: what is an SLA and how to calculate it?

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

시스템 설계 면접의 목적
지원자가 협력에 적합한지, 압박 상황을 잘 견디는지 모호한 문제로도 건설적으로 해결할 능력이 있는지 등을 확인합니다. 과도한 엔지니어링을 피하고 ‘타협적 결정’을 할 필요가 있습니다.

효과적 면접을 위한 4단계 접근법

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

• 올바른 질문을 하고 가정을 하고, 시스템 구축에 필요한 정보를 모아야 합니다.
• 기능, 사용자 수, 규모 확장성, 기술스택 등

2단계 개략적인 설계안 제시 및 동의 구하기

• 핵심 컴포넌트 다이어그램 그리기
• 클라이언트(모바일/웹), API, 웹 서버, 데이터 저장소, 캐시, CDN, 메시지 큐 등

3단계 상세 설계

• 컴포넌트 사이의 우선순위 정하기
• 불필요한 세부사항에 집중하지 말고 면접에 더 초점이 맞춰진 부분에 대해 주의를 기울여야 합니다.

4단계 마무리

• 후속질문
• 운영 이슈에 대해 이야기(배포, 로그, 모니터링)
• 오류 발생시에 대하여

시스템 설계 면접에서 하지 말아야 할 것

• 전형적인 면접 문제에 대비하지 않은 상태에서 가지 말라.
• 요구사항이나 가정들이 분명하지 않은 상태에서 설계를 제시하지 말라.
• 처음부터 특정 컴포넌트의 세부사항을 너무 깊이 설명하지 말라. 개략적 설계를 마친 뒤에 세부사항으로 나아가라.
• 진행 중 막혔다면, 힌트를 청하기를 주저하지 말자.
• 소통을 하자.
• 설계안을 내놓은 후에도 면접관의 의견을 자주 구하라.

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

처리율 제한 장치는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치입니다.

• DoS에 의한 자원고갈 공격을 방지
• 우선순위가 높은 API에 자원을 할당하거나 API 사용에 따른 과금 횟수를 제한
• 서버 과부하 방지

책에서는 3장에서 설명한 단계별로 처리율 제한 장치 설계를 설명하고 있습니다.

1단계 - 문제 이해 및 설계 범위 확정
처리율과 응답시간, 메모리 사용량, 예외처리, 결함 감내성은 어떤지 등에 대한 시스템 요구사항을 정해야 합니다.

2단계 - 개략적인 설계안 제시 및 동의 구하기
처리율 제한장치를 서버에 둘지 게이트웨이에 둘지는 회사의 지침, 기술 스택 등에 따라 달라집니다.
처리율 제한장치 미들웨어로 만들어 많은 요청이 발생한 경우 429 Too many request를 반환합니다. 마이크로서비스에서는 보통 API 게이트웨이라는 컴포넌트에 설계되는데, SSL 종단, 사용자 인증, IP 허용목록 관리 등을 지원하는 완전 위탁관리형 서비스입니다.

처리율 제한 알고리즘

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

토큰 버킷

• 간단하고 인터넷 기업들이 보편적으로 사용하고 있는 알고리즘으로 아마존과 스트라이프에서 API 통제를 위해 사용하고 있습니다.
• 토큰이 정기적으로 채워지고 요청이 처리될 때마다 하나의 토큰을 사용합니다. 토큰이 없는 경우 해당 요청은 버려집니다.
• 버킷의 크기, 토큰 공급률 필요
• 구현이 수비고 메모리 효율도 좋지만, 두 개의 인자값을 적절히 튜닝하는 것은 어렵습니다.

누출 버킷

• FIFO
• 큐에 빈자리가 있는 경우 요청을 추가하고 자리가 없으면 요청을 버립니다.
• 버킷 크기, 처리율
• 큐의 크기가 제한되어 메모리 사용량 측면에서 효율적이지만 요청이 몰릴 경우 오래된 요청들이 쌓이고 최신 요청들이 버려집니다. 토큰 버킷 알고리즘과 같이 올바르게 인자값을 튜닝하는 것이 어렵습니다.

고정 윈도 카운터

• 타임라인을 고정된 간격의 윈도로 나누고 각 윈도마다 카운터를 붙입니다.
• 요청이 접수되면 카운터가 1씩 증가되고, 카운터가 임계치를 벗어나면 새로운 요청은 새 윈도가 열릴 때까지 버려집니다.
• 순간적으로 많은 트래픽이 몰릴 경우, 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있습니다.

이동 윈도 로그

• 고정 윈도 카운터에서 한 순간에 트래픽이 몰리는 경우에 할당보다 더 많은 요청을 처리하는 문제를 해결할 수 있는 방식입니다.
• 요청의 타임스탬프를 레디스 정렬집합과 같은 캐시에 보관합니다.
• 새 요청을 로그에 추가하고, 만료된 타임스탬프를 제거합니다.
• 거부된 요청의 타임스탬프로 저장하기 때문에 다량의 메모리를 사용합니다.

이동 윈도 카운터

• 고정 윈도 카운터와 이동 윈도 로그를 결합한 것으로 요청의 계산은 다음과 같습니다.
• 현재 1분간 요청 수 + 직전 1분간의 요청 수 * 이동 윈도와 직접 1분이 겹치는 비율
• 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨합니다.

카운터의 보관
Redis 메모리 기반 저장장치에 저장하며, 카운터 값을 1씩 증가시키는 INCR와 카운터의 타임아웃 값을 정하는 EXPIRE가 있습니다.

3단계 - 상세 설계
처리율 제한 config 파일

domain: messaging
descriptors:
- key: message_type
  Value: marketing
  rate_limit:
     unit: day
      requests_per_unit: 5  

처리율 한도 초과 트래픽의 처리
클라이언트는 HTTP 응답 헤더를 통해 얼마나 많은 요청이 있는지, 윈도에 남은 요청 수, 윈도마다 가능한 요청의 수, 한도 제한에 걸리지 않기 위해 얼마 뒤에 요청을 보내야 하는지를 알 수 있습니다.

• X-Ratelimit-Remaining
• X-Ratelimit-Limit
• X-Ratelimit-Retry-After

분산 환경에서의 처리율 제한 장치의 구현
병행성이 심한 경우에 대해서는 경쟁 조건 이슈가 발생합니다. 락은 시스템 성능을 많이 떨어뜨리기 때문에 이를 해결하기 위해서는 루아 스크립트 또는 정렬 집합이라는 레디스 자료 구조를 사용하는 방법이 있습니다.

동기화 이슈를 위해서 고정 세션 대신 레디스와 같은 중앙 집중형 데이터 저장소를 사용하는 것이 좋습니다.

성능최적화를 위해서는 데이터 센터의 지리적 위치에 따라 에지 서버를 두어 지연시간을 줄이는 것이 필요합니다. 그리고 제한 장치 간 데이터를 동기화할 때 최종 일관성 모델을 사용해야 합니다.

처리율 제한 장치를 모니터링 해 더 트래픽 패턴을 잘 처리할 수 있는 알고리즘으로 바꾸는 것이 적합합니다.

4단계 마무리
그 외에도 다음 사항들을 고려해볼 수 있습니다.

• 경성 또는 연성 처리율 제한
• 다양한 계층에서의 처리율 제한
• 처리율 제한을 회피하기 위해 클라이언트를 어떻게 설계할 것인가

5장. 안정 해시 설계

서버의 부하를 균등하게 나누기 위해서 해시함수를 사용해 서버에 배치되는 키 값의 분산을 정할 수 있습니다. 하지만 특정 서버가 죽으면 캐시 클라이언트가 데이터가 없는 서버에 접속하는 캐시 미스가 발생할 수 있습니다.

안정 해시
해시공간을 구부려 해시 링으로 만들면 그 위에 해시 서버와 해시 키를 배치할 수 있습니다. 해당 키의 시계방향에 위치하는 링을 탐색해 처음 만나는 서버에 키를 저장하는 방식입니다. 서버가 추가되거나 삭제되더라도 다음 서버로 재배치됩니다.
하지만 파티션의 크기를 균등하게 유지 하지 못해 일부 큰 해시공간을 할당받게 될 수 있습니다.
이를 해결하기 위해서는 가상노드 또는 복제 방법이 사용됩니다 . 하나의 서버를 배치하는 것이 아닌 여러 개의 서버를 링에 배치하므로서 여러 개의 파티션을 하나의 서버가 관리해야 하는 방식입니다. 노드가 많을수록 키의 분포는 더 균등해집니다.
가상 노드의 개수를 더 늘리면 표준 편차의 값은 더 떨어질 것입니다. 그러나 가상노드 데이터를 저장할 공간을 더 많이 필요할 것입니다. 타협적 결정이 필요하므로 시스템 요구사항에 맞게 가상 노드 개수를 적절히 조정해야 합니다.

• 서버가 추가 또는 삭제될 때 재배치되는 키의 수가 최소화됩니다.
• 데이터가 균등하게 분포되므로 수평적 규모 확장성을 달성
• 핫 스팟 키문제를 줄여줍니다. 특정 샤드에 접근이 빈번한 경우 서버 과부하 문제가 발생할 수 있습니다.

6장. 키-값 저장소 설계

키-값 저장소는 키-값 데이터베이스라고 불리는 비 관계형 데이터베이스입니다. 아마존 다이나모, memcached, Redis와 같은 데이터베이스들이 있습니다.

문제 이해 및 설계 범위 확정
키-값 저장소를 설계하고자 할 때 어떤 것을 고려할 수 있을까요?

• 키-값 쌍의 크기
• 데이터의 크기
• 가용성
• 규모 확장성
• 데이터의 일관성
• 응답 지연시간

단일 서버 키-값 저장소
키-값 쌍 전부를 해시테이블에 저장하는 것은 검색 속도는 빠를 수 있으나 모든 데이터를 메모리 안에 두기 어려울 수 있습니다. 이를 해결하기 위해 데이터 압축이나 자주 쓰는 데이터만 디스크에 저장할 수 있습니다.

분산 키-값 저장소
분산 해시 테이블은 키-값 쌍 자체를 여러 테이블에 분산시키는 것으로 CAP정리에 따라 데이터 일관성(Consistency), 가용성(Availability), 분할 내성(Partition tolerance)을 고려해야 합니다. (1장 CAP 참조)
실제 분산 시스템 환경에서 파티션 문제가 발생하지 않는다고 100% 보장할 수 없음으로 일관성과 가용성 중 하나를 선택해야 합니다. 따라서 면접관과 상의 후 적절한 시스템을 설계해야 합니다. (즉, CP나 AP)

구현에 사용될 핵심 컴포넌트 및 기술들

• 데이터 파티션
  • 데이터 파티션을 위해서는 여러 서버에 데이터를 고르게 분산할 수 있는지, 노트 추가/삭제시 데이터 이동을 최소화할 수 있는지를 따져봐야 합니다. 안정해시를 사용하면 규모 확장을 자동화할 수 있게 만들 수 있고, 서버 용량에 맞는 가상 노드로 수를 조정할 수 있습니다. (5장. 안정해시 참조)
• 데이터 다중화
  • 높은 가용성과 안정성 확보를 위해서는 데이터를 N개의 서버에 비동기적으로 다중화할 필요가 있습니다.
  • 가상노드를 사용하면 선택한 N개의 노드가 대응될 실제 물리 서버의 개수가 N보다 작아질 수 있습니다.
  • 물리 서버 선택 중복을 막고, 데이터 사본을 다른 서버에 보관하는 등 보완이 필요합니다.
• 데이터 일관성
  • 여러 노드에 다중화된 데이터는 적절히 동기화되어야 합니다. 정족수 합의 프로토콜을 쓰면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있습니다.
    • N = 사본 개수
    • W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 합니다.
    • R = 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 합니다.
  • W+R>N인 경우에는 강한 일관성이 보장됩니다. 일관성을 보증할 최신 데이터를 가진 노드가 최소 하나는 겹칠 것이기 때문입니다.
    • R=1, W=N: 빠른 읽기 연산에 최적화된 시스템
    • W=1, R=N: 빠른 읽기 연산에 최적화된 시스템
    • W+R>N: 강한 일관성이 보장됨
    • W+R<=N: 강한 일관성이 보장되지 않음
• 일관성 모델
  • 강한 일관성, 약한 일관성, 최종 일관성
  • 최종 일관성은 약한 일관성의 한 형태로 갱신 결과가 결국에는 모든 사본에 반영되는 모델입니다.
• 데이터 버저닝
  • 데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성이 높아집니다.
  • 버저닝: 데이터 변경 시마다 해당 데이터의 새로운 버전을 만드는 것
  • 벡터 시계: [서버, 버전]의 순서쌍을 데이터에 매단 것
    • 만약 두 개의 서버에 각각 데이터가 업데이트 됐고 그 데이터 값이 다르다고 가정해봅시다.
    • 벡터 시계를 이용하면 어떤 버전이 선행인지 다른 버전과의 충돌가능성을 파악할 수 있습니다.
    • 단점으로는 클라이언트 구현이 복잡해질 수 있다는 점과, [서버, 버전]의 순서쌍이 빠르게 증가할 수 있다는 점입니다.

• 장애감지
  • 서버가 많은 경우 모든 노드에 멀티캐스팅 채널을 구축하기보다는 가십 프로토콜과 같은 분산형 장애 감지 솔루션을 채택하는 것이 좋습니다.
  • 가십 프로토콜
    • 각 노드는 주기적으로 자신의 박동 카운터를 증가
    • 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보냄
    • 어떤 멤버의 박동 카운터 값이 지정 시간동안 갱신되지 않으면 장애 상태인 것으로 간주

• 장애해소
  • 일시적 장애처리
    • 느슨한 정족수 접근법에 따라 건강한 서버들을 선정하고 장애 상태 서버로 가는 요청을 임시로 다른 서버가 처리하게 합니다.
    • 단서(hint)를 통한 임시 위탁(hinted handoff)기법을 사용해
  • 영구 장애처리
    • 반-엔트로피 프로토콜을 사용해 최신 버전으로 동기화
    • 머클 트리
      • 해시 크리라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시 또는 자식 노드드르이 레이블로부터 계산된 해시값을 레이블로 붙여두는 트리
      • 루트 노드의 해시값이 다르면 자식 노드의 해시값을 왼쪽에서 오른쪽으로 가면서 비교하고 다른 데이터를 같은 버킷을 찾아 동기화할 수 있습니다.
      • 머클 트리를 사용하면 동기화해야 하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐, 두 서버에 보관된 데이터의 총량과는 무관해집니다.

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

• 중재자는 클라이언트에게 키-값 저장소에 대한 프락시 역할을 하는 노드
• 노드는 안정해시의 해시 링에 분포
• 노드는 자동으로 추가 또는 삭제할 수 있도록 시스템은 완전히 분산
• 모든 노드가 같은 책임을 지는 형태

쓰기경로

• 쓰기 요청이 들어오면 메모리 캐시에 기록
• 메모리 캐시가 임계치에 도달하면 데이터는 디스크의 SSTable(Sorted-String Table)에 기록
  • SSTable: <키, 값>의 순서쌍을 정렬된 리스트 형태로 관리하는 테이블

읽기경로

• 메모리 캐시에 데이터가 없는 경우, 디스크의 SSTable에서 블룸 필터를 이용해 데이터를 가지고 옵니다.

블룸 필터(Bloom filter)의 원리
블룸 필터는 여러 개의 해시함수를 사용해 데이터를 여러 해시 값을 만들고 대응되는 비트 값들을 모두 1로 변경하므로써 비트 배열의 상태를 통해 데이터 값이 없는지 혹은 있을 수 있는지를 파악하는데 도움을 줍니다.
따라서 모든 디스크 데이터를 파악하지 않아도 되기 때문에 조회해야 할 데이터 공간을 축소시켜 줍니다.
블룸 필터 원리의 예

• 예를 들어, 해시 함수 1은 ‘apple’을 3, ‘banana’를 7, ‘orange’를 2로 매핑할 수 있습니다. 해시 함수 2는 ‘apple’을 4, ‘banana’를 2, ‘orange’를 6으로 매핑할 수 있습니다. 마지막으로 해시 함수 3은 ‘apple’을 1, ‘banana’를 5, ‘orange’를 4로 매핑할 수 있습니다.
• 이렇게 해시 함수를 통해 매핑된 각 과일의 여러 해시 값에 대응되는 비트들을 1로 변경하면, 비트 배열의 상태는 다음과 같이 됩니다.

  Index: 1 2 3 4 5 6 7 8
  Value: 1 1 1 1 0 1 1 0

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

ID를 생성할 때 어떻게 해야할까? 프로젝트를 하면서 UUID, auto_increment를 이용해서 간편하게 ID를 생성했었는데 특정 조건이 있을 때 어떻게 ID를 생성하는 것이 좋을까에 대해 알 수 있었습니다.

1단계 문제 이해 및 설계 범위 확정
유일 ID 생성기를 만들어보라고 했을 때 우리는 어떤 걸 확인해야 할까요?

• ID의 특성
• 새로운 ID 생성시 증가
• 구성문자 - 숫자인지 문자인지 혼합인지
• 시스템 규모 (초당 10,000 ID 생성 필요)

2단계 계략적 설계안 제시 및 동의 구하기

• 다중 마스터 복제 (multi-master replication)
  • 데이터베이스의 auto-increment 기능을 활용하는데, 현재 사용중인 데이터베이스 서버의 수만큼 ID 값을 증가시킵니다.
  • 하지만 여러 가지 단점이 존재합니다.
    • 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵습니다.
    • ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞춰 커지도록 보장할 수 없습니다.
    • 서버를 추가하거나 삭제할 때도 잘 동작하도록 하기 어렵습니다.
• UUID (Universally Unique Identifier)
  • 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128bit 자리 수
  • 중복 UUID가 1개 생기기 위해서는 초당 10억개의 UUID를 100년 동안 계속 만들어야 한다고 합니다.
  • 동기화 이슈가 없고, 규모 확장이 쉽습니다.
  • 대신 ID가 128비트로 길고, 시간순 정렬이나 숫자만으로 만들 수 없습니다.
• 티켓 서버
  • 플리커는 분산 기본 키를 만들어 내기 위해 이 기술을 이용했습니다.
  • auto-increment 기능을 가진 데이터베이스 서버를 중앙 집중형으로 쓰는 방식입니다.
  • 하지만 이렇게 하면, 티켓 서버가 SPOF(Single-Point-of-Failure)가 된다는 문제가 있고, 여러 대로 만들면 또 데이터 동기화 이슈가 발생합니다.
• 트위터 스노플레이크 접근법
  • 생성해야 하는 ID 구조를 여러 절로 분할 (64비트 ID를 분할)
    • 사인 비트: 사원여부를 확인하기 위한 1비트
    • 타임스탬프: 기원 시각 이후로 몇 밀리초 경과했는지 나타내는 값
    • 데이터센터 ID
    • 서버 ID
    • 일련번호
• 분산 환경에서 규모 확장이 가능

3단계 상세 설계
2단계에서 설명한 스노우플레이크 접근법에 대해서 상세설계하는 과정입니다. 일단 데이터센터 ID와 서버 ID는 시스템 시작시 결정되는 부분입니다.

• 타임스탬프
  • 41비트를 차지하고 있는 부분인데 시간순 정렬을 가능하게 하고, 이 부분을 10진수화하고 트위터 기원 시각(epoch)을 더하면 밀리초 값이 계산되고 이를 UTC 시각으로 변환하면 값을 구할 수 있습니다.
  • 41비트이므로 최대로 표현할 수 있는 값은 대략 69년(219902325551 밀리초)에 해당합니다.
• 일련번호
  • 12비트이므로 4096개의 값을 가질 수 있습니다.
  • 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어낸 경우에만 0보다 큰 값을 갖게 됩니다.

4단계 마무리
추가로 논의할 수 있는 부분은 어떤게 있을까?

• 시계 동기화
  • ID 생성 서버들이 전부 같은 시계를 사용하지 않을 수 있다는 점
  • NTP(Network Time Protocol)으로 해결할 수 있습니다.
• 각 절의 길이 최적화
  • 동시성이 낮고 수명이 긴 애플리케이션은 일련번호 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적일 수 있습니다.
• 고가용성

8장. URL 단축키 설계

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

• URL 단축키는 긴 URL을 입력했을 때 단축 URL을 제공하고, 단축 URL로 접근했을 때는 원래 URL로 돌아갈 수 있어야 합니다.
• 트래픽 규모
• 단축 URL의 길이
• 단축 URL에 포함될 문자
• 삭제, 갱신 여부

2단계 개략적 설계안 제시 및 동의 구하기

• API 엔드포인트
  • URL 단축용 엔드포인트, URL 디리렉션용 엔드포인트
  • 301 Permanently Moved
    • URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답입니다. 브라우저는 이 응답을 캐시해 추후 요청이 오면 원래 URL로 보내게 됩니다.
    • 서버 부하를 줄이기에 좋은 방법입니다.
  • 302 Found
    • 일시적으로 Location 헤더가 지정하는 URL에 의해 처리해야 한다는 응답으로 항상 단축 URL 서버를 통하게 됩니다.
• URL 단축에 적절한 해시함수를 찾는 것이 중요합니다.

3단계 상세 설계
메모리보다는 관계형 데이터베이스에 단축 URL, 원래 URL 순서쌍을 저장합니다. 단축을 위해서는 해시 함수를 사용하는데 원하는 단축값의 길이, 문자 유형 등을 고려해야 합니다.
책에서는 해시 후 충돌 해소 전략과 Base-62 변환을 소개하고 있습니다.

• 해시 후 충돌 해소 전략
  • 단축 URL 길이를 더 줄이기 위해서 해시 값의 일부만 사용하는 경우에는 충돌이 발생할 수 있습니다.
  • 이를 해소하기 위해 충돌해소까지 사전에 정한 문자열을 추가해서 해시함수를 사용하는 방법도 있습니다.
  • 하지만 결국, 데이터베이스로 반복적으로 조회해야 하기 때문에 오버헤드가 크다는 문제가 있습니다.
  • CRC32, MD5, SHA-1
• base-62 변환
  • 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자가 62개이기 때문이고, 62진법의 나머지에 따라 62진수로 표현하는 방식입니다.
  • 이 경우 ID 유일성 보장된 후 에 적용 가능한 전략이라 충돌이 불가능합니다.
  • 대신 다음 단축 URL이 무엇인지 쉽게 알아낼 수 있다는 문제가 있습니다.

4단계 마무리
추가로 논의할 사항들

• 처리율 제한 장치
• 웹 서버의 규모 확장
  • 웹 계층이 무상태 계층으로 설계되어 있으므로 자유롭게 증설 삭제가 가능합니다.
• 데이터베이스 규모 확장
• 데이터 분석 솔루션
  • 어떤 링크로의 사용자 접근이 많은지 언제 클릭했는지 등을 데이터 분석 솔루션을 통합해두면 알 수 있습니다.
• 가용성, 데이터 일관성, 안정성