search

caffeine-library / system-design-interview

🌱 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 읽는 스터디
4 stars 0 forks source link

[keyword] 7~8장 키워드 정리 #22

Closed wooyounggggg closed 2 years ago

wooyounggggg commented 2 years ago

주제

7~8장을 읽고 내용을 요약하거나, 중요✨ 하다고 생각하는 키워드 및 관련 설명을 코멘트로 달아주세요

연관 챕터

21

@caffeine-library/readers-system-design-interview

wooyounggggg commented 2 years ago

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

전제 조건

다중 마스터 복제

DB의 auto_increment 기능을 활용하는 방법

image k개의 마스터 db가 존재하는 경우, 각 DB 시스템에서 다음 id를 k만큼 증가하는 방법 해당 방법은 아래와 같은 문제를 가짐

UUID(Universally Unique Identifier)

유일성이 보장되는 128비트 크기 ID를 만드는 방법

image

위와 같이 UUID를 각 서버에서 만드는 방식을 사용하면 각 인스턴스에서 독립적으로 충돌하지 않는 UUID들을 만들어 운용 가능 But, 아래와 같은 단점을 가짐

티켓 서버

유일성이 보장되는 ID 생성

image auto_increment 기능을 갖춘 티켓 서버(DB 서버)를 중앙 집중형으로 하나만 사용하는 방법. 유일성이 보장되는 숫자로만 구성된 ID를 쉽게 만들 수 있고, 중소 규모 애플리케이션에 적합함 다음과 같은 단점을 가짐

트위터의 스노플레이크

image

64비트의 ID는 위 그림의 구조를 가짐

타임스탬프

image 타임스탬프 비트에는 시간 값이 기록되므로, 타임스탬프 비트를 Sign 비트를 제외한 가장 앞에 두면 개별 서버에서 ID를 생성하더라도 시간별 정렬이 가능함 41비트로 표현할 수 있는 최댓값은 대략 69년이므로, 해당 시스템은 69년 동안 동작하는 시스템임

일련번호

어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우, 만들어진 ID에 넘버링할 목적으로 사용

추가 논의 과제

시계 동기화

물리적으로 독립된 장비에서 스노 플레이크로 접근하는 경우, 각 시스템이 시간이 동기화되지 않을 수 있으므로 시간별 정렬이 불가능할 수 있음

각 section 길이 최적화

동시성이 낮고 수명이 긴 Application은 일련번호 section을 줄이고 타임 스탬프 section을 늘리는 것이 효과적일 수 있음 비즈니스 상황에 따라 움직일 것

고가용성

ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 함

wooyounggggg commented 2 years ago

8장 URL 단축기 설계

기본 기능

개략적 추정

API 엔드포인트

  1. URL 단축용 엔드포인트 
    
// URL 주소를 단축 URL로 변환하는 api

Endpoint POST /api/v1/data/shorten

Body { longUrl: longURLString }

Result 단축된 URL


2. URL 리디렉션용 엔드포인트
```javascript
// 단축 URL에 대한 요청을 원래 URL로 리디렉션 하는 api

Endpoint
POST /api/v1/shortUrl

Result
HTTP redirection 목적지가 될 원래 URL

URL 리디렉션

단축 URL을 입력하는 경우, HTTP STATUS CODE는 301 또는 302를 반환하며, location에는 redirection target url이 작성됨

301 Permanantly Moved

해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 url로 이전되었다는 응답 영구 이전 되었으므로, 브라우저는 이 응답을 캐시하여 동일한 단축 URL 재요청시 캐시된 원래 URL로 URL을 변경하여 요청함 서버 부하를 줄이기 위해서는 301 처리가 유리함

302 Found

주어진 URL로의 요청이 일시적으로 Location 헤더가 지정한 URL에 의해 처리되어야 한다는 응답 클라이언트 요청은 언제나 단축 URL 서버에 보내진 후에 원래 URL로 리디렉션 됨 트래픽 통계 분석이 중요할 때는 302 처리가 유리함

URL 단축

요구사항

binchoo commented 2 years ago

블룸 필터

image image

한 문자열이 과거에 한 번 이상 입력되었는지 판단하는 배열입니다. →같이 보기: Trie 자료구조

Notations

BloomFilter: 길이 m인 배열이다. 0으로 초기화한다. N: 문자열 집합 K: 해시 함수 집합 해시 함수의 치역: 구간 [0, m-1] 이내

알고리즘

문자열 s를 K의 각 해시함수에 통과시켜 숫자들을 얻습니다. K(S) = (k1(s), k2(s), k3(s), ...) 이 숫자들을 인덱스로 하여 블룸 필터의 대응하는 위치를 읽습니다.

if all(BloomFilter[K(s)]):
  return true
else:
  BloomFilter[K(s)] = 1
  return false

오류 가능성

블룸필터 대응 위치 값들이 모두 1로 읽혔다고 해서 과거에 s가 반드시 입력된 것이라 할 수 없습니다.

M: 8
문자열: "126"
k1: "126" % 4 = 2
k2: "126" % 9 = 0 
k3: "126" % 3 = 0

Then
BloomFilter : [1 0 1 0 0 0 0 0]

문자열: "36"
K("36") = (0, 0, 0)

Then
BloomFilter[0]는 이미 1로 셋되어 있으므로 "36"이 과거에 입력되었다고 오판하게 된다.

에러율

i개의 문자열들이 블룸필터에 입력되었다고 가정하자. 임의의 s에 대하여, 블룸필터의K(s) 위치가 모두 1로 셋되어 있을 확률은?

image

산수에 따라

해시 함수 k=4개
블룸 필터 길이 m=5000
입력 횟수 i=500회

위 조건에서, s를 블룸필터에 입력 된 적이 있다고 판단할 확률은 1.18% 입니다.

최적 설정

image

참고자료

https://www.youtube.com/watch?v=bgzUdBVr5tE (동영상) https://hackernoon.com/probabilistic-data-structures-bloom-filter-5374112a7832 (블로그)