가상 면접 사례로 배우는 대규모 시스템 설계 기초 -2-

스터디

가상 면접 사례로 배우는 대규모 시스템 설계 기초 -2-

정한_s 2022. 2. 25. 20:38

네트워크 시스템 처리율 제한 장치(rate limiter)

클라이언트 또는 서비스가 보내는 트래픽 제어 장치이다.

사용예시 : 사용자 특정 기간내 API 요청 횟수 제한하여 임계치가 넘어갈 경우 그 이후 호출은 중단되게 한다.

장점

특정 요청을 계속 보내서 공격하는 Dos 공격을 방지할 수 있다.
비용 절감 : 요청 처리를 제한 함으로써 서버의 수를 줄여 비용을 절감 할 수 있다.
서버 과부화 방지 : 트래픽을 조절 함으로써 서버의 과부화를 막을 수 있다

처리율 제한 장치 위치

처리율 제한 장치를 각각 위치에 두었을 때 특징을 말한다

클라이언트 : 클라이언트의 요청은 쉽게 위변조가 가능하고 통제가 어렵기 때문에 비추천
API 서버 : 요청을 API 서버측에서 검증하고 통제한다
미들웨어 : 장치를 클라이언트와 서버 사이에 미들웨어로 두어 API 서버로 가는 요청을 filtering 한다. MSA의 경우에 처리율 제한 장치는 보통 API 게이트웨이 서버에 두어 처리한다.

*API 게이트 웨이 서버

처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리, 로드 밸런싱, 포워딩등을 담당하는 서비스

처리율 제한 알고리즘

토큰 버킷
누출 버킷
고정 윈도 카운터
이동 윈도 로그
이동 윈도 카운터

토큰 버킷 알고리즘

처리율 제한에 폭넓게 이용되고 있다. 간단하고, 보편적이다

동작원리

토큰 버킷은 지정된 용량을 갖는 컨테이너이다.
- 이 버킷에는 사전 설정된 양의 토큰이 주기적으로 채워진다.
- 토큰이 꽉 찬 버킷에는 더 이상의 토큰은 추가 되지 않는다
- 각 요청은 처리될 때 마다 하나의 토큰을 사용한다.
요청이 도착하면 버킷에 충분한 토큰이 있는지 검색한다
- 충분한 토큰이 있는 경우, 버킷에서 토큰을 꺼내 요청을 서버에 전달한다
- 충분한 토큰이 없는 경우, 해당 요청은 버려진다

토큰 버킷 인자

버킷 크기 : 버킷에 담을 수 있는 토큰의 최대 개수
토큰 공급률 : 초당 몇 개의 토큰이 버킷에 공급되는가

버킷을 두는 기준

API 엔드 포인트 마다 별도의 버킷을 둔다
IP 주소 별로 처리율 제한을 해야 한다면 IP 주소마다 버킷을 할당한다
시스템 처리율을 제한하고 싶다면 모든 요청이 하나의 버킷을 공유한다

장점

구현이 쉽다
메모리 사용 측면에서 효율적이다
버킷의 토큰만 남아 있다면 요청은 서버에 전송된다. 따라서 트래픽 변동에 유연하다

단점

최적의 버킷 크기와 토큰 공급률을 찾기 어렵다

누출 버킷 알고리즘

토큰 버킷 알고리즘과 비슷하지만 요청 처리율이 고정되어 있다

보통 FIFO 큐로 구현 한다.

동작 원리

요청이 도착하면 큐가 가득 차 있는지 확인. 빈자리가 있는 경우 큐에 요청 추가
큐가 가득 찬 경우 새 요청을 버린다
지정된 시간마다 큐에서 요청을 꺼내어 처리(고정 속도로 처리)

누출 버킷 인자

버킷 크기 : 큐 사이즈와 같은 값이다. 큐에는 처리될 항목을 보관한다
처리율 : 지정된 시간당 몇 개의 항목을 처리할지 지정한다. 보통 초 단위로 표기

장점

큐의 크기가 제한되어 메모리 사용 측면에서 효율적이다
고정된 처리율을 가지고 있기 때문에 안정된 출력이 필요할 경우 적합하다

단점

많은 트래픽이 오는 경우 큐에 요청이 쌓이고, 요청을 처리 못할시 최신 요청을 버려진다
최적의 처리율과 버킷 크기를 찾기 어렵다

고정 윈도 카운터 알고리즘

동작원리

타임라인을 고정된 간격의 윈도로 나누고, 각 윈도마다 카운터를 붙인다
요청이 접수될 때마다 카운터의 값은 1씩 증가한다
카운터의 값이 임계치에 도달하면 이후 요청은 새 윈도가 열릴때 까지 버려진다

장점

메모리 효율이 좋다
이해하기 쉽다
특정 트래픽 패턴을 처리하기 적합하다

단점

윈도 경계 부근에서 일시적으로 많은 트래픽이 몰리는 경우, 기대했던 시스템 처리 한도 보다 많은 양의 요청을 처리 한다

ex) expect 분당 처리 count 5, 초단위로 slice 했다고 가정했을 때,

0~ 30 초 처리 0, 30~60 처리 5, 60~90 처리 5, 90~120 처리 0 라고 할때 2분당 처리한 결과는 총 10개이지만, 특정 시간 30~90 인 1분 동안 처리한 결과는 10개로 분당 처리 5개를 넘는다

이동 윈도 로깅 알고리즘

설정된 요청보다 많은 요청을 처리하는 문제를 해결하는 알고리즘

동작 원리

요청의 타임스탬프를 추적한다. 타임스탬프 데이터는 보통 레디스의 정렬 집합 같은 캐시에 보관한다
새 요청이 오면 만료된 타임스탬프는 제거한다. 만료된 타임스탬프는 그 값이 현재 윈도의 시작 시점보다 오래된 타임스탬프를 말한다
새 요청의 타임스탬프를 로그에 추가한다
로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달한다. 그렇지 않을 경우 처리를 거부한다

장점

처리율 메커니즘이 정교하다. 허용되는 요청의 개수는 시스템의 처리율 한도를 넘지 않는다

단점

다량의 메모리를 사용한다.(거부된 요청의 타임스템프도 보관한다)

이동 윈도 카운터 알고리즘

고정 윈도 카운터 알고리즘과 이동 윈도 로깅 알고리즘을 결합한 것이다.

조건

처리율 제한 장치의 한도가 분당 7개 요청으로 설정되어 있음
1분 동안 5개의 요청이, 그리고 현재 1분 동안 3개의 요청이 왔다고 가정

문제

현재 1분의 30% 시점에 도착한 새 요청의 경우, 현재 윈도에 몇 개의 요청이 온 것으로 보고 처리해야 하는가?

계산

현재 1분간의 요청 수 + 직전 1분 간의 요청 수 * 이동 윈도와 직전 1분이 겹치는 비율
이 공식에 따르면 현재 윈도에 들어 있는 요청은 3 + 5 * 70% = 6.5개

조건에 따라서 분당 7개 요청이므로 새 요청은 서버에 전달된다. 또한 그 이후의 요청은 받을 수 없다

장점

이전 시간대의 평균 처리율에 따라 현재 윈도의 상태를 계산하므로 트래픽에 잘 대응한다
메모리 효율이 좋다

단점

직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산하기 떄문에 다소 느슨하다 (생각보다 심각하지는 않다)

처리율 알고리즘 설계

처리율 알고리즘은 단순하다. 얼마나 요청이 접수되었는지 추적할 수 있는 카운터를 추적 대상 별로 두고, 카운터 값이 한도를 넘으면 요청을 거부한다

카운터 보관

데이터베이스는 디스크 접근으로 인한 속도 저하로 사용하면 안된다
메모리 상에서 동작하는 캐시가 바람직하다(ex 레디스)

*redis 명령어 : INCR(숫자 1씩 증가), EXPIRE(타임 아웃 값을 설정, 설정 시간 지나면 삭제)

처리율 장치 미들웨어에서 Redis 사용 경우

클라이언트가 처리율 제한 미들웨어에게 요청을 보냄
처리율 제한 미들웨어는 레디스의 지정 버킷에서 카운터를 가져와 한도에 도달했는지 아닌지를 검사
- 한도에 도달했다면 요청은 거부됨
- 한도에 도달하지 않았다면 요청은 API 서버로 전달됨
- 한편 미들웨어는 카운터의 값을 증가시킨 후 다시 레디스에 저장

상세 설계

처리율 제한 규칙은 디스크에 보관. 작업 프로세스는 수시로 규칙을 디스크에서 읽어 캐시에 저장
클라이언트가 요청을 서버에 보내면 요청은 먼저 처리율 제한 미들웨어에 도달
처리율 제한 미들웨어는 제한 규칙을 캐시에서 가져옴. 아울러 카운터 및 마지막 요청의 타임스탬프를 레디스 캐시에서 가져옴
가져온 값들에 근거해 해당 미들웨어는 다음과 같은 결정을 내림
- 해당 요청이 처리율 제한에 걸리지 않은 경우 API 서버로 보냄
- 해당 요청이 처리율 제한에 걸렸다면 429 too many requests 에러를 클라이언트에게 보냄
  - 해당 요청은 버려질 수도, 메시지 큐에 보관할 수도 있음

분산환경에서 고려해야 할점

경쟁 조건
동기화

경쟁 조건

경쟁 조건을 해결하기 위해 lock을 사용하면 된다. 하지만 lock의 경우 시스템의 성능을 떨어뜨릴 수 있다. 루아 스크립트 사용, 정렬 집합 사용

동기화 이슈

고정 세션을 사용하여 동기화한다.
- 같은 클라이언트는 항상 같은 처리율 처리 장치로 간다
레디스와 같은 중앙 집중형 데이터 저장소를 사용한다
- 저장소에서 데이터를 보관하여 전체 데이터를 동기화 한다

성능 최적화

사용자 트래픽을 가장 가까운 edge 서버에 전달하여 지연 시간을 줄인다.

모니터링

현재 알고리즘이 효율적으로 동작하는 지 확인을 위한 과정, 트래픽 패턴에 잘 처리할 수 있는 알고리즘을 사용해야한다

*more

경성과 연성

경성 : 임계치를 절대 넘어설 수 없다
연성 : 잠시동안은 임계치를 넘어 설 수 있다

처리율 제한 회피

클라이언트 측에 캐시를 사용해서 API 호출 횟수를 줄인다
짧은 시간동안 너무 많은 메시지를 보내지 않게 한다
재시도시 충분한 백오프 시간을 둔다

Redis

레디스는 싱글 스레드 이다.

Redis별도의 시스템 명령들을 사용하는 전용 스레드(백업 등)가 있지만, 실제 사용자가 사용하는 명령어는 싱글 스레드에서 동작한다.

레디스 백업

RDB : 특정 시점(SNAPSHOT)의 메모리에 있는 데이터 전체를 바이너리 파일로 저장

AOF : 입력/수정/삭제 명령이 실행될 때마다 기록된다. 조회 명렁어 제외

레디스 원자성과 트랜잭션

레디스의 트랜잭션은 모든 명령은 순서대로 실행되고, 고립된 상태로 처리되기 때문에 다른 명렁어가 끼어들 수 없다(원자성). 다만 RDB 트랜잭션과 다르게 롤백의 특성은 없다.

원자성 보장 방법

MULTI 및 EXEC 명령어 사용
- MULTI 명령 : Transaction 시작을 나타내는 명령
- Exec 명령 : Transaction 작성을 마치고 내용들을 실행하는 명령
Lua script 사용
- Eval 명령어를 이용하여 수행하고자 하는 스크립트를 레디스로 전송한다

분산락

스핀락 방법
- 스레드가 락을 계속 획득하려고 시도하기 때문에 레디스에 많은 트래픽을 유발한다.
Redisson 분산락 방법
- pubsub 기능(비동기 메시지 통신) 사용, Lua 스크립트로 원자성 보장

참고자료

(https://hyperconnect.github.io/2019/11/15/redis-distributed-lock-1.html)

(https://hoooon-s.tistory.com/25)

(https://caileb.tistory.com/205)

(https://engineering.linecorp.com/ko/blog/atomic-cache-stampede-redis-lua-script/)

안정 해시 설계

수평적 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.

해시 키 재배치 문제

N개의 캐시 서버 부하를 균등하게 나누는 보편적인 방법은 index = hash(key)%N , 나머지 연산을 하는 것이다.
이는 서버 풀의 크기가 고정되거나, 데이터 분포가 균등할 때 잘 동작한다.
하지만 서버가 추가 되거나 기존 서버가 삭제되는 등 N이 변경 되면 문제가 생긴다

안정 해시는 이러한 문제를 해결해 주는 기술이다.

안정 해시

안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술
k는 키의 개수, n은 슬롯(slot)의 개수
대부분 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치했었음

해시공간과 해시링

해시공간 : 해시 함수 f로 나올 수 있는 해시 공간

해시링 : 해시 공간을 양쪽을 구부려 접어 링 형태로 만든 것 (원형 큐)

해시 서버와 해시 키

해시 함수 f를 사용하여 링 위의 어떤 위치에 대응한다.

안정 해시는 나머지 연산을 사용하지 않는다

기본 구현

서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다
키의 위치에서 링을 시계방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.

서버 조회

어떤 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫번째 서버이다

k는 key, s는 서버를 나타낸다. 예시로 k0는 s0에 저장되고, k1은 s1에 저장된다

서버 추가

서버를 추가할시 키 가운데 일부만 재배치 하면 된다.

k는 key, s는 서버를 나타낸다. 예시로 s4 서버가 추가된다면 k0만 재배치 된다. k0는 s4에 저장된다

서버 제거 역시 하나의 서버가 제거되면 해당 서버에 저장된 key 만 다른 서버에 재배치 하면 된다

기본 구현 문제점

서버가 추가되거나 삭제되는 상황에서 각 서버의 파티션 크기를 균등하게 유지하는 것이 불가능하다. (파티션이란 인접한 서버 사이의 해시 공간)
키의 균등 분포를 달성하기 어렵다 (한 서버에 키가 몰릴수 있다)

이러한 문제를 해결하기 위해 가상노드(복제) 기법을 사용한다

가상노드

실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러개의 가상 노드를 가질 수 있다.
따라서 각 서버는 하나가 아닌 여러개의 파티션을 관리해야 한다
편차를 줄이기 위해 파티션을 잘게 쪼개는 기법, 표준 편차가 작아지기 때문에 데이터가 고르게 분포된다
가상노드가 많아 질 수록 가상노드를 저장할 공간이 많아져야 하므로, 데이터의 균등한 분포와 데이터 공간 간에 트레이드 오프가 발생한다

안정 해시의 장점

서버가 추가되거나 삭제 될 때 재배치되는 키의 수가 최소화 된다
데이터가 균등하게 분포되어 수평적 규모 확장성을 달성하기 쉬워진다(가상노드 기법 사용시)
핫스팟 키 문제(유명인사 문제)를 줄인다.
- 특정 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있는데, 안정해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제 줄일 수 있다

키-값 저장소 설계

키-값 데이터베이스라고도 불리는 비 관계형 데이터베이스이다. 키-값 쌍에서 키는 유일 해야 하며 해당 키에 매달린 값은 키를 통해서 접근할 수 있다.

키는 일반 텍스트일 수도 있고 해시 값 일수도 있다. 키는 성능상 짧을 수록 좋다. 보통 값으로 무엇이 오든 상관하지 않는다.

단일 서버 키-값 저장소

가장 직관적인 방법은 키-값 쌍 전부를 메모리에 해시 테이블로 저장하는 것
메모리에 저장하기 때문에 빠른 것이 장점이지만 공간의 제약으로 모든 데이터를 메모리 안에 두는 것이 불가능 할 수도 있다. 다음은 개선 방법이다.
- 데이터 압축으로 데이터의 양을 줄인다
- 자주 쓰는 데이터만 메모리로 캐시하고 나머지는 디스크에 저장한다

분산 서버 키-값 저장소

분산 해시 태이블이라고 불린다

키-값 쌍을 여러 서버에 분산시킨다
분산 시스템을 설계할 때 CAP 정리를 이해해야 한다

CAP 정리

데이터 일관성(consistency), 가용성(availability), 파티션 감내(partition tolerance)라는 세 가지 요구사항을 동시에 만족하는 분산 시스템을 설계하는 것은 불가능하다는 정리

어떤 두가지를 충족하려면 나머지 하나는 반드시 희생해야 한다

데이터 일관성

분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다

가용성

분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다

파티션 감내

파티션은 두 노드 사이에 통신 장애가 발생하였음을 의미한다. 파티션 감내는 네트워크에 파티션이 생기더라도 시스템은 계속 동작하여야 한다는 것을 뜻한다

CP 시스템 : 가용성을 희생, 대용량 분산 파일 시스템, ex) 몽고 DB, Hbase
AP 시스템 : 일관성을 희생, 비동기화식 서비스 ,SNS서비스 ex) 카산드라
CA 시스템 : 파티션 감내를 희생, 트랜잭션 보장 ex) RDMS

데이터 파티션

데이터를 여러 서버에 고르게 분산할 수 있어야 하며 노드가 추가되거나 삭제 될 때 데이터들의 이동을 최소화 해야 한다.

안정 해시 사용해 파티션시 장점

규모 확장 자동화 : 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제되도록 만들 수 있음
다양성 : 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있음. 고성능 서버는 더 많은 가상노드를 갖도록 설정 가능

데이터 다중화

높은 가용성과 안정성을 확보하기 위해 데이터를 N개 서버에 비동기적으로 다중화 할 필요가 있다. 중복 서버를 제외하고 만나는 N개의 서버에 데이터 사본을 보관한다

데이터 일관성

여러 노드에 다중화된 데이터는 적절히 동기화가 되어야 한다.

정족수 합의 프로토콜을 사용하면 읽기/쓰기 연산 모두에 일관성을 보장할 수 있다

정족수 합의 프로토콜

정의

N = 사본의 개수
W = 쓰기 연산에 대한 정족수. 쓰기 연산이 성공한 것으로 간주되려면 적어도 W개의 서버로부터 쓰기 연산이 성공했다는 응답을 받아야 함
R = 읽기 연산에 대한 정족수. 읽기 연산이 성공한 것으로 간주되려면 적어도 R개의 서버로부터 응답 받아야 함

N, W, R 구성

R = 1, W = N : 빠른 읽기 연산에 최적화된 시스템
W = 1, R = N : 빠른 쓰기 연산에 최적화된 시스템
W + R > N : 강한 일관성이 보장됨 (보통 N = 3, W = R = 2)
W + R <= N : 강한 일관성이 보장되지 않음

일관성 모델

데이터 일관성의 수준을 결정한다

강한 일관성 : 모든 읽기 연산은 가장 최근에 갱신된 결과를 반환한다. 클라이언트는 절대 낡은 데이터를 보지 못한다
약한 일관성 : 읽기 연산은 가장 최근에 갱신된 결과를 반환하지 못할 수 있다
최종 일관성 : 약한 일관성의 형태로, 갱신 결과가 모든 사본에 반영(동기화) 되는 모델이다

강한 일관성 모델은 현재 쓰기 연산 결과가 반영될 때 까지 해당 데이터에 쓰기/읽기를 금지하는 것이므로 고가용성 시스템에 적합하지 않다.

따라서 카산드라나 다이나모 같은 저장소는 최종 일관성 모델을 사용한다. 데이터의 일관성이 깨질 경우 클라이언트가 해결해야 한다

비 일관성 해소 기법: 데이터 버저닝

버저닝

데이터를 변경할때마다 해당 데이터의 새로운 버전을 만드는 것이다
각 버전의 데이터는 변경 불가능 하다

백터 시계

충돌을 발견하고 해결할때 사용하는 기술
[서버, 버전]의 순서쌍을 데이터에 매단 것
순서쌍을 비교함으로써 어떤 버전이 선행 버전인지, 후행 버전인지 충돌이 일어났는지 판단에 사용된다
충돌이 일어났다면 클라이언트가 충돌을 해결한 후에 서버에 기록한다

장애 감지

분산 시스템에서 보통 두 대 이상의 서버가 똑같이 서버 A의 장애를 보고해야 해당 서버가 실제 장애가 발생했다고 간주한다.

모든 노드끼리 연결하는 방법이 서버 장애를 감지하는데 쉬운 방법이지만 서버가 많을 때 비효율적이다.

가십 프로토콜 같은 분산형 장애 감지 방법이 효율적이다

가십 프로토콜 동작원리

각 노드는 멤버십 목록을 유지. 멤버십 목록은 각 멤버 ID와 그 박동 카운터(heartbeat counter) 쌍의 목록
각 노드는 주기적으로 자신의 박동 카운터를 증가시킴
각 노드는 무작위로 선정된 노드들에게 주기적으로 자기 박동 카운터 목록을 보냄
박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버는 장애 상태인 것으로 간주

일시적 장애 처리

단서 후 임시 위탁 기법

네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리한다.
그동안 발생한 변경 사항은 서버가 복구 되었을 때 일괄 반영하여 데이터 일관성을 보존한다
장애 서버 대신 임시로 쓰기 연산을 처리한 서버에는 그에 관련한 단서를 남겨둔다

영구 장애 처리

반-엔트로피 프로토콜을 구현하여 사본들을 동기화
반-엔트로피 프로토콜은 사본들을 비교하여 최신 버전으로 갱신하는 과정을 포함한다
사본 간의 일관성이 망가진 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클 트리 사용

머클 트리

해시트리라고도 불린다. 대규모 자료 구조의 내용을 효과적이고 안전하게 검증 할 수 있다

동작 원리

키 공간을 버킷으로 나눈다
버킷에 포함된 각각의 키에 해시 함수를 적용해 해시 값을 계산한다
버킷 별로 해시 값을 계산 후에, 해당 해시 값을 레이블로 갖는 노드를 만든다
자식 노드(버킷 부터 시작)의 레이블부터 새로운 해시값을 계산해서 이진 트리를 상향식으로 구성한다

머클 트리 비교

각 머클 트리의 비교는 루트 노드의 해시 값을 비교하는 것으로 시작
루트 노드의 해시 값이 일치하면 두 서버는 같은 데이터를 가짐
다른 데이터를 갖는 버킷을 찾고 그 버킷들만 동기화

요약

목표/문제	기술
대규모 데이터 저장	안정 해시를 사용해 서버들에 부하 분산
읽기 연산에 대한 높은 가용성 보장	데이터를 여러 데이터센터에 다중화
쓰기 연산에 대한 높은 가용성 보장	버저닝 및 벡터 시계를 사용한 충돌 해소
데이터 파티션	안정 해시
점진적 규모 확장성	안정 해시
다양성(heterogeneity)	안정 해시
조정 가능한 데이터 일관성	정족수 합의
일시적 장애 처리	느슨한 정족수 프로토콜과 단서 후 임시 위탁
영구적 장애 처리	머클 트리
데이터 센터 장애 대응	여러 데이터 센터에 걸친 데이터 다중화