2부에 해당하는 분산 시스템에 관련된 알고리즘을 소개한다

• 들어가기 전에…
  • 일관성 모델: 동시에 수행되는 작업의 수행 순서를 정의하고 다른 참가자가 순서를 알 수 있도록 하는 모델
  • 결과적 일관성을 보장하는 시스템에서는 읽기 중에 노드 쿼럼(정족수)을 쿼리해 복제 노드 사이의 상태 불일치를 해결하는 로직을 사용 할 수 있다
  • 노드의 장애를 하트비트 프로토콜과 장애 검출기를 이용해 감지하고 이를 그룹에서 제외할 수 있다
  • 링크: 송신자와 수신자의 통신 방법을 추상화한 표현
    • 손실 허용 링크: 분산 시스템에서 송신자는 메시지의 전달 여부를 확인 할 수 없는 링크
    • 스터번 링크: 송신자가 메시지가 성공적으로 전달받았음을 의미하는 응답을 받을때 까지 계속 재시도하는 링크
    • 퍼펙트 링크: 메시지 순서와 재전송 문제를 해결한 링크
    • 링크의 전달
      • 최대 한 번 전달: 메시지를 전송한 후 전달 여부를 사실 상 신경 쓰지 않음
      • 최소 한 번 전달: 몇 번의 재시도 후에 응답을 받지 못하면 실패로 간주
      • 정확히 한번 전달:
        • 속성을 만족하기 위해서는 모든 노드는 공통 정보를 공유해야 한다
        • 모든 노드가 레코드의 상태에 동의해야 하기 때문
  • FLP 불가능 이론: 비동기 시스템은 항상 일정 시간 내에 합의에 도달 할 수 없다는 이론
    • 이를 해결하기 위해 일정 부분 동기성을 지녀 타임아웃을 사용할 수 있어야 한다
  • 장애 모델
    • 충돌: 프로세스가 알고리즘 수행을 중단하고 다른 프로세스에 더 이상 메시지를 보내지 않는 현상
    • 누락: 알고리즘의 단계 중 일부를 건너뛰거나 수행할 수 없는 등의 상태
    • 임의의 장애(비잔티움 장애): 프로세스가 알고리즘의 의도와 모순되는 방식으로 수행되는 상태
• 장애 감지
  • 라이브니스: 의도된 이벤트는 반드시 발생됨을 나타내는 속생
  • 안정성: 의도되지 않은 이벤트는 반드시 발생되지 않음을 나타내는 속성
  • 하트비트: 인근 프로세스에 자신의 활성 상태를 알리는 메시지를 전송
  • 핑: 원격 프로세스에 메시지를 보내 일정 시간에 내에 응답하는지 확인
  • 알고리즘
    • 타임 아웃 없는 장애 감지(하트비트 알고리즘)
      • 각 프로세스는 인근 프로세스 목록과 각 프로세스의 카운터를 저장하고 인근 프로세스에 하트비트 전송
      • 모든 프로세스가 메시지를 수신하면 전파를 중지하고 시스템의 장애 여부 판단
    • 하트비트 아웃 소싱(SWIM 프로토콜)
      • 주변 프로세스의 관점에서 프로세스의 라이브니스를 판단하는 방식
      • 응답하지 않는 프로세스가 존재할 때 주변 프로세스에 신호를 보내 응답하지 않는 프로세스가 응답하는지 체크하고 처음 프로세스에 장애 여부를 전달해 준다
    • 파이 누적 장애 감지
      • 슬라이딩 윈도우에 주변 프로세스의 마지막 하트비트 도착 시간을 기록한다
      • 다음 하트비트의 도착 시간을 예측하고 실제 시간과 비교해 장애 감지 정확성을 타나내는 불신도를 계산
      • 불신도가 높으면 장애로 판별
    • 가십 프로토콜
      • 각 노드는 전체 노드 목록과 각 노드의 하트비트 카운터 및 마지막 타임스탬프를 저장한다
      • 주기적으로 자신의 카운터를 업데이트하고 임의 노드로 전송한다
      • 특정 노드의 카운터가 일정 기간동안 업데이트되지 않으면 장애로 판단한다
• 리더 선출
  • 선출 알고리즘의 지속성(liveness)는 거의 항상 리더가 존재하고 선출 과정은 결국 완료됨을 보장한다
  • 리더 프로세스가 병목이 될 수 있어 파티션을 나누고 파티션 별로 리더를 선출하는 시스템이 많다
  • 리더를 선출하면 조정 오버헤드를 줄이고 알고리즘의 성능을 향상 시킬 수 있다
  • 알고리즘
    • 불리 알고리즘
      • 미리 지정된 프로세스 순위를 기반으로 선출
      • 스플릿 브레인과 선출 작업이 무한정 반복 되는 현상이 존재 할 수 있다
      • 차기 리더를 미리 지정해 장애를 감지한 프로세스가 차기 리더에게 알려 리더 역활을 하도록 개선된 버전이 존재한다
    • 초대 알고리즘
      • 선출 시 서로 자신의 그룹으로 초대하는 방식으로 리더 선정
      • 그룹 병합 시 필요한 메시지 수를 최소화하기 위해 큰 그룹의 리더가 항상 선출되는 편이 좋다
    • 링 알고리즘
      • 모든 노드를 링 형태로 연결돼 있고 각 노드는 링의 앞/뒤 토폴로지 정보를 가진다
      • 리더 장애 발생 시 한 쪽 방향으로 장애를 전파하고 다시 돌아오면 가장 높은 순위의 노드가 리더로 선출된다
• 복제와 일관성 모델
  • 복제 노드가 어떻게 작동해야 하고 읽기/쓰기 작업을 요청한 사용자에게 어떤 값을 반환해야 하는지 정의한 모델
  • CAP 이론
    • 일관성, 가용성, 분할 내성 사이의 트레이드 오프에 관한 이론
    • CP: 높은 일관성과 분할 허용. 정상적 처리보다 일관된 데이터가 중요한 시스템
    • AP: 일관성을 일부 포기하고 가용성이 중요한 시스템
    • CA: 비동기 시스템에서는 구현 불가능.
  • 선형화
    • 가능성: 단일 객체와 연산에 대해 가장 엄격한 모델.
    • 스테일 읽기(정확하지 않은 데이터)를 방지하고 단조 읽기(일단 어떤 값을 읽으면, 모든 후속 읽기가 정확히 현재 값 또는 새로운 값을 반환한다)만 허용한다
    • 이를 지원하기 위해 분산 시스템에서는 조정과 순서화가 필요하지만 많은 시스템이 지원하지 않는다
  • 순차 일관성 모델: 각 프로세스가 실제로 연산을 수행한 순서를 유지하면서 연산이 순차적인것처럼 보이도록 한 모델
  • 인과적 일관성 모델: 인과 관계가 성립하는 연산의 순서는 모든 프로세스에서 동일한 모델
    • 인과 순서를 정의하면 메시지가 순서에 맞지 않게 전달되더라도 수행 순서를 재구성 할 수 있다
    • 백터 클럭: 이벤트 간의 부분 순서를 정의하고 여러 부분 순서 사이의 불일치를 해결하는데 쓰인다
  • 세션 모델: 클라이언트 관점에서 분산 시스템의 상태를 설명한 모델
    • 자신이 쓴 값 읽기: 읽기 작업에는 이전에 쓴 내용이 반영된다
    • 단조 읽기: 이미 읽은 값보다 더 이전에 쓴 값을 반환하지 않는다
    • 단조 쓰기: 하나의 클라이언트가 쓴 여러 값은 순서 그대로 다른 클라이언트에게 전파된다
    • 읽기 후 쓰기: 동일한 클라이언트의 쓰기 요청은 이전에 읽은 값을 쓴 작업 뒤에 배치한다
  • 결과적 일관성 모델: 시스템에서 비동기적으로 전파되고 데이터가 변경되지 않는다면으로 모든 읽기는 가장 최신값을 반환하는 일관성 모델
    • 일관성 조정
      • 복제 팩터(N): 데이터 복제본을 저장하는 노드 수
      • 쓰기 일관성(W): 쓰기 성공을 위해 응답해야 하는 노드 수
      • 읽기 일관성(R): 읽기가 성공하기 위해 값을 반환해야 하는 노드 수
    • [N/2] + 1 의 노드로 일관성 수준을 쿼럼(정족수) 라고 부른다
  • 강력한 결과적 일관성 모델
    • 선형화 가능성, 결과적 일관성 모델의 일부 장점을 모두 포함하는 모델
    • CRDTs: 충돌이 발생하지 않는 특수한 자료 구조
• 안티 엔트로피와 배포
  • 엔트로피: 분산 시스템에서는 노드 사이의 정보 불일치 정도를 나타낸다
  • 안티 엔트로피: 노드 동기화를 위해 누락되거나 충돌이 발생한 레코드를 비교 및 조정하는 프로세스
  • 브로드 캐스트: 한 프로세스가 전체 노드에 정보를 전달하는 방식
  • 안티-엔트로피 방식
  • 가십 전파
• 분산 트랜잭션
• 합의

• 논리 클럭: 단조 증가하는 카운터
• 물리 클럭(Wall Clock): 실제 현실 시간
• 백 프레셔: 프로듀서가 컨슈머가 요청을 처리할 수 있는 속도보다 빠른 속도로 메시지를 발행하는 경우 의도적으로 프로듀서의 속도를 늦추는 알고리즘. 분산 시스템에서는 잘 사용되지 않는다
• 백오프 전략: 재시도를 스케쥴링하고 요청 사이의 시간을 늘려 증폭 문제를 해결
• 지터: 백오프 기간에 짧은 임의의 시간을 추가해 여러 클라이언트가 동시에 재시도하는 현상을 해결