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

서평

• 
• 이 책은 도메인 주도 설계 첫걸음과 같이 추천을 받아서 읽게 된 책입니다. 이 책은 12가지의 시스템 설계에 대해서 문제 이해 및 설계 범위 확정, 개략적인 설계안 제시 및 동의 구하기, 상세 설계, 마무리라는 4단계 접근법을 통해서 공략하고 있습니다. 책을 읽으면서 시스템에 대해서 많은 생각이 들었고 아키텍처 그림과 실제 시스템 디자인 면접을 보는 듯한 느낌이 좋았습니다.
• 이 책의 목적은 시스템 설계 면접 문제를 푸는 데 안정적으로 적용할 수 있는 전략을 제시하는 것으로 규모 확장성을 갖춘 시스템을 만들기 위 해 필수적인 지식도 제공하고 있습니다. 이 책에서는 시스템 설계 면접 문제들을 공략하는 단계적 접근법도 다루고 있어서 해당 접근법을 실제로 따라 하면서 배울 수 있도록 많은 예제를 상세한 설명과 함께 제공하고 있어서 좋았습니다.
• 12가지의 시스템 설계는 처리율 제한 장치의 설계, 안정 해시 설계, 키-값 저장소 설계, 분산 시스템을 위한 유일 ID 생성기 설계, URL 단축기 설계, 웹 크롤러 설계, 알림 시스템 설계, 뉴스 피드 시스템 설계, 채팅 시스템 설계, 검색어 자동완성 시스템, 유튜브 설계, 구글 드라이브 설계입니다.
• 다음은 몇 가지 시스템 설계의 아키텍처를 도식화한 것입니다.
• 데이터베이스 샤딩을 적용한 아키텍처
  • 
  • 데이터베이스에 대한 부하를 줄이기 위해 굳이 관계형 데이터 베이스가 요구되지 않는 기능들은 NoSQL로 이전
• 피드 발행
  • 
• 뉴스 피드 가져오기
  • 
• 분산 키-값 저장소의 쓰기,읽기 경로
  • 
  • 쓰기 경로
    • 쓰기 요청이 커밋 로그(commit log) 파일에 기록됨
    • 데이터가 메모리 캐시에 기록됨
    • 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 딧드크에 있는 SSTable에 기록됨. SSTable은 Sorted-String Table의 약어로 <키,값>의 순서쌍을 정렬히 리스트 형태로 관리하는 테이블
  • 읽기 경로
    • 데이터가 메모리에 없을 때 읽기연산이 처리되는 경로
      • 데이터가 메모리에 있는지 검사함. 없으면 2로 감
      • 데이터가 메모리에 없으면 블룸 필터를 검사함
      • 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아냄
      • SSTable에서 데이터를 가져옴
      • 해당 데이터를 클라이언트에게 반환함

사용자 수에 따른 규모 확장

• 규모 확장성과 관계된 설계 문제를 푸는 데 쓰일 유용한 지식들을 배울 수 있습니다.
• 단일 서버
  • 실제 요청
    • 웹 애플리케이션 : 비즈니스 로직, 데이터 저장 등을 처리하기 위해서는 서버 구현용 언어(자바, 파이썬 등)를 사용하고, 프레젠테이션용으로는 클라이언트 구현용 언어(HTML, 자바스크립트 등)를사용함
    • 모바일 앱 : 모바일 앱과 웹 서버 간 통신을 위해서는 HTTP 프로토콜을 이용함. HTTP 프로토콜을 통해서 반환될 응답 데이터의 포맷으로는 보통 JSON(JavaScript Object Notation)이 그 간결함 덕에 널리 쓰임
• 데이터 베이스
  • 사용자가 늘면 서버 하나로는 충분하지 않아서 여러 서버를 두어야 함. 하나는 웹/모바일 트래픽 처리 용도고, 다른 하나는 데이터베이스용. 웹/모바일 트래픽 처리 서버(웹 계층)와 데이터베이스 서버(데이터 계층)를 분리하면 그 각각을 독립적으로 확장해 나갈 수 있게 됨
  • 어떤 데이터베이스를 사용할 것인가?
    • 관계형 데이터베이스는 관계형 데이터베이스 관리 시스템(Relational Data-base Management System,RDBMS). RDBMS 가운데 가장 유명한 것으로는 MySQL, 오라클 데이터베이스, PostgreSQL 등이 있음. 관계형 데이터베이스는 자료를 테이블과 열, 칼럼으로 표현함
    • 비 관계형 데이터베이스는 NoSQL으로 대표적인 것으로는 CouchDB, Neo4j, Cassandra, HBase, Amazon DynamoDB 등이 있음.
    • NOSQL은 다시 네 분류로 나눠짐. 키 값 저장소, 그래프 저장소, 칼럼 저장소, 문서저장소. 비-관계형 데이터베이스는 일반적으로 조인 연산은 지원하지 않음
    • 비-관계형 데이터베이스가 바람직한 선택일 경우
      • 아주 낮은 응답 지연시간(latency)이 요구됨
      • 다루는 데이터가 비정형(unstructured)이라 관계형 데이터가 아님
      • 데이터(JSON, YAML, XML 등)를 직렬화하거나(serialize) 역직렬화(deserial-ize) 할 수 있기만 하면 됨
      • 아주 많은 양의 데이터를 저장할 필요가 있음
• 수직적 규모 확장 vs 수평적 규모 확장
  • 스케일 업, 수직적 규모 확장(vertical scaling) 프로세스는 서버에 고사양 자원(더 좋은 CPU, 더 많은 RAM 등)을 추가하는 행위를 말함
  • 스케일 아웃이라고도 하는 수평적 규모 확장 프로세스는 더 많은 서버를 추가하여 성능을 개선하는 행위를 말함
  • 서버로 유입되는 트래픽의 양이 적을 때는 수직적 확장이 좋은 서택이며 가장 큰 장점은 단순함. 단점은 다음과 같음
    • 수직적 규모 확장에는 한계가 있음. 한 대의 서버에 CPU나 메모리를 무한대로 증설할 방법은 없음
    • 수직적 규모 확장법은 장애에 대한 자동복구(failover) 방안이나 다중화(re-dundancy) 방안을 제시하지 않음. 서버에 장애가 발생하면 웹사이트/앱은 완전히 중단됨
  • 대규모 애플리케이션을 지원하는 데는 수평적 규모 확장법이 보다 적절함
  • 로드 밸런서
    • 로드밸런서는 부하 분산 집합(load balancing set)에 속한 웹 서버들에게 트래픽 부하를 고르게 분산하는 역할을 함
    • 사용자는 로드밸런서의 공개 IP 주소 (public IP address)로 접속함
    • 웹 서버는 클라이언트의 접속을 직접 처리하지 않음. 더 나은 보안을 위해, 서버 간 통신에는 사설 IP 주소(private IP address)가 이용됨. 사설 IP 주소는 같은 네트워크에 속한 서버 사이의 통신에만 쓰일 수 있는 IP주소로, 인터넷을 통해서는 접속할 수 없음. 로드밸런서는 웹 서버와 통신하기 위해 바로 이 사설 주소를 이용함
    • 부하 분산 집합에 또 하나의 웹 서버를 추가하고 나면 장애를 자동복구하지 못하는 문제(no failover)는 해소되며, 웹 계층의 가용성(availability)은 향상됨
      • 서버 1이 다운되면(offline) 모든 트래픽은 서버 2로 전송됨. 웹 사이트 전체가 다운되는 일이 방지됨. 부하를 나누기 위해 새로운 서버를 추가할 수도 있음
      • 웹사이트로 유입되는 트래픽이 가파르게 증가하면 두 대의 서버로 트래픽을 감당할 수 없는 시점이 오는데, 로드밸런서가 있으므로 우아하게 대처할 수 있음. 웹 서버 계층에 더 많은 서버를 추가하기만 하면 됨. 로드밸런스가 자동적으로 트래픽을 분산하기 시작함
  • 데이터베이스 다중화
    • 많은 데이터베이스 관리 시스템이 다중화를 지원함. 보통은 서버 사이에 주(master)-부(slave) 관계를 설정하고 데이터 원본은 주서버에, 사본은 부 서버에 저장하는 방식
    • 쓰기 연산(write operation)은 마스터에서만 지원함. 부 데이터베이스는 주 데이터베이스로부터 그 사본을 전달받으며, 읽기 연산(read operation)만을 지원함.
    • 데이터베이스를 변경하는 명령어들, 가령 insert, delete, update 등은 주 데이터베이스로만 전달되어야 함
    • 대부분의 애플리케이션은 읽기 연산의 비중이 쓰기 연산보다 훨씬 높음
    • 이점
      • 더 나은 성능
        • 주-부 다중화 모델에서 모든 데이터 변경 연산은 주 데이터베이스 서버로만 전달되는 반면 읽기 연산은 부 데이터베이스 서버들로 분산됨.
        • 병렬로 처리될 수 있는 질의(query)의 수가 늘어나므로, 성능이 좋아짐
      • 안정성(reliability)
        • 자연 재해 등의 이유로 데이터베이스 서버 가운데 일부가 파괴되어도 데이터는 보존될 것
        • 데이터를 지역적으로 떨어진 여러 장소에 다중화시켜 놓을 수 있기 때문
      • 가용성(availability)
        • 데이터를 여러 지역에 복제해 둠으로써, 하나의 데이터베이스 서버에 장애가 발생하더라도 다른 서버에 있는 데이터를 가져와 계속 서비스할 수 있게 됨
    • 응답 시간은 캐시를 붙이고 정적 콘텐츠를 콘텐츠 전송 네트워크(Content Delivery Network, CDN)로 옮기면 개선할 수 있음
• 캐시
  • 캐시는 값비싼 연산 결과 또는 자주 참조되는 데이터를 메모리 안에 두고, 뒤이은 요청이 보다 빨리 처리될 수 있도록 하는 저장소
  • 캐시 계층
    • 캐시 계층(cache tier)은 데이터가 잠시 보관되는 곳으로, 데이터베이스보다 훨씬 빠름. 별도의 캐시 계층을 두면 성능이 개선될 뿐 아니라 데이터베이스의 부하를 줄일 수 있고, 캐시 계층의 규모를 독립적으로 확장시키는 것도 가능해짐
    • 캐시 사용시 유의할 점
      • 데이터 갱신은 자주 일어나지 않지만 참조는 빈번하게 일어난다면 고려해볼 만 ㅎ마
      • 캐시는 데이터를 휘발성 메모리에 두므로, 영속적으로 보관할 데이터를 캐시에 두는 것은 바람직하지 않음. 캐시 서버가 재시작되면 캐시 내의 모든 데이터는 사라짐
      • 만료된 데이터는 캐시에서 삭제되어야 함
      • 일관성은 데이터 저장소의 원본과 캐시 내의 사본이 같은지 여부. 저장소의 원본을 갱신하는 연산과 캐시를 갱신하는 연산이 단일 트랜잭션으로 처리되지 않는 경우 이 일관성은 깨질 수 있음
      • 캐시 서버를 한 대만 두는 경우 해당 서버는 단일 장애 지점(Single Point of Failure, SPOF)이 되어버릴 가능성이 있음
      • 캐시 메모리가 너무 작으면 액세스 패턴에 따라서 데이터가 너무 자주 캐시에서 밀려나버려(eviction) 캐시의 성능이 떨어지게 됨. 이를 막을 한 가지 방법은 캐시 메모리를 과할당(overprovision)하는 것
      • 캐시가 꽉 차버리면 추가록 캐시에 데이터를 넣어야 할 경우 기존 데이터를 내보내야 함. 캐시 데이터 방출 정책이라고 함. 그 가운데 가장 널리 쓰이는 것은 LRU(Least Recently Used - 마지막으로 사용된 시점이 가장 오래된 데이터를 내보내는 정책). 다른 정책으로는 LFU(Least Freqeuntly Used - 사용된 빈도가 가장 낮은 데이터를 내보내는 정책)이나 FIFO(First In First Out - 가장 먼저 캐시에 들어온 데이터를 가장 먼저 내보내는 정책)
• 콘텐츠 전송 네트워크(CDN)
  • CDN은 정적 콘텐츠를 전송하는 데 쓰이는, 지리적으로 분산된 서버의 네트워크. 이미지, 비디오, CSS, JavaScript 파일 등을 캐시할 수 있음
  • 요청 경로(request path), 질의 문자열(query string), 쿠키(cookie), 요청 헤더(requeset header) 등의 정보에 기반하여 HTML 페이지를 캐시하는 것
  • 고려해야 할 사항
    • 비용
      • CDN은 보통 제3 사업자(third-party providers)에 의해 운영되며, 여러분은 CDN으로 들어가고 나가는 데이터 전송 양에 따라 요금을 내게 됨
    • 적절한 만료 시한 설정
      • 시의성이 중요한(time-sensitive) 콘텐츠의 경우 만료 시점을 잘 정해야 함
    • CDN 장애에 대한 대처 방안
      • CDN 자체가 죽었을 경우 웹사이트/애플리케이션이 어떻게 동작해야 하는지 고려해야 함
    • 콘텐츠 무효화(invalidation)
• 무상태(stateless) 웹 계층
  • 상태 정보(사용자 세션 데이터와 같은)를 관계형 데이터베이스나 NoSQL 같은 지속성 저장소에 보관하고, 필요할 때 가져오도록 하는 것.
  • 상태 정보 의존적인 아키텍처
    • 상태 정보를 보관하는 서버는 클라이언트 정보, 즉 상태를 유지하여 요청들 사이에 공유되도록 함. 무상태 서버에는 이런 장치가 없음
  • 무상태 아키텍처
    • 세션 데이터를 웹 계층에서 분리하고 지속성 데이터 보관소 저장하도록 만들었음. 이 공유 저장소는 관계형 데이터베이스일 수도 있고, Memcached/Redis 같은 캐시 시스템일 수도 있으며 , NoSQL일 수도 있음 .
    • NoSQL을 사용하였는데, 규모 확장이 간편해서. 자동 규모 확장은 트래픽 양에 따라 웹 서버를 자동으로 추가하거나 삭제하는 기능을 뜻함
• 데이터 센터
  • 장애가 없는 상황에서 사용자는 가장 가까운 데이터 센터로 안내되는데, 통상 이 절차를 지리적 라우팅(geoDNS-routing 또는 geo-routing)
  • 지리적 라우팅에서의 geoDNS는 사용자의 위치에 따라 도메인 이름을 어떤 IP 주소로 변환할지 결정할 수 있도록 해 주는 DNS 서비스
  • 다중 데이터센터 아키텍처를 만들려면 몇 가지 기술적 난제를 해결해야 함
    • 트래픽 우회: 올바른 데이터 센터로 트래픽을 보내는 효과적인 방법을 찾아야 함
    • 데이터 동기화(synchronization) : 데이터 센터마다 별도의 데이터베이스를 사용하고 있는 상황이라면, 장애가 자동으로 복귀되어 트래픽이 다른 데이터베이스로 우회된다 해도, 해당 데이터센터에는 찾는 데이터가 없을 수 있음. 이런 상황을 막는 보편적 전략은 데이터를 여러 데이터 센터에 걸쳐 다중화하는 것
    • 테스트와 배포(deployment) : 자동화된 배포 도구는 모든 데이터 센터에 동일한 서비스가 설치되도록 하는 데 중요한 역할을 함
• 메시지 큐
  • 메시지 큐는 메시지의 무손실(durability, 즉 메시지 큐에 일단 보관된 메시지는 소비자가 꺼낼 때까지 안전히 보관된다는 특성)을 보장하는, 비동기 통신(asynchronous communication)을 지원하는 컴포넌트. 메시지의 버퍼 역할을 하며, 비동기적으로 전송함
  • 생산자 또는 발행자(producer/publisher)라고 불리는 입력 서비스가 메시지를 만들어 메시지 큐에 발행(publish)함. 큐에는 보통 소비자 혹은 구독자(consumer/subscriber)라 불리는 서비스 혹은 서버가 연결되어 있는데, 메시지를 받아 그에 맞는 동작을 수행하는 역할을 함
  • 메시지 큐를 이용하면 서비스 또는 서버 간 결합이 느슨해져서, 규모 확장성이 보장되어야 하는 안정적 애플리케이션을 구성하기도 좋음. 생산자는 소비자 프로세스가 다운되어 있어도 메시지를 발행할 수 있고, 소비자는 생산자 서비스가 가용한 상태가 아니더라도 메시지를 수신할 수 있음
• 로그, 메트릭 그리고 자동화
  • 로그 : 에러 로그를 모니터링하는 것은 중요함. 시스템의 오류와 문제들을 보다 쉽게 찾아낼 수 있도록 하기 때문
  • 메트릭 : 메트릭을 잘 수집하면 사업 현황에 관한 유용한 정보를 얻을 수도 있고, 시스템의 현재 상태를 손쉽게 파악할 수도 있음
    • 호스트 단위 메트릭 : CPU, 메모리, 디스크 I/O에 관한 메트릭
    • 종합(aggregated) 메트릭 : 데이터베이스 계층의 성능, 캐시 계층의 성능
    • 핵심 비즈니스 메트릭 : 일별 능동 사용자(daily active user), 수익(revenue), 재방문(retention)
  • 자동화
    • 시스템이 크고 복잡해지면 생산성을 높이기 위해 자동화 도구를 활용해야 함. 지속적 통합을 도와주는 도구를 활용하면 개발자가 만드는 코드가 어떤 검증 절차를 자동으로 거치도록 할 수 있어서 문제를 쉽게 감지할 수 있음
    • 빌드, 테스트, 배포 등의 절차를 자동화할 수 있어서 개발 생산성을 크게 향상시킬 수 있음
• 데이터베이스 규모 확장
  • 수직적 확장
    • 스케일 업이라고도 부르는 수직적 규모 확장법은 기존 서버에 더 많은, 또는 고성능의 자원(CPU, RAM, 디스크 등)을 증설하는 방법.
    • 몇 가지 심각한 약점
      • 데이터베이스 서버 하드웨어에는 한계가 있으므로 CPU, RAM 등을 무한 증설할 수는 없음
      • SPOF로 인한 위험성이 큼
      • 비용이 많이 듬. 고성능 서버로 갈수록 가격이 올라가게 마련
  • 수평적 확장
    • 데이터베이스의 수평적 확장은 샤딩(sharding)이라고도 부르는데, 더 많은 서버를 추가함으로써 성능을 향상시킬 수 있도록 함
    • 샤딩은 대규모 데이터베이스를 샤드(shard)라고 부르는 작은 단위로 분할하는 기술을 일컫는다. 모든 샤드는 같은 스키마를 쓰지만 샤드에 보관되는 데이터 사이에는 중복이 없음
    • 샤딩 전략을 구현할 때 고려해야 할 가장 중요한 것은 샤딩 키를 어떻게 정하느냐 하는 것. 샤딩 키는 파티션 키라고도 부르는데, 데이터가 어떻게 분산될지 정하는 하나 이상의 칼럼으로 굿어됨
    • 샤딩 키를 정할 때는 데이터를 고르게 분할 할 수 있도록 하는 게 가장 중요함
    • 샤딩을 도입하면 시스템이 복잡해지고 풀어야 할 새로운 문제도 생김
      • 데이터의 재 샤딩(resharding)
        • 데이터가 너무 많아져서 하나의 샤드로는 더 이상 감당하기 어려울 때, 샤드 간 데이터 분포가 균등하지 못하여 어떤 샤드에 할당된 공간 소모가 다른 샤드에 비해 빨리 진행될 때, 샤드 소진(shard exhaustion)이라고도 부르는 이러한 현상이 발생하면 샤드 키를 계산하는 함수를 변경하고 데이터를 재배치하여야 함
        • 유명인사(celebrity) 문제 : 핫스파 킷 문제라고도 부르는데, 특정 샤드에 질의가 집중되어 서버에 과부하가 걸리는 문제
        • 조인과 비정규화(join and de-normalization) : 일단 하나의 데이터베이스를 여러 샤드 서버로 쪼개고 나면, 여러 샤드에 걸친 데이터를 조인하기가 힘들어짐. 데이터베이스를 비정규화하여 하나의 테이블에서 질의가 수행될 수 있도록 하는 것
        • 데이터베이스 샤딩을 적용한 아키텍처
          • 데이터베이스에 대한 부하를 줄이기 위해 굳이 관계형 데이터 베이스가 요구되지 않는 기능들은 NoSQL로 이전하였습니다.
          • 
• 백만 사용자, 그리고 그 이상
  • 시스템 규모 확장을 위해 살펴본 기법들
    • 웹 계층은 무상태 계층으로
    • 모든 계층에 다중화 도입
    • 가능한 한 많은 데이터를 캐시할 것
    • 여러 데이터 센터를 지원할 것
    • 정적 콘텐츠는 CDN을 통해 서비스할 것
    • 데이터 계층은 샤딩을 통해 그 규모를 확장할 것
    • 각 계층은 독립적 서비스로 분할할 것
    • 시스템을 지속적으로 모니터링하고, 자동화 도구들을 활용할 것

개략적인 규모 추정

• 개략적인 규모 추정(back-of-the-envelope esti-mation)은 보편적으로 통용되는 성능 수치상에서 사고 실험(thought experi-ments)을 행하여 추정치를 계산하는 행위로서, 어떤 설계가 요구사항에 부합할 것인지 보기 위한 것
• 모든 프로그래머가 알야아 하는 응답지연 값
  • 메모리는 빠르지만 디스크는 아직도 느리다
  • 디스크 탐색(seek)은 가능한 한 피하라
  • 단순한 압축 알고리즘은 빠르다
  • 데이터를 인터넷으로 전송하기 전에 가능하면 압축하라
  • 데이터 센터는 보통 여러 지역에 분산되어 있고, 센터들 간에 데이터를 주고받는 데는 시간이 걸림
• 가용성에 관계된 수치들
  • 고가용성은(high availability)은 시스템이 오랜 시간 동안 지속적으로 중단 없이 운영될 수 있는 능력을 지칭하는 용어
  • SLA(Service Level Agreement)은 서비스 사업자(service provider)가 보편적으로 사용하는 용어로, 서비스 사업자와 고객 사이에 맺어진 합의를 의미함
  • 서비스 사업자가 제공하는 서비스 가용시간(uptime)이 공식적으로 기술되어 있음
  • 가용시간은 관습적으로 숫자 9를 사용해 표시함. 9가 많으면 많을수록 좋다고 보면 됨

    • 가용률	하루당 장애시간	주당 장애시간	개월당 장애시간	연간 장애시간
      99%	14.40분	1.68시간	7.31시간	3.65일
      99.9%	1.44분	10.08분	43.83분	8.77시간
      99.99%	8.64초	1.01분	4.38분	52.60분
      99.999%	864.00밀리초	6.05초	26.30초	5.26분
      99.9999%	86.40밀리초	604.80밀리초	2.63초	31.56초

• 많이 출제되는 개략적 규모 추정 문제는 QPS, 최대 QPS, 저장소 요구량, 캐시 요구량, 서버 수 등을 추정하는 것

시스템 설계 면접 공략법

• 효과적 면접을 위한 4단계 접근법
  • 문제 이해 및 설계 범위 확정
    • 속도를 늦춰라. 깊이 생각하고 질문하여 요구사항과 가정들을 분명히 하라
    • 엔지니어가 가져야 할 가장 중요한 기술 중 하나는 올바른 질문을 하는 것, 적절한 가정을 하는 것, 그리고 시스템 구축에 필요한 정볼르 모으는 것
    • 요구사항을 정확히 이해하는 데 필요한 질문을 하라
      • 구체적으로 어떤 기능들을 만들어야 하나?
      • 제품 사용자 수는 얼마나 되나?
      • 회사의 규모는 얼마나 빨리 커지리라 예상하나? 석 달, 여섯 달, 일년 뒤의 규모는 얼마가 되리라 예상하는가?
      • 회사가 주로 사용하는 기술 스택은 무엇인가? 설계를 단순화하기 위해 활용할 수 있는 기존 서비스로 어떤 것들이 있는가?
  • 개략적인 설계안 제시 및 동의 구하기
    • 설계안에 대한 최초 청사진을 제시하고 의견을 구하라. 면접관을 마치 팀원인 것처럼 대하라
    • 화이트보드나 종이에 핵심 컴포넌트를 포함하는 다이어그램을 그려라
    • 이 최초 설계안이 시스템 규모에 관계된 제약사항들을 만족하는지를 개략적으로 계산해 보라. 계산 과정은 소리 내어 설명하라
    • 예제
      • 피드 발행 : 사용자가 포스트를 올리면 관련된 데이터가 캐시/데이터베이스에 기록되고, 해당 사용자의 친구 뉴스 피드에 뜨게 됨
      • 피드 생성 : 어떤 사용자의 뉴스 피드는 해당 사용자 친구들의 포스트를 시간 역순으로(최신 포스트부터 오래된 포스트 순으로) 정렬하여 만듬
  • 상세 설계
    • 시스템에서 전반적으로 달성해야 할 목표와 기능 범위 확인
    • 전체 설계의 개략적 청사진 마련
    • 해당 청사진에 대한 면접관의 의견 청취
    • 상세 설계에서 집중해야 할 영역들 확인
    • 피드 발행
      • 
    • 뉴스 피드 가져오기
      • 
  • 마무리
    • 면접관이 시스템 병목구간, 혹은 더 개선 가능한 지점을 찾아내라 주문할 수 있음
    • 여러분이 만든 설계를 한번 다시 요약해주는 것도 도움이 될 수 있음
    • 오류가 발생하면 무슨 일이 생기는지(서버 오류, 네트워크 장애 등) 따져보면 흥미로울 것
    • 운영 이슈도 논의할 가치가 충분함. 메트릭은 어떻게 수집하고 모니터링 할 것인가? 로그는? 시스템은 어떻게 배포해(roll-out) 나갈 것인가?
    • 미래에 닥칠 규모 확장 요구에 어떻게 대처할 것인지도 흥미로운 주제
    • 해야 할 것
      • 질문을 통해 확인하라. 스스로 내린 가정이 옳다 믿고 진행하지 말라
      • 문제의 요구사항을 이해하라
      • 정답이니 최선의 답안 같은 것은 없다는 점을 명심하라. 스타트업을 위한 설계안과 수백만 사용자를 지원해야 하는 중견 기업을 위한 설계안이 같을리 없다. 요구사항을 정확하게 이해했는지 다시 확인하라
      • 면접관이 여러분의 사고 흐름을 이해할 수 있도록 하라. 면접관과 소통하라
      • 가능하다면 여러 해법을 함께 제시하라
      • 개략적 설계에 면접관이 동의하면, 각 컴포넌트의 세부사항을 설명하기 시작하라. 가장 중요한 컴포넌트부터 진행하라
      • 면접관의 아이디어를 이끌어 내라. 좋은 면접관은 여러분과 같은 팀원처럼 협력한다.
      • 포기하지 말라
    • 하지 말아야 할 것
      • 전형적인 면접 문제들에도 대비하지 않은 상태에서 면접장에 가지 말라
      • 요구사항이나 가정들을 분명히 하지 않은 상태에서 설계를 제시하지 말라
      • 처음부터 특정 컴포넌트의 세부사항을 너무 깊이 설명하지 말라. 개략적 설계를 마친 뒤에 세부사항으로 나아가라
      • 진행 중에 막혔다면, 힌트를 정하기를 주저하지 말라
      • 다시 말하지만, 소통을 주저하지 말라. 침묵 속에 설계를 진행하지 말라
      • 설계안을 내놓는 순간 면접이 끝났다고 생각하지 말라. 면접관이 끝났다고 말하기 전까지는 끝난 것이 아니다. 의견을 일찍, 그리고 자주 구하라
    • 시간 배분
      • 문제 이해 및 설계 범위 확정 : 3분에서 10분
      • 개략적 설계안 제시 및 동의 구하기 : 10분에서 15분
      • 상세 설계 : 10분에서 25분
      • 마무리 : 3분에서 5분

처리율 제한 장치의 설계

• 네트워크 시스템에서 처리율 제한 장치(rate limiter)는 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치. HTTP로 예로 들면 이 장치는 특정 기간 내에 전송되는 클라이언트의 요청 횟수를 제한함. API 요청 횟수가 제한 장치에 정의된 임계치(threshold)를 넘어서면 추가로 도달한 모든 호출은 처리가 중단(block)됨
  • 사용자는 초당 2회 이상 새 글을 올릴 수 없음
  • 같은 IP 주소로는 하루에 10개 이상의 계정을 생성할 수 없음
  • 같은 디바이스로는 주당 5회 이상 리워드(reward)를 요청할 수 없음
• API 처리율 제한 장치를 두면 좋은 점
  • DoS(Denial of Service) 공격에 의한 자원 고갈(resource starvation)을 방지할 수 있음
  • 비용을 절감함. 추가 요청에 대한 처리를 제한하면 서버를 많이 두지 않아도 되고, 우선순위가 높은 API에 더 많은 자원을 할당할 수 있음
  • 서버 과부하를 막음. 봇에서 오는 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러내는데 처리율 제한 장치를 활용할 수 있음
• 문제 이해 및 설계 범위 확정
  • 요구사항
    • 설정된 처리율을 초과하는 요청은 정확하게 제한함
    • 낮은 응답시간 : 이 처리율 제한 장치는 HTTP 응답시간에 나쁜 영향을 주어서는 곤란함
    • 가능한 한 적은 메모리를 써야 함
    • 분산형 처리율 제한: 하나의 처리율 제한 장치를 여러 서버나 프로세스에서 공유할 수 있어야 함
    • 예외 처리 : 요청이 제한되었을 때는 그 사실을 사용자에게 분명하게 보여주어야 함
    • 높은 결함 감내성(fault tolerance) : 제한 장치에 장애가 생기더라도 전체 시스템에 영향을 주어서는 안됨
• 개략적 설계안 제시 및 동의 구하기
  • 클라이언트는 처리율 제한을 안정적으로 걸 수 있는 장소가 못 됨. 클라이언트 요청은 쉽게 위변조가 가능하므로
  • HTTP 상태 코드 429는 사용자가 너무 많은 요청을 보내려고 했음(Too many requests)을 알림
  • 클라우드 마이크로 서비스의 경우 처리율 제한 장치는 보통 API 게이트웨이라 불리는 컴포넌트에 구현됨.
    • API 게이트 웨이 : 처리율 제한, SSL 종단(termination), 사용자 인증(authentication), IP 허용 목록(whitelist) 관리 등을 지원하는 완전 위탁관리형 서비스(fully managed), 즉 클라우드 업체가 유지 보수를 담당하는 서비스
  • 처리율 제한을 설계할 때 몇 가지 지침
    • 프로그래밍 언어, 캐시 서비스 등 현재 사용하고 있는 기술 스택을 점검하라
    • 여러분의 사업 필요에 맞는 처리율 제한 알고리즘을 찾아라
    • 여러분의 설계가 마이크로서비스에 기반하고 있고, 사용자 이증이나 IP 허용목록 관리 등을 처리하기 위해 API 게이트웨이를 이미 설계에 포함시켰다면 처리율 제한 기능 또한 게이트웨이에 포함시켜야 할 수도 있음
    • 처리율 제한 서비스를 직접 만드는 데는 시간이 듬
  • 처리율 제한 알고리즘
    • 토큰 버킷(token bucket)
      • 간단하고, 알고리즘에 대한 세간의 이해도도 높은 편이며 인터넷 기업들이 보편적으로 사용하고 있음
      • 토큰 버킷은 저장된 용량을 갖는 컨테이너. 이 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워짐. 토큰이 꽉 찬 버킷에는 더 이상의 토큰은 추가되지 않음
      • 장점
        • 구현이 쉬움
        • 메모리 사용 측면에서도 효율적임
        • 짧은 시간에 집중되면 트래픽(burst of traffic)도 처리 가능함 버킷에 남은 토큰이 있기만 하면 요청은 시스템에 전달될 것
      • 단점
        • 이 알고리즘은 버킷 크기와 토큰 공급률이라는 두 개 인자를 가지고 있는데, 이 값을 적절하게 튜닝하는 것은 까다로운 일이 될 것
    • 누출 버킷(leaky bucket)
      • 토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다는 점이 다름. 누출 버킷 알고리즘은 보통 FIFO 큐로 구현함
        • 요청이 도착하면 큐가 가득 차 있는지 봄. 빈자리가 있는 경우에는 큐에 요청을 추가함
        • 큐가 가득차 있는 경우에는 새 요청은 버림
        • 지정된 시간마다 큐에서 요청을 꺼내어 처리함
        • 장점
          • 큐의 크기가 제한되어 있어 메모리 사용량 측면에서 효율적
          • 고정된 처리율을 갖고 있기 때문에 안정적 출력(stable outflow rate)이 필요한 경우에 적합함
        • 단점
          • 단시간에 많은 트래픽이 몰리는 경우 큐에는 오래된 요청들이 쌓이게 되고, 그 요청들을 제때 처리 못하면 최신 요청들은 버려지게 됨
          • 두 개 인자를 갖고 있는데, 이들을 올바르게 튜닝하기가 까다로울 수 있음
    • 고정 윈도 카운터(fixed window counter)
      • 동작
        • 타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙임
        • 요청이 접수될 때마다 이 카운터의 값은 1씩 증가함
        • 이 카운터의 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도가 열릴 때까지 버려짐
      • 이 알고리즘의 가장 큰 문제는 윈도우 경계 부근에 순간적으로 많은 트래픽이 집중될 경우 윈도에 할당된 양보다 더 많은 요청이 처리될 수 있다는 것
      • 장점
        • 메모리 효율이 좋음
        • 이해하기 쉬움
        • 윈도가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기에 적합함
      • 단점
        • 윈도 경계 부근에서 일시적으로 많은 트래픽이 몰려드는 경우, 기대했던 시스템의 처리 한도보다 많은 양의 요청을 처리하게 됨
    • 이동 윈도 로그(sliding window log)
      • 윈도 경계 부근에 트래픽이 집중되는 경우 시스템에 설정된 한도보다 많은 요청을 처리하게 된다는 것
      • 이동 윈도 로깅 알고리즘은 이 문제를 해결함
      • 장점
        • 이 알고리즘이 구현하는 처리율 제한 메커니즘은 아주 정교함. 어느 순간의 윈도를 보더라도, 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않음
      • 단점
        • 이 알고리즘은 다량의 메모리를 사용하는데, 거부된 요청의 타임스탬프도 보관하기 때문
    • 이동 윈도 카운터(sliding window counter)
      • 고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것
      • 장점
        • 이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응함
        • 메모리 효율도 좋음
      • 단점
        • 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 때문에 다소 느슨함
  • 개략적인 아키텍처
    • 얼마나 많은 요청이 접수되었는지를 추적할 수 있는 카운터를 추적 대상별로 두고(사용자별로 추적할 것인가? 아니면 IP 주소별로? 아니면 API 엔드포인트나 서비스 단위로?), 이 카운터의 값이 어떤 한도를 넘어서면 한도를 넘어 도착한 요청은 거부하는 것
    • 카운터는 어디 보관할 것. 데이터베이스는 디스크 접근 때문에 느리니까 사용하면 안 될 것. 메모리상에서 동작하는 캐시가 바람직한데, 빠르데다 시간에 기반한 만료 정책을 지원하기 때문.
    • 레디스는 처리율 제한 장치를 구현할 때 자주 사용되는 메모리 기반 저장장치로서, INCR과 EXPIRE의 두 가지 명령어를 지원함
      • INCR: 메모리에 저장된 카운터의 값을 1만큼 증가시킴
      • EXPIRE: 카운터에 타임아웃 값을 설정함. 설정된 시간이 지나면 카운터는 자동으로 삭제됨
    • 처리율 제한 장치의 동작 원리
      • 클라이언트가 처리율 제한 미들웨이(rate limiting middleware)에게 요청을 보냄
      • 처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와서 한도에 도달했는지 아닌지를 검사함
        • 한도에 도달했다면 요청은 거부됨
      • 한도에 도달하지 않았다면 요청은 API 서버로 전달됨. 한편 미들웨어는 카운터의 값을 증가시킨 후 다시 레디스에 저장함
• 상세 설계
  • 상세한 설계 도면
    • 처리율 제한 규칙은 디스크에 보관함. 작업 프로세스는 수시로 규칙을 디스크에서 읽어 캐시에 저장함
    • 클라이언트가 요청을 서버로 보내면 요청은 먼저 처리율 제한 미들웨이에 도달함
    • 처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져옴. 아울러 카운터 및 마지막 요청의 타임스탬프를 레디스 캐시에서 가져옴
      • 해당 요청이 처리율 제한에 걸리지 않은 경우에는 API 서버로 보냄
      • 해당 요청이 처리율 제한에 걸렸다면 429 too many requests 에러를 클라이언트에 보냄. 한편 해당 요청은 그대로 버릴 수도 있고 메시지 큐에 보관할 수도 있음
  • 분산 환경에서의 처리율 제한 장치의 구현
    • 여러 대의 서버와 병렬 스레드를 지원하도록 시스템을 확장하는 것은 또 다른 문제. 두 가지 어려운 문제
      • 경쟁 조건(race condition)
        • 처리율 제하 장치는 대략 다음과 같잉 동작함
          • 레디스에서 카운터의 값을 읽는다(counter)
          • counter + 1의 값이 임계치를 넘는지 본다
          • 넘지 않는다면 레디스에 보관된 카운터 값을 1만큼 증가시킴
          • 병행성이 심환 환겨에서는 경쟁 조건 이슈가 발생할 수 있ㅇ므
        • 경쟁 조건 문제를 해결하려는 가장 널리 알려진 해결책은 락(lock). 하지만 락은 시스템의 성능을 상당힐 떨어뜨린다는 문제가 있음
      • 동기화(synchronization)
        • 동기화는 분산 환경에서 고려해야 할 또 다른 중요한 요소. 수백만 사용자를 지원하려면 한 대의 처리율 제한 장치 서버로는 충분하지 않을 수 있음. 처리율 제한 장치 서버를 여러 대 두게 되면 동기화가 필요해짐
        • 고정 세션(sticky session)을 활용하여 같은 클라이언트로부터의 요청은 항상 같은 처리율 제한 장치로 보낼 수 있도록 하는 것. 하지만 이 방법은 추천하고 싶지 않은데, 규모면에서 확장 가능하지도 않고 유연하지도 않기 때문. 레디스와 같은 중앙 집중형 데이터 저장소를 쓰는 것
• 해당 알고리즘을 구현하는 아키텍처, 분산환경에서의 처리율 제한 장치, 성능 최적화와 모니터링 등의 주제를 살펴보았음
  • 경성(hard) 또는 연성(soft) 처리율 제한
    • 경성 처리율 제한 : 요청의 개수는 임계치를 절대 넘어설 수 없음
    • 연성 처리율 제한 : 요청 개수는 잠시 동안은 임계치를 넘어설 수 있음
  • 다양한 계층에서의 처리율 제한
    • 애플리케이션 계층(HTTP: OSI 네트워크 계층도 기준으로 7번 계층)에서의 처리율 제한에 대해서만 살펴보았음.
    • Iptables를 사용하면 IP 주소(IP는 OSI 기준으로 3번 계층)에 처리율 제한을 적용하는 것이 가능함.
    • OSI는 Open Systems Interconnection model의 약어로, 총 7개의 계층으로 구성됨. 1번 계층은 물리(physical) 계층, 2번 계층은 데이터 링크(data link) 계층, 3번은 네트워크 계층, 4번은 전송(transport) 계층, 5번은 세션(session) 계층, 6번은 표현(presentaion) 계층, 그리고 7번은 애프리케이션 계층
    • 처리율 제한을 회피하는 방법
      • 클라이언트 측 캐시를 사용하여 API 호출 횟수를 줄임
      • 처리율 제한의 임계치를 이해하고, 짧은 시간 동안 너무 많은 메시지를 보내지 않도록 함
      • 예외나 에러를 처리하는 코드를 도입하여 클라이언트가 예외적 상황으로부터 우하하게(gracefully) 복구될 수 있도록 함
      • 재시도(retry) 로직을 구현할 때는 충분한 백오프(back-off) 시간을 둠

안정 해시 설계

• 수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요함. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하ㅡㄴ 기술
• 안정 해시(consistent hash)
  • 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술
  • k는 키의 개수이고, n은 슬롯(slot)의 개수. 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치함
  • 기본 구현법의 두 가지 문제
    • 절차
      • 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치함
      • 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
    • 두 가지 문제
      • 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 게 불가능하다는 것. 파티션은 인접한 서버 사이에 해시 공간.
      • 키의 균등 분포를 달성하기 어렵다는 것.
    • 이 문제를 해결하기 위해 제안된 기법이 가상 노드(virtual node)또는 복제(replica)라 불리는 기법
  • 가상 노드
    • 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있음
  • 이점
    • 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화됨
    • 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉬움
    • 핫스팟 키 문제를 줄임. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있음. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄임
• 안정 해시의 유명한 것 몇 가지
  • 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
  • 아파치 카산드라 클러스터에서의 데이터 파티셔닝
  • 디스코드 채팅 어플리케이션
  • 아카마이 CDN
  • 매그레프 네트워크 부하 분산기

키-값 저장소 설계

• 키-값 저장소(key-value store)는 키-값 데이터베이스라고도 불리는 비 관계형(non-relational) 데이터베이스. 이 저장소에 저장되는 값은 고유 식별자(identifier)를 키로 가져야 함. 키와 값 사이의 이런 연결 관계를 키-값 쌍(pair)이라고 지칭함
• 키-값 쌍에서는 키는 유일해야 하며 해당 키에 매달린 값은 키를 통해서만 접근할 수 있음. 키는 일반 텍스트일 수도 있고 해시 값일 수도 있음. 성능상의 이유로, 키는 짧을수록 좋음
• 키-값 저장소로 널리 알려진 것으로는 아마존 다이나모, memcached, 레디스 같은 것들이 있음
• 설계
  • put(key, value) : 키-값 쌍을 저장소에 저장함
  • get(key) : 인자로 주어진 키에 매달린 값을 꺼냄
• 단일 서버 키-값 저장소
  • 빠른 속도를 보장하긴 하지만 모든 데이터를 메모리 안에 두는 것이 불가능할 수도 있다는 약점. 개선책
    • 데이터 압축
    • 자주 쓰이는 데이터만 메모리에 두고 나머지는 디스크에 저장
• 분산 키-값 저장소
  • 분산 키-값 저장소는 분산 해시 테이블이라고도 불림. 키-값 쌍을 여러 서버에 분산시키는 탓. 분산시스템을 설계할 때는 CAP 정리(Consistency, Availability, Partition Tolerance theorem)를 이해하고 있어야 함
  • CAP 정리
    • 데이터 일관성(consistency), 가용성(availability), 파티션 감내(partition tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리
      • 데이터 일관성 : 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 함
      • 가용성 : 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 함
      • 파티션 감내 : 파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미함. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작해야 한다는 것을 뜻함
    • CAP정리는 어떤 두 가지를 충족하려면 나머지 하나는 반드시 희생되어야 한다는 것을 의미함
      • CP 시스템 : 일관성과 파티션 감내를 지원하는 키-값 저장소. 가용성을 희생함
      • AP 시스템 : 가용성과 파티션 감내를 지원하는 키-값 저장소. 데이터 일관성을 희생함
      • CA 시스템 : 일관성과 가용성을 지원하는 키-값 저장소. 파티션 감내는 지원하지 않음. 그러나 통상 네트워크 장애는 피할 수 없는 일로 여겨지므로, 분산 시스템은 반드시 파티션 문제를 감내할 수 있도록 설계되어야 함. 그러므로 실세계에 CA 시스템은 존재하지 않음
  • 데이터 파티션
    • 데이터를 작은 파티션들로 분할한 다음 여러 대 서버에 저장하는 것.
    • 데이터를 파티션 단위로 나눌 때는 다음 두 가지 문제를 중요하게 따져봐야 함
      • 데이터를 여러 서버에 고르게 분산할 수 있는가
      • 노드가 추가되거나 삭제될 때 데이터의 이동을 최소화할 수 있는가
      • 안정 해시를 사용하여 데이터를 파티션하면 좋은 점
        • 규모 확장 자동화(automatic scaling) : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있음
        • 다양성(heterogeneity) : 각 서버의 용량에 맞게 가상 노드(virtual node)의 수를 조정할 수 있음. 고성ㄴ으 서버는 더 많은 가상 노드를 갖도록 설정할 수 있음
  • 데이터 다중화
    • 높은 가용성과 안정성을 확보하기 위해서는 데이터를 N개 서버에 비동기적으로 다중화(replication)할 필요가 있음. N은 튜닝 가능한 값
    • 안정성을 담보하기 위해 데이터의 사본은 다른 센터의 서버에 보관하고, 센터들은 고속 네트워크로 연결함
  • 데이터 일관성
    • 여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 함. 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모둥에 일관성을 보장할 수 있음
  • 일관성 모델(consistency model)
    • 키-값 저장소를 설계할 때 고려해야할 또 하나의 중요한 요소
      • 강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환함. 클라이언트는 절대로 낡은(out-of-date) 데이터를 보지 못함
      • 약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있음
      • 최종 일관성(eventual consistency) : 약한 일관성의 한 형태로, 갱신 결과가 결국에는 모든 사본에 반영(즉, 동기화)되는 모델
    • 강한 일관성을 달성하는 일반적인 방법은, 모든 사본에 현재 쓰기 연산의 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지하는 것. 이 방법은 고가용성 시스템에는 적합하지 않음. 새로운 요청의 처리가 중단되기 때문
  • 비 일관성 해소 기법 : 데이터 버저닝
    • 데이터를 다중화하면 가용성은 높아지지만 사본 간 일관성이 깨질 가능성은 높아짐.
    • 버저닝(versioning)과 벡터 시계(vector clock)는 그 문제를 해소하기 위해 등장한 기술.
    • 버저닝은 데이터를 변경할 때마다 해당 데이터의 새로운 버전을 만드는 것을 의미함. 따라서 각 버전의 데이터는 변경 불가능(immutable)함
    • 벡터 시계는 [서버, 버전]의 순서쌍을 데이터에 매단 것. 어떤 버전이 선행 버전인지, 후행 버전인지, 아니면 다른 버전과 충돌이 있는지 판별하는데 쓰임
    • 벡터 시계를 사용해 충돌을 감지하고 해소하는 방법에는 두 가지 분명한단점이 있음
      • 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로, 클라이언트 구현이 복잡해진다는 것
      • [서버: 버전]의 순서쌍 개수가 굉장히 빨리 늘어난다는 것. 이 문제를 해결하려면 그 길이에 어떤 임계치(threshold)를 설정하고, 임계치 이상으로 길이가 길어지면 오래된 순서쌍을 벡터 시계에서 제거하도록 해야 함
  • 장애 처리
    • 장애 감지(failure detection) 기법.
      • 분산 시스템에서는 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버에 실제로 장애가 발생했다고 간주하게 됨.
      • 모든 노드 사이에 멀티캐스팅 채널을 구축하는 것이 서버 장애를 감지하는 가장 손쉬운 방법. 서버가 많을 때는 분명 비효율적
      • 가십 프토콜(gossip protocol) 같은 분산형 장애 감지(decentralized failure detection) 솔루션을 채택하는 편이 보다 효율적
    • 장애 해소(failure resolution) 전략들
    • 일시적 장애 처리
      • 엄격한 정족수(strict quorum) 접근법을 쓴다면, 앞서 데이터 일관성 절에서 설명한 대로, 읽기와 쓰기 연산을 금지해야 할 것
      • 느슨한 정족수(sloppy quorum) 접근법은 이 조건을 완화하여 가용성을 높임
      • 반-엔트로피(anti-entropy) 프로토콜을 구현하여 사본들을 동기화할 것. 반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함함. 사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해서는 머클(Merkle) 트리를 사용할 것
      • 머클 트리의 정의는 해시 트리라고도 불리는 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시(자식 노드가 종단(leaf) 노드인 경우), 또는 자식 노드들의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리
    • 데이터 센터 장애 처리
      • 데이터 센터 장애는 정전, 네트워크 장애, 자연재해 등 다양한 이유로 발생할 수 있음. 데이터 센터 장애에 대응할 수 있는 시스템을 만들려면 데이터를 여러 데이터 센터에 다중화하는 것이 중요함
  • 시스템 아키텍처 다이어 그램
    • 주된 기능
      • 클라이언트는 키-값 저장소가 제공하는 두 가지 단순한 API, 즉 get(key) 및 put(key, value)와 통신함
      • 중재자(coordinator)는 클라이언트에게 키-값 저장소에 대한 프락시 역할을 하는 노드
      • 노드는 안정 해시(consistent hash)의 해시 링(hash ring) 위에 분포함
      • 노드를 자동으로 추가 또는 삭제할 수 있도록, 시스템은 완전히 분산됨(decentralized)
      • 데이터는 여러 노드에 다중화됨
      • 모든 노드가 같은 책임을 지므로, SPOF는 존재하지 않음
    • 
    • 쓰기 경로
      • 쓰기 요청이 커밋 로그(commit log) 파일에 기록됨
      • 데이터가 메모리 캐시에 기록됨
      • 메모리 캐시가 가득차거나 사전에 정의된 어떤 임계치에 도달하면 데이터는 딧드크에 있는 SSTable에 기록됨. SSTable은 Sorted-String Table의 약어로 <키,값>의 순서쌍을 정렬히 리스트 형태로 관맇나느 테이블
    • 읽기 경로
      • 데이터가 메모리에 없을 때 읽기연산이 처리되는 경로
        • 데이터가 메모리에 있는지 검사함. 없으면 2로 감
        • 데이터가 메모리에 없으면 블룸 필터를 검사함
        • 블룸 필터를 통해 어떤 SSTable에 키가 보관되어 있는지 알아냄
        • SSTable에서 데이터를 가져옴
        • 해당 데이터를 클라이언트에게 반환함

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

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

• auto_increment 속성이 설정된 관계형 데이터베이스의 기본 키를 쓰면 되지 않을까? 하지만 분산 환경에서 이 접근법은 통하지 않을 텐데, 데이터베이스 서버 한 대로는 그 요구를 감당할 수 없을뿐더러, 여러 데이터베이스 서버를 쓰는 경우에는 지연 시간(delay)을 낮추기가 무척 힘들 것이기 때문
• 개략적 설계안 제시 및 동의 구하기
  • 분산 시스템에서 유일성이 보장되는 ID를 만드는 여러 가지 방법
    • 다중 마스터 복제(multi-master replication)
    • UUID(Universally Unique Identifier)
    • 티켓 서버(ticket server)
    • 트위터 스노플레이크(twitter snowflake) 접근법
  • 다중 마스터 복제(multi-master replcation)
    • 데이터베이스의 auto_increment 기능을 활용하는 것. ID의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, K만큼 증가시킴. K는 현재 사용 중인 데이터베이스 서버의 수
    • 단점
      • 여러 데이터 센터에 걸쳐 규모를 늘리기 어려움
      • ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할수는 없음
      • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어려움
  • UUID
    • UUID는 유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법. UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수. UUID 값은 충돌 가능성이 지극히 낮음
    • 장점
      • UUID를 만드는 것은 단순함. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없음
      • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉬움
    • 단점
      • ID가 128비트로 길다
      • ID를 시간순으로 정렬할 수 없음
      • ID에 숫자(numeric) 아닌 값이 포함될 수 있음
  • 티켓 서버(ticket server)
    • 유일성이 보장되는 ID를 만들어 내는 데 쓰일 수 있는 또 하나의 흥미로운 방법
    • auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것
      • 장점
        • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있음
        • 구현하기 쉽고, 중소 규모 애플리케이션에 적합함
      • 단점
        • 티켓 서버가 SPOF가 됨. 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받음. 이 이슈를 피하려면 티켓 서버를 여러 대 준비해야 함. 하지만 그렇게 하면 데이터 동기화 같은 새로운 문제가 발생할 것
  • 트위터 스노플레이크 접근법
    • 생성해야 하는 ID의 구조를 여러 절(section)로 분할하는 것
• 마무리
  • 시계 동기화(clock synchronization)
    • ID 생성 서버들이 전부 같은 시계를 사용한다고 가정하였음. 하지만 이런 가정은 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있음. 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에도 마찬가지. NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적인 수단
  • 각 절(section)의 길이 최적화
    • 예를 들어 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적일 수도 있을 것
  • 고가용성(high availability)
    • ID 생성기는 필수 불가결(mission critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 할 것

URL 단축기 설계

• 개략적 설계안 제시 및 동의 구하기
  • API 엔드포인트
    • 클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신함. 우리는 엔드포인트를 REST 스타일로 설계할 것
    • URL 단축기는 기본적으로 두 개의 엔드포인트를 필요로 함
      • URL 단축용 엔드 포인트
        • 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 함.
        • POST/api/v1/data/shorten
          • 인자 : {longUrl:longURLstring}
          • 반환 : 단축 URL
      • URL 디리렉션용 엔드포인트 : 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트
        • GET/api/v1/shortUrl
          • 반환 : HTTP 리디렉션 목적지가 될 원래 URL
    • URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것. 해시 테이블에 <단축 URL, 원래 URL>의 쌍을 지정한다고 가정한다면, URL 리디렉션은 다음과 같이 구현될 수 있음
      • 원래 URL = hashTable.get(단축 URL)
      • 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송
• 상세 설계
  • 두 접근법 비교

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

• 마무리
  • 처리율 제한 장치(rate limiter) : 지금까지 살펴본 시스템은 엄청난 양의 URL 단축 요청이 밀려들 경우 무력화될 수 있다는 잠재적 보안 결함을 갖고 있음. 처리율 제한 장치를 두면, IP 주소를 비롯한 필터링 규칙(filtering rule)들을 이용해 요청을 걸래낼 수 있을 것
  • 웹 서버의 규모 확장 : 본 설계에 포함된 웹 계층은 무상태(stateless) 계층이므로, 웹 서버를 자유로이 증설하거나 삭제할 수 있음
  • 데이터베이스의 규모 확장 : 데이터베이스를 다중화하거나 샤딩하여 규모 확장성을 달성할 수 있음
  • 데이터 분석 솔루션 : 성공적인 비즈니스를 위해서는 데이터가 중요함. URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있을 것
  • 가용성, 데이터 일관성, 안정성 : 대규모 시스템이 성공적으로 운영되기 위해서는 반드시 갖추어야 할 속성들

웹 크롤러 설계

• 웹 크롤러는 로봇 또는 스파이더라고도 부름. 웹에 새로 올라오거나 갱신된 콘텐츠를 찾아내는 것이 주된 목적
• 이용
  • 검색 엔진 인덱싱
    • 크롤러의 가장 보편적인 용례. 크롤러는 웹 페이지를 모아 검색 엔진을 위한 로컬 인덱스를 만듬. 일례로 Googlebot은 구글 검색 엔진이 사용하는 웹 크롤러
  • 웹 아카이빙(web archiving)
    • 나중에 사용할 목적으로 장기보관하기 위해 웹에서 정보를 모으는 절차를 말함. 많은 국립 도서관이 크롤러를 돌려 웹 사이트를 아카이빙하고 있음. 대표적으로 미국 국회 도서관, EU 웹 아카이브
  • 웹 마이닝
    • 웹의 폭발적 성장세는 데이터 마이닝 업계에 전례 없는 기회. 웹 마이닝을 통해 인터넷에서 유용한 지식을 도출해 낼 수 있을 것. 일례로, 유명 금융 기업들은 크롤러를 사용해 주주 총회 자료나 연차 보고서를 다운받아 기업의 핵심 사업 방향을 알아내기도 함
  • 웹 모니터링
    • 크롤러를 사용하면 인터넷에서나 저작권이나 상표권 침해되는 사례를 모니터링할 수 있음. 일례로 디지마크사는 웹 크롤러를 해적판 저작물을 찾아내서 보고함
• 문제 이해 및 설계 범위 확정
  • 좋은 웹 크롤러가 만족시켜야 할 속성
    • 규모 확장성 : 웹은 거대함. 병행성을 활용하면 보다 효과적으로 웹 크롤링을 할 수 있을 것
    • 안정성(robustness) : 웹은 함정으로 가득함. 잘못 작성된 HTML, 아무 반응이 없는 서버, 장애, 악성 코드가 붙어 있는 링크 등. 비정상적인 입력이나 환경에 잘 대응할 수 있어야 함
    • 예절(politeness) : 크롤러는 수집 대상 웹 사이트에 짧은 시간 동안 너무 많은 요청을 보내서는 안됨
    • 확장성(extensibility) : 새로운 형태의 콘텐츠를 지원하기 쉬워야 함
• 개략적 설계안 제시 및 동의 구하기
  • 시작 URL 집합
    • 시작 URL 집합은 웹 크롤러가 크롤링을 시작하는 출발점
  • 미수집 URL 저장소
    • 크롤링 상태를 (1) 다운로드 할 URL, 그리고 (2) 다운로드된 URL
    • 다운로드할 URL을 저장 관리하는 컴포넌트를 미수집 URL 저장소(URL frontier), FIFO 큐라고 생각하면 됨
  • HTML 다운로더 : 인터넷에서 웹 페이지에 다운로드하는 컴포넌트
  • 도메인 이름 변환기 : 웹 페이지를 다운로드 받으려면 URL을 IP 주소로 변환하는 절차가 필요함.
  • 콘텐츠 파서 : 웹 페이지를 다운로드하면 파싱과 검증 절차를 거쳐야 함
  • 중복 콘텐츠인가 : 같은 콘텐츠를 여러 번 저장하게 될 수 있음
  • 콘텐츠 저장소
    • 콘텐츠 저장소는 HTML 문서를 보관하는 시스템.
    • 저장소를 구현하는 데 쓰일 기술을 고를 때는 저장할 데이터 유형, 크기, 저장소 접근 빈도, 데이터의 유효 기간 등을 종합적으로 고려해야 함
  • URL 추출기
    • URL 추출기는 HTML 페이지를 파싱하여 링크들을 골라내는 역할을 함
  • URL 필터 : URL 필터는 특정한 콘텐츠 타입이나 파일 확장자를 갖는 URL, 접속시 오류가 발생하는 URL, 접근 제외 목록(deny list)에 포함된 URL 등을 크롤릴 대상에서 배제하는 역할을 함
  • 이미 방문한 URL : 이미 방문한 URL이나 미수집 URL 저장소에 보관된 URL을 추적할 수 있도록 하는 자료 구조를 사용할 것
  • URL 저장소 : URL 저장소는 이미 방문한 URL을 보관하는 저장소
• 상세 설계
  • 가장 중요한 컴포넌트와 그 구현 기술
    • DFS를 쓸 것인가, BFS를 쓸 것인가
      • 웹은 유향 그래프(directed graph)나 같음. 페이지는 노드이고 하이퍼링크는 에지라고 보면 됨. DFS, 즉 깊이 우선 탐색법은 좋은 선택이 아닐 가능성이 높음. 그래프 크기가 클 경우 어느 정도로 깊숙이 가게 될지 가늠하기 어려움
      • 웹 크롤러는 보통 BFS, 즉 너비 우선 탐색법을 사용함. BFS는 FIFO 큐를 사용하는 알고리즘. 한쪽으로는 탐색할 URL을 집어넣고, 다른 한쪽으로는 꺼내기만 함
    • 미수집 URL 저장소
      • URL 저장소는 다운로드할 URL을 보관하는 장소. 이 저장소를 잘 구현하면 예의(politeness)를 갖춘 크롤러, URL 사이의 우선순위와 신선도를 구별하는 크롤러를 구현할 수 있음
      • 예의
        • 웹 클롤러는 수집 대상 서버로 짧은 시간 안에 너무 많은 요청을 보내는 것을 삼가야 함. 너무 많은 요청을 보내는 것은 무례한(impolite) 일이며, 때로는 DoS(Denial-of-Service) 공격으로 간주되기도 함
    • HTML 다운로더
      • 성능 최적화 : HTML 다운로더에 사용할 수 있는 성능 최적화 기법들
        • 분산 크롤링 : 성능을 높이기 위해 크롤링 작업을 여러 서버에 분산하는 방법
        • 도메인 이름 변환 결과 캐시
          • 도메인 이름 변환기(DNS Resolver)는 크롤러 성능의 병목 중 하나인데, 이는 DNS 요청을 보내고 결과를 받는 작업의 동기적 특성 때문
          • DNS 조회 결과로 얻어진 도메인 이름과 IP 주소 사이의 관계를 캐시에 보관해 놓고 크론 잡(cron job) 등을 돌려 주기적으로 갱신하도록 해 놓으면 성능을 효과적으로 높일 수 있음
        • 지역성
          • 크롤링 작업을 수행하는 서버를 지역별로 분산하는 방법.
          • 크롤링 서버가 크롤링 대상 서버와 지역적으로 가까우면 페이지 다운로드 시간은 줄어들 것. 지역성을 활용하는 전략은 크롤 서버, 캐시, 큐, 저장소 등 대부분의 컴포넌트에 적용 가능함
        • 짧은 타임아웃
          • 대기 시간이 길어지면 좋지 않으므로 최대 얼마나 기다릴지를 미리 정해두는 것
• 마무리
  • 서버 측 렌더링(server-side rendering)
    • 많은 웹사이트가 자바스크립트, AJAX 등의 기술을 사용해서 링크를 즉석에서 만들어 냄. 웹 페이지를 그냥 있는 그대로 다운받아서 파싱해보면 그렇게 동적으로 생성되는 링크는 발견할 수 없을 것. 이 문제는 페이지를 파싱하기 전에 서버 측 렌더링(동적 렌더링)을 적용하면 해결할 수 있음
    • 원치 않는 페이지 필터링 : 저장 공간 등 크롤링에 소요되는 자원은 유한하기 때문에 스팸 방지 컴포넌트를 두어 품질이 조악하거나 스팸성인 페이지를 걸러내도록 해 두면 좋음
    • 데이터 베이스 다중화 및 샤딩 : 다중화나 샤딩 같은 기법을 적용하면 데이터 계층의 가용성, 규모 확장성, 안정성이 향상됨
    • 수평적 규모 확장성 : 대규모 크롤링을 위해서는 다운로드를 실행할 서버가 수백 혹은 수천 대 필요하게 될 수도 있음. 수평적 규모 확장성을 달성하는 데 중요한 것은 서버가 상태정보를 유지하지 않도록 하는 것, 즉 무상태(stateless) 서버로 만드는 것
    • 가용성, 일관성, 안정성 : 이런 개념들은 성공적인 ㄷ대형 시스템을 만들기 위해 필수적으로 고려해야 하는 것들
    • 데이터 분석 솔루션 : 데이터를 수집하고 분석하는 것은 어느 시스템에게나 중요함

알림 시스템 설계

• 알림 시스템은 모바일 푸시 알람, SMS 메시지, 그리고 이메일ㅇ릐 세 가지로 분류할 수 있음
• 개략적 설계안 제시 및 동의 구하기
  • 알림 유형별 지원 방안
    • iOS 푸시 알림
      • iOS에서 푸시 알림을 보내기 위해서는 세 가지 컴포넌트가 필요함
      • 알림 제공자 : 알림 요청을 만들어 애플 푸시 알림 서비스(APNS)로 보내는 주체
      • APNS: 애플이 제공하는 원격 서비스
      • iOS 단말 : 푸시 알림을 수신하는 사용자 단말
    • 안드로이드 푸시 알림
      • APNS 대신 FCM(Firebase Cloud Messaging)을 사용한다는 점만 다름
    • SMS 메시지
      • SMS 메시지를 보낼 때는 보통 트윌리오, 넥스모 같은 제 3사업자의 서비스를 많이 이용함
    • 이메일
      • 상용 이메일 서비스를 이용함. 센드그리드, 메일침프. 전송 성공률도 높고, 데이터 분석 서비스도 제공함
  • 개략적 설계안(개선된 버전)
    • 데이터베이스와 캐시를 알림 시스템의 주 서버에 분리함
    • 알림 서버를 증설하고 자동으로 수평적 규모 확장이 이루어질 수 있도록 함
    • 메시지 큐를 이용해 시스템 컴포넌트 사이의 강한 결합을 끊음
    • 시스템 개선안
      • 1부터 N까지의 서비스 : 알림 시스템 서버의 API를 통해 알림을 보낼 서버들
      • 알림 서버
        • 알림 전송 API : 스팸 방지를 위해 보통 사내 서비스 또는 인증된 클라이언트만 이용 가능함
        • 알림 검증 : 이메일 주소, 전화번호 등에 대한 기본적 검증을 수행함
        • 데이터베이스 또는 캐시 질의: 알림에 포함시킬 데이터를 가져오는 기능
        • 알림 전송 : 알림 데이터를 메시지 큐에 넣음. 본 설계안의 경우 하나 이상의 메시지 큐를 사용하므로 알림을 병렬적으로 처리할 수 있음
      • 캐시 : 사용자 정보, 단말 정보, 알림 템플릿 등을 캐시함
      • 데이터베이스 : 사용자, 알림, 설정 등 다양한 정보를 저장함
      • 메시지 큐 : 시스템 컴포넌트 간 의존성을 제거하기 위해 사용함. 다량의 알림이 전송되어야 하는 경우를 대비한 버퍼 역할도 함.
      • 작업 서버 : 메시지 큐에 전송할 알림을 꺼내서 제3자 서비스로 전달하는 역할을 담당하는 서버
      • 제3자 서비스(third party services) : 이 서비스들은 사용자에게 알림을 실제로 전달하는 역할을 함
      • iOS, 안드로이드, SMS, 이메일 단말
    • 어떻게 협력하여 알림을 전송하는지
      • API를 호출하여 알림 서버로 알림을 보냄
      • 알림 서버는 사용자 정보, 단말 토큰, 알림 설정 같은 메타데이터를 캐시나 데이터베이스에서 가져옴
      • 알림 서버는 전송할 알림에 맞는 이벤트를 만들어서 해당 이벤트를 위한 큐에 넣음.
      • 작업 서버는 메시지 큐에서 알림 이벤트를 꺼냄
      • 작업 서버는 알림을 제3자 서비스로 보냄
      • 제3자 서비스는 사용자 단말로 알림을 전송함
• 상세 설계
  • 안정성
    • 분산 환경에서 운영될 알림 시스템을 설계할 때는 안정성을 확보하기 위한 사항 몇 가지를 고려해야 함
    • 데이터 손실 방지 : 알림 로그(notification log) 데이터베이스를 유지하는 것이 한 ㄱ자ㅣ 방법
    • 알림 중복 전송 방지
      • 중복되어 전송되기 때문에 빈도를 줄이려면 중복을 탐지하는 메커니즘을 도입하고, 오류를 신중하게 처리해야 함
      • 보내야 할 알림이 도착하면 그 이벤트 ID를 검사하여 이전에 본 적이 있는 이벤트인지 살핌. 중복된 이벤트라면 버리고, 그렇지 않으면 알림을 발송함

뉴스 피드 시스템 설계

• 개략적 설계안 제시 및 동의 구하기
  • 피드 발행 : 사용자가 스토리를 포스팅하려면 해당 데이터를 캐시와 데이터베이스에 기록함. 새 포스팅은 친구의 뉴스 피드에 전송됨
  • 뉴스 피드 생성 : 지면 관계상 뉴스 피드는 모든 친구의 포스팅을 시간 흐름 역순으로 모아서 만든다고 가정함
  • 뉴스 피드 API
    • 뉴스 피드 API는 클라이언트가 서버와 통신하기 위해 사용하는 수단. HTTP 프로토콜 기반이고, 상태 정보를 업데이트하거나, 뉴스 피드를 가져오거나, 친구를 추가하는 등의 다양한 작업을 수행하는 데 사용함
• 상세 설계
  • 포스팅 전송(팬아웃) 서비스
    • 어떤 사용자의 새 포스팅을 그 사용자와 친구 관계에 있는 모든 사용자에게 전달하는 과정
  • 쓰기 시점에 팬아웃하는 모델
    • 새로운 포스팅을 기록하는 시점에 뉴스 피드를 갱신하게 됨. 포스팅이 완료되면 바로 해당 사용자의 캐시에 해당 포스팅을 기록하는 것
    • 장점
      • 뉴스 피드가 실시간으로 갱신되며 친구 목록에 있는 사용자에게 즉시 전송 됨
      • 새 포스팅이 기록되는 순간에 뉴스 피드가 이미 갱신되므로(pre-computed) 뉴스 피드를 읽는 데 드는 시간이 짧아짐
    • 단점
      • 친구가 많은 사용자의 경우 친구 목록을 가져오고 그 목록에 있는 사용자 모두의 뉴스 피드를 갱신하는 데 많은 시간이 소요될 수도 있음. 핫키라고 부르는 문제
      • 서비스를 자주 이용하지 않는 사용자의 피드까지 갱신해야 하므로 컴퓨팅 자원이 낭비됨
  • 읽기 시점에 팬아웃하는 모델
    • 피드를 읽어야 하는 시점에 뉴스 피드를 갱신함. 요청 기반(on-demand) 모델. 사용자가 본인 홈페이지나 타임라인을 로딩하는 시점에 새로운 포스트를 가져오게 됨
    • 장점
      • 비활성화된 사용자, 또는 서비스에 거의 로그인하지 않는 사용자의 경우에는 이 모델이 유리함. 로그인하기까지는 어떤 컴퓨팅 자원도 소모하지 않아서
      • 데이터를 친구 각각에 푸시하는 작업이 필요 없으므로 핫키 문제도 생기지 않음
    • 단점
      • 뉴스 피드를 읽는 데 많은 시간이 소요될 수 있음
• 마무리
  • 데이터베이스 규모 확장
    • 수직적 규모 확장 vs 수평적 규모 확장
    • SQL vs NoSQL
    • 주-부(master-slave) 다중화
    • 복제본(replica)에 대한 읽기 연산
    • 일관성 모델(consistency model)
    • 데이터베이스 샤딩(sharding)
  • 논의 주제
    • 웹 계층(web tier)을 무상태로 운영하기
    • 가능한 한 많은 데이터를 캐시할 방법
    • 여러 데이터 센터를 지원할 방법
    • 메시지 큐를 사용하여 컴포넌트 사이의 결합도 낮추기
    • 핵심 메트릭에 대한 모니터링, 예를 들어 트래픽이 몰리는 시간대의 QPS(Queries per Second), 사용자가 뉴스 피드를 새로고침 할때의 지연시간 등이 이에 해당함

채팅 시스템 설계

• 문제 이해 및 설계 범위 확정
  • 페이스북 메신저, 위챗(WeChat), 왓츠앱처럼 1:1 채팅에 집중하는 앱들이 있는가 하면 슬랙 같은 그룹 채팅에 중점을 둔 업무용 앱이나, 게임 채팅에 쓰이는 디스코드 같이 대규모 그룹의 소통과 응답지연이 낮은 음성 채팅에 집중하는 앱도 있음
  • 기능
    • 응답지연이 낮은 일대의 채팅 기능
    • 최대 100명까지 참여할 수 있는 그룹 채팅 기능
    • 사용자의 접속상태 표시 기능
    • 다양한 단말 지원, 하나의 계정으로 여러 단말에 동시 접속 지원
    • 푸시 알림
• 개략적 설계안 제시 및 동의 구하기
  • 채팅 시스템의 경우 클라이언트는 모바일 앱이거나 웹 애플리케이션. 클라이언트는 서로 직접 통신하지 않음
  • 채팅 서비스는 아래 기능을 제공해야 함
    • 클라이언트들로부터 메시지 수신
    • 메시지 수신자(recipient) 결정 및 전달
    • 수신자가 접속 상태가 아닌 경우에는 접속할 때까지 해당 메시지 보관
  • HTTP는 클라이언트가 연결을 만드는 프로토콜이며, 서버에서 클라이언트로 임의 시점에 메시지를 보내는 데는 쉽게 쓰일 수 없음. 서버가 연결을 만드는 것처럼 동작할 수 있도록 하기 위해 많은 기법이 제안되어 왔는데 폴링, 롱 폴링, 웹 소켓 등이 그런 기술
  • 롱 폴링
    • 폴링은 여러 가지로 비효율적일 수 있어서 나온 기법이 롱 폴링
    • 롱 폴링의 경우 클라이언트는 새 메시지가 반환되거나 타임아웃 될 때까지 연결을 유지함. 클라이언트는 새 메시지를 받으면 기존 연결을 종료하고 서버에 새로운 요청을 보내어 모든 절차를 다시 시작함
    • 약점
      • 메시지를 보내는 클라이언트와 수신하는 클라이언트가 같은 채팅 서버에 접속하게 되지 않을 수도 있음
      • 서버 입장에서는 클라이언트가 연결을 해제했는지 아닌지 알 좋은 방법이 없음
      • 여전히 비효율적, 메시지를 많이 받지 않는 클라이언트도 타임아웃이 일어날 때마다 주기적으로 서버에 다시 접속할 것
  • 웹 소켓
    • 서버가 클라이언트에게 비동기(async) 메시지를 보낼 때 가장 널리 사용하는 기술
    • 웹소켓 연결은 클라이언트가 시작함. 한번 맺어진 연결은 항구적이며 양방향임. 이 연결은 처음에는 HTTP 연결이지만 특정 핸드세이크 절차를 걸쳐 웹소켓 연결로 업그레이드됨
    • 일단 이 항구적인 연결이 만들어지고 나면 서버는 클라이언트에게 비동기적으로 메시지를 전송할 수 있음. 웹 소켓은 일반적으로 방화벽이 있는 환경에서도 잘 동작함
  • 개략적 설계안
    • 무상태 서비스
      • 로그인, 회원가입, 사용자 프로파일 표시 등을 처리하는 전통적인 요청/응답 서비스
      • 무상태 서비스는 로드밸런서 뒤에 위치함. 로드밸런서가 하는 일은 요청을 그 경로에 맞는 서비스로 정확하게 전달하는 것
    • 상태 유지 서비스
      • 본 설계안에서 유일하게 상태 유지가 필요한 서비스는 채팅 서비스
      • 각 클라이언트가 채팅 서버와 독립적인 네트워크 연결을 유지해야 하기 때문
    • 제3자 서비스 연동
      • 채팅 앱에서 가장 중요한 제3자 서비스는 푸시 알림
      • 새 메시지를 받았다면 설사 앱이 실행 중이지 않더라도 알림을 받아야 해서
  • 규모 확장성
    • 실시간으로 메시지를 주고받기 위해 클라이언트는 채팅 서버와 웹소켓 연결을 끊지 않고 유지한다는 것
      • 채팅 서버는 클라이언트 사이에 메시지를 중계하는 역할을 담당함
      • 접속상태 서버(presence server)는 사용자의 접속 여부를 관리함
      • API 서버는 로그인, 회원가입, 프로파일 변경 등 그 외 나머지 전부를 처리함
      • 알림 서버는 푸시 알림을 보냄
      • 키-값 저장소(key-value store)에는 채팅 이력(chat history)을 보관함. 시스템에 접속한 사용자는 이전 채팅 이력을 전부 보게 될 것
  • 저장소
    • 관계형 데이터베이스를 쓸 것인가 아니면 NoSQL을 채택할 것인가? 이 질문에 대한 올바른 답을 하기 위해 중요하게 따져야 할 것은, 데이터의 유형과 읽기/쓰기 연산의 패턴
    • 채팅 시스템이 다루는 데이터는 보통 두 가지.
      • 사용자 프로파일 설정, 친구 목록처럼 일반적인 데이터. 이런 데이터는 안정성을 보장하는 관계형 데이터베이스에 보관함. 다중화와 샤딩은 이런 데이터의 가용성과 규모확장성을 보증하기 위해 보편적으로 사용되는 기술
      • 데이터는 채팅 시스템에 고유한 데이터로, 바로 채팅 이력. 이 데이터를 어떻게 보관할지 결정하려면 읽기/쓰기 연산 패턴을 이해해야 함
    • 키-값 저장소를 추천
      • 키-값 저장소는 수평적 규모확장이 쉬움
      • 키-값 저장소는 데이터 접근 지연시간(latency)이 낮음
      • 관계형 데이터베이스는 데이터 가운데 롱 테일에 해당하는 부분을 잘 처리하지 못하는 경향이 있음. 인덱스가 커지면 데이터에 대한 무작위적 접근을 처리하는 비용이 늘어남
      • 이미 많은 안정적인 채팅 시스템이 키-값 저장소를 채택하고 있음. 페이스북 메신저나 디스코드가 그 사례. 페이스북 메신저는 HBase를 사용하고있고 디스코드는 카산드라를 이용하고 있음
  • 데이터 모델
    • 메시지 ID
      • message_id는 메시지들의 순서도 표현할 수 있어야 함
        • message_id의 값은 고유해야 함(uniqueness)
        • ID 값은 정렬 가능해야 하며 시간 순서와 일치해야 함. 즉 새로운 ID는 이전 ID보다 큰 값이어야 함
      • RDBMS라면 auto_increment가 대안이 될 수 있겠지만 NoSQL은 보통 해당 기능을 제공하지 않음
      • 스노우플레이크같은 전역적 64-bit 순서 번호(sequence number) 생성기를 이용하는 것
      • 지역적 순서 번호 생성기
        • 지역적이라 함은, ID의 유일성은 같은 그룹 안에서만 보증하면 충분하다는 것. 이 방법이 통하는 이유는ㅇ 메시지 사이의 순서는 같은 채널 , 혹은 같은 1:1 채팅 세션 안에서만 유지되면 충분하기 때문
• 상세 설계
  • 서비스 탐색
    • 서비스 탐색 기능의 주된 역할은 클라이언트에게 가장 적합한 채팅 서버를 추천하는 것. 이 때 사용되는 기준으로 클라이언트의 위치(geographical location), 서버와 용량 등이 있음
    • 서비스 탐색 기능을 구현하는 데 널리 쓰이는 오픈 소스 솔루션으로는 아파치 주키퍼 같은 것이 있음. 사용 가능한 모든 채팅 서버를 여기 등록시켜 두고, 클라이언트가 접속을 시도하면 사전에 정한 기준에 따라 최적의 채팅 서버를 골라 주면 됨
• 마무리
  • 채팅 앱을 확장하여 사진이나 비디오 등의 미디어를 지원하도록 하는 방법: 미디어 파일은 텍스트에 비해 크기가 큼. 그와 관련하여 압축 방식, 클라우드 저장소, 섬네일 생성 등을 논의해보면 재미있을 것
  • 종단 간 암호화: 왓츠앱은 메시지 전송에 있어 종단 간 암호화를 지원함. 메시지 발신인과 수신자 이외에는 아무도 메시지 내용을 볼 수 없다는 뜻
  • 캐시: 클라이언트에 이미 읽은 메시지를 캐시해 두면 서버와 주고받는 데이터 양을 줄일 수 있음
  • 로딩 속도 개선 : 슬랙은 사용자의 데이터, 채널 등을 지역적으로 분산하는 네트워크를 구축하여 앱 로딩 속도를 개선하였음
  • 오류 처리
    • 채팅 서버 오류 : 채팅 서버 하나에 수십만 사용자가 접속해 있는 상황을 생각해보자. 그런 서버 하나가 죽으면 서비스 탐색 기능(주키퍼 같은)이 동작하여 클라이언트에게 새로운 서버를 배정하고 다시 접속할 수 있도록 해야 함
    • 메시지 재전송 : 재시도(retry)나 큐(queue)는 메시지의 안정적 전송을 보장하기 위해 흔히 사용되는 기법

검색어 자동완성 시스템

• 상세 설계
  • 트라이(trie) 자료 구조
    • 트라이는 문자열들을 간략하게 저장할 수 있는 자료구조. 트라이라는 이름은 retrieval이라는 단어에서 온 것인데 ,문자열을 꺼내는 연산에 초점을 맞추어 설계된 자료구조임을 미루어 짐작할 수 있음.
    • 트라이 자료구조의 핵심 아이디어
      • 트라이는 트리 형태의 자료구조
      • 이 트리의 루트 노드는 빈 문자열을 나타냄
      • 각 노드는 글자 하나를 저장하며, 26개(해당 글자 다음에 등장할 수 있는 모든 글자의 개수)의 자식 노드를 가질 수 있음
      • 각 트리 노드는 하나의 단어, 또는 접두어 문자열(prefix sstring)을 나타냄
  • 데이터 수집 서비스
    • 로그 취합 서버
      • 대부분의 경우에는 일주일에 한 번 정도로 로그를 취합해도 충분할 것. 면접장에서 데이터 취합의 실시간성이 얼마나 중요한지 확인하는 것은 중요함
    • 취합된 데이터
    • 작업 서버
      • 작업 서버(worker)는 주기적으로 비동기적 작업(job)을 실행하는 서버 집합. 트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 담당함
    • 트라이 캐시 : 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 구실을 함. 매주 트라이 데이터베이스의 스냅샷을 떠서 갱신함
    • 트라이 데이터베이스
      • 트라이 데이터베이스는 지속성 저장소
        • 문서 저장소(document store) : 새 트라이를 매주 만들 것으로, 주기적으로 트라이를 직렬화하여 데이터베이스에 저장할 수 있음
        • 키-값 저장소
          • 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
          • 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환
  • 질의 서비스
    • 질의 서비스는 번개처럼 빨라야함. 최적화 방안
      • AJAX 요청(request): 웹 애플리케이션의 경우 브라우저는 보통 AJAX 요청을 보내어 자동완성된 검색어 목록을 가져옴. 이 방법의 장점은 요청을 보내고 받기 위해 페이지를 새로고침할 필요가 없다는 것
      • 브라우저 캐싱: 대부분의 애플리케이션의 경우 자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않음. 제안된 검색어들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져갈 수 있음. 구글 검색 엔진이 이런 캐시 메커니즘을 사용했음
      • 데이터 샘플링 : 대규모 시스템의 경우, 모든 질의 결과를 로깅하도록 해 놓으면 CPU 자원과 저장공간을 엄청나게 소진하게 됨. 데이터 샘플링 기법은 그럴 때 유용함. N개 요청 가운데 1개만 로깅하도록 하는 것
  • 규모 확장이 가능한 저장소
    • 첫 글자를 기준으로 샤딩하는 방법
      • 검색어를 보관하기 위해 두 대 서버가 필요하다면 a부터 m까지 글자로 시작하는 검색어는 첫 번째 서버에 저장하고, 나머지는 두 번째 서버에 저장함
      • 세 대 서버가 필요하다면 a부터 i까지는 첫 번째 서버에, j 부터 r까지는 두 번째 서버에, 나머지는 세 번째 서버에 저장함
  • 트라이 연산
    • 검색어 삭제
      • 혐오성이 짙거나, 폭력적이거나, 성적으로 노골적이거나, 여러 가지로 위험한 질의어를 자동완성 결과에서 제거해야 함
      • 트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 하는 것. 필터 계층을 두면 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있다는 장점이 있음. 데이터베이스에서 해당 검색어를 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비동기적으로 진행하면 됨
• 마무리
  • 아이디어
    • 샤딩을 통하여 작업 대상 데이터의 양을 줄임
    • 순위 모델(ranking model)를 바꾸어 최근 검색어에 보다 높은 가중치를 주도록 함
    • 데이터가 스트림 형태로 올 수 있다는 점, 즉 한번에 모든 데이터를 동시에 사용할 수 없음을 가능성이 있다는 점을 고려해야 함. 데이터가 스트리밍 된다는 것은, 즉 데이터가 지속적으로 생성된다는 뜻. 스트림 프로세싱에는 특별한 종류의 시스템이 필요함. 아파치 하둡 맵리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등이 그런 부류의 시스템

유튜브 설계

• 문제 이해 및 설계 범위 확정
  • 빠른 비디오 업로드
  • 원활한 비디오 재생
  • 재생 품질 선택 기능
  • 낮은 인프라 비용
  • 높은 가용성과 규모 확장성, 그리고 안정성
  • 지원 클라이언트: 모바일 앱, 웹브라우저, 그리고 스마트 TV
• 개략적 설계안 제시 및 동의 구하기
  • 단말(client): 컴퓨터, 모바일 폰, 스마트 TV를 통해서 유튜브를 시청할 수 있음
  • CDN : 비디오는 CDN에 저장함. 재생 버튼을 누르면 CDN으로부터 스트리밍이 이루어짐
  • API 서버: 비디오 스트리밍을 제외한 모든 요청은 API 서버가 처리함. 피드 추천, 비디오 업로드 URL 생성, 메타데이터 데이터베이스와 캐시 갱신, 사용자 가입 등등이 API 서버가 처리하는 작업
  • 비디오 업로드 절차
    • 사용자 : 컴퓨터나 모바일 폰, 혹은 스마트 TV를 통해 유튜브를 시청하는 이용자
    • 로드밸런서: API 서버 각각으로 고르게 요청을 분산하는 역할을 담당함
    • API 서버 : 비디오 스트리밍을 제외한 다른 모든 요청을 처리함
    • 메타데이터 데이터베이스(metadata db) : 비디오의 메타데이터를 보관함. 샤딩과 다중화를 적용하여 성능 및 가용성 요구사항을 충족함
    • 메타데이터 캐시(metadata cache) : 성능을 높이기 위해 비디오 메타데이터와 사용자 객체(user object)는 캐시함
    • 원본 저장소(original storage) : 원본 비디오를 보관할 대형 이진 파일 저장소(BLOB, Binary Large Object Storage) 시스템. BLOB 저장소는 이진 데이터를 하나의 개체로 보관하는 데이터베이스 관리 시스템
    • 트랜스코딩 서버(transcoding server) : 비디오 트랜스코딩은 비디오 인코딩이라 부르기도 하는 절차로, 비디오 포맷(MPEG, HLS 등)을 변환하는 절차. 단말이나 대역폭 요구사항에 맞는 최적의 비디오 스트림을 제공하기 위해 필요함
    • 트랜스코딩 비디오 저장소(transcoded storage) : 트랜스코딩이 완료된 비디오를 저장하는 BLOB 저장소
    • CDN : 비디오를 캐시하는 역할을 담당함. 사용자가 재생 버튼을 누르면 비디오 스트리밍은 CDN을 통해 이루어짐
    • 트랜스코딩 완료 큐 : 비디오 트랜스코딩 완료 이벤트들을 보관할 메시지 큐
    • 트랜스코딩 완료 핸들러 : 트랜스코딩 완료 큐에서 이벤트 데이터를 꺼내어 메타데이터 캐시와 데이터베이스를 갱신할 작업 서버들
  • 비디오 업로드
    • 비디오를 원본 저장소에 업로드함
    • 트랜스코딩 서버는 원본 저장소에 해당 비디오를 가져와 트랜스코딩을 시작함
    • 트랜스코딩이 완료되면 아래 두 절차가 병렬적으로 수행됨
      • 완료된 비디오를 트랜스코딩 비디오 저장소로 업로드함
      • 트랜스코딩 완료 이벤트를 트랜스코딩 완료 큐에 넣음
        • 트랜스코딩이 끝난 비디오를 CDN에 올림
        • 완료 핸들러가 이벤트 데이터를 큐에서 꺼냄
        • 완료 핸들러가 메타데이터 데이터베이스와 캐시를 갱신함
    • API 서버가 단말에게 비디오 업로드가 끝나서 스트리밍 준비가 되었음을 알림
  • 비디오 스트리밍 절차
    • 유튜브에서 비디오 재생버튼을 누르면 스트리밍은 바로 시작되며 비디오 다운로드가 완료되어야 영상을 볼 수 있다거나 하는 불편함은 없음. 여기서 다운로드라 함은 비디오를 단말로 내려받는 것을 말하며, 스트리밍은 여러분의 장치가 원격지의 비디오로부터 지속적으로 비디오 스트림을 전송 받아 영상을 재생하는 것을 말함
    • 스트리밍 프로토콜은 비디오 스트리밍을 위해 데이터를 전송할 때 쓰이는 표준화된 통신방법. 널리 사용되는 스트리밍 프로토콜로는 다음과 같은 것이 있음
      • MPEG-DASH(Moving Picture Experts Group, Dynamic Adaptive Streaming over HTTP)
      • 애플 HLS(HTTP Live Streaming)
      • 마이크로소프트 스무드 스트리밍(Smooth Streaming)
      • 어도비 HTTP 동적 스트리밍(Dynamic Streaming, HDS)
    • 비디오 스트리밍 서비스를 설계할 때는 서비스의 용례에 맞는 프로토콜을 잘 골라야함.
    • 비디오는 CDN에서 바로 스트리밍 됨. 사용자의 단말에 가장 가까운 CDN 에지 서버가 비디오 전송을 담당할 것. 따라서 전송지연은 아주 낮음
• 상세 설계
  • 비디오 트랜스코딩
    • 비디오를 녹화하면 단말(보통 전화나 카메라)은 해당 비디오를 특정 포맷으로 저장함. 이 비디오가 다른 단말에서도 순조롭게 재생되려면 다른 단말과 호환되는 비트레이트와 포맷으로 저장되어야 함
    • 비트레이트는 비디오를 구성하는 비트가 얼마나 빨리 처리되어야 하는 지를 나타내는 단위. 비트레이드가 높은 비디오는 일반적으로 고화질 비디오
    • 비트레이드가 높은 비디오 스트림을 정상 재생하려면 보다 높은 성능의 컴퓨팅 파워가 필요하고, 인터넷 회선 속도도 빨라야 함
    • 인코딩 포맷
      • 컨테이너 : 비디오 파일, 오디오, 메타데이터를 담는 바구니 같은 것. 컨테이너 포맷은 .avi, .mov, .mp4 같은 파일 확장자를 보면 알 수 있음
      • 코덱(codec) : 비디오 화질은 보존하면서 파일 크기를 줄일 목적으로 고안된 압축 및 압축 해제 알고리즘. 가장 많이 사용되는 비디오 코덱으로는 H.264, VP9, HEVC가 잇음
  • 유향 비순환 그래프(DAG) 모델
    • 페이스북의 스트리밍 비디오 엔진은 유향 비순환 그래프 프로그래밍 모델을 도입, 작업을 단계별로 배열할 수 있도록 하여 해당 작업들이 순차적으로 또는 병렬적으로 실행될 수 있도록 하고 있음
  • 비디오 트랜스코딩 아키텍처
    • 클라우드 서비스를 활용한 비디오 트랜스코딩 아키텍처
      • 전처리기
        • 비디오 분할. 비디오 스트림을 GOP라고 불리는 단위로 쪼갬. GOP는 특정 순서로 배열된 프레임 그룹. 하나의 GOP는 독립적으로 재생 가능하며, 길이는 보통 몇 초 정도
        • DAG 생성 : 클라이언트 프로그래머가 작성한 설정 파일에 따라 DAG를 만들어냄
        • 데이터 캐시 : 전처리기는 분할된 비디오의 캐시. 안정성을 높이기 위해 전처리기는 GOP와 메타데이터를 임시 저장소에 보관함
      • DAG 스케줄러
        • DAG 그래프를 몇 개 단계로 분할한 다음에 그 각각을 자원 관리자의 작업 큐(task queue)에 집어넣음
      • 자원 관리자
        • 자원 배분을 효과적으로 수행하는 역할을 담당함. 세 개의 큐와 작업 스케줄러로 구성됨
          • 작업 큐 : 실행할 작업이 보관되어 있는 우선순위 큐
          • 작업 서버 큐 : 작업 서버의 가용 상태 정보가 보관되어 있는 우선순위 큐
          • 실행 큐 : 현재 실행 중인 작업 및 작업 서버 정보가 보관되어 있는 큐
          • 작업 스케줄러: 최적의 작업/서버 조합을 골라, 해당 작업 서버가 작업을 수행하도록 지시하는 역할을 담당함
      • 작업 서버
        • 작업 서버는 DAG에 정의된 작업을 수행함
        • 임시 저장소 구현에는 여러 저장소 시스템을 활용할 수 있음
      • 인코딩된 비디오 : 인코딩 파이프라인의 최종 결과물
  • 시스템 최적화
    • 속도 최적화
      • 비디오 병렬 업로드
      • 업로드 센터를 사용자 근거리에 지정
      • 모든 절차를 병렬화 : 느슨하게 결합된 시스템을 만들어서 병렬성을 높이는 것
      • 메시지 큐를 도입한 뒤에 인코딩 모듈은 다운로드 모듈의 작업이 끝나기를 더 이상 기다릴 필요가 없음. 메시지 큐에 보관된 이벤트 각각을 인코딩 모듈은 병렬적으로 처리할 수 있음
    • 안전성 최적화
      • 미리 사인된 업로드 URL
      • 비디오 보호
        • 비디오의 저작권을 보고하기 위해 다음 세 가지 선택지 가운데 하나를 채택할 수 있음
          • 디지털 저작권 관리(DRM: Digital Rights Management) 시스템 도입 : 애플의 페어플레이, 구글의 와이드 바인, 마이크로소프트의 플레이레디
          • AES 암호화(encryption) : 비디오를 암호화하고 접근 권한을 설정하는 방식. 암호화된 비디오는 재생 시에만 복호화함. 허락된 사용자만 암호화된 비디오를 시청할 수 있음
          • 워터마크 : 비디오 위에 소유자 정보를 포함하는 이미지 오버레이를 올리는 것. 회사 로고나 이름 등을 이 용도에 사용할 수 있음
    • 비용 최적화
      • 유튜브 비디오 스트리밍은 롱테일 분포를 다름. 인기 있는 비디오는 빈번히 재생되는 반면, 나머지는 거의 보는 사람이 없다는 것

구글 드라이브 설계

• 구글 드라이브는 파일 저장 및 동기화 서비스로, 문서, 사진, 비디오, 기타 파일을 클라우드에 보관할 수 있도록 함
• 문제 이해 및 설계 범위 확정
  • 기능 설계
    • 파일 추가. 가장 쉬운 방법은 파일을 구글 드라이브 안으로 떨구는(drag-and-drop) 것
    • 파일 다운로드
    • 여러 단말에 파일 동기화. 한 단말에서 파일을 추가하면 다른 단말에도 자동으로 동기화되어야 함
    • 파일 갱신 이력 조회(revision history)
    • 파일 공유
    • 파일이 편집되거나 삭제되거나 새롭게 공유되었을 때 알림 표시
  • 비-기능적 요구사항
    • 안정성 : 저장소 시스템에서 안정성은 아주 중요함. 데이터 손실은 발생하면 안됨
    • 빠른 동기화 속도 : 파일 동기화에 시간이 너무 많이 걸리면 사용자는 인내심을 잃고 해당 제품을 더 이상 사용하지 않게 될 것
    • 네트워크 대역폭 : 이 제품이 네트워크 대역폭을 불필요하게 많이 소모한다면 사용자는 좋아하지 않을 것. 모바일 데이터 플랜을 사용하는 경우라면 더욱 그렇다.
    • 규모 확장성 : 이 시스템은 아주 많은 양의 트래픽도 처리 가능해야 함
    • 높은 가용성 : 일부 서버에 장애가 발생하거나, 느려지거나, 네트워크 일부가 끊겨도 시스템은 계속 사용 가능해야 함
• 개략적 설계안 제시 및 동의 구하기
  • 한 대 서버의 제약 극복
    • 데이터를 다중화 할 때는 같은 지역 안에서만 할 수도 있고 여러 지역에 걸쳐 할 수도 있음. 여러 지역에 걸쳐 다중화하면 데이터 손실을 막고 가용성을 최대한 보장할 수 있으므로 그렇게 하기로 함
    • 로드밸런서 : 네트워크 트래픽을 분산하기 위해 로드밸런서를 사용함. 로드밸러서는 트래픽을 고르게 분산할 수 있을 뿐 아니라, 특정 웹 서버에 장애가 발생하면 자동으로 해당 서버를 우회해줌
    • 웹 서버 : 로드밸런서를 추가하고 나면 더 많은 웹 서버를 손쉽게 추가할 수 있음. 따라서 트래픽이 폭증해도 쉽게 대응이 가능함
    • 메타데이터 데이터베이스 : 데이터베이스를 파일 저장 서버에서 분리하여 SPOF를 회피함. 아울러 다중화 및 샤딩 정책을 적용하여 가용성과 규모 확장성 요구사항에 대응함
    • 파일 저장소 : S3를 파일 저장소로 사용하고 가용성과 데이터 무손실을 보장하기 위해 두 개 이상의 지역에 데이터를 다중화함
  • 개략적 설계안
    • 사용자 단말 : 사용자가 이용하는 웹브라우저나 모바일 앱 등의 클라이언트
    • 블록 저장소 서버(block server) : 파일 블록을 클라우드 저장소에 업로드하는 서버
    • 클라우드 저장소 : 파일은 ㅍ블록 단위로 나눠져 클라우드 저장소에 보관됨
    • 아카이빙 저장소 : 오랫동안 사용되지 않은 비활성 데이터를 저장하기 위한 컴퓨터 시스템
    • 로드밸런서 : 요청을 모든 API 서버에 고르게 분산하는 구실을 함
    • API 서버 : 파일 업로드 외에 거의 모든 것을 담당하는 서버
    • 메타데이터 데이터베이스 : 사용자, 파일, 블록, 버전 등의 메타데이터 정보를 관리함
    • 메타데이터 캐시 : 성능을 높이기 위해 자주 쓰이는 메타데이터는 캐시함
    • 알림 서비스 : 특정 이벤트가 발생했음을 클라이언트에게 알리는데 쓰이는 발생/구독 프로토콜 기반 시스템
    • 오프라인 사용자 백업 큐
• 상세 설계
  • 블록 저장소 서버
    • 정기적으로 갱신되는 큰 파일들은 업데이트가 일어날 때마다 전체 파일을 서버로 보내면 네트워크 대역폭을 많이 잡아먹게 됨. 최적화 하는 방법
      • 델타 동기화 : 파일이 수정되면 전체 파일 대신 수정이 일어난 블록만 동기화하는 것
      • 압축 : 블록 단위로 압축해 두면 데이터 크기를 많이 줄일 수 있음. 이때 압축 알고리즘은 파일 유형에 따라 정함. 예를 들어 텍스트 파일을 압축할 때는 gzip이나 bzip2를 쓰고, 이미지나 비디오를 압축할 때는 다른 압축 알고리즘을 씀
  • 높은 일관성 요구사항
    • 메모리 캐시는 보통 최종 일관성(eventual consistency) 모델을 지원함. 강한 일관성을 달성하려면 다음 사항을 보장해야 함
      • 캐시에 보관된 사본과 데이터베이스에 있는 원본이 일치함
      • 데이터베이스에 보관된 원본에 변경이 발생하면 캐시에 있는 사본을 무효화함
    • 관계형 데이터베이스는 ACID를 보장하므로 강한 일관성을 보장하기 쉬움. 하지만 NoSQL 데이터베이스는 이를 기본으로 지원하지 않으므로, 동기화 로직 안에 프로그램해 넣어야 함
  • 알림 서비스
    • 파일의 일관성을 유지하기 위해, 클라이언트는 로컬에서 파일이 수정되었음을 감지하는 순간 다른 클라이언트에 그 사실을 알려서 충돌 가능성을 줄여야 함
    • 롱 폴링(long polling) : 드롭박스가 이 방식을 채택하고 있음
    • 웹소켓(WebSocket) : 클라이언트와 서버 사이에 지속적인 통신 채널을 제공함. 따라서 양방향 통신이 가능함
      • 웹소켓은 실시간 양방향 통신이 요구되는 채팅 같은 응용에 적합함
  • 저장소 공간 절약
    • 파일 갱신 이력을 보존하고 안정성을 보장하기 위해서는 파일의 여러 버전을 여러 데이터센터에 보관할 필요가 있음. 그런 상황에서 모든 버전을 자주 백업하게 되면 저장용량이 너무 빨리 소진될 가능성이 있음. 이런 문제를 피하고 비용을 절감하기 위해서는 보통 세 가지 방법을 사용함
      • 중복 제거(de-dupe) : 중복된 파일 블록을 계정 차원에서 제거하는 방법. 두 블록이 같은 블록인지는 해시 값을 비교하여 판단함
      • 지능적 백업 전략을 도입함
        • 한도 설정 : 보관해야 하는 파일 버전 개수에 상한을 두는 것
        • 중요한 버전만 보관 : 어떤 파일은 아주 자주 바뀜
      • 자주 쓰이지 않는 데이터는 아카이빙 저장소(cold storage)로 옮김
  • 장애 처리
    • 장애는 대규모 시스템이라면 피할 수 없는 것으로, 설계 시 그 점을 반드시 고려해야 함. 면접관이 관심 있어 할 만한 부류의 장애
      • 로드밸런서 장애 : 로드밸런서에 장애가 발생한 경우 부(secondary) 로드밸런서가 활성화되어 트래픽을 이어받아야 함. 로드 밸런서끼리는 보통 박동 신호를 주기적으로 보내서 상태를 모니터링함. 일정 시간 동안 박동 신호에 응답하지 않은 로드밸런서는 장애가 발생한 것으로 간주함
      • 블록 저장소 서버 장애 : 블록 저장소 서버에 장애가 발생하였다면 다른 서버가 미완료 상태 또는 대기 상태인 작업을 이어받아야 함
      • 클라우드 저장소 장애 : S3 버킷은 여러 지역에 다중화할 수 있으므로, 한 지역에서 장애가 발생하였다면 다른 지역에서 파일을 가져오면 됨
      • API 서버 장애 : API 서버들은 무상태 서버. 따라서 로드밸런서는 API 서버에 장애가 발생하면 트래픽을 해당 서버로 보내지 않음으로써 장애 서버를 격리할 것
      • 메타데이터 캐시 장애 : 메타데이터 캐시 서버도 다중화함. 따라서 한 노드에 장애가 생겨도 다른 노드에서 데이터를 가져올 수 있음. 장애가 발생한 서버는 새 서버로 교체하면 됨
      • 메타데이터 데이터베이스 장애
        • 주 데이터베이스 서버 장애 : 부 데이터베이스 서버 가운데 하나를 주 데이터베이스 서버로 바꾸고, 부 데이터베이스 서버를 새로 하나 추가함
        • 부 데이터베이스 서버 장애 : 다른 부 데이터베이스 서버가 읽기 연산을 처리하도록 하고 그동안 장애 서버는 새 것으로 교체함
      • 알림 서비스 장애 : 접속 중인 모든 사용자는 알림 서버와 롱 폴링 연결을 하나씩 유지함
      • 오프라인 사용자 백업 큐 장애" 이 큐 또한 다중화해 두어야 함. 큐에 장애가 발생하면 구독 중인 클라이언트들은 백업 큐로 구독 관계를 재설정해야 할 것

배움은 계속된다

• 회사별 엔지니어링 블로그
  • 구글
  • 그루폰
  • 깃허브
  • 넥스트도어
  • 넷플릭스
  • 도커
  • 드롭박스
  • 레딧
  • 링크드인
  • 믹스패널
  • 비트토렌트
  • 사운드클라우드
  • 섬텍
  • 세일즈포스
  • 쇼피파이
  • 슬랙
  • 스트라이프
  • 스포티파이
  • 아마존
  • 아사나
  • 아틀라시안
  • 야후
  • 에어비앤비
  • 우버
  • 옐프
  • 이베이
  • 인스타그램
  • 인스타카트
  • 줌
  • 큐오라
  • 클라우데라
  • 트위터
  • 페이스북
  • 페이팔
  • 핀터레스트
  • 하이스케일러빌리티