요즘 개발자를 위한 시스템 설계 수업 - 3장 분산 시스템의 이론과 데이터 구조 2

3.3 비잔티움 장군 문제

신뢰성과 장애 허용성을 논할 때 등장하는 개념

여러 하위 시스템 중 일부가 오류를 발생시키거나 잘못된 명령을 전달할 때, 나머지 시스템이 어떻게 정상 기능을 유지하며 작동할 수 있는지를 고민하는 일종의 사고 실험

분산 시스템에서 일부 노드가 잘못된 정보를 전달하거나 의도치 않은 데이터를 퍼뜨리는 상황에서도 신뢰성과 장애 허용성을 확보

해결 방법

• 투표 알고리즘
• 반복 서명 방식
• 쿼럼 방식
• 타임아웃과 확인 절차
• 무작위 선택 방식

 

핵심은 투표로 배신자 색출, 나머지 인원만으로도 합의할 수 있도록 중복성을 확보하는 것

 

3.3.1 비잔티움 장애

소프트웨어 버그가 아닌 하드웨어 레벨에서도 비잔티움 에러는 발생 가능. 예컨대 우주선이나 항공기의 RAM에서 우주 방사선으로 인한 Bit Flip (비트 반전)이 발생하면, 완벽히 정상 작동하는 시스템도 다른 컴포넌트에게 오염된 데이터를 전송하는 악성 노드로 돌변할 수 있어 ECC 메모리와 하드웨어 레벨의 TMR(Triple Modular Redundancy)이 필수

3.3.2 비잔티움 장애 허용성

일부 노드가 고장 나거나 악의적으로 행동하더라도 시스템이 올바르게 가능하며 합의에 도달할 수 있는 성질

초기 버전은 고장 노드 비율이 ⅓ 인 경우에만 정상 동작, 모든 노드가 서로 통신해야 하므로 계산 및 통신 비용이 많이 소모됨 

3.3.3 최신 비잔티움 장애 허용성

기존 단점인 통신 비용을 줄이고, 대규모 네트워크에서 효율적으로 동작 가능한 합의 매커니즘을 사용

비트코인의 경우 확정적 합의를 포기하고, 확률적 합의와 작업 증명(PoW)을 도입해 경제적으로 해결

3.4 FLP 불가능성 정리

하나의 노드에 문제가 생겼을 때 완전 비동기 환경에서는 모든 노드가 동일한 결정을 내리도록 하는 것이 불가능하다는 이론

 

완전한 비동기 시스템에서는 메시지 전달 시간의 상한선 없다는 것을 알아야 이해가 됨

전제 조건

• 비동기성
• 프로세스 장애
• 유한한 단계

 

메시지 도착 시간의 보장이 없는 순수 비동기 모델에서는, 저기 응답 없는 노드가 "죽은 것"인지 "단지 아주 느린 것"인지 절대 알 수 없음, 이런 모호함 때문에 신뢰할 수 있는 합의에 도달하기 어려움

 

극복 방법

• 메시지 지연 시간을 설정
• 합의에 확률 알고리즘 사용
• 무작위 요소나 시간 동기화 방식 도입
• 리더 선출, 조정자 역할 두기

3.5 일관된 해싱

데이터를 여러 노드에 효율적으로 분배하면서 노드를 추가하거나 삭제할 때 데이터 위치를 다른 곳으로 옮겨야 하는 과정이 최소화되도록 하는 방식

 

시스템의 확장성과 장애 허용성에 영향을 줌

 

일반적으로 해시 함수는 모듈로 해싱 방식으로 보통 이해를 함. 

key 값을 해싱 후 해싱된 값을 노트 수 만큼 나누고 나머지를 사용하는 방식, 나머지는 노드의 인덱스가 된다.

위 방식의 치명적인 문제점은 노드 추가, 삭제 및 해시 알고리즘 변경 시 전부 재계산이 필요하기 때문에 시스템 가용성을 떨어트림

 

일관된 해싱이 해결하고자 하는 주요 문제는 분산 시스템의 확장성과 장애 허용성

노드 추가, 삭제 시 전체 재계산이 아닌 일부 데이터만 이동하여 영향을 최소화하는 것이 목표

해시 공간은 원 모양 순환 구조

각 노드는 식별자로 데이터는 키 값으로 해시 함수 값에 따라 링 위에 흩뿌려져 있음.

키 위치에 따라 시계 방향에서 처음 만나는 노드가 해당 데이터를 처리, 이 노드를 `담당 노드`, `관리 노드`라 함

링모양의 문제점

• 실제 요청이 균등하게 분배되지 않을 수 있다
• 노드 하나 다운되면 그 다음 노드 작업량이 급증해 또 다운되는 연쇄 반응이 발생할 수 있음

 

위 문제를 극복하기 위해서 노드 마다 추가 가상 지점을 해시 링에 더 흩뿌려 놓음

이 방식은 더 촘촘하게 노드가 분포되어 있어 하나 노드가 죽어도 훨씬 균등하게 부하가 분산 됨

반대로 노드를 추가할 때도 근처 데이터만 재매핑하면 되기 때문에 부하가 적음

 

가상 노드의 추가적 이점은 기존 노드가 1의 성능 신규 노드가 4의 성능인 경우 4의 노드에 가상 노드를 4배 더 부과하여 부하를 균등하게 관리할 수도 있다

해시 알고리즘은 CPU 연산속도가 중요하기 때문에 CPU 캐시 친화적 알고리즘을 쓰는 것이 유리

 

3.6 블룸 필터

메모리 적게 사용하면서 특정 요소가 집합에 속해 있는지 빠르게 확인할 수 있는 확률적 데이터 구조

해시 함수와 비트 배열 기반

어디까지나 확률이기 때문에 거짓 양성이 나올 수 있음

해시 개수와 배열 크기를 조정해 거짓 양성 확률을 줄일 수 있음

사용 사례

• 포함 여부 검사
• 캐싱
• 데이터베이스 최적화
• 네트워크 라우팅
• 중복 제거

 

거짓 양성: 데이터가 없는데도 있다고 잘못 판별하는 것. 블룸 필터가 가진 태생적 한계이자 받아들여야 하는 경제적 확률

거짓 부정: 데이터가 있는데도 없다고 판별하는 것. 블룸 필터에서는 절대 발생하지 않음

 

블룸 필터에서 비트는 0으로 바꾸지 못한다. 이유는 다른 값들과 비트를 공유하는 형태이기 때문인데 그래서 삭제 연산을 지원 못한다. 

확률적 구조이기 때문에 설정한 비트 배열에서 1로 설정된 값이 전체 비트 수에서 50%를 넘기 시작하면 거짓 양성이 발생할 확률이 기하급수적으로 증가하기 때문에 모니터링하여 스케일을 키워야 한다.

 

3.7 카운트–민 스케치

• 데이터 스트림에서 요소의 빈도를 추정하는 확률적 데이터 구조
• 메모리가 제한된 환경과 대규모 데이터 스트림 실시간 처리에 효과적
• 이차원 배열 형태로 카운터가 구성
• 행과 열 수는 정확도와 오류율로 결정됨
• 데이터가 아무리 많아도 설정해둔 메모리는 고정, 다만 충돌 확률이 올라갈 
• 각 요소 마다 해시 함수들을 실행 각 해시 함수마다 나온 값을 배열 위치에 카운팅해 빈도 측정
• 최종적으로 빈도를 측정하려면 해당 요소(값)에 대한 해시 값들 중 최소값을 찾으면 됨(확률)

 

사용처

• 빈도 추정
• 트래픽 분석
• 웹 분석
• 분산 시스템
• 데이터 스트림 처리

3.8 하이퍼로그로그

• 집합 내 중복되지 않은 요소 개수를 적은 메모리로 파악하는 데 사용하는 확률적 알고리즘
• 집합 크기와 상관없이 고정된 양의 메모리
• 비트 스트림에서 끝자리가 `0` 개수로 근사치 추정
• 데이터 샘플이 작으면 추정 값이 더욱 흔들림

방문자 수 측정 방법

• 사용자 이름 해시 값을 무작위로 버킷 k 개로 나눔
• 각 버킷에서 끝에 연속된 0의 최대 개수를 계산
• 전 단계에서 계산한 끝자리 0의 개수를 각 버킷에 저장
• 모든 버킷에서 구한 값을 바탕으로 L 계산, 이때 조화 평균을 사용하기 때문에 하이퍼로그로그라는 이름을 붙임
• 마지막으로 2(L+1) 계산하여 방문자 수 측정

메모리 사용량 추정

2(L+1)  = 방문자수 10억 명

L =  log2(10억) = 29.897352853986263(L) + 1 = 30

log2(30) = 4.906890595608519 = 4 + 1 = 5

5bit 

 

+1 을 하는 이유는 2진수 체계는 0,1을 표현하는 경우의 수이기 때문에 해당하는 값을 표현하려면 2진수가 표현할 수 있는 경우의 수 범위 안에 들어와야 하기 때문

조화 평균

• '가장 작은 값'에 강력한 가중치를 부여하는 수학적 특성을 지님. 따라서 극단적으로 큰 이상치가 발생해도 전체 지표가 오염되는 것을 방지
• 이 말은 역으로 높은 값이 나오다가 되려 작은 값이 이상치로 나온다면 전체 지표가 오염됨

API 요청 속도에 따라 산술 평균, 조화 평균 값

비교 항목	Case A (10, 10, 1000)	Case B (1000, 1000, 10)
산술 평균 (AM)	340.0 ms	670.0 ms
조화 평균 (HM)	14.93 ms	29.41 ms
영향력 분석	10ms가 2개라 거의 10에 고정	1000이 2개지만 여전히 10의 힘이 강함

Case B를 보면 1000이 정상이고 10이 비정상일 경우 되려 값이 왜곡된다.