🐹 12. System design & Scalability

09. 시스템 설계 및 규모 확장성

[ 문제를 다루는 방법 ]

• 소통하라

  : 시스템 설계 문제를 출제하는 가장 큰 목적은 의사소통 능력을 평가하기 위함이다. 면접관과 끊임없이 의사소통하라. 면접관에게 질문을 던지고, 시스템에 발생할 수 있는 문제점을 열린 마음으로 받아들이라.

• 처음에는 포괄적으로 접근하라

  : 알고리즘으로 바로 뛰어들지 말고 특정 부분을 과도하게 파고들지 말라

• 화이트보드를 사용하라

  : 화이트보드는 우리가 제안하는 설계를 면접관이 이해하게끔 도움을 준다. 문제를 받자마자 화이트보드에 우리가 제안하는 그림을 그리며 설명하라.

• 면접관이 우려하는 부분을 인정하라

  : 면접관은 아마도 우려되는 부분을 파고들려 할 것이다. 그것을 무시하지 말라. 면접관의 우려를 인정해라. 면접관이 짚은 문제점을 인정하고 적절하게 수정하라.

• 가정을 할 때 주의하라

  : 잘못된 가정은 문제를 완전히 다르게 바꿔 버릴 수 있다. 일례로 데이터 통계/분석 결과를 만드는 시스템이 있을 때, 이 시스템의 분석 결과가 언제나 최신 결과를 나타내야 하는지 아닌지에 따라 큰 차이가 있다.

• 여러분이 생각하는 가정을 명확히 언급하라

  : 가정을 할 때 그것을 면접관에게 알려 줘야 한다. 그래야 실수했을 때 면접관이 바로잡아 줄 수 있고, 적어도 현재 어떤 가정을 하고 있는지 면접관이 알 수 있다.

• 필요하다면 어림잡아 보라

  : 많은 경우에 우리가 필요한 데이터가 없을 수 있다. 예를 들어, 웹 크롤러(web crawler)를 설계한다고 할 때, 모든 URL을 저장하는 데 필요한 공간이 얼마나 되는지 어림잡아 볼 필요가 있다. 우리가 알고 있는 다른 데이터를 이용해서 이 크기를 어림잡아 볼 수 있다.

• 뛰어들라

  : 지원자로서 문제를 책임져야 한다. 그렇다고 조용히 있으면 안 된다. 반드시 면접관과 이야기를 해야 한다. 하지만 그와 동시에 문제도 풀어내야 한다. 장단점을 열린 마음으로 받아들여라. 계속해서 깊이 파고들어라. 계속해서 향상시켜 나가라.

이런 문제들은 최고의 설계를 해내는 것보다 대게 그 과정을 중요하게 본다.

[ 시스템 설계: 단계별 접근법 ]

실제 설계에 들어가기 전에 많은 질문이 있는 것처럼 면접에서도 이런 방식으로 문제에 접근해야 한다.

1단계: 문제의 범위를 한정하라

만들고자 하는 시스템과 면접관이 원하는 것이 같은지 확실히 할 수 있다는 점에서 문제의 범위를 한정하는 작업은 중요하다.

TinyURL 설계 문제를 풀어야 할 때, 정확히 무엇을 구현해야 하는지 알고 싶을 것이다.

• 개개인이 원하는 대로 축약된 URL을 만들 수 있는가?
• 축약된 URL이 항상 자동으로 생성되는가?
• 클릭에 관한 통계 정보를 기록할 필요가 있는가?
• 한 번 설정된 URL은 영원히 없어지지 않는가, 아니면 일정 시간이 지나면 삭제되는가?

이 질문들은 시스템 설계에 앞서 반드시 짚고 넘어가야 할 것들이다.

주요한 특징이나 사용되는 사례를 나열해보자. 예를 들어 TinyURL은 아마도 다음과 같은 특징이 있을 것이다.

• URL을 TinyURL로 축약
• URL을 분석
• TinyURL과 연결된 URL을 검색
• 사용자 계정 및 링크 관리

2단계: 합리적인 가정을 만들라

필요하다면 가정을 세우는 것도 괜찮지만, 합당해야 한다. 예를 들어, 시스템이 하루에 100명의 사용자를 처리할 수만 있으면 된다거나, 메모리에 제약이 없다거나 하는 가정은 합당하지 않다.

하지만 하루에 최대 백만 개의 URL을 생성하는 시스템을 가정하는 것은 합당하다. 이런 가정을 통해 얼마나 많은 데이터를 저장해야 하는지 계산해볼 수 있다.

어떤 가정을 세우려면 ‘제품에 대한 감’이 있어야 할 수도 있다

예를 들어, 최근 데이터에 비해 최대 10분 정도 오차가 있어도 괜찮은가? 이런 건 상황에 따라 다르다. 방금 추가한 URL이 제대로 동작하기까지 10분이 걸린다면 그 제품은 아무도 사용하지 않을 것이다. 사람들은 대부분 URL을 추가한 뒤 곧바로 사용하기를 원한다. 그렇지만, 통계적으로 봤을 때 데이터가 10분 정도 오래된 건 괜찮다.

3단계: 중요한 부분을 먼저 그리라

시스템의 주요한 부분을 다이어그램으로 그리라. 예를 들어 여러 개의 프론트엔드 서버가 백엔드에서 데이터를 받아 오는 시스템일 수도 있고, 한 서버군은 인터넷에서 데이터를 긁어 오고 다른 서버군은 이 데이터를 분석하는 작업을 하는 시스템일 수도 있다. 그 시스템이 어떻게 생겼는지 그림으로 그리라.

시스템의 처음부터 마지막까지 어떻게 동작하는지 그 흐름을 보여라. 사용자가 새로운 URL을 입력했다면 그 다음에는 어떻게 되겠는가?

현재 단계에선 규모 확장성 문제를 무시해도 된다. 그냥 단순하고 명백하게 동작한다고 접근해도 괜찮다.

4단계: 핵심 문제점을 찾아라

마음속에서 기본적인 설계를 마친 뒤에는 발생할 수 있는 핵심 문제에 집중해야 한다. 어느 부분이 병목지점일까? 이 시스템이 풀어야 할 주된 문제는 무엇인가?

ex) TinyURL 설계

어떤 URL은 드물게 사용되는 반면 특정 URL의 사용량이 갑자기 치솟는 경우가 있다. 이럴 때 시스템이 끊김없이 데이터베이스를 읽어오길 원하지는 않을 것이다.

이 부분에서 아마도 면접관이 어느 정도 가이드를 해줄 것이다. 그럴 땐 그 조언을 받아들이고 시스템에 적용하라

5단계: 핵심 문제점을 해결할 수 있도록 다시 설계하라

핵심 문제에 맞도록 설계를 수정해야 한다.

시스템 전체를 갈아 엎거나, 몇 가지 자잘한 부분만 수정(캐시 사용) 해결할 수 있다. 본인이 생각하고 있는 제약사항들을 면접관과 이야기하는 것 또한 중요하다.

[ 규모 확장을 위한 알고리즘: 단계별 접근법 ]

단순히 시스템의 한 부분 혹은 알고리즘을 설계해 보라는 요청을 받을 수도 있는데, 반드시 규모 확장성을 신경 써야 한다.

1단계: 질문하라

문제를 제대로 이해했는지 확인하기 위해 질문해야 한다. 면접관이 언급하지 않은 세부사항이 있을 수 있다.

2단계: 현실적 제약을 무시하라

메모리 제약이 없고, 컴퓨터 한 대에서 모든 데이터를 다 처리할 수 있다 가정했을 때 이에 대한 대답이 실제 정답에 대한 윤곽을 그리는 데 도움이 될 것이다.

3단계: 현실로 돌아오라

원래 문제로 돌아와 컴퓨터 한 대에 저장할 수 있는 데이터의 크기는 얼마나 되는지, 데이터를 여러 조각으로 쪼갰을 때 어떤 문제가 발생할지 생각해 봐라.

여기서 발생할 수 있는 흔한 문제는

• 어떤 논리로 데이터를 나눌 것인가
• 특정 컴퓨터가 어느 데이터 조각을 사용했는지 어떻게 알 수 있을 것인가

등이 있다.

4단계: 문제를 풀어라

발견한 문제점을 어떻게 해결할 지 생각해 봐야 한다. 상황에 따라 문제점 자체를 완전히 해결할 수도 있고, 그 수준을 완화시키는 데 그칠 수도 있다.

순환적 접근법(iterative approach)이 일반적으로 유용한 접근법이다. 3단계에서 어떤 문제를 해결하면 또 다른 문제가 발생하고, 그러면 그 문제를 다시 해결해 나가고 이를 반복하는 작업을 뜻한다.

문제를 분석하고 풀 수 있는 능력을 입증하려는 목적이다. 답안에서 새로운 문제점을 만들어 내는 방법이 그 능력을 입증할 수 있는 굉장히 좋은 방법이다.

[ 시스템 설계의 핵심 개념 ]

수평적(horizontal) vs 수직적(vertical) 규모 확장

• 수직적 규모 확장(vertical scaling)

  : 특정 노드의 자원(resource)의 양을 늘리는 방법.

  ex) 서버에 메모리를 추가하여 서버의 처리 능력을 향상시킴

• 수직적 규모 확장(horizontal scaling)

  : 노드의 개수를 늘리는 방법

  ex) 서버를 추가함으로써 서버 한 대가 다뤄야 하는 부하(load)를 줄일 수 있음

수직적 규모 확장이 일반적으로 수평적 규모 확장보다 쉽지만, 메모리 혹은 디스크와 같은 것만 추가할 수 있으므로 제한적이다.

서버 부하 분산 장치(load balancer)

일반적으로 규모 확장성이 있는 웹사이트의 프론트엔드 부분은 서버 부하 분산 장치(load balancer)를 통해 제공된다.

서버에 걸리는 부하를 여러 대의 서버에 균일하게 분산시킬 수 있고 서버 한 대 때문에 전체 시스템이 죽거나 다운되는 상황을 방지할 수 있다.

이렇게 하기 위해선 서버 여러 대가 근본적으로 똑같은 코드와 데이터를 사용하도록 하는 네트워크를 구현해놔야 한다.

데이터베이스 역정규화(denormalization)와 NoSQL

조인 연산은 시스템이 커질수록 굉장히 느려진다.

역정규화(denormalization)

데이터베이스에서 여분의 정보를 추가해서 읽기 연산 속도를 향상시킨 것

ex) 한 프로젝트가 여러 과제를 수행하도록 설계된 데이터베이스

프로젝트 이름과 과제 정보를 함께 알고 싶은 경우에 두 테이블을 조인하기보단 애초에 과제 테이블에 프로젝트 이름 정보를 추가로 저장해 놓으면 더 빠르게 작업을 수행할 수 있다.

NoSQL

조인 연산 자체를 지원하지 않는다. 따라서 자료를 조금 다른 방식으로 구성해 놓는데, 이 방식이 규모 확장성에 좋도록 설계되어 있다.

[ 데이터베이스 분할(샤딩) ]

샤딩(sharding)

데이터를 여러 컴퓨터에 나눠 저장하는 동시에 어떤 데이터가 어떤 컴퓨터에 저장되어 있는지 알 수 있는 방식

• 수직적 분할(vertical partitioning)

  : 자료의 특성별로 분할하는 방식

  ex) 소셜 네트워크를 만들 때, 개인 정보와 관련된 혹은 메시지와 관련된 부분과 같이 그 특성에 따라 자료 분할

  • 단점

    특정 테이블의 크기가 일정 수준 이상으로 커지면, (다른 방식을 사용해서) 데이터베이스를 재분할해야 할 수도 있다

• 키 혹은 해시 기반 분할

  : mod(key, n)의 값을 이용해서 N개의 서버에 분할 저장

  • 문제점

    서버의 개수가 고정되어 있어야 한다. 서버를 새로 추가할 때마다 모든 데이터를 다시 재분배 해야하는데, 굉장히 비용이 큰 작업이다.

• 디렉터리 기반 분할

  데이터를 찾을 때 사용되는 조회 테이블을 유지하는 방법

  • 장점

    서버를 추가하기 쉽다

  • 단점
    • 조회 테이블이 단일 장애 지점이 될 수 있음
    • 지속적으로 테이블을 읽는 행위가 전체 성능에 영향을 미칠 수 있음

캐싱(caching)

인메모리(in-memory) 캐시를 사용하면 결과를 굉장히 빠르게 가져올 수 있다.

인메모리 캐시

키-값(key-value)을 쌍으로 갖는 간단한 구조로 일반적으로 애플리케이션과 데이터 저장소 사이에 자리잡고 있다.

1. 애플리케이션이 자료를 요청하면 캐시 먼저 확인
2. 캐시가 해당 키 값을 갖고 있지 않으면 그때 데이터 저장소 살핌

캐시할 때

• 쿼리와 그 결과를 캐싱
• 특정 객체를 캐시에 저장

ex) 웹 페이지의 어떤 부분을 렌더링한 결과나 혹은 블로그에 올라온 최근 포스팅 리스트

비동기식 처리 & 큐

속도가 느린 연산은 비동기식(asynchronous)로 처리해야 한다. 그렇지 않으면 해당 연산이 끝나기까지 하염없이 기다려야 할 수도 있기 때문이다.

어떤 경우에는 이 연산을 미리 해 놓을 수도 있다.

ex) 곧 갱신해야 할 웹사이트의 각 부분들이 큐에 들어있다.

이 웹사이트가 어떤 포럼이라고 했을 때, 큐에 들어 있는 작업 중 하나는 아마도 가장 최근의 글들과 몇 가지 코멘트를 보여 주는 페이지를 다시 만들어 주는 일이다. 이 경우 최근 글 리스트가 약간 오래되어 덜 정확하더라도 괜찮다.

→ 새로운 코멘트 하나 때문에 캐시 미스(cache miss)가 나고, 그래서 웹사이트를 새로 불러오느라 속도가 느려지는 것보다는 결과가 덜 정확한 것이 낫다.

네트워크 성능 척도

네트워크의 성능을 측정할 때 사용되는 몇 가지 중요한 척도(metric)은 다음과 같다.

• 대역폭(bandwidth)

  : 단위 시간에 전송할 수 있는 데이터의 최대치

  • 보통 초당 몇 비트(bit)를 보낼 수 있는지로 계산
  • 혹은 초당 몇 기가바이트(gigabyte)를 보낼 수 있는지로 계산

• 처리량(throughput)

  : 단위 시간에 실제로 전송된 데이터의 양

• 지연속도(latency)

  : 데이터를 전송하는 데 걸리는 시간

  즉, 발송자(sender)가 데이터를 보낸 시점부터 수신자(receiver)가 데이터를 받는 시점까지 걸린 시간

ex) 공장의 컨베이어 벨트 물품 이동

→ 지연속도: 물품 하나가 한 지점에서 다른 지점까지 옮겨지는 데 걸린 시간

→ 처리량: 단위 시간에 옮겨진 물품의 개수

• 컨베이어 벨트의 폭을 넓힌다고 지연 속도가 달라지지 않는다. 하지만 처리량과 대역폭을 바꾼다면 달라질 수 있다.

  → 더 많은 물품을 벨트 위에 올려놓으면 주어진 단위 시간에 더 많은 물품을 처리할 것이다.

• 벨트의 길이를 줄이면 지연 속도 또한 줄어들 것이다. 하지만 대역폭이나 처리량이 달라지지 않는다.

• 컨베이어 벨트의 속도를 빠르게 만들면 세 가지 척도 모두 바꿀 수 있다.

  공장에서 물품 옮기는 속도가 줄어들 것이고, 단위 시간에 옮길 수 있는 물품의 개수 또한 늘어날 것이다.

• 대역폭 = 최상의 조건에서 단위 시간에 전송할 수 있는 물품의 개수

  처리량 = 실제 상황에서(기계가 잘 동작 안하는 경우에도) 단위 시간에 전송된 물품의 개수

지연시간은 무시되기 쉽지만 특정 상황에선 굉장히 중요한 역할을 한다

ex) 온라인 게임

온라인 스포츠 게임을 하고 있을 때 상대방의 움직임을 바로바로 볼 수 없다면 게임을 어떻게 진행할 수 있겠는가?

처리량은 압축 등의 방법으로 어떻게든 향상시킬 수 있지만, 지연 시간을 단축시키기 위해 할 수 있는 일은 일반적으로 많지 않다.

MapReduce

→ 구글과 관련 있는데, 현재는 구글에 국한되지 않고 널리 사용되고 있다.

MapReduce 프로그램은 보통 굉장히 커다란 데이터를 처리하는 데 사용된다.

맵(Map) 단계와 리듀스(Reduce) 단계를 구현해야 한다. 나머지 부분은 시스템이 알아서 처리할 것이다.

• Map은 데이터를 입력으로 받은 뒤 <key, value>쌍을 반환한다.
• Reduce는 키(key), 그리고 키와 관련된 값(value)들을 입력으로 받은 뒤 나름의 처리 과정을 거친 후 새로운 키와 값을 반환한다. 경우에 따라 이 결과를 또 다른 Reduce 프로그램에 넘길 수도 있다.

MapReduce는 많은 과정을 병렬로 처리할 수 있게 도와주기 때문에 굉장히 커다란 데이터에 대해서도 규모 확장이 쉬워진다.

[ 시스템 설계 시 고려할 점 ]

• 실패(Failures)

  : 시스템의 어떤 부분이든 실패 가능성이 존재한다. 따라서 각 부분이 실패했을 때를 대비한 대비책을 준비해야 한다.

• 가용성(availability) 및 신뢰성(relliability)

  : 가용성 - 사용 가능한 시스템의 시간을 백분율로 나타낸 것 신뢰성 - 특정 단위 시간에 시스템이 사용 가능할 확률

• 읽기 중심 vs 쓰기 중심

  : 읽는 연산이 많은지 아니면 쓰는 연산이 많은지에 따라 설계 방식이 달라질 수 있다. → 쓰는 연산이 많다면 큐를 사용하는 방법 생각 → 읽는 연산이 많다면 캐시를 사용하는 방법 생각

• 보안(security)

  : 보안 위협은 시스템에 엄청난 해를 가할 수 있다. 해당 시스템이 직면할 수 있는 문제점에 대해 생각해보고 그를 해결하기 위해 어떻게 시스템을 설계할지 생각해야 한다.

[ ‘완벽한’ 시스템은 없다 ]

TinyURL, 구글 맵스, 다른 어떤 시스템에 대해서도 완벽하게 동작하는 시스템 설계는 존재하지 않는다. 모든 시스템에 장단점이 존재한다.

이러한 문제를 받았을 때

• 사례를 잘 이해하고
• 문제의 범위를 설정하고
• 합리적인 가정을 세운 뒤

명확하게 설계한 시스템을 만드는 것이다.

[ 연습 문제 ]

수백만 개의 문서가 주어졌을 때, 특정 단어 리스트가 포함된 문서를 찾으려고 한다.

단어가 등장하는 순서는 중요하지 않지만, 해당 단어가 완벽하게 나타나야 한다. 즉, “bookkeeper”라는 단어에 “book”이라는 단어가 포함되긴 하지만 해당 문서가 “book”의 검색 결과로 나타나서는 안된다.

문제를 풀기 전 문서를 찾는 행위를 한 번만 할 것인지 findWords를 반복적으로 호출할 것인지 알고 있어야 한다. 여기서는 findWords를 같은 문서 집합에 대해 여러 번 호출한다고 가정하자. 따라서 약간의 전처리 과정이 들어가도 괜찮다.

1단계

우선 문서가 겨우 수십 개 있을 때를 가정한다.

이럴 경우에 findWords를 어떻게 구현할 것인가?

한 가지 방법은 전처리 과정을 통해 모든 문서에 대한 해시테이블을 만드는 것이다. 해시테이블은 단어와 해당 단어를 포함하는 문서 리스트에 대한 정보를 담고 있다.

"books" -> {doc2, doc3, doc6, doc8}
"many" -> {doc1, doc3, doc7, doc8, doc9}

“many books”를 탐색하려면, 단순히 “books”와 “many”의 교집합을 구하면 된다. 그러면 [doc3, doc8]을 구할 수 있다.

2단계

문서의 개수가 수백만 개로 늘어나면 어떻게 해야 할까?

문서를 여러 대의 컴퓨터로 나눠서 보내야 할 것이다. 또한 여러 가지 다른 요인(단어의 수나 출현 빈도 등) 때문에 해시테이블조차도 한 컴퓨터에 온전히 보관할 수 없을 수 있다. 실제로 해시테이블도 분할해서 저장해야 하는 상황이 벌어졌다고 가정해보자.

데이터를 나누려면, 다음과 같은 사항들을 고민해야 한다.

1. 해시테이블은 어떻게 분할할 것인가? 키워드에 따라 나눌 수 있다. 이때, 어떤 단어에 대한 문서 목록은 컴퓨터 한 대에 온전히 저장될 것이다. 혹은 문서에 따라 나눌 수도 있다. 즉, 전체 문서 집합 가운데 특정한 부분집합에 대한 해시테이블만 한 컴퓨터에 두는 것이다.
2. 데이터를 분할하기로 결정하면, 어떤 컴퓨터에서는 문서를 처리하고 그 처리 결과를 다른 컴퓨터로 옮겨야 할 수 있다. 이 과정은 어떻게 정의할 수 있을까? 해시테이블을 문서에 따라 나누기로 했다면 이 과정이 불필요할 수도 있다는 점에 유의한다.
3. 어떤 컴퓨터에 어떤 데이터가 보관되어 있는지 알 수 있어야 한다. 이 조회 테이블의 형태는? 조회 테이블은 어디 두어야 하겠는가?

여기서는 세 가지 사항만 언급했지만, 이보다 더 많을 수도 있다.

3단계

이제 각 문제점들에 대한 해법을 찾아야 한다.

한 가지 방법은 키워드를 알파벳 순서에 따라 분할하는 것이다. 즉, 한 컴퓨터가 특정한 범위의 단어들만(가령 ‘after’부터 ‘apple’까지) 통제하게 하는 것이다.

키워드를 알파벳 순서로 돌면서 가능한 데이터를 저장하는 알고리즘은 쉽게 구현할 수 있다. 용량이 꽉 차면, 다른 컴퓨터로 옮겨 가야 한다.

• 장점
  • 조회 테이블을 작고 단순하게 만들 수 있다.(값의 범위만 명시하면 되기 때문)
  • 각 컴퓨터에 조회 테이블의 복사본을 저장할 수 있다.
• 단점
  • 새로운 문서나 단어가 추가되면 키워드를 굉장히 많이 이동시켜야 할 수도 있다.

특정한 문자열 집합을 포함하는 모든 문서를 찾기 위해 우선 해당 문자열의 리스트를 정렬한 다음 각 컴퓨터에 그중 일부에 해당하는 문자열들을 찾으라는 요청을 보내면 된다. 가령 문자열 리스트가 “after builds boat amaze banana”와 같이 주어졌다면, 첫 번째 컴퓨터에는 {”after”, “amaze”}에 대한 요청을 보내는 것이다.

첫 번째 컴퓨터는 “after”와 “amaze”를 포함하는 문서들의 교집합을 구하여 반환한다. 세 번째 컴퓨터는 {”banana”, “boat”, “builds”}에 대해 같은 작업을 수행한다.

마지막으로, 초반에 전체 요청을 보냈던 컴퓨터는 첫 번째와 세 번째 컴퓨터로부터 받은 결과의 교집합을 구한다.

이 절차를 다이어그램으로 그려보면 다음과 같다.