좋은 해법과 나쁜 해법은 있지만 완벽한 해법은 없다.

시스템 설계 류의 문제는 실제 세계에서 어떻게 행동할지 보기 위해 고안된 문제로,

실제 일을 하듯이 면접관에게 질문하고 장단점을 토론하면 된다.

면접자가 할 일은 기업이 수 억 들여 만든 복잡한 시스템을 재설계 하는 것이 아니다.

문제를 분석하고 풀 수 있는 능력을 입증하려는 목적이 크다.

• 면접자의 의사소통 능력을 평가하기 위한 문제이므로, 면접관과 끊임없이 소통해야 한다.
• 처음에는 포괄적으로 접근한다.
• 화이트보드를 사용해 면접관이 잘 이해할 수 있도록 그림을 그리며 설명한다.
• 면접관이 우려하는 부분을 인정하고 적절하게 수정한다.
• 가정을 할 때는 명확히 언급한다. 잘못된 가정은 문제를 완전히 다르게 바꿔버리는데, 명확히 밝혀두면 실수를 했을 때 면접관이 바로잡아 줄 수 있다.
• 정확히 가정할 수 없다면 이미 알고 있는 수치를 기준으로 어림잡아 본다.

내가 만들려는 시스템이 면접관이 원하는 것인지 알아보는 단계이다.

예를들어 TinyURL을 만든다면 아래와 같은 것을 알아야 하겠다.

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

또한, 아래와 같은 기능을 만들어야 하겠다.

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

적절한 제약을 가정해 문제를 풀어야 한다.

• 하루에 100개의 URL만 처리하면 된다 / 하루에 최대 백만 개의 URL을 생성한다
• 최근 데이터에 비해 10분 오차가 있어도 된다 / 방금 추가한 URL은 곧바로 사용할 수 있어야 한다

아래와 같이 시스템 뼈대를 그려보는 단계다.

• 여러 개의 프론트엔드 서버가 백엔드에서 데이터를 받아오는 시스템
• 한 서버군은 인터넷에서 데이터를 긁어오고 다른 서버군은 이 데이터를 분석하는 작업하는 시스템

병목 지점 등 시스템이 풀어야 할 주된 문제를 찾는다.

• 어떤 URL은 드물게 사용되는 반면 특정 URL의 사용량이 갑자기 치솟는 경우

면접관이 언급하지 않은 세부사항이 있는지 문제를 정확히 이해한 것이 맞는지

면접관과 질답하며 문제를 구체화한다.

그 다음 메모리 제약도, 처리능력 제약도 없는 상태에서 시스템 뼈대를 설계한다.

• 컴퓨터 한 대에 저장할 수 있는 데이터의 크기

• 데이터를 여러 조각으로 쪼갰을 때 어떤 문제가 발생할 것인지

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

시스템 설계 문제는 면접자가 무엇을 알고 있는지 확인하는 문제는 아니다.

다만, 특정 개념을 알고 있다면 더 쉽게 풀 수 있다.

이하 모든 개념들은 깊이 있고 복잡한 문제이므로 추가 학습이 필요하다.

• 수직적 규모확장(vertical scaling) : 특정 노드의 자원의 양을 늘리는 방법이다. 서버에 메모리를 추가해 처리능력을 키울 수 있다.

• 수평적 규모확장(horizontal scaling) : 노드의 개수를 방법이다. 서버를 추가함으로써 서버 한 대가 다루는 부하를 줄일 수 있다.

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

SQL과 같은 관계형 데이터베이스의 조인 연산은 시스템이 커질수록 굉장히 느려지므로, 필요에 따라 데이터베이스를 합쳐 역정규화할 수 있다.

• 역정규화: 데이터베이스 테이블에 여분의 정보를 추가해서 읽기 연산 속도를 향상
• 정규화: 데이터베이스 테이블간 중복된 데이터를 허용하지 않으므로써 무결성을 유지하고 저장용량을 줄임

NoSQL 같은 비정형 데이터베이스는(redis, mongoDB 등) 조인 연산 자체를 지원하지 않는다. 유연한 규모 확장에 좋도록 설계되어 있다.

NoSQL 데이타 모델링 #1-데이타모델과, 모델링 절차 (tistory.com)

NoSQL 데이타 모델링 #2- 데이타 모델링 패턴 (tistory.com)

샤딩은 데이터를 어떻게 나누어 저장할지, 어떤 데이터가 어디에 저장되어 있는지 알 수 있는 방식이다.

• 수직적 분할: 자료의 특성별로 분할
  • 소셜 네트워크를 만들 때 개인정보/메시지 관련부분 등 특성에 따라 자료를 분할
  • 특정 테이블의 크기가 일정 수준 이상으로 커지면 데이터베이스를 재분할해야 할 수도 있음
• 키 혹은 캐시 기반 분할
  • mod(key, n)의 값을 이용해 N개의 서버에 분할
  • 서버의 개수가 고정되어 있어 서버를 추가할 때마다 모든 데이터를 재분배해야 함
• 디렉터리 기반 분할: 데이터를 찾을 때 사용되는 조회 테이블을 유지
  • 상대적으로 서버를 추가하기 쉬움
  • 조회 테이블이 병목지점이 될 수 있다
  • 지속적으로 테이블을 읽는 행위가 전체 성능에 영향을 미칠 수 있음

인메모리 캐시를 사용하면 결과를 빠르게 가져올 수 있다.

• 이상적이라면, 속도가 느린 작업은 비동기식으로 처리해야 한다.

  • 작업 소요시간을 미리 보여주고 끝나면 사용자에게 알려줄 수도 있다.

• 경우에 따라 동기 작업으로 속도가 느려지는 대신 덜 정확하게 처리해도 될 수 있다.

  • 어떤 포럼에 글과 댓글이 새로 달렸다고해서, 웹페이지를 매번 새로 불러오는 것은 비효율적이다.

애플리케이션의 특성에 따라, 이를테면 게임은 지연속도가 대용량 데이터의 전송은 처리량이 중요하겠다.

• 대역폭(bandwidth): 단위 시간에 전송할 수 있는 데이터의 최대치.
• 처리량(throughput): 단위 시간에 실제로 전송된 데이터의 양.
• 지연속도(latency): 데이터를 전송하는 데 걸리는 시간.

매우 큰 데이터를 처리하는 데 사용. 많은 과정을 병렬로 처리할 수 있게 도와줌.

• Map은 데이터를 입력받아 <key, value> 쌍을 반환
• Reduce는 키, 값을 입력으로 받은 뒤 내부 처리과정을 거쳐 새로운 키, 값을 반환. 다른 Reduce로 넘겨 이 과정을 반복할 수 있음.

• 실패: 시스템의 어떤 부분이 실패했을 때의 대비책
• 가용성과 신뢰성
  • 가용성: 사용 가능한 시스템의 시간을 백분율로 나타낸 것
  • 신뢰성: 특정 단위 시간에 시스템이 사용 가능한 확률을 나타낸 것
• 읽기중심, 쓰기중심
  • 읽기중심: 캐시 사용을 고려
  • 쓰기중심: 큐 사용을 고려
• 보안

• 수백만 개의 문서에서 특정 단어 리스트가 포함된 문서를 찾으려고 한다 → 데이터를 분할 처리
• 단어가 등장하는 순서는 중요치 않지만, 단어가 완전히 일치해야 한다 → 각 단어별 검색결과의 교집합 구하기
• 검색 연산은 여러 번 호출한다 → 시간이 오래 걸리더라도 전처리 작업 가능

1단계

문서가 수십 개라면

전처리 과정으로 모든 문서에 대한 해시테이블을 만들 수 있다.

"books" -> {doc1, 2, 3}
"many" -> {doc2, 4}

"many books"를 탐색하려면 다 집합의 교집합을 구하면 된다.

2단계

문서가 수백만 개라면

• 해시테이블을 어떻게 분할할까?
  • 키워드 단위로: a-c키워드는 서버1, d-f 키워드는 서버2 등
  • 문서 단위로: 문서1-10에 대한 키워드는 서버1, 문서5-13에 대한 키워드는 서버2 등
• 데이터를 처리해 분할하는 작업은 어떻게 처리할까?
• 데이터가 어떤 컴퓨터에 보관되어 있는지 어떻게 알 수 있을까?

3단계

• 키워드 단위로 해시테이블을 분할했을 경우
  • 조회 테이블을 작고 단순하게 만들 수 있으며, 각 컴퓨터에 조회 테이블 복사본을 저장할 수도 있음
  • 새로운 문서나 단어가 추가되면 굉장히 많이 이동시켜야 할 수도 있음
  • 여러 키워드를 입력받으면 컴퓨터별 검색결과의 교집합을 구하면 됨

• 폐장 시점 주가정보(시작가, 종가, 최고가)를 최대 1000개 클라이언트에게 제공
• 데이터는 어떤 형태로든 저장할 수 있다
• 개발과 배포, 시스템 모니터링, 사용자에게 전송되는 정보 관리를 수행해야 함

미리 고려할점

• 클라이언트/서버측 구현/유지보수가 용이해야 한다
• 상황에 맞춰 유연하게 변경할 수 있어야 한다
• 서비스에 과도한 부담이 가지 않도록 규모확장이 용이해야 한다

방안1 : 텍스트파일

텍스트 파일을 FTP서버로 배포하는 경우

• 사용, 백업, 유지보수가 용이하다

• 쿼리를 날리려면 텍스트 파일을 파싱해야 한다.

  • 새로운 칼럼이 추가되면 기존 파싱 방법이 동작하지 않을 수 있다

방안2 : SQL DB

데이터를 일반적인 SQL데이터베이스로 관리하는 경우

• 장점
  • 클라이언트에서 쿼리를 날려 여러 부가기능을 제공할 수 있다
  • 쿼리 취소, 데이터 백업, 보안 유지 등 기능이 데이터베이스 기능에 포함되어 구현이 쉽다
  • 기존 애플리케이션에 통합하기 쉽다
• 단점
  • 개발결과물이 필요 이상으로 무거워진다
  • 데이터를 조회하려면 쿼리를 작성하고 사용자가 보기쉽게 추가적으로 구현해야 한다
  • 클라이언트에게 적절한 권한을 부여하지 않으면 보안상 문제가 발생할 수 있다

방안3 : XML (JSON도 마찬가지)

• 장점
  • 사람이 보기에도, 기계가 처리하기도 쉽다
  • 대부분 프로그래밍 언어에 XML/JSON을 처리하는(파싱/백업) 라이브러리가 포함되어 있다
  • 데이터 포맷이 정해져 있으므로 새 칼럼을 추가해도 파서를 새로 구현할 필요는 없다
• 단점
  • 클라이언트가 필요한 게 자료 중 일부라고 하더라도 모든 자료를 전송한다
  • 쿼리를 수행하려면 전체 파일을 파싱해야 한다

• 페이스북이나 링크드인과 같은 대규모 소셜 네트워크를 위한 자료구조는 어떻게 설계하겠는가?

• 두 사람 사이의 최단 경로를 보여주는 알고리즘은 어떻게 설계할 것인가

단계1: 문제단순화

• 각 사용자를 노드 친구 관계를 간선으로 하는 그래프를 가정

• 두 사용자간 경로는 한 사용자부터 시작해 너비 우선 탐색

  • 깊이 우선 탐색을 하면 최단경로를 찾지 못할 수 있고, 또한 불필요하게 수백 만 개 노드를 탐색할 수 있다

• 두 사용자간 경로를 각 사용자부터 시작해 양방향 너비 우선 탐색

  • S에서 D까지 경로를 탐색할 때, 각각 K명의 친구를 가지고 있다면
  • S→D 너비우선탐색은 K+K*K 친구들을 거쳐야하나, 양방향 탐색은 K+K로 끝이난다
  • 단, 양방향 탐색은 시작지점과 도착지점에 모두 접근 가능할 때 사용할 수 있는 방법

소셜 네트워크 연습문제 구현코드(careercup/CtCI-6th-Edition)

다음은 구현코드에 대한 간략한 설명이다.

Person
데이터노드
- ArrayList<Integer> friends : 친구ID 목록
- Integer personID : 본인ID
- String info : 부가정보

PathNode
- Person person : 현재 노드
- PathNode previousNode : 이전에 방문한 노드
- LinkedList<Person> collapse(boolean startWithRoot) : 매개인자로 받은 플래그가 true면 앞에서 뒤로 탐색하는 경우이고, false면 뒤에서 앞으로 탐색하는 경우이다.

BFSData
BFS 탐색을 위한 래퍼클래스. 일반적으로 플래그 배열을 사용해서 방문여부를 표시하지만, 동시에 여러 개의 탐색이 진행될 수 있기 때문에 방문여부를 별도 객체에서 처리한다.
- Queue<PathNode> toVisit : BFS로 방문할 노드
- HashMap<Integer, PathNode> visited : BFS로 방문한 노드

테스트 코드에 대한 설명이다.

QuestionA
너비우선탐색 테스트

QuestionB
양방향 너비우선탐색 테스트
- ::mergePath : 충돌이 발생하면 양방향에서 탐색한 노드를 합친다.
- ::searchLevel : 깊이기준 한 단계씩만 들어가서 찾는 노드가 있는지 확인한다. 현재 탐색방향의 노드가 역방향 탐색에서 방문한 노드라면 해당 데이터노드를 반환한다. 충돌이 없으면 null반환.
- ::findPathBiBFS : searchLevel로 단계별로 탐색하고, 충돌이 발생하면 mergePath로 탐색한 노드를 합친다.

Tester
- ::printPeople : 데이터노드 목록을 출력
- ::isEqual : 데이터노드 목록이 동일한지 비교
- ::isEquivalent : isEqual의 오버로딩

단계2: 수백만 사용자처리

데이터노드가 아주 많아 한 서버기계에 저장할 수 없다면

적절한 논리에 따라 서버기계에 분산저장한 후, 추상화된 계층을 통해 접근할 수 있다.

이를테면 사용자ID와 서버ID가 매칭된 해시테이블을 둘 수 있겠다.

Machine 
데이터를 분산저장할 추상화된 서버기계
- HashMap<Integer, Person> persons : ID/데이터노드

Server 
데이터를 분산/처리하는 추상화된 서버
- HashMap<Integer, Machine> machines : 서버기계 목록
- HashMap<Integer, Integer> personToMachineMap : 어떤 데이터노드가 어떤 서버기계에 들어있는지

단계3: 최적화

• 다른 서버에 대한 탐색을 줄이기: 탐색해야할 친구 중 같은 서버에 있는 친구는 한 번에 조회한다.
• 연관된 데이터를 같은 서버기계에 저장하는 등 보다 나은 방법으로 사용자 정보를 분산보관한다.

더 고려할 점

• 서버가 죽는다면 알고리즘에 어떤 영향을 미칠까?
• 캐싱을 이용하려면?
• 그래프의 끝을 만날 때까지 무한히 탐색해야 할까? 탐색을 그만둘 시점은 어떻게 정할까?
• 탐색을 시작할 위치를 정할 때, A와 B를 이어줄 가능성이 높은 C노드를 어떻게 알 수 있을까?

• 크롤러가 무한루프에 빠지지 않으려면 어떻게 해야 하는가

해법

웹을 단순히 그래프라고 가정하면, 사이클이 존재하는지 확인하면 된다.

• 방문한 페이지를 해시테이블에 저장하고 방문여부를 확인하면 된다.
  • 방문여부 기준이 URL이라면 : HTTP GET으로 URL에 포함된 인자가 달라지면 완전히 다른 페이지로 갈 수 있다. 그런데 웹 애플리케이션이 인식하지 않는 인자는 URL 뒤에 붙여도 같은 페이지로 간다. URL을 페이지를 구별하는 유일한 값으로 볼 수는 없다.
  • 방문여부 기준이 페이지 내용이라면 : 해당 페이지가 무작위로 데이터를 추천해주는 페이지라면, 해당 페이지를 언제나 다른 페이지라고 볼 수는 없다.
  • 페이지간 유사성을 가늠해볼 수 있다 : 페이지 내용과 URL을 토대로, 방문한 페이지들과 충분히 유사하다면 우선순위를 낮춘다. 내용 일부와 URL을 토대로 모종의 시그니처를 생성할 수 있겠다.
    • 페이지의 특정 섹션과 URL을 토대로 시그니처를 생성
    • 데이터베이스 쿼리를 통해 해당 시그니처가 최근 탐색된 적 있는지 확인
    • 해당 시그니처를 갖는 페이지가 최근 탐색되었으면 우선순위를 낮춰 데이터베이스에 추가
    • 그렇지 않다면 해당 페이지를 탐색하고 그 페이지에 연결된 링크를 데이터베이스에 추가

• 100억 개의 URL에서 중복된 문서를 찾으려면? '중복'이란 '같은 URL'을 말한다.

단계1

• URL이 평균 100개의 문자로 구성되고 각 문자는 4바이트라고 할 때
• 100억 개의 URL은 4테라의 메모리가 필요하다

일단 모든 URL을 메모리에 저장할 수 있다고 가정해보면, 살펴본 URL에 대해 true를 반환하는 해시테이블로 충분하다.

단계2

• 디스크에 분할저장 : (해시값 % 4000) 식을 통해 1GB 4000개 파일로 분할한다. 이후 각 파일을 메모리에 올려 URL의 해시테이블을 생성하고 중복이 존재하는지 찾는다.
• 여러서버에 분할저장
  • 연산을 병렬로 처리할 수 있다
  • 서버에 장애가 발생할 경우, 서버 개수가 증가함에 따라 복잡해지는 시스템 등을 고려해야한다.

간단한 검색엔진 역할을 수행하는 웹서버가 있다.

• 100개의 컴퓨터가 검색 요청을 처리한다. 컴퓨터집단에 processSearch 메서드를 요청하면, 그중 어떤 컴퓨터가 작업을 처리한다.
• processSearch 메서드는 아주 고비용이다.
• 최근 검색 요청을 캐시에 저장하는 메커니즘을 설계하라. 또한 데이터가 바뀌었을 때 어떻게 캐시를 갱신할 것인지 반드시 설명하라.

가정

• 모든 쿼리는 최초로 호출된 서버에서 처리한다
• 캐시하고자 하는 쿼리의 수는 굉장히 크다(수백만 개)
• 서버간 호출은 상대적으로 빨리 처리한다
• 쿼리결과는 정렬된 URL리스트이며, 각 원소에는 최대 50글자 제목과 200글자 요약문이 포함된다
• 가장 인기 있는 쿼리의 경우 항상 캐시에 보관되어 있다

시스템요구사항

주요기능은 다음과 같다

• 주어진 키를 사용한 빠른 탐색
• 오래된 데이터를 버리고 새로운 데이터로 교체
• 쿼리 결과가 변경될 경우 캐시를 변경하거나 삭제

단계1: 단일시스템 캐시설계

오래된 데이터를 쉽게 제거하는 동시에 주어진 키에 대응되는 값을 효율적으로 찾는 자료구조는 무엇인가?

• 연결리스트: 오래된 데이터를 쉽게 제거할 수 있다. 리스트가 지정된 크기를 넘어가면 연결리스트의 마지막 항목을 제거하도록 구현할 수도 있다.

• 해시테이블: 데이터를 효율적으로 탐색할 수 있지만, 오래된 데이터를 간단히 제거할 수 있는 것은 아니다.

• 순서가 유지되는 해시테이블(자바의 TreeMap) : 오래된 데이터를 쉽게 제거할 수 있고 데이터도 효율적으로 탐색할 수 있다.

• 연결리스트 + 해시테이블: 해시테이블에 삽입할 노드를 별도 연결리스트로 저장해둔다.

Node
- Node prev
- Node next
- public String[] results
- public String query

Cache
- public HashMap<String, Node> map : 빠른 탐색을 위한 참조용 해시테이블 <쿼리, 노드>
- public Node head : 연결리스트의 머리
- public Node tail : 연결리스트의 꼬리
- ::moveToFront : removeFromLinkedList로 연결리스트에서 제거한 노드를 연결리스트의 맨앞으로 옮긴다.
- ::removeFromLinkedList : 주어진 노드를 연결리스트에서 제거한다.
- ::getResult : 주어진 쿼리로 해시테이블에서 검색해 결과를 반환한다. 
- ::insertResult : 주어진 쿼리와 결과값을 해시테이블에 저장한다.

단계2: 여러 서버로 확장

서버간 캐시를 어떻게 공유할 것인지가 핵심

방법1

• 각 서버별로 별도의 캐시
  • 같은 쿼리가 반복되도 서버별로 새로운 쿼리로 인식하므로 효과적이지 않음

방법2

• 각 서버에 캐시 복사본을 둔다
  • 새로운 데이터가 캐시에 추가되면 모든 서버로 보내진다
  • 캐시를 갱신할 때마다 서버간 작업을 N번 수행하며, 데이터 저장공간도 N배 더 커야한다

방법3

• 각 서버에 캐시 일부를 저장한다
  • 캐시가 서버별로 분할저장되어, 어떤 서버에 어떤 캐시가 있는지 찾아야 한다
  • hash(query) % N을 사용해서 쿼리를 배정할 수 있다

단계3: 내용이 변경되면 결과를 갱신

언제 쿼리결과가 바뀌는지 살펴보자.

• URL이 가리키는 페이지 내용이 바뀌거나 삭제되었을 때
• 페이지의 랭킹이 바뀌어 결과의 순서가 변경될 때
  • 내용/랭킹 데이터를 추가로 저장/처리해야 한다
  • 주기적으로 탐색해서 갱신하는 방식이 있다
• 특정한 쿼리에 관련있는 새로운 페이지가 등장할 때
  • 특정 쿼리에 대하여 탐색해서 갱신하는 방식이 있다
  • 그러나 최선은 쿼리에 대한 캐시를 일정 기간 동안만 유지하는 것이다

캐시 연습문제 구현코드(careercup/CtCI-6th-Edition)

• 가장 잘 팔리는 제품의 리스트(전체/카테고리별)를 출력해야 한다

단계1: 문제를 구체화

• 전자상거래 시스템 전체를 설계하는 것이 아니므로 관련있는 몇가지에만 집중
• '잘 팔린다' = 전체기간에 걸쳐 팔린 총량인지, 지난 한주/한달 동안인지 등, 여기서는 지난 한 주 동안의 판매량
• 각 제품은 여러 카테고리에 포함될 수 있고 서브카테고리는 없다고 가정

단계2: 합리적인 가정

• 통계 결과가 언제나 100% 최신 데이터는 아닐 수 있다.
• 인기 있는 제품의 경우 정확도가 중요하지만, 인기가 별로 없는 제품은 약간의 오차도 허용한다
• 가장 있기 있는 제품은 한 시간마다 갱신하지만, 데이터 범위가 정확히 7일이 아닐 수 있다
• 카테고리 분류는 판매자 이름을 기준으로 하고, 가격/날짜를 기준으로 하지 않는다

단계3: 주요 구성요소 그리기

[구매시스템] -(1)→ [데이터베이스] -(2)→ [판매순위데이터] → [프론트엔드]
(1) 주문정보를 저장한다
(2) 판매순위에 따라 정렬한다

단계4: 핵심문제 파악

• 데이터베이스에 너무 자주 접근한다. 필요한 데이터만 가져와서 처리한다.

  • 과거 구매기록은 다른 시스템이 맡고 있다고 가정하고, 판매 데이터만 따로 저장해서 처리한다
  • 지난 일주일간 데이터를 한 칼럼에 저장하면 매일 갱신해야 하므로
  • 월-일로 환형큐와 같이 여러 칼럼에 나누어 저장하면 연산을 줄일 수 있다

• 데이터베이스에 너무 자주 기록한다. 한 번에 모았다가 처리한다.

  • 초단위로 구매기록이 들어오므로 너무 자주 기록한다. 메모리 캐시와 같은 저장소에 저장했다가 주기적으로 모아서 기록한다
  • 만약 제품ID가 4바이트 구매량이 4바이트라면, 천만 개의 제품을 표현하려면 40메가 바이트면 충분하다
  • 단, 제품별로 메모리 캐시에서 구매량을 읽어들이는 주기가 달라 결과가 편향될 수 있다
    • 메모리 캐시를 시간대별로 나눠서 제품별로 차이가 없도록 하거나
    • 모든 데이터를 읽어들이기 전까지는 이전 데이터로 처리하도록 할 수 있다

• 데이터베이스 join은 비용이 비싸다.

  • 각 카테고리마다 제품의 정보를 읽어오면 값비싼 join연산을 여러번 해야한다
  • 제품과 카테고리에 대해 join을 수행해 정보를 읽어들이고 새로 정렬할 수도 있다
  • 카테고리 내부에서 데이터를 정렬하고 정보를 읽어들이고 전체 결과는 다시 전체를 정렬할 수도 있다
  • 혹은 처음부터 제품 정보를 함께 저장해둘 수도 있다

• 데이터베이스 쿼리는 비용이 비싸므로, 맵리듀스 같은 다른 시스템을 사용할 수 있다

더 고려할 점

• 병목현상이 일어날 수 있는 지점은?
• 서브 카테고리가 있다면?
• 데이터가 더 정확해야 한다면? 이를테면 적어도 30분 이내에 갱신된 것이어야 한다면?

• 2의 제곱수(아스키 문자 하나는 2바이트)

• 응답지연 값(2020년 기준)
  • 메모리는 빠르지만 디스크는 느리다
  • 디스크 탐색은 가능한 피해야한다
  • 단순한 압축 알고리즘은 빠르다
  • 데이터를 인터넷으로 전송하기전 가능한 압축하라
  • 데이터센터는 여러지역에 분산되어 있는데, 센터들간 데이터 주고받는 데 시간이 걸린다

*나노초(ns), 마이크로초(μs), 밀리초(ms)

*1나노초=10^-9초, 1마이크로초=10^-6초=1000나노초, 1밀리초=10^3초=1000마이크로초

• 가용성 관련수치

• 가정

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

• 추정

  • QPS추정
    • 일간 능동사용자 = 3억 X 50% = 1.5억 명
    • QPS = 1.5억 명 X 2트윗/24시간/3600초 = 약 3500
    • 최대 QPS = 2 X QPS = 약 7000
  • 미디어 저장을 위한 저장소 요구량 추정
    • 평균 트윗크기: id에 64바이트, 텍스트에 140바이트, 미디어에 1MB
    • 미디어 저장소 요구량: 1.5억 X 2 X 10% X 1MB = 30TB/일
    • 5년간 미디어를 보관하기 위한 요구량: 30TB X 365 X 5 = 약55PB

알렉스 쉬, 이병준 옮김, 가상 면접 사례로 배우는 대규모 시스템 설계 기초, 2020, 인사이트, pp.33-38

Google Pro Tip: Use Back-Of-The-Envelope-Calculations To Choose The Best Design, 2011/01