안녕하세요!

<대규모 시스템 설계 기초> 스터디 네번째 글입니다.

지난글

1회차 : OpenLab - 대규모 시스템 설계 기초 #1

2회차 : OpenLab - 대규모 시스템 설계 기초 #2

3회차 : OpenLab - 대규모 시스템 설계 기초 #3-1, #3-2

스터디 목차

1회차

• 1장 사용자 수에 따른 규모 확장성

• 2장 개략적인 규모 추정

2회차

• 4장 처리율 제한 장치의 설계

3회차

• 5장 안정 해시 설계

• 6장 키-값 저장소 설계

4회차

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

• 8장 URL 단축기 설계

  
  

스터디 개요

벌써 스터디가 후반으로 접어들고 있습니다.

본 스터디는 참고 도서의 12장 내용, "채팅 시스템 설계"를 마지막으로 스터디를 종료하게 됩니다. 앞으로 2번의 스터디가 남았네요!

이번 4회차 스터디는 호스트 개인 사정으로 인해 온라인 모임으로 진행했습니다.

온라인으로 진행하다 보니 자유롭게 토론 하는 방식이 쉽진 않아 멤버들 한 분, 한 분 돌아가며 스터디 내용에서 궁금했던 점이나 실무에서 겪었던 유사 사례를 공유하는 방식으로 진행 했습니다.

스터디 시작 전에는 '오늘은 특별히 할 이야기가 있을까?' 라는 생각으로 시작하는데 막상 진행하면 각자의 경험과 궁금한 점들을 주고 받다 보니 1시간 30분의 시간이 훌쩍 지나가게 되네요.

이번 스터디는 스터디 선정 도서의 7,8장을 진행했습니다.

7장 유일 ID 생성기의 경우 흔히 접했던 내용은 아니었는데 거래 관련한 트랜잭션 처리 시 유일ID를 사용하는 사례가 있다는 것을 스터디를 공유하며 알게되었습니다.

8장 URL 단축기의 경우 https://bitly.com/ 와 같은 서비스를 자주 이용해봐서 어떤 것인지는 알았으나 이번 스터디를 통해 좀 더 자세한 설계 내용을 알 수 있었습니다.

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

분산 환경에서 유일성이 보장되는 ID 생성 시스템을 설계하는 것이 목표

문제 이해 및 설계 범위 확정

유일 ID 생성 시스템은 아래의 조건 범위를 만족시킨다

• ID는 유일해야 한다

• ID는 숫자로만 구성되어야 한다

• ID는 64비트로 표현할 수 있는 값

• ID는 발급 날짜에 따라 절렬 하능해야한다

• 초등 10000개이의 ID

유일 ID 생성 방법

아래와 같은 유일 ID 생성 방법에 대해 살펴볼 것

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

• UUID(Universally Unique Identifier)

• 티켓 서버(ticket server)

• 트위터 스노프레이크(twitter snowflake) 접근법

다중 마스터 복제

• DB의 auto increment 기능을 활용하는 것

• 다음 ID 값을 구할 때 DB 개수 만큼 정해진 k값을 증가시킴

• 규모 확장 가능한 구조

단점

• 여러 데이터센터에 걸쳐 규모를 늘리기 어려움

• ID의 유일성은 보장하지만, 그 값이 시간 흐름에 맞추어 커지는 보장은 없음

• 서버를 추가하거나 삭제할 때도 잘 동작하도록 하기 어려움

UUID

• 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트 수

• 충돌 가능성이 지극히 낮음

• 중복이 한 개 생길 확률을 50%로 만들려면 초당 10억개의 UUID를 100년 동안 계속 만들어야함

• 일반적으로 8-4-4-4-12 형식

  • ex) 123e4567-e89b-12d3-a456-426614174000

장점

• UUID를 만드는 것은 서버 사이 조율이 필요없으므로 단순하고 동기화 이슈가 없음

• 각 서버가 각자 ID를 생성해서 사용하면 되는 구조이므로 규모 확장 용이

단점

• ID가 128비트로 길다

• ID를 시간순으로 정렬 할 수 없다

  • -> UUID 구조를 보면 time base로 생성하는 버전도 있는데 이것도 마찬가지로 시간순 정렬이 안 되나?

• ID에 숫자(numeric)이 아닌 값이 포함될 수 있음

티켓 서버

• auto increment 기능을 갖춘 DB 서버(티켓서버)를 중앙 집중형으로 하나만 사용

장점

• 유일성이 보장되는 숫자로만 구성된 ID를 쉽게 만들 수 있음

• 구현하기 쉽워 중소 규모 애플리케이션에 적합

단점

• 티켓 서버가 SPOF가 됨

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

• 생성해야 하는 ID의 구조를 여러 절(section)으로 분할

• sign bit : 음수와 양수를 구별하는데 사용할 수 있으나 일반적으로 사용 유보

• timestamp : 41 비트 할당. 기원 시각(epoch) 이후로 몇 밀리초가 경과했는지를 나타냄

  • 해당 값으로 최대 언제까지 ID 생성기를 사용 가능한지 추정 가능

• 데이터센터 ID : 5비트로 할당, 2^5=32개 데이터센터 지원

• 서버 ID : 5비트 할당, 데이터센터당 32개 서버 지원

• 일련번호 : 12비트 할당, 각 서버에서 ID를 생성할 때마다 이 일련 번호를 1증가

  • 해당 값은 1밀리초가 경과하면 0으로 리셋

타임스탬프

• 시간 흐름에 따라 점점 큰 값을 갖게 되므로, ID는 시간 순으로 정렬 가능

• 41비트로 표현할 수 있는 타임스탬프의 최대값은 2^41 - 1 = 2199023255551 밀리초 -> 69년 사용 가능

일련번호

• 일련 번호는 12비트 -> 2^12 = 4096개

• 밀리초 내에 하나 이상의 ID 생성시만 증가

참고

UUID

• https://docs.tosspayments.com/resources/glossary/uuid

snowflake

• https://bistros.tistory.com/185

  
  

Chapter 8 - URL 단축기 설계

• Long URL 입력시 Short URL로 변환

• 변환된 URL로 접속 시 본래 URL로 redirect

문제 이해 및 설계 범위

• 쓰기 연산 : 매일 1억개의 단축 URL 생성

• 초당 쓰기 연산 : 1억/24/3600 = 1160

• 읽기 연산 : 읽기 연산과 쓰기 연산 비율은 10:1이라고 가정 -> 읽기 연산은 초당 11600회

• URL 단축 서비스 10년 운영 시 1억 x 365 x 10 = 3650억개 레코드 보관해야함

• 축약 전 URL의 평균 길이는 100으로 가정

• 10년 동안 필요한 저장 용량은 3650억 x 100 byte = 36.5TB

API Endpoint

• URL 단축용

  • POST /api/v1/data/shorten

  • 인자 : {longURL : longURLstring}

  • 반환 : 단축 URL

• URL Redirection용

  • GET /api/v1/shortUrl

  • 반환 : HTTP 리디렉션 목적지가 될 원래 URL

URL 리디렉션

• 브라우저에서 단축 URL 호출 시 아래와 같이 동작

• URL을 받은 서버는 그 URL을 원래 URL로 바꾸어 301 응답의 Location 헤더에 반환

• 301 Permanently moved : 브라우저에서 해당 응답을 캐시

  • 301 방식은 서버 부하를 줄이는 것이 중요한 경우 채택

• 302 Found : 일시적으로 Location 헤더에 URL 전달, 클라이언트 요청은 언제나 단축 URL tjqjdp qhsowla

  • 302 방식은 클릭 발생률이나 발생 위치를 추적하는 경우 유리

URL 단축

• 단축 URL은 다음과 같은 형식

  • www.tinyurl.com/{hashValue}

• 중요한 것은 긴 URL과 단축 URL을 대응시키는 해시 함수 fx를 찾는 것

요구사항

• 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야함

• 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야함

데이터모델

• 모든 것을 해시 테이블에 두는 것은 메모리 제한 등으로 문제가 있음

• 더 나은 방법은 <단축 URL, 원래 URL> 쌍으로 DB에 저장하는 것

• 다축 URL DB Table

  • ID

  • shortURL

  • longURL

해시 함수

• 원래 URL을 단축 URL로 변환하는데 사용

해시 값 길이

• hashValue는 [0-9, a-z, A-Z]의 문자들로 구성

• 사용할 수 있는 문제 개수는 62개

• 최초 요구 사항이었던 3650억개 이상의 URL 생성 필요시 hashValue의 길이는 7자 되어야함

해시 함수 구현 기술

해시 후 충돌 해소

• 7글자 문자열로 해시를 생성하는 쉬운 방법은 CRC32, MD5, SHA-1 등을 이용하여 7자로 자르는 방법

• 이 경우 서로 충돌 가능성이 높아짐

• 충돌이 발생하면 사전에 정한 문자열을 해시 값에 덧붙임

단점

• 충돌 시 한 번 이상 DB 조회 필요

base-62 변환

• 진법 변환(base conversion)은 URL 단축기 구현 시 흔히 사용되는 접근법

• 62진법은 총 62개 문자(앞서 요구사항에 정의한 문자들)를 사용하는 진법

• 0은 0, 9는 9, a는 10, z는 35, Z는 61로 대응

• ID : 11157(10진법) -> 2TX로 변환됨

URL 단축기 상세 설계

• 입력된 URL이 https://en.wikipedia.org/wiki/Systems_design 인 경우

• 이 URL에 대해 ID 생성기가 반환한 ID는 2009215674938이 됨

• 이 ID를 62진수로 변환하면 zn9edcu를 얻게됨

• ID는 분산 시스템 전역에서 유일한 ID여야함