가상 면접 사례로 배우는 대규모 시스템 설계 기초 1편 - 여러 이슈 살펴보기

1. 들어가며

 

저번 글에서는 거시적인 관점에서 서버를 확장해나가면서 어떻게 구성될 수 있는지 살펴보았습니다.

https://rawshrimpsushi.tistory.com/50

가상 면접 사례로 배우는 대규모 시스템 설계 기초 1편 - 트래픽에 따른 서버 확장

 

이번 글에서는 규모 확장을 마친 각 서버의 구성 요소에서 어떤 이슈가 발생할 수 있는지, 어떻게 설계하면 좋은지 세부적으로 살펴보도록 하겠습니다.

 

2. 책 내용 정리

1) 서버 응답지연 값

 

대규모 설계를 하거나 최적화를 한다고 하면 제일 중요한 것은 측정치를 기반으로 움직이는 것이라 생각합니다! 제일 좋은 건 직접 측정하는 것이겠지만 그게 불가능할 경우 대략적으로 추정을 해볼 수도 있습니다.

그런 추정에 도움되는, 서버에서 주로 일어나는 연산에 대한 응답지연 값입니다. 컴퓨터구조 첫 단원에서도 나왔던 내용으로 기억합니다 :)

연산명	시간
L1 캐시 참조	0.5ns
분기 예측 오류	5ns
L2 캐시 참조	7ns
뮤텍스 락, 언락	100ns
주 메모리 참조	100ns
Zippy로 1KB 압축	10,000ns
1Gps 네트워크로 2KB 전송	20,000ns
메모리에서 1MB 순차적으로 Read	250,000ns
같은 데이터 센터 내에서의 메시지 왕복 지연시간	500,000ns
디스크 탐색	10,000,000ns
네트워크에서 1MB 순차적으로 read	10,000,000ns
디스크에서 1MB 순차적으로 read	30,000,000ns
한 패킷의 캘리포니아부터 네덜란드까지의 왕복 지연 시간	150,000,000ns

 

위 표에서 다음과 같은 내용을 추정해볼 수 있습니다.

 

• 메모리는 빠르지만 디스크는 느리다.
• 디스크 탐색은 가능한 한 피하라.
• 단순한 압축 알고리즘은 빠르다.
• 데이터를 인터넷으로 전송하기 전에 가능하면 압축해라.
• 데이터 센터는 보통 여러 지역에 분산되어 있고 센터들 간에 데이터를 주고 받는데는 시간이 걸린다.

 

2) 처리율 제한 서비스

 

• 정의: 클라이언트 또는 서비스가 보내는 트래픽의 처리율을 제어하는 장치
• 방법: API 요청 횟수가 임계치를 넘어서면 이후 모든 호출은 중단된다.
• 필요성: Dos 공격을 막거나 지나치게 많은 third party api 사용 요금을 줄이기 위해서 사용자의 서버 이용량을 제한을 둬야할 수 있습니다. 생각나는 실제 예시로는 chat GPT가 떠오릅니다. 또 예전에 네이버 메일을 기다릴 때 지나치게 많은 새로고침을 해서 잠시 제 접속을 거부했던 기억이 있습니다. 이처럼 거의 대부분의 대형 IT 서비스 기업은 처리율 제한 장치를 두고 있습니다. 
• 구현:보통 클라우드 마이크로 서비스인 경우 처리율 제한 장치는 API gateway에 구현됩니다. 물론 서버 로직에 포함시켜도 되며 정답은 없습니다. 다만 위변조의 가능성이 있는 클라이언트에 구현은 불가능할 것입니다.

- 주요 알고리즘

 

1. 토큰 버킷: 각 요청이 처리될 때마다 하나의 토큰을 사용하고 토큰이 없을 경우 해당 요청은 버려진다. 버킷 크기와 토큰 공급률(초당 몇 개의 토큰이 버킷에 공급되는가)를 정의한다. 각 토큰은 IP 주소마다 할당하던, 전체로 할당하던 달라진다.
2. 누출 버킷: FIFO 큐를 통해 요청이 도착되면 큐에 넣고 큐가 가득차면 버린다.
3. 고정 윈도 : 타임라인마다 고정된 윈도우를 할당하고 그 윈도우를 넘는 요청은 버린다. 순간적으로 많은 트래픽이 집중되면 윈도에 할당된 양보다 많이 처리될 수 있다.
4. 이동 윈도 로깅: 타임스탬프를 추적하여 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템이 전달한다.

 

그렇다면 각 카운터, 버킷토큰 등은 어디에 보관하면 좋을까요? 

캐시, 그리고 sticky session이 되지 않기 위해 REDIS도 적합해 보입니다. 특히 여러 사용자가 여러 인스턴스로 들어간다면 각각의 사용자 제한을 모든 인스턴스 단위로 하기 쉽지 않기 때문에 Redis는 좋은 선택입니다.

 

처리율 제한은 임계치를 절대 넘어설 수 없게 하거나 잠시 동안은 임계치를 넘어설 수 있게 하는 등 제한 방식도 다릅니다.

Race Condition in Redis
카운터, 버킷 토큰은 Race Condition에 빠져서는 안될 것입니다. 데이터베이스에서는 트랜잭션, Lock 등을 통해 경쟁 상태를 피하는데요. Redis에서는 어떨까요? 카운터, 버킷 토큰뿐만 아니라 Redis에 저장되는 다양한 값들에서도 중요한 이슈라고 할 수 있습니다.

기본적으로 Redis는 싱글 스레드로 동작하기 때문에 경쟁 상태에서 좀 더 자유롭습니다. 하지만 싱글 스레드도 Parallel할 수 없는 것이지 Concurrent 할 수는 있기에 경쟁 상태가 없는 건 아닙니다.

따라서 Redis에서 지원하는 트랜잭션을 사용하거나, 하나의 단위로 실행되는 Lua Script를 사용해야 합니다. 다만 싱글 스레드인만큼 각 트랜잭션 혹은 Lua Script는 가능한 한 짧은 로직이어야 합니다.

또 Redis Transation은 RDB의 Transaction 지원 범위보다 빈약한 편입니다. 또한 cluster mode에서는 지원하지 않습니다. Redis에서도 Lua Script가 더 낫다고 판단하여 추후 deprecate을 고려하고 있다고 합니다.
https://redis-doc-test.readthedocs.io/en/latest/topics/transactions/

 

 

3) 안정 해시설계

 

서버의 수평적 규모 확장을 위해서는 유저를 서버에 균등하게 나눠야 합니다. 이때 나누는 로직은 어떻게 짜면 좋을까요? 서버뿐만 아니라 데이터베이스를 샤딩할 때도 마찬가지일 것입니다.

이를 위해 안정 해시를 사용합니다.

정의: 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. k는 키의 개수 n은 slot의 개수이다.

해결: 안정 해시는 서버 풀의 크기가 변동될 때 각 user들의 해시가 바뀌면서 대규모 캐시 미스가 발생하는 것을 해결해줍니다.

 

구체적인 알고리즘은 다음 영상을 참조해주세요! (모르는 분입니다,,)

https://www.youtube.com/watch?v=1a4iG-SYWMc

 

 

4) 분산 시스템과 CAP 정리

 

분산 시스템은 이상적인 시스템을 꿈꾸었습니다만

 

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

• 데이터 일관성: 분산 시스템에 접속하는 모든 클라이언트는 어떤 노드에 접속했느냐에 관계없이 언제나 같은 데이터를 보게 되어야 한다.
• 가용성: 분산 시스템에 접속하는 클라이언트는 일부 노드에 장애가 발생하더라도 항상 응답을 받을 수 있어야 한다.
• 파티션 감내: 파티션은 두 노드 사이에 통신 장애가 발생했음을 의미한다. 그럴 경우 시스템은 계속 작동해야 한다.

위의 CAP theorem으로 불가능하다고 합니다. 왜 그럴까요?

 

이유:

통신 장애는 피할 수 없는 문제로 여겨집니다. 그렇다면 통신 장애가 발생했을 때 데이터 일관성과 가용성 둘다 챙길 수 없는 이유가 뭘까요?

여러 노드 중 한 노드가 망가지면 그 노드의 정보가 다른 노드들에 전달되지 않은 채 망가질 수 있습니다. 그럴 경우 가용성을 선택한다면 오래된 데이터일 수 있다는 리스크를 져야 하며, 일관성을 선택한다면 다른 시스템은 그 노드가 복구될 때까지 오류를 반환해야 합니다. 즉 양자택일을 할 수 밖에 없습니다.

 

그렇다고 해도 완화할 방법을 찾지 않아야 한다는 것은 아닙니다. 어떤 방법이 있을지 살펴보도록 하겠습니다.

 

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

 

• 정족수 합의 프로토콜
  여러 노드에 다중화된 데이터는 적절히 동기화하기 위해, 노드들이 정족수로 승인하는 알고리즘
  사실 매우 다양합니다.. 다음 글을 참조해주세요!
  https://seongjin.me/raft-consensus-algorithm/
• 데이터버저닝 - 벡터 시계
  다른 서버 인스턴스가 동시에 다른 변경 요청을 받는다면? 두 서버의 데이터는 일관성이 깨져버릴 수 있습니다. 이러한 문제를 해결하기 위해 벡터 시계를 사용합니다. 이 벡터 시계가 데이터버저닝 기법의 일종입니다.벡터 시계란 [서버, 버전]의 순서쌍을 데이터에 매단 것입니다. 만일 데이터가 기록되면 시스템은 [서버, 버전+1]을 기록합니다. 클라이언트가 다른 버전의 데이터를 읽는다면 해당 클라이언트가 충돌을 해소할 책임을 얻습니다. 
• 박동 카운터(Heartbeat Counter)
  각 서버마다 박동 카운터를 두고 각 서버가 자신의 박동 카운터를 증가시킵니다. 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 장애 상태인 것으로 간주합니다.
• 버클 트리
  부모 트리가 자식 트리 값들의 해시를 가지고 있고, 리프 노드에선 버킷으로 여러 값들이 저장되어있는데 각 값들은 본인 값의 해시를 가지고 있는 트리입니다. 이를 통해 다른 서버와 해시 값이 다른 것을 이진 탐색 유사값으로 찾아낼 수 있습니다. (각 리프노드의 버킷 크기에 따라 다르다.)

 

5) 그 외 읽어보면 재밌는 주제

 

• 분산시스템을 위한 유일 ID 생성기 설계
  • 유일해야 하며
  • 시간의 흐름에 따라 커져야 하고(시간 순 정렬이 가능하다.)
  • 대규모로 만들어낼 수 있어야 한다.
    • https://tech-monster.tistory.com/228
    • https://kjhoon0330.tistory.com/104
• 알림 서비스 구현
  • 메시지 큐 이용이 어떻게 될 수 있는지 읽어보기 좋습니다.
  • https://velog.io/@broccolism/알림-시스템-설계-대규모-시스템-설계-기초-10장
  • https://engineering.linecorp.com/ko/blog/about-messaging-hub-2