가상 면접 사례로 배우는 대규모 시스템 설계 기초 4장 ~ 6장

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

처리율 제한 장치(rate limiter)

• 처리율 제한 장치는 클라이언트나 서비스가 보내는 트래픽의 처리율을 제어하기 위한 장치다.
• HTTP에선 API 요청 횟수가 제한 장치에 정의된 임계치(threshold)를 초과하면 다른 모든 호출은 처리가 중단(block)된다.
  • 사용자는 초당 2회 이상 새 글 생성 불가
  • 같은 ip 주소로 하루 10개의 계정 생성 제한
  • 같은 디바이스 주 5회 이상 리워드 요청 불가

처리율 제한 장치의 이점

• DoS 공격에 의한 자원 고갈 방지
• 비용 절감
  • 서버 부하를 줄여 서버 비용을 절감할 수 있다.
  • 제 3자(third-party) API에 사용료를 지불할 경우 매우 중요함.
• 서버 과부하 방지
  • 봇에 의한 트래픽이나 사용자의 잘못된 이용 패턴으로 유발된 트래픽을 걸러낼 수 있음

1단계 - 문제 이해 및 설계 범위 확정

• 어떤 종류의 처리율 제한 장치를 만들어야 하는가?
  • Q) 클라이언트 측인지, 서버 측 제한 장치인지?
    • A) 서버측 API를 위한 장치를 설계
• 어떤 기준을 사용해 API 호출을 제한 할 것인가?
  • Q) IP/사용자 ID 또는 다른 기준?
    • A) 다양한 형태의 제어 규칙(throttling rules)를 정의할 수 있는 유연한 시스템
• 시스템 규모는?
  • Q) 스타트업/큰 기업
    • A) 대규모 요청을 처리할 수 있어야함.
• Q) 분산 환경에서 동작하는가?
  • A) 넹
• Q) 처리율 제한 장치는 독립된 서비스인가, 애플리케이션 코드에 포함될 수 있는가?
  • A) 본인 선택
• Q) 사용자의 요청이 limiter에 의해 걸린 경우 사용자에게 알려야 하는가?
  • A) 넹
• 요약된 요청 사항
  • 설정된 처리율을 초과하는 요청은 정확하게 제한
  • 낮은 응답 시간
    • HTTP 응답 시간에 악영향을 주면 안됨
  • 가능한 적은 메모리 사용
  • 분산형 처리율 제한
    • 하나의 limiter를 여러 서버나 프로세스에서 공유 가능
  • 예외 처리
    • 요청이 제한되면 사용자가 알 수 있어야함
  • 높은 내결함
    • limiter에 장애가 생겨도 시스템에는 영향을 주면 안됨

2단계 개략적 설계안 제시 및 동의 구하기

• 처리율 제한 장치를 어디에 둘 것인가?
  • 클라/서버 둘 다 가능
  • 클라
    • 안정적이지 못함
    • 위변조가 쉽게 가능
    • 모든 클라의 구현을 통제하는 것이 어려움
  • 서버
    • API 서버 뒤에 위치
    • 클라와 API 서버 사이 미들 웨어로 사용
    • 클라우드 마이크로 서비스에서는 보통 API 게이트웨이라 불리는 컴포넌트에 구현됨
      • API 게이트웨이
        • 처리율 제한, SSL 종단, 사용자 인증, IP 허용 목록 관리 등 지원
• rate limiter 설계 시 중요한 것
  • 서버에 두드냐, 게이트웨이에 두느냐?
    • 회사의 기술 스택과 인력, 목표 등에 따라 매우 달라짐
  • 기술 스택을 점검하고 서버 측 구현을 지원하기 충분한가?
  • 서버 측에서 모든 것을 구현
    • 알고리즘에서 자유로움
  • third-party 게이트웨이 서비스 사용
    • 선택지가 제한적
    • 비용이 들 수 있음
    • 간편함
  • 이미 마이크로서비스에 기반하고 사용자 인증이나 IP 허용 목록 관리 등을 위해 API 게이트웨이가 있다면 게이트웨이에 포함할 수 있음
  • 직접 구현은 시간과 자원이 모소됨

처리율 제한 알고리즘

• Token Bucket
  • 토큰 버킷 알고리즘은 토큰을 일정한 속도로 생성하는 버킷에 토큰을 담아두고, 요청이 들어올 때마다 토큰을 소비하는 방식
  • 토큰이 없으면 요청을 거부
  • 인터넷 기업들이 보편적으로 사용
  • 토큰 버킷 알고리즘은 2개의 파라미터를 받음
    • 버킷 크기 : 버킷에 담을 수 있는 최대 토큰의 수
    • 토큰 공급률(refill rate) : 초당 몇 개의 토큰이 버킷에 공금되는지
  • 통상적으로 API 엔드포인트마다 별도의 버킷이 존재.
  • IP 주소에 따른 제한을 적용 시 IP 주소마다 버킷을 할당해야함.
  • 시스템 천제의 처리율을 제한하고 싶다면 모든 요청이 하나의 버킷을 공유하도록 해야 함.
  • 장점
    • 구현이 쉬움
    • 메모리 사용 측면에서도 효율적
    • 짧은 시간 집중되는 트래픽도 처리 가능.
    • 남은 토큰만 있다면 요청이 시스템에 전달됨
  • 단점
    • 버킷 크기와 토큰 공급률이라는 파라미터를 적절하게 튜닝하는 것이 까다로움
    • 트래픽이 갑자기 증가하면 토큰 버킷 알고리즘은 이를 처리할 수 없음
• Leaky Bucket
  • 토큰 버킷과 비슷하지만, 요청 처리율이 고정되어 있음
  • 보통 FIFO 큐로 구현
  • 동작 원리
    • 요청이 도착하면 큐가 pull인지 확인.
    • 빈자리가 잇을 경우 큐에 요청을 추가
    • 큐가 가득 찬 경우 새 요청은 버림.
    • 지정된 시간마다 큐에서 요청을 꺼내 처리
  • 알고리즘이 사용하는 두 파라미터
    • 버킷 크기 : 큐 사이즈와 같은 값으로 큐에서 처리될 항목들이 보관됨
    • 처리율(outflow rate) : 지정된 시간당 몇 개의 항목을 처리할지 지정하는 값, 보통 초 단위로 표현
  • 장점
    • 큐 크기가 제한되어 있어 메모리 사용량 측면에서 효율적
    • 고정된 처리율을 갖고 있기 때문에 안정적 출력(stable outflow rate)이 필요한 경우에 적합
  • 단점
    • 단 시간에 많은 요청이 몰리면 큐에 오래된 요청이 쌓여서 최신 요청들이 버려지게 됨
    • 두 파라미터에 대한 튜닝이 까다로움
• Fixed Window Counter
  • 타임 라인을 고정된 간격의 윈도우로 나누고, 각 윈도우마다 카운터를 붙임
  • 요청이 접수될 대마다 이 카운터의 값은 1씩 증가
  • 카운터 값이 사전에 설정된 임계치에 도달하면 새로운 요청은 새 윈도우가 열릴 때까지 버려짐.
  • 윈도우의 경계 부근에서 순간적으로 많은 트래픽이 집중되면 할당량보다 더 많은 요청이 처리될 수 있다.
  • 장점
    • 메모리 효율이 좋다
    • 이해하기 쉽다
    • 윈도우가 닫히는 시점에 카운터를 초기화하는 방식은 특정한 트래픽 패턴을 처리하기 적합하다
  • 단점
    • 윈도우 경계 부근에서 일시적으로 트래픽이 많이 몰리면 기대했던 처리한도보다 더 많은 요청을 처리하게 됨.
• Sliding Window Log
  • 고정 윈도우 카운터 알고리즘의 경계 부근 트래픽 집중을 해결
  • 동작 원리
    • 요청의 타임스탬프를 추적
      • 타임스탬프 데이터는 보통 레디스의 정렬 집합 같은 캐시에 보관
    • 새 요청이 들어오면 만료된 타임스탬프는 제거.
      • 만료된 타임스탬프 : 그 값이 윈도우의 시작 시점보다 오래된 타임스탬프
    • 새 요청의 타임스탬프를 로그에 추가
    • 로그의 크기가 허용치보다 같거나 작으면 요청을 시스템에 전달. 그렇지 않은 경우에는 처리를 거부
  • 장점
    • 처리율 제한 메커니즘이 아주 정교함
    • 어느 순간의 윈도우를 봐도 허용되는 요청의 개수는 시스템의 처리율 한도를넘지 않음
  • 단점
    • 거부된 요청의 타임스탬프도 보관하기에 다량의 메모리를 사용함
• Sliding Window Counter
  • 고정 윈도우 카운터와 이동 윈도우 로깅 알고리즘을 결합한 것
  • 두 가지 접근법이 사용될 수 있는데, 일단 하나만 설명
  • 요청 수 계산
    • 1분간의 요청 수 + (직전 1분간의 요청 수 * 이동 윈도우와 직전 1분이 겹치는 비율)
  • 장점
    • 이전 시간대의 평균 처리율에 따라 현재 윈도우의 상태를 계산하므로 짧은 시간에 몰리는 트래픽에도 잘 대응한다
    • 메모리 효율이 좋다
  • 단점
    • 직전 시간대에 도착한 요청이 균등하게 분포되어 있다고 가정한 상태에서 추정치를 계산해서 다소 느슨함
      • 하지만, 클라우드 플레어에서의 실험에 따르면 40억개 중 시스템의 실제 상태와 맞지 않게 허용되거나 버려진 요청은 0.003%에 불과

개략적인 아키텍처

• 카운터 값에 따라서 요청을 처리할지 거부할지 결정하는 서비스를 만들어야 함
• DB는 디스크 접근으로 인해서 느리므로 캐시가 바람직함
  • 빠르고 시간에 기반한 만료 정책을 지원
  • 레디스는 INCR와 EXPIRE 두 가지 명령어 지원
    • INCR : 메모리에 저장된 카운터의 값을 1만큼 증가
    • EXPIRE : 카운터의 타임아웃 값을 설정. 설정된 시간이 지나면 카운터는 자동 삭제

3단계 - 상세 설계

처리율 제한 규칙은 어떻게 만들어지고 어디에 저장되는가?

• 어떤 요청이 한도 제한에 걸리면 API는 429 응답을 클라이언트에게 보낸다.
• 클라이언트가 자신의 요청이 제한에 걸리고 있는지 감지하는 방법
  • HTTP 응답 헤더
    • X-RateLimit-Reamaining : 윈도우 내에 남은 처리 가능 요청의 수
    • X-RateLimit-Limit : 제한된 요청 수
    • X-RateLimit-Retry-After : 한도 제한에 걸리지 않으려면 몇 초 뒤에 요청을 다시 보내야 하는지 알림
• 분산 환경에서의 처리율 제한 장치의 구현
  • 문제점
    • 경쟁 조건(동시성 이슈)
      • 락은 시스템 성능을 상당히 떨어뜨린다는 문제가 있음
      • 루아 스크립트
      • 레디스의 자료 구조 중 하나인 정렬 집합 사용
    • 동기화
      • 여러 대의 처리율 제한 장치를 두게되면 서로 동기화가 필요함
      • 고정 세션
        • 항상 같은 처리율 제한 장치로 요청을 처리
        • 확장도 어렵고 유연하지 않음
      • 레디스 같은 중앙 집중형 데이터 저장소 사용
• 성능 최적화
  • 데이터 센터에서 멀리 떨어진 사용자의 경우 지연 시간이 길어질 수 있음
  • 제한 장치 간의 데이터 동기화 시 최종 일관성 모델을 사용하는 것

4단계 - 마무리

• 추가적인 고도화
  • 경성 또는 연성 처리율 제한
    • 경성 처리율 제한
      • 요청의 개수는 임계치를 절대 넘어설 수 없ㅁ다.
    • 연성 처리율 제한
      • 요청 개수는 잠시 동안은 임계치를 넘을 수 있음
    • 다양한 계층에서 처리율 제한
      • 애플리케이션 계층에서만 적용했지만, 다른 계층에서도 가능
      • Iptable을 사용하면 IP 주소에 제한 적용 가능
  • 처리율 제한을 회피하는 방법
    • 클라이언트 측 캐시를 이용해 API 호출 횟수를 줄인다
    • 짧은 시간 너무 많은 메시지를 보내지 않도록 한다
    • 예외나 에러 처리 코드를 도입해 클라가 예외적 상황으로부터 우아하게 복구될 수 있게 한다.
    • 재시도 로직을 구현 시 충분한 백오프 시간을 둔다

5장 - 안정 해시 설계

해시 키 재배치(rehash) 문제

• serverIndex = hash(key) % N(서버의 개수)
  • 보편적으로 균등하게 나누는 해시 함수
  • 서버 풀의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때 좋은 해결책임
  • 서버 추가/삭제 에서 문제가 발생
    • 4개의 서버가 동작하는 환경에서 1개가 죽으면 N이 3으로 줄게되어 키 분포가 달라지게 된다.
      • 장애가 발생한 서버 뿐 아니라 다른 서버에 보관된 키도 전부 재분배 되게 되었음.
      • 이로 인해서 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 됨
      • 대규모 캐시 미스 발생 가능성을 초래
      • 안정 해시를 통해 이를 해결할 수 있음.

안정 해시

• 수평 규모 확장을 위해서는 서버에 균등하게 요청과 데이터를 나누는 것이 중요함.
• 이를 달성하기 위해서 보편적으로 사용
• 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시 기술이다.
  • K는 키의 개수, n은 슬롯의 개수
  • 안정 해시와 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 대부분 키를 재배치한다.

해시 공간과 해시 링

• 해시 함수로 SHA-1을 사용 시
  • SHA-1의 해시 공간의 범위는 0 ~ 2^160 - 1
    • x0 = 0
    • xn = 2^160 - 1
  • 이 해시 공간을 구부려 접어서 해시 링을 만들 수 있다.

해시 서버

• 위에서 만든 해시 함수 f를 이용해 서버 IP나 이름을 해시 링 위의 어떤 위치에 대응시킬 수 있음

해시 키

• 해시 키 또한 해시 링 위의 어떤 점에 위치시킬 수 있음.
  • 해시 키 재배치 문제와 다름
  • 나머지 연산을 사용하고 있지 않음.

서버 조회/추가/제거

• 어떤 키가 저장되는 서버는 해당 키의 위치에서 시계 방향으로 가장 처음 만나는 서버임.
• 따라서 서버를 추가하더라도 키 가운데 일부만 재배치하면 됨.
• 자연스럽게 서버 제거에서도 키 가운데 일부만 재배치될 뿐임.

기본적인 구현법

• 서버와 키를 균동 배포 해시 함수를 사용해 해시 링에 배치
• 키의 위치에서 시계 방향으로 탐색해서 최초로 만나는 서버가 키가 저장될 서버가 됨.

두 가지 문제점

• 서버 추가/제거 등의 상황을 감안하면 균등하게 파티션 크기를 유지하는 게 불가능함.
• 키의 균등 분포를 달성하기 어렵다.
  • 이 문제를 해결하기 위해 가상 노드(virtual node) 또는 복제(replica)라 불리는 기법이다

가상 노드

• 실제 노드를 가리키는 노드
  • 하나의 서버는 여러 개의 가상 노드를 가질 수 있다.
  • 실제 시스템에서는 아주 많은 가상 노드를 설정한다.
• 여러 개의 가상 노드를 배치하여 각 서버는 하나가 아닌 여러 개의 파티션을 관리하게 된다.
• 가상 노드의 개수가 늘어날 수록 키 분포는 균등해짐
  • 표준 편차가 작아서 데이터가 고르게 분포되기 때문임
• 표준 편차는 점점 떨어지지만, 가상 노드의 데이터를 저장할 공간은 더 많이 필요해짐.
  • 타협적 결정이 필요해짐.

Q) 파티션을 잘게 쪼갠다는 말은 낭비되는 지점이 많이 생길 수 있게 됨. 이런 경우는 해결법이 있는 것인지, 아니면 무시하는 것인지?

• 사용되지 않는 유휴 공간, 조각 공간이 많이 생김

안정 해시의 이점

• 서버 추가/삭제 시 재배치되는 키의 수 최소화
• 데이터가 균등하게 분포되므로 수평적 규모 확장성에 유리함
• 핫스팟 키 문제를 줄인다.
  • 특정 샤드에 대한 접근이 빈번하면 서버 과부하가 생길 수 있음.

6장 - key-value 저장소 설계

• key-value pair
  • key-value DB에 저장되는 값은 고유 식별자를 키로 가져야 함
• key는 유일해야함.
• value는 쌍이 되는 key를 통해서만 접근할 수 있다.
• key는 일반 텍스트일 수도 있고, 해시 값일 수도 있다.
• value는 문자열, 리스트, 객체 등이 될 수 있고, 보통 value에 어떤 것이 오든 상관하지 않는다.

문제 이해 및 설계 범위 확정

요구 사항

• key-value 쌍의 크기는 10KB 이하이다.
• 큰 데이터를 저장할 수 있어야 한다.
• 높은 가용성을 제공해야 한다.
  • 장애가 있어도 빠르게 응답해야함
• 높은 규모 확장성을 제공해야 한다.
  • 트래픽 양에 따라 자동적으로 서버 증설/삭제가 되어야 함.
• 데이터 일관성 수준을 조정할 수 있어야 한다.
• latency가 짧아야 함.

단일 서버 key-value 저장소

• key-value pair를 전부 메모리에 해시 테이블로 저장
  • 가장 직관적임.
  • 속도는 빠름
  • 모든 데이터를 메모리 안에 두는 것은 불가능함.
  • 개선책
    • 데이터 압축(compression)
    • 자주 쓰는 데이터만 메모리에 적재하고 나머지는 디스크에 저장

qnstks key-value 저장소

CAP 정리

• 세 가지 요구 사항
  • 데이터 일관성(consistency)
    • 분산 시스템에 접속하는 모든 클라이언트는 접속한 노드에 상관 없이 언제나 같은 데이터를 보게 됨
  • 가용성(availability)
    • 일부 노드에 장애가 발생해도 항상 응답을 받을 수 있어야함.
  • 파티션 감내(partition tolerance)
    • 파티션 감내는 네트워크에서 두 노드 사이에서 통신 장애가 발생해도 시스템은 계속 동작해야 함.
      • 파티션 : 두 노드 사이에 통신 장애가 발생
• 위 세 가지 요구 사항을 만족하는 분산 시스템은 불가능하다는 정리
• CP 시스템
  • 일관성과 파티션 감내를 지원하는 key-value 저장소
  • 가용성을 희생
• AP 시스템
  • 가용성과 파티션 감내를 지원하는 key-value 저장소
  • 데이터 일관성을 희생
• CA 시스템
  • 일관성과 가용성을 지원하는 key-value 저장소
  • 파티션 감내를 의생
  • 통상 네트워크 장애는 피할 수 없는 일로 여겨짐
  • 분산 시스템은 반드시 파티션 문제를 감내할 수 있어야 함.
  • CA 시스템은 실 세계에 존재하지 않음.

실세계의 분산 시스템

• 분산 시스템은 파티션 문제를 피할 수 없음.
• 따라서 일관성과 가용성 사이에서 하나를 선택해야 함.

A, B, C 세 개의 서버 환경에서 C 서버에 장애 발생 시

• 일관성을 선택할 경우 (CP 시스템)
  • 불일치 문제를 해결하기 위해 장애가 발생하지 않은 A와 B에 대해서 쓰기 연산을 중단해야함.
    • 가용성이 깨지게 됨.
    • 은행권 시스템은 보통 데이터 일관성을 양보하지 않음.
• 가용성을 선택할 경우 (AP 시스템)
  • 낡은 데이터를 반환할 위험이 있더라도 계속 읽기 연산을 허용해야 함.
  • 장애가 발생하지 않은 A, B에 계속 쓰기 작업이 일어나고, 장애 해결 후 C에 새 데이터를 전송함.

데이터 파티션

• 데이터를 작은 파티션들로 분할하여 여러 서버에 저장
• 데이터 파티션 시 중요하게 다뤄야할 문제
  • 데이터를 여러 서버에 고르게 분산할 수 있는가
  • 노드가 추가되거나 삭제 시 데이터 이동을 최소화할 수 있는가
• 안정 해시를 사용하면 위의 문제를 풀기에 적합하다.
  • 규모 확장 자동화
    • 시스템 부하에 따라 서버가 자동으로 추가되거나 삭제됨
  • 다양성
    • 각 서버의 용량에 맞게 가상 노드의 수를 조정할 수 있다.

데이터 다중화

• 높은 가용성과 안정성을 위해 데이터를 N 개의 서버에 비동기적으로 다중화할 필요가 있다.
• 가상 노드 선택 시 선택한 N개의 노드가 대응될 실제 물리 서버의 개수 N보다 작아질 수 있다.
  • 노드 선택 시 같은 물리 서버를 중복 선택하지 않도록 해야 함.
• 실제 같은 물리 서버에 저장되면 여전히 안정성에 문제가 생길 수 있음.
  • 안정성 확보를 위해 데이터 사본은 다른 센터의 서버에 저장하고, 고속 네트워크로 연결되어야 함.

데이터 일관성

• 여러 노드에 다중화된 데이터는 적절히 동기화 되어야 함.
• 정족수 합의(Quorum Consensus) 프로토콜을 사용하면 읽기/쓰기 연산 모두에서 일관성을 보장할 수 있다.
  • N : 사본 개수
  • W : 쓰기 연산에 대한 정족수, 쓰기 연산이 성공했다고 하기 위해서는 적어도 W 개의 서버에서 쓰기 연산 성공에 대한 응답을 받아야 함.
  • R : 읽기 연산에 대한 정족수, 읽기 연산이 성공한 것으로 간주되려면 적어도 R 개의 서버로부터 응답을 받아야 한다.
• 중재자(coordinator)는 클라이언트와 노드 사이 프록시 역할을 함.
• W + R > N
  • 강환 일관성이 보장됨
• R = 1 && W = N
  • 빠른 읽기 연산에 최적화된 시스템
• W = 1 && R = N
  • 빠른 쓰기 연산에 최적화된 시스템
• W + R > N
  • 강한 일관성이 보장됨 (보통 N = 3, W = R = 2)
• W + R <= N
  • 강한 일관성이 보장되지 않음

일관성 모델

• 강한 일관성
  • 모든 읽기 연산은 가장 최샌 결과를 반환
  • 클라이언트는 절대 낡은 데이터를 보지 못함
  • 모든 사본에 현재 쓰기 결과가 반영될 때까지 해당 데이터에 대한 읽기/쓰기를 금지
  • 새로운 요청 처리가 중단되기에 고가용성이 떨어지게됨.
• 약한 일관성
  • 읽기 연산은 가장 최신 결과를 반환하지 못할 수 있음
• 최종 일관성
  • 다이나모와 카산드라 등이 채택함.
  • 약한 일관성의 한 형태
  • 갱신 결과가 결국에는 모든 사본에 반영(동기화)되는 모델
  • 쓰기 연산이 병렬저긍로 일어나면 시스템에 저장된 값의 일관성이 깨질 수 있음.
    • 이를 클라이언트가 해결해야 함.
    • 비 일관성 해소 기법 : 데이터 비저닝
      • 데이터 변경 시 마다 해당 데이터의 새로운 버전을 만듦
        • 각 버전의 데이터는 immutable임
      • 벡터 시계
        • 데이터에 [서버, 버전] pair를 매닮
        • 선행 버전과 후행 버전, 다른 버전과 충돌 판별에 사용됨
        • 어떤 버전 X가 버전 Y의 이전 버전인지 쉽게 판단할 수 있음.
        • 버전 Y에 포함된 모든 구성 요소의 값이 X에 포함된 모든 구성요소 값보다 같거나 큰지만 보면 됨.
        • 단점
          • 충돌 감지 및 해소 로직이 클라이언트에 들어가야 하므로 클라이언트 구현이 복잡해짐.
          • [서버, 버전] pair가 굉장히 빠르게 늘어남.
            • 어떤 임계치를 설정하고 임계치 이상 길어지면 오래된 순서쌍을 제거하도록 해야함.
            • 하지만, 이렇게하면 버전 간 선후 관계가 정확하게 결정될 수 없어서 충돌 해소 과정의 효율성이 감소함.
            • 아마존에서는 실제 서비스에서 이런 문제를 본 적은 없어서 괜찮을 것이라고 생각함.

장애 감지

• 분산 시스템에서는 한 대의 서버가 특정 서버가 죽었다고해서 바로 장애처리 하지 않고, 두 대 이상이 같은 장애를 보고해야 장애로 판단함.
• 모든 노드 사이에 멀티 캐스팅 채널을 구축하는 방법은 가장 쉽지만 비효율적임.
• gossip protocol 같은 분산형 장애 감지(decentralized failure detection) 솔루션을 선택하는 것이 효율적임.
• 가십 프로토콜
  • 각 노드는 멤버십 목록을 유지한다.
    • 멤버십 목록은 각 멤버 ID와 그 박동 카운터(heartbeat counter) 쌍의 목록임
  • 각 노드는 주기적으로 자신의 박동 카운터를 증가 시킴
  • 각 노드는 무작위로 선정된 노드에게 주기적으로 자신의 박동 카운터 목록을 보냄
  • 박동 카운터 목록을 받은 노드는 멤버십 목록을 최신 값으로 갱신
  • 어떤 멤버의 박동 카운터 값이 지정된 시간 동안 갱신되지 않으면 해당 멤버를 장애 상태로 간주함.

Q) 모든 노드가 서로 직접 통신하는가...?

일시적인 장애 처리

• 네트워크나 서버 문제로 장애 상태인 서버로 가는 요청은 다른 서버가 잠시 맡아 처리함.
  • 그 동안 발생한 변경 사항은 해당 서버가 복구되면 일관 반영해 데이터 일관성을 보존함.
  • 이를 위해서 임시로 쓰기 연산을 처리한 서버에는 이에 대한 hint를 남겨 둔다.
  • 이를 단서 후 임시 위탁(hinted handoff)라고 부른다.

영구 장애 처리

• 반-엔트로피(anti-entropy) 프로토콜을 구현해 사본들을 동기화
  • 반-엔트로피 프로토콜은 사본들을 비교해 최신 버전으로 갱신하는 과정을 포함함.
  • 사본 간의 일관성이 망가지 상태를 탐지하고 전송 데이터의 양을 줄이기 위해 머클(Merkle) 트리를 사용함.
    • 머클 트리는 각 노드에 그 자식 노드들에 보관된 값의 해시, 또는 자식 노드딀의 레이블로부터 계산된 해시 값을 레이블로 붙여두는 트리임.
    • 1단계
      • 키 공간을 버킷으로 나눈다.
    • 2단계
      • 버킷에 포함된 각각의 키에 균등 분포 해시 함수를 적용해 해시 값을 계산함
    • 3단계
      • 버킷별로 해시값을 계산 후 해당 해시 값을 레이블로 갖는 노드를 만든다.
    • 4단계
      • 자식 노드의 레이블로부터 새로운 해시 값을 계산해, 이진 트리를 상향식으로 구성해 나간다.
    • 각 서버의 루트부터 이진 트리를 비교해 하향식으로 틀린 부분을 찾아나간다.
    • 동기화해야 하는 데이터의 양은 실제로 존재하는 차이의 크기에 비례할 뿐임.
    • 두 서버에 보관된 데이터의 총량과는 무관함.
    • 하지만, 실제 시스템의 경우 버킷 하나의 크기가 꽤 크다.

요약

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