program punch!

https://product.kyobobook.co.kr/detail/S000001033116

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

요구사항

- 1:1채팅, 그룹 채팅 모두 지원

- 웹/앱 모두 지원

- DAU는 5천만명

- 그룹 채팅 최대 인원은 100명

- 사용자의 접속상태를 표시해야함

- 메시지 길이는 100,000자 이하여야 한다.

- 채팅 이력은 영원히 보관해야 한다.

채팅 프로토콜

채팅 서비스는 메시지 송신 클라언트로부터 메시지를 받아서 저장하고, 메시지 수신 클라이언트에게 메시지를 전달해야 한다. 이를 위해 어떤 프로토콜을 사용할지 살펴보자.

- 폴링

폴링은 주기적으로 수신 클라이언트가 서버에게 새 메시지가 있는지 물어보는 방식이다 . 이 방식은 서버 자원 불필요하게 낭비된다는 단점이 있다.

- 롱 폴링

폴링의 단점을 완화하기 위해서 새 메시지가 반환되거나 타임아웃 될 때까지 연결을 유지하는 방식이다. 이 방식은 수신 클라이언트와 송신 클라이언트가 다른 서버에 접속할 수도 있다는 문제가 있다. 또한 서버 입장에서 클라이언트가 연결을 해제했는지 아닌지 알 방법이 없다. 그리고 무엇보다 여전히 비효율적이다.

- 소켓
웹소켓은 서버가 클라이언트에게 비동기 메시지를 보낼 때 가장 널리 사용하는 기술이다. 웹 소켓은 HTTP 기반의 방식들과 달리 클라이언트가 시작한다. 한번 맺어진 연결을 항구적이며 양방향이다. 웹 소켓을 이용하면 메시지를 보낼 때나 받을 때 동일한 프로토콜을 사용할 수 있으므로 설계와 구현이 단순하고 직관적이다. 다만 웹소켓 연결은 항구적으로 유지되어야 하기 때문에 서버 측에서 연결 관리를 효율적으로 해야 한다.

개략적인 설계

개략적인 설계는 무상태 시스템, 상태 유지 시스템, 제 3자 서비스 연동 시스템으로 나눌 수 있다.

- 무상태 서비스

무상태 서비스는 일반적인 API서버와 동일하게 로그인, 회원가입, 사용자 프로파일 표시 등을 처리한다.

- 상태 유지 서비스

채팅 서버는 상태 유지가 필요하다. 이는 클라이언트가 채팅 서버와 독립적인 네트워크 설정을 유지해야 하기 떄문이다.

- 제 3자 서비스 연동

제 3자 서비스는 푸시 알림이다. 새 메시지를 받았다면 앱이 꺼져 있어도 알람이 와야 할 것이다.

- 규모의 확장성

SPOF를 막기 위해서라도 규모의 확장성을 고려하는 것은 필수적이다. 위의 언급된 요소들을 하나로 묶으면 다음과 같은 개략적인 설계안이 나온다. (키-값 저장소에는 채팅 이력을 보관한다.)

- 저장소

사용자 프로파일/설정/친구 목록 처럼 일반적인 데이터는 RDB에 보관하면서 다중화와 샤딩과 같은 기술을 고려한다.

채팅 이력 데이터는 키-값 저장소를 사용한다. 이를 이해하려면 채팅 이력 데이터의 읽기/쓰기 연산 패턴을 이해 해야 한다.

1. 채팅 이력 데이터는 양이 많다.(페북 메신저는 매일 600억개의 메시지를 처리한다)

2. 최근 주고받은 데이터를 주로 본다. 오래된 메시지는 잘 보지 않는다.

3. 검색 기능, 특정 사용자 언급 메시지, 특정 메시지로 점프 등의 기능을 위해 무작위 데이터 접근하는 기능도 지원해야한다.

4. 1대1채팅 앱의 경우 읽기:쓰기 비율은 대략 1:1이다.

이런 특징을 모두 지원하기 위해 키-값 저장소를 사용하는데 그 이유는 다음과 같다.

1. 수평적 규모확장이 쉽다.

2. 접근 지연시간이 낮다.

3. RDB는 롱 테일에 해당하는 부분을 잘 처리하지 못한다. 또한 인텍스가 커지면 데이터 무작위 접근 비용이 증가한다.

4. 이미 많은 채팅 시스템이 키-값 저장소를 사용한다.

 - 데이터 모델

키-값 저장소를 사용하기로 했으니 이제 메시지 데이터를 어떤 형태로 보관할 것인지 살펴보자. 왼쪽은 1:1 메시지를 저장할 떄 사용하는 테이블이고, 오른쪽은 그룹 메시지를 저장할 때 사용할 테이블이다.

message_id는 다음과같은 조건을 만족해야 한다.

- 고유해야한다.

- ID값은 정렬 가능해야 하며 시간 순서와 일치해야 한다.

이를 위한 전략은 앞서 살펴본 SnowFlake와 같은 방식과 지역적 순서 번호 생성기를 이용하는 것이다. 여기서 지역적 순서 번호 생성기는 ID의 유일성은 같은 그룹 안에서만 보증하면 충분하는 것이다.

상세 설계

이제 상세 설계를 살펴보자

서비스 탐색(상세 설계)

서비스 탐색 기능의 주된 역할은 클라이언트에게 가장 적합한 채팅 서버를 추천해 주는 것이다. 이때 위치, 서버 용량 등을 기준으로 선택한다. 이를 위해 아파치 주키퍼와 같은 오픈소스를 사용할 수 있다. 서비스 탐색은 다음과 같이 동작한다.

메시지 흐름(상세 설계)

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

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

채팅은 모바일, 데스크톱, 테블릿 등의 다양한 단말에서 사용할 수 있다. 각 단말을 동기화 하는 방식은 다음과 같은 방식으로 이루어 진다.

채팅 서버에서는 사용자의 모든 단말에 대한 웹 소캣 연결을 유지한다. 그리고 각 단말은 본인이 읽어온 가장 최신 메시지의 ID를 가지고 있다. 이제 각 단말에 접근했을 때 다음과 같은 2가지 조건을 만족하는 메시지는 새 메시지로 간주한다.

- 수신자 ID가 현재 로그인한 사용자 ID와 같다.

- 키-값 저장소에 보관된 메시지로서, 그 ID가 cur_max_message_id보다 크다.

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

현재 요구사항은 그룹채팅이 500명까지 가능하므로, 소규모라고 볼 수 있다. 이를 위해서는 메시지 큐를 사용자 단말마다 하나씩 생성해서 두고, 송신 측에서 보내야 하는 사용자에게 넣어주면 된다.

이 방식은 소규모 그룹 채팅에서 적합한데 그 이유는 새 메시지를 확인하기 위해 자기 큐만 보면 되니까 동기화가 쉽고, 그룹이 크지 않다면 메시지를 수신자별로 복사해서 큐에 넣는 작업의 비용이 크지 않기 때문에 좋다.

접속상태 표시(상세 설계)

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

로그 아웃은 단순히 키-값 저장소에 저장소에 보관된 사용자 상태가 online에서 offline으로 변경되면 된다.

- 접속 장애

네트워크 환경은 언제가 가용하지 않는다. 예컨데 터널만 들어가도 그렇다. 그래서 x초 이상 통신이 되지 않는 경우에만 접속상태를 offline으로 변경해야 한다. 이를 위해서 저자는 박동(heartbeat)검사를 제안한다. 즉, 온라인 상태의 클라이언트로 하여금 주기적으로 박동 이벤트를 서버로 보내고, 마지막 이벤트를 받은 지 x초가 지나도 다음 박동 이벤트가 오지 않으면 오프라인으로 바꾸는 것이다.

- 상태 정보의 전송

발행-구독 모델을 사용해서 사용자의 상태 변화를 알릴 수 있다. 이는 친구관계당 하나씩 채널을 두는 것으로 하면 된다. 이 방법은 그룹의 크기가 작을 때 효과적이다. 하지만 그룹 크기가 커지면 이런 식으로 접속 상태 변화를 알려서는 비용이나 시간이 많이 들게 되므로 좋지 않다.

근데 왜 친구관계당 하나씩 두는지는 잘 이해되지 않는다. 사용자당 하나의 채널을 만들어두고, 구독자를 여러명 두면 되는 것 아닌가? 메시지가 소비되는 것이 문제라면 메시지에 읽어야 하는 사용자 수를 기록해 두고 한명의 사용자가 읽을 때마다 1씩 감소시켜서 0이 되면 메시지를 최종적으로 삭제하도록 할 수는 없는것인가? 혹시 동시성 문제가 걱정되는 것인가?

https://product.kyobobook.co.kr/detail/S000001033116

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

뉴스피드 설계는 개인적으로 이해하기 어려운 부분이 있었다. 마이크로 서비스를 시작으로 시스템을 설계하기 때문이다. 하지만 천처히 따라가 보자.

요구사항

- 모바일과 웹 둘다 자원하는 시스템이다

- 주요기능 : 새로운 스토리를 올릴 수 있어야 하고, 친구가 올리는 스토리를 볼 수 있어야 한다.

- 뉴스피드는 시간 흐름 역순으로 표시한다.

- 한명의 사용자는 최대 5000명의 친구를 가질 수 있다.

- 매일 천만 명이 방문한다.

- 스토리에 미디어 파일이 포함될 수 있다.

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

설계는 피드 발행(feed publishing)과 뉴스 피드 생성(news feed building)의 두 부분으로 나뉘어 진다.

- 피드 발행: 사용자가 스토리를 포스팅하면 해당 데이터를 캐시와 DB에 저장하며, 새 포스팅은 친구의 뉴스 피드에도 전송된다.

- 뉴스 피드 생성: 뉴스 피드는 모든 친구의 포스팅을 시간 흐름에 따라 역순으로 만든다.

피드 발행(개략적 설계)

뉴스 피드 생성(개략적 설계)

피드 발행 흐름 상세 설계

이 시스템은 사용자가 포스팅을 하면 포스트를 DB에 저장하는 피드 발행 시스템과 사용자가 피드를 확인하면 포스트들의 집합을 보여주는 피드 시스템으로 이루어져 있다. 여기서 가장 부하가 많고, 고민스러운 부분은 뉴스 피드를 조회했을 때 수많은 포스트 중에 사용자에게 보여줘야하는 피드가 무엇인지 선택하는 것이다. 심지어 최대한 빠르게 말이다. 이를 위해서 책에선 포스팅 시스템에 전송 서비스를 넣어 둔 것이다. 이를 통해서 사용자에 따라 피드를 빠르게 구성할 수 있다. 여기서 설계자는 포스팅 전송(팬아웃) 서비스를 구성하기 위해 2가지 전략을 선택할 수 있다.

- 쓰기 시점에 팬아웃 하는 모델(푸시 모델)

포스팅을 기록하는 시점에 뉴스 피드를 갱신. 즉, 포스팅이 완료되면 바로 해당 사용자의 캐시에 기록

장점

1. 뉴스 피드가 실시간으로 갱신되며 친구 목록에 있는 사용자에게 즉시 전송

2. 새 포스팅이 기록되는 순간 뉴스 피드가 갱신되므로, 뉴스 피드를 읽는 속도가 빠름

단점

1. 친구가 많은 사용자는 전송에 시간이 오래걸린다. 이는 핫키(hotkey) 라고 부르는 문제이다.

2. 서비스를 자주 이용하지 않는 사용자의 피드까지 갱신하는 비효율이 존재

- 읽기 시점에 팬아웃 하는 모델(풀 모델)

피드를 읽어야하는 시점에 뉴스 피드를 갱신(on-demand model)

장점

1. 비활성화/자주 사용하지 않는 유저를 위한 컴퓨터 자원을 소모하지 않는다.

2. 핫키 문제가 발생하지 않는다.

단점

1. 뉴스피드를 읽는데 오래 걸릴 수 있다.

저자는 2가지 방법의 장점을 취하고 단점을 버리는 전략을 제안한다. 대부분에 사용자에 대해서는 푸시 모델을 사용하고, 핫키 문제가 발생할 수 있는 친구나 팔로어가 맣은 사용자는 풀 모델을 사용하는 것이다. 아울러 안정 해시를 통해 요청과 데이터를 보다 고르게 분산하여 핫키 문제를 최소화 한다.

피드 읽기 흐름 상세 설계

미디어 파일은 CDN에 저장해서 전송 속도를 높혔다.

https://product.kyobobook.co.kr/detail/S000001033116

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

이 챕터를 읽으면서 호환성과 확장성이 좋은 프로그램을 오픈소스로 만들어보고 싶다는 생각이 들었다. 알람시스템은 언제나 필요하기 때문에 완성도 있는 프로그램을 만들어둔다면 두고두고 잘 쓰지 않을까?

 요구사항

- 푸시알림, SMS메시지, 이메일을 지원해야한다.

- 연성 실시간(soft real-time)이어야 한다.

- 푸시알림은 iOS, 안드로이드, 랩톱/데스크톱을 지원해야 한다.

- 알림은 클라이언트 애플리케이션 프로그램이 만들수도, 서버에서 스케줄링 할 수도 있다.

- 사용자가 알람 수신을 거부할 수 있다.

- 하루에 천만 건의 모바일 푸시 알림, 백만 건의 SMS 메시지, 5백만 건의 이메일을 보낼 수 있어야 한다.

아래에서는 다음과 같은 내용을 다룬다.

- 알림 유형별 지원 방안

- 연락처 정보 수집 절차

- 알림 전송 및 수신 절차

알림 유형별 지원 방안

iOS는 APNS라는 애플이 제공하는 푸시 알림을 iOS장치로 보내는 열할을 담당하는 원격 서비스가 필요하다. 

안드로이드는 APNS 대신 FCM(Firebase Cloud Messaging)을 사용한다.

SMS는 다양한 제3 사업자의 서비스를 사용한다.

이메일 역시 다양한 제3 서비스를 사용한다. 물론 직접 메일 서버를 구축해도 좋지만, 전송 성공률도 높고 데이터 분석도 제공하는 제 3자 서비스가 선호된다.

연락처 수집 절차

사용자가 직접 입력해줘야 한다.

알림 전송 및 수신 절차

알림 시스템에게 요청을 보내면 알림시스템이 각각의 알림 유형별로 알림보내기 위한 초안이다. 하지만 알림 시스템이 하나의 서버로 이루어져 있어서 몇가지 문제를 발생시킨다. 알림 시스템은 SPOF가 될 것이며, 규모의 확장성(DB나 캐시 등 컴포넌트의 규모를 개별적으로 늘릴 수 없다)이 부족하다. 또한 성능 병목이 될 것이다.

개략적 설계안(개선된 버전)

DB와 캐시를 분리하고, 메시지 큐를 통해 컴포넌트들 사이의 강한 결합을 끊었다.

상세 설계

앞서 살펴본 개략적인 설계에서 다음과 같은 세부 설계를 살펴보쟈ㅏ

- 안정성

- 추가 컴포넌트 및 고려사항

- 개선된 설계안

안정성

- 데이터 손실 방지

각 작업서버에서 알림 로그 데이터 베이스를 둬서 어떤 상황에서도 알림이 소실되지 않게 만들 수 있다.

- 알림 중복 전송 방지

중복을 완벽하게 막는 것은 불가능하다. 분산 시스템의 특성상 가끔 같은 알림이 중복 전송되기도 할 것이다. 하지만 그 빈도를 줄이기 위해 중복 탐지 알고리즘을 적용할 수 있을 것이다. 그 대표적인 방법으로 이벤트 ID를 검사해서 이전에 본 적이 있는 이벤트인지 살필 수 있다.

 추가로 필요한 컴포넌트 및 고려사항

- 알림 템플릿

대형 알림 시스템은 하루에도 수백만 건 이상의 알림을 처리한다. 하지만 대부분 형식이 같으므로 템플릿을 만들어두면 편하게 알림을 보낼 수 있고, 알림들의 형식을 일관성 있게 유지하며, 오류를 줄이고 시간을 아낄 수 있다.

- 알림 설정

사용자가 알림을 받고자 하는 채널과 알림 전공 여부를 설정해 줄 수 있다. 이 정보는 알림 설정 테이블에 보관한다.

- 전송률 제한

사용자가 너무 많은 알림을 받지않도록 하는 한가지 방법은 사용자가 받을 수 있는 알림의 빈도를 제한하는 것이다. 사용자는 너무 알림이 많으면 알림을 꺼버리기 마련이다.

- 재시도 방법

실패한 알림을 재시도 전용 큐에 넣고 재시도 하며, 같은 문제가 반복적으로 발생하면 개발자에게 통지한다.

- 푸시 알림과 보안

iOS와 안드로이드는 appKey와 appSecret을 사용하며 보안을 유지한다. 따라서 인증된(또는 승인된) 클라이언트만해당 API를 사용해서 알림을 보낼 수 있다.

- 큐 모니터링

큐에 쌓인 알림의 갯수를 모니터링 해서 서버 증설을 계획할 수 있다.

-이벤트 추적

데이터 분석 서비스는 보통 이벤트 추적 기능도 제공한다. 따라서 알림 시스템을 만들면 데이터 분석 서비스와 통합해서 알림 확인율, 클릭율, 실제 앱 사용으로 이어지는 비율 등을 확인해야 한다.

수정된 설계안

https://product.kyobobook.co.kr/detail/S000001033116

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

이번 장에서는 웹 크롤러를 설계해본다. 웹 크롤러는 다음과 같은 목표로 사용되곤 한다.

- 검색 엔진 인덱싱

- 웹 아카이빙

- 웹 마이닝

- 웹 모니터링

요구사항

- 검색 엔진 인덱싱 용으로 사용

- 1달에 10억 개의 웹 페이지 수집

- 수집한 웹 페이지는 5년간 저장

- 중복 컨텐츠 무시

- 규모의 확장성, 안정성, 예절, 확장성을 확보한다.

개략적 규모 추정

- QPS = 10억 * 30일 * 24시간 * 3600초 = 400페이지/초

- Peak QPS = 2* QPS = 800

- 1달간 필요한 저장공간 = 10억 페이지 * 500k(웹 페이지의 평균 크기) = 500TB/월

- 5년간 데이터를 보관한다는 가정 하에 최종적으로 필요한 저장 공간 = 500TB * 12Month * 5년 = 30PB

우선 기본적인 설계를 살펴본다. 이미 직관적으로 이해가 되는 그림이지만, 각 파트에의 세부적인 부분에 대해서만 조금 이야기해보자.

-미수집 URL 저장소

아직 다운로드 하지 않은 URL을 저장 관리하는 컴포넌트다. FIFO Queue로 구현된다.

-콘텐츠 파서

웹 페이지를 다운로드하고 파싱과 검증을 통해 필요없는(또는 이상한) 페이지를 제외한다.

-중복 콘텐츠인가?

중복 컨텐츠는 해시 값을 비교하는 것을 통해서 중복을 제거한다.

-URL 추출기

HTML페이지를 파싱하여 링크들을 모두 골라낸다.

-URL 필터

접근 제외 목록, 오류 발생URL, 특정 콘텐츠 타입이나 파일확장자를 갖는 URL 등을 걸러준다.

-이미 방문한 URL?

부하를 줄이고 무한 루프를 방지하기 위해 이미 방문한 URL을 제외한다. 이는 블룸필터나 해시 테이블이 널리 사용된다.

상세 설계

DFS vs BFS

DFS를 사용해서 URL을 수집하면 어디까지 깊게 들어갈지 몰라서 선호하지 않는다. 따라서 크롤러는 주로 BFS를 사용하는데, 이도 2가지 문제가 있다. 

첫째로 하이퍼링크로 찾는 URL들은 기존 서버에게로 가는 요청일 확률이 아주 높아서, BFS의 FIFO Queue에 들어가는 URL들이 모두 기존서버일 확률이 높다. 이 수집하려는 사이트에 부하를 줄 수 있어서, 예의 없는 크롤러로 간주된다.

둘째로 BFS 알고리즘은 URL간에 우선순위가 없다. 하지만 페이지 중에서도 중요도를 판단해서 우선순위를 구별하는 것이 좋다.

미수집 URL 저장소

예의 있게  URL을 수집하기 위해 같은 호스트에 속하는 모든 URL은 같은 큐에 넣어두자. 그리고 각 큐를 순회하면서 크롤링을 하는 작업 스레드에게 URL 다운로드 작업을 요청한다. 이때 같은 호스트에 속하는 URL끼리는 시간을 두고 수집하기도 한다.

URL간의 우선순위를 두기 위해서 트래픽 양, 갱신 빈도, 페이지 랭크 등의 척도를 사용한다. 우선순위에 의해서 분리된 URL은 각각의 우선순위마다 정의되어있는 큐에 넣는다. 그 뒤로 각 큐에서부터 URL을 꺼내서 앞서 설면한 호스트별 큐에 넣게 된다. 

한번 수집된 페이지가 변경되는 경우도 있다. 이런 경우에는 우선순위에 따라 자주 재수집하거나, 웹 페이지의 변경 이력을 활용할 수 있을 것이다.

HTML 다운로더

HTML다운로더에 사용한 수 있는 성능 최적화 방법은 분산 크롤링, 도메인 이름 변환 결과 캐시, 지역성(크롤링 서버를 분산해서 물리적으로 가까운 서버에서 HTML을 다운받는 것), 짧은 타임아웃이 있다. 

안정성 확보 전략

안정 해시를 통한 분산 크롤러 서버를 관리하는 것과 크롤링 상태 및 수집 데이터를 저장해서 쉽게 해결하는 전략, 그리고 예외 처리와 데이터검증을 통해 안정성을 확보할 수 있다. 

확장성 확보 전략

앞서 보여준 설계에서 URL 추출기를 새로운 모듈로 갈아끼울 수 있도록 설계해서 새로운 형태의 콘텐츠를 지원하는 모듈을 확장할 수있다. 

문제 있는 콘텐츠 감지 및 회피 전략

1. 중복콘텐츠

해시나 체크섬을 통해 중복 콘텐츠를 탐지하자.

2. 거미 덫

예건케 다음과 같이 무한히 깊은 디렉터리 구조를 포함할 수 있다.

spidertrapexample.com/foo/bar/foo/bar/foo/bar/foo ...

이런 종류는 URL의 최대 길이를 제한하면 된다. 하지만 모든 종류의 덫을 피할 수 있는 해결책은 없다. 이런 덫이 설치된 사이트는 수작업으로 찾은 후 덫이 있는 사이트를 필터로 제안하는 방식이 주로 사용된다.

3. 데이터 노이즈

광고나, 스크립트 코드, 스팸 등의 가치없는 데이터는 최대한 제외해야한다.

https://product.kyobobook.co.kr/detail/S000001033116 

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

이번 장에서는 URL 단축 서비스를 설계해 볼 것이다. 그 전에 URL 단축 서비스가 왜 필요한지 먼저 이야기 해보자. 사실 필자는 URL 단축 서비스를 사용해본 적이 없다. 조금 긴 URL을 전송하거나 사용한다고 해서 큰 문제가 발생하지 않기 때문이다. 하지만 아마 twitter와 같이 제한된 글자 수를 보낼 수 있는 서비스를 사용하는 사람들은 URL을 짧게해야 한다는 필요성이 있을 것이다. 최근 자주 보고 있는 유명한 서비스로 bit.ly와 tiney url과 같은 서비스가 있다.

요구사항

- URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.

- URL 리디렉션(redirection): 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내

- 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨

개략적인 추정

- 쓰기 연산: 매일 1억 개의 단축 URL 생성

- 초당 쓰기 연상: 1억/24/3600=1160

- 읽기 연산: 읽기 연산과 쓰기연산의 비율을 10:1로 한다. 따라서 초당 읽기 연산은 11600이다.

- URL단축 서비스를 10년간 운영한다고 가정하면 1억*365*10=3650억개의 레코드를 보관해야 한다.

- 축약 전 URL의 평균 길이는 100B라고 가정하자. 따라서 10년 동안 필요한 저장 용량은 3650억 * 100Byte = 36.5TB이다.

데이터 모델

단축 URL 서비스를 위해서는 데이터를 어떤 형태로 저장해 둬야할까? 간단하게 DB에 id, shortURL, longURL으로 저장하면 된다. (실제 테이블은 이것보다 더 많은 칼럼을 가질 수 있지만, 간추린 것이다) 이게 logURL으로 shortURL을 만드는 방법을 알아보자.

해시함수

앞선 요구사항에서 3650억개의 레코드를 저장해야 했기 때문에, Hash Value의 길이는 7으로 정하자.(hashValue는 [0-9, a-z, A-Z]총 62개의 문자로 구성되며, 62^7 = 약 35조로 충분하다) 해시 함수 구현에 쓰일 기술로는 해시 후 충돌 해소 방법과 base-62변환을 살펴보자.

해시 후 충돌 해소

잘 알려진 해시 함수는 CRC32, MD5, SHA-1 등이 있다. 이때 7글자를 넘는 해시 결과는 뒤를 잘라서 사용하자. 이렇게 되면 충돌확률이 증가하는데, 충돌이 발생하면 기존 hashFunction에 넣어줬던 longURL의 맨 뒤에 정해진 문자열을 더해서 다시 hashFunction에 넣어주는 식으로 해결한다.

이 방법은 충돌을 해결하지만, URL을 생성할때 DB 조회를 여러번 해야 하므로 오버헤드가 크다. 이때 어떤 집합에 특정 원소가 있는지 검사할 수 있는 확률론에 기초한 공간 효율이 좋은 기술인 블룸 필터를 사용할 수 있다.

블룸필터는 개념도 간단하고 재미있기 때문에 꼭 찾아보길 추천한다.

base-62 변환

base-62방식은 특정 진법으로 되어있는 숫자를 62진법으로 변환하는 것이다. 이때 62진법인 이유는 앞서 확인했던 것 처럼 hashValue가 62개의 문자로 구성되어 있기 때문이다. 이제 ID값을 shortURL 생성 요청이 들어올 때마다 만들어서 생성된 ID를 62진법으로 변환한 결과를 URL으로 사용하게 된다.(ID를 생성하는 방법은 앞선 7장에서 열심히 살펴봤다)

https://product.kyobobook.co.kr/detail/S000001033116

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

이번 장에서는 분산환경에서 사용될 유일 ID 생성기를 설계한다. auto_increment 속성이 설정된 관계형 데이터베이스의 기본 키를 사용하는 것은 DB서버 한대로 그 요구를 감당할 수 없을 뿐더러, 여러 DB서버를 쓰는 경우에는 지연 시간을 낮추기가 무척 힘들 것이기 때문에 불가능하다. 이제 아래에서 자세한 설계를 살펴본다.

요구사항

- ID는 유일해야 한다.

- ID는 숫자로만 구성되어야 한다.

- ID는 64비트로 표현될 수 있는 값이어야 한다.

- ID는 발급 날짜에 따라 정렬 가능해야 한다.

- 초당 10,000개의 ID를 만들 수 있어야 한다.

후보

1. 다중 마스터 복제(multi-master replication)

다중 마스터 복제는 n개의 DB서버에서 1씩 증가하는 값을 생성하는 것이 아니라, n씩 증가하는 값을 생성하는 것이다. 하지만 이 방식은 여러 데이터 센터에 걸쳐 규모를 늘리기 어려우며, 서버를 추가/삭제할 때도 잘 동작하도록 하기 어렵다. 그리고 ID의 유일성은 보장되지만, 시간이 흐름에 따라 커지도록 할 수 없다.

2. UUID

UUID는 랜덤한 값을 사용하는 128비트짜리 수다. 충돌확률이 0에 가깝게 작다.(물론 0은 아니다) UUID는 각 서버에서 독립적으로 ID를 발급하는 방식이기 때문에 동기화이슈도 없고, 단순하다. 또한 규모에 확장 역시 간편하다. 하지만 128비트로 길이가 길고, 시간순으로 정렬할 수 없으며, ID에 숫자가 아닌 값이 포함된다는 단점이 있다.

3. 티켓서버

ID를 생성하는 서버를 하나 두고 필요할 때마다 발급 받는 것이다.(아이디를 생성하는 방식은 auto_increment) 이는 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다. 구현이 쉽고, 중소 규모 애플리케이션에 적합하다. 하지만 티켓서버가 SPOF가 된다는 치명적인 단점이 있다.

4. 트위터 스노플레이크 접근법(땅땅땅 결정)

트위터 스노플레이스 ID 생성 기법은 다음과 같다.

사인 비트(1비트) + 타임스탬프(41비트) + 데이터센터 ID(5비트) + 서버 ID(5비트) + 일련번호(12비트)

이 방법은 앞선 모든 요구사항을 만족시킬 수 있다!

https://product.kyobobook.co.kr/detail/S000001033116

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

이번장도 필자가 재밌게 읽었던 부분 중에 한 파트이다. 특히 5장과 연계되어서 설명되는 다양한 해결책들을 보고있으면 이마를 탁 치게 된다.

키-값 저장소에서는 키를 통해서만 값에 접근할 수 있다. 이때 키는 일반 텍스트일 수도 있고 해시 값일 수도 있다. 성능상의 이류로, 키는 짧을수록 좋다.

요구사항

- 키-값 쌍의 크기는 10KB 이하이다.

- 큰 데이터를 저장할 수 있어야 한다.

- 높은 가용성을 제공해야 한다. 따라서 트래픽 양에 따라 자동적으로 서버 증설/삭제가 이루어져야 한다.

- 데이터 일관성 수준은 조정이 가능해야 한다.

- 응답 지연시간(latency)이 짧아야 한다.

단일 서버 키-값 저장소

이 방식은 아주 쉽다. 가장 직관적인 방식은 메모리에 해시 테이블로 키-값 쌍을 저장하는 것이다. 물론 이 방식은 빠르지만, 저장 공간이 부족할 수 있다. 이를 해결하기 위해서 데이터 압축과 자주 사용되지 않는 데이터는 디스크에 저장하는 방법이 있다. 하지만, 이렇게 개선한다고 해도 앞선 장에서 계속 그랬듯, 단일 서버로는 부족하다. 이제 분산 키-값 저장소를 설계하기 위한 기본 지식으로 CAP 정리를 확인해보자.

분산 키-값 저장소

분산시스템을 설계할 때는 CAP 정리를 이해해야한다.

CAP 정리는 일관성(Consistency), 가용성(Availability), 파티션 감내(Partition Tolerance)라는 세가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능 하다는 것이다. 따라서 목적에 따라 CA시스템, CP시스템, AP시스템 중에 하나를 선택해서 분산 시스템을 설계해야 한다.

일관성, 가용성, 파티션 감내의 의미가 어려워서 자세히 적어둔다.

- 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 항상 같은 데이터를 보게 된다.

- 가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.

- 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야 한다는 것을 뜻한다.

CA시스템은 파티션 감내가 절대 발생하지 않을 것이라는 아주아주 이상적인 상태를 의미한다.(실세계에선 네트워크 장애를 피할 수 없기 때문에 불가능 하다) 따라서 우린 파티션 문제가 발생하면 우린 일관성과 가용성 사이에서 옵션을 선택해야 한다. 일관성을 지키기 위해서는 CP 시스템을 선택하면 파티션 문제가 발생했을 때 모든 노드에서 쓰기 연산을 중지해야 할 것이다. 따라서 이 방식은 가용성이 깨지게 된다. 반면 AP 시스템은 파티션 문제로 낡은 데이터를 반환하는 한이 있더 계속해서 읽기 연산과 쓰기 연산을 허용한다. 그리고 파티션 문제가 해결 됐을 때 변경된 데이터의 정합성을 맞추는 것이다.

이제 설계하려는 시스템의 목적에 따라서 CP 또는 AP 시스템을 설계하면 된다. 

시스템 컴포넌트

이제 분산 키-값 저장소를 설계하기 위해 필요한 핵심 컴포넌트들 및 기술들에 대해서 살펴 볼 것이다.

1. 데이터 파티션

데이터를 여러 서버에 고르게 분산하기 위해서 5장에서 살펴본 안정 해시를 사용하다. 안정 해시를 사용하므로서 규모의 확장 자동화(시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되는 것)와 다양성(가상 노드를 통해 고성능 서버는 더 많은 가상 노드를 가지게 해서 각 서버에 맞게 데이터의 양을 조절할 수 있다)

2. 데이터 다중화

높은 가용성과 안정성을 확보하기 위해서 데이터를 여러 서버에 비동기적으로 다중화 할 필요가 있다. 이는 안정 해시에서 현재 노드 다음 순서에 있는 노드에 데이터를 복제하는 방식으로 달성할 수 있다.

3. 데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화 되어야 한다. 이를 위해 정족수 합의(Quorum Consensus) 프로토콜을 사용할 수 있다. 정족수 합의 프로토콜의 각 설정값을 조정하는 것으로 응답 지연과 데이터 일관성 사이의 타협점을 찾을 수 있다.

4. 일관성 모델

일관성 모델은 키-값 저장소를 설계할 때 고려해야할 또 하나의 중요한 요소다. 일관성 모델은 3가지의 종류가 있는데, 이 개념은 자주 사용되는 개념으로, 이 글에서 간단히 언급하고 넘어가겠다.

- 강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다.

- 약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다.

- 최종 일관성 : 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영되는 모델이다.

강한 일관성을 달성하기 위해서는 모든 사본에 현재 쓰기 연산이 동기화 될 때 까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것이다. 이는 고가용성 시스템에는 적합하지 않다. 따라서 최종 일관성을 자주 사용한다.

최종 일관성 모델을 사용하는 경우 비 일관성 해소 방법으로 버저닝과 벡터 시계라는 기술이 있다. 

5. 장애 처리

장애 감지

어떤 서버가 죽었다는 사실을 알기 위해서는 모든 노드 사이에 멀티 캐스팅 채널을 구축해서 감지할 수 있다. 하지만 이 방법은 서버가 많으면 분명 비효율적이다. 따라서 가십 프로토콜(hossip protocol), 분산형 장애 감지(decentralized failure detection) 솔루션을 사용하는 것이 효과적이다.

일시적 장애 처리

네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아서 처리하고, 해당 서버가 복구 되었을 때 일관 반영하여 데이터 일관성을 보존한다. 이러한 방식을 임시 위탁 기법이라고 부른다.\

영구 장애 처리

영구적인 노드의 장애 상태를 처리하기 위해서는 반-엔트로피(anti-entropy)프로토콜을 구현하여 사본들을 동기화 할 것이다. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클(Merkle)트리를 활용할 것이다.

데이터 센터 장애 처리

데이터 센터 장애에 대응할 수 있는 시스템을 만들기 위해 데이터 센터를 다중화해야한다

https://product.kyobobook.co.kr/detail/S000001033116

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

이 파트는 필자가 정말 재밌게 읽었던 부분이다. 안정해시와 관련해서 최범균님의 영상도 있으니 관심있는 사람은 같이 봐도 좋을 것 같다.

https://www.youtube.com/watch?v=UQfNytDFpgk&t=281s 

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

해시 키 재배치(rehash)문제

N개의 캐시서버에 부하를 균등하게 나누기 위해서 일반적으로 아래의 해시함수를 이용한다.

serverIndex = hash(key) % N

그런 만약 여기서 캐시 서버가 증가하거나 제거된다면 문제가 생긴다. N -> N-1으로 변경되었으니, 기존에 들어있던 데이터들이 잘못된 위치에 들어간 꼴이 되는 것이다. 따라서 현재 서버에 들어가 있는 대부분의 데이터를 다른 서버로 재 분배 해야한다. 안정해시는 이 문제를 효과적으로 해결하는 기술이다.

안정 해시

안정해시는 해시 테이블 크기가 조정 될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다.(k=키 개수, n=슬롯 개수)
해시 함수로 SHA-1을 사용한다고 했을 때 함수의 출력 값 범위(해시 공간; hash space)는 0~ 2^160-1이다. 여기서 처음과 끝을 연결해서 연결리스트처럼 만든 모양을 해시 링이라고 부른다.

해시 서버

해시 서버를 사용하면 해시 링의 특정 위치에 서버를 위치 시킬 수 있다. 이제 링의 특정 위치에 할당되는 서버는 특정 위치에서 값을 증가시키면서 가장 먼저 만나는 서버로 정할 수 있을 것이다. 그럼 서버가 제거된다면 제거된 서버 다음순서로 있던 서버로 기존 데이터를 옮기면 될 것이고, 서버가 추가된다면 추가된 서버 다음에 있는 서버에 할당되어 있던 데이터들 중에 추가된 서버보다 앞에 있던 데이터를 추가된 서버로 옮기면 될 것이다. 

안정 해시 알고리즘의 기본 절차는 2가지이다.

1. 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.

2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.

이 접근법은 2가지 문제가 있다.

1. 서버가 추가/삭제 된다면 파티션의 크기를 균등하게 유지할 수 없다.

2. 해시의 특성상 특정 서버에 데이터가 몰릴 수 있어서 키의 균등 분포를 달성하기 어렵다.

이 문제들을 해결하는 방법이 바로 가상 노드이다.

가상 노드

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.(바로가기, link를 생각하면 이해하기 쉽다) 이를 통해 파티션이 더 잘게 쪼개지게 되며, 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다. 그러나 가상 노드의 개수가 늘어나면 저장 공간은 더 늘어나게 된다. 트레이드 오프가 필요한 순간이다.