[5장] 안정 해시 설계
배경
여러 서버들에 부하를 균등하게 나누는 방법으로 해시 함수를 이용함
→ hash(key0) % 4 = 1 → 서버 1에 접속해야함
하지만 이 방법은 서버 풀의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 동작함
but 서버가 추가되거나 줄어든다? → 키에 따른 해시값은 동일하지만 결과 값은 달라짐
→ 장애가 발생한 서버에 보관되어 있던 키가 재분배되며 데이터가 없는 다른 서버에 접속하게되는 캐시 미스가 발생
→ 이를 해결해주는 기술 ⇒ 안정 해시
안정 해시
- 해시 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시기술
- k = 키의 개수, n = 슬롯의 개수
안정 해시의 동작원리
- 해시 함수로 SHA-1를 사용하면, 해시 공간의 범위 = 0~2^160-1
- 해시 공간의 시작과 끝이 이어지게(2^160-1 의 다음 값이 0) 만든 것이 해시 링
- 해시 함수를 이용하여 서버를 해시 링의 어떤 위치에 배치, 해시 키도 링 위의 어디든 배치 가능
- 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색하며 만나는 첫 서버 → 아래 그림과 같이 중간에 서버
s4가 추가 되었지만, 다른 키는 변함없이key0만s0에서s4로 재배치됨
→ 서버가 제거되어도 일부 key만 재배치됨
안정 해시의 기본 구현법
- 서버와 키를 균등 분포 해시 함수를 사용해서 해시 링에 배치
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
기본 구현법의 문제점
- 서버 추가, 삭제 시 파티션의 크기를 균등하게 유지하는 것이 불가능
- 파티션: 두 서버 사이의 해시 공간
- 키의 균등 분포를 달성하기 어려움
→ 가상 노드 or 복제 기법으로 위 문제들을 해결
가상 노드
- 이 그림에서는 서버0과 서버1은 각각 3개의 가상 노드를 가짐
- 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상노드가 해당 키의 서버가됨 → 위 그림과 같이 가상노드를 기준으로 각 서버가 관리하는 파티션이 나뉨
안정 해시의 이점
- 서버가 추가/삭제될 때 재배치되는 키의 수가 최소화됨
- 데이터가 보다 균등하게 분포 → 수평적 규모 확장성 유리
- 핫스팟 키 문제를 줄임
[6장] 키-값 저장소 설계
분산 키-값 저장소
- 데이의 일관성
- 가용성: 일부 노드에 장애가 발생해도 정상작동
- 파티션 감내: 두 노드 사이에 통신 장애(파티션)가 발생하더라도 정상 작동
→ 보통 가용성 or 데이터 일관성 중 하나를 희생하여 설계함(파티션 감내는 필수)
시스템 컴포넌트
-
데이터 파티션
- 데이터를 하나의 서버가 아닌 여러 파티션에 나눠서 넣음
- 고르게 분산할 수 있는가? 노드 추가 및 삭제 시 데이터 이동 최소화 가능?
→ 안정 해시 → 규모 확장 자동화, 다양성
-
데이터 다중화
-
데이터 일관성
- 강한 일관성: 모든 사본에 쓰기 연산 결과가 반영될 때 까지 읽기/쓰기 금지 → 가용성 하락
- 데이터 버저닝: 데이터 변경 시 해당 데이터의 새로운 버전을 만드는 것을 의미
→ 벡터 시계([서버, 버전] 순서쌍을 데이터에 매단 것)를 사용
-
장애처리
- 장애 감지
- 가십 프로토콜: 각 노드는 멤버십 목록(id와 heartbeat counter)보유 중, 주기적으로 heartbeat counter 증가 후 다른 노드에 알리고 오래동안 갱신되지 않으면 장애로 간주
- 일시적 장애처리: 장애가 발생하면 대신 읽기/쓰기 연산을 해줄 서버를 해시링에서 고르고 원래 서버에 대한 단서를 남겨둠. 장애가 복구되면 원래서버에 반영함.
- 영구 장애 처리: 반 엔트로피 프로토콜을 구현하여 사본들을 동기화 + 머클 트리 사용
- 장애 감지
-
클라이언트는 key-value 저장소의 put, get api와 통신
-
중재자는 proxy 역할을 하는 노드
-
노드는 안정 해시의 해시 링 위에 분포한다
-
데이터는 여러 노드에 다중화
-
SPOF 존재 X
요약
- 대규모 데이터 저장 → 안정 해시
- 읽기 연산에 대한 가용성 → 데이터 다중화
- 쓰기 연산에 대한 가용성 → 데이터 버저닝 + 벡터 시계
[7장] 분산 시스템을 위한 유일 ID 생성기 설계
분산 시스템에서는 auto_increment 속성으로 기본키를 쓰면 안됨. 왜냐면 DB하나로는 요구를 감당 불가능, 여러 DB를 쓰면 지연시간을 낮추기 힘듦
분산 시스템에서 유일성이 보장되는 ID 만드는법
- 다중 마스터 복제: 서버1 = 1,4,7… 서버2 = 2,5,8… 서버3 = 3,6,9…
- 장점: 규모확장성 문제 해결, id의 유일성 보장, 초당 생산 id 수 증가
- 단점: 여러 데이터 센터에 걸쳐 규모를 늘리기 어려움, id로 시간흐름을 알 수 없음, 서버 추가/삭제 시 잘 동작하도록 만들기 어려움
- UUID
- 장점: 독립적으로 생성 가능, 규모확장이 쉽다, 유일성도 웬만하면 보장됨
- 단점: 128비트, 시간순 정렬X, 숫자가 아닌 값이 포함될 수 있음
- 티켓 서버: auto_increment 기능을 갖춘 DB서버(티켓 서버)를 중앙 집중형으로 하나만 사용
- 장점: 유일성 + 숫자로만 구성 + 시간순 정렬O, 쉬움
- 단점: 티켓 서버가 SPOF가 됨
- 트위터 스노플레이크 접근법
- 64비트를 1비트=0, 41비트=타임스탬프, 5비트=데이터센터ID, 5비트=서버ID, 12비트=일련번호
→ 64비트로 숫자로만 이루어지고, 시간순 정렬이 가능하며 유일하고 확장성도 문제 없음
- 64비트를 1비트=0, 41비트=타임스탬프, 5비트=데이터센터ID, 5비트=서버ID, 12비트=일련번호
[8장] **URL 단축기 설계**
URL 단축기
- https://search.naver.com/search.naver?where=nexearch&sm=top_hty&fbm=0&ie=utf8&query=아무거나 → https://naver.me/Gbx1kC8P
이런식으로 url을 줄여줌. 보통 단축된 URL을 접속하면 원래 URL로 Redirection 시켜줌
흐름
- 단축 URL 방문 → location: 원래 url + 301 반환 → 원래 URL 방문
API 엔드포인트
- URL 단축용 엔드포인트: [POST] /api/v1/data/shorten
- 인자: 단축시킬 URL
- 반환: 단축된 URL
- URL 리디렉션용 엔드포인트: [GET] /api/v1/shortUrl
- 반환: Redirection 목적지가 될 URL(status code: 301)
응답코드 - 301 vs 302
- 301: 영구적인 redirection, 브라우저는 이 응답을 cache함
- 302: 일시적인 redirection, cache X
→ 성능은 301 > 302, BUT 301은 캐싱으로 인해 서버를 거치지 않아서 트래픽 분석이 어려움
상세 설계
- 단축 URL과 원래 URL을 관계형 데이터베이스에 저장하는 방법으로 설계 ㄱㄱ
- 해시 함수 정하기: CRC, SHA-1 같은 해시함수 이용
→ BUT 너무 김 → 7자리까지만 사용하고, 이미 같은 값이 있으면 뒤에 값까지 붙히는 방식
→ DB한번 더 확인해서 별로 → 블룸 필터라는 기술 사용 가능(집한안에 특정 원소 있는지 확인하는 기술) - base-62 변환: 62진법을 사용하여 변환. url길이가 가변적, 유일성이 보장되는 ID가 필요, 기본키가 auto-increment면 다음에 쓸 단축URL 예측 가능
로드밸런서의 동작 흐름 정리
- 단축 URL 클릭
- 로드밸런서가 요청을 웹 서버에 전달
- 캐시에 단축 URL이 있으면 바로 전달
- 캐시에 단축 URL이 없으면 DB에서 꺼냄
- URL을 캐시에 넣고 사용자에게 반환
