Software Engineer

취미로 블로그하는 개발자

System design

시간 배분

1단계 - 문제 이해 및 설계 범위 확정 : 3-10분 2단계 - 개략적 설계안 제시 및 동의 구하기 : 10-15분 3단계 - 상세 설계 : 10분에서 25분 4단계 - 마무리 : 3-5분

5장 안정 해시 설계

해시 키 재배치 문제

캐시 서버 N개가 있다고 하자. 보편적으로 우리는 전체 데이터를 서버 N개로 나눈 나머지 값으로 파티셔닝을 합니다.

serverIndex = hash(key) % N

그러나 이 경우, 서버를 추가하거나 삭제시 데이터 전체를 재분배해야하는 문제가 있습니다.

# 3 server
server 1 : 1,4,7
server 2 : 2,5,8
server 3 : 0,3,6,9

이 문제를 해결하기 위해 안정해시라는 기술이 나오게 되었습니다.

안정 해시

해시 테이블 크기가 조정될 떄 평균적으로 k/n개의 키만 재배치하는 해시 기술입니다. 전체 데이터 키(k)　중에 서버 수(n) 로 나눈 값만큼만 재배치됩니다.

해시 공간과 해시 링

해시 서버

해시 키

서버 조회 / 추가 / 제거

기본 구현법의 두 가지 문제

1. 서버 추가 삭제 시 파티션의 크기를 균등하게 유지할 수 없습니다.
2. 그에 따라 키의 균등 분포를 달성하기가 어렵습니다. #### 가상 노드 문제 해결을 위해 가상 노드를 도입합니다. #### 재배치할 키 결정 서버 추가시의 키의 재배치 서버 제거시의 키의 재배치 #### 안정 해시 이점
1. 서버가 추가/삭제시 재배치의 키의 수가 최소화됩니다.
2. 데이터가 균등하게 분포되므로, 수평적 확장에 용이합니다.

더 나아가

해시키 이상의 데이터를 저장하려면? Separate Chaining 을 이용해서 저장하면 됩니다.

분산환경이라면 이 안정해시 마스터 데이터의 같은 키가 만들어질 수가 있는데, 락을 이용할 시 병목구간이 될 여지가 있습니다. 이를 위해 미리 키를 생성해 놓는 키생성기로 쓰일 키를 미리 확보해놓을 수 있습니다.

이걸 현실에서 어떻게 구현할 것인가? 해시링 마스터 데이터 가상 노드 정보를 가지고 있는 데이터가 필요하다. [(1노드) 0,1,2,3….99,(2번노드) 100 ] 캐시 서버라는 가정하여, 메모리기반의 중앙 집중형 레디스를 이용.

파티션이 계속 늘어나는데, 어떻게 관리할 것인가? 결국에는 가상 노드를 재배치해야하는 순간이 온다. 언제?

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

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

  • ID는 어떤 특성을 갖나요?
  • 새로운 레코드에 붙일 ID는 항상 1만큼 큰 값이여야 하나요?
  • ID는 숫자로만 구성되나요?
  • 시스템의 규모는 어느 정도입니까?

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

  • 다중 마스터 복제 (multi-master replication)
  • UUID (Universally Unique Identifier)
  • 티켓 서버 (ticket server)
  • 트위터 스노플레이크 (twitter snowflake) 접근법

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

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

UUID

  • 128비트짜리의 수
  • 서버 간 조율 없이 독립적으로 생성 가능하다.
  • 장점
    • 단순, 동기화 이슈 없음
    • 규모 확장이 쉽다.
  • 단점
    • ID가 128비트로 길다. 요구사항은 64비트
    • ID를 시간순으로 정렬할 수 없다.
    • ID에 숫자가 아닌 값이 포함될 수 있다. UUID에 SHA-2를 돌려 16진수를 구함.

티켓 서버 (ticket server)

  • auto_increment 기능을 갖춘 데이터베이스 서버, 티켓 서버를 중앙 집중형으로 하나만 사용하는 것.
  • 장점
    • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
    • 구현 쉬움
  • 단점
    • SPOF가 된다.
    • 티켓 서버를 여러 대 준비해야 한다. 데이터 동기화 문제가 발생

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

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

  • 사인(sign) 비트 : 1비트를 할당.
  • 타임스탬프(timestamp) : 41비트를 할당한다. epoch(기원시각) 이후로 몇 밀리초 경과했는지 나타냄
  • 데이터 센터 ID : 5비트
  • 서버 ID : 5비트
  • 일련번호 : 12비트, 1밀리초가 경과할 때마다 0으로 초기화 된다.

4단계 마무리

multi master replication, UUID, ticket server, twitter snowflake

  • twitter snowflake : 모든 요구사항을 만족하면서도 분산 환경에서 규모 확장이 가능했기 때문이다.

  • 시계 동기화 (clock synchronization) : NTP (Network Time Protocol)
  • 각 절(section)의 길이 최적화 : 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프의 절의 길이를 늘리는 방법.

8장 URL 단축기 설계

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

  • URL 단축기가 어떻게 동작하는지 예제 문의
  • 트래픽의 규모는?
  • 단축 URL의 길이는 어느 정도인지?
  • 단축 URL에 포함될 문자에 제한은?
  • 단축 URL을 시스템에서 지우거나 갱신가능한지?
  • 다른 유저로부터 중복된 긴 URL이 들어올 경우는?

개략적 추정

  • 쓰기 연산 : 매일 1억개 생성
  • 초당 쓰기 연산 : 1억/24/3600 = 1160
  • 읽기 연산 : 읽기-쓰기 비율을 10:1이라 가정하면, 11,600회 발생
  • 레코드의 수 : 10년간 운영한다면 1억x365x10=3650억　레코드
  • 축약 전의 URL 평균 길이 : 100 bytes
  • 10년간 필요한 저장용량 : 3650억 x 100바이트 = 36.5TB

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

API 엔드포인트

  1. URL 단축용 엔드포인트
  2. URL 리다이렉션용 엔드포인트

    URL 리다렉션

    • 301 Permanently Moved
    • 302 Found

      URL 단축

    • 요구사항 :
      • 입력이 다르면 해시 값도 달라야 한다.
    • 해시 값은 복원이 가능해야 한다.

3단계 상세 설계

데이터 모델

해시 함수

해시 값 길이
  • 해시 후 충돌 해소
  • base-62 변환
    두 접근법 비교

URL 단축키 상세 설계

URL 리디렉션 상세 설계

4단계 마무리

  • 처리율 제한 장치
  • 웹 서버의 규모 확장
  • 데이터베이스의 규모 확장
  • 데이터 분석 솔루션
  • 가용성, 데이터 일관성, 안정성

9장 웹 크롤러 설계

  • 검색 엔진 인덱싱
    • 크롤러의 가장 보편적인 용례
    • 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만듦
  • 웹 아카이빙
    • 장기보관하기 위해 웹에서 정보를 모으는 절차 (예. 국립 도서관)
  • 웹 마이닝
    • 데이터 마이닝으로, 인터넷에서 유용한 지식을 도출해냄
  • 웹 모니터링
    • 인터넷에서 저작권이나 상표권이 침해되는 사례를 모니터링 할 수 있음

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

웹 크롤러의 기본 알고리즘

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

질문을 통해 요구사항을 알아내고 설계 범위를 좁히자

  • 이 크롤러의 주된 용도는 무엇인가요? 검색 엔진 인덱스 생성용 / 데이터 마이닝 / 그외 다른 용도
  • 매달 얼마나 많은 웹 페이지를 수집해야 하나요?
  • 새로 만들어진 웹 페이지나 수정된 웹 페이지도 고려해야 하나요?
  • 수집한 웹 페이지는 저장해야 합니까?
  • 중복된 콘텐츠는 어떻게 해야 하나요?

웹 크롤러가 만족시켜야 할 속성들

  • 규모 확장성
    • 오늘날 수십억 개의 페이지가 존재하니 병행성(parallelism)을 활용
  • 안정성(robustness)
    • 비정상적 입력이나 환경에 잘 대응 (예. 잘못 작성된 HTML, 반응없는 서버, 악성 코드 링크)
  • 예절(politeness)
    • 짧은 시간 동안 너무 많은 요청을 보내서는 안 된다.
  • 확장성(extensibility)
    • 새로운 형태의 콘텐츠를 지원이 용이.

개략적 규모 추정

  • 매달 10억개 웹 페이지 : QPS 10억/1달=400page/sec
  • 최대 QPS = 2*QPS
  • 웹 페이지의 크기 평균을 500k로 가정
  • 10억 페이지 * 500k = 500TB/month & 5년 = 30PB

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

시작 URL 집합

  • 크롤러가 가능한 한 많은 일크를 탐색할 수 있도록 하는 URL을 고르는 것이 바람직
  • 일반적으로는 전체 URL 공간을 작은 부분집합으로 나누는 전략
  • 다른 방법은 주제별로 다른 시작 URL을 사용하는 것

미수집 URL 저장소

  • 다운로드할 URL과 다운로드된 URL
  • 다운로드할 URL을 저장 관리하는 컴포넌트를 ‘미수집 URL 저장소’라 하고 큐라 생각하면 됨

HTML 다운로더

  • 인터넷에서 웹 페이지를 다운로드하는 컴포넌트

도메인 이름 변환기

  • URL을 IP 주소로 변환

콘텐츠 파서

  • 웹 페이지를 다운로드 후 파싱과 검증 절차를 거친다
  • 이상한 웹 페이지는 문제를 일으킬 수 있고, 저장 공간을 낭비하기 때문이다.

중복 콘텐츠인가?

  • 29% 가량의 웹 페이지 콘텐츠는 중복이라는 연구 결과가 있다
  • 비교 대상 문서의 수가 10억에 달해, 두 HTML 문서를 문자열로 비교하기 보단, 웹 피이지의 해시 값을 비교

콘텐츠 저장소

  • HTML 문서를 보관하는 시스템
  • 저장할 데이터의 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간 등을 고려
  • 해당 예제는 디스크와 메모리를 동시에 사용하는 저장소를 선택
    • 데이터 양이 막대해, 대부분의 콘텐츠는 디스크에 저장
    • 인기 있는 콘텐츠는 메모리에 두어 접근 지연시간을 줄임

URL 추출기

  • HTML 페이지를 파싱하여 링크들을 골라내는 역할
  • 상대 경로는 전부 절대 경로로 변환한다.

URL 필터

  • 특정 콘텐츠 타입이나 파일 확장자를 갖는 URL
  • 접속 시 오류가 발생하는 URL
  • 접근 제외 목록에 포함된 URL 등등

이미 방문한 URL?

  • 서버 부하를 줄이고 시스템이 무한 루프에 빠지는 일을 방지할 수 있음
  • 블룸 필터나 해시 테이블 자료 구조를 이용

URL 저장소

3단계 상세 설계

  • DFS vs BFS
  • 미수집 URL 저장소
  • HTML 다운로더
  • 안정성 확보 전략
  • 확장성 확보 전략
  • 문제 있는 콘텐츠 감지 및 회피 전략

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

BFS

  • 웹은 유향 그래프(directed graph)와 같다. 페이지는 노드이고, 하이퍼링크(URL)은 데지(edge)라고 보면 된다.
  • 크롤링 프로세스는 이 유향 그래프를 에지를 따라 탐색하는 과정이다.
  • DFS, BFS는 그래프 탐색에 널리 사용되는 알고리즘
  • DFS　깊이 우선 탐색법은 그래프 크기가 클 경우 어느 정도로 깊숙이 가게 될지 가늠하기 어려움
  • 웹 크롤러는 보통 BFS(breath-first search)을 사용한다. BFS는 FIFO(First-In-First-Out) 큐를 사용하는 알고리즘이빈다.
  • 이 큐의 한쪽으로는 탐색할 URL을 집어넣고, 다른 한쪽으로는 꺼내기만 한다.

문제점

  • 한 페이지에서 나오는 링크의 상당수는 같은 서버로 되돌아간다. 즉 예의 없는 크롤러가 된다.
  • URL 간에 우선순위를 두지 않는다.
    • 페이지 순위, 사용자 트래픽의 양, 업데이트 빈도등 척도를 활용해 우선순위 구별

미수집 URL 저장소

이 저장소를 잘 구현하면 예의를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있다.

예의
  • 원칙 : 동일 웹 사이트에 대해서는 한 번에 한 페이지만 요청
    • 같은 웹 사이트의 페이지를 다운받는 태스크는 시간차를 두고 실행하도록 하면 될 것이다.
    • 이를 위해, 웹사이트의 호스트명과 다운로드를 수행하는 작업 스레드 사이의 관계를 유지하면 된다.
    • 즉 각 다운로드 스레드는 별도 FIFO 큐를 가지고 있어서, 해당 큐에서 꺼낸 URL만 다운로드한다.
      우선순위
  • 페이지 랭크, 트레픽 양, 갱신 빈도 등 다양한 척도를 사용
  • 순위결정장치 계산
신선도

이미 다운로드한 페이지라도 주기적으로 재수집할 필요가 있다. 이 작업을 최적화 하기 위한 전략

  • 웹 페이지의 변경 이력 활용
  • 우선순위를 활용하여, 중요한 페이지는 좀 더 자주 재수집
미수집 URL 저장소를 위한 지속성 저장장치

HTML 다운로더

Robots.txt

이 파일에는 크롤러가 수집해도 되는 페이지 목록이 들어 있다.

  • 웹 사이트를 긁어 가기 전에 크롤러는 해당 파일에 나열된 규칙을 확인
  • 이 파일을 계속 다운로드하는 것을 피하기 위해, 이 파일은 주기적으로 다시 다운받아 캐시에 보관할 것이다.

성능 최적화

분산 크롤링
도메인 이름 변환 결과 캐시
  • 병목 중 하나. 동기적 특성으로 결과를 받기 전까지는 다음 작업을 진행할 수 없음
  • 또한, 스레드 가운데 어느하나라도 이 작업을 하고 있으면 다른 스레드의 DNS 요청은 전부 블록된다.
  • 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론잡으로 돌려 주기적으로 갱신
지역성
  • 크롤링 작업을 수행하는 서버를 지역별로 분산
짧은 타임아웃
  • 특정 웹 서버는 응답이 느리거나 응답하지 않으므로 wait time을 둔다.
  • 응답 안할시 다운로드 중단하고 다음 페이지로 넘어간다.
안정성
  • 안정 해시 : 다운로더 서버들에 부하를 분산할 때 적용
  • 크롤링 상태 및 수집 데이터 저장 : 장애 발생시, 크롤링 상태 및 수집 데이터를 지속적으로 저장장치에 기록
  • 예외 처리 : 예외 발생해도 시스템 중단되지 않고 이어나가게 구성
확장성
  • 새로운 형태의 콘텐츠를 지원할 수 있도록 설계
문제있는 콘텐츠 감지 및 회피
  • 중복 콘텐츠 : 해시나 체크섬
  • 거미 덫(무한루프) : 수작업으로 제외하거나 필터 목록에 걸어 넣는다.
데이터 노이즈
  • 쓸모 없는 광고, 스팸 URL

4단계 마무리

  • 서버 측 렌더링 : 링크를 즉석에서 만드는 경우, 서버 측 렌더링(동적 렌더링)을 적용
  • 원치 않는 페이지 필터링 :
  • 데이터베이스 다중화 및 샤딩 : 데이터 계층의 가용성, 규모 확장성, 안정성 향상
  • 수평적 규모 확장성 : 무상태 서버로 만들어 손쉽게 달성
  • 가용성, 일관성, 안정성
  • 데이터 분석 솔루션

11장 뉴스 피드 시스템 설계

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

  • 모바일 앱과 웹 모두 지원하는 시스템
  • 사용자는 뉴스 피드 페이지에 새로운 스토리를 올릴 수 있어야 한다
  • 친구들이 올리는 스토리를 볼 수도 있어야 한다
  • 뉴스 피드에는 단순 시간 흐름 역순으로 표시된다
  • 한 명의 사용자는 최대 5,000명의 친구를 가질 수 있다
  • 트래픽 규모는, 매일 천만 명이 방문하는 서비스를 가정
  • 스토리에는 이미지나 비디오 등의 미디어 파일이 포함될 수 있다

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

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

뉴스 피드 API

  • 클라이언트가 서버와 통신하기 위해 사용하는 수단
  • HTTP 프로토콜 기반이고, 상태 정보를 업데이트하거나, 뉴스 피드를 가져오거나, 친구를 추가하는 등의 다양한 작업을 수행하는 데 사용.
피드 발행 API
  • POST /v1/me/feed
  • 인자
    • body : 포스팅 내용에 해당한다.
    • Authoriation : 호출을 인증하기 위해 사용한다.
      피드 읽기 API
  • 뉴스 피드를 가져오는 API
  • GET /v1/me/feed
  • 인자
    • Authoriation 헤더 : 호출을 인증하기 위해 사용한다.

피드 발행

웹 서버

  • 포스팅 저장 서비스
  • 포스팅 전송 서비스

  • 알림 서비스

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

뉴스 피드 생성

  • 사용자
  • 로드 밸런서
  • 웹서버
  • 뉴스 피드 서비스 : 캐시에서 뉴스 피드를 가져오는 서비스
  • 뉴스 피드 캐시 : 뉴스 피드를 렌더링할 때 필요한 피드 ID를 보관

3단계 상세 설계

피드 발행 흐름 상세 설계

포스팅 전송(fanout) 서비스

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

  • 쓰기 시점에 팬아웃 모델 : 새로운 포스팅을 기록하는 시점에 뉴스 피드를 갱신하게 된다.
    • 장점
      • 뉴스 피드가 실시간으로 갱신되며, 친구 목록에 있는 사용자에게 즉시 전송
      • 포스팅이 기록되는 순간에 뉴스 피드가 갱신, 뉴스 피드를 읽는데 드는 시간이 짧아짐
    • 단점
      • 친구가 많은 사용자의 경우, 뉴스 피드를 갱신하는데 많은 시간이 소요 핫키 (hotkey)라고 부르는 문제
      • 서비스를 자주 이용하지 않는 사용자의 피드까지 갱신하므로 자원낭비
  • 읽기 시점에 팬아웃하는 모델 : 요청 기반 모델. 사용자가 로딩하는 시점에 새로운 포스트를 가져옴
    • 장점 :비활성화된 사용자 경우 유리
    • 단점 : 뉴스 피드를 읽는데 많은 시간이 소요

피드 읽기 흐름 상세 설계

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

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

  • 사용자가 입력하는 단어는 자동완성될 검색어의 첫 부분이어야 하나요? 아니면 중간 부분이 될 수도 있습니까?
  • 몇 개의 자동완성 검색어가 표시되어야 합니까?
  • 자동완성 검색어 5개를 고르는 기준은 무엇입니까?
    • 질의 빈도에 따라 정해지는 검색어 인기 순위를 기준으로 삼겠습니다.
  • 맞춤법 검사 기능도 제공해야 합니까?
  • 질의는 영어입니까?
  • 대문자나 특수 문자 처리도 해야 합니까?
  • 얼마나 많은 사용자를 지원해야 합니까?
    • 일간 능동 사용자(DAU)기준으로 천만 명입니다.

요구사항

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

개략적 규모 추정

  • 일간 능동 사용자는 천만 명
  • 평균적으로 한 사용자가 맹리 10건의 검색을 수행한다고 가정
  • 질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정
    • 문자 인코딩으로 ASCII를 사용한다고 가정, 1문자 = 1바이트
    • 질의문은 평균적으로 4개 단어로 이루어진다고 가정
    • 각 단어는 평균 다섯 글자로 구성된다고 가정
  • 검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 벡엔드에 요청을 보냄
    • 따라서 평균적으로 1회 검색당 20건의 요청이 벡엔드로 전달
  • 대략 초당 24,000건의 질의(QPS)가 발생 (천만 * 10질의/일 * 20자 / 24시간 / 3600초)
  • 최대 QPS = QPS * 2 = 대략 48,000
  • 질의 가운데 20% 정도는 신규 검색어라고 가정할 것이다.
    • 따라서 대략 0.4GB 정도다. 맹리 0.4GB의 신규 데이터가 시스템에 추가된다는 뜻이다.

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

시스템은 두 부분으로 나뉜다.

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

데이터 수집 서비스

  • 질의문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정
    • 질의 단어 : 빈도 수

질의 서비스

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

  • column : query : frequency 
    SELECT *
FROM frequency_table
WHERE query Like `prefix%`
ORDER BY frequency DESC
LIMIT 5
;
  • 데이터가 아주 많아지면 데이터베이스가 병목이 될 수 있음. 상세 설계안에서 이 문제를 해결할 방법을 생각해보자.

3단계 - 상세 설계

  • 데이터 수집 서비스와 질의 서비스의 두 부분으로 구성된 개략적 설계안은 최적화된 결과물은 아니지만, 출발점으로서는 괜찮은 안.
  • 컴포넌트를 몇 개 골라 보다 상세히 설계하고 다음 순서로 최적화 방안을 논의하자.
    • 트라이(trie) 자료구조
    • 데이터 수집 서비스
    • 질의 서비스
    • 규모 확장이 가능한 저장소
    • 트라이 연산

트라이 자료구조

저장소로 사용한 관계형 데이터베이스를 트라이를 사용해 해결

  • 트라이는 문자열들을 간략하게 저장할 수 있는 자료구조
  • 트라이라는 이름은 “retrieval”이라는 단어에서 온 것인데, 문자열을 꺼내는 연산에 초점을 맞추어 설계된 자료구조임을 짐작.
    • 트라이는 트리 형태의 자료구조
    • 이 트리의 루트 노드는 빈 문자열을 나타냄
    • 각 노드는 글자(character) 하나를 저장하며, 26개(가능한 다음 글자)의 자식 노드를 가질 수 있음
    • 각 트리 노드는 하나의 단어, 또는 접두어 문자열을 나타낸다.

트라이로 검색어 자동완성 구현

  • p : 접두어(prefix)의 길이
  • n : 트라이 안에 있는 노드 개수
  • c : 주어진 노드의 자식 노드 개수

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

  • 해당 접두어를 표현하는 노드를 찾는다. 시작 복잡도는 O(p)
  • 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다. 시간 복잡도는 O(c)
  • 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾는다. 시간 복잡도는 O(clogc)
예제

k=2이고, 사용자가 검색창에 ‘be’을 입력했다고 하자.

  1. 접두어 노드 ‘be’을 찾는다.
  2. 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다.
    1. 예) ‘beer’:10, ‘best’:35, ‘bet’:29
  3. 유효 노드를 정렬하여 2개만 골라낸다.

이 알고리즘의 시간 복잡도는 위의 각 단계에 소요된 시간의 합이다. O(p + c + clogc) 이 알고리즘은 직관적이지만 최악의 경우에는 k개 결과를 얻으려고 전체 트라이를 다 검색해야 하는 일이 생길 수 있다. 이를 해결할 방법으로는

  1. 접두어의 최대 길이를 제한
  2. 각 노드에 인기 검색어를 캐시
접두어 최대 길이 제한

사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없다. p값은 작은 정수값(예 50 같은)이라고 가정해도 안전하다. 이 경우, ‘접두어 노드를 찾는’ 단계의 시간복잡도는 O(p) -> O(상수) = O(1)

노드에 인기 검색어 캐시
  • 각 노드에 k개의 인기 검색어를 저장해 두면 전체 트라이를 검색하는 일을 방지할 수 있다.
  • 5-10개 정도의 자동완성 제안을 표시하면 충분하므로, k는 작은 값이다.
  • 각 노드에 인기 질의어를 캐시하면 ‘top 5’ 검색어를 질의하는 시간 복잡도를 엄청나게 낮출 수 있다.
    • 하지만 각 노드에 질의어를 저장할 공간이 많이 필요하게 된다는 단점도 있다.
    • 그러나 빠른 응답속도가 아주 중요할 때는 이 정도 저장공간을 희생할 만한 가치는 있다.

앞의 두 가지 최적화 기법을 적용하면 시간 복잡도 변화는 아래와 같다.

  1. 접두어 노드를 찾는 시간 복잡도는 O(1)로 바뀐다.
  2. 최고 인기 검색어 5개를 찾는 질의의 시간 복잡도도 O(1)로 바뀐다. 검색 결과가 이미 캐시되어 있음

각 단계의 시간 복잡도가 O(1)로 바뀐 덕분에, 최고 인기 검색어 k개를 찾는 전체 ㅇ라고리즘의 복잡도도 O(1)로 바뀌게 된다.

데이터 수집 서비스

사용자가 검색창에 뭔가 타이핑을 할 때마다 실시간으로 데이터를 수정할 경우 문제

  • 매일 수천만 건의 질의가 입력될 텐데, 그때마다 트라이를 갱신하면 질의 서비스는 심각하게 느려짐
  • 트라이가 만들어지고 나면 인기 검색어는 자주 바뀌지 않으므로, 자주 갱신할 필요가 없다.
데이터 분석 서비스 로그

데이터 분석 서비스 로그에는 검색창에 입력된 질의에 관한 원본 데이터가 보관

로그 취합 서버

데이터 분석 서비스로부터 나오는 로그를 잘 취합하여 우리 시스템이 쉽게 소비할 수 있도록 해야 한다. 예를 들어 트위터와 같은 실시간 애플리케이션의 경우, 결과를 빨리 보여주는 것이 중요하므로 데이터 취합 주기를 보다 짧게 가져간다. 그러나 대부분의 경우 일주일에 한 번 정도로 로그를 취합해도 충분.

  • 데이터 취합의 실ㄹ시간성이 얼마나 중요한지 확인하자
    취합된 데이터
  • query / time / frequency
    작업 서버(worker)

    트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 담당

    트라이 캐시

    트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높임. 매주 트라이 데이터베이스의 스냅샷을 떠서 갱신

    트라이 데이터베이스

    지속성 저장소.

    1. 문서 저장소 : 새 트라이를 매주 만들 것이므로, 주기적으로 트라이를 직렬화하여 저장할 수 있음. 예) 몽고디비
    2. 키-값 저장소 :
    • 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환.
    • 각 트라이 노드에 보관도니 모든 데이터를 해시 테이블 값으로 변환

질의 서비스

  1. 검색 질의가 로드밸런서로 전송된다.
  2. 로드밸런서는 해당 질의를 API 서버로 보낸다.
  3. API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성한다.
  4. 데이터가 트라이 캐시에 없는 경우에는 데이터를 데이터베이스에서 가져와 캐시에 채운다.
    1. 캐시미스는 캐시 버서의 메모리가 부족하거나 캐시 서버에 장애가 있어도 발생할 수 있다.

빠른 응답의 질의 서비스를 위한 최적화 방안

  • AJAX 요청 : 웹 어플리케이션의 경우 브라우저는 보통 AJAX 요청을 보내어 자동완성된 검색어 목록을 가져옴.
    • 장점 :요청을 보내고 받기 위해 페이지를 새로고침할 필요가 없음
  • 브라우저 캐싱 : 제안된 검색어들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 캐시에서 바로 가져갈 수 있다.
    • 구글이 사용함. 한 시간동안 캐시해 둠. cache-control 헤더 값에 등장하는 private는 해당 응답이 요청을 보낸 사용자의 캐시에만 보관될 수 있으며, 공용 캐시에 저장되어서는 안된다는 뜻.
  • 데이터 샘플링 : N개 요청 가운데 1개만 로깅하도록 함. (대규모 시스템에서 유리)

트라이 연산

트라이 생성

트라이 생성은 작업 서버가 담당하며, 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용

트라이 갱신
  1. 매주 한 번 갱신하는 방법 : 새로운 트라이를 만든 다음에 기존 트라이를 대체
  2. 트라이의 각 노드를 개별적으로 갱신하는 방법
    • 트라이가 작을 때 고려해볼만한 방안
    • 트라이 노드를 갱신할 때는 그 모든 상위 노드도 갱신해야 하는데, 상위 노드에도 인기 검색어 질의 결과가 보관되기 때문
      검색어 삭제

      트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 함

저장소 규모 확장

영트라이의 크기가 한 서버에 넣기엔 너무 큰 경우의 규모 확장성

  • 영어만 지원하므로, 간단하게 첫 글자를 기준으로 샤딩하는 방법.
    • 이 경우, 데이터를 각 서버에 균등하게 배분하기가 불가능
  • 그러므로, 과거 질의 데이터의 패턴을 분석하여 샤딩하는 방법도 있음
    • 예로, ‘s’로 시작하는 검색어의 양이 5개의 다른 알파벳의 검색어의 양과 같으면 샤딩을 유연하게 가져감.

4단계 마무리

  • 다국어 지원이 가능하도록 시스템을 확장하려면?
    • 트라이에 유니코드 데이터를 저장해야함.
    • 유니코드는 세상에 존재하는 모든 문자 체계를 지원하는 표준 인코딩 시스템
  • 국가별로 인기 검색어 순위가 다르다면?
    • 국가별로 다른 트라이를 사용하도록 하자.

12장 채팅 시스템 설계

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

현재 시장에 나와 있는 앱들을 보면,

  • 1:1 채팅에 집중하는 앱 : 페이스북 메신저 ,위챗, 왓츠앱
  • 슬랙같은 그룹 채팅에 중점을 둔 업무용 앱
  • 게임 채팅에 쓰이는 디스코드 같이 대규모 그룹의 소통과 응답지연이 낮은 음성 채팅에 집중하는 앱

면접관이 원하는 앱이 정확히 무엇인지 알아내기 위한 질문을 하자.

  • 어떤 앱을 설계해야 하나요? 1:1 채팅 앱입니까 아니면 그룹 채팅 앱입니까?
  • 모바일 앱인가요 아니면 웹 앱인가요?
  • 처리해야하는 트래픽 규모는 어느 정도인가요?
    • 일별 능동 사용자 수 기준으로 5천만 명을 처리할 수 있어야 합니다.

15장 구글 드라이브 설계

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

  • 가장 중요하게 지원해야 할 기능들은 무엇인가요?
    • 파일 업로드/다운로드, 파일 동기화, 그리고 알림입니다.
  • 모바일 앱이나 웹 앱 가운데 하나만 지원하면 되나요, 아니면 둘 다 지원해야 합니까?
    • 둘 다 지원해야 합니다.
  • 파일을 암호화해야 할까요?
    • 네
  • 파일 크기에 제한이 있습니까?
    • 10GB 제한이 있습니다.
  • 사용자는 얼마나 됩니까?
    • 일간 능동 사용자 기준으로 천만 명입니다.

이번 장에서 다음 기능의 설게에 집중

  • 파일 추가, 가장 쉬운 방뻡은 파일을 구글 드라이브 안으로 떨구는 것
  • 파일 다운로드
  • 여러 단말에 파일 동기화. 한 단말에서 파일을 추가하면 다른 단말에도 자동으로 동기화되어야 한다.
  • 파일 갱신 이력 조회
  • 파일 공유
  • 파일이 편집되거나 삭제되거나 새롭게 공유되었을 때 알림 표시

기능적 요구사항 이외에, 다음의 비-기능적 요구사항을 이해하는 것도 중요하다.

  • 안정성 : 저장소 시스템에서 안정성은 아주 중요하다. 데이터 손실은 발생하면 안된다.
  • 빠른 동기화 속도 : 파일 동기화에 시간이 너무 많이 걸리면 사용자는 인내심을 잃고 해당 제품을 더 이상 사용하지 않게 될 것이다.
  • 네트워크 대역폭 : 이 제품이 네트워크 대역폭을 불필요하게 많이 소모한다면 사용자는 좋아하지 않을 것이다. 모바일 데이터 플랜을 사용하는 경우라면 더욱 그렇다.
  • 규모 확장성 : 아주 많은 양의 트레픽도 처리 가능해야 한다.
  • 높은 가용성 : 일부 서버에 장애가 발생하거나, 느려지거나, 네트워크 일부가 끊겨도 시스템은 계속 사용 가능해야 한다.

개략적 추정치

  • 가입 사용자는 오천만, 천만 명의 DAU 사용자로 가정
  • 모든 사용자에게 10GB의 무료 저장공간 할당
  • 매일 각 사용자가 평균 2개의 파일을 업로드한다고 가정. 각 파일의 평균 크기는 500KB
  • 읽기 : 쓰기 비율은 1:1
  • 필요한 저장공간 총량 = 5천만 사용자 * 10GB = 500페타바이트
  • 업로드 API QPS = 1천만 사용자 * 2회 업로드 / 24시간 / 3600초 = 약 240
  • 최대 QPS = 2배

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

이번에는 다른 접근 법을 취해보겠다. 모든 것을 담은 한 대 서버에서 출발해 점진적으로 천만 사용자 지원 가능한 시스템으로 발전시켜 나가는 것이다.

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

아파치 웹 서버, MySQL 데이터 베이스, 업로드되는 파일을 저장할 drive/라는 디렉터리를 준비.

API

기본적으로 세 가지 API가 필요하다. 파일 업로드, 파일 다운로드, 파일 갱신 히스토리

1. 파일 업로드 API

  • 단순 업로드 : 파일 크기가 작을 때 사용한다.
  • 이어 올리기 : 파일 사이즈가 크고 네트워크 문제로 업로드가 중단될 가능성이 높다고 생각되면 사용한다.
https://api.example.com/files/upload?uploadType=resumable

인자

  • uploadType=resumable
  • data : 업로드할 로컬 파일

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

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

2. 파일 다운로드 API

https://api.example.com/files/download

인자

  • path : 다운로드할 파일의 경로
  • 예 : {“path” : “/recipes/soup/best_soup.txt”}

3. 파일 갱신 히스토리 API

https://api.example.com/files/list_revisions

인자

  • path : 갱신 히스토리를 가져올 파일의 경로
  • limit : 히스토리 길이의 최대치

지금까지의 모든 API는 사용자 인증을 필요로 하고, HTTPS 프로토콜을 사용해야 한다. SSL(Secure Socket Layer)를 지원하는 프로토콜을 이용하는 이유는 클라이언트와 벡엔드 서버가 주고받는 데이터를 보호하기 위한 것이다.

한 대 서버 제약 극복

  • user_id를 기준으로 샤딩한 예제
  • 파일을 S3에 저장하면서 다중화 지원. (데이터 손실 예방)
  • 로드밸런서 및 웹 서버, 메타데이터 데이터베이스, 파일 저장소 구현

동기화 충돌

먼저 처리되는 변경은 성공한 것으로 보고, 나중에 처리되는 변경은 충돌이 발생한 것으로 표시하는 전략을 사용.

  • 오류 발생한 시점에 이 시스템에는 같은 파일의 두 가지 버전이 존재하게 된다.

3단계 - 상세 설계

블록 저장소 서버

정기적으로 갱신되는 큰 파일들은 업데이트가 일어날 때마다 전체 파일을 서버로 보내면 네티워크 대역폭을 많이 잡아먹게 된다. 이를 최적화하는 방법으로는

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

이 시스템에서 블록 저장소 서버는 파일 업로드에 관계된 힘든 일을 처리하는 컴포넌트다. 클라이언트가 보낸 파일을 블록 단위로 나눠야 하고, 각 블록에 압축 알고리즘을 적용해야 하고, 암호화까지 해야 한다. 아울러 전체 파일을 저장소 시스템으로 보내는 대신 수정된 블록만 전송해야 한다.

  • 주어진 파일을 작은 블록들로 분할한다.
  • 각 블록을 압축한다.
  • 클라우드 저장소로 보내기 전에 암호화한다.
  • 클라우드 저장소로 보낸다.

블록 저장소 서버에 델타 동기화 전략과 압축 알고리즘을 도입하였으므로, 네트워크 대역폭 사용량을 절감할 수 있다.

높은 일관성 요구사항

같은 파일이 단말이나 사용자에 따라 다르게 보이는 것은 허용할 수 없다. 메타데이터 캐시와 데이터베이스 계층에도 같은 원칙이 적용되어야 한다.

메모리 캐시는 보통 최종 일관성 모델을 지원한다.

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

관계형 데이터베이스는 ACID(Atomicity, Consistency, Isolation, Durability)를 보장하므로 강한 일관성을 보장하기 쉽다.

업로드 절차

2개의 요청

  1. 파일 메타데이터를 추가하기 위한 요청
  2. 파일을 클라우드 저장소로 업로드하기 위한 요청
  • 파일 메타데이터 추가
    1. 클라이언트1이 새 파일의 메타데이터를 추가하기 위한 요청 전송
    2. 새 파일의 메타데이터를 데이터베이스에 저장하고 업로드 상태를 대기 중으로 변경
    3. 새 파일이 추가되었음을 알림 서비스에 통지
    4. 알림 서비스는 관련된 클라이언트2에게 파일이 업로드되고 있음을 알림
  • 파일을 클라우드 저장소에 업로드
    1. 클라이언트 1이 파일을 블록 저장소 서버에 업로드
    2. 블록 저장소 서버는 파일을 블록 단위로 쪼갠 다음 압축하고 암호화 한 다음에 클라우드 저장소에 전송
    3. 업로드가 끝나면 클라우드 스토리지는 완료 콜백을 호출, 이 콜백 호출은 API 서버로 전송됨
    4. 메타 데이터 DB에 기록된 해당 파일의 상태를 완료로 변경
    5. 알림 서비스에 파일 업로드가 끝났음을 통지
    6. 알림 서비스는 관련된 클라이언트2에게 파일 업로드가 끝났음을 알림

다운로드 절차

You may also enjoy